The Common Lisp Cookbook – Functions

Functions that return functions

“How do I write a function that returns a function?” is a typical question asked by people who have learned Scheme before they started with Common Lisp. In Scheme, they were accustomed to be able to do things like this:

==> (define (adder n) (lambda (x) (+ x n)))
adder

==> ((adder 3) 5)
8

==> (define (doubler f) (lambda (x) (f x x)))
doubler

==> ((doubler +) 4)
8

This can of course be done in Common Lisp, but the syntax and the semantics are different. The first step, creating a function that returns a function, looks very similar apart from minor syntactical conventions, but what happens behind the scenes is different:

CL-USER> (defun adder (n) (lambda (x) (+ x n)))
ADDER

Here we have defined the function adder which returns an object of type function. To create such an object you’ll have to use the special operator function and apply it to a lambda expression. (function form) may be abbreviated as #'form. In our example above we used a shorthand notation provided by the macro lambda. Without this little bit of syntactical sugar we would have to write it as

CL-USER> (defun adder (n) #'(lambda (x) (+ x n)))
ADDER

or

CL-USER> (defun adder (n) (function (lambda (x) (+ x n))))
ADDER

No matter how we write it, adder will now return a function whenever we call it. But we can’t use it in the same way we would use it in Scheme:

CL-USER> (adder 3)
#<Interpreted Function "LAMBDA (N)" {485FFE81}>

CL-USER> ((adder 3) 5)
In: (ADDER 3) 5
    ((ADDER 3) 5)
Error: Illegal function call.

Here is why: CL has different namespaces for functions and variables, i.e. the same name can refer to different things depending on it’s position in a form that’s evaluated:

CL-USER> (boundp 'foo)
NIL
CL-USER> (fboundp 'foo)
NIL
CL-USER> (defparameter foo 42)
FOO
* foo
42
CL-USER> (boundp 'foo)
T
CL-USER> (fboundp 'foo)
NIL
CL-USER> (defun foo (x) (* x x))
FOO
CL-USER> (fboundp 'foo)
T
* foo            ;;; ***
42
CL-USER> (foo 3)        ;;; +++
9
CL-USER> (foo foo)
1764
CL-USER> (function foo)
#<Interpreted Function FOO {48523CC1}>
* #'foo
#<Interpreted Function FOO {48523CC1}>
CL-USER> (let ((+ 3)) (+ + +))
6

To simplify a bit, you can think of each symbol in CL having (at least) two “cells” in which information is stored. One cell - sometimes referred to as its value cell - can hold a value that is bound to this symbol, and you can use boundp to test whether the symbol is bound to a value (in the global environment). You can access the value cell of a symbol with symbol-value.

The other cell - sometimes referred to as its function cell - can hold the definition of the symbol’s (global) function binding. In this case, the symbol is said to be fbound to this definition. You can use fboundp to test whether a symbol is fbound. You can access the function cell of a symbol (in the global environment) with symbol-function.

Now, if a symbol is evaluated, it is treated as a variable in that it’s value cell is returned - see the line marked with *** above. If a compound form, i.e. a cons, is evaluated and its car is a symbol, then the function cell of this symbol is used - see the line marked +++ above.

In Common Lisp, as opposed to Scheme, it is not possible that the car of the compound form to be evaluated is an arbitrary form. If it is not a symbol, it must be a lambda expression, which looks like

(lambda lambda-list form*)

This explains the error message we got above - (adder 3) is neither a symbol nor a lambda expression. But, you might ask, how do we use the function object that is returned by adder? The answer is: Use funcall or apply:

;;; continued from above
CL-USER> (funcall (adder 3) 5)
8
CL-USER> (apply (adder 3) '(5))
8
CL-USER> (defparameter *my-fun* (adder 3))
*MY-FUN*
* *my-fun*
#<Interpreted Function "LAMBDA (N)" {486468C9}>
CL-USER> (funcall *my-fun* 5)
8
CL-USER> (*my-fun* 5)
Warning: This function is undefined:
  *MY-FUN*

Note that in the last example the function object returned by (adder 3) is stored in the value cell of *my-fun* - thus the error message. If we want to be able to use the symbol *my-fun* in the car of a compound form, we have to explicitely store something in its function cell (which is normally done for us by the macro defun):

;;; continued from above
CL-USER> (fboundp '*my-fun*)
NIL
CL-USER> (setf (symbol-function '*my-fun*) (adder 3))
#<Interpreted Function "LAMBDA (N)" {4869FA19}>
CL-USER> (fboundp '*my-fun*)
T
CL-USER> (*my-fun* 5)
8

Now we are ready do define doubler as well:

CL-USER> (defun doubler (f)
    (lambda (x) (funcall f x x)))
DOUBLER
CL-USER> (doubler #'+)
#<Interpreted Function "LAMBDA (F)" {48675791}>
CL-USER> (doubler '+)
#<Interpreted Function "LAMBDA (F)" {486761B1}>
CL-USER> (funcall (doubler #'+) 4)
8
CL-USER> (funcall (doubler '+) 4)
8
CL-USER> (defparameter *my-plus* '+)
*MY-PLUS*
CL-USER> (funcall (doubler *my-plus*) 4)
8
CL-USER> (defparameter *my-fun* (doubler '+))
*MY-FUN*
CL-USER> (funcall *my-fun* 4)
8

Note that the argument to funcall (and apply) can either be the function itself, i.e. #'+, or a symbol which has the function in its function cell (is fbound to the function), i.e. '+.

All of the above is extremely simplified - we haven’t even mentioned macros, special forms, symbol macros, self-evaluating objects, and lexical environments. Read the CLHS section about form evaluation for the real deal.

Currying functions

Concept

A related concept is that of currying which you might be familiar with if you’re coming from a functional language. After we’ve read the last section that’s rather easy to implement:

CL-USER> (declaim (ftype (function (function &rest t) function) curry) (inline curry))
NIL
CL-USER> (defun curry (function &rest args)
           (lambda (&rest more-args)
	           (apply function (append args more-args))))
CURRY
CL-USER> (funcall (curry #'+ 3) 5)
8
CL-USER> (funcall (curry #'+ 3) 6)
9
CL-USER> (setf (symbol-function 'power-of-ten) (curry #'expt 10))
#<Interpreted Function "LAMBDA (FUNCTION &REST ARGS)" {482DB969}>
CL-USER> (power-of-ten 3)
1000

Note that the declaim statement above is just a hint for the compiler so it can produce more efficient code if it so wishes. Leaving it out won’t change the semantics of the function.

With the Alexandria library

Now that you know how to do it, you may appreciate using the implementation of the Alexandria library (in Quicklisp).

(ql:quickload :alexandria)

(defun adder (foo bar)
  "Add the two arguments."
  (+ foo bar))

(defvar add-one (alexandria:curry #'adder 1) "Add 1 to the argument.")

(funcall add-one 10)  ;; => 11

(setf (symbol-function 'add-one) add-one)
(add-one 10)  ;; => 11