Lazy Ruby

Lazy Evaluation and Recursive Lists

In Haskell, it is possible to construct infinite lists via recursive definition. This is only possible because Haskell uses lazy evaluation rather than eager evaluation. Otherwise, the entire list would need to be calculated and the program would never terminate.

Because Haskell makes it easy to define lists and is lazy, the code for defining an infinite series is very simple. The following list represents the fibonacci sequence.

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

The list is defined recursively; the first two values are one, and every subsequent value is the sum of zipping the entire list with the tail of the list, evaluating to the sum of the two previous number for any position beyond the second. Pulling numbers off the list is as easy as the following.

> take 10 fibs
[1,1,2,3,5,8,13,21,34,55]

I was originally exposed to this concept while reading the book Programming Languages: Application and Interpretation which provides a more thorough introduction to the topic of lazy evaluation.

Spurious Examples and Limitations in Ruby

Ruby 2 introduced lazy evaluation to its Enumarable module, accessible via #lazy. The method returns a new instance of a lazy enumerator.

We can use these additions to create the same sort of infinite lists that are possible in Haskell. First, we start by generating a simple infinite series, upon which we can build further abstractions.

> inf = (1..Float::INFINITY).lazy
=> #<Enumerator::Lazy: 1..Infinity>

Now we have an enumerator, upon which we can build additional abstractions. In fact, you can represent any countable set using abstractions on this enumerator.

Unfortunately, Enumerator::Lazy#zip is limited, such that it is not possible to pass it a block without eager evaluation being triggered. This is easy, albeit inelegent, to circumvent by #maping subsequent to a #zip call. For instance, to get the sum of all adjacent numbers, the following never completes.

> adjacents = inf.zip(inf.drop(1)) { |a, b| a + b }

But by simply interposing a #map, it becomes possible.

> adjacents = inf.zip(inf.drop(1)).map { |a, b| a + b }
=> #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator::Lazy: 1..Infinity>:zip(#<Enumerator::Lazy: #<Enumerator::Lazy: 1..Infinity>:drop(1)>)>:map>

> adjacents.take(10).force
=> [3, 5, 7, 9, 11, 13, 15, 17, 19, 21]

Note that it is necessary to forece the evaluation, otherwise Ruby continues to return lazy enumerators to allow chaining.

Fibonacci in Lazy Ruby

We now have all the pieces we need to replicate the Haskell example. Ruby allows us to define a new infinite enumerator based on the original one, but lacks expressiveness for a few of the features Haskell as. As such, we need to map the infinite series onto another one using a block, which is analogous to defining a new infinite series, but does not read as cleanly.

Regardless of how well it reads, functionally, the following example accomplishes the same as the Haskell version.

> fibs = inf.map do |n|
    if n < 3
      1
    else
      fibs.zip(fibs.drop(1)).map { |a, b| a + b }.first(n - 2).last
    end
  end
=> #<Enumerator::Lazy: #<Enumerator::Lazy: 1..Infinity>:map>

> fibs.take(10).force
=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Fast & Lazy Fibonacci

This implementation is, unsurprisingly, painfully slow since it needs to reevaluate every single preceeding term in order to calculate a given term. This is a canonical issue with the naive recursive definition of fibonacci number calculations.

My original exposure to the following approach manipulates the fibonacci function by using a fixed point and a general memoization strategy based on the y combinator. For this particular example, a simple caching strategy will do, but it is worth knowing about the more general solution.

> fibs = -> {
    cache = []

    inf.map do |n|
      if cache[n]
        cache[n]
      elsif n < 3
        1
      else
        cache[n] = fibs.zip(fibs.drop(1)).
                        map { |a, b| a + b }.
                        first(n - 2).
                        last
      end
    end
  }.call

This allows us to calculate much higher values of the fibonacci sequence in a reasonable amount of time. Retrieving the 200th number happens instantly.

> fibs.take(200).force.last
=> 280571172992510140037611932413038677189525

Of course, this is not particularly idiomatic Ruby, since it uses a closure to bind the cache variable. It would be possible to rewrite this as a class (and I had, admittedly, originally done so), but the resulting code is over twice as long and amounts to a great deal of boilerplate and little else.

The way I see it, as long as we are abusing Ruby for its lazy evaluation, we may as well abuse it functionally as well.

