7 ms·
The problem with tail calls is that they are implicit. That's why it's usually called tail call optimization. There is nothing in the syntax to indicate that y
by nabla9 8y ago
The problem with tail calls is that they are implicit. That's why it's usually called tail call optimization. There is nothing in the syntax to indicate that you actually have a tail call. You may have made a mistake and it actually blows up the stack.
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.
- willtim 8y agoIt's debatable whether tail calls should be classified as an optimisation. In my view, they should be part of the operational semantics.
- chriswarbo 8y agoI 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).
- shakna 8y agoTail 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.
- junke 8y ago"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.
- steinuil 8y agoTail 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.
- shakna 8y agoClojure 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.
- yvdriess 8y agoWhile 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.
- nabla9 8y agothe following is also tailcall: x = f(a) ... ... return x
- tonyg 8y agoThat'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.
- steinuil 8y agoThat'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.
- nabla9 8y agoBetter 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.
- astrobe_ 8y ago> You would use keyword or syntax to perform tail-calls explicitly That's what I did in my Forth dialect; I called it "goto".
- davexunit 8y agoTail 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.
- junke 8y agoApparently 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.