Evaluating Combinators as List Manipulations
Evaluating Combinators as List Manipulations
By Eric James Parfitt
Code
Code
The Project
The Project
I’ve been interested in how things that higher level languages can do, such as implementing functions that can input and output other functions, can be build up from a more lower level language. SK combinators can be a bridge from being able to implement these kinds of functions and something lower level. mainly here then I’ve been trying to make a bridge between “functional” programming languages that can move functions around, which is represented by SK combinators, and a lower level “imperative” language that just does one kind of step at a time.
I’ve imagined the the SK combinator expressions to be directed acyclic graphs(DAGs), so that multiple parts of a combinator can point back at one shared part. I’ve turned the DAG into a list of pairs, where the left element of each pair points to a left branch, and the right element to a right branch. Then there’s an integer that points to each pair that essentially keeps track of how many other pairs are pointing to it, which when it reaches zero means that part of the expression is deleted. Then there are lots of rules for following along the DAG to find the first part that matches one of the combinator rules, and then rules for shuffling around the pointers to implement the rewrite rules for the combinators.
Anyway, it works. Here’s the list shuffling:
I’ve imagined the the SK combinator expressions to be directed acyclic graphs(DAGs), so that multiple parts of a combinator can point back at one shared part. I’ve turned the DAG into a list of pairs, where the left element of each pair points to a left branch, and the right element to a right branch. Then there’s an integer that points to each pair that essentially keeps track of how many other pairs are pointing to it, which when it reaches zero means that part of the expression is deleted. Then there are lots of rules for following along the DAG to find the first part that matches one of the combinator rules, and then rules for shuffling around the pointers to implement the rewrite rules for the combinators.
Anyway, it works. Here’s the list shuffling:
In[]:=
evolution=evaluateFixedPointList[toCounterPointered@s[s[s[s]][s][s][s][k]],12];
In[]:=
Grid[evolution,Frame->All]
Out[]=
1{s,2} | 1{3,k} | 1{4,s} | 1{5,s} | 1{6,s} | 1{s,7} | 1{s,s} | | | | | |
1{s,2} | 1{3,k} | 1{4,s} | 1{5,6} | 1{7,s} | 1{s,s} | 1{s,s} | | | | | |
1{s,2} | 1{3,k} | 1{4,s} | 1{5,7} | 1{s,6} | 2{s,s} | 1{s,6} | | | | | |
1{s,2} | 1{3,k} | 1{4,5} | 1{6,s} | 1{7,s} | 2{s,s} | 1{s,6} | | | | | |
1{s,2} | 1{3,k} | 1{4,8} | 1{s,5} | 2{7,s} | 1{s,s} | 1{s,6} | 1{s,5} | | | | |
1{s,2} | 1{3,4} | 1{5,k} | 1{8,k} | 2{7,s} | 1{s,s} | 1{s,6} | 1{s,5} | | | | |
1{s,2} | 1{3,4} | 1{9,10} | 1{8,k} | 1{7,s} | 2{s,s} | 1{s,6} | 1{s,5} | 1{6,k} | 1{s,k} | | |
1{s,2} | 1{3,4} | 1{9,11} | 1{8,k} | 1{7,s} | 1{s,s} | 1{s,6} | 1{s,5} | 1{s,10} | 2{s,k} | 1{k,10} | |
1{s,2} | 1{3,9} | 1{10,4} | 2{8,k} | 1{7,s} | 1{s,s} | 1{s,6} | 1{s,5} | 1{11,4} | 2{s,k} | 1{k,10} | |
1{s,2} | 1{3,12} | 1{k,9} | 2{8,k} | 1{7,s} | 1{s,s} | 1{s,6} | 1{s,5} | 2{11,4} | 1{s,k} | 1{k,10} | 1{4,9} |
1{s,9} | {} | {} | 1{8,k} | 1{7,s} | 1{s,s} | 1{s,6} | 1{s,5} | 1{11,4} | 1{s,k} | 1{k,10} | {} |
1{s,10} | {} | {} | {} | {} | {} | {} | {} | {} | 1{s,k} | {} | {} |
1{s,10} | {} | {} | {} | {} | {} | {} | {} | {} | 1{s,k} | {} | {} |
Which can then be interpreted as SK combinators evaluating. This is the correct evaluation of that combinator:
In[]:=
toComb/@evolution//Column
Out[]=
s[s[s[s]][s][s][s][k]] |
s[s[s][s][s[s]][s][k]] |
s[s[s[s]][s[s[s]]][s][k]] |
s[s[s][s][s[s[s]][s]][k]] |
s[s[s[s[s]][s]][s[s[s[s]][s]]][k]] |
s[s[s[s]][s][k][s[s[s[s]][s]][k]]] |
s[s[s][k][s[k]][s[s[s[s]][s]][k]]] |
s[s[s[k]][k[s[k]]][s[s[s[s]][s]][k]]] |
s[s[k][s[s[s[s]][s]][k]][k[s[k]][s[s[s[s]][s]][k]]]] |
s[k[k[s[k]][s[s[s[s]][s]][k]]][s[s[s[s]][s]][k][k[s[k]][s[s[s[s]][s]][k]]]]] |
s[k[s[k]][s[s[s[s]][s]][k]]] |
s[s[k]] |
s[s[k]] |