.SCM File Format – Control and tail calls

Proper tail recursion

A tail call is a procedure call in a tail context. An implementation is properly tail-recursive if it supports an unbounded number of active tail calls, where a call is active if the called procedure might still return. A tail call reuses the continuation of the procedure that makes it, so it does not grow the stack.

A tail context is always relative to one lambda expression. These are the tail contexts (R7RS section 3.5):

• the last expression of the body of a lambda, and of every clause body of case-lambda;
• when the enclosing form is itself in a tail context: both branches of if; the last expression of each clause of cond and case and of their else clauses; the last test of and and or; the last expression of when and unless; the last expression of the bodies of let, named let, let*, letrec, letrec*, let-values, let*-values, let-syntax and letrec-syntax; the last expression of begin; the result expressions of do;
• the implied call in a (test => expression) clause of cond or case (the call is a tail call, the expression is not);
• the first argument passed to apply and to call-with-current-continuation, the second argument of call-with-values, and the expression passed to eval: each of these procedures must make a tail call.

In the report’s own example the only tail call is the call to f; the calls to g and h are not, and the reference to x is in a tail context but is not a call.

(lambda ()
  (if (g)
      (let ((x (h)))
        x)
      (and (g) (f))))

;; a loop that runs in constant space
(define (count-to n)
  (let loop ((i 0))
    (if (< i n)
        (loop (+ i 1))   ; a tail call
        i)))

A call such as (+ 1 (f (- n 1))) is not a tail call, because the addition still has to run after f returns. A procedure written that way uses stack proportional to n, and implementations grow the stack (Chez, Guile, CHICKEN) or report an error (some others) when it is too deep.

Control procedures

Multiple values

A procedure can return several values with values. A continuation that takes several values is made by call-with-values, by let-values, let*-values and define-values, and by the continuation of a non-final expression in a body, which accepts any number of values and discards them. What happens when the number of values does not fit the continuation (for example (+ 1 (values 2 3))) is unspecified, and implementations signal an error. R7RS also says that a result that the report calls unspecified is still a single value.

(call-with-values (lambda () (values 4 5))
                  (lambda (a b) b))          ; 5

(let-values (((q r) (floor/ 17 5)))
  (list q r))                               ; (3 2)

(define-values (x y) (exact-integer-sqrt 17))
(list x y)                                  ; (4 1)

SRFI 8 receive ((receive formals expression body)) is a common shorthand in implementations that provide it, and SRFI 210 gives a larger set of procedures and syntax for multiple values.

Promises and lazy evaluation

(delay expr) makes a promise and (force promise) evaluates it once and returns the same value on later calls. (delay-force expr) is for a promise whose value is another promise, and chains of them run in bounded space; a lazy stream written with it can be walked without the stack growing. (make-promise obj) makes an already forced promise, or returns obj if it is a promise, and (promise? obj) tests for one. force on a value that is not a promise may return it unchanged. A promise is not necessarily disjoint from other types (it may be a procedure or a record). R7RS defines delay so that it works as in the SRFI 45 algorithm; R5RS and R6RS had only delay and force.

(define integers
  (letrec ((next (lambda (n)
                   (delay (cons n (next (+ n 1)))))))
    (next 0)))

(define head (lambda (stream) (car (force stream))))
(define tail (lambda (stream) (cdr (force stream))))
(head (tail (tail integers)))   ; 2

Parameter objects and dynamic binding

A parameter is a procedure of no arguments made by make-parameter. parameterize rebinds it for the dynamic extent of its body, and the binding is restored when control leaves, including by a continuation. This is the standard way to change current-output-port for a call, and it is safe in the presence of call/cc, which a variable set with set! is not. The converter of (make-parameter init converter) runs on the initial value and on each value given to parameterize.

(define radix
  (make-parameter 10
    (lambda (x)
      (if (and (exact-integer? x) (<= 2 x 16))
          x
          (error "invalid radix")))))

(define (f n) (number->string n (radix)))

(f 12)                              ; "12"
(parameterize ((radix 2)) (f 12))   ; "1100"
(f 12)                              ; "12"

Iteration forms compared

Not described

Known, not yet covered

• Reference: the details of eval and environments (R7RS section 6.12) and of the R6RS eval and environment with library import specifications are named but not described.
• Reference: how each implementation handles a deep non-tail recursion (growing the stack, a limit, an error) is from memory and was not checked.

See also

• Continuations and dynamic-wind – capturing and escaping
• Error handling – raise and guard as structured escapes
• Lists, vectors and strings – the sequence procedures