TorchLean

8.1. Tensors and Graphs🔗

TorchLean starts with shape-indexed tensors and then offers three ways to describe a computation. GraphSpec.Chain is typed sequential syntax, GraphSpec.DAG adds sharing, and NN.IR.Graph is the ordinary op-tagged graph used at runtime boundaries. Keeping those representations distinct makes the claims attached to each one easier to read.

Definition8.1.1
Group: Scalar operations, tensor shapes, and the algebra used by model specifications. (9)
Group member previews
Preview
Definition 8.1.2
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 0
Used by 9
Reverse dependency previews
Preview
Definition 8.1.2
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Context α collects the arithmetic, order, constants, natural-number casts, and transcendental operations needed by scalar-polymorphic model code. It carries no laws.

Lean code for Definition8.1.11 definition
  • class(extends 18, 38 methods)defined in NN/Spec/Core/Context.lean
    complete
    class Context (α : Type) : Type
    class Context (α : Type) : Type
    The full scalar interface required by spec-level tensors and models. 
    • Inhabited α
    • One α
    • Zero α
    • Add α
    • Sub α
    • Mul α
    • Div α
    • Neg α
    • Pow α α
    • Max α
    • Min α
    • BEq α
    • LT α
    • LE α
    • MathFunctions α
    • NatCast α
    • RatCast α
    • TorchLean.Numeric.QuotientArithmetic α
    default : α
    Inherited from
    1. Inhabited
    one : α
    Inherited from
    1. One
    zero : α
    Inherited from
    1. Zero
    add : α  α  α
    Inherited from
    1. Add
    sub : α  α  α
    Inherited from
    1. Sub
    mul : α  α  α
    Inherited from
    1. Mul
    div : α  α  α
    Inherited from
    1. Div
    neg : α  α
    Inherited from
    1. Neg
    pow : α  α  α
    Inherited from
    1. Pow
    max : α  α  α
    Inherited from
    1. Max
    min : α  α  α
    Inherited from
    1. Min
    beq : α  α  Bool
    Inherited from
    1. BEq
    lt : α  α  Prop
    Inherited from
    1. LT
    le : α  α  Prop
    Inherited from
    1. LE
    exp : α  α
    Inherited from
    1. FloatLib.Numerics.MathFunctions
    tanh : α  α
    Inherited from
    1. FloatLib.Numerics.MathFunctions
    cosh : α  α
    Inherited from
    1. FloatLib.Numerics.MathFunctions
    sqrt : α  α
    Inherited from
    1. FloatLib.Numerics.MathFunctions
    abs : α  α
    Inherited from
    1. FloatLib.Numerics.MathFunctions
    log : α  α
    Inherited from
    1. FloatLib.Numerics.MathFunctions
    pi : α
    Inherited from
    1. FloatLib.Numerics.MathFunctions
    cos : α  α
    Inherited from
    1. FloatLib.Numerics.MathFunctions
    sin : α  α
    Inherited from
    1. FloatLib.Numerics.MathFunctions
    sinh : α  α
    Inherited from
    1. FloatLib.Numerics.MathFunctions
    natCast :   α
    Inherited from
    1. NatCast
    ratCast :   α
    Inherited from
    1. RatCast
    supported : Bool
    Inherited from
    1. TorchLean.Numeric.QuotientArithmetic
    depth : 
    Inherited from
    1. TorchLean.Numeric.QuotientArithmetic
    addWithFlags : α  α  α × UInt8
    Inherited from
    1. TorchLean.Numeric.QuotientArithmetic
    subWithFlags : α  α  α × UInt8
    Inherited from
    1. TorchLean.Numeric.QuotientArithmetic
    mulWithFlags : α  α  α × UInt8
    Inherited from
    1. TorchLean.Numeric.QuotientArithmetic
    divWithFlags : α  α  α × UInt8
    Inherited from
    1. TorchLean.Numeric.QuotientArithmetic
    encode : α  Option (TorchLean.Numeric.QuotientCoefficients (TorchLean.Numeric.QuotientArithmetic.depth α))
    Inherited from
    1. TorchLean.Numeric.QuotientArithmetic
    decode : TorchLean.Numeric.QuotientCoefficients (TorchLean.Numeric.QuotientArithmetic.depth α)  Option α
    Inherited from
    1. TorchLean.Numeric.QuotientArithmetic
    copyPrimal : α  α  α
    Inherited from
    1. TorchLean.Numeric.QuotientArithmetic
    defaultEpsilon : α
    Backend-selected safeguard used by default in guarded formulas; not machine epsilon. 
    decidableGT : DecidableRel fun x1 x2 => x1 > x2
    Decision procedure for the scalar type's strict order. 
    stopGradient? : Option (α  α)
    Remove differentiation metadata from a scalar at a `detach` boundary.
    
    Ordinary numeric carriers leave this as `none`, so detaching a tensor can reuse its storage.
    A carrier such as `Dual α` supplies a map that keeps the primal value and clears its tangents.
    This is needed when a reverse pass runs over dual numbers: cutting the tape edge alone would
    leave the detached value's forward tangent available to later operations.
    
