Lambda the Ultimate

The paper defines a form multi exp r1 ... rn, which evaluates an expression exp, resulting in a value v. The multi form provides one or more possible "return points" for exp, i.e. r1 thru rn. The expression exp can specify which of those return points to return to, using a return point specifier of the form #n. If the evaluated expression doesn't specify a return point, then the first return point is used.

A return point can either be a lambda expression, or a return point specifier (#n). If a return point is a lambda expression, it is applied to the value v mentioned above. If a return point is itself a return point specifier of the form #n, then v is returned to the n'th return point in the calling context.

It might be easier to explain it in code than English, although the following requires familiarity with Scheme. Here's a (naive) definition of a multi macro which implements multi-return function calls:

(define ret-mark '(ret-mark))
; The following 'ret' function is overloaded in a hackish way:
; (ret n) returns a return point specifier, can be used in multi expressions
; (ret n v) returns value v to return point n, used in the multi implementation
(define (ret n . v) (cons ret-mark (cons n v)))
(define (ret-mark? m) (and (pair? m) (eq? (car m) ret-mark)))
(define ret-index cadr)
(define ret-value caddr)

; apply-ret: apply a return point to a value
; returns either a plain value, or a new return point containing the value
(define (apply-ret ret-pt v)
  (cond
    ((ret-mark? ret-pt)  ; ret-pt is a return point specifier
     (let ((i (ret-index ret-pt)))
       (if (= i 1) v     ; support non-multi contexts, return plain value
           (ret i v))))  ; return v to i'th return point in caller
    ((procedure? ret-pt) ; ret-pt is a lambda expression
     (ret-pt v))         ; apply it to v
    (else 
     (error (format "Invalid return point specified: ~a" ret-pt)))))

; the multi macro
(define-syntax multi 
  (syntax-rules ()
    ((multi exp r1 ...)
     (let ((v exp)
           (ret-pts (vector r1 ...)))
       (if (ret-mark? v)
           ; the expression returned a value tagged with a return point specifier
           (let ((rn (ret-index v))  ; return point index
                 (rv (ret-value v))) ; returned value
             ; apply return point to value
             (apply-ret (vector-ref ret-pts (- rn 1)) rv))
           ; otherwise, the expression return a plain value, apply r1 to it
           (apply-ret (vector-ref ret-pts 0) v))))))

This definition allows us to implement the filter function given in the paper:

; filter example from paper
; code layout matches paper's figure 1 line for line
(define (filter f lis)
  (letrec ((recur (match-lambda ('() '())
                              ((x . xs)
                               (if (f x)
                                   (multi (recur xs)
                                          (ret 1)
                                          (lambda (ans) (multi (cons x ans) (ret 2))))
                                   (multi (recur xs)
                                          (lambda _ (multi xs (ret 2)))
                                          (ret 2)))))))
    (multi (recur lis)
           (lambda _ lis)
           (ret 1))))

Finally, here's a test which proves that the function achieves the desired goal, of "[sharing] the longest possible tail between input and output":

(define lis '(3 7 12 4 13 7 8 6 10))
(define ans (filter even? lis))
ans ; => (12 4 8 6 10)
(eq? (list-tail lis 6) (cddr ans)) ; => #t

Of course, implementing multi-return functions with a macro (especially one as naive as the above) won't necessarily achieve some of the machine-level efficiencies described in the paper. However, the macro is useful for experimenting with the concept, without having to modify a compiler!

Here's a different angle that may or may not be helpful: Suppose you had a case statement that chose one of several cases based on the return value of a function. With a multi-return function call you could have the called function jump straight back into the appropriate case, without having to return a value and perform comparisons. If any of the cases just returned on up the stack, you could instead have the called function jump directly up the stack to where it needed to go.

By itself this isn't too special. But as the paper demonstrates, it opens the door to some interesting optimizations, like stack-shrinking tail calls, or non-tail calls that run in constant space. It also allows for "leakage containment" in the sense of the paper that Andris mentioned.