Compiled eight-way recursive matrix multiplication: source execution definitions
DefinitionCLRS_Chapter4_Algo2LeanExamples_MatrixRecursiveGeneratedThis bundle gives the deterministic generated transition system and scoped call/output relations for eight-way recursive matrix multiplication, generated from matrix_recursive.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 «MatrixRecursiveLibrary»
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_block where
v0 : CollectionRef := 0 -- a
v1 : CollectionRef := 0 -- b
v2 : CollectionRef := 0 -- c
v3 : Int := 0 -- stride
v4 : Int := 0 -- row
v5 : Int := 0 -- col
v6 : Int := 0 -- inner
v7 : Int := 0 -- n
v8 : Int := 0 -- half
t9 : Int := 0 -- temporary
t10 : Int := 0 -- temporary
t11 : CollectionRef := 0 -- temporary
t12 : CollectionRef := 0 -- temporary
t13 : CollectionRef := 0 -- temporary
t14 : Int := 0 -- temporary
t15 : Int := 0 -- temporary
t16 : Int := 0 -- temporary
t17 : Int := 0 -- temporary
t18 : Int := 0 -- temporary
t19 : Int := 0 -- temporary
t20 : CollectionRef := 0 -- temporary
t21 : CollectionRef := 0 -- temporary
t22 : CollectionRef := 0 -- temporary
t23 : Int := 0 -- temporary
t24 : Int := 0 -- temporary
t25 : Int := 0 -- temporary
t26 : Int := 0 -- temporary
t27 : Int := 0 -- temporary
t28 : Int := 0 -- temporary
t29 : CollectionRef := 0 -- temporary
t30 : CollectionRef := 0 -- temporary
t31 : CollectionRef := 0 -- temporary
t32 : Int := 0 -- temporary
t33 : Int := 0 -- temporary
t34 : Int := 0 -- temporary
t35 : Int := 0 -- temporary
t36 : Int := 0 -- temporary
t37 : Int := 0 -- temporary
t38 : CollectionRef := 0 -- temporary
t39 : CollectionRef := 0 -- temporary
t40 : CollectionRef := 0 -- temporary
t41 : Int := 0 -- temporary
t42 : Int := 0 -- temporary
t43 : Int := 0 -- temporary
t44 : Int := 0 -- temporary
t45 : Int := 0 -- temporary
t46 : Int := 0 -- temporary
t47 : CollectionRef := 0 -- temporary
t48 : CollectionRef := 0 -- temporary
t49 : CollectionRef := 0 -- temporary
t50 : Int := 0 -- temporary
t51 : Int := 0 -- temporary
t52 : Int := 0 -- temporary
t53 : Int := 0 -- temporary
t54 : Int := 0 -- temporary
t55 : Int := 0 -- temporary
t56 : CollectionRef := 0 -- temporary
t57 : CollectionRef := 0 -- temporary
t58 : CollectionRef := 0 -- temporary
t59 : Int := 0 -- temporary
t60 : Int := 0 -- temporary
t61 : Int := 0 -- temporary
t62 : Int := 0 -- temporary
t63 : Int := 0 -- temporary
t64 : Int := 0 -- temporary
t65 : CollectionRef := 0 -- temporary
t66 : CollectionRef := 0 -- temporary
t67 : CollectionRef := 0 -- temporary
t68 : Int := 0 -- temporary
t69 : Int := 0 -- temporary
t70 : Int := 0 -- temporary
t71 : Int := 0 -- temporary
t72 : Int := 0 -- temporary
t73 : Int := 0 -- temporary
t74 : CollectionRef := 0 -- temporary
t75 : CollectionRef := 0 -- temporary
t76 : CollectionRef := 0 -- temporary
t77 : Int := 0 -- temporary
t78 : Int := 0 -- temporary
t79 : Int := 0 -- temporary
t80 : Int := 0 -- temporary
t81 : Int := 0 -- temporary
t82 : Bool := false -- temporary
t83 : Int := 0 -- temporary
structure State_matrix_recursive where
v0 : CollectionRef := 0 -- a
v1 : CollectionRef := 0 -- b
v2 : Int := 0 -- n
v3 : CollectionRef := 0 -- c
v4 : Int := 0 -- row
t5 : CollectionRef := 0 -- temporary
t6 : Int := 0 -- temporary
t7 : CollectionRef := 0 -- temporary
t8 : CollectionRef := 0 -- temporary
t9 : CollectionRef := 0 -- temporary
t10 : Int := 0 -- temporary
t11 : Int := 0 -- temporary
t12 : Int := 0 -- temporary
t13 : Int := 0 -- temporary
t14 : Int := 0 -- temporary
t15 : Bool := false -- temporary
t16 : SeqRef := 0 -- temporary
t17 : Int := 0 -- temporary
t18 : CollectionRef := 0 -- temporary
t19 : Int := 0 -- temporary
t20 : CollectionRef := 0 -- temporary
t21 : SeqRef := 0 -- temporary
t22 : Int := 0 -- temporary
inductive Frame where
| invalid
| fn_matrix_block (pc : Nat) (state : State_matrix_block)
| fn_matrix_recursive (pc : Nat) (state : State_matrix_recursive)
inductive Result where
| fn_matrix_block (value : Int)
| fn_matrix_recursive (value : CollectionRef)
abbrev Configuration := Algo2LeanCore.Config Heap Frame Result
abbrev Stack := Algo2LeanCore.Stack Frame Result
inductive Step : Configuration → Configuration → Prop where
| matrix_block_pc1 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_matrix_block (s.t9)) stack)
| matrix_block_pc2 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 2 s) stack) (.active h (Frame.fn_matrix_block 1 { s with t9 := (0 : Int) }) stack)
| matrix_block_pc3 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 3 s) stack) (.active h (Frame.fn_matrix_block 82 ({ v0 := s.t11, v1 := s.t12, v2 := s.t13, v3 := s.t14, v4 := s.t15, v5 := s.t16, v6 := s.t17, v7 := s.t18 } : State_matrix_block)) ((fun value => match value with | .fn_matrix_block result => (Frame.fn_matrix_block 2 { s with t10 := result }) | _ => .invalid) :: stack))
| matrix_block_pc4 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 4 s) stack) (.active h (Frame.fn_matrix_block 3 { s with t18 := s.v8 }) stack)
| matrix_block_pc5 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 5 s) stack) (.active h (Frame.fn_matrix_block 4 { s with t17 := (s.v6 + s.v8) }) stack)
| matrix_block_pc6 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 6 s) stack) (.active h (Frame.fn_matrix_block 5 { s with t16 := (s.v5 + s.v8) }) stack)
| matrix_block_pc7 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 7 s) stack) (.active h (Frame.fn_matrix_block 6 { s with t15 := (s.v4 + s.v8) }) stack)
| matrix_block_pc8 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 8 s) stack) (.active h (Frame.fn_matrix_block 7 { s with t14 := s.v3 }) stack)
| matrix_block_pc9 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 9 s) stack) (.active h (Frame.fn_matrix_block 8 { s with t13 := s.v2 }) stack)
| matrix_block_pc10 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 10 s) stack) (.active h (Frame.fn_matrix_block 9 { s with t12 := s.v1 }) stack)
| matrix_block_pc11 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 11 s) stack) (.active h (Frame.fn_matrix_block 10 { s with t11 := s.v0 }) stack)
| matrix_block_pc12 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 12 s) stack) (.active h (Frame.fn_matrix_block 82 ({ v0 := s.t20, v1 := s.t21, v2 := s.t22, v3 := s.t23, v4 := s.t24, v5 := s.t25, v6 := s.t26, v7 := s.t27 } : State_matrix_block)) ((fun value => match value with | .fn_matrix_block result => (Frame.fn_matrix_block 11 { s with t19 := result }) | _ => .invalid) :: stack))
| matrix_block_pc13 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 13 s) stack) (.active h (Frame.fn_matrix_block 12 { s with t27 := s.v8 }) stack)
| matrix_block_pc14 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 14 s) stack) (.active h (Frame.fn_matrix_block 13 { s with t26 := s.v6 }) stack)
| matrix_block_pc15 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 15 s) stack) (.active h (Frame.fn_matrix_block 14 { s with t25 := (s.v5 + s.v8) }) stack)
| matrix_block_pc16 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 16 s) stack) (.active h (Frame.fn_matrix_block 15 { s with t24 := (s.v4 + s.v8) }) stack)
| matrix_block_pc17 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 17 s) stack) (.active h (Frame.fn_matrix_block 16 { s with t23 := s.v3 }) stack)
| matrix_block_pc18 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 18 s) stack) (.active h (Frame.fn_matrix_block 17 { s with t22 := s.v2 }) stack)
| matrix_block_pc19 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 19 s) stack) (.active h (Frame.fn_matrix_block 18 { s with t21 := s.v1 }) stack)
| matrix_block_pc20 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 20 s) stack) (.active h (Frame.fn_matrix_block 19 { s with t20 := s.v0 }) stack)
| matrix_block_pc21 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 21 s) stack) (.active h (Frame.fn_matrix_block 82 ({ v0 := s.t29, v1 := s.t30, v2 := s.t31, v3 := s.t32, v4 := s.t33, v5 := s.t34, v6 := s.t35, v7 := s.t36 } : State_matrix_block)) ((fun value => match value with | .fn_matrix_block result => (Frame.fn_matrix_block 20 { s with t28 := result }) | _ => .invalid) :: stack))
| matrix_block_pc22 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 22 s) stack) (.active h (Frame.fn_matrix_block 21 { s with t36 := s.v8 }) stack)
| matrix_block_pc23 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 23 s) stack) (.active h (Frame.fn_matrix_block 22 { s with t35 := (s.v6 + s.v8) }) stack)
| matrix_block_pc24 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 24 s) stack) (.active h (Frame.fn_matrix_block 23 { s with t34 := s.v5 }) stack)
| matrix_block_pc25 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 25 s) stack) (.active h (Frame.fn_matrix_block 24 { s with t33 := (s.v4 + s.v8) }) stack)
| matrix_block_pc26 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 26 s) stack) (.active h (Frame.fn_matrix_block 25 { s with t32 := s.v3 }) stack)
| matrix_block_pc27 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 27 s) stack) (.active h (Frame.fn_matrix_block 26 { s with t31 := s.v2 }) stack)
| matrix_block_pc28 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 28 s) stack) (.active h (Frame.fn_matrix_block 27 { s with t30 := s.v1 }) stack)
| matrix_block_pc29 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 29 s) stack) (.active h (Frame.fn_matrix_block 28 { s with t29 := s.v0 }) stack)
| matrix_block_pc30 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 30 s) stack) (.active h (Frame.fn_matrix_block 82 ({ v0 := s.t38, v1 := s.t39, v2 := s.t40, v3 := s.t41, v4 := s.t42, v5 := s.t43, v6 := s.t44, v7 := s.t45 } : State_matrix_block)) ((fun value => match value with | .fn_matrix_block result => (Frame.fn_matrix_block 29 { s with t37 := result }) | _ => .invalid) :: stack))
| matrix_block_pc31 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 31 s) stack) (.active h (Frame.fn_matrix_block 30 { s with t45 := s.v8 }) stack)
| matrix_block_pc32 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 32 s) stack) (.active h (Frame.fn_matrix_block 31 { s with t44 := s.v6 }) stack)
| matrix_block_pc33 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 33 s) stack) (.active h (Frame.fn_matrix_block 32 { s with t43 := s.v5 }) stack)
| matrix_block_pc34 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 34 s) stack) (.active h (Frame.fn_matrix_block 33 { s with t42 := (s.v4 + s.v8) }) stack)
| matrix_block_pc35 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 35 s) stack) (.active h (Frame.fn_matrix_block 34 { s with t41 := s.v3 }) stack)
| matrix_block_pc36 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 36 s) stack) (.active h (Frame.fn_matrix_block 35 { s with t40 := s.v2 }) stack)
| matrix_block_pc37 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 37 s) stack) (.active h (Frame.fn_matrix_block 36 { s with t39 := s.v1 }) stack)
| matrix_block_pc38 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 38 s) stack) (.active h (Frame.fn_matrix_block 37 { s with t38 := s.v0 }) stack)
| matrix_block_pc39 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 39 s) stack) (.active h (Frame.fn_matrix_block 82 ({ v0 := s.t47, v1 := s.t48, v2 := s.t49, v3 := s.t50, v4 := s.t51, v5 := s.t52, v6 := s.t53, v7 := s.t54 } : State_matrix_block)) ((fun value => match value with | .fn_matrix_block result => (Frame.fn_matrix_block 38 { s with t46 := result }) | _ => .invalid) :: stack))
| matrix_block_pc40 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 40 s) stack) (.active h (Frame.fn_matrix_block 39 { s with t54 := s.v8 }) stack)
| matrix_block_pc41 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 41 s) stack) (.active h (Frame.fn_matrix_block 40 { s with t53 := (s.v6 + s.v8) }) stack)
| matrix_block_pc42 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 42 s) stack) (.active h (Frame.fn_matrix_block 41 { s with t52 := (s.v5 + s.v8) }) stack)
| matrix_block_pc43 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 43 s) stack) (.active h (Frame.fn_matrix_block 42 { s with t51 := s.v4 }) stack)
| matrix_block_pc44 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 44 s) stack) (.active h (Frame.fn_matrix_block 43 { s with t50 := s.v3 }) stack)
| matrix_block_pc45 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 45 s) stack) (.active h (Frame.fn_matrix_block 44 { s with t49 := s.v2 }) stack)
| matrix_block_pc46 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 46 s) stack) (.active h (Frame.fn_matrix_block 45 { s with t48 := s.v1 }) stack)
| matrix_block_pc47 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 47 s) stack) (.active h (Frame.fn_matrix_block 46 { s with t47 := s.v0 }) stack)
| matrix_block_pc48 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 48 s) stack) (.active h (Frame.fn_matrix_block 82 ({ v0 := s.t56, v1 := s.t57, v2 := s.t58, v3 := s.t59, v4 := s.t60, v5 := s.t61, v6 := s.t62, v7 := s.t63 } : State_matrix_block)) ((fun value => match value with | .fn_matrix_block result => (Frame.fn_matrix_block 47 { s with t55 := result }) | _ => .invalid) :: stack))
| matrix_block_pc49 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 49 s) stack) (.active h (Frame.fn_matrix_block 48 { s with t63 := s.v8 }) stack)
| matrix_block_pc50 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 50 s) stack) (.active h (Frame.fn_matrix_block 49 { s with t62 := s.v6 }) stack)
| matrix_block_pc51 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 51 s) stack) (.active h (Frame.fn_matrix_block 50 { s with t61 := (s.v5 + s.v8) }) stack)
| matrix_block_pc52 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 52 s) stack) (.active h (Frame.fn_matrix_block 51 { s with t60 := s.v4 }) stack)
| matrix_block_pc53 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 53 s) stack) (.active h (Frame.fn_matrix_block 52 { s with t59 := s.v3 }) stack)
| matrix_block_pc54 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 54 s) stack) (.active h (Frame.fn_matrix_block 53 { s with t58 := s.v2 }) stack)
| matrix_block_pc55 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 55 s) stack) (.active h (Frame.fn_matrix_block 54 { s with t57 := s.v1 }) stack)
| matrix_block_pc56 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 56 s) stack) (.active h (Frame.fn_matrix_block 55 { s with t56 := s.v0 }) stack)
| matrix_block_pc57 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 57 s) stack) (.active h (Frame.fn_matrix_block 82 ({ v0 := s.t65, v1 := s.t66, v2 := s.t67, v3 := s.t68, v4 := s.t69, v5 := s.t70, v6 := s.t71, v7 := s.t72 } : State_matrix_block)) ((fun value => match value with | .fn_matrix_block result => (Frame.fn_matrix_block 56 { s with t64 := result }) | _ => .invalid) :: stack))
| matrix_block_pc58 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 58 s) stack) (.active h (Frame.fn_matrix_block 57 { s with t72 := s.v8 }) stack)
| matrix_block_pc59 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 59 s) stack) (.active h (Frame.fn_matrix_block 58 { s with t71 := (s.v6 + s.v8) }) stack)
| matrix_block_pc60 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 60 s) stack) (.active h (Frame.fn_matrix_block 59 { s with t70 := s.v5 }) stack)
| matrix_block_pc61 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 61 s) stack) (.active h (Frame.fn_matrix_block 60 { s with t69 := s.v4 }) stack)
| matrix_block_pc62 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 62 s) stack) (.active h (Frame.fn_matrix_block 61 { s with t68 := s.v3 }) stack)
| matrix_block_pc63 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 63 s) stack) (.active h (Frame.fn_matrix_block 62 { s with t67 := s.v2 }) stack)
| matrix_block_pc64 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 64 s) stack) (.active h (Frame.fn_matrix_block 63 { s with t66 := s.v1 }) stack)
| matrix_block_pc65 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 65 s) stack) (.active h (Frame.fn_matrix_block 64 { s with t65 := s.v0 }) stack)
| matrix_block_pc66 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 66 s) stack) (.active h (Frame.fn_matrix_block 82 ({ v0 := s.t74, v1 := s.t75, v2 := s.t76, v3 := s.t77, v4 := s.t78, v5 := s.t79, v6 := s.t80, v7 := s.t81 } : State_matrix_block)) ((fun value => match value with | .fn_matrix_block result => (Frame.fn_matrix_block 65 { s with t73 := result }) | _ => .invalid) :: stack))
| matrix_block_pc67 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 67 s) stack) (.active h (Frame.fn_matrix_block 66 { s with t81 := s.v8 }) stack)
| matrix_block_pc68 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 68 s) stack) (.active h (Frame.fn_matrix_block 67 { s with t80 := s.v6 }) stack)
| matrix_block_pc69 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 69 s) stack) (.active h (Frame.fn_matrix_block 68 { s with t79 := s.v5 }) stack)
| matrix_block_pc70 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 70 s) stack) (.active h (Frame.fn_matrix_block 69 { s with t78 := s.v4 }) stack)
| matrix_block_pc71 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 71 s) stack) (.active h (Frame.fn_matrix_block 70 { s with t77 := s.v3 }) stack)
| matrix_block_pc72 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 72 s) stack) (.active h (Frame.fn_matrix_block 71 { s with t76 := s.v2 }) stack)
| matrix_block_pc73 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 73 s) stack) (.active h (Frame.fn_matrix_block 72 { s with t75 := s.v1 }) stack)
| matrix_block_pc74 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 74 s) stack) (.active h (Frame.fn_matrix_block 73 { s with t74 := s.v0 }) stack)
| matrix_block_pc75 (h : Heap) (s : State_matrix_block) (stack : Stack) (defined : ((2 : Int) ≠ 0)) :
Step (.active h (Frame.fn_matrix_block 75 s) stack) (.active h (Frame.fn_matrix_block 74 { s with v8 := (Int.fdiv s.v7 (2 : Int)) }) stack)
| matrix_block_pc76 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 76 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_matrix_block (s.t83)) stack)
| matrix_block_pc77 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 77 s) stack) (.active h (Frame.fn_matrix_block 76 { s with t83 := (0 : Int) }) stack)
| matrix_block_pc78 (h : Heap) (s : State_matrix_block) (stack : Stack) (defined : ((((((seq_Seq_Int.get h s.v2 s.v4).isSome = true)) ∧ (((seq_Seq_Int.get h s.v2 s.v4).getD 0) < h.nextRef)) ∧ (((((seq_Seq_Int.get h s.v0 s.v4).isSome = true)) ∧ (((seq_Seq_Int.get h s.v0 s.v4).getD 0) < h.nextRef)) ∧ ((((seq_Seq_Int.get h s.v1 s.v6).isSome = true)) ∧ (((seq_Seq_Int.get h s.v1 s.v6).getD 0) < h.nextRef)))) ∧ (((seq_Seq_Int.get h s.v2 s.v4).isSome = true))) ∧ (((seq_Seq_Int.get h s.v2 s.v4).getD 0) < h.nextRef)) :
Step (.active h (Frame.fn_matrix_block 78 s) stack) (.active (h.write ((seq_Seq_Int.get h s.v2 s.v4).getD 0) s.v5 ((h.read ((seq_Seq_Int.get h s.v2 s.v4).getD 0) s.v5) + ((h.read ((seq_Seq_Int.get h s.v0 s.v4).getD 0) s.v6) * (h.read ((seq_Seq_Int.get h s.v1 s.v6).getD 0) s.v5)))) (Frame.fn_matrix_block 77 s) stack)
| matrix_block_pc79 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 79 s) stack) (.active (h.tick "multiplications" 1) (Frame.fn_matrix_block 78 s) stack)
| matrix_block_pc80_true (h : Heap) (s : State_matrix_block) (stack : Stack) (condition : s.t82 = true) :
Step (.active h (Frame.fn_matrix_block 80 s) stack) (.active h (Frame.fn_matrix_block 79 s) stack)
| matrix_block_pc80_false (h : Heap) (s : State_matrix_block) (stack : Stack) (condition : s.t82 = false) :
Step (.active h (Frame.fn_matrix_block 80 s) stack) (.active h (Frame.fn_matrix_block 75 s) stack)
| matrix_block_pc81 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 81 s) stack) (.active h (Frame.fn_matrix_block 80 { s with t82 := (decide ((s.v7 ≤ (1 : Int)))) }) stack)
| matrix_block_pc82 (h : Heap) (s : State_matrix_block) (stack : Stack) :
Step (.active h (Frame.fn_matrix_block 82 s) stack) (.active (h.tick "calls" 1) (Frame.fn_matrix_block 81 s) stack)
| matrix_recursive_pc1 (h : Heap) (s : State_matrix_recursive) (stack : Stack) (defined : seq_Seq_Int.valid h s.t5) :
Step (.active h (Frame.fn_matrix_recursive 1 s) stack) (Algo2LeanCore.resumeConfig h (Result.fn_matrix_recursive (s.t5)) stack)
| matrix_recursive_pc2 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 2 s) stack) (.active h (Frame.fn_matrix_recursive 1 { s with t5 := s.v3 }) stack)
| matrix_recursive_pc3 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 3 s) stack) (.active h (Frame.fn_matrix_block 82 ({ v0 := s.t7, v1 := s.t8, v2 := s.t9, v3 := s.t10, v4 := s.t11, v5 := s.t12, v6 := s.t13, v7 := s.t14 } : State_matrix_block)) ((fun value => match value with | .fn_matrix_block result => (Frame.fn_matrix_recursive 2 { s with t6 := result }) | _ => .invalid) :: stack))
| matrix_recursive_pc4 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 4 s) stack) (.active h (Frame.fn_matrix_recursive 3 { s with t14 := s.v2 }) stack)
| matrix_recursive_pc5 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 5 s) stack) (.active h (Frame.fn_matrix_recursive 4 { s with t13 := (0 : Int) }) stack)
| matrix_recursive_pc6 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 6 s) stack) (.active h (Frame.fn_matrix_recursive 5 { s with t12 := (0 : Int) }) stack)
| matrix_recursive_pc7 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 7 s) stack) (.active h (Frame.fn_matrix_recursive 6 { s with t11 := (0 : Int) }) stack)
| matrix_recursive_pc8 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 8 s) stack) (.active h (Frame.fn_matrix_recursive 7 { s with t10 := s.v2 }) stack)
| matrix_recursive_pc9 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 9 s) stack) (.active h (Frame.fn_matrix_recursive 8 { s with t9 := s.v3 }) stack)
| matrix_recursive_pc10 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 10 s) stack) (.active h (Frame.fn_matrix_recursive 9 { s with t8 := s.v1 }) stack)
| matrix_recursive_pc11 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 11 s) stack) (.active h (Frame.fn_matrix_recursive 10 { s with t7 := s.v0 }) stack)
| matrix_recursive_pc12_true (h : Heap) (s : State_matrix_recursive) (stack : Stack) (condition : s.t15 = true) :
Step (.active h (Frame.fn_matrix_recursive 12 s) stack) (.active h (Frame.fn_matrix_recursive 19 s) stack)
| matrix_recursive_pc12_false (h : Heap) (s : State_matrix_recursive) (stack : Stack) (condition : s.t15 = false) :
Step (.active h (Frame.fn_matrix_recursive 12 s) stack) (.active h (Frame.fn_matrix_recursive 11 s) stack)
| matrix_recursive_pc13 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 13 s) stack) (.active h (Frame.fn_matrix_recursive 12 { s with t15 := (decide ((s.v4 < s.v2))) }) stack)
| matrix_recursive_pc14 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 14 s) stack) (.active h (Frame.fn_matrix_recursive 13 { s with v4 := (s.v4 + (1 : Int)) }) stack)
| matrix_recursive_pc15 (h : Heap) (s : State_matrix_recursive) (stack : Stack) (defined : (seq_Seq_Int.valid h s.t18)) :
Step (.active h (Frame.fn_matrix_recursive 15 s) stack) (.active (seq_Seq_Int.set h s.t18 s.t17 s.t16) (Frame.fn_matrix_recursive 14 s) stack)
| matrix_recursive_pc16 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 16 s) stack) (.active h (Frame.fn_matrix_recursive 15 { s with t17 := s.v4 }) stack)
| matrix_recursive_pc17 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 17 s) stack) (.active h (Frame.fn_matrix_recursive 16 { s with t18 := s.v3 }) stack)
| matrix_recursive_pc18 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 18 s) stack) (.active (h.allocate (fun _ => s.t19)) (Frame.fn_matrix_recursive 17 { s with t16 := h.nextRef }) stack)
| matrix_recursive_pc19 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 19 s) stack) (.active h (Frame.fn_matrix_recursive 18 { s with t19 := (0 : Int) }) stack)
| matrix_recursive_pc20 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 20 s) stack) (.active h (Frame.fn_matrix_recursive 13 { s with v4 := (0 : Int) }) stack)
| matrix_recursive_pc21 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 21 s) stack) (.active h (Frame.fn_matrix_recursive 20 { s with v3 := s.t20 }) stack)
| matrix_recursive_pc22 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 22 s) stack) (.active (seq_Seq_Int.const h s.t21).1 (Frame.fn_matrix_recursive 21 { s with t20 := h.nextCollection }) stack)
| matrix_recursive_pc23 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 23 s) stack) (.active (h.allocate (fun _ => s.t22)) (Frame.fn_matrix_recursive 22 { s with t21 := h.nextRef }) stack)
| matrix_recursive_pc24 (h : Heap) (s : State_matrix_recursive) (stack : Stack) :
Step (.active h (Frame.fn_matrix_recursive 24 s) stack) (.active h (Frame.fn_matrix_recursive 23 { s with t22 := (0 : Int) }) stack)
end Algo2LeanGenerated
open Algo2LeanGenerated
def matrix_block.ValidInput (h : Heap) (input : CollectionRef × CollectionRef × CollectionRef × Int × Int × Int × Int × Int) : Prop := seq_Seq_Int.valid h input.1 ∧ seq_Seq_Int.valid h input.2.1 ∧ seq_Seq_Int.valid h input.2.2.1
def matrix_block.Call (h : Heap) (input : CollectionRef × CollectionRef × CollectionRef × Int × Int × Int × Int × Int) (h' : Heap) (output : Int) : Prop :=
_root_.CLRS.MatrixRecursiveLibrary.matrix_block.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_matrix_block 82 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2.1, v3 := input.2.2.2.1, v4 := input.2.2.2.2.1, v5 := input.2.2.2.2.2.1, v6 := input.2.2.2.2.2.2.1, v7 := input.2.2.2.2.2.2.2 } : State_matrix_block)) h' (Result.fn_matrix_block output)
-- Complete this function from the supplied local state, under any caller stack.
-- Object inputs carry their heap, preserving shared references and cycles.
-- Output and clock increments from one completed execution.
def matrix_recursive.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_recursive.initial (h : Heap) (input : CollectionRef × CollectionRef × Int) : Configuration :=
Algo2LeanCore.start h (Frame.fn_matrix_recursive 24 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2 } : State_matrix_recursive))
def matrix_recursive.Run (h : Heap) (input : CollectionRef × CollectionRef × Int) (h' : Heap) (output : CollectionRef) : Prop :=
_root_.CLRS.MatrixRecursiveLibrary.matrix_recursive.ValidInput h input ∧ Algo2LeanCore.Reaches Step (_root_.CLRS.MatrixRecursiveLibrary.matrix_recursive.initial h input) (.done h' (Result.fn_matrix_recursive output))
def matrix_recursive.Call (h : Heap) (input : CollectionRef × CollectionRef × Int) (h' : Heap) (output : CollectionRef) : Prop :=
_root_.CLRS.MatrixRecursiveLibrary.matrix_recursive.ValidInput h input ∧ Algo2LeanCore.Summary Step h (Frame.fn_matrix_recursive 24 ({ v0 := input.1, v1 := input.2.1, v2 := input.2.2 } : State_matrix_recursive)) h' (Result.fn_matrix_recursive output)
-- Complete this function from the supplied local state, under any caller stack.
-- Object inputs carry their heap, preserving shared references and cycles.
def matrix_recursive.load (input : Heap × (CollectionRef × CollectionRef × Int)) : Heap × (CollectionRef × CollectionRef × Int) := input
def matrix_recursive.Returns (my_input : Heap × (CollectionRef × CollectionRef × Int)) (my_output : Heap × (CollectionRef)) : Prop :=
let loaded := _root_.CLRS.MatrixRecursiveLibrary.matrix_recursive.load my_input
_root_.CLRS.MatrixRecursiveLibrary.matrix_recursive.Run loaded.1 loaded.2 my_output.1 my_output.2
-- Output and clock increments from one completed execution.
def matrix_recursive.ReturnsWithCost (my_input : Heap × (CollectionRef × CollectionRef × Int)) (my_output : Heap × (CollectionRef)) (costs : Clocks) : Prop :=
let loaded := _root_.CLRS.MatrixRecursiveLibrary.matrix_recursive.load my_input
_root_.CLRS.MatrixRecursiveLibrary.matrix_recursive.Run loaded.1 loaded.2 my_output.1 my_output.2 ∧ Heap.cost loaded.1 my_output.1 = costs
end «MatrixRecursiveLibrary»
end CLRS