Definition8.1.2
Group: Scalar operations, tensor shapes, and the algebra used by model specifications. (9)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

LawfulContext α records, for a scalar type that also carries a Mathlib linearly ordered field structure, that the Context dictionary computes the same addition, multiplication, subtraction, division, negation, order, maximum, minimum, absolute value, and small numeric constants as the field, and that its epsilon is positive. The instance for is proved; transcendental constants and the total power operation stay unconstrained.

This separation lets executable scalar types provide operations without claiming field laws that rounded arithmetic cannot satisfy. A theorem using LawfulContext can transfer the listed operations to Mathlib's field structure. It still needs any further hypotheses about logarithms, exponentials, or powers explicitly; the class does not supply those analytic facts.

Lean code for Definition8.1.21 definition
  • class(16 methods)defined in NN/Spec/Core/Context.lean
    complete
    class LawfulContext (α : Type) [Context α] [Field α] [LinearOrder α]
      [IsStrictOrderedRing α] : Prop
    class LawfulContext (α : Type) [Context α]
      [Field α] [LinearOrder α]
      [IsStrictOrderedRing α] : Prop
    Compatibility of a `Context` dictionary with a linearly ordered field structure on the same type.
    
    Each field equates a `Context` projection (written with the explicit instance path
    `Context.to*`) with the corresponding Mathlib operation.
    
    add_eq :  (x y : α), x + y = x + y
    Dictionary addition is ring addition. 
    mul_eq :  (x y : α), x * y = x * y
    Dictionary multiplication is ring multiplication. 
    sub_eq :  (x y : α), x - y = x - y
    Dictionary subtraction is ring subtraction. 
    div_eq :  (x y : α), x / y = x / y
    Dictionary division is field division. 
    neg_eq :  (x : α), -x = -x
    Dictionary negation is ring negation. 
    zero_eq : Zero.zero = Zero.zero
    The dictionary zero is the ring zero. 
    one_eq : One.one = One.one
    The dictionary one is the ring one. 
    lt_iff :  (x y : α), x < y  x < y
    The dictionary strict order is the field order. 
    le_iff :  (x y : α), x  y  x  y
    The dictionary order is the field order. 
    max_eq :  (x y : α), x  y = max x y
    Dictionary `max` is the lattice maximum. 
    min_eq :  (x y : α), x  y = min x y
    Dictionary `min` is the lattice minimum. 
    beq_iff :  (x y : α), (x == y) = true  x = y
    Boolean equality decides propositional equality. 
    natCast_eq :  (n : ), n = n
    The natural-number cast is the semiring cast. 
    ratCast_eq :  (value : ), value = value
    The rational-number cast is the field cast. 
    abs_eq :  (x : α), MathFunctions.abs x = |x|
    The dictionary absolute value is the lattice absolute value. 
    defaultEpsilon_pos : 0 < Context.defaultEpsilon
    The backend tolerance is strictly positive. 
Definition8.1.3
Group: Scalar operations, tensor shapes, and the algebra used by model specifications. (9)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 0
Used by 14
Reverse dependency previews
Preview
Theorem 8.1.7
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

Spec.Shape is List Nat, the dimensions outermost first, and it indexes TorchLean.Tensor α s, so tensor dimensions are present in the type. Each value stores one contiguous row-major buffer with a proof that its length equals the shape's element count. Storage α selects packed FloatArray storage for Float, ByteArray for UInt8, and ordinary arrays for other scalars. Proofs observe this same value through coordinate lookup; the storage invariant does not prove the correctness of native C or CUDA implementations.

Lean code for Definition8.1.31 definition
  • complete
    abbrev TorchLean.Tensor (α : Type) (shape : Spec.Shape) [TorchLean.Storage α] :
      Type
    abbrev TorchLean.Tensor (α : Type)
      (shape : Spec.Shape)
      [TorchLean.Storage α] : Type
    The single tensor representation used by TorchLean proofs and execution.
    
    The public shape is `Spec.Shape`, which is the same type as the shape carried by the buffer, so
    this alias only reorders arguments. The implementation is one certified contiguous row-major buffer
    selected by `Storage`.
    
Definition8.1.4
Group: Scalar operations, tensor shapes, and the algebra used by model specifications. (9)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 0used by 1L∃∀N

A shape is well formed when every one of its dimensions is positive.

The empty list of dimensions satisfies this condition and describes one scalar coordinate. A shape with a zero axis instead has no elements and fails the condition. This distinction is why positivity of total size is a useful hypothesis for a mean or a normalization denominator.

Lean code for Definition8.1.41 definition
  • complete
    def Spec.Shape.wellFormed : Spec.Shape  Prop
    def Spec.Shape.wellFormed : Spec.Shape  Prop
    `well_formed s` means "all dimensions of `s` are positive" (recursively). 
Definition8.1.5
Group: Scalar operations, tensor shapes, and the algebra used by model specifications. (9)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 0used by 0L∃∀N

CanBroadcastTo s₁ s₂ records when values with shape s₁ can be expanded to shape s₂.

