Re: A Lisp compiler?

[tc@gauss.muc.de (Matthias Hölzl)]

Ken Raeburn <raeburn@cygnus.com> writes:

> Two thoughts:
> 
>  1) Consider targeting languages that would be helpful to the GNU
>     project, like Emacs Lisp or (better, IMHO) Guile, which is Scheme
>     based.

I am surely biased since I am one of the maintainers of d2c, but
another good choice would be the Dylan language.  Dylan is
semantically very close to Common Lisp/CLOS, but written in algebraic
notation.  Unlike CL which pretty much supposes some "image-based"
implementation if you want to support the whole language, Dylan was
designed to allow efficient batch compilation.  This means that the
language is slightly less dynamic, but it is much better suited to
compile into stand-alone executables.

There is a free Dylan to C compiler available and actively maintained,
and a lot of libraries exist or are in development (see our site at
www.gwydiondylan.org).  D2c supports a fairly good C-FFI and is
designed to allow for multiple back-ends, so it should not be too hard
to write an additional back-end that interfaces d2c to egcs.

If you want to write a Common Lisp front-end you should have a look at
the code available from www.cons.org; especially the CMUCL compiler is
a very well written piece of software and it is in the public domain,
so you might be able to reuse a lot of its code.  I think that it
might be a good idea to use their ICR or maybe even the low level IR
as the starting point for a CL egcs front end.

If you want to write a Scheme front end you may want to look at the
bigloo Scheme to C compiler.  It has a very clean internal structure,
some nice extension like a built in lexer/parser generator and its
author is generally very helpful.

>  2) Translating to C would likely be easier; do you gain much by
>     compiling directly?  The generated C code can even be
>     platform-independent, meaning it could be shipped along with the
>     original lisp source for those who don't have the lisp compiler.
>     (E.g., in the Emacs or Guile distributions.)

For CL or Dylan compiling to C is an attractive solution for a batch
compiler.  The main disadvantage seems to be the increased compilation
time.  However, AFAIK, it is virtually impossible to compile Scheme to
C and still be fully conforming to R5RS since Scheme is "properly tail
recursive", which means that cycles of function calls like f -> g -> h
-> f are not allowed to consume stack space if all the calls are made
in tail position.  E.g.

(define (f x) (g x 1))
(define (g x y) (if (= y 2) x (h 3)))
(define (h x) (f 42))

(f 0)

has to loop indefinitely without running out of space.  All Scheme to
C compilers that I am familiar with only guarantee tail call
elimination on self tail calls.  It seems that in order to provide
full tail recursion you'd have to compile the whole program into one
large C function and implement function calls via gotos (which makes
callbacks from external libraries very hard).

Regards,

  Matthias