import DiffDog2.F32Sig import Lean namespace NestedAD scoped syntax (name := terseAD) "∂" term:max term:max : term open Lean Meta Elab Term /-! Opt in with `open scoped NestedAD` to enable both the terse two-operand `∂` syntax and function-let generalization inside its callbacks. Importing this module alone changes neither ordinary `∂` nor ordinary let elaboration. The frontend elaborates function boundaries, not a scalar term language: arithmetic, names, applications, tuples, patterns and static control flow are elaborated by Lean itself. The result/argument type determines the outer carrier (falling back to `LeanArray DDFloat32` for untyped literals). This experiment is scalar-input/scalar-output and fixed to `F32Sig`/the Float32 backend, not a signature-generic frontend. Static host branching works; branching on symbolic arrays is not promised. Only single untyped scalar function-let parameters are automatically generalized. Annotate host helpers (e.g. `n : Nat`) to keep them ordinary: untyped `let g n := n + 1` is ambiguous and is treated as AD here. Multiple/implicit/pattern parameters, recursion and equation-style AD function lets need an explicitly carrier-polymorphic definition instead. Function bodies remain a shared rank-2 let. Captures are transported by their resolved local declarations and array types; Nat/Bool/configuration values are unchanged. Captured tuples/records/lists containing arrays are NOT reconstructed: first destructure them into array leaves. Local containers and projections are ordinary Lean syntax. First-class or opaque monomorphic functions are NOT made polymorphic; named polymorphic functions are resolved normally and no opaque function body is inspected. No global `Nested` instance is added. Only fully applied two-operand `∂` activates these boundaries; unary/partial forms retain ordinary library behavior and require an already valid rank-2 callback. Examples and parser regressions live in `Examples/NestedDerivative.lean`. -/ private abbrev DefaultCarrier := LeanArray DDFloat32 -- Keeping the edge in the local context also preserves it across postponed elaboration. private structure BoundaryFrame (child parent : Shape → Type) (dictionary : Nested child parent) where token : Unit := () private structure CarrierEdge where child : Expr parent : Expr dictionary : Expr deriving Inhabited private def carrierPath : TermElabM (List CarrierEdge) := do return (← getLCtx).foldl (init := []) fun rest decl => if decl.type.isAppOfArity ``BoundaryFrame 3 then let args := decl.type.getAppArgs { child := args[0]!, parent := args[1]!, dictionary := args[2]! } :: rest else rest private def liftValue (edge : CarrierEdge) (shape value : Expr) : Expr := mkAppN (mkConst ``Nested.lift) #[edge.child, edge.parent, edge.dictionary, shape, value] /-- Dictionaries for exactly this lexical path, including a body-local identity dictionary. -/ private def pathDictionaries (edges : List CarrierEdge) : TermElabM (List (Expr × Expr)) := do let some first := edges.head? | return [] let shapeTy ← elabType (← `(Shape)) withLocalDecl `shape .implicit shapeTy fun shape => withLocalDeclD `value (mkApp first.child shape) fun value => do let mut entries := [(first.child, ← mkLambdaFVars #[shape, value] value)] let mut chain : List CarrierEdge := [] for edge in edges do chain := chain ++ [edge] let fn ← withLocalDeclD `captured (mkApp edge.parent shape) fun captured => do let lifted := chain.foldr (fun e v => liftValue e shape v) captured mkLambdaFVars #[shape, captured] lifted entries := entries ++ [(edge.parent, fn)] return ← entries.mapM fun (parent, fn) => do let ty := mkApp2 (mkConst ``Nested) first.child parent return (ty, mkAppN (mkConst ``Nested.mk) #[first.child, parent, fn]) private partial def withDictionaries (entries : List (Expr × Expr)) (k : TermElabM Expr) : TermElabM Expr := do match entries with | [] => k | (ty, value) :: rest => withLetDecl (← mkFreshUserName `adNested) ty value fun evidence => do mkLetFVars #[evidence] (← withDictionaries rest k) private def capturedArray? (edges : List CarrierEdge) (type : Expr) : TermElabM (Option (Expr × List CarrierEdge)) := do let type ← whnf (← instantiateMVars type) unless type.isApp do return none let carrier := type.appFn! let mut chain := [] for edge in edges do chain := chain ++ [edge] if ← withReducible <| isDefEq carrier edge.parent then return some (type.appArg!, chain) return none private partial def withCaptures (edges : List CarrierEdge) (captures : List LocalDecl) (k : TermElabM Expr) : TermElabM Expr := do match captures with | [] => k | decl :: rest => -- Compare declaration identity, not printed names; a new parameter may shadow a capture. let visible := (← getLCtx).findFromUserName? decl.userName if visible.any (·.fvarId == decl.fvarId) then if let some (shape, chain) ← capturedArray? edges decl.type then let value := chain.foldr (fun e v => liftValue e shape v) decl.toExpr withLetDecl decl.userName (mkApp edges.head!.child shape) value fun lifted => do mkLetFVars #[lifted] (← withCaptures edges rest k) else withCaptures edges rest k else withCaptures edges rest k private def withBoundaryContext (parent child dictionary : Expr) (ancestors : List CarrierEdge) (captures : List LocalDecl) (k : TermElabM Expr) : TermElabM Expr := do let edges := { child, parent, dictionary : CarrierEdge } :: ancestors let markerTy := mkAppN (mkConst ``BoundaryFrame) #[child, parent, dictionary] let markerVal := mkAppN (mkConst ``BoundaryFrame.mk) #[child, parent, dictionary, mkConst ``Unit.unit] withLetDecl (← mkFreshUserName `adEdge) markerTy markerVal (kind := .implDetail) fun marker => do -- Do not add a competing immediate-parent dictionary, or expose these in the signature. let dicts ← pathDictionaries edges let dicts := dicts.take 1 ++ dicts.drop 2 let result ← withDictionaries dicts <| withCaptures edges captures <| withSynthesize k mkLetFVars #[marker] (← instantiateMVars result) private def elabScalarBoundary (parent : Expr) (parameter : Ident) (body : Term) (expectedType? : Option Expr) : TermElabM Expr := do let ancestors ← carrierPath let captures := (← getLCtx).foldr (fun decl rest => decl :: rest) [] elabToSyntax (fun _ => pure parent) fun parentStx => elabToSyntax (fun expected? => do let some expected := expected? | throwError "nested AD: missing scalar boundary type" let expected ← instantiateMVars expected let child := expected.appFn! let dictionary ← synthInstance (mkApp2 (mkConst ``Nested) child parent) withBoundaryContext parent child dictionary ancestors captures <| elabTermEnsuringType body expected) fun bodyStx => do let stx ← `(fun {ADCarrier : Shape → Type} [Carrier F32Sig ADCarrier] [Interpretable F32Sig ADCarrier] [Nested ADCarrier $parentStx] ($parameter : ADCarrier []) => ($bodyStx : ADCarrier [])) elabTermEnsuringType stx expectedType? /-- Explicit lambda binders remain Lean's responsibility. Only wrap their scalar body boundary with a frame; do not alias captures here, since explicit callbacks may already use `⇧`. -/ private def elabExplicitBoundary (parent : Expr) (function : Term) (expected : Expr) : TermElabM Expr := do let `(fun $binders* => $body) := Parser.Term.dropParens function | return ← elabTermEnsuringType function expected let ancestors ← carrierPath elabToSyntax (fun result? => do let some result := result? | return ← elabTerm body none let result ← whnf (← instantiateMVars result) unless result.isApp do return ← elabTermEnsuringType body result let child := result.appFn! unless ← isDefEq (← inferType child) (← elabType (← `(Shape → Type))) do return ← elabTermEnsuringType body result let dictionary ← synthInstance (mkApp2 (Lean.mkConst ``Nested) child parent) withBoundaryContext parent child dictionary ancestors [] <| elabTermEnsuringType body result) fun bodyStx => do elabTermEnsuringType (← `(fun $binders* => $bodyStx)) expected /-- Adapt a function expression at the expected rank-2 boundary, without inspecting its body. Lean still resolves and instantiates the original function; the telescope supplies ancestor lifts when its closure belongs to an earlier carrier. -/ private def elabRankTwoBoundary (parent : Expr) (function : Term) (expected? : Option Expr) : TermElabM Expr := do let some expected := expected? | throwError "nested AD: missing rank-2 function type" if blockImplicitLambda function then return ← elabExplicitBoundary parent function expected let ancestors ← carrierPath let captures := (← getLCtx).foldr (fun decl rest => decl :: rest) [] forallBoundedTelescope expected (some 4) fun xs resultType => do unless xs.size == 4 do throwError "nested AD: expected the gradS rank-2 boundary" let child := xs[0]! let carrierType ← elabType (← `(Shape → Type)) let carrierClass ← mkAppM ``Carrier #[Lean.mkConst ``F32Sig, child] let interpreterClass ← mkAppM ``Interpretable #[Lean.mkConst ``F32Sig, child] let nestedClass := mkApp2 (Lean.mkConst ``Nested) child parent for x in xs, ty in #[carrierType, carrierClass, interpreterClass, nestedClass] do unless ← isDefEq (← inferType x) ty do throwError "nested AD: unexpected gradS boundary binder type" unless (← getFVarLocalDecl child).binderInfo == .implicit && (← xs.toList.drop 1 |>.allM fun x => return (← getFVarLocalDecl x).binderInfo == .instImplicit) do throwError "nested AD: unexpected gradS boundary binder kind" let scalar := mkApp child (← elabTerm (← `([])) (some (Lean.mkConst ``Shape))) unless ← isDefEq resultType (← mkArrow scalar scalar) do throwError "nested AD: expected a scalar function boundary" let result ← withBoundaryContext parent child xs[3]! ancestors captures <| elabTermEnsuringType function resultType mkLambdaFVars xs result private partial def scalarLambda? (stx : Term) : Option (Ident × Term) := match stx with | `(($inner)) => scalarLambda? inner | `(fun $x:ident => $body) => some (x, body) | _ => none -- This hook only changes function-let boundaries in an active callback, not ordinary lets. private def elabFunctionLet : TermElab := fun stx expected? => do let some current := (← carrierPath).head? | throwUnsupportedSyntax let some (name, parameter, value, body) := (match stx with | `(let $f:ident $y:ident := $value; $body) => some (f, y, value, body) | `(let $f:ident := $value; $body) => (scalarLambda? value).map fun (y, rhs) => (f, y, rhs, body) | _ => none) | throwUnsupportedSyntax elabToSyntax (elabScalarBoundary current.child parameter value) fun rhs => do let rebuilt ← `(let $name := @$rhs; $body) elabLetDeclCore rebuilt expected? {} private def carrierFromType? (type : Expr) : TermElabM (Option Expr) := do let type ← whnf (← instantiateMVars type) if type.isApp && !type.hasMVar then let candidate := type.appFn! if ← isDefEq (← inferType candidate) (← elabType (← `(Shape → Type))) then return some candidate return none private def outerCarrier (expected? : Option Expr) (argument : Term) : TermElabM Expr := do if let some type := expected? then if let some carrier ← carrierFromType? type then return carrier -- A numeral alone defaults to Nat without context; probe only for an already-known array type. -- Discard all probe state, including diagnostics and metavariables, before actual elaboration. let saved ← saveState let inferred ← try withoutErrToSorry <| withSynthesize do carrierFromType? (← inferType (← elabTerm argument none)) catch _ => pure none finally restoreState saved return inferred.getD (Lean.mkConst ``DefaultCarrier) @[scoped term_elab terseAD] private def elabDerivative : TermElab := fun stx expected? => do let `(∂ $f $x) := stx | throwUnsupportedSyntax let parent ← match (← carrierPath).head? with | some current => pure current.child | none => outerCarrier expected? x elabToSyntax (fun _ => pure parent) fun parentStx => do if let some (parameter, body) := scalarLambda? f then elabToSyntax (elabScalarBoundary parent parameter body) fun rhs => do let expanded ← `(gradS (Op := F32Sig) (R := $parentStx) @$rhs $x) elabTermEnsuringType expanded expected? else elabToSyntax (elabRankTwoBoundary parent f) fun rhs => do let expanded ← `(gradS (Op := F32Sig) (R := $parentStx) @$rhs $x) elabTermEnsuringType expanded expected? attribute [scoped term_elab Lean.Parser.Term.let] elabFunctionLet end NestedAD