Lean code for Definition8.1.51 definition
  • complete
    def Spec.Shape.CanBroadcastTo : Spec.Shape  Spec.Shape  Prop
    def Spec.Shape.CanBroadcastTo :
      Spec.Shape  Spec.Shape  Prop
    `CanBroadcastTo source target` holds when `source` broadcasts to `target` with right-aligned
    axes: after prepending singleton axes to reach the target rank, every source extent equals the
    target extent or is one. 
Theorem8.1.6
Group: Scalar operations, tensor shapes, and the algebra used by model specifications. (9)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

A well-formed shape has positive total size.

Lean code for Theorem8.1.61 theorem
  • theoremdefined in NN/Spec/Core/Shape.lean
    complete
    theorem Spec.Shape.size_pos_of_well_formed {s : Spec.Shape} :
      s.wellFormed  0 < s.size
    theorem Spec.Shape.size_pos_of_well_formed
      {s : Spec.Shape} :
      s.wellFormed  0 < s.size
    If `s.wellFormed`, then `Spec.Shape.size s > 0`. 
Proof for Theorem 8.1.6

The proof recurses over the list of axes and uses positivity of every dimension.

Theorem8.1.7
Group: Scalar operations, tensor shapes, and the algebra used by model specifications. (9)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

Rebuilding a flattened shape-indexed tensor at its original shape returns that tensor.

Lean code for Theorem8.1.71 theorem
  • theorem TorchLean.Tensor.unflattenSpec_flattenSpec {α : Type}
      [TorchLean.Storage α] {shape : Spec.Shape}
      (tensor : TorchLean.Tensor α shape) :
      TorchLean.Tensor.unflattenSpec shape tensor.flattenSpec = tensor
    theorem TorchLean.Tensor.unflattenSpec_flattenSpec
      {α : Type} [TorchLean.Storage α]
      {shape : Spec.Shape}
      (tensor : TorchLean.Tensor α shape) :
      TorchLean.Tensor.unflattenSpec shape
          tensor.flattenSpec =
        tensor
    Unflattening a flattened tensor returns the original tensor. 
Proof for Theorem 8.1.7
uses 0

Flattening and rebuilding preserve the same certified row-major scalar sequence; the proof reduces to the inverse laws for the tensor representation's zero-copy reshape.

Definition8.1.8
Group: Scalar operations, tensor shapes, and the algebra used by model specifications. (9)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 1L∃∀N

toEuclidean is a linear equivalence between the real tensor representation at a shape and the Euclidean space indexed by its coordinates. The NormedAddCommGroup and InnerProductSpace ℝ instances on real tensors are induced along it, so a real tensor is a finite-dimensional inner-product space without a second representation.

Coordinates give the connection: each tensor entry becomes the corresponding coordinate of the Euclidean vector, and the inverse reconstructs those entries. The induced norm is therefore about the same values used by tensor operations. Analytic statements can use Mathlib's normed-space API without introducing a separate tensor conversion into every theorem.

Lean code for Definition8.1.81 definition
  • complete
    def TorchLean.Tensor.toEuclidean (s : TorchLean.Tensor.Internal.Shape) :
      TorchLean.Tensor.Internal.Rep  s ≃ₗ[]
        EuclideanSpace  (TorchLean.Tensor.Internal.Coord s)
    def TorchLean.Tensor.toEuclidean
      (s : TorchLean.Tensor.Internal.Shape) :
      TorchLean.Tensor.Internal.Rep  s ≃ₗ[]
        EuclideanSpace 
          (TorchLean.Tensor.Internal.Coord s)
    The coordinate view of a real tensor as a point of Euclidean space. 
Theorem8.1.9
Group: Scalar operations, tensor shapes, and the algebra used by model specifications. (9)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

Under the induced structure, the inner product of two real tensors is the sum of their coordinatewise products; the norm lemmas of the tensor library follow from this formula.

Lean code for Theorem8.1.91 theorem
  • complete
    theorem TorchLean.Tensor.inner_eq_sum {s : TorchLean.Tensor.Internal.Shape}
      (x y : TorchLean.Tensor.Internal.Rep  s) :
      inner  x y =  i, x.get i * y.get i
    theorem TorchLean.Tensor.inner_eq_sum
      {s : TorchLean.Tensor.Internal.Shape}
      (x y :
        TorchLean.Tensor.Internal.Rep  s) :
      inner  x y =  i, x.get i * y.get i
    The inner product of two real tensors is the sum of coordinatewise products. 
Proof for Theorem 8.1.9

The inner product is transported along toEuclidean, where it is the Euclidean sum.

Theorem8.1.10
Group: Scalar operations, tensor shapes, and the algebra used by model specifications. (9)
Group member previews
Preview
Definition 8.1.1
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 1L∃∀N

Matrix-vector multiplication satisfies the dot-product adjoint identity used by the linear-layer gradient rule for typed tensors over a commutative semiring.

