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

Dictionaries are sometimes not necessary


I don't think I have replied yet to your message which starts:

> 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...

    f :: Integral a => [b] -> a -> a
    f x y = length x + y

This would be compiled to:

    Function "f" [
     Local 1,	-- fetch x from argument stack
     Global 1,	-- fetch "length" closure from current closure
     Apply 1,	-- length x
     Local 1,	-- fetch y from argument stack
     Global 2,	-- getch "+" closure from current closure
     Apply 2,	-- length x + y

The "current closure" refers to the closure for the currently active function.
This closure would have been generated once at program startup.  In my earlier
message I said that we might generate several closures for "f", e.g. "f.Int",
"f.Integer".  All would share the same function.  When compiling "f", we do not
need to know what instances of it will be required by any program using "f",
since the code is independent of the actual values of its free variables.

As far as stack and heap usage is concerned, function arguments (e.g. x and y)
are passed on an argument stack, and free variables (e.g. "length" and "+") are
fields of heap-allocated closures (but these are only allocated once for
functions defined at the outermost lexical level).

Your other example is tricker (thanks, I needed that)!  Let me simplify it

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

Any difficulty here is also present in:

    main = print (map (f "hello") [1,2,3])

My compiler would treat this as:

    main = print (map (\ y -> f "hello" y) [1,2,3])

Assuming that we have default Int (to resolve the ambiguous integer literals),
and we do a bit of type analysis:

    map				     :: (a -> b) -> [a] -> [b]
    \ y -> f "hello" y		     :: Integral a => a -> a
    map (\ y -> f "hello" y) [1,2,3] :: [Int]
    \ y -> f "hello" y		     :: Int -> Int, in this particular instance

When compiling main, we determine that one of its free variables should be
"f.Int".  If the program had been written as:

    g :: Integral a => a -> a
    g y = f "hello" y

    main = print (map g [1,2,3])

We would determine that one of main's free variables should be "g.Int", and the
dependency list generated for "g" would be:

    "g.a"	"f.a"

Thus to generate a closure for "g.Int", we would have to generate a closure for

The above analysis can be performed independently of the compilation of
functions such as "f" and "map".  I should mention, however, that the
generation of closure-building code for a Haskell program is carried out in the
program linking stage, and requires access to dependency lists for all of the
modules being linked together.  These dependency lists are generated
automatically by the compiler.

I would appreciate any more tricky examples that you have encountered.  Still I
hope that my scheme is implementable!


E.Ireland@massey.ac.nz          Evan Ireland, School of Information Sciences,
  +64 63 69099 x8541          Massey University, Palmerston North, New Zealand.