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.

Answer 1

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))

Answer 2

How about you use a tail call?

(defun fn (x)
  (if x
      (progn
        (princ x)
        (fn (cdr x)))
      (progn
        (rest))))

It calls fn in a tail position. If an implementation provides tail call optimization, you won't get a stack overflow. If you don't want to rely on that, you would need to handle the problem in a non recursive way. There are no explicit 'remove this functions stack frame and then call function X' operators in Common Lisp.