Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Compiled ordinary matrix multiplication: source execution definitions

Definition
CLRS_Chapter4_Algo2LeanExamples_MatrixMultiplyGenerated

by Chutong · Oct 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgo2lean-clrs-chapter4-fd33cf9algorithmsclrsrunning-timetextbook

This bundle gives the deterministic generated transition system and scoped call/output relations for ordinary matrix multiplication, generated from matrix_multiply.algo at the pinned development source snapshot. Inputs use genuine Seq[Seq[Int]] arrays of row references. The generated semantics retain mutable aliasing, integer-indexed sequences, function calls, allocation and named source ticks. The semantics are distinct from the handwritten correctness proofs. Reproducing the generated code does not constitute a compiler-correctness proof.

Formalization Note. This content is transcribed from Algo2Lean development snapshot fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41, with explicit platform import and namespace adaptation. It is not attributed to public compiler v0.1.4. The submitted definition bundle must be checked without unfinished-proof assumptions.

Definition code
import Definitions.Def_CLRS_Chapter4_Algo2Lean
import Std

set_option autoImplicit false
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true

namespace CLRS

namespace «MatrixMultiplyLibrary»

open _root_.CLRS.Algo2LeanGenerated

-- Generated by Algo2Lean 0.1.1 https://github.com/lunjiah/algo2lean
-- Generated direct transitions; outputs are completed valid transcripts.
namespace Algo2LeanGenerated

def seq_Seq_Int : SequenceType SeqRef where
  name := "Seq[Int]"
  encode := fun value => (ObjectValue.seqValue value)
  decode := ObjectValue.asSeq
  decode_encode := by intro value; rfl

structure State_matrix_dot where
  v0 : CollectionRef := 0 -- a
  v1 : CollectionRef := 0 -- b
  v2 : Int := 0 -- n
  v3 : Int := 0 -- row
  v4 : Int := 0 -- column
  v5 : Int := 0 -- k
  v6 : Int := 0 -- total
  t7 : Int := 0 -- temporary
  t8 : Bool := false -- temporary

structure State_matrix_row where
  v0 : CollectionRef := 0 -- a
  v1 : CollectionRef := 0 -- b
  v2 : Int := 0 -- n
  v3 : Int := 0 -- row
  v4 : SeqRef := 0 -- result
  v5 : Int := 0 -- column
  v6 : Int := 0 -- value
  t7 : SeqRef := 0 -- temporary
  t8 : Bool := false -- temporary
  t9 : Int := 0 -- temporary
  t10 : CollectionRef := 0 -- temporary
  t11 : CollectionRef := 0 -- temporary
  t12 : Int := 0 -- temporary
  t13 : Int := 0 -- temporary
  t14 : Int := 0 -- temporary
  t15 : SeqRef := 0 -- temporary
  t16 : Int := 0 -- temporary

structure State_matrix_multiply where
  v0 : CollectionRef := 0 -- a
  v1 : CollectionRef := 0 -- b
  v2 : Int := 0 -- n
  v3 : CollectionRef := 0 -- result
  v4 : Int := 0 -- row
  t5 : CollectionRef := 0 -- temporary
  t6 : Bool := false -- temporary
  t7 : SeqRef := 0 -- temporary
  t8 : Int := 0 -- temporary
  t9 : CollectionRef := 0 -- temporary
  t10 : CollectionRef := 0 -- temporary
  t11 : CollectionRef := 0 -- temporary
  t12 : Int := 0 -- temporary
  t13 : Int := 0 -- temporary
  t14 : CollectionRef := 0 -- temporary
  t15 : SeqRef := 0 -- temporary
  t16 : Int := 0 -- temporary

inductive Frame where
  | invalid
  | fn_matrix_dot (pc : Nat) (state : State_matrix_dot)
  | fn_matrix_row (pc : Nat) (state : State_matrix_row)
  | fn_matrix_multiply (pc : Nat) (state : State_matrix_multiply)

inductive Result where
  | fn_matrix_dot (value : Int)
  | fn_matrix_row (value : SeqRef)
  | fn_matrix_multiply (value : CollectionRef)

abbrev Configuration := Algo2LeanCore.Config Heap Frame Result
abbrev Stack := Algo2LeanCore.Stack Frame Result


