order matters with return-from in SBCL

Question

I'm on Day 3 of trying to learn Common Lisp (SBCL) by doing Advent of Code. I understand there is more than one type of return. I'm wondering if someone could explain to me why the following function will return nil (this makes sense)

(defun fn (n)
    (cond ((zerop n) 
           (return-from fn nil))
          (t  
           (write-line "Hello World") 
           (fn (- n 1)))))

but the following function will return "Hello World" (this does not make sense to me).

(defun fn (n)
    (cond ((zerop n) 
           (return-from fn nil))
          (t 
           (fn (- n 1)) 
           (write-line "Hello World"))))

I found a great post covering some aspects of SBCL's return behaviour here, but to my understanding it doesn't seem to address this particular detail.

EDIT: a loop call is a more sensible way of writing this function, but it is not the way that I discovered this behaviour. My suspicion is that this behaviour arises because fn is called recursively.

Answer 1

(I started writing this before Sylwester's answer, which is mostly better I think.)

A critical difference between Lisp-family languages and many other languages is that Lisp-family languages are 'expression languages'. What this means technically is that languages like (say) C or Python there are two sorts of constructs:

• expressions, which have values;
• statements, which do not;

While in Lisp-family languages there is one sort of thing: expressions, which have values. Lisp-family languages are sometimes called 'expression languages' as a result of this.

This makes a huge difference if you want to write functions, which are things which return values (a function call is an expression in other words).

Conventional languages (Python as an example)

In a language which is not an expression language then if you're defining a function and find yourself in the middle of some construct which is a statement and you want to return a value, you have to use some special magic construct, often called return to do that. So in Python, where conditionals are statements, you might write:

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

And in fact you have to use return because the body of a function definition in Python is a series of statements, so to return any kind of value at all you need to use return.

In fact, Python (and C, and Java &c &c) have a special form of a conditional which is an expression: in Python this looks like this:

def fib(n):
    return n if n < 2 else (fib(n - 1) + fib(n - 2)

It looks different in C but it does the same thing.

But you still need this annoying return (OK, only one of them now) & that brings to light another feature of such languages: if some place in the syntax wants a statement you generally need to have a statement there, or if you can put an expression there its value just gets dropped. So you can try something like this:

def fib(n):
    n if n < 2 else (fib(n - 1) + fib(n - 2)

And that's syntactically OK -- the expression gets turned into a statement -- but it fails at runtime because the function no longer returns a useful value. In Python you can get around this if you want people to hate you:

fib = lambda n: n if n < 2 else fib(n - 1) + fib(n - 2)

Python people will hate you if you do this, and it's also not useful, because Python's lambda only takes expressions so what you can write is crippled.

Lisp

Lisp has none of this: in Lisp everything is an expression and therefore everything has a value, you just need to know where it comes from. There is still return (in CL, anyway) but you need to use it much less often.

But, of course people often do want to write programs which look like 'do this, then do this, then do this', where most of the doing is being done for side-effect, so Lisps generally have some kind of sequencing construct, which lets you just have a bunch of expressions one after the other, all but (typically) one of which get evaluated for side-effect. In CL the most common sequencing construct is called progn (for historical reasons). (progn ...) is an expression made of other expressions, and its value is the value of last expression in its body.

progn is so useful in fact that a bunch of other constructs have 'implicit progns' in them. Two examples are function definitions (the body of defun is an implicit progn) and cond (the body of a cond-clause is an implicit `progn).

Your function

Here is your function (first version) with its various parts notated

(defun fn (n)
  ;; the body of fn is an implicit progn with one expression, so
  ;; do this and return its value
  (cond
   ;; the value of cond is the value of the selected clause, or nil
   ((zerop n)
    ;; the body of this cond clause is an implicit progn with on
    ;; expression so do this and ... it never returns
    (return-from fn nil))
   (t
    ;; the body of this cond clause is an implicit progn with two expressions, so
    ;; do this for side-effect
    (write-line "Hello World")
    ;; then do this and return its value
    (fn (- n 1)))))

Here is the second version

(defun fn (n)
  ;; the body of fn is an implicit progn with one expression, so
  ;; do this and return its value
  (cond
   ;; the value of cond is the value of the selected clause, or nil
   ((zerop n)
    ;; the body of this cond clause is an implicit progn with on
    ;; expression so do this and ... it never returns
    (return-from fn nil))
   (t
    ;; the body of this cond clause is an implicit progn with two expressions, so
    ;; do this for side-effect
    (fn (- n 1))
    ;; then do this and return its value
    (write-line "Hello World"))))

So you can see what is happening here: in the first version the value that gets returned is either nil or the value of the recursive call (also nil). In the second version the value that gets returned is either nil or whatever write-line returns. And it turns out that write-line returns the value of its argument, so that's what you get if you call it with an integer greater than zero.

Why have return-from at all in Lisp?

One thing that should be immediately clear from this whole expression-language thing is that you hardly ever need to explicitly return something in Lisp: you just have an expression that computes the value you want. But there are two good uses (which perhaps are really the same use) of explicit returns.

The first is that sometimes you are doing some big search for something in the form of a bunch of nested loops and at some point you just want to say 'OK, found it, here's the answer'. You can do that in one of two ways: you can carefully structure your loops so that once you find what you're after they all terminate nicely and the value gets passed back up, or you can just say 'here's the answer'. The latter thing is what return-from does: it just says 'I'm done now, unwind the stack carefully and return this':

(defun big-complicated-search (l m n)
  (dotimes (i l)
    (dotimes (j m)
      (dotimes (k n)
        (let ((it (something-involving i j k l m n)))
          (when (interesting-p it)
            (return-from big-complicated-search it)))))))

And return-from does this in the right way:

(defun big-complicated-file-search (file1 file2)
  (with-open-file (f1 file1)
    (with-open-file (f2 file2)
      ...
      (when ...
        (return-from big-complicated-search found)))))

When you call this, and when the thing is found, return-from will make sure that the two files you have opened are properly closed.

The second, which is really almost the same thing, is that sometimes you need to just give up, and return-from is a good way of doing this: it returns immediately, deals with clean-ups (see above) and is generally a nice way of saying 'OK, I give up now'. At first blush this seems like something you would do with some kind of exception-handling system, but in fact there are two critical differences:

• in an exception-handling system (which CL has, of course), you need some kind of exception to raise so you might need to invent something;
• exception-handling systems are dynamic not lexical: if you raise an exception then the thing that gets to handle it is hunted for up the stack dynamically: this means that you're at the mercy of anyone who stuck a handler in the way and it also typically rather slow.

Finally the exceptional-return-via-error-handling-mechanism is just, well, horrid.