Making Sense of Lambda Calculus 4: Applicative vs. Normal Order

Normal Order: We Don't Do "Real World" Here

So normal order is the "default" order Lambda Calculus people do. Because it's theoretic, mathematical, and elegant.

The way it works is:

• Take the left function (it has to be a function).
• Apply it to the first argument following it.
• Replace these two with the result of the application/reduction. You remember reduction and application, right?
• Rinse and repeat.

Which is a simple way to do Lambda Calculus: just replace pieces of the expression. But this left-to-right order where arguments are only "evaluated" when they are needed... Is not friendly to how most programming languages work.

Applicative Order: Unelegant But Practical

What programming languages do is evaluating the arguments before calling a function. All of them arguments, usually in unpredictable (unspecified, undefined) order. So this type of code is likely to get one in trouble:

(defun omega (omega)
  (omega omega))

Applicative order (the name for this arguments-then-function order) is easier on the computer and might be more intuitive for the programmer. Well, unless the programmer (a rare occurence) is also a mathematician.

So we have this chasm separating two worlds: normal and applicative. The "code" written for normal order is not always runnable in applicative systems. We need some hacks to port Lambda Calculus programs there.

Hacks For Applicative Order

So I'm making a compiler from Binary Lambda Calculus to Lisp. And a whole programming language based on it—in Lisp too. Lisp is applicative. Most of the normal order function examples won't work. I have to somehow avoid infinite recursion and other niceties of normal order.

The biggest problem is the Y combinator. No, not that startup thing. The recursive "fixed point" combinator turning function recursive:

Y = λg.(λx.g (x x)) (λx.g (x x))

See that (x x) here? That's alarming: it's infinitely applying a given function to itself. Which is quite recursive and beautiful, yes. But it also leads to

Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.

PROCEED WITH CAUTION.
   [Condition of type SB-KERNEL::CONTROL-STACK-EXHAUSTED]

So the most fundamental tool of Lambda Calculus is lost on us. What do we do? Use Z combinator, of course!

Z = λf.((λx.(f λy.(x x y))) (λx.(f λy.(x x y))))

In addition to being longer and harder to read, it's stack-friendly. Z combinator establishes one more layer of indirection with these λy lambdas.

Conditionals and logic are another problematic point for applicative order. Because normal order conditionals evaluate both if branches regardless of. Applicative order conditionals can't do that. Because either (or both) of the branches can get recursive and kill the stack.

So my hack is: introduce another lambda layer into the conditional. And only call these lambdas after the branch is chosen. Something like:

((if condition?
     (lambda (_) do-dangerous-stuff)
     (lambda (_) do-other-dangerous-stuff)) nil)

Another option with conditionals would be making them built-in. And only evaluating one branch of if when interpreting code. But that means adding a special form and rules for it to my language. Too much hustle. So lambda-wrapping it is.

These two hacks cover the majority of practical stack deaths. So these are enough to me.

These applicative-vs.-normal order hacks are included by default in Lamber, my LC-compiling programming language. You only need recursion and conditionals, the rest is implementable with these. Just mind the stack!

Leave feedback! (via email)