closure and overload represention
Geoffrey Irving
ValClosure Var (List TypeVal) (List Value)
In order to call a closure, one has to look up the variable in
progOverloads, traverse through the Ptrie, and either call the result
if fully applied or create a new closure.
Here are several improvements we could make:
1. Replace the Var with a reference to the partially traversed Ptrie,
so that each new applied argument only has to traverse through one
Ptrie step, and (importantly) doesn't need access to progOverloads.
Unfortunately, the naive way of doing this would require making the
Ptrie's mutable, since we're now converting references into functions
into ValClosure at Ir -> Lir conversion time. This is worth some
thought to get right. It's clear that either some mutability or
access to a global (essentially mutable) map is required. For
example, we could load and compile a module defining a sum function,
which contains an internal reference to (+). Later we might load a
module of complex numbers, which defines another (+) overload. sum
needs to be able to access this overload. The same applies to
partially evaluated ValClosures created via constant folding.
2. Replace TypeVal with a thin TypeRep wrapper around an integer, and
provide a module that caches TypeVals into unique TypeReps.
3. Replace the lists with packed arrays. The result would look like
struct ValClosure {
Ptrie f;
size_t n;
TypeRep types[n];
Value value0;
Value value1;
....
}
Actually, it's better than that. By replacing "Ptrie f" with
"Something f" which provides more information, we can simply store
struct ValClosure {
Something f;
Value value0;
Value value1;
...
};
4. In order to make the Ptrie (or Something) part of ValClosure, we
need to be able to define it in duck, which means we have to have some
sort of Map in duck as well. The two main options are hashtables and
red black trees. Hashtables might make sense if we're going to make
the Ptries fundamentally mutable, especially since we can generate the
TypeRep's via a random number generator so they're automatically
excellent hash keys.
5. I'd been imagining that the caller code would contain logic for
whether adding one argument fully applies the closure, but we can
instead add stub functions which take the extra argument and append it
to make a new closure. There only needs to be one of these stubs per
sizeof(Value), so they won't generate code bloat.
On a separate note, we'll want to switch to imperative execution of
duck before writing the backend. This will remove the need to worry
about IOValue. IOValue wouldn't appear if we had effect types
anyways. In fact, effect types have the nice property that they have
no runtime representation whatsoever, so if we ever get around to
adding them it'll be purely at the type layer.
Geoffrey