Files
skills/public/lambda-calculus.html
zeekayandHanzo Dev 9e10c1c10e Each llms index points at the other two
hanzoskills.com/llms.txt now opens with the install line, the API
reference index and the company index, so an agent that lands on any
one of the three can find the rest.

robots.txt claimed 537 documents while llms.txt counts 920. The number
is gone from robots.txt; llms.txt derives it.

public/ is regenerated from scripts/site.py, which it had fallen
behind: the copy-prompt menu and agent bar were in the generator and
not in the committed pages. tests/site.mjs passes against the result.

Co-authored-by: Hanzo Dev <[email protected]>
2026-09-11 00:27:59 -07:00

578 lines
27 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!doctype html>
<html lang="en"><head>
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
<title>lambda-calculus</title>
<meta name="color-scheme" content="dark">
<style>
/* Committed to one visual world: a dark instrument panel. No light variant —
the dot field and the hairline rules only read on black, and a naive
inversion would wash both out. Every colour is painted explicitly so the page
never borrows a host background. */
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
:root{
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
--font-zen-pixel-square:'Zen Pixel Square',monospace;
--mono:var(--font-zen-mono);
--sans:var(--font-zen-sans);
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
--r:999px; --r-soft:14px;
}
*{box-sizing:border-box}
html{-webkit-text-size-adjust:100%}
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
/* The dot field. A halftone made of one repeating radial-gradient, faded out
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
/* No overflow clip here: the dot field is inset to the box already, and a clip
would cut off the copy-prompt menu. */
.hero{position:relative;border-bottom:1px solid var(--line)}
.hero::before{content:"";position:absolute;inset:0;
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
background-size:7px 7px;
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
pointer-events:none}
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
nav{border-bottom:1px solid var(--line)}
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
justify-content:space-between;align-items:center;gap:1rem}
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--ink);text-decoration:none;
display:inline-flex;align-items:center;gap:.6rem}
.brand i{font-style:normal;color:var(--faint)}
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--soft);text-decoration:none}
nav a.up:hover{color:var(--ink)}
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
h1 em{font-style:normal;color:var(--faint)}
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
line-height:1.2;font-weight:400}
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
.btn.solid:hover{background:#d8d8d4}
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
/* Copy-prompt selector. Each row copies the prompt for its own target. */
.copy{position:relative;display:inline-flex}
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
padding:.4rem;display:flex;flex-direction:column;
box-shadow:0 12px 32px rgba(0,0,0,.75)}
.menu[hidden]{display:none}
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
white-space:nowrap}
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
.mi:hover .mark{color:var(--ink)}
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
letter-spacing:.1em;text-transform:uppercase}
/* Works-with bar: one scrolling row, name and mark per agent. */
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
display:flex;align-items:center}
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
-webkit-overflow-scrolling:touch;
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
.bar::-webkit-scrollbar{display:none}
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
text-decoration:none;background:var(--ground)}
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
.agent .mark{width:.95rem;height:.95rem}
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
p{margin:0 0 1rem;max-width:70ch}
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
li{margin:.22rem 0}
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
text-decoration-color:var(--line-hi)}
a:hover{text-decoration-color:var(--ink)}
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
display:block;overflow-x:auto}
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
.curl{display:block;background:var(--panel);border:1px solid var(--line);
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
white-space:pre;line-height:1.9}
.curl b{color:var(--ink);font-weight:400}
.curl i{font-style:normal;color:var(--faint)}
/* index */
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
#q:focus{outline:none;border-color:var(--soft)}
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
text-transform:uppercase;margin:0 0 2rem}
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
padding-bottom:.45rem}
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
border-radius:var(--r-soft);text-decoration:none}
.row:hover{background:#0a0a0a}
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
color:var(--faint);font-size:.85rem}
footer a{color:var(--soft)}
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
margin:0 0 2rem;font-size:.85rem}
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
border-bottom:1px solid var(--line);padding-bottom:.4rem}
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
.fmap a:hover{text-decoration:underline}
.fmap div{color:var(--faint);line-height:1.5}
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
@media (max-width:640px){
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
.btns{gap:.5rem}
.btn{padding:.75rem 1.15rem;font-size:.68rem}
.copy,.copy .btn{width:100%;justify-content:center}
.menu{left:0;right:0;min-width:0}
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
.strip b{border-right:0;padding-right:0}
.bar{width:100%}
}
</style>
<link rel="alternate" type="text/markdown" href="/lambda-calculus.md">
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/lambda-calculus">
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/lambda-calculus.md
Index: https://hanzoskills.com/llms.txt
Corpus: https://hanzoskills.com/all.md
Append .md to any path for the markdown twin. -->
<body>
<nav><div class="in">
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
<a class="up" href="/">All skills</a>
</div></nav>
<div class="wrap">
<h1>lambda-calculus</h1><p class="lede">Lambda calculus including untyped, simply typed, Church encodings, and reduction strategies</p><h1>Lambda Calculus</h1>
<p><strong>Scope</strong>: Untyped λ-calculus, simply typed λ-calculus, Church encodings, β-reduction, combinators <strong>Lines</strong>: ~420 <strong>Last Updated</strong>: 2025-10-25</p>
<h2>When to Use This Skill</h2>
<p>Activate this skill when:</p>
<ul><li>Understanding foundations of functional programming</li><li>Studying computation theory and Church-Turing thesis</li><li>Implementing interpreters for functional languages</li><li>Working with higher-order functions and closures</li><li>Formalizing programming language semantics</li><li>Exploring type theory foundations</li></ul>
<h2>Core Concepts</h2>
<h3>Syntax and Terms</h3>
<p><strong>λ-terms</strong>:</p>
<ul><li>Variables: x, y, z, ...</li><li>Abstraction: λx. M (function with parameter x, body M)</li><li>Application: M N (apply M to N)</li></ul>
<pre><code class="lang-python">from dataclasses import dataclass
from typing import Union
# Abstract syntax tree for λ-terms
@dataclass
class Var:
name: str
def __repr__(self):
return self.name
@dataclass
class Abs:
&quot;&quot;&quot;Abstraction: λx. body&quot;&quot;&quot;
param: str
body: &#x27;Term&#x27;
def __repr__(self):
return f&quot;(λ{self.param}. {self.body})&quot;
@dataclass
class App:
&quot;&quot;&quot;Application: func arg&quot;&quot;&quot;
func: &#x27;Term&#x27;
arg: &#x27;Term&#x27;
def __repr__(self):
return f&quot;({self.func} {self.arg})&quot;
Term = Union[Var, Abs, App]
# Example terms
identity = Abs(&#x27;x&#x27;, Var(&#x27;x&#x27;)) # λx. x
const = Abs(&#x27;x&#x27;, Abs(&#x27;y&#x27;, Var(&#x27;x&#x27;))) # λx. λy. x
apply_twice = Abs(&#x27;f&#x27;, Abs(&#x27;x&#x27;, App(Var(&#x27;f&#x27;), App(Var(&#x27;f&#x27;), Var(&#x27;x&#x27;))))) # λf. λx. f (f x)
print(f&quot;Identity: {identity}&quot;)
print(f&quot;Const: {const}&quot;)
print(f&quot;Apply twice: {apply_twice}&quot;)</code></pre>
<h3>Free and Bound Variables</h3>
<p><strong>Free variables</strong>: FV(M) = variables not bound by λ <strong>Bound variables</strong>: Variables under a λ-abstraction</p>
<pre><code class="lang-python">def free_vars(term: Term) -&gt; set:
&quot;&quot;&quot;Compute set of free variables&quot;&quot;&quot;
match term:
case Var(name):
return {name}
case Abs(param, body):
return free_vars(body) - {param}
case App(func, arg):
return free_vars(func) | free_vars(arg)
# Examples
print(f&quot;FV(λx. x) = {free_vars(identity)}&quot;) # ∅
print(f&quot;FV(λx. y) = {free_vars(Abs(&#x27;x&#x27;, Var(&#x27;y&#x27;)))}&quot;) # {y}
print(f&quot;FV((λx. x) y) = {free_vars(App(identity, Var(&#x27;y&#x27;)))}&quot;) # {y}</code></pre>
<h3>Substitution and α-conversion</h3>
<p><strong>Substitution</strong>: M[x := N] replaces free occurrences of x in M with N <strong>α-conversion</strong>: Rename bound variables (λx. M) →_α (λy. M[x := y])</p>
<pre><code class="lang-python">def substitute(term: Term, var: str, replacement: Term) -&gt; Term:
&quot;&quot;&quot;
term[var := replacement]
Capture-avoiding substitution
&quot;&quot;&quot;
match term:
case Var(name):
return replacement if name == var else term
case Abs(param, body):
if param == var:
# Variable shadowed, don&#x27;t substitute
return term
elif param in free_vars(replacement):
# Capture would occur, need α-conversion
fresh = fresh_var(param, free_vars(term) | free_vars(replacement))
renamed_body = substitute(body, param, Var(fresh))
return Abs(fresh, substitute(renamed_body, var, replacement))
else:
return Abs(param, substitute(body, var, replacement))
case App(func, arg):
return App(substitute(func, var, replacement), substitute(arg, var, replacement))
_counter = 0
def fresh_var(base: str, avoid: set) -&gt; str:
&quot;&quot;&quot;Generate fresh variable name&quot;&quot;&quot;
global _counter
while True:
name = f&quot;{base}{_counter}&quot; if _counter &gt; 0 else base
_counter += 1
if name not in avoid:
return name
# Example: (λx. λy. x)[x := y] with capture avoidance
term = Abs(&#x27;x&#x27;, Abs(&#x27;y&#x27;, Var(&#x27;x&#x27;)))
result = substitute(term, &#x27;x&#x27;, Var(&#x27;y&#x27;))
print(f&quot;{term}[x := y] = {result}&quot;)</code></pre>
<h3>β-reduction</h3>
<p><strong>β-reduction</strong>: (λx. M) N →_β M[x := N]</p>
<p><strong>Reduction strategies</strong>:</p>
<ul><li>Normal order: leftmost-outermost redex first</li><li>Applicative order: leftmost-innermost redex first (call-by-value)</li><li>Call-by-name: like normal order but no reduction under λ</li></ul>
<pre><code class="lang-python">def is_redex(term: Term) -&gt; bool:
&quot;&quot;&quot;Check if term is a β-redex: (λx. M) N&quot;&quot;&quot;
match term:
case App(Abs(_, _), _):
return True
case _:
return False
def beta_reduce_once(term: Term) -&gt; Term:
&quot;&quot;&quot;Perform one β-reduction step (normal order)&quot;&quot;&quot;
match term:
case App(Abs(param, body), arg):
# β-redex: reduce it
return substitute(body, param, arg)
case App(func, arg):
# Try reducing function first
if not isinstance(func, Var):
return App(beta_reduce_once(func), arg)
else:
# Then try reducing argument
return App(func, beta_reduce_once(arg))
case Abs(param, body):
# Reduce under abstraction (normal order does this)
return Abs(param, beta_reduce_once(body))
case _:
return term
def normalize(term: Term, max_steps: int = 100) -&gt; Term:
&quot;&quot;&quot;Reduce to normal form (if exists)&quot;&quot;&quot;
for _ in range(max_steps):
try:
new_term = beta_reduce_once(term)
if new_term == term:
break
term = new_term
except:
break
return term
# Example: (λx. x) (λy. y) →_β λy. y
term = App(identity, identity)
result = normalize(term)
print(f&quot;{term} →* {result}&quot;)
# Example: (λf. λx. f (f x)) (λy. y) z →_β z
term = App(App(apply_twice, identity), Var(&#x27;z&#x27;))
result = normalize(term)
print(f&quot;{term} →* {result}&quot;)</code></pre>
<h3>Church Encodings</h3>
<p><strong>Church numerals</strong>: Encode natural numbers as functions</p>
<pre><code class="lang-python">def church_numeral(n: int) -&gt; Term:
&quot;&quot;&quot;
n̅ = λf. λx. f^n x
0 = λf. λx. x
1 = λf. λx. f x
2 = λf. λx. f (f x)
&quot;&quot;&quot;
body = Var(&#x27;x&#x27;)
for _ in range(n):
body = App(Var(&#x27;f&#x27;), body)
return Abs(&#x27;f&#x27;, Abs(&#x27;x&#x27;, body))
# Successor: succ = λn. λf. λx. f (n f x)
succ = Abs(&#x27;n&#x27;, Abs(&#x27;f&#x27;, Abs(&#x27;x&#x27;,
App(Var(&#x27;f&#x27;), App(App(Var(&#x27;n&#x27;), Var(&#x27;f&#x27;)), Var(&#x27;x&#x27;)))
)))
# Addition: add = λm. λn. λf. λx. m f (n f x)
add = Abs(&#x27;m&#x27;, Abs(&#x27;n&#x27;, Abs(&#x27;f&#x27;, Abs(&#x27;x&#x27;,
App(App(Var(&#x27;m&#x27;), Var(&#x27;f&#x27;)), App(App(Var(&#x27;n&#x27;), Var(&#x27;f&#x27;)), Var(&#x27;x&#x27;)))
))))
# Multiplication: mul = λm. λn. λf. m (n f)
mul = Abs(&#x27;m&#x27;, Abs(&#x27;n&#x27;, Abs(&#x27;f&#x27;,
App(Var(&#x27;m&#x27;), App(Var(&#x27;n&#x27;), Var(&#x27;f&#x27;)))
)))
# Example: 2 + 3
two = church_numeral(2)
three = church_numeral(3)
five = normalize(App(App(add, two), three))
print(f&quot;2̅ + 3̅ = {five}&quot;)</code></pre>
<p><strong>Church booleans</strong>:</p>
<pre><code class="lang-python"># true = λt. λf. t
# false = λt. λf. f
true = Abs(&#x27;t&#x27;, Abs(&#x27;f&#x27;, Var(&#x27;t&#x27;)))
false = Abs(&#x27;t&#x27;, Abs(&#x27;f&#x27;, Var(&#x27;f&#x27;)))
# if = λb. λt. λf. b t f (identity in λ-calculus!)
if_then_else = Abs(&#x27;b&#x27;, Abs(&#x27;t&#x27;, Abs(&#x27;f&#x27;, App(App(Var(&#x27;b&#x27;), Var(&#x27;t&#x27;)), Var(&#x27;f&#x27;)))))
# and = λp. λq. p q p
and_op = Abs(&#x27;p&#x27;, Abs(&#x27;q&#x27;, App(App(Var(&#x27;p&#x27;), Var(&#x27;q&#x27;)), Var(&#x27;p&#x27;))))
# or = λp. λq. p p q
or_op = Abs(&#x27;p&#x27;, Abs(&#x27;q&#x27;, App(App(Var(&#x27;p&#x27;), Var(&#x27;p&#x27;)), Var(&#x27;q&#x27;))))
# not = λp. λa. λb. p b a
not_op = Abs(&#x27;p&#x27;, Abs(&#x27;a&#x27;, Abs(&#x27;b&#x27;, App(App(Var(&#x27;p&#x27;), Var(&#x27;b&#x27;)), Var(&#x27;a&#x27;)))))
# Example: not true →_β false
result = normalize(App(not_op, true))
print(f&quot;not true →* {result}&quot;)</code></pre>
<h3>Combinators</h3>
<p><strong>S, K, I combinators</strong> (SKI combinator calculus):</p>
<pre><code class="lang-python"># I = λx. x (identity)
I = Abs(&#x27;x&#x27;, Var(&#x27;x&#x27;))
# K = λx. λy. x (constant)
K = Abs(&#x27;x&#x27;, Abs(&#x27;y&#x27;, Var(&#x27;x&#x27;)))
# S = λx. λy. λz. x z (y z)
S = Abs(&#x27;x&#x27;, Abs(&#x27;y&#x27;, Abs(&#x27;z&#x27;,
App(App(Var(&#x27;x&#x27;), Var(&#x27;z&#x27;)), App(Var(&#x27;y&#x27;), Var(&#x27;z&#x27;)))
)))
# Theorem: SKK = I
SKK = App(App(S, K), K)
result = normalize(SKK)
print(f&quot;S K K →* {result}&quot;) # Should reduce to identity
# Y combinator (fixed-point): Y = λf. (λx. f (x x)) (λx. f (x x))
Y = Abs(&#x27;f&#x27;,
App(
Abs(&#x27;x&#x27;, App(Var(&#x27;f&#x27;), App(Var(&#x27;x&#x27;), Var(&#x27;x&#x27;)))),
Abs(&#x27;x&#x27;, App(Var(&#x27;f&#x27;), App(Var(&#x27;x&#x27;), Var(&#x27;x&#x27;))))
)
)
# Property: Y f →_β f (Y f)
# Used for recursion in λ-calculus</code></pre>
<h3>Simply Typed λ-calculus</h3>
<p><strong>Types</strong>: τ ::= α | τ → τ</p>
<pre><code class="lang-python">from dataclasses import dataclass
from typing import Union as TUnion
@dataclass
class TVar:
&quot;&quot;&quot;Type variable&quot;&quot;&quot;
name: str
def __repr__(self):
return self.name
@dataclass
class TArrow:
&quot;&quot;&quot;Function type: τ₁ → τ₂&quot;&quot;&quot;
input: &#x27;Type&#x27;
output: &#x27;Type&#x27;
def __repr__(self):
return f&quot;({self.input} → {self.output})&quot;
Type = TUnion[TVar, TArrow]
# Typing context: Γ = {x₁: τ₁, ..., xₙ: τₙ}
Context = dict[str, Type]
def type_check(term: Term, context: Context) -&gt; Type:
&quot;&quot;&quot;
Type checking for simply typed λ-calculus
Γ ⊢ M : τ
&quot;&quot;&quot;
match term:
case Var(name):
if name not in context:
raise TypeError(f&quot;Unbound variable: {name}&quot;)
return context[name]
case Abs(param, body):
# Need type annotation in practice
# For now, assume param has type α
param_type = TVar(&#x27;α&#x27;)
new_context = context | {param: param_type}
body_type = type_check(body, new_context)
return TArrow(param_type, body_type)
case App(func, arg):
func_type = type_check(func, context)
arg_type = type_check(arg, context)
match func_type:
case TArrow(input_type, output_type):
if input_type != arg_type:
raise TypeError(f&quot;Type mismatch: expected {input_type}, got {arg_type}&quot;)
return output_type
case _:
raise TypeError(f&quot;Expected function type, got {func_type}&quot;)
# Example: type check identity function
try:
id_type = type_check(identity, {})
print(f&quot;Type of λx. x: {id_type}&quot;) # α → α
except TypeError as e:
print(f&quot;Type error: {e}&quot;)</code></pre>
<hr>
<h2>Patterns</h2>
<h3>Pattern 1: Recursion via Fixed Points</h3>
<pre><code class="lang-python"># Factorial using Y combinator
# fact = Y (λf. λn. if (n = 0) 1 (n * f (n-1)))
# In practice, use recursive definitions with Y:
def factorial_lambda():
&quot;&quot;&quot;
Factorial: F = λf. λn. if (n = 0) 1 (n · f (pred n))
fact = Y F
&quot;&quot;&quot;
# Simplified representation
return &quot;Y (λf. λn. if (isZero n) 1 (mul n (f (pred n))))&quot;</code></pre>
<h3>Pattern 2: Encoding Data Structures</h3>
<pre><code class="lang-python"># Pairs: pair = λx. λy. λf. f x y
pair = Abs(&#x27;x&#x27;, Abs(&#x27;y&#x27;, Abs(&#x27;f&#x27;, App(App(Var(&#x27;f&#x27;), Var(&#x27;x&#x27;)), Var(&#x27;y&#x27;)))))
# fst = λp. p (λx. λy. x)
fst = Abs(&#x27;p&#x27;, App(Var(&#x27;p&#x27;), K))
# snd = λp. p (λx. λy. y)
snd = Abs(&#x27;p&#x27;, App(Var(&#x27;p&#x27;), Abs(&#x27;x&#x27;, Abs(&#x27;y&#x27;, Var(&#x27;y&#x27;)))))
# Lists (Church encoding):
# nil = λc. λn. n
# cons = λh. λt. λc. λn. c h (t c n)
nil = Abs(&#x27;c&#x27;, Abs(&#x27;n&#x27;, Var(&#x27;n&#x27;)))
cons = Abs(&#x27;h&#x27;, Abs(&#x27;t&#x27;, Abs(&#x27;c&#x27;, Abs(&#x27;n&#x27;,
App(App(Var(&#x27;c&#x27;), Var(&#x27;h&#x27;)), App(App(Var(&#x27;t&#x27;), Var(&#x27;c&#x27;)), Var(&#x27;n&#x27;)))
))))</code></pre>
<hr>
<h2>Quick Reference</h2>
<h3>Reduction Rules</h3>
<pre><code>β-reduction: (λx. M) N →_β M[x := N]
α-conversion: λx. M →_α λy. M[x := y] (y fresh)
η-conversion: λx. M x →_η M (if x ∉ FV(M))</code></pre>
<h3>Church Encodings</h3>
<p>| Concept | Encoding | |---------|----------| | 0 | λf. λx. x | | succ | λn. λf. λx. f (n f x) | | true | λt. λf. t | | false | λt. λf. f | | pair | λx. λy. λf. f x y | | nil | λc. λn. n |</p>
<h3>Combinators</h3>
<pre><code>I = λx. x
K = λx. λy. x
S = λx. λy. λz. x z (y z)
Y = λf. (λx. f (x x)) (λx. f (x x))</code></pre>
<hr>
<h2>Anti-Patterns</h2>
<p>❌ <strong>Forgetting capture avoidance</strong>: (λx. λy. x)[x := y] ≠ λy. y (capture!) ✅ Use α-conversion: (λx. λy₀. x)[x := y] = λy₀. y</p>
<p>❌ <strong>Assuming all terms terminate</strong>: Ω = (λx. x x) (λx. x x) loops forever ✅ Simply typed λ-calculus has strong normalization</p>
<p>❌ <strong>Confusing β-equivalence with syntactic equality</strong>: (λx. x) ≠ (λy. y) syntactically but =_β ✅ Use α-conversion or compare normal forms</p>
<hr>
<h2>Related Skills</h2>
<ul><li><code>type-systems.md</code> - Type checking, inference, polymorphism</li><li><code>dependent-types.md</code> - Dependent function types, Π-types</li><li><code>curry-howard.md</code> - Propositions as types correspondence</li><li><code>operational-semantics.md</code> - Formal semantics for λ-calculus</li><li><code>formal/lean-proof-basics.md</code> - Formalizing λ-calculus in Lean</li></ul>
<hr>
<p><strong>Last Updated</strong>: 2025-10-25 <strong>Format Version</strong>: 1.0 (Atomic)</p>
<footer>
<div class="fmap">
<div><b>Build</b>
<a href="https://hanzo.app">hanzo.app</a> app builder
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
<div><b>Run</b>
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
<div><b>Account</b>
<a href="https://hanzo.id">hanzo.id</a> sign in
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
<div><b>Company</b>
<a href="https://hanzo.ai">hanzo.ai</a> canonical
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
</div>
<div class="fend"><a href="/lambda-calculus.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>