Re:SICP Goodness – Why you don't need looping constructs
by shakna on Friday June 29, 2018 @07:36AM
(#17423867)
Tail calls were made explicit in Clojure, with the recur construct. It had more to do with the JVM than syntactic benefits, but it turns out to be a decent idea.
Re:SICP Goodness – Why you don't need looping constructs
by junke on Friday June 29, 2018 @08:12AM
(#17424020)
"recur" can be used for self-call in tail position, but does not help with the general case where you may want to jump to another function.
Re:SICP Goodness – Why you don't need looping constructs
by steinuil on Friday June 29, 2018 @08:45AM
(#17424159)
Tail calls do not just deal with recursive functions, in general TCO works on any function call in tail position. Maybe a more general recur construct (maybe called "jump") would be a good idea, but then you'd have to remember to use it.
Re:SICP Goodness – Why you don't need looping constructs
by shakna on Friday June 29, 2018 @10:17AM
(#17424635)
Clojure is limited by the JVM, hence the need for recur. However, between it and trampoline you get most of the way to what TCO offers, albeit with the need for the programmer to be explicit.
Re:SICP Goodness – Why you don't need looping constructs
by yvdriess on Friday June 29, 2018 @08:02AM
(#17423974)
While there isn't special form for tailcall, they are not implicit. If the recursive call does something with the result, it's not a tailcall. Unless you are being cute with closures, it's already explicit in the AST.
--> return myself(...) # tail call
--> return var * myself(...) # not a tail call
But there is indeed something to be said about a construct that enforces the tail call guarantee. The point of SICP's scheme though is to keep the number of language constructs to a minimum for educational purposes.
Re:SICP Goodness – Why you don't need looping constructs
by nabla9 on Friday June 29, 2018 @08:36AM
(#17424124)
the following is also tailcall:
x = f(a)
...
...
return x
Re:SICP Goodness – Why you don't need looping constructs
by steinuil on Friday June 29, 2018 @09:24AM
(#17424330)
That's definitely not a tail call, and even with a smart compiler it's pretty hard that it would get optimized into "return f(a)".
If "x" is declared there and never mutated in the subsequent code, and the code in the "..." doesn't perform any side effects, then such an optimization could occur... but then again, if the code in the "..." in your example didn't perform any side effects, it'd be dead code.
Re:SICP Goodness – Why you don't need looping constructs
by nabla9 on Friday June 29, 2018 @11:18AM
(#17424994)
Better examples:
Both
If (b == 3):
x = f(a)
else:
x = g(a)
return x
and if (b == 3):
x = f
else:
x = g
return x(a)
are equivalent to: if (b == 3):
return f(a)
else:
return g(a)
In every example the function call is in the tail position semantically. In the the two cases syntactically. The loop construct is hidden.
Re:SICP Goodness – Why you don't need looping constructs
by tonyg on Friday June 29, 2018 @08:42AM
(#17424140)
That's not right, unless the "... ..." is empty, and even then, it depends on whether x is a global variable, and even if it isn't, it depends on the language.
Re:SICP Goodness – Why you don't need looping constructs
by davexunit on Friday June 29, 2018 @09:31AM
(#17424379)
Tail calls are semantic, not just an optimization, at least in languages like Scheme. Also, blowing the stack only applies to language implementations that have a fixed stack size, it's not a universal truth. In Scheme, a call stack is an implementation detail, and some implementations dynamically allocate stack space to accommodate recursive procedures. For example, here's a simple implementation of 'map':
(define (map proc lst)
(if (null? lst)
'()
(cons (proc (car lst)) (map proc (cdr lst)))))
You might look at this and go "that's bad! it will blow the stack when the list is too long!". Well, some Schemes will dynamically grow the stack so that this straightforward code translates to an efficient process that doesn't hit arbitrary stack limits. Otherwise the programmer would have to contort this into an iterative, tail-recursive process, which would involve building the list backwards and reversing it at the end.
Re:SICP Goodness – Why you don't need looping constructs
by junke on Friday June 29, 2018 @10:30AM
(#17424708)
Apparently some implementations have tail-recursion modulo cons. You spot a tail-recursive function where the result is placed in the cdr, and you compile your code so that it chains cells by calling "set-cdr!"
For example (using CL), the code could be turned into two auxiliary map%% and map% functions (map% would be what a call to map expands into).
(defun map%% (cons function list)
(declare (optimize (speed 3) (debug 1) (safety 1))
(type function function)
(type list list)
(type cons cons))
(when list
(map%% (setf (cdr cons)
(list (funcall function (first list))))
function
(rest list))))
(defun map% (function list)
(let ((fresh (cons nil nil)))
(map%% fresh function list)
(rest fresh)))
Testing TCO: (map% #'1+ '#1=(5 6 8 4 5 1 3 . #1#))
Heap exhausted, game over.
Re:SICP Goodness – Why you don't need looping constructs
by astrobe_ on Friday June 29, 2018 @08:26AM
(#17424074)
> You would use keyword or syntax to perform tail-calls explicitly
That's what I did in my Forth dialect; I called it "goto".
Re:SICP Goodness – Why you don't need looping constructs
by willtim on Friday June 29, 2018 @07:28AM
(#17423830)
It's debatable whether tail calls should be classified as an optimisation. In my view, they should be part of the operational semantics.
Re:SICP Goodness – Why you don't need looping constructs
by chriswarbo on Friday June 29, 2018 @07:41AM
(#17423892)
I try to use the phrase "tail call optimisation" when an implementation may perform it but the language doesn't require it, and "tail call elimination" when the language requires it (and hence any implementation which doesn't is non-conforming).
If I remember correctly, there was briefly discussed interesting proposal to add explicit tail calls into Python almost decade ago. You would use keyword or syntax to perform tail-calls explicitly (not the tail call decorator hack). This would make tail calls actual looping construct.