\documentclass[12pt]{article}
\usepackage[T2A,OT1]{fontenc}
\usepackage[default]{cantarell}
\usepackage[a4paper, top=20mm, bottom=20mm, left=20mm, right=20mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[russian, english]{babel}
\usepackage{tabu}
\usepackage{hyperref}
\usepackage{parskip}
\usepackage{graphicx}
\usepackage{tabularx}
\usepackage[normalem]{ulem}
\usepackage{float}
\floatstyle{boxed}
\restylefloat{figure}
\usepackage{setspace}
\onehalfspacing
\author{Artyom Bologov \href{mailto:lambda-4@aartaka.me}{(email)}}
\date{\today}
\title{Making Sense of Lambda Calculus 4: Applicative vs. Normal Order}
\makeatletter
\def\endenv{\expandafter\end\expandafter{\@currenvir}}
\makeatother
\begin{document}
\maketitle

\includegraphics[width=\textwidth,height=\textheight,keepaspectratio]{./assets/lambda-4.png}

\paragraph{Timeline of Making Sense of Lambda Calculus} \begin{quote}
\begin{itemize}\item \href{run:lambda-0}{0: Abstration, Reduction, Substitution?}
\item \href{run:lambda-1}{1: Ignorant, Lazy, and Greedy Evaluation}
\item \href{run:lambda-2}{2: Numerous Quirks of Numbers}
\item \href{run:lambda-3}{3: Truth or Dare With Booleans}
\item \href{run:lambda-4}{4: Applicative vs. Normal Order}
\item \href{run:lambda-5}{5: Bring Computation to (Aggregate) Data}
\item \href{run:threading}{Interlude: Functional Threading “Macros”}
\item \href{run:lambda-6}{6: Recurring Problems}
\end{itemize}
\end{quote}

I’m slowly getting back to Lambda Calculus.
\href{https://github.com/aartaka/cl-blc}{I implemented my own compiler/toolkit for LC},
and
\href{https://github.com/aartaka/lamber}{made my own programming language, Lamber}
so I can play with
\href{https://github.com/aartaka/stdlambda}{my standard library for LC}
and otherwise write non-trivial programs in this Turing tarpit.

My BLC compiler uses Lisp-native lambdas compiled from s-expressions I generate from Binary Lambda Calculus code.
Which is a verbose and obscure way to say: I just run Lisp instead of BLC.
Which means I have restrictions on stack size.
And most LC programs out there don’t work—they imply normal order reduction instead of applicative order.

Say what now?
Normal? Applicative? What’s that?

\section*{Normal Order: We Don’t Do “Real World” Here} \label{normal}

So normal order is the “default” order Lambda Calculus people do.
Because it’s theoretic, mathematical, and elegant.

The way it works is:

\begin{itemize}\item Take the left function (it has to be a function).
\item Apply it to the first argument following it.
\item Replace these two with the result of the application / reduction.
\href{run:lambda-0}{You remember reduction and application, right?}
\item Rinse and repeat.
\end{itemize}

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.

\section*{Applicative Order: Unelegant But Practical} \label{applicative}

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:

\begin{figure}[h!]\begin{verbatim}
(defun omega (omega)
  (omega omega))
\end{verbatim}\caption{Recursive code that kills applicative order systems}\end{figure}

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.

\section*{Hacks For Applicative Order} \label{hacks}

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:

\begin{figure}[h!]\begin{verbatim}
Y = λg.(λx.g (x x)) (λx.g (x x))
\end{verbatim}\caption{Y combinator}\end{figure}

See that \verb|(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

\begin{figure}[h!]\begin{verbatim}
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]
\end{verbatim}\caption{Ooooops, stack overflow!}\end{figure}

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

\begin{figure}[h!]\begin{verbatim}
Z = λf.((λx.(f λy.(x x y))) (λx.(f λy.(x x y))))
\end{verbatim}\caption{Z combinator}\end{figure}

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

Conditionals and logic are another problematic point for applicative order.
Because normal order conditionals evaluate both \verb|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:

\begin{figure}[h!]\begin{verbatim}
((if condition?
     (lambda (_) do-dangerous-stuff)
     (lambda (_) do-other-dangerous-stuff)) nil)
\end{verbatim}\caption{Lambda-wrapped conditionals}\end{figure}

Another option with conditionals would be making them built-in.
And only evaluating one branch of \verb|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
\href{https://github.com/aartaka/lamber}{Lamber, my LC-compiling programming language}.
You only need recursion and conditionals, the rest is implementable with these.
Just mind the stack!

\href{run:lambda-5}{Back to Lambda Calculus data structures then}!


\par\noindent\rule{\textwidth}{0.4pt}
\href{https://creativecommons.org/licenses/by/4.0}{CC-BY 4.0} 2022-2026 by Artyom Bologov (aartaka,)
\href{https://codeberg.org/aartaka/pages/commit/a91befa}{with one commit remixing Claude-generated code}.
Any and all opinions listed here are my own and not representative of my employers; future, past and present.
\end{document}