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 591 times