How do I jump out of a function in Lisp?

Question

Is it possible in (Common) Lisp to jump to another function instead of call another? I mean, that the current function is broken and another is called, without jumping back through thousands of functions, as if I'd decide myself if tail call optimization is done, even if it is not the tail. I'm not sure if "(return-from fn x)" does, what I want.

Example:

(defun fn (x)
  (when x
    (princ x)
    (jump 'fn (cdr x)))
  (rest))

'jump' should be like calling the following function without saving the position of this function, instead returning to, where the original funcall was, so that there will be no stack overflow. 'rest' should only be executed if x is nil.

maybe you have some code which demonstrates what you want to do? — Rainer Joswig
Note that to make this work, you still have to blow away the current stack frame, which is similar to what you'd have to do if you returned from the function normally. If you find a way to do this, you'll save on stack space, but you'll still have to do just the same number of stack frame setups and teardowns. — Joshua Taylor
(return-from fn (fn (cdr x))) first calculates (fn (cdr x)) (and so causes recursion) and then returns its value as the result; what you want is to return first (control-wise), and then calculate the returned value (avoiding the recursive build-up of the stack). This answer shows how. — Will Ness

Joshua Taylor Joshua Taylor · Accepted Answer · 2014-02-26T16:02:03

When you need a tail call optimization like structure in a language that doesn't (necessarily) provide it, but does provide closures, you can use a trampoline to achieve constant stack space (with a trade off for heap space for closure objects, of course). This isn't quite the same as what you asking for, but you might find it useful. It's pretty easy to implement in Common Lisp:

(defstruct thunk closure)

(defmacro thunk (&body body)
  `(make-thunk :closure (lambda () ,@body)))

(defun trampoline (thunk)
  (do ((thunk thunk (funcall (thunk-closure thunk))))
      ((not (thunk-p thunk)) thunk)))

To use the trampoline, you just call it with a thunk that performs the first part of your computation. That closure can either return another thunk, or a result. If it returns a thunk, then since it returned the initial stack frame is reclaimed, and then the closure of returned thunk is invoked. For instance, here's what an implementation of non-variadic mapcar might look like:

(defun t-mapcar1 (function list)
  (labels ((m (list acc)
             (if (endp list)
                 (nreverse acc)
                 (thunk 
                   (m (rest list)
                      (list* (funcall function (first list)) acc))))))
    (m list '())))

When the list is empty, we get an empty list immediately:

CL-USER> (t-mapcar1 '1+ '())
NIL

When it's not, we get back a thunk:

CL-USER> (t-mapcar1 '1+ '(1 2))
#S(THUNK :CLOSURE #<CLOSURE (LAMBDA #) {10033C7B39}>)

This means that we should wrap a call with trampoline (and this works fine for the base case too, since trampoline passes non-thunk values through):

CL-USER> (trampoline (t-mapcar1 '1+ '()))
NIL
CL-USER> (trampoline (t-mapcar1 '1+ '(1 2)))
(2 3)
CL-USER> (trampoline (t-mapcar1 '1+ '(1 2 3 4)))
(2 3 4 5)

Your example code isn't quite enough to be an illustrative example, but

(defun fn (x)
  (when x
    (princ x)
    (jump 'fn (cdr x)))
  (rest))

would become the following. The return provides the early termination from fn, and the thunk value that's returned provides the “next” computation that the trampoline would invoke for you.

(defun fn (x)
  (when x
    (princ x)
    (return (thunk (fn (cdr x)))))
  (rest))

How do I jump out of a function in Lisp?

3 Answers