Lean code for Theorem8.1.101 theorem
  • complete
    theorem Proofs.TensorAlgebra.dot_mat_linear_adjoint {α : Type}
      [TorchLean.Storage α] [CommSemiring α] {inDim outDim : }
      (W : TorchLean.Tensor α [outDim, inDim])
      (dLdy : TorchLean.Tensor α [outDim])
      (dx : TorchLean.Tensor α [inDim]) :
      Proofs.TensorAlgebra.dot dLdy (Spec.matVecMulSpec W dx) =
        Proofs.TensorAlgebra.dot (Spec.vecMatMulSpec dLdy W) dx
    theorem Proofs.TensorAlgebra.dot_mat_linear_adjoint
      {α : Type} [TorchLean.Storage α]
      [CommSemiring α] {inDim outDim : }
      (W : TorchLean.Tensor α [outDim, inDim])
      (dLdy : TorchLean.Tensor α [outDim])
      (dx : TorchLean.Tensor α [inDim]) :
      Proofs.TensorAlgebra.dot dLdy
          (Spec.matVecMulSpec W dx) =
        Proofs.TensorAlgebra.dot
          (Spec.vecMatMulSpec dLdy W) dx
    Matrix-vector and vector-matrix multiplication are adjoint under `dot`. 
Proof for Theorem 8.1.10

The proof expands the typed tensor operations into finite sums and rearranges those sums.

For an input perturbation dx and output cotangent dLdy, this moves the linear map from one side of the dot product to the other. The resulting input cotangent has the input width. The semiring hypotheses justify rearranging exact sums; this identity alone does not bound rounded reductions.

Definition8.1.11
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.12
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 0
Used by 3
Reverse dependency previews
Preview
Definition 8.1.12
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

A sequential GraphSpec records its parameter shapes, input shape, and output shape in its type. Graphs are built from identity, primitive, and sequential-composition nodes.

Lean code for Definition8.1.111 definition
  • inductive(3 constructors, 3 parameters)defined in NN/GraphSpec/Chain/Syntax.lean
    complete
    inductive NN.GraphSpec.Chain : List Spec.Shape  Spec.Shape  Spec.Shape  Type 2
    inductive NN.GraphSpec.Chain :
      List Spec.Shape 
        Spec.Shape  Spec.Shape  Type 2
    `Chain ps σ τ` is a sequential model from shape `σ` to shape `τ` whose parameters have shapes
    `ps`, in order. Composition concatenates parameter ABIs; use `NN.GraphSpec.DAG` when explicit
    sharing or multi-input nodes are required.
    
    NN.GraphSpec.Chain.id (s : Spec.Shape) :
      NN.GraphSpec.Chain [] s s
    Identity chain: passes the input through unchanged and requires no parameters. 
    NN.GraphSpec.Chain.seq {ps₁ ps₂ : List Spec.Shape}
      {σ τ υ : Spec.Shape} :
      NN.GraphSpec.Chain ps₁ σ τ 
        NN.GraphSpec.Chain ps₂ τ υ 
          NN.GraphSpec.Chain (ps₁ ++ ps₂) σ υ
    Sequential composition. Parameter lists concatenate. 
    NN.GraphSpec.Chain.prim {ps : List Spec.Shape}
      {σ τ : Spec.Shape} :
      NN.GraphSpec.Primitive ps σ τ  NN.GraphSpec.Chain ps σ τ
    Embed a single primitive node in a chain. 
Definition8.1.12
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 3
Statement dependency previews
Preview
Definition 8.1.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
used by 1L∃∀N
Lean code for Definition8.1.121 definition
  • complete
    def NN.GraphSpec.Interp.spec {ps : List Spec.Shape} {σ τ : Spec.Shape}
      (g : NN.GraphSpec.Chain ps σ τ) {α : Type} [TorchLean.Storage α]
      [Context α] :
      TorchLean.TensorPack α ps 
        TorchLean.Tensor α σ  TorchLean.Tensor α τ
    def NN.GraphSpec.Interp.spec
      {ps : List Spec.Shape}
      {σ τ : Spec.Shape}
      (g : NN.GraphSpec.Chain ps σ τ)
      {α : Type} [TorchLean.Storage α]
      [Context α] :
      TorchLean.TensorPack α ps 
        TorchLean.Tensor α σ 
          TorchLean.Tensor α τ
    Pure tensor semantics of a sequential `Chain`. 
Definition8.1.13
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 2
Statement dependency previews
Preview
Definition 8.1.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
used by 0L∃∀N

The runtime translation turns a sequential graph into an execution-polymorphic TorchLean program over the same scalar operations.

Lean code for Definition8.1.131 definition
  • complete
    def NN.GraphSpec.Chain.toProgram {ps : List Spec.Shape} {σ τ : Spec.Shape}
      (g : NN.GraphSpec.Chain ps σ τ) {α : Type} [TorchLean.Storage α]
      [Context α] : Runtime.Autograd.Model.Program α (ps ++ [σ]) τ
    def NN.GraphSpec.Chain.toProgram
      {ps : List Spec.Shape}
      {σ τ : Spec.Shape}
      (g : NN.GraphSpec.Chain ps σ τ)
      {α : Type} [TorchLean.Storage α]
      [Context α] :
      Runtime.Autograd.Model.Program α
        (ps ++ [σ]) τ
    Lower a sequential `Chain` to an execution-polymorphic TorchLean program. 
