Standard Combinator Birds

`oscin.es`

The oscin.es library contains nearly all of the standard combinators from combinatorial logic implemented in JavaScript.

Installing oscin.es is a breeze with npm:

```
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:

```
node
```

We can load any of the standard combinators as functions and try them:

O = require'oscines'var S = OS K = OK I = 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 `x(y)(z)`

in JavaScript. But `Bxyz`

is equivalent to `x(y(z))`

, analogous to `compose`

in the allong.es library and most other FP libraries for JavaScript.

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.

So we have oscin.es loaded into node. Let's solve a problem from To Mock a Mockingbird. Smullyan puts it much more eloquently, but we start with the following basic rules:

- 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`A`

is the name of some bird we know (perhaps "Arthur"), and`x`

and`y`

could 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:

$'Lxy' //=> 'z'

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:

$'Lyx' //=> 'y(xx)'

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:

$'I(xx)' //=> 'xx'

And now substitute `I`

for `y`

:

$'LIx' //=> 'xx'

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.

Of course, you are free to use the combinators themselves in your JavaScript, if you look at the source code you'll find there's no weird special sauce in the definitions:

return acallthis bcallthis b return return 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 `a`

to `z`

have a special role as placeholders within the `reduce`

function. They are not defined.)

There's more on the ocin.es home page

- JavaScript Allongé, CoffeeScript Ristretto, Kestrels, Quirky Birds, and Hopeless Egocentricity, and other books.
- allong.es, practical function combinators and decorators for JavaScript.
- Method Combinators, a CoffeeScript/JavaScript library for writing method decorators, simply and easily.
- jQuery Combinators, what else? A jQuery plugin for writing your own fluent, jQuery-like code.