Prev: printing and reading CLOS objects usably
Next: How to check if file is a regular file (not directory)?
From: Ariel Badichi on 20 Mar 2010 04:40
Alan Malloy <alan.NO.SPAM(a)malloys.org> writes:

> 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.
>

CLISP will "optimize" your second function if you compile it:

(compile 'seq-list)

Ariel
From: joswig on 20 Mar 2010 04:43
On 20 Mrz., 09:11, Kalle Olavi Niemitalo <k...(a)iki.fi> wrote:
> Alan Malloy <alan.NO.S...(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.

It's slightly different. The Common Lisp standard does not
say a single word about it. It does not tell how
support for TCO would look like in CL, which is
not trivial.

It then means that the Common Lisp standard does not
say a word how TCO would interact with the rest
of the language.

* how to tell the compiler to use it?

* interpreting optimization qualities is not necessarily
the best thing to invoke it. This facility often
cannot be invoked on its own. Then after, say,
speed is 3, and debug is 1 a lot of
other things are interpreted differently
by some compilers - not just TCO

* what happens with dynamic scope (special variable
bindings,...)?

(let ((*standard-output* foo-stream))
(bar 10))

probably no TCO then. Warning or not?

>
> 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.

From: Pascal J. Bourguignon on 20 Mar 2010 05:13
Alan Malloy <alan.NO.SPAM(a)malloys.org> writes:

> 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:

Yes, this call to LAZY-SEQ-LIST is not a tail call, since after it
there's a call to CONS.


> 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.

It matters, since TCO depends on the implementation.

Some never do it (rare).

Some always do it (often).

Some, like clisp do it only on compiled code, and avoid it on
interpreted code, so that it can give better debugging information (so
that when breaking inside the recursion, you can see all the recursive
stack frames).


--
__Pascal Bourguignon__
From: Tim Bradshaw on 20 Mar 2010 08:02
On 2010-03-20 07:28:49 +0000, refun said:

> 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).

I don't think it's safe to assume that optimisation declarations will
turn on or off TCO, although they often may - I think an implementation
would be conforming if it always did TCO when it is possible.

I used to think that a NOTINLINE declaration should disable TCO but I
am no longer sure, and in fact I think it doesn't - I think it means
you need to do a full function call, but you would still be allowed to
discard the current stack frame.

Obviously implementations often do allow ways of disabling TCO.

From: Frode V. Fjeld on 28 Mar 2010 09:37
Tamas K Papp <tkpapp(a)gmail.com> writes:

> 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.

But, relevant to this thread, I believe Common Lisp does suggest one
"anti-style": Don't use tail recursion to iterate (linearly).

--
Frode V. Fjeld
First  |  Prev  | 
Pages: 1 2
Prev: printing and reading CLOS objects usably
Next: How to check if file is a regular file (not directory)?