This article is part of the Lambda on Lisp series.

Tags: lambda-calculus, lisp

Lambda on Lisp - The identity function

Constant and Identity: “These are not the symbol-values you're looking for.”

Gabriel’s video: From the beginning to the discussion of lambda syntax at 1m48s

Foreshadowing the constant function

Possibly the simplest type of function in Lisp is one taking no arguments and returning a constant value. The returned value could be “nothing” as in (lambda () nil), or any other constant value, (lambda () 42)

As we’ll see later, the lambda calculus doesn’t have functions that take no arguments. Every function in the calculus takes exactly one argument, so the two Lisp expressions above become something like (lambda (_) nil) and (lambda (_) 42).

In the spirit of following Gabriel’s video, I’ll get back to the constant function later. For now, we’ll start with the next simplest function …

The identity function

Because every function in the lambda calculus takes exactly one argument, the next simplest thing we could do is to just return that argument: (lambda (a) a)

Let’s give it a try:

CL-USER> ((lambda (a) a) 1)
1
CL-USER> ((lambda (a) a) 2)
2
CL-USER> ((lambda (a) a) (lambda (a) a))
#<FUNCTION (LAMBDA (A)) {10024F117B}>

How do we give that lambda a name? Well, in Lisp that’s just a defun.

CL-USER> (defun I (a) a)
I
CL-USER> (I 1)
1
CL-USER> (I 2)
2
CL-USER> (I I)
# [Condition of type UNBOUND-VARIABLE] The variable I is unbound.

The identity of identity

If you’ve been working with Common Lisp long enough, that last one won’t surprise you too much. As I mentioned in the intro, CL is a Lisp-2. It has 2 separate “namespaces” for symbol values and symbol functions, but the only values in lambda calculus are functions.

This is one of the places a Lisp-1 (like Scheme) would have made our lives a little easier, but there is a workaround. If we copy I’s symbol function to its symbol value we get the effect we’re looking for.

CL-USER> (defparameter I #'I)
I
CL-USER> (I I)
#<FUNCTION I>

So that we don’t have to keep on repeating that step, let’s define a version of defun specifically for lambda functions.

(defmacro deflambda (sym args &body body)
  "Defines a lambda calculus function (using Lisp's native `defun`),
but also copies the function to `sym`'s symbol-value to give us the
lambda calculus' value semantics in which we can refer to function ƒ
as just `ƒ` rather than (function ƒ)` or `#'ƒ`."
  `(prog1
     (defun ,sym ,args ,@body)
     (defparameter ,sym #',sym)))
CL-USER> (deflambda I (a) a)
I
CL-USER> (I I)
#<FUNCTION I>

There is one more small problem with CL’s Lisp-2 nature, which we’ll get to later. (Hint: What should ((I I) I) return?)

In this part of the Lambda on Lisp series, we took a look at the identity function, and implemented our first workaround for treating lambda functions as *values*.