mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
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]>
578 lines
27 KiB
HTML
578 lines
27 KiB
HTML
<!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:
|
||
"""Abstraction: λx. body"""
|
||
param: str
|
||
body: 'Term'
|
||
|
||
def __repr__(self):
|
||
return f"(λ{self.param}. {self.body})"
|
||
|
||
@dataclass
|
||
class App:
|
||
"""Application: func arg"""
|
||
func: 'Term'
|
||
arg: 'Term'
|
||
|
||
def __repr__(self):
|
||
return f"({self.func} {self.arg})"
|
||
|
||
Term = Union[Var, Abs, App]
|
||
|
||
# Example terms
|
||
identity = Abs('x', Var('x')) # λx. x
|
||
const = Abs('x', Abs('y', Var('x'))) # λx. λy. x
|
||
apply_twice = Abs('f', Abs('x', App(Var('f'), App(Var('f'), Var('x'))))) # λf. λx. f (f x)
|
||
|
||
print(f"Identity: {identity}")
|
||
print(f"Const: {const}")
|
||
print(f"Apply twice: {apply_twice}")</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) -> set:
|
||
"""Compute set of free variables"""
|
||
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"FV(λx. x) = {free_vars(identity)}") # ∅
|
||
print(f"FV(λx. y) = {free_vars(Abs('x', Var('y')))}") # {y}
|
||
print(f"FV((λx. x) y) = {free_vars(App(identity, Var('y')))}") # {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) -> Term:
|
||
"""
|
||
term[var := replacement]
|
||
Capture-avoiding substitution
|
||
"""
|
||
match term:
|
||
case Var(name):
|
||
return replacement if name == var else term
|
||
|
||
case Abs(param, body):
|
||
if param == var:
|
||
# Variable shadowed, don'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) -> str:
|
||
"""Generate fresh variable name"""
|
||
global _counter
|
||
while True:
|
||
name = f"{base}{_counter}" if _counter > 0 else base
|
||
_counter += 1
|
||
if name not in avoid:
|
||
return name
|
||
|
||
# Example: (λx. λy. x)[x := y] with capture avoidance
|
||
term = Abs('x', Abs('y', Var('x')))
|
||
result = substitute(term, 'x', Var('y'))
|
||
print(f"{term}[x := y] = {result}")</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) -> bool:
|
||
"""Check if term is a β-redex: (λx. M) N"""
|
||
match term:
|
||
case App(Abs(_, _), _):
|
||
return True
|
||
case _:
|
||
return False
|
||
|
||
def beta_reduce_once(term: Term) -> Term:
|
||
"""Perform one β-reduction step (normal order)"""
|
||
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) -> Term:
|
||
"""Reduce to normal form (if exists)"""
|
||
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"{term} →* {result}")
|
||
|
||
# Example: (λf. λx. f (f x)) (λy. y) z →_β z
|
||
term = App(App(apply_twice, identity), Var('z'))
|
||
result = normalize(term)
|
||
print(f"{term} →* {result}")</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) -> Term:
|
||
"""
|
||
n̅ = λf. λx. f^n x
|
||
0 = λf. λx. x
|
||
1 = λf. λx. f x
|
||
2 = λf. λx. f (f x)
|
||
"""
|
||
body = Var('x')
|
||
for _ in range(n):
|
||
body = App(Var('f'), body)
|
||
return Abs('f', Abs('x', body))
|
||
|
||
# Successor: succ = λn. λf. λx. f (n f x)
|
||
succ = Abs('n', Abs('f', Abs('x',
|
||
App(Var('f'), App(App(Var('n'), Var('f')), Var('x')))
|
||
)))
|
||
|
||
# Addition: add = λm. λn. λf. λx. m f (n f x)
|
||
add = Abs('m', Abs('n', Abs('f', Abs('x',
|
||
App(App(Var('m'), Var('f')), App(App(Var('n'), Var('f')), Var('x')))
|
||
))))
|
||
|
||
# Multiplication: mul = λm. λn. λf. m (n f)
|
||
mul = Abs('m', Abs('n', Abs('f',
|
||
App(Var('m'), App(Var('n'), Var('f')))
|
||
)))
|
||
|
||
# Example: 2 + 3
|
||
two = church_numeral(2)
|
||
three = church_numeral(3)
|
||
five = normalize(App(App(add, two), three))
|
||
print(f"2̅ + 3̅ = {five}")</code></pre>
|
||
<p><strong>Church booleans</strong>:</p>
|
||
<pre><code class="lang-python"># true = λt. λf. t
|
||
# false = λt. λf. f
|
||
true = Abs('t', Abs('f', Var('t')))
|
||
false = Abs('t', Abs('f', Var('f')))
|
||
|
||
# if = λb. λt. λf. b t f (identity in λ-calculus!)
|
||
if_then_else = Abs('b', Abs('t', Abs('f', App(App(Var('b'), Var('t')), Var('f')))))
|
||
|
||
# and = λp. λq. p q p
|
||
and_op = Abs('p', Abs('q', App(App(Var('p'), Var('q')), Var('p'))))
|
||
|
||
# or = λp. λq. p p q
|
||
or_op = Abs('p', Abs('q', App(App(Var('p'), Var('p')), Var('q'))))
|
||
|
||
# not = λp. λa. λb. p b a
|
||
not_op = Abs('p', Abs('a', Abs('b', App(App(Var('p'), Var('b')), Var('a')))))
|
||
|
||
# Example: not true →_β false
|
||
result = normalize(App(not_op, true))
|
||
print(f"not true →* {result}")</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('x', Var('x'))
|
||
|
||
# K = λx. λy. x (constant)
|
||
K = Abs('x', Abs('y', Var('x')))
|
||
|
||
# S = λx. λy. λz. x z (y z)
|
||
S = Abs('x', Abs('y', Abs('z',
|
||
App(App(Var('x'), Var('z')), App(Var('y'), Var('z')))
|
||
)))
|
||
|
||
# Theorem: SKK = I
|
||
SKK = App(App(S, K), K)
|
||
result = normalize(SKK)
|
||
print(f"S K K →* {result}") # Should reduce to identity
|
||
|
||
# Y combinator (fixed-point): Y = λf. (λx. f (x x)) (λx. f (x x))
|
||
Y = Abs('f',
|
||
App(
|
||
Abs('x', App(Var('f'), App(Var('x'), Var('x')))),
|
||
Abs('x', App(Var('f'), App(Var('x'), Var('x'))))
|
||
)
|
||
)
|
||
|
||
# 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:
|
||
"""Type variable"""
|
||
name: str
|
||
|
||
def __repr__(self):
|
||
return self.name
|
||
|
||
@dataclass
|
||
class TArrow:
|
||
"""Function type: τ₁ → τ₂"""
|
||
input: 'Type'
|
||
output: 'Type'
|
||
|
||
def __repr__(self):
|
||
return f"({self.input} → {self.output})"
|
||
|
||
Type = TUnion[TVar, TArrow]
|
||
|
||
# Typing context: Γ = {x₁: τ₁, ..., xₙ: τₙ}
|
||
Context = dict[str, Type]
|
||
|
||
def type_check(term: Term, context: Context) -> Type:
|
||
"""
|
||
Type checking for simply typed λ-calculus
|
||
Γ ⊢ M : τ
|
||
"""
|
||
match term:
|
||
case Var(name):
|
||
if name not in context:
|
||
raise TypeError(f"Unbound variable: {name}")
|
||
return context[name]
|
||
|
||
case Abs(param, body):
|
||
# Need type annotation in practice
|
||
# For now, assume param has type α
|
||
param_type = TVar('α')
|
||
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"Type mismatch: expected {input_type}, got {arg_type}")
|
||
return output_type
|
||
case _:
|
||
raise TypeError(f"Expected function type, got {func_type}")
|
||
|
||
# Example: type check identity function
|
||
try:
|
||
id_type = type_check(identity, {})
|
||
print(f"Type of λx. x: {id_type}") # α → α
|
||
except TypeError as e:
|
||
print(f"Type error: {e}")</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():
|
||
"""
|
||
Factorial: F = λf. λn. if (n = 0) 1 (n · f (pred n))
|
||
fact = Y F
|
||
"""
|
||
# Simplified representation
|
||
return "Y (λf. λn. if (isZero n) 1 (mul n (f (pred n))))"</code></pre>
|
||
<h3>Pattern 2: Encoding Data Structures</h3>
|
||
<pre><code class="lang-python"># Pairs: pair = λx. λy. λf. f x y
|
||
pair = Abs('x', Abs('y', Abs('f', App(App(Var('f'), Var('x')), Var('y')))))
|
||
|
||
# fst = λp. p (λx. λy. x)
|
||
fst = Abs('p', App(Var('p'), K))
|
||
|
||
# snd = λp. p (λx. λy. y)
|
||
snd = Abs('p', App(Var('p'), Abs('x', Abs('y', Var('y')))))
|
||
|
||
# Lists (Church encoding):
|
||
# nil = λc. λn. n
|
||
# cons = λh. λt. λc. λn. c h (t c n)
|
||
nil = Abs('c', Abs('n', Var('n')))
|
||
cons = Abs('h', Abs('t', Abs('c', Abs('n',
|
||
App(App(Var('c'), Var('h')), App(App(Var('t'), Var('c')), Var('n')))
|
||
))))</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> |