\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-1@aartaka.me}{(email)}}
\date{\today}
\title{Making Sense of Lambda Calculus 1: Ignorant, Lazy, and Greedy Evaluation}
\makeatletter
\def\endenv{\expandafter\end\expandafter{\@currenvir}}
\makeatother
\begin{document}
\maketitle

\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}

Lambda Calculus is not hard, but some parts of it are confusing.
While I’ve
\href{run:lambda-0}{sorted out the confusing terms},
I’m still getting tripped over

\begin{itemize}\item missing parentheses,
\item unclear lambda scope,
\item and general computation / definition order.
\end{itemize}

This post is me trying to clear up Lambda Calculus evaluation properties.

\section*{Being Ignorant} \label{ignorant}

My programmer background doesn’t make it easier.
I’m used to the fact that arguments are evaluated before the function call.

\begin{figure}[h!]\begin{verbatim}
int i = 0;
f(i++, i++, i);
// equivalent to f(0, 1, 2)
\end{verbatim}\caption{Order of evaluation in most programming language}\end{figure}

Lambda Calculus is working the other way around.
Arguments are evaluated only when the function is applied to them.
And the function is evaluated before the arguments.
You can have a looped computation as argument to your function.
And that doesn’t necessarily makes your function stuck.
Depends on what is the order of computation.
Here’s an example:

\begin{figure}[h!]\begin{verbatim}
int i = 0;
f(i++, i++, i);
// equivalent to
// f1 = f
// f2 = f1(i++)
// f3 = f2(i++)
// result = f3(i)
\end{verbatim}\caption{Order of evaluation in Lambda Calculus}\end{figure}

So there actually is computation in between argument evaluation.
Scary, right?
But that’s how it works.

\section*{Being Lazy} \label{lazy}

It’s often the case with LC examples that they omit parentheses.
Some of these are uncertain in what to do first.

\begin{figure}[h!]\begin{verbatim}
f g h
\end{verbatim}\caption{Example of confusing application order}\end{figure}

This one first applies \verb|f| to \verb|g| and then applies the result of that to \verb|h|.
Spelling that out doesn’t make it clearer for me.
But here’s the point: the argument are lazily collected.
So you only take an argument when you need one.
And, again, you don’t evaluate arguments until you need to use them.

\section*{Being Greedy} \label{greedy}

Okay, so the order of application is lazy and minimalist.
It only takes arguments when it needs them.
If a function needs only one argument, it only takes one.

\begin{figure}[h!]\begin{verbatim}
(λx.5) y z // only consumes y and returns 5 (to be applied to z later)
\end{verbatim}\caption{Example of unused argument computation}\end{figure}

What’s extremely inconsistent is that abstraction is greedy.
It extends as far to the right as possible.
The previous example would be a single lambda if we remove parentheses

\begin{figure}[h!]\begin{verbatim}
λx.5 y z // a single huge lambda.
\end{verbatim}\caption{Example of abstraction greediness}\end{figure}

That’s why most examples you see out in the wild parenthesize the function:
they need to restrict the abstraction from eating up too much expressions.

\section*{Up next: Numerous Quirks of Numbers} \label{up-next}

Lambda Calculus might seem really nasty at this point: it’s Ignorant, Lazy, and Greedy.
But I’m being misleading here: LC is still a powerful idea.
And my negative impressions might be a consequence of getting repulsed by its specificities.
So let’s bear with it and get to appreciate it while diving deeper.

We’ve established the order
of typical LC operations
and
\href{run:lambda-0}{understood basic terms}
used in LC.
Now to the actual practice: Church Numerals encoding numbers!
Arithmetic, numbers as function applications, elegant multiplication and exponentiation, and... ugly subtraction.


\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}