The Misp Chronicles IX: fn

Functions are created with the fn keyword. Other Lisps use lambda in tribute to the Lambda Calculus. Unfortunately, the word “lambda” makes me think of llamas, which are quite upsetting, so we’ll use fn instead. A function has two parts. The head is a list of symbols that are bound when the function is invoked. The body is an expression which uses those symbols. Consider the function (fn (x) (pair x x)). The subexpression (x) is its head or parameter list. The subexpression (pair x x) is the the body.

We invoke a function by making it the first element in a list. The subsequent items are used as arguments. For example, ((fn (x) (pair x x)) ‘hello) takes an argument x and returns x paired with itself. In this invocation, ‘hello is bound to x. This means that x refers to ‘hello when the body of the function is evaluated. Every time we come across x we know to replace it with ‘hello. Thus (pair x x) means the same thing as (pair ‘hello ‘hello) which evaluates to (hello . hello).

When describing the Lambda Calculus, we usually say that ‘hello is substituted for all (free) occurrences of x in (pair x x). Lisps see the world differently. Instead of replacing x upfront, we wait. We make a note that x ought to be replaced with ‘hello, but we don’t actually do the replacement until its needed. The collection of notes saying what ought to be replaced is called an environment. We’ll talk a lot more about environments in the future.

For today, we’ll introduce some shorthand for functions. Experienced Lisp programmers say, “after a while you don’t notice the parenthesis.” I’m not one of them. With all the rough terrain ahead, I don’t want us overburdened by parens. I’d rather trade simplicity for clarity. We’ll adopt Ruby like block syntax for our function definitions.

Let’s start with ((fn (x) (pair x x)) ‘hello). Instead of writing (fn …), let’s use curly braces {...}. Instead of grouping arguments with parenthesis (x), let’s group them with vertical bars |x|. These are little changes, but I think it helps: ({|x|(pair x x)} ‘hello). As another example, consider this function (fn (x y) y) which returns its second argument. It becomes {|x y| y}.

This shorthand leaves a two sticky cases. The expression ((fn (x . xs) xs) ‘a ‘b ‘c) ends the parameter list with the symbol xs instead of nil. (Recall that (x y) is short for (x . (y . nil)).) What do we do now? Scheme binds x to the first argument a and binds xs to the rest of the arguments (b c). Therefore, ((fn (x . xs) xs) ‘a ‘b ‘c) evaluates to (b c). The shorthand for this must wait because we’ve stumbled across a curious hole. Intrepid explorers we will see what there is to see.

Recall that (tl ‘(a b c)) is (b c). We just saw a function that is remarkably similar. Can we go all the way? Note that ((fn (x . xs) xs) ‘a ‘b ‘c) is the same as ((fn (x . xs) xs) . ‘(a b c)). We need to generalize from ‘(a b c) to any old list. We’re in luck, functions are good at this. We just replace ‘(a b c) by a symbol ls, bind ls by a function, and apply ‘(a b c).

Behold ((fn (ls) ((fn (x . xs) xs) . ls)) ‘(a b c)). The expression evaluates to (b c) just like (tl ‘(a b c)). The equality isn’t an accident: it works in general. We’ve defined a function that does the same thing as tl without mentioning tl. So tl is not an irreducible primitive in Misp. We can replace tl with the function (fn (ls) ((fn (x . xs) xs) . ls)). Similarly, we can replace hd with the function (fn (ls) ((fn (x . xs) x) . ls)). fn just ate hd and tl. The function construct is a cannibal god. It demands the sacrifice of primitives.