inductive Step : Configuration → Configuration → Prop where
  | matrix_dot_pc1 (h : Heap) (s : State_matrix_dot) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_dot 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_matrix_dot (s.t7)) stack)
  | matrix_dot_pc2 (h : Heap) (s : State_matrix_dot) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_dot 2 s) stack) (.active h (Frame.fn_matrix_dot 1 { s with t7 := s.v6 }) stack)
  | matrix_dot_pc3_true (h : Heap) (s : State_matrix_dot) (stack : Stack) (condition : s.t8 = true) :
      Step (.active h (Frame.fn_matrix_dot 3 s) stack) (.active h (Frame.fn_matrix_dot 7 s) stack)
  | matrix_dot_pc3_false (h : Heap) (s : State_matrix_dot) (stack : Stack) (condition : s.t8 = false) :
      Step (.active h (Frame.fn_matrix_dot 3 s) stack) (.active h (Frame.fn_matrix_dot 2 s) stack)
  | matrix_dot_pc4 (h : Heap) (s : State_matrix_dot) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_dot 4 s) stack) (.active h (Frame.fn_matrix_dot 3 { s with t8 := (decide ((s.v5 < s.v2))) }) stack)
  | matrix_dot_pc5 (h : Heap) (s : State_matrix_dot) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_dot 5 s) stack) (.active h (Frame.fn_matrix_dot 4 { s with v5 := (s.v5 + (1 : Int)) }) stack)
  | matrix_dot_pc6 (h : Heap) (s : State_matrix_dot) (stack : Stack) (defined : (((((seq_Seq_Int.get h s.v0 s.v3).isSome = true)) ∧ (((seq_Seq_Int.get h s.v0 s.v3).getD 0) < h.nextRef)) ∧ ((((seq_Seq_Int.get h s.v1 s.v5).isSome = true)) ∧ (((seq_Seq_Int.get h s.v1 s.v5).getD 0) < h.nextRef)))) :
      Step (.active h (Frame.fn_matrix_dot 6 s) stack) (.active h (Frame.fn_matrix_dot 5 { s with v6 := (s.v6 + ((h.read ((seq_Seq_Int.get h s.v0 s.v3).getD 0) s.v5) * (h.read ((seq_Seq_Int.get h s.v1 s.v5).getD 0) s.v4))) }) stack)
  | matrix_dot_pc7 (h : Heap) (s : State_matrix_dot) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_dot 7 s) stack) (.active (h.tick "multiply_add" 1) (Frame.fn_matrix_dot 6 s) stack)
  | matrix_dot_pc8 (h : Heap) (s : State_matrix_dot) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_dot 8 s) stack) (.active h (Frame.fn_matrix_dot 4 { s with v6 := (0 : Int) }) stack)
  | matrix_dot_pc9 (h : Heap) (s : State_matrix_dot) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_dot 9 s) stack) (.active h (Frame.fn_matrix_dot 8 { s with v5 := (0 : Int) }) stack)
  | matrix_row_pc1 (h : Heap) (s : State_matrix_row) (stack : Stack) (defined : s.t7 < h.nextRef) :
      Step (.active h (Frame.fn_matrix_row 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_matrix_row (s.t7)) stack)
  | matrix_row_pc2 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 2 s) stack) (.active h (Frame.fn_matrix_row 1 { s with t7 := s.v4 }) stack)
  | matrix_row_pc3_true (h : Heap) (s : State_matrix_row) (stack : Stack) (condition : s.t8 = true) :
      Step (.active h (Frame.fn_matrix_row 3 s) stack) (.active h (Frame.fn_matrix_row 13 s) stack)
  | matrix_row_pc3_false (h : Heap) (s : State_matrix_row) (stack : Stack) (condition : s.t8 = false) :
      Step (.active h (Frame.fn_matrix_row 3 s) stack) (.active h (Frame.fn_matrix_row 2 s) stack)
  | matrix_row_pc4 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 4 s) stack) (.active h (Frame.fn_matrix_row 3 { s with t8 := (decide ((s.v5 < s.v2))) }) stack)
  | matrix_row_pc5 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 5 s) stack) (.active h (Frame.fn_matrix_row 4 { s with v5 := (s.v5 + (1 : Int)) }) stack)
  | matrix_row_pc6 (h : Heap) (s : State_matrix_row) (stack : Stack) (defined : s.v4 < h.nextRef) :
      Step (.active h (Frame.fn_matrix_row 6 s) stack) (.active (h.write s.v4 s.v5 s.v6) (Frame.fn_matrix_row 5 s) stack)
  | matrix_row_pc7 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 7 s) stack) (.active h (Frame.fn_matrix_row 6 { s with v6 := s.t9 }) stack)
  | matrix_row_pc8 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 8 s) stack) (.active h (Frame.fn_matrix_dot 9 ({ v0 := s.t10, v1 := s.t11, v2 := s.t12, v3 := s.t13, v4 := s.t14 } : State_matrix_dot)) ((fun value => match value with | .fn_matrix_dot result => (Frame.fn_matrix_row 7 { s with t9 := result }) | _ => .invalid) :: stack))
  | matrix_row_pc9 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 9 s) stack) (.active h (Frame.fn_matrix_row 8 { s with t14 := s.v5 }) stack)
  | matrix_row_pc10 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 10 s) stack) (.active h (Frame.fn_matrix_row 9 { s with t13 := s.v3 }) stack)
  | matrix_row_pc11 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 11 s) stack) (.active h (Frame.fn_matrix_row 10 { s with t12 := s.v2 }) stack)
  | matrix_row_pc12 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 12 s) stack) (.active h (Frame.fn_matrix_row 11 { s with t11 := s.v1 }) stack)
  | matrix_row_pc13 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 13 s) stack) (.active h (Frame.fn_matrix_row 12 { s with t10 := s.v0 }) stack)
  | matrix_row_pc14 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 14 s) stack) (.active h (Frame.fn_matrix_row 4 { s with v5 := (0 : Int) }) stack)
  | matrix_row_pc15 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 15 s) stack) (.active h (Frame.fn_matrix_row 14 { s with v4 := s.t15 }) stack)
  | matrix_row_pc16 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 16 s) stack) (.active (h.allocate (fun _ => s.t16)) (Frame.fn_matrix_row 15 { s with t15 := h.nextRef }) stack)
  | matrix_row_pc17 (h : Heap) (s : State_matrix_row) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_row 17 s) stack) (.active h (Frame.fn_matrix_row 16 { s with t16 := (0 : Int) }) stack)
  | matrix_multiply_pc1 (h : Heap) (s : State_matrix_multiply) (stack : Stack) (defined : seq_Seq_Int.valid h s.t5) :
      Step (.active h (Frame.fn_matrix_multiply 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_matrix_multiply (s.t5)) stack)
  | matrix_multiply_pc2 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 2 s) stack) (.active h (Frame.fn_matrix_multiply 1 { s with t5 := s.v3 }) stack)
  | matrix_multiply_pc3_true (h : Heap) (s : State_matrix_multiply) (stack : Stack) (condition : s.t6 = true) :
      Step (.active h (Frame.fn_matrix_multiply 3 s) stack) (.active h (Frame.fn_matrix_multiply 13 s) stack)
  | matrix_multiply_pc3_false (h : Heap) (s : State_matrix_multiply) (stack : Stack) (condition : s.t6 = false) :
      Step (.active h (Frame.fn_matrix_multiply 3 s) stack) (.active h (Frame.fn_matrix_multiply 2 s) stack)
  | matrix_multiply_pc4 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 4 s) stack) (.active h (Frame.fn_matrix_multiply 3 { s with t6 := (decide ((s.v4 < s.v2))) }) stack)
  | matrix_multiply_pc5 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 5 s) stack) (.active h (Frame.fn_matrix_multiply 4 { s with v4 := (s.v4 + (1 : Int)) }) stack)
  | matrix_multiply_pc6 (h : Heap) (s : State_matrix_multiply) (stack : Stack) (defined : (seq_Seq_Int.valid h s.t9)) :
      Step (.active h (Frame.fn_matrix_multiply 6 s) stack) (.active (seq_Seq_Int.set h s.t9 s.t8 s.t7) (Frame.fn_matrix_multiply 5 s) stack)
  | matrix_multiply_pc7 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 7 s) stack) (.active h (Frame.fn_matrix_multiply 6 { s with t8 := s.v4 }) stack)
  | matrix_multiply_pc8 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 8 s) stack) (.active h (Frame.fn_matrix_multiply 7 { s with t9 := s.v3 }) stack)
  | matrix_multiply_pc9 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 9 s) stack) (.active h (Frame.fn_matrix_row 17 ({ v0 := s.t10, v1 := s.t11, v2 := s.t12, v3 := s.t13 } : State_matrix_row)) ((fun value => match value with | .fn_matrix_row result => (Frame.fn_matrix_multiply 8 { s with t7 := result }) | _ => .invalid) :: stack))
  | matrix_multiply_pc10 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 10 s) stack) (.active h (Frame.fn_matrix_multiply 9 { s with t13 := s.v4 }) stack)
  | matrix_multiply_pc11 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 11 s) stack) (.active h (Frame.fn_matrix_multiply 10 { s with t12 := s.v2 }) stack)
  | matrix_multiply_pc12 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 12 s) stack) (.active h (Frame.fn_matrix_multiply 11 { s with t11 := s.v1 }) stack)
  | matrix_multiply_pc13 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 13 s) stack) (.active h (Frame.fn_matrix_multiply 12 { s with t10 := s.v0 }) stack)
  | matrix_multiply_pc14 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 14 s) stack) (.active h (Frame.fn_matrix_multiply 4 { s with v4 := (0 : Int) }) stack)
  | matrix_multiply_pc15 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 15 s) stack) (.active h (Frame.fn_matrix_multiply 14 { s with v3 := s.t14 }) stack)
  | matrix_multiply_pc16 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 16 s) stack) (.active (seq_Seq_Int.const h s.t15).1 (Frame.fn_matrix_multiply 15 { s with t14 := h.nextCollection }) stack)
  | matrix_multiply_pc17 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 17 s) stack) (.active (h.allocate (fun _ => s.t16)) (Frame.fn_matrix_multiply 16 { s with t15 := h.nextRef }) stack)
  | matrix_multiply_pc18 (h : Heap) (s : State_matrix_multiply) (stack : Stack) :
      Step (.active h (Frame.fn_matrix_multiply 18 s) stack) (.active h (Frame.fn_matrix_multiply 17 { s with t16 := (0 : Int) }) stack)