Hooks in AngularJS Controllers

The Situation

Sometimes when working with nested scopes, you may encounter a situation in which some scope action depends on the status of some arbitarily nested controller. This could be a multi-part form built from reusable components, preventing the user from proceeding until complete, for example.

An architecture that allows scopes nested within another scope to influence the life cycle of the latter has one primary advantage, namely, greater separation of concerns. A nested controller can supply functions for data validation and formatting, while the parent controller defines functions for navigation and accumulation of results. This leads to better modularity, as the parent controller is isolated from the implementation of nested controllers, while the latter are able to be used modularly in more contexts.

A Simple Example

Open in Plunkr

As the structure of the following example indicates, we have three controllers - one that coordinates and two that handle user input. We have taken the liberty of using underscore to simplify checking if all conditions are met.

Here, the FormCheckboxCtrl has no validation, but does coerce its results to be human readible, while FormTextInputCtrl returns the text input and is invalid if none is provided.

What remains is, simply, to make it work.

<body ng-app="HookExample">
  <div ng-controller="FormPageCtrl">
    <p>Please enter some text below.</p>

    <span ng-controller="FormCheckboxCtrl">
      <input type="checkbox" ng-model="checkbox" />
    </span>

    <span ng-controller="FormTextInputCtrl">
      <input type="text" ng-model="textInput" />
    </span>

    <div ng-show="showResults()"></div>
  </div>
</body>
var HookExample = angular.module("HookExample", []);

HookExample.controller("FormPageCtrl", function($scope, RegisterHook) {
  $scope.showResults = function() {
    return RegisterHook("isDataValid", $scope, _.every);
  };

  $scope.results = function() {
    return RegisterHook("getResults", $scope, function(results) {
      return results.join(" - ");
    });
  };
});

HookExample.controller("FormTextInputCtrl", function($scope) {
  $scope.isDataValid = function() {
    return $scope.textInput && $scope.textInput !== "";
  };

  $scope.getResults = function() {
    return $scope.textInput;
  };
});

HookExample.controller("FormCheckboxCtrl", function($scope) {
  $scope.getResults = function() {
    return $scope.checkbox ? "Yes" : "No";
  };
});

A Hook Implementation

By recursively traversing the $$childHead and $$nextSibling properties of the scope, we can give ask if any controller nested within the heirarchy wishes to respond to the hook, thereby influincing the life cycle of our parent controller.

HookExample.factory("RegisterHook", function() {
  return function(name, scope, callback) {
    var results = [];

    (function traverse(scope) {
      if (!scope) {
        return;
      }

      if (_.(scope, name)) {
        results.push(scope[name]());
      }

      traverse(scope.$$childHead);
      traverse(scope.$$nextSibling);
    })(scope.$$childHead);

    return callback(results);
  }
});

This simple implemnation will look for and call the name function on any scope, starting from the $$childHead of the scope passed in. Once all the results have been accumulated, the callback is called with those results, allowing for a nice functional interface, as in the case of passing in _.every.

Since the callback is required in this naive implementation, it would be possible to pass in angular.noop as the callback to discard the results, thereby issuing some call to arbitrarily nested controllers. In that case, however, a more reasonable approach would be to $broadcast an event.

Hooks vs. Events vs. Services

When is this approach of registering hooks more appropriate than using events? Primarily when you need to get the data back from the user via collaborating controllers. The way event broadcasting requires an event to the child controllers, each of which must call another event for the parent controller to handle quickly becomes brittle. In cases where the data is not transient, it is likely best to use a service object to store all the data and have the collaborators reference it directly.

That said, there is certainly still a place for hooks like the one outlined above, but it is necessary to use it in appropriate situations. Littering our code with hooks that would be best treated as services for their persistence or events for their unidirectionality will not be an improvement.

But in cases where data transience and bidirectional collaboration between controllers at different levels of nesting is present, hooks reign supreme by exposing carefully selected points of interaction.

Improvements

Herein, we have only examined a very simple hooking mechanism, which can certainly be built out to have some additional interesting properties. Optional callbacks and the ability to handle arguments would be straight forward changes. More interesting is the possiblity to return more than just a single function for accumulating results, but instead having a more robust interface. This could include functionality akin to that in ActiveRecord callbacks, wherein returning false prevents future hooks from running and prevents some default action.