Definition8.1.14
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 0
Used by 2
Reverse dependency previews
Preview
Definition 8.1.15
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

A typed DAG model pairs initialized parameters with a term whose environment contains the parameter and input shapes. Terms may name arguments and share intermediate results.

Sharing is represented by a typed reference into that environment. Two later operations can use one previously computed value without copying its defining term. The reference's shape determines which operations may consume it, while the environment records where the value came from.

Lean code for Definition8.1.141 definition
  • structure(2 fields)defined in NN/GraphSpec/DAG/Model.lean
    complete
    structure NN.GraphSpec.DAG.Model (ps ins : List Spec.Shape) (τ : Spec.Shape) :
      Type 1
    structure NN.GraphSpec.DAG.Model
      (ps ins : List Spec.Shape)
      (τ : Spec.Shape) : Type 1
    A small “model” wrapper around DAG terms.
    
    This mirrors the sequential `Chain` surface:
    
    - `ps` are parameter tensor shapes (tracked at the type level),
    - `ins` are the shapes of *non-parameter inputs* (e.g. data tensors),
    - `τ` is the output shape.
    
    The model body is a `Term (ps ++ ins) τ`, i.e. it expects an environment that starts with
    parameters and then contains the actual inputs.
     
    initParams : TorchLean.TensorPack Float ps
    Initial parameter values, one tensor per shape in `ps`. Shipping the initialization with the
    model means a `Model` is runnable on its own, with no separate setup step. 
    body : NN.GraphSpec.DAG.Term (ps ++ ins) τ
    The computation itself, as a term over the environment `ps ++ ins`: parameters first, then
    data inputs. That fixed ordering is what lets `initParams` be typed by `ps` alone. 
Definition8.1.15
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 2
Statement dependency previews
Preview
Definition 8.1.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
used by 0L∃∀N

The DAG interpreter evaluates the model body from typed parameter and input lists under the scalar context.

Lean code for Definition8.1.151 definition
  • complete
    def NN.GraphSpec.DAG.Model.specFwd {ps ins : List Spec.Shape}
      {τ : Spec.Shape} (m : NN.GraphSpec.DAG.Model ps ins τ) {α : Type}
      [TorchLean.Storage α] [Context α] (params : TorchLean.TensorPack α ps)
      (xs : TorchLean.TensorPack α ins) : TorchLean.Tensor α τ
    def NN.GraphSpec.DAG.Model.specFwd
      {ps ins : List Spec.Shape}
      {τ : Spec.Shape}
      (m : NN.GraphSpec.DAG.Model ps ins τ)
      {α : Type} [TorchLean.Storage α]
      [Context α]
      (params : TorchLean.TensorPack α ps)
      (xs : TorchLean.TensorPack α ins) :
      TorchLean.Tensor α τ
    Pure forward semantics of a DAG model.
    
    We build the full environment `Γ = ps ++ ins` by appending the parameter list and the input list,
    then evaluate the body using `Term.eval`.
     
Definition8.1.16
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 2
Statement dependency previews
Preview
Definition 8.1.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
used by 0L∃∀N

The DAG lowering pass turns the same model body into an execution-polymorphic TorchLean program over the same scalar operations.

Lean code for Definition8.1.161 definition
  • complete
    def NN.GraphSpec.DAG.Model.toProgram {ps ins : List Spec.Shape}
      {τ : Spec.Shape} (m : NN.GraphSpec.DAG.Model ps ins τ) {α : Type}
      [TorchLean.Storage α] [Context α] :
      Runtime.Autograd.Model.Program α (ps ++ ins) τ
    def NN.GraphSpec.DAG.Model.toProgram
      {ps ins : List Spec.Shape}
      {τ : Spec.Shape}
      (m : NN.GraphSpec.DAG.Model ps ins τ)
      {α : Type} [TorchLean.Storage α]
      [Context α] :
      Runtime.Autograd.Model.Program α
        (ps ++ ins) τ
    Lower a DAG model to an execution-polymorphic TorchLean program.
    
    The resulting program expects arguments in the order `ps ++ ins` (parameters first, then inputs),
    matching the environment discipline used by `specFwd`.
     
Definition8.1.17
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1
Used by 2
Reverse dependency previews
Preview
Theorem 8.1.18
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

The sequential GraphSpec MLP composes two linear maps with an intervening ReLU. Its type fixes the order and shapes of both weights and biases.

Lean code for Definition8.1.171 definition
  • complete
    def NN.GraphSpec.Models.mlp (inputWidth hiddenWidth outputWidth : ) :
      NN.GraphSpec.Chain
        [[hiddenWidth, inputWidth], [hiddenWidth],
          [outputWidth, hiddenWidth], [outputWidth]]
        [inputWidth] [outputWidth]
    def NN.GraphSpec.Models.mlp
      (inputWidth hiddenWidth outputWidth :
        ) :
      NN.GraphSpec.Chain
        [[hiddenWidth, inputWidth],
          [hiddenWidth],
          [outputWidth, hiddenWidth],
          [outputWidth]]
        [inputWidth] [outputWidth]
    2-layer MLP: `Linear(input, hidden) → ReLU → Linear(hidden, output)`.
    
    Notice how the parameter interface is explicit in the type:
    
    - the first linear layer contributes tensors `W₁ : Tensor α [hiddenWidth, inputWidth]` and
      `b₁ : Tensor α [hiddenWidth]`,
    - the second linear layer contributes tensors `W₂ : Tensor α [outputWidth, hiddenWidth]` and
      `b₂ : Tensor α [outputWidth]`,
    - and `ReLU` contributes no parameters.
    
    So the overall parameter list is exactly:
    `[[hiddenWidth, inputWidth], [hiddenWidth], [outputWidth, hiddenWidth], [outputWidth]]`.
    
