proofs/kernel_tile_witness.bend
stelliferous@0.0.3.0 · 86 lines · 0 definitions
1import Base
2import stelliferous@0.0.3.0/kernel_block.bend as Block
3import stelliferous@0.0.3.0/kernel_tile.bend as Tile
4import stelliferous@0.0.3.0/proofs/traversal_witness.bend as TraversalWitness
5
6# Pair composition consumes already established observations. Context and
7# values may be erased, so a cached head need not become a live proof field.
8def pair(~State: Type,~Context: Data,~Element: Data,~read: State -> Context -> Nat -> State & Element,~stride: Nat,
9 -state: State,-context: Context,+index: Nat,
10 first: TraversalWitness.Sample<State,Element,state,read(state,context,index)>,
11 second: TraversalWitness.Sample<State,Element,state,read(state,context,Nat.add(index,stride))>) ->
12 TraversalWitness.Sample<State,Block.Twin<Element>,state,Block.read_pair(~State,~Context,~Element,~read,~stride,state,context,index)>:
13 TraversalWitness.Sample{left,left_equation} = first
14 TraversalWitness.Sample{right,right_equation} = second
15 %Equal.sym(State & Element,read(state,context,index),(state,left),left_equation) :
16 TraversalWitness.Sample<State,Block.Twin<Element>,state,Block.read_second(~State,~Context,~Element,~Nat,~read,_,context,Nat.add(index,stride))>
17 %Equal.sym(State & Element,read(state,context,Nat.add(index,stride)),(state,right),right_equation) :
18 TraversalWitness.Sample<State,Block.Twin<Element>,state,Block.finish_pair(~State,~Element,left,_)>
19 TraversalWitness.Sample{Block.Twin{left,right},{==}}
20
21def finish(~State: Type,-state: State,-result: State & Block.Twin<Block.Twin<Block.Twin<F32>>>,
22 evidence: TraversalWitness.Sample<State,Block.Twin<Block.Twin<Block.Twin<F32>>>,state,result>) ->
23 TraversalWitness.Sample<State,Tile.Tile8,state,Tile.finish_pairs(~State,result)>:
24 TraversalWitness.Sample{value,equation} = evidence
25 %Equal.sym(State & Block.Twin<Block.Twin<Block.Twin<F32>>>,result,(state,value),equation) :
26 TraversalWitness.Sample<State,Tile.Tile8,state,Tile.finish_pairs(~State,_)>
27 TraversalWitness.Sample{Tile.pairs_value(value),{==}}
28
29def with_head(~State: Type,~Context: Data,~Evidence: @-state: State -> Data,
30 ~read: State -> Context -> Nat -> State & F32,
31 ~read_preserves: @-state: State -> @context: Context -> @index: Nat -> Evidence(state) -> TraversalWitness.Sample<State,F32,state,read(state,context,index)>,
32 -state: State,+context: Context,-head: F32,+index: Nat,evidence: Evidence(state)) ->
33 TraversalWitness.Sample<State,F32,state,Tile.read_with_head(~State,~Context,~read,state,Tile.HeadContext{head,context},index)>:
34 match index:
35 case 0n: TraversalWitness.Sample{head,{==}}
36 case 1n+rest: read_preserves(state,context,1n+rest,evidence)
37
38def pair_head(~State: Type,~Context: Data,~Evidence: @-state: State -> Data,
39 ~read: State -> Context -> Nat -> State & F32,
40 ~read_preserves: @-state: State -> @context: Context -> @index: Nat -> Evidence(state) -> TraversalWitness.Sample<State,F32,state,read(state,context,index)>,
41 -state: State,+context: Context,-head: F32,+index: Nat,+evidence: Evidence(state)) ->
42 TraversalWitness.Sample<State,Block.Twin<F32>,state,
43 Block.read_pair(~State,~Tile.HeadContext<Context>,~F32,~Tile.read_with_head(~State,~Context,~read),~1n,state,Tile.HeadContext{head,context},index)>:
44 pair(~State,~Tile.HeadContext<Context>,~F32,~Tile.read_with_head(~State,~Context,~read),~1n,state,Tile.HeadContext{head,context},index,
45 with_head(~State,~Context,~Evidence,~read,~read_preserves,state,context,head,index,evidence),
46 with_head(~State,~Context,~Evidence,~read,~read_preserves,state,context,head,Nat.add(index,1n),evidence))
47
48def four_head(~State: Type,~Context: Data,~Evidence: @-state: State -> Data,
49 ~read: State -> Context -> Nat -> State & F32,
50 ~read_preserves: @-state: State -> @context: Context -> @index: Nat -> Evidence(state) -> TraversalWitness.Sample<State,F32,state,read(state,context,index)>,
51 -state: State,+context: Context,-head: F32,+index: Nat,+evidence: Evidence(state)) ->
52 TraversalWitness.Sample<State,Block.Twin<Block.Twin<F32>>,state,
53 Block.read_pair(~State,~Tile.HeadContext<Context>,~Block.Twin<F32>,
54 ~Block.read_pair(~State,~Tile.HeadContext<Context>,~F32,~Tile.read_with_head(~State,~Context,~read),~1n),~2n,state,Tile.HeadContext{head,context},index)>:
55 pair(~State,~Tile.HeadContext<Context>,~Block.Twin<F32>,
56 ~Block.read_pair(~State,~Tile.HeadContext<Context>,~F32,~Tile.read_with_head(~State,~Context,~read),~1n),~2n,state,Tile.HeadContext{head,context},index,
57 pair_head(~State,~Context,~Evidence,~read,~read_preserves,state,context,head,index,evidence),
58 pair_head(~State,~Context,~Evidence,~read,~read_preserves,state,context,head,Nat.add(index,2n),evidence))
59
60def eight_head(~State: Type,~Context: Data,~Evidence: @-state: State -> Data,
61 ~read: State -> Context -> Nat -> State & F32,
62 ~read_preserves: @-state: State -> @context: Context -> @index: Nat -> Evidence(state) -> TraversalWitness.Sample<State,F32,state,read(state,context,index)>,
63 -state: State,+context: Context,-head: F32,+evidence: Evidence(state)) ->
64 TraversalWitness.Sample<State,Block.Twin<Block.Twin<Block.Twin<F32>>>,state,
65 Block.read_pair(~State,~Tile.HeadContext<Context>,~Block.Twin<Block.Twin<F32>>,
66 ~Block.read_pair(~State,~Tile.HeadContext<Context>,~Block.Twin<F32>,
67 ~Block.read_pair(~State,~Tile.HeadContext<Context>,~F32,~Tile.read_with_head(~State,~Context,~read),~1n),~2n),~4n,state,Tile.HeadContext{head,context},0n)>:
68 pair(~State,~Tile.HeadContext<Context>,~Block.Twin<Block.Twin<F32>>,
69 ~Block.read_pair(~State,~Tile.HeadContext<Context>,~Block.Twin<F32>,
70 ~Block.read_pair(~State,~Tile.HeadContext<Context>,~F32,~Tile.read_with_head(~State,~Context,~read),~1n),~2n),~4n,state,Tile.HeadContext{head,context},0n,
71 four_head(~State,~Context,~Evidence,~read,~read_preserves,state,context,head,0n,evidence),
72 four_head(~State,~Context,~Evidence,~read,~read_preserves,state,context,head,4n,evidence))
73
74def tail(~State: Type,~Context: Data,~Evidence: @-state: State -> Data,
75 ~read: State -> Context -> Nat -> State & F32,
76 ~read_preserves: @-state: State -> @context: Context -> @index: Nat -> Evidence(state) -> TraversalWitness.Sample<State,F32,state,read(state,context,index)>,
77 -state: State,+context: Context,-first: State & F32,evidence: Evidence(state),sample: TraversalWitness.Sample<State,F32,state,first>) ->
78 TraversalWitness.Sample<State,Tile.Tile8,state,Tile.read_tail(~State,~Context,~read,first,context)>:
79 TraversalWitness.Sample{head,equation} = sample
80 %Equal.sym(State & F32,first,(state,head),equation) :
81 TraversalWitness.Sample<State,Tile.Tile8,state,Tile.read_tail(~State,~Context,~read,_,context)>
82 finish(~State,state,
83 Block.read_pair(~State,~Tile.HeadContext<Context>,~Block.Twin<Block.Twin<F32>>,
84 ~Block.read_pair(~State,~Tile.HeadContext<Context>,~Block.Twin<F32>,
85 ~Block.read_pair(~State,~Tile.HeadContext<Context>,~F32,~Tile.read_with_head(~State,~Context,~read),~1n),~2n),~4n,state,Tile.HeadContext{head,context},0n),
86 eight_head(~State,~Context,~Evidence,~read,~read_preserves,state,context,head,evidence))