Re: Hi! Interested in GSoC. Feedback on these ideas?

[Mark H Weaver]

Paul Raccuglia <address@hidden> writes:
> - AOT Compiler: write an interface to GCC
> I think this would be really cool. A good plan would be to use GCC,
> because it's already pretty sophisticated and handles lots of
> architectures. I would start by writing a scheme interface to GCC, and
> then writing the compiler in scheme.

There is one _very_ serious problem with using GCC to compile Scheme, or
at least there was the last time I researched this issue: tail calls.
Although GCC has long been able to do tail call optimization in some
limited situations, standard C calling conventions prevent tail calls
from being done consistently in the general case.

The fundamental problem is that in C, the caller of a function is
responsible for popping the arguments off the stack after the call
returns.  This is required to support normal C varargs behavior, where
the callee does not necessarily know how many parameters were passed to
it, and therefore does not know how many parameters to pop.

In Scheme, which requires tail calls, it is the caller that does not
know how many parameters to pop, because the function which returns will
not necessarily be the same one originally called.  For example:

  (define (main)     (foo 5))
  (define (foo a)    (bar a a))
  (define (bar x y)  y)

If this is implemented with standard C calling conventions, main pushes
one argument (et al) on the stack before calling (foo 5), and then pops
one argument (et al) after it returns.  But it is (bar 5 5) that returns
to main, and so actually two parameters must be popped.

Many people have worked on this issue over the years, but in GCC (and
probably other C compilers) the assumptions about calling conventions
are very deeply ingrained, and last I checked, no one has found any
feasible solutions, short of making procedure calls through a
trampoline, or doing the "Cheney on the MTA" trick that Chicken does.

See http://users.cecs.anu.edu.au/~baueran/thesis/ for a detailed
analysis of possible strategies to properly support tail calls in GCC
circa 2003.  (If anyone has more recent information, please do share!)

> I noticed a relevant (but now dead) project to write a GCC scheme
> compiler : http://gna.org/projects/gsc  ; they started in '05 and died
> by '06, but I think it would help me think through the process to look
> at what other people did.

The first thing I would check is how they deal with tail calls.  Some
so-called Scheme implementations do not implement tail calls
consistently (though they may do this "optimization" in some limited
cases).  I strongly believe that this is not good enough for Guile, nor
any other implementation that rightly calls itself Scheme.

Anyway, thanks for looking into this!

     Best,
      Mark