Dictionaries are sometimes not necessary

[E.Ireland@massey.ac.nz]

Original-Via: uk.ac.nsf; Mon, 11 Mar 91 01:09:00 GMT
Date: Mon, 11 Mar 91 14:03:21 NZD
From: E.Ireland@massey.ac.nz
To: kh <kh%cs.glasgow.ac.uk@massey.ac.nz>, haskell@edu.yale.cs
In-Reply-To: Kevin Hammond's message of Thu, 28 Feb 91 22:31:55 GMT <11392.9102282231@tuvula.cs.glasgow.ac.uk>
Subject: Dictionaries are sometimes not necessary
Sender: haskell-request@cs.glasgow.ac.uk

I will attempt to answer Kevin's questions with an example.

> To implement this, you will need to construct the call-graph for an
> entire program, and traverse it multiple times (for the different
> uses).  This seems quite an expensive proposition.  I suspect this will
> be impractical for non-trivial programs, unless you can find a cheap
> solution [in which case, let us know, we have some problems in partial
> evaluation that could use this].
> 
> 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

    a :: Int
    a = 1

    b :: Integer
    b = 2

    main = print (show (f [1..3] a) ++ show (f [1..2] b))

(This should print "44" when run).

In my proposal, I would compile four functions (f, a, b, main).  When this
module is linked with the standard library, I would generate closure-building
code to be executed once at program startup.

Let "f.t" denote a closure generated for function f, specialised for type t.
So "length.Int" would be a closure for function length with result type Int.

We can simply generate the closures "a" and "b".  Assume that when f is
compiled, we generate a template for its free variables (I call this a
dependency list).  Note the ".a" indicates a type variable.

	"f.a"		"length.a"
			"+.a"

And the dependency list generated for main will be:

	"main"		"print"
			"show.Int"
			"f.Int"
			"a"
			"show.Integer"
			"f.Integer"
			"b"

I will ignore the "show" closures, as they are handled in the same way as "f".
To generate a closure for "main", we require "f.Int" and "f.Integer".  But we
have no such closures.  We can, however, generate them from the template:

	"f.Int"		"length.Int"
			"+.Int"

	"f.Integer"	"length.Integer"
			"+.Integer"

"+.Int" and "+.Integer" would be provided by the Prelude.  Assume that length
is defined as below (module PreludeList defines it differently, but I don't
want to introduce another function, foldl, into my example).

    length []     = 0
    length (x:xs) = 1 + length xs

The dependency list for length would be:

	"length.a"	"length.a"
			"+.a"

And so we can use this to generate the required closures for length:

	"length.Int"		"length.Int"
				"+.Int"

	"length.Integer"	"length.Integer"
				"+.Integer"

Thus generation of closures would proceed in a top-down fashion, starting with
the dependency list for main, and generating closures according to main's free
variables (and their dependency lists, etc.)  Templates would be expanded where
necessary, which may result in more closures needing to be generated.  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.

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.

Oh well, this has been a rather long message.  Bye.
_______________________________________________________________________________

E.Ireland@massey.ac.nz          Evan Ireland, School of Information Sciences,
  (063) 69-099 x8541          Massey University, Palmerston North, New Zealand.