Tail call optimisation

[michael]

I am slowly making my way through the book and wanted to know about the tail call optimisation of the 'add-new-dice' function on page 333/4.

Is it optimised because the first conditional argument is a (zerop n) not the (null lst), ie testing an atom not a list? Is that part of the optimisation? It seems to be only mentioned briefly in the book.

And from my searching online I've just found mentions of the work that the compiler does. But I got the impression, it's mainly about the style that code is written in.



Sorry, can't paste code example because I've been going along in emacs and just discovered can't copy/paste/yank it out of emacs (in iterm)


Thanks

[Win Treese]

> On Dec 27, 2014, at 9:34 PM, michael <michae...@gmail.com> wrote:
>
> I am slowly making my way through the book and wanted to know about the tail call optimisation of the 'add-new-dice' function on page 333/4.
>
> Is it optimised because the first conditional argument is a (zerop n) not the (null lst), ie testing an atom not a list? Is that part of the optimisation? It seems to be only mentioned briefly in the book.
>
> And from my searching online I've just found mentions of the work that the compiler does. But I got the impression, it's mainly about the style that code is written in.

The key point for tail call optimization is that the return value of
the recursive call is returned directly from the calling function.
In that’s sense, it’s a matter of programming style, in that the
function was written that way. But the style makes possible the
tail call optimization, in which the compiler generates code that
doesn’t have to keep the intermediate stack frame around, since
the return value of the tail call is the return value of the function.

Hope this helps.

Win

[michael]

I see. Yes, that does help a lot.

This book is my intro to programming, so thanks for that Win.

[Win Treese]

Glad to help, and welcome to programming! Especially in Lisp, which can

be mind-stretching.

 - Win

--
You received this message because you are subscribed to the Google Groups "Land of Lisp" group.
To unsubscribe from this group and stop receiving emails from it, send an email to land-of-lisp...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[michael]

Thanks Win. Yes, mind being stretched enormously. Right now reading and re-reading the macro/dsl chapters. But I love it.

Hope you have a good new years :)

[pete...@gmail.com]

I assume functions in the lazy list library such as lazy-mapcar should also be tail-call optimized (in CLISP by compiling these functions). Is there any special reason why they are not? Otherwise, a sequence iterating function such as mapcar would presumably cause a performance bottleneck?

[Edward Kenworthy]

Compiling doesn't necessarily tail call optimise, they're different things. The ANSI CL standard doesn't require an implementation to perform TCO but a particular implementation might.

Is there any reason code might not be written to enable TCO? Yes if it has little value (limited levels of recursion for example) or otherwise where the cost of restructuring your code outweighs the benefit: which is not guaranteed by the standard.

Sent from my Windows Phone

---

From: pete...@gmail.com
Sent: ‎11/‎08/‎2016 01:49
To: Land of Lisp
Subject: Re: Tail call optimisation

[pete...@gmail.com]

I understand that. It was well-explained in "Land of Lisp". My question was about whether newly defined higher-order functions (relying on tail recursion in this case) should be optimized? The lazy mapcar function from the book was not. I was just wondering why, as it presumably forms a bottleneck in any lazy code relying on the mapcar function.