end Algo2LeanGenerated

open Algo2LeanGenerated

def matrix_dot.ValidInput (h : Heap) (input : CollectionRef × CollectionRef × Int × Int × Int) : Prop := seq_Seq_Int.valid h input.1 ∧ seq_Seq_Int.valid h input.2.1



def matrix_dot.Call (h : Heap) (input : CollectionRef × CollectionRef × Int × Int × Int) (h' : Heap) (output : Int) : Prop :=
  _root_.CLRS.MatrixMultiplyLibrary.matrix_dot.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_matrix_dot 9 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2.1, v3 := input.2.2.2.1, v4 := input.2.2.2.2 } : State_matrix_dot)) h' (Result.fn_matrix_dot output)
-- Complete this function from the supplied local state, under any caller stack.
def matrix_dot.CallFrom (state : Configuration) (finalHeap : Heap) (output : Int) : Prop :=
  match state with
  | .active heap (Frame.fn_matrix_dot pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_matrix_dot pc locals) finalHeap (Result.fn_matrix_dot output)
  | _ => False
-- Object inputs carry their heap, preserving shared references and cycles.




-- Output and clock increments from one completed execution.






def matrix_row.ValidInput (h : Heap) (input : CollectionRef × CollectionRef × Int × Int) : Prop := seq_Seq_Int.valid h input.1 ∧ seq_Seq_Int.valid h input.2.1



