# Waquo/combinators-info.github.com

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
238 lines (179 sloc) 23 KB
 12 Appendix: Finding Joy in Combinators

12 Appendix: Finding Joy in Combinators

In this book, we have looked at a few interesting combinators and some Ruby code inspired by them. Today we’ll review the definition of a combinator, and from there we’ll learn something intriguing about an entire family of programming languages, the Concatenative Languages.

Let’s start at the beginning: What is a combinator?

One definition of a combinator is a function with no free variables. Another way to put it is that 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.

So if I tell you that:

finch.call(a).call(b).call(c)
=> c.call(b).call(a)

Then you know that finch is a combinator because the effect it produces is made up solely of combining the effects of the things it takes as parameters. That’s easy, but yet… Where is our vaunted simplicity? Working with Ruby’s lambdas and braces and calls gets in our way. We can learn a lot from combinatorial logic to help our Ruby programming, but Ruby is a terrible language for actually learning about combinatorial logic.

12.1 Languages for combinatorial logic

Combinatorial logicians use a much simpler, direct syntax for writing expressions:

Fabc => cba

Whenever a logician writes abc, he means the same thing as when a Rubyist writes a.call(b).call(c). Note that like Ruby, the precedence in combinatorial logic is to the left, so abc is equivalent to (ab)c just as in Ruby a.call(b).call(c) is equivalent to (a.call(b)).call(c).

I think you’ll agree that abc is much simpler than a.call(b).call(c). Here’s another look at the combinators we’ve met in this series, using the simpler syntax:

Kxy => x
Txy => yx
Cxyz => xzy
Q3xyz => z(xy) # Q3 is shorthand for the Quirky bird
Bxyz = x(yz)
Qxyz = y(xz) # Q is shorthand for the Queer bird

There are many, many more combinators, of course. Infinitely more, in fact. We only have names for some of the most useful. For example, the Warbler Twice Removed, or W** is written:

W**xyzw => xyzww

(Warblers are actually in a whole ‘nother family of birds that introduce duplication. Other members of that family include the Mockingbird and Starling. They’re incredibly useful for introducing ideas like iteration and recursion.)

You could say that combinators take a string of symbols (like x, y, z, w, and so forth), then they introduce some erasing, some duplication, some permutation, and add some parentheses. That they work to rearrange our string of symbols.

We have seen that parentheses are allowed, and that some combinators introduce parentheses. Before you say that the combinators introduce new symbols, remember that parentheses are punctuation. If you think of the symbols as words and the parentheses as punctuation, you see that the combinators simply rearrange the words and change the punctuation without introducing new words.

Now I said that combinators work with strings of symbols. This was a terrible analogy, because it made us talk about punctuation and why parentheses are not symbols. Another thing you could say is that combinator work with lists of symbols, then they re-arrange the symbols, including removing symbols, introducing sub-lists, and duplicating symbols.

This is more interesting! Now we can see that in our notation, adding parentheses is a way of introducing a sub list. Let’s revisit the bluebird:

Bxyz = x(yz)

Now what we can say is this: The bluebird takes a list of three symbols and answers a list of one symbol and a sublist of two symbols. In Ruby:

bluebird = lambda { |*args|
x, y, z = args
[x, [y, z]]
}

bluebird.call(:x, :y, :z)
=> [:x, [:y, :z]]

This is easy. What about the Thrush?

thrush = lambda { |*args|
x, y = args
[y, x]
}

thrush.call(:x, :y)
=> [:y, :x]

Now let’s pause for a moment. Imagine we had an entire programming language devoted to this style of programming. The primary thing it does is define combinators that take a list of symbols and recombine them. Since it works with lists and we are thinking about combinatory logic, we will represent our expressions as lists:

idiot :x
=> :x

mockingbird :x
=> :x :x

bluebird :x :y :z
=> :x [:y :z]

thrush :x :y
=> :y :x

Wait! Do not shout Lisp! Just because we have lists of things does not mean we are programming in Lisp!! Let’s keep going, and you will see in the next example that I do not mean Lisp:

bluebird thrush :x :y :z
=> thrush [:x :y] :z
=> :z [:x :y]

And therefore in our fictitious language we can write:

quirky = bluebird thrush

And thus:

