#lang scribble/doc

@require[scribble/manual
         scribble/base
         scribble/eval
         scheme/runtime-path
         (planet cce/scheme:4:1/planet)]

@require[(for-syntax scheme/base)]

@require[(for-label scheme/base
                    (this-package-in main))]

@define-runtime-path[home (build-path 'same)]

@define[the-eval
        (let ([the-eval (make-base-eval)])
          (parameterize ([current-directory home])
            (the-eval `(require (file ,(path->string (build-path home "main.ss")))))
            (the-eval '(define (current-continuation-marks-list key)
                         (continuation-mark-set->list (current-continuation-marks) key))))
          the-eval)]

@title[#:tag "top"]{@bold{Tail} Recursion Utilities}

by Dave Herman (@tt{dherman at ccs dot neu dot edu})

This library provides utilities for tail recursion.

@defmodule/this-package[]

@table-of-contents[]

@section[#:tag "trace"]{Disabling Tail Recursion}

@defform[#:id trace-begin
         (trace-begin body-expr ...+)]{
A syntax for evaluating a sequence of expressions, like @scheme[begin], but
without preserving tail position. In particular, the last of the @scheme[body-expr]
expressions is @italic{not} in tail position.}

@defthing[trace-app (syntax? -> syntax?)]{
A @scheme[for-syntax] binding that behaves like the @scheme[#%app] of @scheme[scheme/base],
but without evaluating the procedure application in tail position. To disable tail recursion
on a per-module basis, add the following line to the top of the module:

@schemeblock[(define-syntax #%app trace-app)]}

@section[#:tag "continuations"]{Tail-Recursive Continuations}

@deftogether[[
@defform[#:id let-tail-continuation
         (let-tail-continuation k-id body-expr ...+)]{}
@defform[#:id let/tc
         (let/tc k-id body-expr ...+)]{}
]]{
Syntactic forms for capturing a continuation and binding a special form
that always invokes the continuation in tail position.}

The identifier @scheme[k-id] is bound to a special form that invokes the
captured continuation in tail position with respect to the entire @scheme[let/tc]
expression.

@examples[#:eval the-eval
         (define (down n)
           (with-continuation-mark 'down n
             (let/ec return
               (if (zero? n)
                   (return (current-continuation-marks-list 'down))
                   (return (down (sub1 n)))))))
         (down 10)
         (define (down* n)
           (with-continuation-mark 'down* n
             (let/tc return
               (if (zero? n)
                   (return (current-continuation-marks-list 'down*))
                   (return (down* (sub1 n)))))))
         (down* 10)]

To achieve proper tail recursion, the argument to @scheme[k-id] is evaluated
in the hole of the captured continuation, i.e., @italic{after} abandoning the current
continuation. Note that this behavior is significant when the argument expression
performs side effects.

@examples[#:eval the-eval
          (with-continuation-mark 'jump 'after
            (let/cc k
              (with-continuation-mark 'jump 'before
                (k (current-continuation-marks-list 'jump)))))
          (with-continuation-mark 'jump 'after
            (let/tc k
              (with-continuation-mark 'jump 'before
                (k (current-continuation-marks-list 'jump)))))
          (with-handlers ([exn? (lambda (exn) 'uncaught)])
            (let/ec k
              (with-handlers ([exn? (lambda (exn) 'caught)])
                (k (error 'stop)))))
          (with-handlers ([exn? (lambda (exn) 'uncaught)])
            (let/tc k
              (with-handlers ([exn? (lambda (exn) 'caught)])
                (k (error 'stop)))))]

The captured continuation @scheme[k-id] can only be applied to exactly one argument. (If
control returns normally, i.e., without explicitly invoking @scheme[k-id], it may
return any number of values.)

@examples[#:eval the-eval
          (let/tc k
            (k 1 2 3))
          (let/tc k
            (values 1 2 3))]

@section[#:tag "marks"]{Generalized Continuation Marks}

@defform[#:id with-continuation-mark*
         (with-continuation-mark* key-expr val-expr update-expr body-expr ...+)]{
Like @scheme[with-continuation-mark], but instead of automatically overwriting existing
marks, applies procedure obtained from @scheme[update-expr] to the existing value.}

@examples[#:eval the-eval
          (let down ([n 10])
            (if (zero? n)
                (current-continuation-marks-list 'down)
                (with-continuation-mark* 'down 0 add1 (down (sub1 n)))))]