def matrix_row.Call (h : Heap) (input : CollectionRef × CollectionRef × Int × Int) (h' : Heap) (output : SeqRef) : Prop :=
  _root_.CLRS.MatrixMultiplyLibrary.matrix_row.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_matrix_row 17 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2.1, v3 := input.2.2.2 } : State_matrix_row)) h' (Result.fn_matrix_row output)
-- Complete this function from the supplied local state, under any caller stack.
def matrix_row.CallFrom (state : Configuration) (finalHeap : Heap) (output : SeqRef) : Prop :=
  match state with
  | .active heap (Frame.fn_matrix_row pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_matrix_row pc locals) finalHeap (Result.fn_matrix_row output)
  | _ => False
-- Object inputs carry their heap, preserving shared references and cycles.




-- Output and clock increments from one completed execution.






def matrix_multiply.ValidInput (h : Heap) (input : CollectionRef × CollectionRef × Int) : Prop := seq_Seq_Int.valid h input.1 ∧ seq_Seq_Int.valid h input.2.1
def matrix_multiply.initial (h : Heap) (input : CollectionRef × CollectionRef × Int) : Configuration :=
  Algo2LeanCore.start h (Frame.fn_matrix_multiply 18 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2 } : State_matrix_multiply))
def matrix_multiply.Run (h : Heap) (input : CollectionRef × CollectionRef × Int) (h' : Heap) (output : CollectionRef) : Prop :=
  _root_.CLRS.MatrixMultiplyLibrary.matrix_multiply.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.CLRS.MatrixMultiplyLibrary.matrix_multiply.initial h input) (.done h' (Result.fn_matrix_multiply output))

def matrix_multiply.Call (h : Heap) (input : CollectionRef × CollectionRef × Int) (h' : Heap) (output : CollectionRef) : Prop :=
  _root_.CLRS.MatrixMultiplyLibrary.matrix_multiply.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_matrix_multiply 18 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2 } : State_matrix_multiply)) h' (Result.fn_matrix_multiply output)
-- Complete this function from the supplied local state, under any caller stack.
def matrix_multiply.CallFrom (state : Configuration) (finalHeap : Heap) (output : CollectionRef) : Prop :=
  match state with
  | .active heap (Frame.fn_matrix_multiply pc locals) _ =>
      Algo2LeanCore.Summary Step heap (Frame.fn_matrix_multiply pc locals) finalHeap (Result.fn_matrix_multiply output)
  | _ => False
-- Object inputs carry their heap, preserving shared references and cycles.




-- Output and clock increments from one completed execution.







end «MatrixMultiplyLibrary»

end CLRS
Source
Algo2Lean Chapter 4 development, module Algo2LeanExamples.MatrixMultiplyGenerated, immutable source fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41: https://github.com/chutongyang98/Lean_formalization/blob/fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41/examples/matrix_multiply.algo; https://github.com/chutongyang98/Lean_formalization/blob/fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41/examples/analysis/matrix_multiply.lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me