[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Dictionaries are sometimes not necessary



> > Also, how do you solve the "dictionary transfer problem", as shown by:
> 
> Assume that we are compiling the Haskell program below:
> 
>     f :: Integral a => [b] -> a -> a
>     f x y = length x + y

>  [... example showing parameterised closures for f, instantiated to
>       the types actually used...]

I'm still interested in the code you would generate for f (say in a
separately compiled module).  From what you've said, it sounds as if
you would pass parameters for each operation specialised to a given
type.  The relative costs are debatable, but I would expect such a
solution to consume more stack, and perhaps heap, than the dictionary
solution which passes one parameter per class.  Maybe you have a more
elegant solution, though (delay some or all code generation, maybe)?
Or maybe the costs balance out in your implementation?

Also, how would this work with polymorphic uses such as maps, e.g.

	main = print (map (f "hello") [1,2,3], map (f "goodbye") [4,5,6])

I think you need to construct some kind of parameterised call graph
(the partial applications are a slight pain, I know).  I assume you can
avoid having to examine the code for "map" (for separate compilation you
don't want to look at the module implementation, only the interface)?

> I believe that termination of this process would be guaranteed by the static
> nature of Haskell programs, and that generation of the closure-building code
> would take time in proportion to the number of closures that must be generated.

Yes, this sounds likely.  The time required for code generation (and object
code size) will not be in general be linear in the number of source functions,
however, unless these are non-overloaded.

> I wonder if this, at least in part, helps to answer Satish Thatte's question:
> 
> | The question really is: how workable is the dictionary-passing style
> | *in general*, e.g., for languages that are *not* lazy.  Since the
> | classes idea has nothing to do with laziness, it would be nice to find
> | an implementation that does not rely on laziness for its viability.
> 
> This approach should work just as well for strict languages.  Dictionaries are
> not explicit, but are implicit in the generated closures.

I hadn't realised dictionaries relied on lazy evaluation -- dictionaries are
static objects and the dictionary hierarchy may be traversed by functions
which are guaranteed to terminate.  Can someone explain the problem, please?

Regards,
Kevin

PS	I hope you find these comments constructive...