Files
skills/public/type-systems.html
zeekay 747dafba10 Register WebMCP tools on every page, and name each page's twin from site.py
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.
2026-10-26 20:57:05 -07:00

704 lines
30 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>type-systems</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/type-systems">
<link rel="alternate" type="text/markdown" href="/type-systems.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/type-systems.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>type-systems</h1><p class="lede">Type systems including type checking, inference, polymorphism, subtyping, and soundness</p><h1>Type Systems</h1>
<p><strong>Scope</strong>: Type checking, type inference, polymorphism, subtyping, soundness, gradual typing <strong>Lines</strong>: ~450 <strong>Last Updated</strong>: 2025-10-25</p>
<h2>When to Use This Skill</h2>
<p>Activate this skill when:</p>
<ul><li>Designing type systems for programming languages</li><li>Implementing type checkers and type inference algorithms</li><li>Understanding parametric polymorphism and generics</li><li>Working with subtyping and object-oriented type systems</li><li>Proving type soundness (progress + preservation)</li><li>Exploring gradual typing and type migration</li></ul>
<h2>Core Concepts</h2>
<h3>Type Judgments</h3>
<p><strong>Typing judgment</strong>: Γ ⊢ e : τ (in context Γ, expression e has type τ)</p>
<pre><code class="lang-python">from dataclasses import dataclass
from typing import Union, Optional
from enum import Enum
# Types
@dataclass
class TInt:
def __repr__(self):
return &quot;Int&quot;
@dataclass
class TBool:
def __repr__(self):
return &quot;Bool&quot;
@dataclass
class TFun:
&quot;&quot;&quot;Function type: τ₁ → τ₂&quot;&quot;&quot;
param: &#x27;Type&#x27;
result: &#x27;Type&#x27;
def __repr__(self):
return f&quot;({self.param} → {self.result})&quot;
@dataclass
class TVar:
&quot;&quot;&quot;Type variable for polymorphism&quot;&quot;&quot;
name: str
def __repr__(self):
return self.name
Type = Union[TInt, TBool, TFun, TVar]
# Terms
@dataclass
class IntLit:
value: int
@dataclass
class BoolLit:
value: bool
@dataclass
class Var:
name: str
@dataclass
class Abs:
&quot;&quot;&quot;λx:τ. e (annotated abstraction)&quot;&quot;&quot;
param: str
param_type: Type
body: &#x27;Expr&#x27;
@dataclass
class App:
func: &#x27;Expr&#x27;
arg: &#x27;Expr&#x27;
@dataclass
class If:
cond: &#x27;Expr&#x27;
then_branch: &#x27;Expr&#x27;
else_branch: &#x27;Expr&#x27;
Expr = Union[IntLit, BoolLit, Var, Abs, App, If]
# Type environment
Context = dict[str, Type]
def type_check(expr: Expr, ctx: Context) -&gt; Type:
&quot;&quot;&quot;
Type checking algorithm
Returns type if well-typed, raises TypeError otherwise
&quot;&quot;&quot;
match expr:
case IntLit(_):
return TInt()
case BoolLit(_):
return TBool()
case Var(name):
if name not in ctx:
raise TypeError(f&quot;Unbound variable: {name}&quot;)
return ctx[name]
case Abs(param, param_type, body):
# Γ, x:τ₁ ⊢ e:τ₂ ⟹ Γ ⊢ λx:τ₁. e : τ₁ → τ₂
new_ctx = ctx | {param: param_type}
body_type = type_check(body, new_ctx)
return TFun(param_type, body_type)
case App(func, arg):
# Γ ⊢ e₁ : τ₁ → τ₂ Γ ⊢ e₂ : τ₁ ⟹ Γ ⊢ e₁ e₂ : τ₂
func_type = type_check(func, ctx)
arg_type = type_check(arg, ctx)
match func_type:
case TFun(param_type, result_type):
if not types_equal(param_type, arg_type):
raise TypeError(f&quot;Type mismatch: expected {param_type}, got {arg_type}&quot;)
return result_type
case _:
raise TypeError(f&quot;Expected function type, got {func_type}&quot;)
case If(cond, then_branch, else_branch):
# Γ ⊢ e₁ : Bool Γ ⊢ e₂ : τ Γ ⊢ e₃ : τ ⟹ Γ ⊢ if e₁ then e₂ else e₃ : τ
cond_type = type_check(cond, ctx)
if not isinstance(cond_type, TBool):
raise TypeError(f&quot;Condition must be Bool, got {cond_type}&quot;)
then_type = type_check(then_branch, ctx)
else_type = type_check(else_branch, ctx)
if not types_equal(then_type, else_type):
raise TypeError(f&quot;Branches have different types: {then_type} vs {else_type}&quot;)
return then_type
def types_equal(t1: Type, t2: Type) -&gt; bool:
&quot;&quot;&quot;Check type equality&quot;&quot;&quot;
match (t1, t2):
case (TInt(), TInt()) | (TBool(), TBool()):
return True
case (TFun(p1, r1), TFun(p2, r2)):
return types_equal(p1, p2) and types_equal(r1, r2)
case (TVar(n1), TVar(n2)):
return n1 == n2
case _:
return False
# Example: type check λx:Int. x + 1
identity_int = Abs(&#x27;x&#x27;, TInt(), Var(&#x27;x&#x27;))
id_type = type_check(identity_int, {})
print(f&quot;Type of λx:Int. x: {id_type}&quot;) # Int → Int</code></pre>
<h3>Type Inference (Algorithm W)</h3>
<p><strong>Hindley-Milner type inference</strong>: Infer types without annotations</p>
<pre><code class="lang-python">from typing import Dict, Set
@dataclass
class TyVar:
&quot;&quot;&quot;Type variable for inference&quot;&quot;&quot;
id: int
def __repr__(self):
return f&quot;&#x27;t{self.id}&quot;
InferType = Union[TInt, TBool, TFun, TyVar]
class TypeInference:
def __init__(self):
self.next_tyvar = 0
self.substitution: Dict[int, InferType] = {}
def fresh_tyvar(self) -&gt; TyVar:
&quot;&quot;&quot;Generate fresh type variable&quot;&quot;&quot;
tv = TyVar(self.next_tyvar)
self.next_tyvar += 1
return tv
def apply_subst(self, ty: InferType) -&gt; InferType:
&quot;&quot;&quot;Apply substitution to type&quot;&quot;&quot;
match ty:
case TyVar(id) if id in self.substitution:
return self.apply_subst(self.substitution[id])
case TFun(param, result):
return TFun(self.apply_subst(param), self.apply_subst(result))
case _:
return ty
def unify(self, t1: InferType, t2: InferType):
&quot;&quot;&quot;
Unification: find substitution making t1 = t2
Robinson&#x27;s algorithm
&quot;&quot;&quot;
t1 = self.apply_subst(t1)
t2 = self.apply_subst(t2)
match (t1, t2):
case (TInt(), TInt()) | (TBool(), TBool()):
return
case (TFun(p1, r1), TFun(p2, r2)):
self.unify(p1, p2)
self.unify(r1, r2)
case (TyVar(id1), TyVar(id2)) if id1 == id2:
return
case (TyVar(id), _):
if self.occurs_check(id, t2):
raise TypeError(f&quot;Infinite type: &#x27;t{id} = {t2}&quot;)
self.substitution[id] = t2
case (_, TyVar(id)):
if self.occurs_check(id, t1):
raise TypeError(f&quot;Infinite type: &#x27;t{id} = {t1}&quot;)
self.substitution[id] = t1
case _:
raise TypeError(f&quot;Cannot unify {t1} and {t2}&quot;)
def occurs_check(self, id: int, ty: InferType) -&gt; bool:
&quot;&quot;&quot;Check if type variable occurs in type&quot;&quot;&quot;
ty = self.apply_subst(ty)
match ty:
case TyVar(id2):
return id == id2
case TFun(param, result):
return self.occurs_check(id, param) or self.occurs_check(id, result)
case _:
return False
def infer(self, expr: Expr, ctx: Dict[str, InferType]) -&gt; InferType:
&quot;&quot;&quot;
Type inference (Algorithm W)
Returns inferred type
&quot;&quot;&quot;
match expr:
case IntLit(_):
return TInt()
case BoolLit(_):
return TBool()
case Var(name):
if name not in ctx:
raise TypeError(f&quot;Unbound variable: {name}&quot;)
return ctx[name]
case Abs(param, None, body): # Unannotated abstraction
param_ty = self.fresh_tyvar()
new_ctx = ctx | {param: param_ty}
body_ty = self.infer(body, new_ctx)
return TFun(param_ty, body_ty)
case App(func, arg):
func_ty = self.infer(func, ctx)
arg_ty = self.infer(arg, ctx)
result_ty = self.fresh_tyvar()
self.unify(func_ty, TFun(arg_ty, result_ty))
return self.apply_subst(result_ty)
case If(cond, then_branch, else_branch):
cond_ty = self.infer(cond, ctx)
self.unify(cond_ty, TBool())
then_ty = self.infer(then_branch, ctx)
else_ty = self.infer(else_branch, ctx)
self.unify(then_ty, else_ty)
return self.apply_subst(then_ty)
# Example: infer type of λx. x
@dataclass
class UntypedAbs:
param: str
body: Expr
unannotated_id = UntypedAbs(&#x27;x&#x27;, Var(&#x27;x&#x27;))
inferencer = TypeInference()
inferred_type = inferencer.infer(unannotated_id, {})
inferred_type = inferencer.apply_subst(inferred_type)
print(f&quot;Inferred type of λx. x: {inferred_type}&quot;) # &#x27;t0 → &#x27;t0 (polymorphic!)</code></pre>
<h3>Parametric Polymorphism</h3>
<p><strong>System F (polymorphic λ-calculus)</strong>:</p>
<ul><li>Type abstraction: Λα. e</li><li>Type application: e [τ]</li></ul>
<pre><code class="lang-python">@dataclass
class ForAll:
&quot;&quot;&quot;Polymorphic type: ∀α. τ&quot;&quot;&quot;
tyvar: str
body: Type
def __repr__(self):
return f&quot;∀{self.tyvar}. {self.body}&quot;
@dataclass
class TyAbs:
&quot;&quot;&quot;Type abstraction: Λα. e&quot;&quot;&quot;
tyvar: str
body: Expr
@dataclass
class TyApp:
&quot;&quot;&quot;Type application: e [τ]&quot;&quot;&quot;
expr: Expr
tyarg: Type
# Polymorphic identity: Λα. λx:α. x
poly_id = TyAbs(&#x27;α&#x27;, Abs(&#x27;x&#x27;, TVar(&#x27;α&#x27;), Var(&#x27;x&#x27;)))
# Type: ∀α. α → α
# Instantiation: (Λα. λx:α. x) [Int]
# Result type: Int → Int</code></pre>
<h3>Subtyping</h3>
<p><strong>Subtype relation</strong>: τ₁ &lt;: τ₂ (τ₁ is a subtype of τ₂)</p>
<p><strong>Rules</strong>:</p>
<ul><li>Reflexivity: τ &lt;: τ</li><li>Transitivity: τ₁ &lt;: τ₂, τ₂ &lt;: τ₃ ⟹ τ₁ &lt;: τ₃</li><li>Functions (contravariant in argument): τ₁&#x27; &lt;: τ₁, τ₂ &lt;: τ₂&#x27; ⟹ (τ₁ → τ₂) &lt;: (τ₁&#x27; → τ₂&#x27;)</li></ul>
<pre><code class="lang-python">def is_subtype(t1: Type, t2: Type) -&gt; bool:
&quot;&quot;&quot;Check if t1 &lt;: t2&quot;&quot;&quot;
# Reflexivity
if types_equal(t1, t2):
return True
match (t1, t2):
# Function subtyping (contravariant in argument, covariant in result)
case (TFun(p1, r1), TFun(p2, r2)):
return is_subtype(p2, p1) and is_subtype(r1, r2) # Note: p2 &lt;: p1!
# Additional rules for records, objects, etc.
case _:
return False
# Example: (Int → Bool) &lt;: (Int → Bool)? Yes (reflexive)
# (Int → Int) &lt;: (Int → Bool)? No
# (Bool → Int) &lt;: (Int → Int)? No (Int ⊀: Bool)</code></pre>
<h3>Type Soundness</h3>
<p><strong>Progress</strong>: Well-typed terms are not stuck <strong>Preservation</strong>: If Γ ⊢ e : τ and e →* e&#x27;, then Γ ⊢ e&#x27; : τ</p>
<pre><code class="lang-python">def progress(expr: Expr, ty: Type) -&gt; bool:
&quot;&quot;&quot;
Progress theorem: well-typed closed term is either value or can step
Proof sketch:
- Base cases (literals): values, done
- Abs: value, done
- App: by IH, func is value or steps
- If value, must be Abs, so can β-reduce
- If steps, can step App
- If: cond is value or steps, etc.
&quot;&quot;&quot;
# Values: literals and abstractions
if isinstance(expr, (IntLit, BoolLit, Abs)):
return True # Is value
# Otherwise can step (simplified check)
return can_step(expr)
def can_step(expr: Expr) -&gt; bool:
&quot;&quot;&quot;Check if expression can take a step&quot;&quot;&quot;
match expr:
case App(Abs(_, _, _), _):
return True # β-reduction
case App(func, arg):
return can_step(func) or can_step(arg)
case If(BoolLit(_), _, _):
return True # Can select branch
case If(cond, _, _):
return can_step(cond)
case _:
return False
def preservation(expr: Expr, ty: Type, ctx: Context) -&gt; bool:
&quot;&quot;&quot;
Preservation theorem: if Γ ⊢ e : τ and e → e&#x27;, then Γ ⊢ e&#x27; : τ
Proof by induction on typing derivation
&quot;&quot;&quot;
# Verify type is preserved after stepping
if can_step(expr):
expr_stepped = step(expr) # Would need evaluation function
try:
ty_stepped = type_check(expr_stepped, ctx)
return types_equal(ty, ty_stepped)
except TypeError:
return False
return True
def step(expr: Expr) -&gt; Expr:
&quot;&quot;&quot;Single evaluation step (simplified)&quot;&quot;&quot;
match expr:
case App(Abs(param, _, body), arg):
# β-reduction (substitute arg for param in body)
return substitute(body, param, arg)
case _:
return expr
def substitute(expr: Expr, var: str, replacement: Expr) -&gt; Expr:
&quot;&quot;&quot;Substitute variable in expression&quot;&quot;&quot;
match expr:
case Var(name):
return replacement if name == var else expr
case Abs(param, ty, body):
if param == var:
return expr # Shadowed
return Abs(param, ty, substitute(body, var, replacement))
case App(func, arg):
return App(substitute(func, var, replacement), substitute(arg, var, replacement))
case _:
return expr</code></pre>
<hr>
<h2>Patterns</h2>
<h3>Pattern 1: Generics in Languages</h3>
<p><strong>ML-style polymorphism</strong>:</p>
<pre><code class="lang-ocaml">(* OCaml *)
let id x = x;; (* &#x27;a -&gt; &#x27;a *)
let const x y = x;; (* &#x27;a -&gt; &#x27;b -&gt; &#x27;a *)</code></pre>
<p><strong>Java generics</strong>:</p>
<pre><code class="lang-java">&lt;T&gt; T identity(T x) { return x; }
&lt;T extends Comparable&lt;T&gt;&gt; T max(T a, T b) { ... }</code></pre>
<h3>Pattern 2: Algebraic Data Types</h3>
<pre><code class="lang-python"># Representing sum types
@dataclass
class Option:
&quot;&quot;&quot;Option&lt;T&gt; = None | Some(T)&quot;&quot;&quot;
pass
@dataclass
class None_(Option):
pass
@dataclass
class Some(Option):
value: Type
# Type checking pattern matching
def match_option(opt: Option, none_case: Expr, some_case: Expr) -&gt; Type:
&quot;&quot;&quot;Type check: match opt { None =&gt; ..., Some(x) =&gt; ... }&quot;&quot;&quot;
pass</code></pre>
<h3>Pattern 3: Gradual Typing</h3>
<p><strong>Dynamic type</strong>: ⋆ (unknown type)</p>
<pre><code class="lang-python">@dataclass
class TDynamic:
&quot;&quot;&quot;Dynamic type ⋆&quot;&quot;&quot;
def __repr__(self):
return &quot;⋆&quot;
def consistent(t1: Type, t2: Type) -&gt; bool:
&quot;&quot;&quot;
Consistency relation: t1 ~ t2
More permissive than equality, allows ⋆
&quot;&quot;&quot;
match (t1, t2):
case (TDynamic(), _) | (_, TDynamic()):
return True # ⋆ consistent with everything
case (TFun(p1, r1), TFun(p2, r2)):
return consistent(p1, p2) and consistent(r1, r2)
case _:
return types_equal(t1, t2)</code></pre>
<hr>
<h2>Quick Reference</h2>
<h3>Typing Rules (Simply Typed λ-Calculus)</h3>
<pre><code>Γ(x) = τ
────────── (Var)
Γ ⊢ x : τ
Γ, x:τ₁ ⊢ e:τ₂
────────────────────── (Abs)
Γ ⊢ λx:τ₁. e : τ₁ → τ₂
Γ ⊢ e₁ : τ₁ → τ₂ Γ ⊢ e₂ : τ₁
─────────────────────────────── (App)
Γ ⊢ e₁ e₂ : τ₂</code></pre>
<h3>Type Inference (Hindley-Milner)</h3>
<pre><code>Algorithm W (unification-based):
1. Generate fresh type variables
2. Collect constraints
3. Unify constraints
4. Apply substitution</code></pre>
<h3>Subtyping Rules</h3>
<pre><code>τ &lt;: τ (Refl)
τ₁ &lt;: τ₂ τ₂ &lt;: τ₃
─────────────────── (Trans)
τ₁ &lt;: τ₃
τ₁&#x27; &lt;: τ₁ τ₂ &lt;: τ₂&#x27;
──────────────────────────── (Arrow)
τ₁ → τ₂ &lt;: τ₁&#x27; → τ₂&#x27;</code></pre>
<hr>
<h2>Anti-Patterns</h2>
<p>❌ <strong>Confusing type checking and type inference</strong>: Checking needs annotations, inference doesn&#x27;t ✅ Bidirectional typing combines both</p>
<p>❌ <strong>Ignoring variance</strong>: List&lt;Dog&gt; is not subtype of List&lt;Animal&gt; (invariant) ✅ Array types are invariant, function arguments contravariant</p>
<p>❌ <strong>Assuming soundness</strong>: Unsafe features (casts, null) break type soundness ✅ Gradual typing makes unsoundness explicit with ⋆ type</p>
<p>❌ <strong>Over-constraining inference</strong>: Requiring full annotations defeats purpose ✅ Use bidirectional typing: infer when possible, check when needed</p>
<hr>
<h2>Related Skills</h2>
<ul><li><code>lambda-calculus.md</code> - Foundation for typed λ-calculi</li><li><code>dependent-types.md</code> - Types depending on values</li><li><code>curry-howard.md</code> - Proofs as programs, types as propositions</li><li><code>operational-semantics.md</code> - Evaluation and reduction</li><li><code>program-verification.md</code> - Proving program properties via types</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="/type-systems.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>