New Common Lisp, Lisp-to-C translation, Lisp library for C
Robert Munyer
In article <31B5FBFA...@elwoodcorp.com>,
"Howard R. Stearns" <how...@elwoodcorp.com> wrote:
> [...] the Eclipse compiler can be used to generate human-readable
> C code which uses the library. The generated functions and variables
> use normal C naming and argument passing conventions. [...]
How does this compiler handle tail recursion?
Howard R. Stearns
I. There are effectively three compilers involved:
A. Eclipse produces byte code by default. The byte-code compiler does
the usual jump rather than call for all tail position function calls.
B. Eclipse can produce C code. The emphasis is on being readable and on
being as efficient as hand written C code, not on being BETTER than hand
written C code. To this end, there is one C function for each Lisp
function. Obvious self recursive calls GOTO the beginning of the
function, but other function calls, tail position or otherwise, become
normal C function calls.
C. A user supplied C compiler is used to compile the C code, whether that
compiler handles tail recursion is a matter for the C compiler vendor.
II. Note that unlike Scheme, Common Lisp does not require tail recursion
elimination. Specifically, tail recursive functions do not need to run in
constant stack space. This is why Common Lisp provides so many iteration
constructions that Scheme does not.
W.K. Woelbeling
"Howard R. Stearns" <how...@elwoodcorp.com> wrote:
>Robert Munyer wrote:
>>
>> In article <31B5FBFA...@elwoodcorp.com>,
>> "Howard R. Stearns" <how...@elwoodcorp.com> wrote:
>> > [...] the Eclipse compiler can be used to generate human-readable
>> > C code which uses the library. The generated functions and variables
>> > use normal C naming and argument passing conventions. [...]
>>
>> How does this compiler handle tail recursion?
>I. There are effectively three compilers involved:
> A. Eclipse produces byte code by default. The byte-code compiler does
> the usual jump rather than call for all tail position function calls.
> B. Eclipse can produce C code. The emphasis is on being readable and on
> being as efficient as hand written C code, not on being BETTER than hand
> written C code. To this end, there is one C function for each Lisp
> function. Obvious self recursive calls GOTO the beginning of the
> function, but other function calls, tail position or otherwise, become
> normal C function calls.
Are you sure about this? C fully supports recursion. What is this
'self recursive' thing? I thought that recursive functions required
that they make a call to themselves at some point in their design.
> C. A user supplied C compiler is used to compile the C code, whether that
> compiler handles tail recursion is a matter for the C compiler vendor.
Does eclipse recommend a specific compiler? I have had some problems
porting code (C) from compiler to compiler with hand generated code.
It could be a nightmare to try and port autogenerated code.
>II. Note that unlike Scheme, Common Lisp does not require tail recursion
>elimination. Specifically, tail recursive functions do not need to run in
>constant stack space. This is why Common Lisp provides so many iteration
>constructions that Scheme does not.
Bill Woelbeling
SIUC-CS
Erik Naggum
[W.K. Woelbeling]
| Are you sure about this? C fully supports recursion. What is this
| 'self recursive' thing? I thought that recursive functions required
| that they make a call to themselves at some point in their design.
(defun oddp (n) (if (zerop n) nil (evenp (1- n))))
(defun evenp (n) (if (zerop n) t (oddp (1- n))))
these functions are recursive but not self-recursive. in Scheme, they will
be implemented with jumps. in C, they will be function calls consuming
stack resources, unless special provisions are made.
--
IRC/EFnet: gamlerik
Howard R. Stearns
W.K. Woelbeling wrote:
>
> "Howard R. Stearns" <how...@elwoodcorp.com> wrote:
>
> >Robert Munyer wrote:
> >>
> >> In article <31B5FBFA...@elwoodcorp.com>,
> >> "Howard R. Stearns" <how...@elwoodcorp.com> wrote:
> >> > [...] the Eclipse compiler can be used to generate human-readable
> >> > C code which uses the library. The generated functions and variables
> >> > use normal C naming and argument passing conventions. [...]
> >>
> >> How does this compiler handle tail recursion?
>
> >I. There are effectively three compilers involved:
> > A. Eclipse produces byte code by default. The byte-code compiler does
> > the usual jump rather than call for all tail position function calls.
> > B. Eclipse can produce C code. The emphasis is on being readable and on
> > being as efficient as hand written C code, not on being BETTER than hand
> > written C code. To this end, there is one C function for each Lisp
> > function. Obvious self recursive calls GOTO the beginning of the
> > function, but other function calls, tail position or otherwise, become
> > normal C function calls.
>
> 'self recursive' thing? I thought that recursive functions required
> that they make a call to themselves at some point in their design.
Erik Naggum has answered this in another thread.
>
> > C. A user supplied C compiler is used to compile the C code, whether that
> > compiler handles tail recursion is a matter for the C compiler vendor.
>
> Does eclipse recommend a specific compiler? I have had some problems
> porting code (C) from compiler to compiler with hand generated code.
> It could be a nightmare to try and port autogenerated code.
On each platform, we test with the vendor compiler and with gcc from the Free
Software Foundation.
Compiler and other platform peculiarities are addressed in the library and header
file, not in the generated code. The web site,
http://www.elwoodcorp.com/eclipse.htm, describes both general (eg., K&R vs ANSI, etc.)
and specific (eg., limits on length of external C identifiers) expectations on the C
compiler.
FLAME BAIT: One of the great myths of C is that it is portable. It is true that
some C code is portable (and we hope we've acheived that with the generated code),
but it is certainly also true that C compilers will allow you to develop very
unportable applications which work only on the system they were developed on.
Common Lisp was carefully designed to avoid or define issues which C left open.
Here's an example. In C, the order of evaluation of arguments to a function is
not defined. Some compilers go left-to-right, others go right-to-left, still others
might vary depending on register contents, optimization switches, etc. By contrast,
Common Lisp specifies left-to-right evaluation. When Eclipse compiles Lisp code
to C, it separates out the arguments into temporary variables which are assigned in
well ordered statements. Thus the generated code does not depend on the ordering
chosen by the compiler.
(Before everyone gets grossed out, I should point out, regarding:
ugliness: that temporary variables are not created by the Eclipse compiler if
it can prove that the reference has no side effects and isn't
effected by other argument expressions. For example, (FOO A (BAR B 2))
will not use temporary variables (unless A or B are declared special).
efficiency: a good C compiler can eliminate the remaining temporary variables.
The temporaries effectively become a declaration to the C compiler
to use the proper ordering of evaluation, rather than an actual
storage requirement.)
There are, of course, other examples, including pointer nonsense, integer encoding,
setjmp behavior, etc. The bottom line is that not all C code
is portable, but all C code generated by the Eclipse compiler IS. (Subject
to the restrictions described on the website.) Valid Common Lisp
code is pretty darn portable, and so should the C code generated from it. We
can take up the issue of libraries on another day....
Marty Hall
In article <31C6B691...@elwoodcorp.com> "Howard R. Stearns"
<how...@elwoodcorp.com> writes:
> When Eclipse compiles Lisp code
> to C, it separates out the arguments into temporary variables which
> are assigned in well ordered statements. Thus the generated code
> does not depend on the ordering chosen by the compiler.
>
>(Before everyone gets grossed out, I should point out, regarding:
> ugliness: that temporary variables are not created by the Eclipse compiler if
> it can prove that the reference has no side effects and isn't
> effected by other argument expressions.
Obviously, in general you can't prove whether or not a function has
side effects (unless you've figured out how to solve the halting
problem :-), but Eclipse is doing much more limited reasoning here.
> For example, (FOO A (BAR B 2))
> will not use temporary variables (unless A or B are declared special).
I don't see why it matters if B is declared special. Also, I could
imagine pathological cases where BAR is really a macro that expands
into a form that changes A where it would make a difference if
(BAR B 2) were evaluated first, even though A is not special.
Assumedly Eclipse checks for this or is only operating at this point
on forms with macros already expanded.
- Marty
(proclaim '(inline skates))
<http://www.apl.jhu.edu/~hall/lisp.html>
Henry Baker
In article <31C56FDA...@elwoodcorp.com>, "Howard R. Stearns"
<how...@elwoodcorp.com> wrote:
> Robert Munyer wrote:
> >
> > In article <31B5FBFA...@elwoodcorp.com>,
> > "Howard R. Stearns" <how...@elwoodcorp.com> wrote:
> > > [...] the Eclipse compiler can be used to generate human-readable
> > > C code which uses the library. The generated functions and variables
> > > use normal C naming and argument passing conventions. [...]
> >
> > How does this compiler handle tail recursion?
You might have a look at the following paper:
ftp://ftp.netcom.com/pub/hb/hbaker/CheneyMTA.html (also .ps.Z)
also
ftp://ftp.netcom.com/pub/hb/hbaker/cboyer13.c
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
Mark Tillotson
> > For example, (FOO A (BAR B 2))
> > will not use temporary variables (unless A or B are declared special).
>
> I don't see why it matters if B is declared special. Also, I could
How about
(defvar *count*)
(defun foo () (incf *count*))
(defun bar () (let ((*count* 0)) (baz *count* (foo) *count*)))
Raffael Cavallaro
I think there's a small terminology problem. A function which calls itself
is said to be recursive. Two functions which call *each other* are said to
be "mutually recursive." I don't believe that there is a term "self
recursive." Indeed, it would be redundant, since recursive means "calls
itself."
In the example below, oddp and evenp are *mutually recursive*, because
each calls the other.
-----------------------------
In article <30440891...@arcana.naggum.no>, Erik Naggum
<er...@naggum.no> wrote:
> [W.K. Woelbeling]
>
> | Are you sure about this? C fully supports recursion. What is this
> | 'self recursive' thing? I thought that recursive functions required
> | that they make a call to themselves at some point in their design.
>