abstraction_binding_model.py (6226B)
1 """Independent finite model of stable abstraction, for attribution not timing. 2 3 Literal trees are interned DAG IDs. This is NOT a replacement runtime: final 4 normalization is eager and used only for the finite compiled function controls. 5 """ 6 from collections import Counter 7 from dataclasses import dataclass 8 9 10 def var(name): return ('var',name) 11 def call(f,*args): 12 for a in args: f=('app',f,a) 13 return f 14 15 def lam(name,body): return ('lam',name,body) 16 def let(name,value,body): return call(lam(name,body),value) 17 18 def source(expr): 19 kind=expr[0] 20 if kind=='var': return expr[1] 21 if kind=='app': return '('+source(expr[1])+' '+source(expr[2])+')' 22 if kind=='lam': return '('+expr[1]+' : '+source(expr[2])+')' 23 raise ValueError(expr) 24 25 26 def programs(): 27 x,f,z=map(var,['x','flag','z']) 28 leaf=var('t') 29 neg=call(var('negate'),x) 30 cons=lambda a,b:call(leaf,a,b) 31 choose=lambda a,b:call(var('choose'),a,b,f) 32 wrap=lambda body:lam('flag',lam('x',body)) 33 bodies={ 34 'etaExpanded':lam('f',lam('arg',call(var('f'),var('arg')))), 35 'etaContracted':lam('f',var('f')), 36 'singleBound':wrap(let('z',neg,cons(z,x))), 37 'singleInline':wrap(cons(neg,x)), 38 'branchBound':wrap(let('z',neg,choose(cons(z,x),cons(x,z)))), 39 'branchInline':wrap(choose(cons(neg,x),cons(x,neg))), 40 'constructorBound':wrap(let('z',call(leaf,x),choose(cons(z,x),cons(x,z)))), 41 'constructorInline':wrap(choose(cons(call(leaf,x),x),cons(x,call(leaf,x)))), 42 'sharedBound':lam('x',let('z',call(var('copy'),x),cons(z,z))), 43 'sharedInline':lam('x',cons(call(var('copy'),x),call(var('copy'),x))), 44 'closureBound':lam('x',let('z',call(var('loop'),x),lam('ignored',z))), 45 'closureInline':lam('x',lam('ignored',call(var('loop'),x))), 46 'unusedBound':lam('x',let('z',call(var('loop'),leaf),x)), 47 'unusedInline':lam('x',x), 48 'closedBranchBound':lam('flag',let('z',call(var('loop'),leaf),choose(z,leaf))), 49 'closedBranchInline':lam('flag',choose(call(var('loop'),leaf),leaf)), 50 } 51 a,b,c=map(var,['abit','bbit','carry']) 52 select=lambda yes,no,flag:call(var('choose'),yes,no,flag) 53 carry=select(call(var('either'),b,c),call(var('both'),c,b),a) 54 def bit(neg): 55 return select(select(c,neg,b),select(neg,c,b),a) 56 wrap3=lambda body:lam('abit',lam('bbit',lam('carry',body))) 57 bodies['adderBound']=wrap3(let('z',call(var('negate'),c),cons(bit(z),carry))) 58 bodies['adderInline']=wrap3(cons(bit(call(var('negate'),c)),carry)) 59 return bodies 60 61 62 @dataclass(frozen=True) 63 class Term: 64 kind: int 65 value: object 66 shape: int 67 bound: int 68 69 70 class Model: 71 def __init__(self,intern,globals): 72 self.intern=intern 73 self.globals=globals 74 self.stats=Counter() 75 self.leaf=intern.node((0,)) 76 self.k=intern.node((1,self.leaf)) 77 self.i=intern.node((2,intern.node((1,self.k)),self.leaf)) 78 self.brackets=[] 79 80 def literal(self,tree): 81 return Term(1,tree,self.intern.nodes[tree][0]+1,0) 82 83 def variable(self,index): return Term(2,index,4,index+1) 84 85 def raw(self,f,x): 86 bound=min([n for n in [f.bound,x.bound] if n] or [0]) 87 shape=f.shape+1 if f.shape in [1,2] and x.shape else 0 88 return Term(3,(f,x),shape,bound) 89 90 def apply(self,f,x): 91 if f.kind==x.kind==1: 92 tree=self.intern.nodes[f.value] 93 if tree[0]==0: 94 self.stats['literal_leaf_fold']+=1 95 return self.literal(self.intern.node((1,x.value))) 96 if tree[0]==1: 97 self.stats['literal_stem_fold']+=1 98 return self.literal(self.intern.node((2,tree[1],x.value))) 99 return self.raw(f,x) 100 101 def lower(self,t): 102 if not t.bound:return t 103 if t.kind==2:return self.variable(t.value-1) 104 if t.kind==3:return Term(3,tuple(self.lower(c) for c in t.value),t.shape,t.bound-1) 105 return t 106 107 def bracket(self,t): 108 if t.kind==1: 109 self.stats['literal_K']+=1 110 return self.apply(self.literal(self.k),t) 111 if t.kind==2: 112 if t.value==0: 113 self.stats['identity']+=1 114 return self.literal(self.i) 115 self.stats['variable_K']+=1 116 return self.apply(self.literal(self.k),self.variable(t.value-1)) 117 if t.kind==3: 118 if t.bound!=1 and t.shape: 119 self.stats['constructor_K']+=1 120 return self.apply(self.literal(self.k),self.lower(t)) 121 key='independent_computation_distribution' if t.bound!=1 else 'dependent_distribution' 122 self.stats[key]+=1 123 left,right=map(self.bracket,t.value) 124 return self.apply(self.apply(self.literal(self.leaf),self.apply(self.literal(self.leaf),left)),right) 125 raise ValueError(t) 126 127 def eliminate(self,expr,stack=()): 128 kind=expr[0] 129 if kind=='var': 130 name=expr[1] 131 if name in stack:return self.variable(stack.index(name)) 132 return self.literal(self.leaf if name=='t' else self.globals[name]) 133 if kind=='app':return self.apply(self.eliminate(expr[1],stack),self.eliminate(expr[2],stack)) 134 if kind=='lam': 135 body=self.eliminate(expr[2],(expr[1],)+stack) 136 before=self.stats.copy() 137 result=self.bracket(body) 138 self.brackets.append(dict(binder=expr[1],counts=dict(self.stats-before))) 139 return result 140 raise ValueError(expr) 141 142 def tree_apply(self,f,x): 143 a=self.intern.nodes[f] 144 if a[0]==0:return self.intern.node((1,x)) 145 if a[0]==1:return self.intern.node((2,a[1],x)) 146 p=self.intern.nodes[a[1]] 147 if p[0]==0:return a[2] 148 if p[0]==1:return self.tree_apply(self.tree_apply(p[1],x),self.tree_apply(a[2],x)) 149 q=self.intern.nodes[x] 150 if q[0]==0:return p[1] 151 if q[0]==1:return self.tree_apply(p[2],q[1]) 152 return self.tree_apply(self.tree_apply(a[2],q[1]),q[2]) 153 154 def run(self,t): 155 if t.kind==1:return t.value 156 if t.kind==3:return self.tree_apply(self.run(t.value[0]),self.run(t.value[1])) 157 raise ValueError('unbound residual') 158 159 def compile(self,expr):return self.run(self.eliminate(expr))