# Waquo/combinators-info.github.com

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
338 lines (268 sloc) 37.3 KB
 7 Mockingbirds

7 Mockingbirds

In this chapter, we will meet a combinator that duplicates its arguments, and see how to use it to achieve recursion. Such combinators are called recursive combinators, and are an important foundation for separating the concrete implementation of an algorithm from its definition.

7.1 Duplicative Combinators

Almost all of the combinators we’ve seen in previous essays about combinators “conserve” their arguments. For example, if you pass xyz to a Bluebird, you get one x, one y, and one z back, exactly what you passed in. You get x(yz) back, so they have been grouped for you. But nothing has been added and nothing has been taken away. Likewise the Thrush reverses its arguments, but again it answers back the same number arguments you passed to it. The Kestrel, on the other hand, does not conserve its arguments. It erases one. If you pass xy to a Kestrel, you only get x back. The y is erased. Kestrels do not conserve their arguments.

Today we are going to meet another combinator that does not conserve its arguments, the Mockingbird. Where a Kestrel erases one of its arguments, the Mockingbird duplicates its argument. In logic notation, Mx = xx. Or in Ruby:

mockingbird.call(x)
#=> x.call(x)

The Mockingbird is not the only combinator that duplicates one or more of its arguments. Logicians have also found important uses for many other duplicating combinators like the Starling (Sxyz = xz(yz)), which is one half of the SK combinator calculus, and the Turing Bird (Uxy = y(xxy)), which is named after its discoverer.

The great benefit of duplicative combinators from a theoretical perspective is that combinators that duplicate an argument can be used to introduce recursion without names, scopes, bindings, and other things that clutter things up. Being able to introduce anonymous recursion is very elegant, and there are times when it is useful in its own right.

7.2 Recursive Lambdas in Ruby

Let’s write a simple recursive combinator in Ruby from first principles. To start with, let’s pick a recursive algorithm to implement: We’ll sum the numbers of a nested list. In other words, we’re going to traverse a tree of numbers and generate the sum of the leaves, a recursive problem.

This is a trivial problem in Ruby, [1, [[2,3], [[[4]]]]].flatten.inject(&:+) will do the trick. Of course, it does so by calling .flatten, a built-in method that is itself recursive. However, by picking a really simple example, it’s easy to focus on the recursion rather than by the domain-specific parts of our problem. That will make things look a little over-engineered here, but when you’re interested in the engineering, that’s a good thing.

So what is our algorithm?

1. If we are given a number, return it.
2. If we are given a list, call ourself for each item of the list and sum the numbers that are returned.

In Ruby:

sum_of_nested_list = lambda do |arg|
arg.kind_of?(Numeric) ? arg : arg.map { |item| sum_of_nested_list.call(it\
em) }.inject(&:+)
end

One reason we don’t like this is that it breaks badly if we ever modify the variable sum_of_nested_list. Although you may think that’s unlikely, it can happen when writing the method combinators you’ve seen in previous chapters. For example, imagine you wanted to write to the log when calling this function, but only once, you don’t want to write to the log when it calls itself.

old_sum = sum_of_nested_list
sum_of_nested_list = lambda do |arg|
puts "sum_of_nested_list(#{arg.inspect})"
old_sum.call(arg)
end

sum_of_nested_list.call([[[[[6]]]]])

sum_of_nested_list([[[[[6]]]]])
sum_of_nested_list([[[[6]]]])
sum_of_nested_list([[[6]]])
sum_of_nested_list([[6]])
sum_of_nested_list([6])
sum_of_nested_list(6)
#=> 6

This doesn’t work because inside our original sum_of_nested_list, we call sum_of_nested_list by name. If that gets redefined by a method combinator or anything else, we’re calling the new thing and not the old one.

Another reason to eschew having lambdas call themselves by name is that we won’t be able to create anonymous recursive lambdas. Although naming things is an important part of writing readable software, being able to make anonymous things like object literals opens up a world where everything is truly first class and can be created on the fly or passed around like parameters. So by figuring out how to have lambdas call themselves without using their names, we’re figuring out how to make all kinds of lambdas anonymous and flexible, not just the non-recursive ones.

7.3 Recursive Combinatorics

The combinator way around this is to find a way to pass a function to itself as a parameter. If a lambda only ever calls its own parameters, it doesn’t depend on anything being bound to a name in its environment. Let’s start by rewriting our function to take itself as an argument:

sum_of_nested_list = lambda do |myself, arg|
arg.kind_of?(Numeric) ? arg : arg.map { |item| myself.call(myself, item) \
}.inject(&:+)
end

One little problem: How are we going to pass our function to itself? Let’s start by currying it into a function that takes one argument, itself, and returns a function that takes an item:

sum_of_nested_list = lambda do |myself|
lambda do |arg|
arg.kind_of?(Numeric) ? arg : arg.map { |item| myself.call(myself).call\
(item) }.inject(&:+)
end
end

