Re: First go at inferring type

On Tuesday 28 March 2006 02:54, Yury Sulsky wrote:
> Gah sorry, my e-mail got sent half-way.
> Here's what I meant to write in the second-to-last part:

Hem. 
It might not be sufficient to infer the prototype of a function,
because you also need the types of subexpressions inside
in order to declare local variables, etc.
You probably do it inside though.

Here is a formalization:

Suppose that you have 'type variables' attached to each expression inside a function.
The various expressions inside the function allow you to express 'constraints' on these type variables.
Suppose you can express these constraints in first order logic (think prolog!).

When you have type declarations inside the functions, you simply add new constraints.
When you call another function, you copy their constraints into your set of constraints.
When you call the function with some specific arguments, you simply add new constraints.
Then you simplify the set of constraints into a DNF (or .. (and ..) (and ..) (and ..)).
Each (and...) suggests a major C variant of the function and specify its types.
Remaining type variables at this point should be handled as unknown types,
and the corresponding values should be wrapped into full lisp objects.

In fact I think one should use an algorithm named 'EBG'  (explanation based generalization).
Instead of adding new constraints when you call the function with specific argument types,
you can use EBG to compute the broadest set of constraints representing the capabilities of 
the C function compiled for the requested argument types. This is what should be saved
with the C function in order to determine when it can be reused.

- L.


-------------------------------------------------------
This SF.Net email is sponsored by xPML, a groundbreaking scripting language
that extends applications into web and mobile media. Attend the live webcast
and join the prime developer group breaking into this new coding territory!
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642