Compiled ordinary matrix multiplication: source execution definitions
DefinitionCLRS_Chapter4_Algo2LeanExamples_MatrixMultiplyGeneratedThis 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.
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