Theorem8.1.18
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

Interpreting the GraphSpec MLP gives the same tensor as the hand-written two-layer MLP specification.

Both sides receive the same parameter tensors and input. The result identifies two descriptions of that forward computation; it does not compare separately trained models or establish that an optimizer reaches particular weights. Initialization alignment below addresses the distinct question of how the initial parameter pack is assembled.

Lean code for Theorem8.1.181 theorem
  • complete
    theorem NN.GraphSpec.Models.mlp_interp_eq_spec_mlp_forward {α : Type}
      [TorchLean.Storage α] [Context α]
      {inputWidth hiddenWidth outputWidth : }
      (params :
        TorchLean.TensorPack α
          (NN.GraphSpec.Models.MLPParams inputWidth hiddenWidth
            outputWidth))
      (x : TorchLean.Tensor α [inputWidth]) :
      NN.GraphSpec.Interp.spec
          (NN.GraphSpec.Models.mlp inputWidth hiddenWidth outputWidth)
          params x =
        match
          match params with
          |
          TorchLean.TensorPack.cons w1
              (TorchLean.TensorPack.cons b1
                (TorchLean.TensorPack.cons w2
                  (TorchLean.TensorPack.cons b2
                    TorchLean.TensorPack.nil))) =>
            (w1, b1, w2, b2) with
        | (w1, b1, w2, b2) =>
          have l1 := { weights := w1, bias := b1 };
          have l2 := { weights := w2, bias := b2 };
          Examples.mlpForward l1 l2 x
    theorem NN.GraphSpec.Models.mlp_interp_eq_spec_mlp_forward
      {α : Type} [TorchLean.Storage α]
      [Context α]
      {inputWidth hiddenWidth outputWidth : }
      (params :
        TorchLean.TensorPack α
          (NN.GraphSpec.Models.MLPParams
            inputWidth hiddenWidth
            outputWidth))
      (x : TorchLean.Tensor α [inputWidth]) :
      NN.GraphSpec.Interp.spec
          (NN.GraphSpec.Models.mlp inputWidth
            hiddenWidth outputWidth)
          params x =
        match
          match params with
          |
          TorchLean.TensorPack.cons w1
              (TorchLean.TensorPack.cons b1
                (TorchLean.TensorPack.cons w2
                  (TorchLean.TensorPack.cons
                    b2
                    TorchLean.TensorPack.nil))) =>
            (w1, b1, w2, b2) with
        | (w1, b1, w2, b2) =>
          have l1 :=
            { weights := w1, bias := b1 };
          have l2 :=
            { weights := w2, bias := b2 };
          Examples.mlpForward l1 l2 x
    **Theorem (GraphSpec MLP agrees with Spec reference).**
    
    Fix widths `inputWidth → hiddenWidth → outputWidth`. Let `params` be the 4-tensor parameter list
    `(W₁, b₁, W₂, b₂)` and `x` an input vector.
    
    Then the GraphSpec interpreter applied to the GraphSpec MLP graph computes exactly the same tensor
    as the reference `Examples.mlpForward` from `NN.Spec.Models.Mlp`, after interpreting the parameter
    list as two `LinearSpec`s.
    
    Informally, both sides compute the same explicit formula:
    
    $$
    \begin{aligned}
    z_1 &= W_1x+b_1,\\
    a_1 &= \operatorname{ReLU}(z_1),\\
    \mathrm{out} &= W_2a_1+b_2.
    \end{aligned}
    $$
    
    where the dot/plus are the `Spec.linearSpec` and `Activation.reluSpec` operations already used by
    the Spec model.
    
Proof for Theorem 8.1.18
Proof uses 2
Proof dependency previews
Preview
Definition 8.1.12
Loading preview
Proof dependency preview content is loaded from the rendered-fragment cache.

The proof unpacks the four-tensor parameter list, unfolds the pure interpreter for the MLP, and reduces both sides to the same two linear maps with an intervening ReLU.

Theorem8.1.19
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

Deterministic initialization for the GraphSpec MLP produces the same typed parameter list, in the same order, as the two TorchLean linear-layer initializers.

