1	import Base
2	import ../kernel_block.bend as Block
3	import ../kernel_tile.bend as Tile
4	import ./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.
8	def 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	
21	def 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	
29	def 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	
38	def 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	
48	def 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	
60	def 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	
74	def 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))