Standard Combinator Birds
npm install oscin.es
You can run the tests if you like:
npm install jasmine-node npm install oscin.es npm test
One day there may be a nice interactive REPL, or better still a browser playground, but for now let's use node:
We can load any of the standard combinators as functions and try them:
O = require'oscines'var S = OSK = OKI = OI;K'foo''bar'//=> 'foo'
If you don't remember all the combinators' letters and what they do, you might want to look at bird.by.bird.spec.coffee. Even if you don't care for CoffeeScript, the tests are in a particularly easy-to-read format:
describe "The Standard Combinators"->validate 'Bxyz = x(yz)'validate 'Cxyz = xzy'validate 'Dxyzw = xy(zw)'validate 'Exyzwv = xy(zwv)'validate 'Fxyz = zyx'validate 'Gxyzw = xw(yz)'
This portion says that the B Combinator (or "Bluebird") performs composition. CL is left-associative, so
xyz is equivalent to
Bxyz is equivalent to
x(y(z)), analogous to
It also says that the C Combinator ("Cardinal") is equivalent to
x(z)(y) reversing two arguments, the D Combinator is a one-removed Bluebird, and so forth. This is the standard notation folks use (well, many would use a "." instead of "=", but that's another story.) Many standard derivations are shown and simultaneously tested as well, like:
describe "The Derivations"->describe "from Bluebirds"->validate 'Dxyzw = BBxyzw = xy(zw)'validate 'Exyzwv = B(BBB)xyzwv = xy(zwv)'describe "from Bluebirds and Thrushes"->validate 'Rxyz = BBTxyz = yzx'validate 'Cxyz = RRRxyz = B(T(BBT))(BBT)xyz = xzy'
This segment describes how to make a Dove out of two Bluebirds, an Eagle out of four Bluebirds and some parentheses, and so forth.
- We are given a forest of birds.
- When you call out the name of some bird to a bird, the bird responds with the name of a bird. We write this as
Ax = y, where
Ais the name of some bird we know (perhaps "Arthur"), and
ycould be any birds in the forest, possibly including Arthur.
- Each bird always gives the same response to the same bird name.
- The Mockingbird (or M Combinator) has the following property: The mockingbird's response to any bird is the same as that bird's response to its own name. We write this as:
Mx = xx.
One of Smullyan's problems is this. Say that we are given that the forest contains the following two birds:
- The Identity Bird (or I Combinator) has the following property: For any bird x,
Ix = x.
- The Lark (or L Combinator) has the following property: For any birds x and y,
Lxy = x(yy)
Prove that the forest contains a Mockingbird.
Let's use the
reduce function to work directly with CL expressions:
var $ = Oreduce$'Ix'//=> 'x'$'Lxy'//=> 'x(yy)'
Is it just parroting? Let's throw it a curve:
Seems legit. Let's see, what we want is some bird "M" such that
Mx = xx. We'll obviously need the Lark, it has a duplicative effect. Let's rewrite things to make it easier to see what we're doing:
So now we're reduced to the problem of "What bird
y is such that y(xx) = xx?" I know a bird like that, the Identity Bird. Let's try it:
And now substitute
So, the Mockingbird is the bird named by the Lark when you call out "Identity Bird!" to it. Or in simple terms,
M = LI. Since we actually found the bird, we have definitively proved that a forest containing a Lark and an Identity Bird also contains a Mockingbird!
The reduce function from oscin.es provides a simple tool for playing with problems like this. You can play with simple combinations of proper and true combinators (A proper combinator has a fixed order. i.e. It shuffles, duplicates, or erases its arguments but doesn't introduce anything. A true combinator can be constructed from proper combinators).
Reduce also works for fixed points ("Sage Birds"). For example:
$'UUx'//=> 'x(UUx)'$'LO(LO)x'//=> 'x(LO(LO)x)'
The first of those sage birds is attributed to Alan Matheson Turing.
return acallthis bcallthis breturnreturn abb
In general, the standard combinators have two versions. One, with the full name, skips around
this so that you can use it to decorate methods if you so desire. It also is "uncurried." You can
curry it with allong.es if you need. The second, "pure" version ignores
this and is written in curried form.
(The lower-case letters from
z have a special role as placeholders within the
reduce function. They are not defined.)
There's more on the ocin.es home page
- jQuery Combinators, what else? A jQuery plugin for writing your own fluent, jQuery-like code.