[chicago-lisp] (no subject)

[dkixk at earthlink.net]

-----Original Message-----
>From: John Quigley <jquigley at jquigley.com>
>Sent: Dec 8, 2006 12:29 PM
>To: Chicago LISP <chicago-lisp at common-lisp.net>
>Subject: Re: [chicago-lisp] (no subject)
>
>That some Common Lisp implementations have poor support for optimized 
>functional usage is an unfortunate, but rather irrelevant, point for me. 
>When I need highly optimized code, I develop in C. 

This has nothing to do with "highly optimized code" in the sense of C being optimized.  That is, tail-call optimization is not important because of its impact on run-time performace.  Consider the two following versions of a naive REPL.  One, I call CL because it uses LOOP, which does not exsit in Scheme, and one I call Scheme, because it uses recursion instead of iteration.

(defun cl-repl ()
  (loop for cmd from 1
        do
        (format t "~&~A> " cmd)
        (princ (eval (read)))))

(defun scheme-repl (&optional (cmd 1))
  (format t "~&~A> " cmd)
  (princ (eval (read)))
  (scheme-repl (1+ cmd)))

And lets see what happens when we run them in a CL image.

PG-USER> (cl-repl)
1> nil
NIL
2> (list 1 2 3)
(1 2 3)
3> (list 'x 'y 'z)
(X Y Z)
4> (list '|x| 'y '|z|)
(x Y z)
5> 

And now we'll break at this point.  Leaving out all of the SWANK calls in the stack trace, we find the following:

 28: (READ)
 29: (LET ((CMD 1)) (DECLARE (TYPE REAL CMD)) (TAGBODY EXCL::NEXT-LOOP (PROGN (FORMAT T "~&~A> " CMD) (PRINC #)) (EXCL::LOOP-REALLY-DESETQ CMD (1+ CMD)) (GO EXCL::NEXT-LOOP) EXCL::END-LOOP))
 30: (CL-REPL)

And now what happens with the other version.

PG-USER> (scheme-repl)
1> nil
NIL
2> (list 1 2 3)
(1 2 3)
3> (list 'x 'y 'z)
(X Y Z)
4> (list '|x| 'y '|z|)
(x Y z)
5> 

And the stack trace.  Again, leaving out all of the SWANK calls.

 28: (READ)
 29: (SCHEME-REPL 5)
 30: (SCHEME-REPL 4)
 31: (SCHEME-REPL 3)
 32: (SCHEME-REPL 2)
 33: (SCHEME-REPL)

So, this lisp is not using tail-call elimination for this code.  If we write code like scheme-repl, we will eventually wind up with a stack overflow.  This has nothing to do with whether or not the code is "highly optimized", as in runs fast as C.  It has everything to do with whether or not the code will do the correct thing as a REPL.  cl-repl will run in any/all CL images and will work as a REPL no matter how many command one types.  scheme-repl in this lisp image will blow up after a large number of commands.  In Scheme, scheme-repl would work just as well as cl-repl works in CL because Scheme requires tail-call elimination.

Is this really irrelevant to you?  Just an optimization issue because if one had infinite memory then the scheme-repl version in this CL would still work for an infinite number of commands?  You know, just make sure to document that your user just needs to install the infinite RAM card before using your software.  I can understand not wanting to quibble about a few megabytes between friends.  One CL implementation only uses 1K and another uses 1M, 2K vs 2M, etc.  Sure, that's just an optimization issue.  But the difference between n and infinity?