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]>
704 lines
30 KiB
HTML
704 lines
30 KiB
HTML
<!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="alternate" type="text/markdown" href="/type-systems.md">
|
||
|
||
<link rel="icon" href="/favicon.svg">
|
||
<link rel="canonical" href="https://hanzoskills.com/type-systems">
|
||
</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 "Int"
|
||
|
||
@dataclass
|
||
class TBool:
|
||
def __repr__(self):
|
||
return "Bool"
|
||
|
||
@dataclass
|
||
class TFun:
|
||
"""Function type: τ₁ → τ₂"""
|
||
param: 'Type'
|
||
result: 'Type'
|
||
|
||
def __repr__(self):
|
||
return f"({self.param} → {self.result})"
|
||
|
||
@dataclass
|
||
class TVar:
|
||
"""Type variable for polymorphism"""
|
||
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:
|
||
"""λx:τ. e (annotated abstraction)"""
|
||
param: str
|
||
param_type: Type
|
||
body: 'Expr'
|
||
|
||
@dataclass
|
||
class App:
|
||
func: 'Expr'
|
||
arg: 'Expr'
|
||
|
||
@dataclass
|
||
class If:
|
||
cond: 'Expr'
|
||
then_branch: 'Expr'
|
||
else_branch: 'Expr'
|
||
|
||
Expr = Union[IntLit, BoolLit, Var, Abs, App, If]
|
||
|
||
# Type environment
|
||
Context = dict[str, Type]
|
||
|
||
def type_check(expr: Expr, ctx: Context) -> Type:
|
||
"""
|
||
Type checking algorithm
|
||
Returns type if well-typed, raises TypeError otherwise
|
||
"""
|
||
match expr:
|
||
case IntLit(_):
|
||
return TInt()
|
||
|
||
case BoolLit(_):
|
||
return TBool()
|
||
|
||
case Var(name):
|
||
if name not in ctx:
|
||
raise TypeError(f"Unbound variable: {name}")
|
||
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"Type mismatch: expected {param_type}, got {arg_type}")
|
||
return result_type
|
||
case _:
|
||
raise TypeError(f"Expected function type, got {func_type}")
|
||
|
||
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"Condition must be Bool, got {cond_type}")
|
||
|
||
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"Branches have different types: {then_type} vs {else_type}")
|
||
|
||
return then_type
|
||
|
||
def types_equal(t1: Type, t2: Type) -> bool:
|
||
"""Check type equality"""
|
||
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('x', TInt(), Var('x'))
|
||
id_type = type_check(identity_int, {})
|
||
print(f"Type of λx:Int. x: {id_type}") # 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:
|
||
"""Type variable for inference"""
|
||
id: int
|
||
|
||
def __repr__(self):
|
||
return f"'t{self.id}"
|
||
|
||
InferType = Union[TInt, TBool, TFun, TyVar]
|
||
|
||
class TypeInference:
|
||
def __init__(self):
|
||
self.next_tyvar = 0
|
||
self.substitution: Dict[int, InferType] = {}
|
||
|
||
def fresh_tyvar(self) -> TyVar:
|
||
"""Generate fresh type variable"""
|
||
tv = TyVar(self.next_tyvar)
|
||
self.next_tyvar += 1
|
||
return tv
|
||
|
||
def apply_subst(self, ty: InferType) -> InferType:
|
||
"""Apply substitution to type"""
|
||
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):
|
||
"""
|
||
Unification: find substitution making t1 = t2
|
||
Robinson's algorithm
|
||
"""
|
||
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"Infinite type: 't{id} = {t2}")
|
||
self.substitution[id] = t2
|
||
|
||
case (_, TyVar(id)):
|
||
if self.occurs_check(id, t1):
|
||
raise TypeError(f"Infinite type: 't{id} = {t1}")
|
||
self.substitution[id] = t1
|
||
|
||
case _:
|
||
raise TypeError(f"Cannot unify {t1} and {t2}")
|
||
|
||
def occurs_check(self, id: int, ty: InferType) -> bool:
|
||
"""Check if type variable occurs in type"""
|
||
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]) -> InferType:
|
||
"""
|
||
Type inference (Algorithm W)
|
||
Returns inferred type
|
||
"""
|
||
match expr:
|
||
case IntLit(_):
|
||
return TInt()
|
||
|
||
case BoolLit(_):
|
||
return TBool()
|
||
|
||
case Var(name):
|
||
if name not in ctx:
|
||
raise TypeError(f"Unbound variable: {name}")
|
||
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('x', Var('x'))
|
||
inferencer = TypeInference()
|
||
inferred_type = inferencer.infer(unannotated_id, {})
|
||
inferred_type = inferencer.apply_subst(inferred_type)
|
||
print(f"Inferred type of λx. x: {inferred_type}") # 't0 → '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:
|
||
"""Polymorphic type: ∀α. τ"""
|
||
tyvar: str
|
||
body: Type
|
||
|
||
def __repr__(self):
|
||
return f"∀{self.tyvar}. {self.body}"
|
||
|
||
@dataclass
|
||
class TyAbs:
|
||
"""Type abstraction: Λα. e"""
|
||
tyvar: str
|
||
body: Expr
|
||
|
||
@dataclass
|
||
class TyApp:
|
||
"""Type application: e [τ]"""
|
||
expr: Expr
|
||
tyarg: Type
|
||
|
||
# Polymorphic identity: Λα. λx:α. x
|
||
poly_id = TyAbs('α', Abs('x', TVar('α'), Var('x')))
|
||
# Type: ∀α. α → α
|
||
|
||
# Instantiation: (Λα. λx:α. x) [Int]
|
||
# Result type: Int → Int</code></pre>
|
||
<h3>Subtyping</h3>
|
||
<p><strong>Subtype relation</strong>: τ₁ <: τ₂ (τ₁ is a subtype of τ₂)</p>
|
||
<p><strong>Rules</strong>:</p>
|
||
<ul><li>Reflexivity: τ <: τ</li><li>Transitivity: τ₁ <: τ₂, τ₂ <: τ₃ ⟹ τ₁ <: τ₃</li><li>Functions (contravariant in argument): τ₁' <: τ₁, τ₂ <: τ₂' ⟹ (τ₁ → τ₂) <: (τ₁' → τ₂')</li></ul>
|
||
<pre><code class="lang-python">def is_subtype(t1: Type, t2: Type) -> bool:
|
||
"""Check if t1 <: t2"""
|
||
# 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 <: p1!
|
||
|
||
# Additional rules for records, objects, etc.
|
||
case _:
|
||
return False
|
||
|
||
# Example: (Int → Bool) <: (Int → Bool)? Yes (reflexive)
|
||
# (Int → Int) <: (Int → Bool)? No
|
||
# (Bool → Int) <: (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', then Γ ⊢ e' : τ</p>
|
||
<pre><code class="lang-python">def progress(expr: Expr, ty: Type) -> bool:
|
||
"""
|
||
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.
|
||
"""
|
||
# 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) -> bool:
|
||
"""Check if expression can take a step"""
|
||
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) -> bool:
|
||
"""
|
||
Preservation theorem: if Γ ⊢ e : τ and e → e', then Γ ⊢ e' : τ
|
||
|
||
Proof by induction on typing derivation
|
||
"""
|
||
# 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) -> Expr:
|
||
"""Single evaluation step (simplified)"""
|
||
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) -> Expr:
|
||
"""Substitute variable in expression"""
|
||
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;; (* 'a -> 'a *)
|
||
let const x y = x;; (* 'a -> 'b -> 'a *)</code></pre>
|
||
<p><strong>Java generics</strong>:</p>
|
||
<pre><code class="lang-java"><T> T identity(T x) { return x; }
|
||
<T extends Comparable<T>> 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:
|
||
"""Option<T> = None | Some(T)"""
|
||
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) -> Type:
|
||
"""Type check: match opt { None => ..., Some(x) => ... }"""
|
||
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:
|
||
"""Dynamic type ⋆"""
|
||
def __repr__(self):
|
||
return "⋆"
|
||
|
||
def consistent(t1: Type, t2: Type) -> bool:
|
||
"""
|
||
Consistency relation: t1 ~ t2
|
||
More permissive than equality, allows ⋆
|
||
"""
|
||
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>τ <: τ (Refl)
|
||
|
||
τ₁ <: τ₂ τ₂ <: τ₃
|
||
─────────────────── (Trans)
|
||
τ₁ <: τ₃
|
||
|
||
τ₁' <: τ₁ τ₂ <: τ₂'
|
||
──────────────────────────── (Arrow)
|
||
τ₁ → τ₂ <: τ₁' → τ₂'</code></pre>
|
||
<hr>
|
||
<h2>Anti-Patterns</h2>
|
||
<p>❌ <strong>Confusing type checking and type inference</strong>: Checking needs annotations, inference doesn't ✅ Bidirectional typing combines both</p>
|
||
<p>❌ <strong>Ignoring variance</strong>: List<Dog> is not subtype of List<Animal> (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> |