Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
167 lines (116 sloc) 10.8 KB

Wrapping Combinators

I received a nice email which asked, in essence:

Which combinator says "For every time you do A, remember to do C after you've done B?" Which combinator codifies the problems like freeing memory (C) after using it (B) whenever we have allocated it (A), or stuff like opening files and sockets (A), reading and/or writing from/to them (B), then closing them (C). Or accessing mutexen (A), working therein (B), and leaving (C)?

This is an interesting question. In essence, we are looking for a combinator that takes a function and imposes some side effects before and after the function.

The purely combinatorial answer

We want a combinator, "?" where:

?xyz = y

Meaning, "compute x, then y, then z, and return the value of y." Now right away the "canonical" list of combinators does not include any such thing. However, there is the rule of composition, meaning that for any two combinators A and B, there exists a combinator C such that:

Cx = A(Bx)

The rule of composition defines the operation of chaining functions together, where the output of one function is fed as the input to another. So what we are seeking is the appropriate composition of existing combinators that will produce the result we seek.

Let's look at our desired combinator again:

?xyz = y

We've already seen something a little like this: A Kestrel is a combinator that looks like this:

Kxy = x

The Kestrel takes a value, "x," and another value, "y," and returns "x" while ignoring "y." In a language with side-effects, and pass-by-value, the Kestrel expresses the idea of computing a value, "x" for the result and then performing some computation, "y" strictly for side-effects after computing "x."

This seems useful: It's half of what we want. Let's rewrite it slightly:

Kyz = y

This is the latter half of what we want. The first half will look something like this, given a combinator "_":

_xyz = yz

And then we would be able to compose a Kestrel with "_":

?xyz = K(_xyz) = y

So what is "_"? We have already decided:

_xyz = yz

Which is the same as:

_xy = y

There are a couple of ways to derive this combinator. One way is to compose a Thrush with a Kestrel:

Txy = yx, therefore:
K(Txy) = Kyx = y

(Another easy derivation uses a Kestrel and an Identity to produce the same result.) But let's verify that our composition of Kestrel and Thrush gets the job done:

K(Txy) = Kyx = y
K(Txyz) = Kyxz = yz
K(K(Txyz)) = K(Kyxz) = Kyz = y

So composing two Kestrels and a Thrush gives us a combinator that computes three values "x," "y," and "z" and returns "y" while throwing away the results of computing "x" and "z." In a world where side effects matter, this allows us to sandwich the computation of "y" in between "x" and "z."

Ruby

This is a fairly common pattern in Ruby, thanks to the convenience of blocks and the yield keyword. It looks a little different than the combinatorial version, but the most popular expression of this idea is probably the syntax for invoking a database transaction in Ruby on Rails:

Campaign.transaction do
  campaign = Campaign.create!(:created_by => current_user)
  campaign.versions.init! params, current_user
  redirect_to presentation_path(:id => campaign.id, :version => 1)
end

The #transaction method starts a database transaction using the connection owned by Campaign, yields to the block to execute the code in the block, and if all is successful it will commit the transaction. The results of starting and committing the transaction are discarded, and the #transaction method returns whatever the block returns. This is just like our K(K(Txyz))) combinator above.

(The source is obviously a little more complicated because it needs to roll the transaction back if there is an exception thrown, but the basic principle applies.)

While the syntax of invoking a transaction is nice and clean, the implementation is a little arbitrary. Using the yield keyword in any arbitrary method brings a Perlisism to mind: Beware the Turing Tar Pit, where everything is possible, but nothing of interest is easy. The yield keyword makes wrapping code in a transaction possible, as well as iterating over a collection possible, implementing a Kestrel, and many other idioms.

Here's the source for #transaction in Rails' ActiveRecord::ConnectionAdapters::DatabaseStatements module:

 def transaction(options = {})
   options.assert_valid_keys :requires_new, :joinable

   last_transaction_joinable = @transaction_joinable
   if options.has_key?(:joinable)
     @transaction_joinable = options[:joinable]
   else
     @transaction_joinable = true
   end
   requires_new = options[:requires_new] || !last_transaction_joinable

   transaction_open = false
   begin
     if block_given?
       if requires_new || open_transactions == 0
         if open_transactions == 0
           begin_db_transaction
         elsif requires_new
           create_savepoint
         end
         increment_open_transactions
         transaction_open = true
       end
       yield
     end
   rescue Exception => database_transaction_rollback
     if transaction_open && !outside_transaction?
       transaction_open = false
       decrement_open_transactions
       if open_transactions == 0
         rollback_db_transaction
       else
         rollback_to_savepoint
       end
     end
     raise unless database_transaction_rollback.is_a?(ActiveRecord::Rollback)
   end
 ensure
   @transaction_joinable = last_transaction_joinable

   if outside_transaction?
     @open_transactions = 0
   elsif transaction_open
     decrement_open_transactions
     begin
       if open_transactions == 0
         commit_db_transaction
       else
         release_savepoint
       end
     rescue Exception => database_transaction_rollback
       if open_transactions == 0
         rollback_db_transaction
       else
         rollback_to_savepoint
       end
       raise
     end
   end
 end

If you study it, you can see the yield buried in the middle and work out that this method exists to do some work before and after the block, just like the combinator we constructed. This is the (current) idiomatic way to wrap some work with side effects executed before and after your code: write a method that takes a block and does the wrapping around the yield keyword.

The obvious challenge with this approach is that it is so ad hoc. having written code for database transactions, if you want to do something similar for persistent file storage (like open a file before using it and then close it when you're done), you need to write the wrapping code all over again. For example, if you wanted to write your own wrapper around Ruby's IO class that opened a file for writing before executing your block then flushed its buffers and closed the file at the end, you'd have to repeat the entire pattern.

As we saw in Refactoring Methods with Recursive Combinators and Practical Recursive Combinators, it is also possible to write Ruby combinators to encapsulate the pattern of wrapping a block explicitly when writing methods. We also saw in Aspect-Oriented Programming in Ruby using Combinator Birds that you can declaratively wrap a method using method advice. There are many roads to the summit :-)

More on combinators: Kestrels, The Thrush, Songs of the Cardinal, Quirky Birds and Meta-Syntactic Programming, Aspect-Oriented Programming in Ruby using Combinator Birds, The Enchaining and Obdurate Kestrels, Finding Joy in Combinators, Refactoring Methods with Recursive Combinators, Practical Recursive Combinators, The Hopelessly Egocentric Blog Post, Wrapping Combinators, and Mockingbirds and Simple Recursive Combinators in Ruby.


My recent work:

JavaScript AllongéCoffeeScript RistrettoKestrels, Quirky Birds, and Hopeless Egocentricity


(Spot a bug or a spelling mistake? This is a Github repo, fork it and send me a pull request!)

Reg Braithwaite | @raganwald