Stackless compilers? - Compilers

This is a discussion on Stackless compilers? - Compilers ; 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 ...

+ Reply to Thread
Results 1 to 4 of 4

Stackless compilers?

  1. Default Stackless compilers?

    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


  2. Default Re: Stackless compilers?

    On Tue, 1 Jul 2008 05:13:52 -0700 (PDT)
    neptundancer <Karol.Skocik@gmail.com> wrote:
    > 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.


    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...s/AITR-474.pdf
    [2] http://repository.readscheme.org/ftp...bs/AIM-443.pdf
    [3] http://citeseer.ist.psu.edu/179975.html (link down at the moment)
    [4] http://repository.readscheme.org/ftp...bit-thesis.pdf

    --
    http://stormwyrm.blogspot.com

  3. Default Re: Stackless compilers?

    neptundancer <Karol.Skocik@gmail.com> writes:


    > 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.


    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

  4. Default Re: Stackless compilers?

    Rafael Sevilla <dido@imperium.ph> writes:

    > On Tue, 1 Jul 2008 05:13:52 -0700 (PDT)
    > neptundancer <Karol.Skocik@gmail.com> wrote:
    >> Could you recommend me some papers on constructing a stackless
    >> compilers? ...


    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


+ Reply to Thread