Mockingbirds and Simple Recursive Combinators in Ruby | Hacker News Reader

Mockingbirds and Simple Recursive Combinators in Ruby

github.com

32 pointsraganwald11 comments

There's an interesting graphical notation for the lambda calculus here:

http://www.cs.virginia.edu/~evans/cs655/readings/mockingbird...

I'd like an easy peasy explanation of what a combinator is.

I just finished reading To Mock a Mockingbird (though I don't recall a formal definition) so I'll take a stab and leave it to others to correct me.

Combinators are the basic building block of combinatorial logic. Simply, they are functions that permute, group, repeat and/or eliminate their arguments.

E.g., The T (thrush using the bird naming convention) combinator takes two args and swaps their order: Txy = yx.

The B (bluebird) combinator groups it's 2nd and 3rd args (overriding the default left-associativity): Bxyz = x(yz).

The M (mockingbird) combinator takes a single arg and repeats it: Mx = xx.

The K (kestrel) combinator takes two args and eliminates the second: Kxy = x.

There are two schools of 'lambda calculus' that use a set of base combinators to build arbitrarily complex ones. The first school uses B, M, T and I which is the identity function: Ix = x. The other school combines B, M and T into a single combinator that permutes, groups and repeats with one application. It's called S (starling): Sxyz = xz(yz). This latter school uses S together with K.

Whether using B/M/T/I or S/K/I, you can build up pretty much any other combinator:

  B = S(KS)K.
  E.g.,
  S(KS)Kxyz, applying the leftmost S =
  (KS)x(Kx)yz, dropping the parens (which are still implied when not present due to the left-associativity) =
  KSx(Kx)yz, applying the leftmost K =
  S(Kx)yz, applying the S =
  (Kx)z(yz) =
  Kxz(yz) =
  x(yz) = Bxyz.

  T = ((S(K(S((SK)K))))K)
  M = ((S((SK)K))((SK)K))
  I = SKK. E.g., SKKx = KK(Kx) = K(x) = x = Ix.
  V**xyzwv = xyvzw.
  V** is spelled: (S(K((S(K((S((S(K((S(KS))K)))S))(KK))))((S(K(S(K((S((S(K((S(KS))K)))S))(KK))))))((S(K((S((S(K((S(KS))K)))S))(KK))))(S(K((S((S(K((S(KS))K)))S))(KK)))))))))

The up-shot of all of this is that any computer program complete with arithmetic functions, boolean/propositional logic, list processing, etc. (i.e., Turing complete) can be expressed as a sequence of these base combinators. There are other practical (less theoretical) applications in programming. E.g., Using the T/thrush combinator to improve readability: http://debasishg.blogspot.com/2009/09/thrush-combinator-in-s... .

The Y combinator, for which this site is named, encapsulates recursion (i.e., a fixed-point combinator). It's spelled: S(K(SII))(S(S(KS)K)(K(SII))).

"The up-shot of all of this is that any computer program complete with arithmetic functions, boolean/propositional logic, list processing, etc. (i.e., Turing complete) can be expressed as a sequence of these base combinators. "

Now, that is interesting. It mirrors some thoughts I've been having lately but unable to express fully. Tell me more.

Try reading the book that steamer25 mentioned (To Mock a Mockingbird by Raymond Smullyan). It's very approachable and well written.

Yeah, the answer is a bit beyond the scope of a HN comment but it kind of boils down to clever representations for the values zero, n+1, true and false, etc. Effectively, any real number is represented as 0+1+1+1+1+1+... E.g., You can compare two numbers (less than, greater than, equal to, etc.) by decrementing them simultaneously and seeing which arrives at zero first (which requires recursion, an isZero function and boolean values for the result), etc. It's very similar to deriving Lisp as in The Little Lisper or The Little Schemer.

The execution of such a program on an actual "Turing machine" probably wouldn't be as performant as on our modern complex-instruction-set processors. Then again, I think the intent is to think of it as executing at the same speed at which a mathematical equation is true. I.e., You could go out and count 999 things or just accept that nine nine nine is a concise symbol representing the same procedure. The SKI representation isn't as terse but it's still just a symbol.

You can also read more at http://en.wikipedia.org/wiki/Lambda_calculus#Encoding_dataty... ...though it doesn't seem as gentle (read hand-holdingly verbose) as To Mock a Mockingbird.

A reference: http://www.angelfire.com/tx4/cus/combinator/birds.html

Also a Combinator Calculator.

A combinator is a function that takes one or more arguments and produces a result without introducing anything new. In Ruby terms, we are talking about blocks, lambdas or methods that do not call anything except what has been passed in.

https://github.com/raganwald/homoiconic/blob/master/2008-11-...

Thanks for pointing out an important omission. Updated.

What do you mean by this, One little problem: How are we going to pass our function to itself? ?

You just pass the function as a parameter to call, like this:

  sum_of_nested_list.call(sum_of_nested_list, [1,[2,3]])

Right? What am I missing?

Again, that depends on binding the function to the name. If that binding changes (as in the example given where some logging is added), things break. Also, being able to do with completely anonymously allows you to use a recursive lambda anywhere you can use a lambda or a block, something that is not currently possible without making a combinator.

There’s a practical example of using the Y-COmbinator to make auto-vivifying hash tables in one of the links.

Got it, thanks. I was confused because I took that sentence to mean that it wasn't possible to pass the function to itself.

Reply on news.ycombinator.com