# Waquo/combinators-info.github.com

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
245 lines (195 sloc) 19.9 KB
 4 Songs of the Cardinal

4 Songs of the Cardinal

In Combinatory Logic, the cardinal is one of the most basic permuting combinators; it reverses and parenthesizes the normal order of evaluation. The cardinal is written Cxyz = xzy. In Ruby:

cardinal.call(proc_over_proc).call(a_value).call(a_proc)
=> proc_over_proc.call(a_proc).call(a_value)

What does this mean? Let’s compare it to the Thrush. The thrush is written Txy = yx. In Ruby terms,

thrush.call(a_value).call(a_proc)
=> a_proc.call(a_value)

The salient difference is that a cardinal doesn’t just pass a_value to a_proc. What it does is first passes a_proc to proc_over_proc and then passes a_value to the result. This implies that proc_over_proc is a function that takes a function as its argument and returns a function.

Or in plainer terms, you want a cardinal when you would like to modify what a function or a block does. Now you can see why we can derive a thrush from a cardinal. If we write:

identity = lambda { |f| f }

Then we can write:

thrush = cardinal.call(identity)

What we have done is say a thrush is what you get when you use a cardinal and a function that doesn’t modify its function but answers it right back.

Note to ornithologists and ontologists:

This is not object orientation: a thrush is not a kind of cardinal. The correct relationship between them in Ruby is that a cardinal creates a thrush. Or in Smullyan’s songbird metaphor, if you call out the name of an identity bird to a cardinal, it will call out the name of a thrush back to you.

Now, this bizarre syntactic convention of writing foo.call(bar).call(bash) is not very helpful for actually writing software. It is great for explaining what’s going on, but if we are going to use Ruby for the examples, we need to lift our game up a level and make some idiomatic Ruby.

4.1 Building a Cardinal in Ruby

The next chunk of code works around the fact that Ruby 1.8 can’t define a proc that takes a block and also doesn’t allow define_method to define a method that takes a block. So for Ruby 1.8, we will start by making a utility method that defines methods that can take a block, based on an idea from coderr. For Ruby 1.9 this is not necessary: you can use define_method to define methods that take blocks as arguments.

def define_method_taking_block(name, method_body_proc)
self.class.send :define_method, "__cardinal_helper_#{name}__", &method_bo\
dy_proc
eval <<-EOM
def #{name}(a_value, &a_proc)
__cardinal_helper_#{name}__(a_value, a_proc)
end
EOM
end

Now we can see what the expression “accidental complexity” means. Do you see how we need a long paragraph and a chunk of code to explain how we are working around a limitation in our tool? And how the digression to explain the workaround is longer than the actual code we want to write? Ugh!

With that out of the way, we can write our cardinal:

def cardinal_define(name, &proc_over_proc)
define_method_taking_block(name) do |a_value, a_proc|
proc_over_proc.call(a_proc).call(a_value)
end
end

Ready to try it? Here’s a familiar example. We’ll need a proc_over_proc, our proc that modifies another proc. Because we’re trying to be Ruby-ish, we’ll write it out as a block:

do |a_proc|
lambda { |a_value|
a_proc.call(a_value) unless a_value.nil?
}
end

This takes a a_proc and returns a brand new proc that only calls a_proc if the value you pass it is not nil. Now let’s use our cardinal to define a new method:

cardinal_define(:maybe) do |a_proc|
lambda { |a_value|
a_proc.call(a_value) unless a_value.nil?
}
end

Let’s try it out:

maybe(1) { |x| x + 1 }
=> 2
maybe(nil) { |x| x + 1 }
=> nil

If we’re using Rails, we can make a slightly different version of maybe:

cardinal_define(:unless_blank) do |a_proc|
lambda { |a_value|
a_proc.call(a_value) unless a_value.blank?
}
end

unless_blank(Person.find(...).name) do |name|
register_name_on_title(name)
end

Remember we said the cardinal can be used to define a thrush? Let’s try our Ruby cardinal out to do the same thing. Recall that expressing the identity bird as a block is:

do |a_proc|
a_proc
end

Therefore we can define a thrush with:

cardinal_define(:let) do |a_proc|
a_proc
end

let((1..10).select { |n| n % 2 == 1 }.inject { |mem, var| mem + var }) do |\
x|
x * x
end
=> 625

As you can see, once you have a defined a cardinal, you can create an infinite variety of methods that have thrush-like syntax–a method that applies a value to a block–but you can modify or augment the semantics of the block in any way you want.

In Ruby terms, you are meta-programming. In Smullyan’s terms, you are Listening to the Songs of the Cardinal.

Table of Contents

1. 0.1 The MIT License
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
20. 6.1 Giving methods advice
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
54. 14 About The Author
55. 14.1 contact