[bitc-dev] Fwd: Retrospective: The Issues with Type Classes
Jonathan S. Shapiro
shap at eros-os.org
Mon Apr 9 21:07:06 PDT 2012
Crud. This should have gone to the list.
Folks: there is no such thing as a stupid question. For every uncertain
question you have, be assured that four other people on the list are
wondering the same thing. Go ahead and ask on the list!
In fact, let's make it official: as a matter of policy, I am to blame for
the stupidity of any and all questions that appear on this list. There. You
are all officially off the hook. :-)
---------- Forwarded message ----------
From: Jonathan S. Shapiro <shap at eros-os.org>
Date: Mon, Apr 9, 2012 at 9:04 PM
Subject: Re: [bitc-dev] Retrospective: The Issues with Type Classes
To: Pal-Kristian Engstad <pal_engstad at naughtydog.com>
On Mon, Apr 9, 2012 at 5:59 PM, Pal-Kristian Engstad <
pal_engstad at naughtydog.com> wrote:
> This wasn't clear to me, as I haven't really followed this discussion.
> Would you mind explaining how bitc was to handle templated (generic)
> functions such as faux-add without using boxing/unboxing and passing hidden
> arguments to the generic function? Also, perhaps you could explain how you
> would deal with dynamic bitc libraries in this context?
I've actually explained this several times on the list. Here is the short
BitC proceeds in recursive-descent form. It starts with three sets:
ID the set of input definitions found in the source (some parametric,
RD the initially empty set of *reachable* definitions.
EP the set of (fully concrete) entry points from which the algorithm
these are the "roots" of instantiation.
The compiler proceeds in recursive-descent fashion, attempting to
instantiate the entry points. Before an entry point can be instantiated at
a concrete type, all of the things that it calls and/or uses must be
instantiated at concrete type. Discovery of dependencies proceeds top-down;
instantiation proceeds bottom-up. Instantiation proceeds as follows:
1. If an instantiation at that type exists in RD, stop. The needed
instance exists already.
2. If an instantiation at that type exists in ID (typically because the
procedure was fully concrete in the source program), move that
instantiation to RD and stop.
3. If some procedure in ID unifies with the desired instantiation, *
specialize* that procedure at the desired concrete type and place the
result in RD.
4. Otherwise, compilation fails
If every entry point instantiates successfully, compilation has succeeded.
This extends to libraries: each entry point into the library is placed in
EP, and off we go.
For *dynamic* libraries, we proceed as described above, but then emit a
library consisting of RD+ID+EP after instantiation has been completed. That
is: we pre-instantiate the library according to the specified entry points,
but retain all of the "unreached" and "uninstantiated" entries for later
There are some important optimizations on this that increase code sharing
by what might be termed "type lowering", but that's a separate discussion.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the bitc-dev