Rough Notes on the S combinator


I've been trying to understand the S combinator from combinatory logic and why it is so powerful:

Sxyz = (xz)(yz) 

That is , the functional result  xz  applied to the functional result yz  ( a combinator is "just" a function that takes other functions as arguments 
and returns a function as a result ..)

I always thought of this was  "substitution" function in some sense , but the inventor of combinators, Schoenfinkel ( a translation
of his 1924 paper appeared in "From Frege to Godel") called it the "fusion" operator. 

Why fusion ?? Well..

To get a clearer model, imagine we're trying to understand the operation of a computer. A computer ( like anything else ..)
is a just collection of states, s - we could be more precise and imagine s is a turing machine table AND its tape, or
just a block of bytes (RAM and/or disc) , ie a von neumann machine.

We can imagine looking at this blob of bytes and from it, somehow "projecting" out  some data, and also projecting out a "program"
After all, its _we_ who look at a magnetic core ( or ddr ram etc)  and  derive some meaning ( data) from it
and its we who deliberately engineer our machines to act in a certain way when their states are in  certain configurations ( ie to "follow" a program.)

So by "projection" i just mean the blob of state can be supplied as an argument to two kinds of functions:

	d: states -> data
	p: states -> program


Things of type program  act on data and produce more world state 
	
	program :: data -> states

This end state is fuel for further computation, of course ( that is, it in turn will be decomposed/projected into further program and data.)


we think of yz  (d)  as setting up the data given a world state z    :
		data =  yz


The value of (xz) is  "the program " 


In fact,  _all_ a von neumann machine does is work out the "next" thing to do, and the "next" thing to do  _this_ to ...


	
	"the program this world state generates " acting on "the data this world state represents"

is just

	(ps)(ds)

 ie we have an instance of our S schema:

	Spds


What this thought-experiment shows is that we can think of the action of any 
von neumann machine as just iterations of the S combinator. ( Of course the
devil is in the details - we need to work out the projection functions.)
What Schoenfinkel means by fusion is the fusion of function and argument in a 
double sense both argument and function are determined the same s, 
- both derive from the same thing, or have the same source - in this particular 
case we can see that both the program and data of our VN machine are just
projections from the same computational state.

Visited 937 times