mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
Every page now loads /webmcp.js, scripts/webmcp.ts with its types stripped (npm run webmcp). Where the browser has document.modelContext it registers two read-only tools: search_skills over the published skills index, and get_skill, which returns a skill's markdown checked against the index digest. The markdown alternate link moves from build.py to site.py, so CI holds every page to it. The API catalog gains the site itself (llms.txt and the skills index) and hanzo.ai/agents; the live discovery check now fetches every catalog link. tests/site.mjs drives the tools through a recording modelContext, and checks a browser without one loads clean.
594 lines
27 KiB
HTML
594 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>operational-semantics</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="icon" href="/favicon.svg">
|
|
<link rel="canonical" href="https://hanzoskills.com/operational-semantics">
|
|
<link rel="alternate" type="text/markdown" href="/operational-semantics.md">
|
|
<script type="module" src="/webmcp.js"></script>
|
|
</head>
|
|
<!-- Reading this with a machine? Every page here is also plain markdown.
|
|
This one: https://hanzoskills.com/operational-semantics.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>operational-semantics</h1><p class="lede">Operational semantics including small-step, big-step, evaluation strategies, and reduction systems</p><h1>Operational Semantics</h1>
|
|
<p><strong>Scope</strong>: Small-step semantics, big-step semantics, evaluation strategies, reduction systems, contextual semantics <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>Defining formal semantics for programming languages</li><li>Proving properties of evaluation (determinism, confluence)</li><li>Understanding call-by-value vs call-by-name evaluation</li><li>Implementing interpreters with formal foundations</li><li>Reasoning about program equivalence</li><li>Designing abstract machines</li></ul>
|
|
<h2>Core Concepts</h2>
|
|
<h3>Small-Step Semantics</h3>
|
|
<p><strong>Transition relation</strong>: e → e' (expression e steps to e')</p>
|
|
<pre><code class="lang-python">from dataclasses import dataclass
|
|
from typing import Union, Optional
|
|
|
|
# Language syntax
|
|
@dataclass
|
|
class IntLit:
|
|
value: int
|
|
|
|
@dataclass
|
|
class BoolLit:
|
|
value: bool
|
|
|
|
@dataclass
|
|
class Var:
|
|
name: str
|
|
|
|
@dataclass
|
|
class Add:
|
|
left: 'Expr'
|
|
right: 'Expr'
|
|
|
|
@dataclass
|
|
class If:
|
|
cond: 'Expr'
|
|
then_branch: 'Expr'
|
|
else_branch: 'Expr'
|
|
|
|
@dataclass
|
|
class Abs:
|
|
"""λx. e"""
|
|
param: str
|
|
body: 'Expr'
|
|
|
|
@dataclass
|
|
class App:
|
|
func: 'Expr'
|
|
arg: 'Expr'
|
|
|
|
Expr = Union[IntLit, BoolLit, Var, Add, If, Abs, App]
|
|
|
|
def is_value(expr: Expr) -> bool:
|
|
"""Check if expression is a value (cannot step further)"""
|
|
return isinstance(expr, (IntLit, BoolLit, Abs))
|
|
|
|
def substitute(expr: Expr, var: str, replacement: Expr) -> Expr:
|
|
"""Capture-avoiding substitution: expr[var := replacement]"""
|
|
match expr:
|
|
case Var(name):
|
|
return replacement if name == var else expr
|
|
case Add(l, r):
|
|
return Add(substitute(l, var, replacement), substitute(r, var, replacement))
|
|
case If(c, t, e):
|
|
return If(substitute(c, var, replacement),
|
|
substitute(t, var, replacement),
|
|
substitute(e, var, replacement))
|
|
case Abs(param, body):
|
|
if param == var:
|
|
return expr # Variable shadowed
|
|
return Abs(param, substitute(body, var, replacement))
|
|
case App(f, a):
|
|
return App(substitute(f, var, replacement), substitute(a, var, replacement))
|
|
case _:
|
|
return expr
|
|
|
|
def small_step(expr: Expr) -> Optional[Expr]:
|
|
"""
|
|
Small-step reduction: e → e'
|
|
Returns None if no step possible (stuck or value)
|
|
"""
|
|
match expr:
|
|
# Values don't step
|
|
case _ if is_value(expr):
|
|
return None
|
|
|
|
# Arithmetic
|
|
case Add(IntLit(m), IntLit(n)):
|
|
return IntLit(m + n)
|
|
case Add(e1, e2) if not is_value(e1):
|
|
e1_stepped = small_step(e1)
|
|
return Add(e1_stepped, e2) if e1_stepped else None
|
|
case Add(e1, e2) if is_value(e1) and not is_value(e2):
|
|
e2_stepped = small_step(e2)
|
|
return Add(e1, e2_stepped) if e2_stepped else None
|
|
|
|
# Conditionals
|
|
case If(BoolLit(True), then_branch, _):
|
|
return then_branch
|
|
case If(BoolLit(False), _, else_branch):
|
|
return else_branch
|
|
case If(cond, t, e) if not is_value(cond):
|
|
cond_stepped = small_step(cond)
|
|
return If(cond_stepped, t, e) if cond_stepped else None
|
|
|
|
# Application (call-by-value)
|
|
case App(Abs(param, body), arg) if is_value(arg):
|
|
# β-reduction
|
|
return substitute(body, param, arg)
|
|
case App(func, arg) if not is_value(func):
|
|
# Evaluate function first
|
|
func_stepped = small_step(func)
|
|
return App(func_stepped, arg) if func_stepped else None
|
|
case App(func, arg) if is_value(func) and not is_value(arg):
|
|
# Then evaluate argument
|
|
arg_stepped = small_step(arg)
|
|
return App(func, arg_stepped) if arg_stepped else None
|
|
|
|
case _:
|
|
return None # Stuck
|
|
|
|
def evaluate(expr: Expr, max_steps: int = 1000) -> Expr:
|
|
"""
|
|
Multi-step evaluation: e →* v
|
|
Reduce to normal form
|
|
"""
|
|
for _ in range(max_steps):
|
|
stepped = small_step(expr)
|
|
if stepped is None:
|
|
break
|
|
expr = stepped
|
|
return expr
|
|
|
|
# Example: (λx. x + 1) 5 →* 6
|
|
term = App(Abs('x', Add(Var('x'), IntLit(1))), IntLit(5))
|
|
print(f"Initial: {term}")
|
|
|
|
step1 = small_step(term)
|
|
print(f"Step 1: {step1}") # x + 1 [x := 5] = 5 + 1
|
|
|
|
step2 = small_step(step1) if step1 else None
|
|
print(f"Step 2: {step2}") # 6
|
|
|
|
result = evaluate(term)
|
|
print(f"Result: {result}") # IntLit(6)</code></pre>
|
|
<h3>Big-Step Semantics</h3>
|
|
<p><strong>Evaluation relation</strong>: e ⇓ v (expression e evaluates to value v)</p>
|
|
<pre><code class="lang-python">def big_step(expr: Expr, env: dict = None) -> Expr:
|
|
"""
|
|
Big-step evaluation: e ⇓ v
|
|
Directly evaluate to value (no intermediate steps)
|
|
"""
|
|
env = env or {}
|
|
|
|
match expr:
|
|
# Values evaluate to themselves
|
|
case _ if is_value(expr):
|
|
return expr
|
|
|
|
# Variables
|
|
case Var(name):
|
|
if name not in env:
|
|
raise NameError(f"Unbound variable: {name}")
|
|
return env[name]
|
|
|
|
# Arithmetic
|
|
case Add(e1, e2):
|
|
v1 = big_step(e1, env)
|
|
v2 = big_step(e2, env)
|
|
if isinstance(v1, IntLit) and isinstance(v2, IntLit):
|
|
return IntLit(v1.value + v2.value)
|
|
raise TypeError("Addition requires integers")
|
|
|
|
# Conditionals
|
|
case If(cond, then_branch, else_branch):
|
|
cond_val = big_step(cond, env)
|
|
if isinstance(cond_val, BoolLit):
|
|
if cond_val.value:
|
|
return big_step(then_branch, env)
|
|
else:
|
|
return big_step(else_branch, env)
|
|
raise TypeError("Condition must be boolean")
|
|
|
|
# Application
|
|
case App(func, arg):
|
|
func_val = big_step(func, env)
|
|
if isinstance(func_val, Abs):
|
|
arg_val = big_step(arg, env)
|
|
# Evaluate body with extended environment
|
|
new_env = env | {func_val.param: arg_val}
|
|
return big_step(func_val.body, new_env)
|
|
raise TypeError("Application requires function")
|
|
|
|
case _:
|
|
raise ValueError(f"Cannot evaluate: {expr}")
|
|
|
|
# Example: if true then 1 + 2 else 3 + 4 ⇓ 3
|
|
term = If(BoolLit(True), Add(IntLit(1), IntLit(2)), Add(IntLit(3), IntLit(4)))
|
|
result = big_step(term)
|
|
print(f"{term} ⇓ {result}") # IntLit(3)</code></pre>
|
|
<h3>Evaluation Strategies</h3>
|
|
<p><strong>Call-by-value (CBV)</strong>: Evaluate arguments before function application</p>
|
|
<pre><code class="lang-python">def cbv_step(expr: Expr) -> Optional[Expr]:
|
|
"""Call-by-value reduction"""
|
|
match expr:
|
|
case App(Abs(param, body), arg) if is_value(arg):
|
|
# Argument is value, reduce
|
|
return substitute(body, param, arg)
|
|
case App(func, arg) if not is_value(func):
|
|
# Reduce function first
|
|
func_stepped = cbv_step(func)
|
|
return App(func_stepped, arg) if func_stepped else None
|
|
case App(func, arg) if is_value(func):
|
|
# Function is value, reduce argument
|
|
arg_stepped = cbv_step(arg)
|
|
return App(func, arg_stepped) if arg_stepped else None
|
|
case _:
|
|
return None
|
|
|
|
# Example: (λx. λy. x) ((λz. z) 1) 2
|
|
# CBV: Reduce (λz. z) 1 first, then apply</code></pre>
|
|
<p><strong>Call-by-name (CBN)</strong>: Substitute arguments without evaluating</p>
|
|
<pre><code class="lang-python">def cbn_step(expr: Expr) -> Optional[Expr]:
|
|
"""Call-by-name reduction"""
|
|
match expr:
|
|
case App(Abs(param, body), arg):
|
|
# Substitute immediately, don't evaluate arg
|
|
return substitute(body, param, arg)
|
|
case App(func, arg):
|
|
# Reduce function only
|
|
func_stepped = cbn_step(func)
|
|
return App(func_stepped, arg) if func_stepped else None
|
|
case _:
|
|
return None
|
|
|
|
# Example: (λx. 1) ((λy. y y) (λy. y y))
|
|
# CBN: Return 1 without evaluating Ω = (λy. y y) (λy. y y)
|
|
# CBV: Loop forever evaluating Ω</code></pre>
|
|
<p><strong>Call-by-need (lazy evaluation)</strong>: CBN with memoization</p>
|
|
<pre><code class="lang-python">class Thunk:
|
|
"""Delayed computation with memoization"""
|
|
def __init__(self, expr: Expr, env: dict):
|
|
self.expr = expr
|
|
self.env = env
|
|
self.value = None
|
|
|
|
def force(self):
|
|
"""Evaluate thunk (memoized)"""
|
|
if self.value is None:
|
|
self.value = lazy_eval(self.expr, self.env)
|
|
return self.value
|
|
|
|
def lazy_eval(expr: Expr, env: dict = None) -> Expr:
|
|
"""Call-by-need evaluation"""
|
|
env = env or {}
|
|
|
|
match expr:
|
|
case Var(name):
|
|
if name not in env:
|
|
raise NameError(f"Unbound variable: {name}")
|
|
# Force thunk if necessary
|
|
val = env[name]
|
|
return val.force() if isinstance(val, Thunk) else val
|
|
|
|
case App(func, arg):
|
|
func_val = lazy_eval(func, env)
|
|
if isinstance(func_val, Abs):
|
|
# Create thunk for argument
|
|
thunk = Thunk(arg, env)
|
|
new_env = env | {func_val.param: thunk}
|
|
return lazy_eval(func_val.body, new_env)
|
|
|
|
case _ if is_value(expr):
|
|
return expr
|
|
|
|
case _:
|
|
raise ValueError(f"Cannot evaluate: {expr}")
|
|
|
|
# Lazy evaluation allows working with infinite data structures</code></pre>
|
|
<h3>Contextual Semantics</h3>
|
|
<p><strong>Evaluation contexts</strong>: E ::= [] | E e | v E | ...</p>
|
|
<pre><code class="lang-python">@dataclass
|
|
class Hole:
|
|
"""Evaluation context hole []"""
|
|
pass
|
|
|
|
@dataclass
|
|
class CtxApp1:
|
|
"""E e (context in function position)"""
|
|
context: 'Context'
|
|
arg: Expr
|
|
|
|
@dataclass
|
|
class CtxApp2:
|
|
"""v E (context in argument position, function is value)"""
|
|
func: Expr
|
|
context: 'Context'
|
|
|
|
Context = Union[Hole, CtxApp1, CtxApp2]
|
|
|
|
def plug(ctx: Context, expr: Expr) -> Expr:
|
|
"""Fill hole in context with expression: E[e]"""
|
|
match ctx:
|
|
case Hole():
|
|
return expr
|
|
case CtxApp1(inner_ctx, arg):
|
|
return App(plug(inner_ctx, expr), arg)
|
|
case CtxApp2(func, inner_ctx):
|
|
return App(func, plug(inner_ctx, expr))
|
|
|
|
def decompose(expr: Expr) -> Optional[tuple[Context, Expr]]:
|
|
"""
|
|
Decompose expression into context and redex: e = E[r]
|
|
Returns (E, r) where r is redex
|
|
"""
|
|
match expr:
|
|
case App(Abs(param, body), arg) if is_value(arg):
|
|
# Found redex
|
|
return (Hole(), expr)
|
|
case App(func, arg):
|
|
if not is_value(func):
|
|
# Decompose function
|
|
ctx, redex = decompose(func)
|
|
return (CtxApp1(ctx, arg), redex)
|
|
elif not is_value(arg):
|
|
# Decompose argument
|
|
ctx, redex = decompose(arg)
|
|
return (CtxApp2(func, ctx), redex)
|
|
case _:
|
|
return None
|
|
|
|
# Context-based stepping
|
|
def contextual_step(expr: Expr) -> Optional[Expr]:
|
|
"""e = E[r] → E[r'] where r → r'"""
|
|
decomp = decompose(expr)
|
|
if decomp is None:
|
|
return None
|
|
|
|
ctx, redex = decomp
|
|
redex_stepped = small_step(redex)
|
|
if redex_stepped is None:
|
|
return None
|
|
|
|
return plug(ctx, redex_stepped)</code></pre>
|
|
<hr>
|
|
<h2>Patterns</h2>
|
|
<h3>Pattern 1: Determinism</h3>
|
|
<pre><code class="lang-python">def is_deterministic(expr: Expr) -> bool:
|
|
"""
|
|
Check if semantics is deterministic:
|
|
If e → e₁ and e → e₂, then e₁ = e₂
|
|
"""
|
|
# For our CBV semantics, this always holds
|
|
# Prove by induction on step relation
|
|
return True</code></pre>
|
|
<h3>Pattern 2: Confluence</h3>
|
|
<pre><code class="lang-python">def is_confluent(expr: Expr) -> bool:
|
|
"""
|
|
Church-Rosser property:
|
|
If e →* e₁ and e →* e₂, then ∃e₃: e₁ →* e₃ and e₂ →* e₃
|
|
"""
|
|
# For pure λ-calculus, this holds
|
|
# For CBV, determinism implies confluence
|
|
return True</code></pre>
|
|
<hr>
|
|
<h2>Quick Reference</h2>
|
|
<h3>Small-Step vs Big-Step</h3>
|
|
<p>| Aspect | Small-Step | Big-Step | |--------|-----------|----------| | Notation | e → e' | e ⇓ v | | Granularity | One step at a time | Direct to value | | Non-termination | e → e' → ... (infinite) | No rule applies | | Intermediate steps | Explicit | Hidden |</p>
|
|
<h3>Evaluation Strategies</h3>
|
|
<p>| Strategy | Rule | Example | |----------|------|---------| | Call-by-value | (λx. e) v → e[x := v] | Strict languages (ML, Scheme) | | Call-by-name | (λx. e) e' → e[x := e'] | Algol, early languages | | Call-by-need | CBN + memoization | Haskell (lazy) |</p>
|
|
<hr>
|
|
<h2>Anti-Patterns</h2>
|
|
<p>❌ <strong>Confusing small-step and big-step</strong>: Different tools for different purposes ✅ Small-step for reasoning about steps, big-step for final results</p>
|
|
<p>❌ <strong>Assuming all languages are deterministic</strong>: Non-deterministic concurrency exists ✅ Explicitly model non-determinism when needed</p>
|
|
<p>❌ <strong>Ignoring evaluation order</strong>: CBV and CBN have different termination behavior ✅ Choose evaluation strategy based on language design goals</p>
|
|
<hr>
|
|
<h2>Related Skills</h2>
|
|
<ul><li><code>lambda-calculus.md</code> - β-reduction and normalization</li><li><code>type-systems.md</code> - Type soundness (progress + preservation)</li><li><code>curry-howard.md</code> - Proof normalization as program evaluation</li><li><code>program-verification.md</code> - Proving properties of evaluation</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="/operational-semantics.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
|
</footer>
|
|
</div></body></html> |