良类型解释器是一种编程语言解释器,它使用索引族排除运行时类型错误。
在被解释语言中编写的函数可以解释为 Lean 函数,同时也可以检查其底层源代码。
良类型解释器的第一步,是选出可以使用的 Lean 类型子集。
这些类型由代码的归纳类型 Ty 表示,并由一个函数将这些代码映射到实际类型。
inductive Ty where
| nat
| arr (dom cod : Ty)
abbrev Ty.interp : Ty → Type
| .nat => Nat
| .arr t t' => t.interp → t'.interp
语言本身表示为一个以变量上下文和结果类型为索引的索引族。
变量使用 de Bruijn 索引表示。
inductive Tm : List Ty → Ty → Type where
| zero : Tm Γ .nat
| succ (n : Tm Γ .nat) : Tm Γ .nat
| rep (n : Tm Γ .nat)
(start : Tm Γ t)
(f : Tm Γ (.arr .nat (.arr t t))) :
Tm Γ t
| lam (body : Tm (t :: Γ) t') : Tm Γ (.arr t t')
| app (f : Tm Γ (.arr t t')) (arg : Tm Γ t) : Tm Γ t'
| var (i : Fin Γ.length) : Tm Γ Γ[i]
deriving Repr
由于 Fin 的 OfNat 实例要求上界非零,因此将 Tm.var 与数值字面量一起使用可能不方便。
辅助函数 Tm.v 可在这些情况下避免类型标注。
def Tm.v
(i : Fin (Γ.length + 1)) :
Tm (t :: Γ) (t :: Γ)[i] :=
.var (Γ := t :: Γ) i
将两个自然数相加的函数使用 rep 运算重复应用后继 Tm.succ。
def plus : Tm [] (.arr .nat (.arr .nat .nat)) :=
.lam <| .lam <| .rep (.v 1) (.v 0) (.lam (.lam (.succ (.v 0))))
每个类型上下文都可以解释为一种运行时环境类型,为上下文中的每个变量提供值:
def Env : List Ty → Type
| [] => Unit
| t :: Γ => t.interp × Env Γ
def Env.empty : Env [] := ()
def Env.extend (ρ : Env Γ) (v : t.interp) : Env (t :: Γ) :=
(v, ρ)
def Env.get (i : Fin Γ.length) (ρ : Env Γ) : Γ[i].interp :=
match Γ, ρ, i with
| _::_, (v, _), ⟨0, _⟩ => v
| _::_, (_, ρ'), ⟨i+1, _⟩ => ρ'.get ⟨i, Γ:List Tyi✝:Fin Γ.lengthρ:Env Γhead✝:Tytail✝:List Tyfst✝:head✝.interpρ':Env tail✝i:NatisLt✝:i + 1 < (head✝ :: tail✝).length⊢ i < tail✝.length All goals completed! 🐙⟩
最后,解释器是关于项的递归函数:
def Tm.interp (ρ : Env α'') : Tm α'' t → t.interp
| .zero => 0
| .succ n => n.interp ρ + 1
| .rep n start f =>
let f' := f.interp ρ
(n.interp ρ).fold (fun n _ x => f' n x) (start.interp ρ)
| .lam body => fun x => body.interp (ρ.extend x)
| .app f arg => f.interp ρ (arg.interp ρ)
| .var i => ρ.get i
将 Tm 强制转换为函数,就是调用解释器。
instance : CoeFun (Tm [] α'') (fun _ => α''.interp) where
coe f := f.interp .empty
由于函数由一阶归纳类型表示,可以检查其代码:
Tm.lam (Tm.lam (Tm.rep (Tm.var 1) (Tm.var 0) (Tm.lam (Tm.lam (Tm.succ (Tm.var 0))))))#eval plus
Tm.lam (Tm.lam (Tm.rep (Tm.var 1) (Tm.var 0) (Tm.lam (Tm.lam (Tm.succ (Tm.var 0))))))
与此同时,凭借强制转换,它们可以像原生 Lean 函数一样应用:
8#eval plus 3 5
8