Prev: printing and reading CLOS objects usably
Next: How to check if file is a regular file (not directory)?
From: Alan Malloy on 20 Mar 2010 03:01
Hi folks. I've always had in the back of my mind that I ought to learn
lisp, but the language looks pretty intimidating so I never got round to
it. I started in earnest this week though and I'm quite liking it thus
far. I've had a couple problems, though, and I'm hoping cll is a good
community to get help from. If it matters, I have no background in
functional-programming at all; most of my experience is with imperative
languages like C and Java.

Anyway, I was trying to get my head around how to write functions which
are tail-recursive to avoid stack-overflow issues, and while it'll take
me some practice to think about it in the right way, I'm sure I
understand the concept. So I decided to write a function that creates a
list of N consecutive integers (I assume there is a library function
that does this but I couldn't find it). My first, naive implementation was:

(defun lazy-seq-list (size &optional (n 1))
(if (zerop size)
nil
(cons n (lazy-seq-list (1- size) (1+ n)))))

This "works" fine but needs O(n) memory: enter tail recursion, right?

(defun seq-list (size &optional list-so-far)
(if (zerop size)
list-so-far
(seq-list (1- size) (cons size list-so-far))))

But either one of these functions succeeds for size 1000, and overflows
the stack with size 10000. My understanding is that lisp supports
tail-recursion optimization, so that the second version ought to work
for arbitrarily large sizes, right? What have I got wrong here?

If it matters, I am running GNU CLISP 2.48 under Cygwin, on Windows XP.

--
Cheers,
Alan (San Jose, California, USA)
From: refun on 20 Mar 2010 03:28
In article <ho1rs7$kv7$1(a)news.eternal-september.org>, alan.NO.SPAM(a)malloys.org
says...
>
> Hi folks. I've always had in the back of my mind that I ought to learn
> lisp, but the language looks pretty intimidating so I never got round to
> it. I started in earnest this week though and I'm quite liking it thus
> far. I've had a couple problems, though, and I'm hoping cll is a good
> community to get help from. If it matters, I have no background in
> functional-programming at all; most of my experience is with imperative
> languages like C and Java.
>
> Anyway, I was trying to get my head around how to write functions which
> are tail-recursive to avoid stack-overflow issues, and while it'll take
> me some practice to think about it in the right way, I'm sure I
> understand the concept. So I decided to write a function that creates a
> list of N consecutive integers (I assume there is a library function
> that does this but I couldn't find it). My first, naive implementation was:
>
> (defun lazy-seq-list (size &optional (n 1))
> (if (zerop size)
> nil
> (cons n (lazy-seq-list (1- size) (1+ n)))))
>
> This "works" fine but needs O(n) memory: enter tail recursion, right?
>
> (defun seq-list (size &optional list-so-far)
> (if (zerop size)
> list-so-far
> (seq-list (1- size) (cons size list-so-far))))
>
> But either one of these functions succeeds for size 1000, and overflows
> the stack with size 10000. My understanding is that lisp supports
> tail-recursion optimization, so that the second version ought to work
> for arbitrarily large sizes, right? What have I got wrong here?
>
> If it matters, I am running GNU CLISP 2.48 under Cygwin, on Windows XP.


The second version is tail-recursive, so a compiler which can perform TCO
should be able to optimize it into a loop. SBCL seems to do it just fine, but
usually it depends on the OPTIMIZE declaration:
http://www.lispworks.com/documentation/HyperSpec/Body/d_optimi.htm

The ANSI CL standard does not require tail-call optimizations like the Scheme
one, but most serious implementations support it (and you can turn it on/off
using the optimize declaration - turning it off might be useful for debugging
purposes as the stack won't contain all calls to your function if TCO is
performed).

If you wanted to write it without tail-recursion, you could just use LOOP:
(defun seq (n)
(loop for i from 1 to n collect i))

If you wanted to write it in a tail-recursive manner without exposing the
internals using the optional parameter, you could use a LABELS:
(defun seq (n)
(labels ((rec (i acc)
(if (zerop i)
acc
(rec (1- i) (cons i acc)))))
(rec n nil)))

If you wanted to write it a way without tail-recursion or even LOOP, you could
use the push/nreverse idiom:

(defun seq (n)
(let (result)
(dotimes (i n (nreverse result))
(push (1+ i) result))))

Or you could use WITH-COLLECTOR(S) macro which is in many libraries - or write
that macro yourself.

Personally, I find the non-tail-recursive versions just as clear as the tail-
recursive one, if not more, and they will work as expected even in Lisps which
don't support TCO, so I only write tail-recursive code when it looks
better/makes more sense than an imperative approach.

P.S: Do you use a good Lisp editor like Emacs(with SLIME and Paredi)? Your
indentation looked a bit weird.
From: Tamas K Papp on 20 Mar 2010 04:05
On Sat, 20 Mar 2010 00:01:28 -0700, Alan Malloy wrote:

> Hi folks. I've always had in the back of my mind that I ought to learn
> lisp, but the language looks pretty intimidating so I never got round to
> it. I started in earnest this week though and I'm quite liking it thus
> far. I've had a couple problems, though, and I'm hoping cll is a good
> community to get help from. If it matters, I have no background in
> functional-programming at all; most of my experience is with imperative
> languages like C and Java.
>
> Anyway, I was trying to get my head around how to write functions which
> are tail-recursive to avoid stack-overflow issues, and while it'll take
> me some practice to think about it in the right way, I'm sure I
> understand the concept. So I decided to write a function that creates a
> list of N consecutive integers (I assume there is a library function
> that does this but I couldn't find it). My first, naive implementation
> was:
>
> (defun lazy-seq-list (size &optional (n 1))
> (if (zerop size)
> nil
> (cons n (lazy-seq-list (1- size) (1+ n)))))
>
> This "works" fine but needs O(n) memory: enter tail recursion, right?
>
> (defun seq-list (size &optional list-so-far)
> (if (zerop size)
> list-so-far
> (seq-list (1- size) (cons size list-so-far))))
>
> But either one of these functions succeeds for size 1000, and overflows
> the stack with size 10000. My understanding is that lisp supports
> tail-recursion optimization, so that the second version ought to work
> for arbitrarily large sizes, right? What have I got wrong here?
>
> If it matters, I am running GNU CLISP 2.48 under Cygwin, on Windows XP.

CL implementations are not required to support tail recursion
optimizations (though most usually do, at some optimization
settings). Also, CL is not a pure functional language, and doesn't
even suggest any particular programming style.

If you are learning Lisp, check out Practical Common Lisp by Peter
Seibel, also available online. It is the best intro book, and will
teach you idiomatic Lisp style. Eg your function could be written as

(defun seq-list (n)
"(list 1 ... n)."
(loop
for i :from 1 :to n
collecting i))

Even though this is a matter of taste, most CL'ers would argue that
this is easier to write and understand than tail-recursive versions.
Some people actually dislike how introductory Scheme texts force every
algorithm into contorted examples of tail recursion.

CL has a lot of facilities to support functional programming, though,
and they are used when they make sense. But tail recursion per se is
not that commonly employed.

Enjoy CL,

Tamas
From: Alan Malloy on 20 Mar 2010 04:07
refun wrote:
> In article <ho1rs7$kv7$1(a)news.eternal-september.org>, alan.NO.SPAM(a)malloys.org
> says...
>> Hi folks. I've always had in the back of my mind that I ought to learn
>> lisp, but the language looks pretty intimidating so I never got round to
>> it. I started in earnest this week though and I'm quite liking it thus
>> far. I've had a couple problems, though, and I'm hoping cll is a good
>> community to get help from. If it matters, I have no background in
>> functional-programming at all; most of my experience is with imperative
>> languages like C and Java.
>>
>> Anyway, I was trying to get my head around how to write functions which
>> are tail-recursive to avoid stack-overflow issues, and while it'll take
>> me some practice to think about it in the right way, I'm sure I
>> understand the concept. So I decided to write a function that creates a
>> list of N consecutive integers (I assume there is a library function
>> that does this but I couldn't find it). My first, naive implementation was:
>>
>> (defun lazy-seq-list (size &optional (n 1))
>> (if (zerop size)
>> nil
>> (cons n (lazy-seq-list (1- size) (1+ n)))))
>>
>> This "works" fine but needs O(n) memory: enter tail recursion, right?
>>
>> (defun seq-list (size &optional list-so-far)
>> (if (zerop size)
>> list-so-far
>> (seq-list (1- size) (cons size list-so-far))))
>>
>> But either one of these functions succeeds for size 1000, and overflows
>> the stack with size 10000. My understanding is that lisp supports
>> tail-recursion optimization, so that the second version ought to work
>> for arbitrarily large sizes, right? What have I got wrong here?
>>
>> If it matters, I am running GNU CLISP 2.48 under Cygwin, on Windows XP.
>
>
> The second version is tail-recursive, so a compiler which can perform TCO
> should be able to optimize it into a loop. SBCL seems to do it just fine, but
> usually it depends on the OPTIMIZE declaration:
> http://www.lispworks.com/documentation/HyperSpec/Body/d_optimi.htm
>
> The ANSI CL standard does not require tail-call optimizations like the Scheme
> one, but most serious implementations support it (and you can turn it on/off
> using the optimize declaration - turning it off might be useful for debugging
> purposes as the stack won't contain all calls to your function if TCO is
> performed).
>
> If you wanted to write it without tail-recursion, you could just use LOOP:
> (defun seq (n)
> (loop for i from 1 to n collect i))
>
> If you wanted to write it in a tail-recursive manner without exposing the
> internals using the optional parameter, you could use a LABELS:
> (defun seq (n)
> (labels ((rec (i acc)
> (if (zerop i)
> acc
> (rec (1- i) (cons i acc)))))
> (rec n nil)))
>
> If you wanted to write it a way without tail-recursion or even LOOP, you could
> use the push/nreverse idiom:
>
> (defun seq (n)
> (let (result)
> (dotimes (i n (nreverse result))
> (push (1+ i) result))))
>
> Or you could use WITH-COLLECTOR(S) macro which is in many libraries - or write
> that macro yourself.
>
> Personally, I find the non-tail-recursive versions just as clear as the tail-
> recursive one, if not more, and they will work as expected even in Lisps which
> don't support TCO, so I only write tail-recursive code when it looks
> better/makes more sense than an imperative approach.
>
> P.S: Do you use a good Lisp editor like Emacs(with SLIME and Paredi)? Your
> indentation looked a bit weird.

Wow! A lot of language features I hadn't imagined existed, despite what
I thought was a reasonable time spent reading documentation. I was
aware, of course, that I could do this iteratively; I'm not desperate to
get this useless function implemented, but looking for a simple example
to practice tail-recursion. I tried adding the OPTIMIZE parameters, and
that seems to have maybe worked - I can get a larger list than before,
anyway, but I don't think I can manage arbitrarily large.

My current editor is not very good. I started out with Eclipse/Cusp, but
was experiencing serious problems there, so I've switched to
LispIDE/Clisp. I've been trying to avoid learning emacs (only one huge
project at a time!), but maybe I will give SLIME a go.

--
Cheers,
Alan (San Jose, California, USA)
From: Kalle Olavi Niemitalo on 20 Mar 2010 04:11
Alan Malloy <alan.NO.SPAM(a)malloys.org> writes:

> My understanding is that lisp supports tail-recursion
> optimization, so that the second version ought to work for
> arbitrarily large sizes, right?

Implementations of Common Lisp do not have to support
tail-recursion optimization. Implementations of Scheme must.

In Common Lisp implementations that do support it, whether the
optimization happens might depend on whether the function was
compiled and what OPTIMIZE declarations were in effect. For
instance, if you (declaim (optimize (debug 3))), then the
implementation might choose not to optimize tail recursion,
so that the debugger can display all the nested calls.

If you just want a list of integers without blowing the stack,
then LOOP is handy for that. Its syntax is rather unlike the
rest of Common Lisp but I find it generally more convenient
than DO or DOLIST or MAPCAR.
 |  Next  |  Last
Pages: 1 2
Prev: printing and reading CLOS objects usably
Next: How to check if file is a regular file (not directory)?