Some Readings on Mixins

05-27-2014 | programming languages

To me, Mixins were always a simple, stateless collection of loosely related methods that could be included in a class. I mean stateless in that they hold no state of their own, but rather that they assume a given state.

As an example, this is the perspective Ruby takes on the topic:

module TestModule

   def test
     puts 'hi'


 class TestClass
   include TestModule
irb> "hi"

Although quite simple, this perspective is misleading according to the classical definition of mixins. Modern mixin’s original definition came from a paper written by Gilad Bracha and William Cook, and their basis is this:

A mixin is an abstract subclass; i.e. a subclass definition that may be applied to different superclasses to create a related family of modified classes. For example, a mixin might be defined that adds a border to a window class; this mixin could be applied to any kind of window to create a bordered-window class.

The bulk of this research came from a paper that Richard P. Gabriel wrote that is actually about the philosophy of science / engineering, where context is all based around mixins. Because I’m obsessed, I went and read the bulk of all the papers he cites while illustrating his, “engineering comes first in computer science” theories. Although these posts won’t cover any of his fascinating perspectives on this philosophy, I’d still definitely recommend reading his paper. He also did a talk on the paper, or at least what inspired him to write the paper: incommensurability.

To begin the delving into mixins, according to Gabriel, we have to start with Warren Teitelman, a PhD candidate at MIT in 1966. More than twenty years before the seminal Bracha and Cook paper, Teitelman wrote his dissertation on a system called PILOT. PILOT uses something called Teitelman called advice. Here’s a reductionist explanation taken from the paper’s abstract:

Advising consists of inserting new procedures at any or all of the entry or exit points to a particular procedure (or class of procedures).

Teitelman’s thesis is verbose ~200 pages, of which I did not read even half. Though, in skimming through, I did stop and read all of chapter 5: Experiments With a Question Answer System. Using a couple of fairly complex logic problems based around a parallel to McCarthy’s Airport ProblemThis is not the googlable “airport problem”, this is why I’ve included the link to the paper where McCarthy first supposes the problem in 1959. One of the first of its kind.

, Teitelman shows how tests and protections (for example) can be predefined as advice, and then a function can use this advice either before or after its invocation. It is even possible for advice block a function from being invoked at all. The clearest example from the paper is still a little murky to me, even after a second and third read though, so rather than attempting to delve into the weeds, I’ll try and explain the best I can at a high level.

Let’s assume a function whose job is to solve a problem by recursively running itself, and, if just the right input is given, it can get stuck in an infinite loop. Using Teitelman’s advice, a programmer can predetermine some invariants to run at the functions entry and exit points to test something like, “how many times have I called myself?” or “have I adequately solved this problem and can I stop the recursive calls?”. The programmer writes these advice procedures in a generic way so that they can be reused by any number of functions who may meet the same requirements.

(tell solution1, (before number advice),
If (countf history ((solution1 -)) is greater than 2, then quit)

This is some code from the example above, where “number” is the number of times the recursive function has called itself:

The user tells PILOT to modify SOLUTION1. The phrase “(before number advice)” tells PILOT to insert this advice immediately before the advice containing the key word “number”.

The first thought to came to mind after skimming this paper was Python decorators. Though not exactly PILOT, I do see some strong similarities. Let’s take the example above, at least the part where we block a call to a function if its invocation count is greater than a pre-determined value. This requires a bit of an understanding of Python and its decoratorsPython decorators are this thing where functions can be passed as parameters to generic functions that utilize the call() method on the type Function. Reminds me, in a way, to a Ruby function that takes a block (Proc).

, but let’s just assume you “get it”, now that I’ve briefly described PILOT.

First we’ll set up a class whose constructor accepts a function and a count. The class then sets these properties as instance variables.

class Decorator(object):

    def __init__(self, func, count = 0):
        self.count = 0 or count
        self.func = func

Next, we’ll override the __call__() method on the class. This is the method that is invoked on a decorator.

def __call__(self):
     self.count += 1
     if self.count < 5:
         print 'not calling'

And last, we define a recursive method, and decorate it with our Decorator class.

 def recurse():
     print 'recurse called'

As expected, the decorator blocks the call once count is greater than five. Output:

recurse called
recurse called
recurse called
recurse called
not calling

On recurse()’s fifth invocation, it is not invoked, and the program exits. To me, this is exactly the type of invariant that Teitelman is describing in the PILOT examples. While not quite aligned with the modern perspective of multiple-inheritance based mixins, this is a clear precursor to the type of reusable, common functionality we understand as mixins today; at least on a much smaller (per function) scale.

(On a side note, how cool is that the same instance is passed to each call to Decorator. I was surprised that it was this simple to implement.)

Up next in the mixin rabbit trail is Flavors, another Lisp based precursor to the Bracha and Cook paper, similar in pattern (before and after), but quite different in concept.