Re: Designing a calling convention for a Lisp->C compiler

Robbert Haarman <comp.compilers@inglorion.net>
Mon, 7 Jun 2010 05:28:51 +0200

          From comp.compilers

Related articles
Designing a calling convention for a Lisp->C compiler msimoni@gmail.com (Manuel) (2010-06-03)
Re: Designing a calling convention for a Lisp->C compiler marc@lithia.nl (Marc van Lieshout) (2010-06-03)
Re: Designing a calling convention for a Lisp->C compiler kym@sdf.lonestar.org (russell kym horsell) (2010-06-04)
Re: Designing a calling convention for a Lisp->C compiler kym@sdf.lonestar.org (russell kym horsell) (2010-06-06)
Re: Designing a calling convention for a Lisp->C compiler cr88192@hotmail.com (BGB / cr88192) (2010-06-06)
Re: Designing a calling convention for a Lisp->C compiler comp.compilers@inglorion.net (Robbert Haarman) (2010-06-07)
Re: Designing a calling convention for a Lisp->C compiler gene.ressler@gmail.com (Gene) (2010-06-06)
| List of all articles for this month |

From: Robbert Haarman <comp.compilers@inglorion.net>
Newsgroups: comp.compilers
Date: Mon, 7 Jun 2010 05:28:51 +0200
Organization: Wanadoo
References: 10-06-008 10-06-010
Keywords: Lisp, translator, code
Posted-Date: 09 Jun 2010 19:02:09 EDT

In addition to what Russel said, I would like to add that the problem
is more complex than deciding on a way to map Lisp function calls to C.


Depending on the features of the Lisp you are implementing, you will also
need to account for things like:


  - Closures. How will you represent a procedure that closes over
      variables from its lexical scope?


  - Conditions and restarts. How will you invoke condition handlers, and
      how do you implement restarts such as abort, continue, and use-value?


  - Continuations. How will you save and restore the activation frames that
      existed at the time the continuation was created?


  - Debugging. Will there be a debugger? What features will it have and
      how will you implement those?


  - Evaluation of forms not in the original program. How will you support
      things like eval and load?


  - Garbage collection. How does your calling convention interact with
      your garbage collector?


  - Tail recursion. Will you perform tail call optimization? If so, how
      will you implement that?


  - Throw and catch. Will you implement these, and, if so, how?


All these issues could influence your choice of calling convention. What
I have ended up doing in the past is:


  - Call frames are allocated on the heap.


  - Arguments, closed-over variables, and local variables each go in arrays.


  - A closure is represented as a data structure containing both a pointer
      to its code and a pointer to its closure environment.


  - Calling a closure consists of creating and populating the argument
      array, storing a pointer to it, a pointer to the closure environment,
      and the return address in thread-local variables, and jumping to the
      closure's code.


  - Continuations can be represented by closures that restore the local
      environment, closure environment, argument array, call chain, and
      return address that existed when the continuation was created, then
      jumping to the return address. "Restoring" here really involves
      copying a couple of pointers out of the continuation into thread-local
      variables.


  - Continuations can be used to implement conditions/restarts and throw/catch.


  - The garbage collector will take care of reclaiming arrays that are
      no longer reachable while keeping around those that may still be needed.


  - Tail calls are optimized by linking the new call frame to the parent
      call frame instead of the current call frame, so that the current call
      frame may be collected by the garbage collector (unless, of course,
      a reference to it is kept in a continuation or such).


This calling convention is probably not the most efficient and it is utterly
unlike C's, but it can cope with most if not all of the challenges in
compiling Lisps. I would like to reiterate what Russel said: there is a lot
of literature pertaining to compiling languages like Common Lisp,
Standard ML, and Scheme, and you could benefit a lot from reading that. One
place to start could be http://www.readscheme.org/


Good luck!


Bob



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.