quirky :x :y :z
=> :z [:x :y]

This looks familiar. Have you ever written a program in Postscript? Or [Forth](http://en.wikipedia.org/wiki/Forth_(programming_language)? What if instead of using a thrush we used a word called swap? Or instead of a mockingbird we used a word called dup?

12.2 Concatenative languages

Concatenative (or stack-based) programming languages–like Postscript, Forth, Factor, and Joy–are almost direct representations of combinatorial logic. There is a list of things, words or combinators permute the list of things, and the things can be anything: data, other combinators, or even programs. These languages are called concatenative languages because the primary way to compose programs and combinators with each other is to concatenate them together, like we did with the bluebird and thrush above.

For me the purpose of life is partly to have joy. Programmers often feel joy when they can concentrate on the creative side of programming, So Ruby is designed to make programmers happy. –Yukihiro Matsumoto

You have probably heard that it is a good idea to learn a new programming language every year. Is a concatenative language on your list of languages to learn? No? Well, here is the reason to learn a concatenative language: You will learn to think using combinatorial logic. For example, the Y Combinator is expressed in Joy as:

[dup cons] swap concat dup cons i

Where dup is a mockingbird, swap is a thrush, i is an idiot bird, and cons and concat are likewise two other combinators. Writing in Joy is writing directly in combinators.

In other programming languages, combinatorial logic is an underpinning. It helps us explain and prove certain things, It inspires us to invent certain things. It is behind everything we do. That’s good. But in a concatenative language, it is not an underpinning or behind a curtain. It is right out there in front of you. And learning to program in a concatenative language means learning to think in combinators.

The combinators we’ve discussed in depth so far are all fascinating, however as a basis for writing programs they are incomplete. You cannot represent every possible program using kestrels, thrushes, cardinals, quirky birds, bluebirds, and queer birds. To represent all possible programs, we need to have at least one combinator that duplicates symbols, like a mockingbird or another from its family.

2. 0.2 Preface
3. 1 Introduction
4. 2 Kestrels
5. 2.1 Object initializer blocks
6. 2.2 Inside, an idiomatic Ruby Kestrel
7. 2.3 The Enchaining Kestrel
8. 2.4 The Obdurate Kestrel
9. 2.5 Kestrels on Rails
10. 2.6 Rewriting “Returning” in Rails
11. 3 The Thrush
12. 3.1 Let
13. 4 Songs of the Cardinal
14. 4.1 Building a Cardinal in Ruby
15. 5 Quirky Birds and Meta-Syntactic Programming
16. 5.1 A limited interpretation of the Quirky Bird in Ruby
17. 5.2 Embracing the Quirky Bird
18. 5.3 Andand even more
19. 6 Aspect-Oriented Programming in Ruby using Combinator Birds
21. 6.2 The super keyword, perhaps you’ve heard of it?
22. 6.3 The Queer Bird
23. 7 Mockingbirds
24. 7.1 Duplicative Combinators
25. 7.2 Recursive Lambdas in Ruby
26. 7.3 Recursive Combinatorics
27. 7.4 Recursive Combinators in Idiomatic Ruby
28. 7.5 The Mockingbird
29. 8 Refactoring Methods with Recursive Combinators
30. 8.1 Divide and Conquer
31. 8.2 The Merge Sort
32. 8.3 Separating Declaration from Implementation
33. 8.4 Practical Recursive Combinators
34. 8.5 Spicing things up
35. 8.6 Building on a legacy
36. 8.7 Seriously
37. 8.8 Separating Implementation from Declaration
38. 8.9 A Really Simple Recursive Combinator
39. 9 You can’t be serious!?
40. 9.1 String to Proc
41. 9.2 The Message
42. 10 The Hopelessly Egocentric Book Chapter
43. 10.1 Object-oriented egocentricity
44. 11 Bonus Chapter: Separating Concerns in Coffeescript using Aspect-Oriented Programming
45. 12 Appendix: Finding Joy in Combinators
46. 12.1 Languages for combinatorial logic
47. 12.2 Concatenative languages
48. 13 Appendix: Source Code
49. 13.1 kestrels
50. 13.2 thrushes
51. 13.3 the cardinal
52. 13.4 quirky birds
53. 13.5 bluebirds