Lean code for Theorem8.1.191 theorem
  • theorem NN.GraphSpec.Models.mlp_detInitParams_eq_torchlean_linear_inits
      (inputWidth hiddenWidth outputWidth : ) :
      NN.GraphSpec.LowerToDAG.Chain.detInitParams?
          (NN.GraphSpec.Models.mlp inputWidth hiddenWidth outputWidth) =
        Except.ok
          ((Runtime.Autograd.Model.Layers.linear inputWidth
                  hiddenWidth).initState.append
            (Runtime.Autograd.Model.Layers.linear hiddenWidth outputWidth
                1).initState)
    theorem NN.GraphSpec.Models.mlp_detInitParams_eq_torchlean_linear_inits
      (inputWidth hiddenWidth outputWidth :
        ) :
      NN.GraphSpec.LowerToDAG.Chain.detInitParams?
          (NN.GraphSpec.Models.mlp inputWidth
            hiddenWidth outputWidth) =
        Except.ok
          ((Runtime.Autograd.Model.Layers.linear
                  inputWidth
                  hiddenWidth).initState.append
            (Runtime.Autograd.Model.Layers.linear
                hiddenWidth outputWidth
                1).initState)
    Deterministic init for `Models.mlp` is exactly the concatenation of the two TorchLean `Linear`
    initializers.
    
    Seed discipline:
    
    - the first linear weight uses occurrence index `0`,
    - the second linear weight uses occurrence index `1`,
    - both biases are initialized exactly to zero.
    
Proof for Theorem 8.1.19

For the two-layer graph, the occurrence-indexed seed calculation reduces to seeds 0, 1 for the first layer and 2, 3 for the second.

Definition8.1.20
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 0used by 1L∃∀N

The Boolean structural predicate checks that node identifiers match their array positions, operation arities are valid, and every parent points to an earlier node.

Lean code for Definition8.1.201 definition
  • defdefined in NN/IR/Graph.lean
    complete
    def NN.IR.Graph.wellFormed (g : NN.IR.Graph) : Bool
    def NN.IR.Graph.wellFormed (g : NN.IR.Graph) :
      Bool
    Basic well-formedness check used by verifier code paths.
    
    This checks:
    - node ids match array indices (common construction invariant),
    - each node respects its op arity convention, and
    - all parent ids are strictly smaller than the node id (topological order).
    
    We keep this as a boolean predicate because some passes want a fast “yes/no” filter. If you need a
    human-facing error, use `checkWellFormed`.
    
Definition8.1.21
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 0
Used by 5
Reverse dependency previews
Preview
Definition 8.1.22
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

The diagnostic checker enforces the same conditions as the Boolean structural predicate, but returns the first useful error message instead of a bare false. The two implementations are kept separate; no equivalence theorem currently connects them.

Lean code for Definition8.1.211 definition
  • defdefined in NN/IR/Graph.lean
    complete
    def NN.IR.Graph.checkWellFormed (g : NN.IR.Graph) : Except String Unit
    def NN.IR.Graph.checkWellFormed
      (g : NN.IR.Graph) : Except String Unit
    Like `wellFormed`, but returns a helpful error message on failure.
    
    This is useful when you want a *clean* user error rather than a silent `false`.
    
Definition8.1.22
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1
Used by 3
Reverse dependency previews
Preview
Theorem 8.1.24
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

After the structural check, shape validation infers every node's output shape and compares it with the shape stored in the graph.

Lean code for Definition8.1.221 definition
  • defdefined in NN/IR/Infer.lean
    complete
    def NN.IR.Graph.checkShapes (g : NN.IR.Graph) : Except String Unit
    def NN.IR.Graph.checkShapes
      (g : NN.IR.Graph) : Except String Unit
    Infer shapes for every node (in topo/id order) and check that `Node.outShape` matches.
    
    This is meant as a lowering/backend consistency check and as a clean IR invariant for the docs:
    well-formed graphs have *self-consistent declared shapes*. `NN.IR.ShapeSoundness` proves that on a
    graph accepted here the reference semantics computes exactly the declared shapes.
    
Definition8.1.23
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 3
Statement dependency previews
Preview
Definition 8.1.1
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
Used by 6
Reverse dependency previews
Preview
Theorem 8.1.24
Loading preview
Reverse dependency preview content is loaded from the rendered-fragment cache.
L∃∀N

After the structural check, IR denotation evaluates every node into a table of shape-tagged tensor values using scalar-polymorphic operations and the supplied external payload.

Lean code for Definition8.1.231 definition
  • defdefined in NN/IR/Semantics.lean
    complete
    def NN.IR.Graph.denoteAll {α : Type} [TorchLean.Storage α] [Context α]
      (g : NN.IR.Graph) (payload : NN.IR.Payload α)
      (input : Spec.SomeTensor α) :
      Except String (Array (Spec.SomeTensor α))
    def NN.IR.Graph.denoteAll {α : Type}
      [TorchLean.Storage α] [Context α]
      (g : NN.IR.Graph)
      (payload : NN.IR.Payload α)
      (input : Spec.SomeTensor α) :
      Except String
        (Array (Spec.SomeTensor α))
    Evaluate a graph to a table of node values.
    
    This returns an array `vals` of length `g.size` where `vals[i]` is the value of node `i`.
    
    We do a structural well-formedness check once up front (ids/arity/topology). For lowering-produced
    graphs, the boolean `Graph.wellFormed` check is a fast path; if it fails we fall back to the
    exception-producing `Graph.checkWellFormed` so callers get a readable error message.
    
    The evaluator always returns either:
    - `.ok vals` (all nodes evaluated successfully), or
    - `.error msg` describing the first failure (malformed IR, missing payload, a local shape error, or
      a `.log` of a nonpositive entry).
    
    `Graph.checkShapes` is not run here: the per-node checks reject the same ill-shaped graphs, and the
    existing lowering-correctness proofs unfold `denoteAll` with only the structural check in place.
    `NN.IR.ShapeSoundness.denoteAllRaw_eq_denoteAll` shows that on a `checkShapes`-accepted graph the
    per-node declared-shape normalization is redundant.
    
