blob: 8ea9d06323c1af648de2fa28dc4db08f72113288 [file]
/-
Copyright (c) 2022 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
module
prelude
public import Lean.Compiler.LCNF.Bind
public section
namespace Lean.Compiler.LCNF
private def refreshBinderName (binderName : Name) : CompilerM Name := do
match binderName with
| .num p _ =>
let r := .num p (← get).nextIdx
modify fun s => { s with nextIdx := s.nextIdx + 1 }
return r
| _ => return binderName
namespace Internalize
abbrev InternalizeM (pu : Purity) := StateRefT (FVarSubst pu) CompilerM
/--
The `InternalizeM` monad is a translator. It "translates" the free variables
in the input expressions and `Code`, into new fresh free variables in the
local context.
-/
instance : MonadFVarSubst (InternalizeM pu) pu true where
getSubst := get
instance : MonadFVarSubstState (InternalizeM pu) pu where
modifySubst := modify
private def mkNewFVarId (fvarId : FVarId) : InternalizeM pu FVarId := do
let fvarId' ← Lean.mkFreshFVarId
addFVarSubst fvarId fvarId'
return fvarId'
private partial def internalizeExpr (e : Expr) : InternalizeM pu Expr :=
go e
where
goApp (e : Expr) : InternalizeM pu Expr := do
match e with
| .app f a => return e.updateApp! (← goApp f) (← go a)
| _ => go e
go (e : Expr) : InternalizeM pu Expr := do
if e.hasFVar then
match e with
| .fvar fvarId =>
match (← get)[fvarId]? with
| some (.fvar fvarId') =>
-- In LCNF, types can't depend on let-bound fvars.
if (← findParam? (pu := pu) fvarId').isSome then
return .fvar fvarId'
else
return anyExpr
| some .erased => return erasedExpr
| some (.type e _) | none => return e
| .lit .. | .const .. | .sort .. | .mvar .. | .bvar .. => return e
| .app f a => return e.updateApp! (← goApp f) (← go a) |>.headBeta
| .mdata _ b => return e.updateMData! (← go b)
| .proj _ _ b => return e.updateProj! (← go b)
| .forallE _ d b _ => return e.updateForallE! (← go d) (← go b)
| .lam _ d b _ => return e.updateLambdaE! (← go d) (← go b)
| .letE .. => unreachable!
else
return e
def internalizeParam (p : Param pu) : InternalizeM pu (Param pu) := do
let binderName ← refreshBinderName p.binderName
let type ← internalizeExpr p.type
let fvarId ← mkNewFVarId p.fvarId
let p := { p with binderName, fvarId, type }
modifyLCtx fun lctx => lctx.addParam p
return p
def internalizeArg (arg : Arg pu) : InternalizeM pu (Arg pu) := do
match arg with
| .fvar fvarId =>
match (← get)[fvarId]? with
| some arg'@(.fvar _) => return arg'
| some arg'@.erased | some arg'@(.type _ _) => return arg'
| none => return arg
| .type e _ => return arg.updateType! (← internalizeExpr e)
| .erased => return arg
def internalizeArgs (args : Array (Arg pu)) : InternalizeM pu (Array (Arg pu)) :=
args.mapM internalizeArg
private partial def internalizeLetValue (e : LetValue pu) : InternalizeM pu (LetValue pu) := do
match e with
| .erased | .lit .. => return e
| .proj _ _ fvarId _ | .oproj _ fvarId _ | .sproj _ _ fvarId _ | .uproj _ fvarId _ =>
match (← normFVar fvarId) with
| .fvar fvarId' => return e.updateProj! fvarId'
| .erased => return .erased
| .const _ _ args _ | .fap _ args _ | .pap _ args _ | .ctor _ args _ =>
return e.updateArgs! (← internalizeArgs args)
| .fvar fvarId args => match (← normFVar fvarId) with
| .fvar fvarId' => return e.updateFVar! fvarId' (← internalizeArgs args)
| .erased => return .erased
def internalizeLetDecl (decl : LetDecl pu) : InternalizeM pu (LetDecl pu) := do
let binderName ← refreshBinderName decl.binderName
let type ← internalizeExpr decl.type
let value ← internalizeLetValue decl.value
let fvarId ← mkNewFVarId decl.fvarId
let decl := { decl with binderName, fvarId, type, value }
modifyLCtx fun lctx => lctx.addLetDecl decl
return decl
mutual
partial def internalizeFunDecl (decl : FunDecl pu) : InternalizeM pu (FunDecl pu) := do
let type ← internalizeExpr decl.type
let binderName ← refreshBinderName decl.binderName
let params ← decl.params.mapM internalizeParam
let value ← internalizeCode decl.value
let fvarId ← mkNewFVarId decl.fvarId
let decl := ⟨fvarId, binderName, params, type, value⟩
modifyLCtx fun lctx => lctx.addFunDecl decl
return decl
partial def internalizeCode (code : Code pu) : InternalizeM pu (Code pu) := do
match code with
| .let decl k => return .let (← internalizeLetDecl decl) (← internalizeCode k)
| .fun decl k _ => return .fun (← internalizeFunDecl decl) (← internalizeCode k)
| .jp decl k => return .jp (← internalizeFunDecl decl) (← internalizeCode k)
| .return fvarId => withNormFVarResult (← normFVar fvarId) fun fvarId => return .return fvarId
| .jmp fvarId args => withNormFVarResult (← normFVar fvarId) fun fvarId => return .jmp fvarId (← internalizeArgs args)
| .unreach type => return .unreach (← internalizeExpr type)
| .cases c =>
withNormFVarResult (← normFVar c.discr) fun discr => do
let resultType ← internalizeExpr c.resultType
let alts ← c.alts.mapM fun
| .alt ctorName params k _ => return .alt ctorName (← params.mapM internalizeParam) (← internalizeCode k)
| .default k => return .default (← internalizeCode k)
| .ctorAlt i k _ => return .ctorAlt i (← internalizeCode k)
return .cases ⟨c.typeName, resultType, discr, alts⟩
| .sset fvarId i offset y ty k _ =>
withNormFVarResult (← normFVar fvarId) fun fvarId => do
withNormFVarResult (← normFVar y) fun y => do
return .sset fvarId i offset y (← internalizeExpr ty) (← internalizeCode k)
| .uset fvarId offset y k _ =>
withNormFVarResult (← normFVar fvarId) fun fvarId => do
withNormFVarResult (← normFVar y) fun y => do
return .uset fvarId offset y (← internalizeCode k)
end
partial def internalizeCodeDecl (decl : CodeDecl pu) : InternalizeM pu (CodeDecl pu) := do
match decl with
| .let decl => return .let (← internalizeLetDecl decl)
| .fun decl _ => return .fun (← internalizeFunDecl decl)
| .jp decl => return .jp (← internalizeFunDecl decl)
| .uset var i y _ =>
-- Something weird should be happening if these become erased...
let .fvar var ← normFVar var | unreachable!
let .fvar y ← normFVar y | unreachable!
return .uset var i y
| .sset var i offset y ty _ =>
let .fvar var ← normFVar var | unreachable!
let .fvar y ← normFVar y | unreachable!
let ty ← normExpr ty
return .sset var i offset y ty
end Internalize
/--
Refresh free variables ids in `code`, and store their declarations in the local context.
-/
partial def Code.internalize (code : Code pu) (s : FVarSubst pu := {}) : CompilerM (Code pu) :=
Internalize.internalizeCode code |>.run' s
open Internalize in
def Decl.internalize (decl : Decl pu) (s : FVarSubst pu := {}): CompilerM (Decl pu) :=
go decl |>.run' s
where
go (decl : Decl pu) : InternalizeM pu (Decl pu) := do
let type ← internalizeExpr decl.type
let params ← decl.params.mapM internalizeParam
let value ← decl.value.mapCodeM internalizeCode
return { decl with type, params, value }
/--
Create a fresh local context and internalize the given decls.
-/
def cleanup (decl : Array (Decl pu)) : CompilerM (Array (Decl pu)) := do
modify fun _ => {}
decl.mapM fun decl => do
modify fun s => { s with nextIdx := 1 }
decl.internalize
def normalizeFVarIds (decl : Decl pu) : CoreM (Decl pu) := do
let ngenSaved ← getNGen
setNGen {}
try
CompilerM.run <| decl.internalize
finally
setNGen ngenSaved
end Lean.Compiler.LCNF