Verbs as Nouns, Functions as Data

Every language has nouns and verbs. Nouns are things and verbs are what we do on those things. Likewise, every programming language has data and functions. Data is some information and function is some procedure on that information. So, data can be thought of as nouns and functions can be thought of as verbs. For example, the input data to a sum procedure can be a price list of things in your shopping cart. Then the output data of the sum procedure will be the total amount payable. You add [function / verb] the numbers [data / noun]. Naturally, we have a wall in our minds that separates the nouns and verbs. However, Lisp breaks this wall down.

Lisp is an ancient programming language, at least insofar as a programming language can be ancient. Some excerpts from the GNU Humour Collection:

For God wrote in Lisp code
When he filled the leaves with green.
The fractal flowers and recursive roots:
The most lovely hack I’ve seen.
And when I ponder snowflakes,
never finding two the same,
I know God likes a language
with its own four-letter name.
…
And when I watch the lightning burn
Unbelievers to a crisp,
I know God had six days to work,
So he wrote it all in Lisp.

Lisp is supposed to be an elegant distillation of the principles of computation. Lisp is the “mind-expanding psychedelic” that programmers on Hacker News urge each other to “try before you die”. So, I decided to swallow the Lisp pill and go down the rabbit hole. It has been a week of using Lisp and that wall seems to be crumbling. But first, why must the wall fall?

Every language provides a framework within which we think. Some thoughts are only possible in some languages. Some words are more powerful than others.

Words in the English language have two main sources of origin: Latin, the fancy language of the Roman Empire and Anglo-Saxon, the plain language of the Germanic tribes. Latin words are long and lofty, ending with -ent and -ion: Precipitation, facilitation, development. Anglo-Saxon words are old and simple: home, sky, fire, walk, bread. They talk to the soul and tell the oldest truths. Now, some of these words can be both nouns and verbs: love, flood, walk. When the wall breaks down for these words, we can think more thoughts all at once:

Noun: We need love.
Verb: Love yourself.

Verb: I will walk the earth.
Noun: Some walks you have to take alone.

Noun: Ancient floods shaped civilizations.
Verb: Bitter-sweet memories flooded my mind.

As verbs become nouns, our ability to express ourselves expand. Inaccessible concepts can suddenly be touched.

As a programmer, you too can unlock new modes of problem-solving by breaking down this wall. In computer science, abstraction is the name of the game. And by treating functions as data, you can achieve higher levels of abstraction.

By generalizing common patterns of computation found within several functions, you can design higher-order functions. When you begin noticing such patterns, you will simplify. Mathematicians have been at this for ages. For example, they invented the sigma notation to generalize the concept of summation. Instead of dealing with sums of squares, sums of cubes and so on, they can express the notion of summation of any function $f(x)$ as: $$\sum\limits ^{b}_{n=a} f( n) =f( a) +\ \dotsc \ +f( b)$$ The field of calculus itself is about functions which manipulate functions.

That’s why Lisp treats its procedures as first-class citizens. They can be named by variables, passed as arguments, returned by other procedures and included in data structures. There is no wall separating procedures and data. Computational procedures as in verbs or actions are data as in nouns or things. But how do you even represent procedures as data?

Enter Lambda Calculus

Lambda Calculus is a way to write functions as computational procedures (from maths to computer science). So the function $x \mapsto x^{2}$ will be written as: $\lambda.x\ x^{2}$. When expressed this way, you will find that functions can indeed encode data types.

Let’s work through an example of using lambda calculus to represent the boolean data type true (1) and false (0) as functions. $$True = \lambda .x\ \lambda .y\ x$$ $$False = \lambda .x\ \lambda .y\ y$$ Here, we define a True function which takes two arguments and returns the first one. The False function takes two arguments and returns the second one. Now, we need to design the Not operator function such that it takes a boolean value and reverses it. $$Not = \lambda .a\ a\ False\ True$$ When we pass a function, representing some boolean data, to this operator function, we have:

\begin{align*} Not\ True & =( \lambda .a\ a\ False\ True) \ True\\
& =True\ False\ True\\
& =False \end{align*}

When we first substitute Not with its formula and apply it on True, we get a weird expression True False True. But remember this is Lambda Calculus. The leftmost True function takes the other two functions as arguments and returns the first one: False.

In the Lisp dialect of Scheme, we can express this as:

(define true   (lambda (x y) x))
(define false  (lambda (x y) y))
(define not    (lambda (a)  (a false true)))

(equal? (not true) false)

OUTPUT> Value: #t

Higher-order functions can be used in any language that grants the first-class status to functions, such as in Python:

true  = lambda x,y: x
false = lambda x,y: y
Not   = lambda a:   a(false, true)

Not(true) == false

OUTPUT> True

Look past the simple expressions to appreciate the underlying beauty. We have no data, these are all pure functions. In the last line of both examples, we compare two functions as if they were data. If we directly evaluate them, the interpreter returns the false function as if it were a data value.

(not true)

OUTPUT> Value: #[compound-procedure 12 false]

True and False doesn’t exist as boolean data anymore. These concepts are expressed as procedures. A computational procedure called true now represents the concrete data value of truth. Mind blown!