3 ms·

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

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.

junke 8y ago
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.

junke 8y ago

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.