[plt-scheme] Re: HTDP: So you thought us empty? and empty

Guenther Schmidt
<gue.schmidt-S0/GAf8tV78 at public.gmane.org> writes:
> I heard that one of the differences between Scheme
and CL is that
> Scheme is "proper tail recursive" and CL isn't.
Until today I'm not
> 100% what that could mean but I think I'm seeing an
effect of it here.
> 
> (defun my-make-list (n)
>  (cond
>   ((< n 1) nil)
>   (t (cons nil (my-make-list (- n 1))))))
> 

First of all, your code isn't tail-recursive. A tail
recursive version
of it could look something like the following:

(defun my-make-list (n)
  (labels ((mml-rc (n accum)
   (cond
     ((< n 1) accum)
     (t (mml-rc (- n 1) (cons nil accum))))))
    (mml-rc n nil)))

> If I run this on Lispworks with let's say merely
n=200 I get a stack
> overflow, if I run it in Scheme with +100000 I just
have to wait a
> little, but no stack overflow.

Here are my results on the LispWorks trial edition
(which has a limited stack size):

CL-USER 1 > (defun my-make-list (n)
  (labels ((mml-rc (n accum)
   (cond
     ((< n 1) accum)
     (t (mml-rc (- n 1) (cons nil accum))))))
    (mml-rc n nil)))
MY-MAKE-LIST

CL-USER 2 > (compile 'my-make-list)
MY-MAKE-LIST
NIL
NIL

CL-USER 3 > (my-make-list 100000)
(NIL NIL NIL ...etc for)

CL-USER 4 > 

> What I really do like about CL and Scheme is the
excessive use of recursion, and the parenthesis too.
> Does this mean I need to switch back to iteration
when dealing with
> lists of over 200 elements in CL?

Many CL's support some form of tco now (usually at
compile time). Some
will do it automatically and others require an
appropriate optimization
declaration.

--
Bill Clementson

__________________________________
Do you Yahoo!?
New Yahoo! Photos - easier uploading and sharing.
http://photos.yahoo.com/