Theorem8.1.24
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
Statement uses 2
Statement dependency previews
Preview
Definition 8.1.22
Loading preview
Statement dependency preview content is loaded from the rendered-fragment cache.
used by 0L∃∀N

If a graph passes shape validation and denotation succeeds, then every value in the resulting table has exactly the output shape declared by its node. Shape inference and the reference semantics are two matches over the operation kinds; this theorem says they agree.

The two success hypotheses serve different purposes. Shape validation checks the declared graph against its operators; successful denotation supplies the actual value table to which the conclusion applies. The theorem does not turn a passed shape check into a guarantee that evaluation succeeds for every external payload or scalar input.

Lean code for Theorem8.1.241 theorem
  • theoremdefined in NN/IR/ShapeSoundness.lean
    complete
    theorem NN.IR.Graph.checkShapes_sound {α : Type} [TorchLean.Storage α]
      [Context α] (g : NN.IR.Graph) (payload : NN.IR.Payload α)
      (input : Spec.SomeTensor α) (vals : Array (Spec.SomeTensor α))
      (hShapes : g.checkShapes = Except.ok ())
      (hEval : g.denoteAll payload input = Except.ok vals) (i : )
      (hi : i < g.nodes.size) (hiv : i < vals.size) :
      vals[i].shape = g.nodes[i].outShape
    theorem NN.IR.Graph.checkShapes_sound {α : Type}
      [TorchLean.Storage α] [Context α]
      (g : NN.IR.Graph)
      (payload : NN.IR.Payload α)
      (input : Spec.SomeTensor α)
      (vals : Array (Spec.SomeTensor α))
      (hShapes : g.checkShapes = Except.ok ())
      (hEval :
        g.denoteAll payload input =
          Except.ok vals)
      (i : ) (hi : i < g.nodes.size)
      (hiv : i < vals.size) :
      vals[i].shape = g.nodes[i].outShape
    Shape inference is sound for the reference semantics: if `checkShapes` accepts a graph and the
    graph evaluates, every node value has the shape inference assigned to it, namely the declared
    one. 
Proof for Theorem 8.1.24
Proof uses 2
Proof dependency previews
Preview
Definition 8.1.22
Loading preview
Proof dependency preview content is loaded from the rendered-fragment cache.

One lemma per operator family shows that the raw node evaluator returns the inferred shape when its parents have the inferred shapes. An induction over the node array then runs inference and evaluation in lockstep.

Theorem8.1.25
Group: Typed architecture descriptions and the shared runtime graph. (14)
Group member previews
Preview
Definition 8.1.11
Loading preview
Group member preview content is loaded from the rendered-fragment cache.
uses 1used by 0L∃∀N

Whenever denotation succeeds, the value table has one entry per node and each entry carries its node's declared shape. This holds without a prior shape check because the evaluator normalizes each result against the declared shape and fails otherwise.

Lean code for Theorem8.1.251 theorem
  • theoremdefined in NN/IR/ShapeSoundness.lean
    complete
    theorem NN.IR.Graph.denoteAll_shape {α : Type} [TorchLean.Storage α] [Context α]
      (g : NN.IR.Graph) (payload : NN.IR.Payload α)
      (input : Spec.SomeTensor α) (vals : Array (Spec.SomeTensor α))
      (h : g.denoteAll payload input = Except.ok vals) :
      vals.size = g.nodes.size 
         (i : ) (hi : i < g.nodes.size) (hiv : i < vals.size),
          vals[i].shape = g.nodes[i].outShape
    theorem NN.IR.Graph.denoteAll_shape {α : Type}
      [TorchLean.Storage α] [Context α]
      (g : NN.IR.Graph)
      (payload : NN.IR.Payload α)
      (input : Spec.SomeTensor α)
      (vals : Array (Spec.SomeTensor α))
      (h :
        g.denoteAll payload input =
          Except.ok vals) :
      vals.size = g.nodes.size 
         (i : ) (hi : i < g.nodes.size)
          (hiv : i < vals.size),
          vals[i].shape = g.nodes[i].outShape
    The literal soundness statement: on a well-shaped graph, every evaluated node value has its
    declared shape.
    
    Note that `hShapes` is not needed for the conclusion, because `evalNode` normalizes each value to
    the declared shape (`denoteAll_shape`); its role is documented by `denoteAllRaw_eq_denoteAll`, which
    shows that on a `checkShapes`-accepted graph the normalization never changes anything.