proofs/kernel_tile_witness.bend

stelliferous@0.0.2.0 · 86 lines · 7 definitions

1import Base
2import stelliferous@0.0.2.0/kernel_block.bend as Block
3import stelliferous@0.0.2.0/kernel_tile.bend as Tile
4import stelliferous@0.0.2.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))