Kestrels, Quirky Birds

Introduction

Combinatory logic is used as a basis of functional programming languages.
A combinator is a higher-order function that uses only function application and ealier defined combinators to define a result from its arguments.

[aside] CSE260 and CSE261 were all about Combinatory logic, Number theory, proving RSA algorithm from first principles.

So what will this book be about? We'll look at several combinators and their ramifications when writing programs using Ruby. Starting form K combinator and Ruby's .tap method, to meta-programming, aspects and recursive combinators.

[word] ornithological - relating to the study of birds. "These ornithological nicknames have become part of the standard lexicon for combinatory logic."

S and K combinators express everything in Lambda Calculus and Set Theory.
To Mock a Mockingbird was a book that gave bird names to combinators for fun.

Kestrels

K Combinator is a function that returns a constant function. Kxy = x. In Ruby think about .tap. Suppose we wanted to log the person, with we'd do this:

address = Person.find(...).tap { |p| log "person #{p} found }.address

Without using tap, we'd need some temp variables to accomplish this logging. It'd be something awkward like this:

person = Person.find(...)
log "person #{person} found"
address = person.address

tap is a method in all objects that passes self to a block and returns self. The result of the block is discarded, it is only there for side effects.

There is also a Krestel named returning in Rails that this book mentions. (though this one is now deprecated). It illustrates the concept well. This method

def registered_person(params = {})
    person = Person.new(params.merge(:registered => true)
    Regisry.register(person)
    person.send_email_notification
    person
end

can be rewritten like this with returning

def registered_person(params = {})
    returning Person.new(params.merge(:registered => true) do |person|
        Registery.register(person)
        person.send_email_notification
    end
end

Object Initializer Blocks

The idea is to accept an optional block with new and evaluate the block for side-effect. This pattern of wanting a Kestrel/returning/tap when you create a new object is so common that it's built into ActiveRecord. So the above method can actually be written without the returning.

def registered_person(params = {})
  Person.new(params.merge(:registered => true)) do |person|
    Registry.register(person)
    person.send_email_notification
  end
end

Inside, an Idiomatic Ruby Kestrel

For initializer block, it doesn't pass the new class to the block as a parameter necessarily but it evaluates the block in the context of the new class.

What does that mean specifically?

It means it evaluates the block with self set to the new class. This is different from tap and returning. They leave self untouched.

The Enchaining Kestrel

Object.tap of Ruby 1.9 is also useful when we want to execute several methods on the same object without having to create a lot of temporary variables. Method chaining in other words. Something like HardDrive.new.capacity(150).external.speed(7200)

There is a really good example of using tap for safely method chaining, with Array methods that don't always return the array, and sometime return nil.

Example: .uniq! apparently returns nil if the array is already unique. (.uniq on the other hand does return the array itself)

irb(main):009:0> arr = [1,2,3,4,5]
=> [1, 2, 3, 4, 5]
irb(main):010:0> arr.uniq
=> [1, 2, 3, 4, 5]
irb(main):011:0> arr.uniq!
=> nil

So we can use .tap to ensure we always get the array like this:

irb(main):012:0> arr.tap(&:uniq!)
=> [1, 2, 3, 4, 5]

And then we can method chain safely if needed [1,2,3,4,5].tap(&:uniq!).sort!

So we can use .tap to enchain methods when the methods do not return the receiver.

The Obdurate Kestrel

This part is about an gem called andand that adds Object#tap to Ruby 1.8 as well another method called Object#dont. #dont simply ignores the block passed in and seems like it can be used for logging and debugging to NOOP a method call. It's kinda like commenting it out. An example is arr.dont.sort!

I don't like the idea of using a get to add behavior to an older version of Ruby. So, interesting but ignoring.

Kestrels on Rails

This section is comparing the semantics of returning vs. object initializer blocks in Rails.

Returning fully evaluates the expression, including all of its callbacks. The object initializer block, on the other hand, is called as part of initializing the object before starting the lifecycle of the object including its callbacks.

Returning is what you want when you want to do stuff involving the fully created object, and logically group the other statements in the block together.

Object initializer is what you want when you want to initialize some fields by hand and perform some calculations before kicking off the object creation lifecycle.

Rewriting `Returning` in Rails

I think returning in Rails has been deprecated since Rails 3. But none the less, this section goes into all the reasons it's a good to use and also how it can be implemented.

First, there is a possibility of a subtle bug while using returning. Namely, assignments inside the block to the variable being return have no effect and so the program does not do what may have been intended. Example:

returning ... do |var|
    #...
    var = something_else
    #...
end

random - "The principle of least surprise" means the design should be internally consistent. Which is not the same thing as familiar.

There is a project called RewriteRails that added syntactic abstraction to Rails projects without monkey patching. This project is long deprecated of course. I checked and the last commit was in October 2012.

This RewritRails thing would change code involving returning such that it would change the value of what was being returned to take into account assignments within the block. Interestingly, it would do this by rewriting the code you write so that the ruby interpreter sees that code and you see your code (apparently this is like Lisp macros). So for example, it would rewrite this:

def registered_person(params = {})
  returning Person.new(params.merge(:registered => true)) do |person|
    if Registry.register(person)
      person.send_email_notification
    else
      person = Person.new(:default => true)
    end
  end
end

into this:

def registered_person(params = {})
  lambda do |person|
    if Registry.register(person)
      person.send_email_notification
    else
      person = Person.new(:default => true)
    end
    person
  end.call(Person.new(params.merge(:registered => true)))
end

The Thrush

In Combinatory logic, the thrush is a simple permuting combinator. It reverses evaluation. So Txy = yx.

With thrush called into you can write this:

    lambda { |x| x * x }.call((1..100).select(&:odd?).inject(&:+))

like this instead

    (1..100).select(&:odd?).inject(&:+).into { |x| x * x }

The advantage being that the second one is clearer to read. Start with numbers from 1 to 100, take the odds ones, add them, then square them.

This type of permuting combinator is not strictly necessary when we have parentheses and local variables though.

Songs of the Cardinal

A Cardinal is a permuting combinator. So a Cardinal first passes a_proc to proc_over_proc and then passes a_value to the result. proc_over_proc is a function that takes a function and return a function.

Thrush can be thought of as a 'special' case of Cardinal where the proc_over_proc is an identity function (identity = lambda { |f| f })

What does all this mean? Let's see in Ruby code (the author mentions a limitation of define_method in 1.8 that was no longer the case in 1.9. Since we are way passed Ruby 1.9 ignoring that part):

Here is a proc_over_proc:

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

This takes a_proc and returns a brand new proc that only calls a_proc if the value passed is not nil.

An example of a Cardinal that is Thrush like:

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

This says take all of the odd numbers from 1-10 then add them together (so 1+3+5+7+9 = 25). That becomes the 'value' and the 'proc' is the block that squares the given value. So the final answer would be 25x25 or 625.

The whole point of all of this is that we can have a method that applies a value to a block but we can modify the semantics of the block in any way we want, on the fly. So this is, in-essence, meta-programming.

Quirky Birds and Meta-Syntactic Programming

First, what does metasyntax mean from wikipedia:

In logic and computer science, a metasyntax describes the allowable structure and composition of phrases and sentences of a metalanguage, which is used to describe either a natural language or a computer programming language.

[aside] wikipedia mentions Backus-Naur form (BNF) and I recall learning about that along with a language call Prolog a while ago, vaguely

So the Quirky Bird combinator is like the Cardinal but while the Cardinal modifies the function that is applied to a value, Quirky Bird modifies the value itself. So the formal definition is:

def quirky_bird_define(a_value, &a_proc)
    a_proc.call(value_proc.call(a_value))
end

value_proc is the thing that changes the value before it's passed into a_proc.

A concrete example:

quicky_bird_define(:square_first) do |a_value|
    a_value * a_value
end

square_first(2) { |n| n+1 }
=> 5

Next, what if we wanted to define maybe using Quirky Bird. With Cardinal we could writ a proc that would modify another proc to return nil if it was passed nil. With Quirky Bird this can't really be done in a way that feels natural There some awkward attempts.

In one attempt value_proc will take a value, and if the value is nil it will return an object that responds with nil to any method called on it.

In another attempt, what if instead of writing maybe(nil) { |n| n+1 } we do it like this nil.maybe + 1 or 1.maybe + 1 instead? In that case, maybe becomes a method on the object class that applies value_proc to its receiver. (this looks more method-oriented or object-oriented rather than function-oriented).

def quirky_bird_extend(method_name, &value_proc)
    Object.send(:define_method, method_name) do
        value_proc.call(self)
    end
end

Copying this straight from the book, as it makes an important point:

We are using define_method and a block rather than the def keyword. The reason is that when we use define_method and a block, the body of the method executes in the context of the block, not the context of the object itself. Blocks are closures in Ruby, which means that the block has access to value_proc, the parameter from our quirky_bird_extend method.
Had we used def, Ruby would try to evaluate value_proc in the context of the object itself. So our parameter would be lost forever. Performance wonks and compiler junkies will be interested in this behaviour, as it has very serious implications for garbage collection and memory leaks.

That above definition of quirky_bird_extend then leads to the definition of maybe and also of try (! I love try, have found it very useful).

[aside] All of these examples are using BlankSlate which is something I've never seen before. The idea is that it's an abstract base class with no predefined methods.

In summary, we can used the quirky bird to create a whole family of methods that modify the receiver in some way to produce new semantics.

Aspect-Oriented Programming in Ruby using Combinator Birds

Bluebird combinator introduced. It is special as it composes two other combinators. (think of the parens in (x * 2) + 1)

It's written officially as

bludebird.call(proc1).call(proc2).call(value)
    => proc1.call(proc2.call(value))

The first line says proc1.call(proc2).call(value) meaning put proc2 into proc1 getting function back, then put value into that function.

The second line says put value into proc2, then put the result of that into proc1

[aside] I first encountered the term Aspect-Oriented Programming (AOP) in the Java programming language at work. I learned of terms like aspects and cross-cutting-concerns and advice. At the time, I understood the code that was doing this stuff in Java but of course don't recall any more. I associate before and after methods in Rails controller to this concept AOP. Also last thought, what a weird word aspect to stick in front of 'oriented'

Don't see how the definitions so far connect to anything practical I know of AOP. Let's keep going.

Giving Methods Advice

This section confirms that calling things like after_save, before_filter are part of Rails support for aspect-oriented programming. then it tries to implement the idea of before methods in Ruby by using a 'trick' the author found on a blog.

At this point, things get into the handy-wavy territory. There is some code pasted in under the NativeBeforeMethods module. With the paragraph after starting with 'as you can see,...' but not explaining anything about the code.

The example of using the before methods is pretty clear and straightforward. We all know this from experience. The before method gets called before the method we specified and does something useful/necessary for our intended method.

class SuperFoo

  def one_parameter(x)
    x + 1
  end

  def two_parameters(x, y)
    x * y
  end
  
end

class Foo < SuperFoo

  include NaiveBeforeMethods

  before :one_parameter do |x|
    x * 2
  end

  before :two_parameters do |x, y|
    [x + y, x - y]
  end

end

Foo.new.one_parameter(5)
	=> 11

Foo.new.two_parameters(3,1)
	=> 8

The Super Keyword

The section makes the point that while we could use the super keyword in places where we are using before method, doing so would be more low level and less clear.

By using 'advice' we can separate clearly what the method does from the other things we may need to decorate it with (e.g. logging). So it separates concerns.

The Queer Bird

This one does things in the opposite direction and useful for after methods. The difference between before and after advice is that after advice is consumes and transforms whatever the method returns, while before advice consumes and transforms the parameters to the method.

The rest of this section is pretty hand-wavy, not actually teaching/explaining anything.

[todo] write about instance_eval and instance_exec for codecuriou.dev

Mockingbirds

The Mockingbird combinator is used to achieve recursion. It's a combinator that does not conserve it's arguments. It changes them by duplicating Mx = xx.

Recursive Lambdas in Ruby

With the below example of summing numbers using a recursive lambda, we create a need to have lambdas call themselves without using their names. We do this by figuring out how to make all kinds of lambdas anonymous and flexible.

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

(This is not the 'natural' way to write this recursion - it calls the lambda again for every single number one by one - but I guess it's done this way for sake of making a point about why the lambda needs to be anonymous)

Section 7.3 The progressive code snippets to make an anonymous lambda that call itself are...the motivation for needing to do this is poorly explained. The why question is not answered sufficiently. Making the whole read a bit unsatisfying.

[1, 2, 3].inject(&:+) == 6
:+.to_proc.call(1, 2)

String to Proc

The #to_proc method of the String class allows us to write certain simple lambdas as strings instead of using the lambda keyword, the proc keyword, or Proc.new. This gets rid of the noise.

Aside: to demonstrate the noise, and motivate and use of String#to_proc the author using the analogy that having the keyword lambda everywhere in the definition of recursive algorithms would like if at a poetry reading the author shouts the punctuation, as in

Two roads diverged in a yellow wood COMMA!
And sorry I could not travel both
And be one traveler COMMA! long I stood
And looked down one as far as I could
To where it bent in the undergrowth SEMI-COMMA!!

This made me laugh out loud. Also reminded me of reading this poem in high school. A road less traveled indeed.

Anyway, back to lambda and String#to_proc. The idea is that we can take this lambda { |x,y| x + y } and write it as 'x,y -> x + y'.

The -> is keeping with modern functional languages while lambda is in keeping with Lisp and lambda calculus. The -> also resembles arrow functions in ES6+.

Inferred parameters

This means that if we write x + y, String#to_proc treats it as x,y -> x + y. This works for simple cases, don't get too fancy with it.

"it"/the hole

If there is only one parameter, we can use _ (underscore) without naming it. So this code

multirec(
  'x.kind_of?(Numeric)',
  'x ** 2',
  'x',
  'z -> z.inject { |sum, n| sum + n }'
)

would become this

multirec(
  '_.kind_of?(Numeric)',
  '_ ** 2',
  '_',
  '_.inject { |sum, n| sum + n }'
)

The author says using the "it" is a matter of taste. And yeah. I do not like it. Looks unpleasant and unclear.

point-free

This terminology I have never heard before. "function points" is what functional programmers usually call parameters. Point-free style is about describing how functions are composed together rather than about describing what happens to their arguments.

Example! With String#to_proce magic this

lambda { |z| z.inject { |sum, n| sum + n } }

can be written as

".inject(&'+')"

That's exactly how (1..100).inject(&:+) in rails works.

The author offers some rules of thumb about when to use all these options provided by String#to_proc and when not to. Most of those rules sensible, though don't result in something that looks clear to me or more elegant (than being more explicit).

There is an example at the bottom of two variations of a function that rotates a matrix. The first is suppose to be hard to read/debug/modify as the fact that it's using recursion/divide-n-conquer is 'hidden'. The second variation makes this more explicit using lambdas and String#to_proc.

Neither seem that clear to me. But this point resonates, the goal is 'to disentangle the question of what we are doing from how we are doing it'. And the option to make the ceremonial parts of the code go away and emphasize the part that matter is nice (unlike other languages where the ceremony is much longer the 'meat' of the function and does feel like the poet shouting out punctuations).

Object-oriented egocentricity

So in OO programming is that programs consist of objects that respond to messages they send each other. A hopelessly egocentric object is easy to imagine: No matter what message you send it, the hopelessly egocentric object responds with itself.

Imagine making nil egocentric. So when we send a message to nil we get back nil. Instead of NoMethodError. That seems desirable for something like person.name.upcase so we don't have to check for nil.

But it's not as simple as that. Making nil egocentric makes sense for queries but not for updates, where the message we send is suppose to have an side effect like person.account.increment_balance(100). It doesn't make any sense for that to return nil or fail silently.

The author lists a number of considerations based on whether the meaning of nil in our context is NONE or UNKNOWN. And whether we are doing a purely functional transformation with a query or if we're doing updates with side effects.

Checking equality with UNKNOWN and truthiness get tricky also.

All of the nuances enumerated in this chapter lead to the conclusion that, while the idea is appealing, implementing an hopelessly egocentric nil in ruby is a no-go. We go with explicit idioms like #try and think deeply about the semantics of our data schemas.