Notice that we now have myself call itself and have the result call an item. To use it, we have to have it call itself:

sum_of_nested_list.call(sum_of_nested_list).call([1, [[2,3], [[[4]]]]]) #=> 10

This works, but is annoying. Writing our function to take itself as an argument and return a function is one thing, we can fix that, but having our function call itself by name defeats the very purpose of the exercise. Let’s fix it. First thing we’ll do, let’s get rid of myself.call(myself).call(item). We’ll use a new parameter, recurse (it’s the last parameter in an homage to callback-oriented programming style). We’ll pass it myself.call(myself), thus removing myself.call(myself) from our inner lambda:

sum_of_nested_list = lambda do |myself|
lambda do |arg|
lambda do |arg, recurse|
arg.kind_of?(Numeric) ? arg : arg.map { |item| recurse.call(item) }.i\
nject(&:+)
end.call(arg, myself.call(myself))
end
end

sum_of_nested_list.call(sum_of_nested_list).call([1, [[2,3], [[[4]]]]])
#=> 10

Next, we hoist our code out of the middle and make it a parameter. This allows us to get rid of the ` sum_of_nested_list.call(sum_of_nested_list)` by moving it into our lambda:

sum_of_nested_list = lambda do |fn|
lambda { |x| x.call(x) }.call(
lambda do |myself|
lambda do |arg|
fn.call(arg, myself.call(myself))
end
end
)
end.call(
lambda do |arg, recurse|
arg.kind_of?(Numeric) ? arg : arg.map { |item| recurse.call(item) }.inj\
ect(&:+)
end
)

sum_of_nested_list.call([1, [[2,3], [[[4]]]]])
#=> 10

Lots of code there, but let’s check and see that it works as an anonymous lambda:

lambda do |fn|
lambda { |x| x.call(x) }.call(
lambda do |myself|
lambda do |arg|
fn.call(arg, myself.call(myself))
end
end
)
end.call(
lambda do |arg, recurse|
arg.kind_of?(Numeric) ? arg : arg.map { |item| recurse.call(item) }.inj\
ect(&:+)
end
).call([1, [[2,3], [[[4]]]]])
#=> 10

Looking at this final example, we can see it has two cleanly separated parts:

# The recursive combinator

lambda do |fn|
lambda { |x| x.call(x) }.call(
lambda do |myself|
lambda do |arg|
fn.call(arg, myself.call(myself))
end
end
)
end.call(

# The lambda we wish to make recursive

lambda do |arg, recurse|
arg.kind_of?(Numeric) ? arg : arg.map { |item| recurse.call(item) }.inj\
ect(&:+)
end

)

7.4 Recursive Combinators in Idiomatic Ruby

We’ve now managed to separate the mechanism of recursing (the combinator) from what we want to do while recursing. Let’s formalize this and make it idiomatic Ruby. We’ll make it a method for creating recursive lambdas and call it with a block instead of a lambda:

def lambda_with_recursive_callback
lambda { |x| x.call(x) }.call(
lambda do |myself|
lambda do |arg|
yield(arg, myself.call(myself))
end
end
)
end

sum_of_nested_list = lambda_with_recursive_callback do |arg, recurse|
arg.kind_of?(Numeric) ? arg : arg.map { |item| recurse.call(item) }.injec\
t(&:+)
end

sum_of_nested_list.call([1, [[2,3], [[[4]]]]])
#=> 10

Not bad. But hey, let’s DRY things up. Aren’t x.call(x) and myself.call(myself) the same thing?

7.5 The Mockingbird

Yes, x.call(x) and myself.call(myself) are the same thing:

def mockingbird &x
x.call(x)
end

def lambda_with_recursive_callback
mockingbird do |myself|
lambda do |arg|
yield(arg, mockingbird(&myself))
end
end
end

sum_of_nested_list = lambda_with_recursive_callback do |arg, recurse|
arg.kind_of?(Numeric) ? arg : arg.map { |item| recurse.call(item) }.injec\
t(&:+)
end

sum_of_nested_list.call([1, [[2,3], [[[4]]]]])
#=> 10

But does it blend?

lambda_with_recursive_callback { |arg, recurse|
arg.kind_of?(Numeric) ? arg : arg.map { |item| recurse.call(item) }.injec\
t(&:+)
}.call([1, [[2,3], [[[4]]]]])
#=> 10

Yes!

And now we have our finished recursive combinator. We are able to create recursive lambdas in Ruby without relying on environment variables, just on parameters passed to blocks or lambdas. Our recursive combinator is built on the simplest and most basic of duplicating combinators, the Mockingbird.

In the next chapter, we’ll build more sophisticated (and practical) recursive combinators. And while doing so, we’ll take an aggressive approach to separating interfaces from implementations in algorithms.

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