Scheme front end for egcs.

Scheme front end for egcs.

[Matthias Hoelzl tc]

I am currently trying to find out whether it would be possible for
me to write a Scheme front end to the gcc/egcs compiler.  

Right now I have figured out how to set up the Makefiles, etc. to add
a new front end to egcs, and I have built a simple compiler that
handles arithmetic functions in Scheme syntax.  But I am unsure how to
deal with some important topics for compiling Scheme:

Scheme requires functions to be properly tail recursive and many
programs rely on this.  Therefore the Scheme equivalent to the
following program

int
main(int argc, char** argv)
{
  a(0);
  return 0;
}

void
a(int i)
{
  if ( i < 100 )
    b(i + 1);
  else
    b(0);
}

void
b(int i)
{
  a(i + 1);
}

should loop indefinitely (instead of overflowing the stack).  However,
unless I am missing something, implementing proper tail recursion is
rather difficult with the current calling convention.  It seems that
support for tail calls might best be implemented by adding some
extensions to the back end; on the other hand complicating the back
end to add support for one not very widely used language might not be
such a good idea.  Robert Strandh has already discussed this topic
with RMS and they reached the conclusion that one of the following
calling conventions should be implemented in addition to the existing
one (quoted from Robert's email):

>	1. (the one I prefer, but RMS thinks is too complicated, I
>	   think the other one is complicated as well)  The calling
>	   convention for Scheme compatible functions would be
>	   completely altered so that the arguments are allocated in
>	   the callee's stack frame the difference between sp and fp
>	   would determine argument count.
>
>	2. (the one RMS prefers) An additional invisible argument is
>	   supplied indicating the argument count (must be the first
>	   argument) and the calling convention is altered so that the
>	   caller does not remove the arguments after the call is
>	   completed.  Tail calling involves tricky manipulation of
>	   the stack frame such as growing or shrinking the area used
>	   for arguments. 

To which I'll add

3. Have a different stack for Scheme->Scheme calls, generate
   tree/rtl instructions to manage this stack directly in the 
   front end and use the "C-stack" only to call non-Scheme functions.  
   This would also ease the handling of first-class continuations, but 
   seems rather inelegant otherwise.  Would the back end be able to
   do register allocation, etc. for Scheme code that basically looks
   like one enormous function?

Personally I would prefer option 1, but I would be interested in your
opinions.  How would different calling conventions be reflected in the
tree language?

Scheme has first-class continuation which require some manipulations
of the stack.  Is there a portable way to find the base of the stack,
to walk the stack and to copy parts of the stack to/from the heap?


Regards,

  Matthias

Re: Scheme front end for egcs.

[Jeffrey A Law]

  In message < 873efv83lo.fsf@gauss.muc.de >you write:
  > Scheme requires functions to be properly tail recursive and many
  > programs rely on this.  Therefore the Scheme equivalent to the
  > following program
Ouch.  Yup, that's going to be tough.  There were some patches (I 
still have them) to implement a more general tail call optimization,
but they need serious work before they'd be useful.  Even so, they
may not be complete enough to help with your problem.


  > Personally I would prefer option 1, but I would be interested in your
  > opinions.  How would different calling conventions be reflected in the
  > tree language?
Can't really comment on the different conventions, I don't have the
time to sit down and analyze them in detail.

Calling conventions are not generally represented at the tree level
other than to say "this call has these args" and "this function
expects these args".  The details of where to put args are controlled
by FUNCTION_ARG and related macros.   Look in calls.c (caller) and
function.c (callee).

  > Scheme has first-class continuation which require some manipulations
  > of the stack.  Is there a portable way to find the base of the stack,
  > to walk the stack and to copy parts of the stack to/from the heap?
Not really.  Just walking the stack is tough enough :-)  Just ask the
C++ folks doing exception handling.

jeff

Re: Scheme front end for egcs.

[Per Bothner]

I too am planning to compile Scheme using gcc.  However, I am planning
a two-stage approach:

1) Compile Scheme to Java bytecodes using Kawa.
See http://www.cygnus.com/~bothner/kawa.html .

2) Compile Java bytecodes to native codes using jc1.
See http://www.cygnus.com/product/javalang/ .

Currently, Kawa does not handle full tail-call-elimination and
continuations.  Using jc1 to compile the bytecodes does not change
that.  There are two approaches I am considering:

a) Have Kawa generate explicit "activation frame" objects.  I won't go
into details, but there is a well-known technique (used in RScheme, for
example) to simulate full tail-call-elimination and continuations
in a language/environment without them.  I have been working on such
a design for Kawa, and I think it can be made reasonably effcicient.
This has the advantage that proper tail-calls are handled in all
Java implementations.

b) Extend Gcc to support a modified calling convention, as you discuss.
Have Kawa emit an annotation (attribute) requesting tail-call
elimination.  Modify jc1 to use the new calling convention when it sees
that attribute.  This will probably provide better efficiency, but has
the disadvantage that you only get proper tail-calls on extended Java
implementations.

The ideal solution supports both.  Kawa can take a flag specifying how
it should handle tail-calls, and the user (or a Makefile) can select
the appropriate strategy depending on the environment.  (My preliminary
design allows mixing the two Kawa calling conventions at the same time.)

	--Per Bothner
Cygnus Solutions     bothner@cygnus.com     http://www.cygnus.com/~bothner