Re: mixing lush with clush

On Thursday 16 March 2006 11:00 pm, Yann LeCun wrote:
> Leon has thought about this quite a bit. He can't 
> do this by himself but would probably provide 
> advice to whoever would be bold enough to dive
> into such an undertaking.

Let me describe the kind of design I had in mind.

1) Runtime support library.
	- define the basic types.
	- define a garbage collecting method.
  
   Here is a first attempt at that (that I reused for the djvu project).
<http://cvs.sourceforge.net/viewcvs.py/djvu/djvulibre-3.5/libdjvu/miniexp.h>
<http://cvs.sourceforge.net/viewcvs.py/djvu/djvulibre-3.5/libdjvu/miniexp.cpp>
   and a proof that it can support a lisp system
<http://cvs.sourceforge.net/viewcvs.py/djvu/djvulibre-3.5/doc/minilisp/>

   Alas this is not good enough. The minivar system is too slow.
   I think the support library should be largely implemented
   as manipulations of a stack machine.  
   That would make the garbage collector a lot simpler.  
   That also facilitates step 2.

2) Define a bytecoded stack machine.
   One of the opcodes is an escape that calls 
   an arbirary C function with natural C arguments.

3) Implement the interpreter as a converter from lisp-expressions to bytecode.
   This can be written in lisp and converted to bytecode by bootstrapping.
   Benefits: we can have lexical scoping right away.

4) Implement a type analysis pass that, for each function, generates
   a set of prolog-like rules that represent the constraints on the types
   of arguments, return values, and intermediate values.

   Optional: part of the type analysis is the escape analysis, which
   determines which intermediate values can be returned from the function.
   Values that cannot be returned can be allocated on the C stack.
   Values that can be returned need to be garbage collected, 
   meaning that they must handled within the runtime stack machine.
   
5) When calling a function that has type information (step4), 
   use the argument types and the rule system to determine the type 
   of all the intermediate values.  Recurse on all functions called
   within that function.  Lookup if we already have a C translation
   of these functions with these specific argument types. 
   If not generate a C translation of the required functions 
   with the required argument types.

Note that each lisp function may have different C 
translations depending on the type of its arguments.
This is how we implement genericity.

The type analysis pass is akin to the dhm-t in the current compiler.
It may not be able to completely determine the type of everyhing.
Type declarations in the lisp code can help, but are not necessary.

The C code generation is similar to the dhm-c in the current compiler.
It uses the type information (and the escape information) to determine
whether one can open-code in natural C, or one needs to use the
runtime library to handle arbitrary typed objects at runtime.

This would be clean. 
But this is also a massive work.

- 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