Hi,

  Could you recommend me some papers on constructing a stackless
compilers? I can only find lots of links about Stackless Python, but I
am more interested in combination of PI calculus and lambda calculus.
I know about CubeVM, but that's just pure PI calculus, and it directly
evaluates AST. I would like to read something about compiler design
for stackless language, but could not find anything.

Thanks,
  Karol

On Tue, 1 Jul 2008 05:13:52 -0700 (PDT)

I suppose what you mean by stackless languages are languages that do
not make use of a run-time stack in their execution, such as Stackless
Python or some implementations of Scheme and Lisp.  Such languages
invariably make use of transformations to continuation-passing style
and must support tail calls, closures, and automatic garbage collection
to be useful, and as such Scheme is one of the first major languages for
which such an approach was practical. An early example of such a
compiler was Guy Steele's Rabbit compiler for Scheme [1], which used
CPS transformations extensively. Steele also wrote about this method of
designing compilers in the famous paper "Debunking the Expensive
Procedure Call Myth, or, Procedure Call Implementations Considered
Harmful, or Lambda: The Ultimate GOTO" [2]. Other useful resources
describing this approach to building a compiler are a paper by Richard
Kelsey and Phil Hudak: "Realistic Compilation by Program
Transformation" [3], and the ORBIT Scheme compiler by David Kranz [4].
I think looking for resources on continuation-passing style
transformations and their use in compiler design will be more fruitful
than using 'stackless' as your keyword.

[1] http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AITR-474.pdf
[2] http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf
[3] http://citeseer.ist.psu.edu/179975.html (link down at the moment)
[4] http://repository.readscheme.org/ftp/papers/orbit-thesis.pdf

--
http://stormwyrm.blogspot.com

It is not clear whether you want the compiler itself to not use a
stack or the generated code to not use a stack?  In the latter case,
are you limited to static memory allocation or can you allocate on a
heap?

SML of New Jersey doesn't use a stack but places everything on the
heap -- closures, activation records, data structures etc.  The
motivation was that by using a single shared area, you are more
flexible and that by using a good GC, heap management isn't
(considerably) more expensive than stack management.  Since the
compiler is bootstrapped, both compiler and target code are stackless.

Many Scheme compilers use a similar strategy, as they have to support
call/cc, which makes simple stacks unsuitable.

        Torben

See: "Compiling with Continuations" by Andrew W. Appel.  A bit dated
by now, but still accurately describes the fundamental implementation
philosophy used by the SML/NJ compiler (www.smlnj.org).

Matthias