Disable Your Links, or Gate Your Functions?

It’s pretty common to disable links and buttons that cause updates, so those updates don’t happen twice, and re-enable them when the update has finished.

At work, our app’s links are usually wired to javascript functions that use jQuery to scrape the form data and post it to web services via ajax. We normally disable links and buttons something like this:

var updateLink = $('#updateLink');  // Find the link.
updateLink.click(function() {       // When it's clicked...
   updateLink.disable();            // disable it...
   ajax({
      data: getFormData(),          // ... & send the form data
      url: 'http://someWebService', // to some web service.
      success: function(results) {  // When the service
         if (results.hasErrors) {   // finishes,
            showErrors(results);    // show any errors,
            updateLink.enable();    // and enable the link
         }                          // so they can try again.
      }
   });
});

We added those enable() and disable() functions to jQuery — they just add or remove the disabled attribute from whatever they’re called on. But it seems Firefox doesn’t support disabled on anchor tags, like IE8 does, so we couldn’t stop the repeat-calls that way.

We got to thinking, what if the link always called its javascript function, but the function could turn itself off after the first call, and back on after a successful ajax post? That led to this:

function makeGated(fn) {
   var open = true;
   var gate = {
      open: function() { open = true; }
      shut: function() { open = false; }
   };

   return function() {
      if (open) {
         fn(gate);
      }
   };
}

makeGated takes your function, and wraps it in another function, a gate function (it “makes your function a gated function”). When you call the function it creates, it will only call your function if the gate is open — which it is, at first. But then, your function can decide whether to close the gate (that’s why the gate is passed to your function). You could use it like this:

var updateLink = $('#updateLink');  // Find the link.
updateLink.click(
   makeGated(function(gate) {       // When it's clicked...
      gate.shut();                  // shut the gate...
      ajax({
         data: getFormData(),       // ...same as before...
         url: 'http://someWebService',
         success: function(results) {
            if (results.hasErrors) {
               showErrors(results);
               gate.open();  // Open the gate
                             // so they can try again.
            }
         }
      });
   }));

We dropped this in, and it worked pretty much as expected: you can click all you want, and the update will only fire once; when the update completes, it’ll turn back on.

The downside? Since it doesn’t disable the link, the user has no idea what’s going on. In fact, since the closed-gate function finishes so quickly, it seems like the button’s not doing anything at all, which might even make it look broken.

So we chucked it, and hid the links instead. It’s not as nifty, and it’s not reusable, but it’s clear enough for both end-users and programmers who don’t grok higher-order functions. Even when you have a nice, flexible language, and can make a sweet little hack, it doesn’t mean the dumb approach won’t sometimes win out.

Clojure Changing My Mind

As good as Processing is, it’s still java. I’ve slowly been learning clojure, and trying to use it with Processing, via clj-processing. While the clojure docs and the book are both good, I’m still in that flounder-around stage, trying out tiny experiments to understand how things work.

I wanted a function to make saw-step sequences: (1 2 3 2 1 2 3 2 …). You give it the low bound, the high bound, and the step-size. For example:

  • (saw-step 1 4 1) gives (1 2 3 4 3 2 1 2 3 4 3 ...)
  • (saw-step 0 15 5) gives (0 5 10 15 10 5 0 5 ...)
  • (saw-step 0 5 2) gives (0 2 4 5 3 1 0 2 4 5 ...)

I’ve coded this kind of thing up in ruby, javascript, or java a dozen times, though it’s usually inside a loop, not returning a list. Something like this:

var min = 3;
var max = 7;
var step = 2;

var n = min;
while(shouldContinue()) {
    doSomethingWith(n);
    n += step;
    if (n+step > max || n-step < min) {
        step *= -1;  // turn around
    }
}

My first try in clojure took a similar tack. I never got it right, but it was something like this:

(defn saw-step
  [min max step-size]
    (let [step (ref step-size)]
      (iterate
       (fn [x]
         (if (or ( min (- x @step)))
           (dosync (alter step -)))
         (+ @step x))
         min)))

It’s a disaster — the parentheses don’t even match — but you get the gist. I was trying to cram the same imperative algorithm into clojure: keep some mutable state, add step to it, and when you reach the edges, mutate step to change direction. I kept getting bugs where it would go one step beyond the edge, or it would start working its way back from one edge, only to turn around again, and bounce against the edge forever.

I gave up and went to bed, but a few days later, I had better luck.

(defn saw-step
  [min max step]
     (cycle
      (into (vec (range min max step)) ; vec, so (into) adds to end
	    (for [x
		  (iterate #(- % step) max)
		  :while (> x min)] x))))

The first not-entirely-wrong step I made was to try breaking the list of numbers I wanted into two parts: the going-up numbers, and the coming-down numbers. (0 2 4 5 3 1) is just (0 2 4) + (5 3 1). The (range min max step) part gives you the going-ups, and the (for [x (iterate ...) stuff is the going-downs, as a list comprehension.

(One mistake I made was trying (range max min step) for the going-downs, which yields an empty list; another was using (iterate dec max), which never ends, because it keeps decrementing into the negatives. I found my way out with the list comprehension, but I bet there’s a better way.)

Once you have those two lists, you can use into to add each item from the second list to the first, giving you (0 2 4 5 3 1). That goes into cycle for a lazy, infinite sequence.

The solution’s not too bad: a saw-step is a cycle of the going-ups, followed by the going-downs. The code looks about that way.

(It occurred to me after that I could always use a default step of 1, and pipe the result through a scaling map. That would give me the bounds I wanted, with the extra benefit of evenly-spaced steps. Maybe I’ll remove step later.)

Alan Perlis said, “A language that doesn’t affect the way you think about programming, is not worth knowing.” He also said, “The only difference(!) between Shakespeare and you was the size of his idiom list – not the size of his vocabulary.”  Clojure’s changing my mind, a bit at a time.

A JavaScript War Story

What follows is an account from the author’s experience. Some details have been changed for the usual reasons, and a poor memory has fuzzed out the rest.

UPDATE: it turns out the technique described below is known as debouncing. What an awesome name!

My last job was for a company that made case-management software. With this software, you could track all kinds of data about your case: you could categorize it, sub-categorize it, say where and when it happened, note whether it was still open, track who was responsible…all kinds of stuff, great for data fiends.

One of our customers’ favorite features was the reports, and they were pretty spiffin’. But, not being ones to rest on our laurels, we were adding pivot-table reports, so you could count the number of cases, grouped by any criteria you wanted. The input screen let the customer pick their pivot criterion, and which criteria they wanted as columns, for sub-counts. We struggled to name these UI fields — something lucid, something explanatory, something evocative — something to make them understand what kind of report they were in for. After a while, we decided to just show them: when they changed their pivot criterion, we’d run some javascript to render a skeleton report, same as the real report, but minus the data. It would save them time, and save our servers.

The javascript was pretty involved. It had to generate the same HTML as we did for the pivot table, which meant it had to know (or make up) values for each criterion, like all the case categories and sub-categories, and which sub-categories belonged to which categories. And we let the customers pivot on up to THREE, count ‘em, different criteria. And it had to happen each time the user picked different pivot criteria. It took a few tricks, but we got it working. It ran slowly, maybe a few seconds, but it was quick enough, probably, especially once we threw in a little “please wait” spinner. Then we realized we needed to re-render whenever the window resized.

No biggie, I thought, and I quickly added window.onResize(reportPreview);. It worked great, except it re-rendered the report with every pixel-wide movement of the mouse, as the window was dragged to new widths and heights. Calling a function, one that runs for a few seconds, a hundred times in the time it took to widen the browser an inch, meant a locked browser. It meant “time to get more coffee,” and after, “time to fix the bug.”

I knew we could delay calling reportPreview, but we only wanted to delay it when the window was being resized — when the user changed the columns, there was no reason to wait. I was sure window.setTimeout() would do what we needed, but I didn’t want to muck up reportPreview() with it.

I’d been reading The Little Schemer lately, and noticing some striking similarities between javascript and scheme: first-class functions, and higher-order functions that take functions as arguments, and return other functions as values. It was fun reading, with its strange teacher-student dialog style. The material was better than brainteasers, and I knew it would make me a better programmer down the road, but I didn’t think of it as relevant to the day-job, as…applicable.

Then I realized higher-order functions were a way out of this. I could write a function, delay, that would wrap one long-running, slow-poke function in another function: an intermediary that you could call as many times a second as you wanted, but it would only call the slow-poke once things had settled down. delay would let us keep setTimeout out of reportPreview. Something like this:

function delay(millis, slowPoke) {
    var timeoutId = undefined;

    // This is the intermediary.  Call it lots, it won't hurt.
    return function() {
        if (timeoutId) {  // If we're waiting...
            clearTimeout(timeoutId); // re-start the clock.
        }
        timeoutId = window.setTimeout(slowPoke, millis);
    }
}

The first time you call the intermediary, it tells the window to call slowPoke after a bit, but every time you call it after that, it starts the clock over. It’s like when you’re in a five-minute time-out, and you start acting up after only three, so your mom says “Ok, buster, another five minutes.”

var fiveMinutes = 5 * 60 * 1000;
var screamAndShout = delay(fiveMinutes, function() {
    getBackToPlaying();
});

screamAndShout(); // Aw nuts, I'm in time-out.

// I'll be good for as long as I can, but...
screamAndShout(); // dang, five MORE minutes!

Once delay was in place, running reportPreview when the window was resized was no problem.

function reportPreview() {
    // recursion, DOM manipulation, insanity...
}
columnPicker.onChange(reportPreview);
window.onResize(delay(100, reportPreview));

After testing, we found that delaying it for 100 milliseconds made all the difference in the world.

Do you have a war story? Share it, and start the healing: tell a short one in the comments, or link to a longer one on your own damn blog.

Higher-Order Functions and Function Composition, with Processing

I was looking for a good way to illustrate functional composition and higher order functions, and thought that something could be done with Processing, a java-based graphics tool. Among other things, Processing exposes raw pixel data for the images it renders, and you can update the pixels programatically, providing a simple kind of image filtering.

For example, here’s some code that converts a color image to grayscale. Just like with HTML, colors are represented1 as 3 channels (red, green, blue), and each channel has 255 increments. A gray pixel has equal amounts of red, green, and blue, so if you get the overall brightness of a pixel, and set its color to that much red, green, and blue, it should turn the image gray.

PImage img = loadImage("tattoo.jpg");
size(img.width, img.height);  // set the window size
image(img, 0, 0);  // render the image at x:y = 0:0

loadPixels(); // load the image's pixels into an array
for (int i = 0; i < pixels.length; i++) {
    // get the color for this pixel
    color c = pixels[i];

    // get its brightness
    float bright = brightness(c);

    // Change its color to its grayscale equivalent
    pixels[i] = color(bright, bright, bright);
}
updatePixels();  // render the new pixels to the screen

Here’s the original image:

the original image

…and here’s the filtered version:

the image in grayscale

You can define a bunch of routines like this, each looping through the pixels the same way, but adjusting the colors differently. But if you can separate the pixel-changing part from the pixel-looping part, then you can swap in ANY pixel-changing routine, giving you a flexible image filtering system.

The pixel-changing code is essentially a function that turns one pixel’s color into a new color, and the pixel-looping code uses it to replace each pixel’s original color. The pixel-changing function could be described like this:

color transform(color c) {
    ...
}

Many modern programming languages support first-class functions, which are a natural way to model this. Processing uses a form of Java, which doesn’t have first-class functions, but we can wrap the functions in a class, giving us an object called a functor. I called this one ColorTrans, for “color transformer”.

abstract class ColorTrans {
    public abstract color transform(color c);
}

The ColorTrans class’ only method, transform, is our pixel-changing function. We can re-write the loop from before to use a ColorTrans filter, and while we’re at it, we’ll move it into a method that takes the filename as a parameter, too.

void filterImage(String path, ColorTrans filter) {
    PImage img = loadImage(path);
    size(img.width, img.height);
    image(img, 0, 0);

    loadPixels();
    for (int i = 0; i < pixels.length; i++) {
        // use the filter parameter
        pixels[i] = filter.transform(pixels[i]);
    }
    updatePixels();
}

We can easily recreate the grayscale filter from earlier as a ColorTrans.

ColorTrans grayscale = new ColorTrans() {
    color transform(color c) {
        float bright = brightness(c);
        return color(bright, bright, bright);
    }
};

filterImage("tattoo.jpg", grayscale);

Another really easy filter to write is an inverter. If a pixel has R:100, G:30, B:255, an inverter will return the color R:(255-100), G:(255-30), B:(255-255), or R:155, G:225, B:0.

ColorTrans invert = new ColorTrans() {
    color transform(color c) {
        return color(255 - red(c),
                     255 - green(c),
                     255 - blue(c));
    }
};

filterImage("tattoo.jpg", invert);

The image produced by an inverter is like a film negative.

inverted, like a negative

Now we begin to see the benefits of keeping the-parts-that-change separate from the-parts-that-don’t: we can easily define and swap in new filters. This is one of the big parts of higher-order programming: writing routines that are configured by passing in functions (or functors, in this case) to do part of the work.

Manufacturing a ColorTrans

A useful kind of filter is one that increases (or decreases) the color on one channel: add some red, or remove some green. This kind of filter is easy to create:

ColorTrans aFifthMoreRed = new ColorTrans() {
    color transform(color c) {
    	return color(red(c) * 1.2, green(c), blue(c));
    }
};

This filter will increase the amout of red in the image by 20%. But 20% is a pretty arbitrary number; it’d be better if we could tell the filter how much to increase the red by. Generally, you’d add an “amount” parameter to the transform method, but then filterImage would have to know that this ColorTrans object takes an extra parameter. It’s kind of nice having filterImage treat all ColorTrans objects the same, just passing in the color.

Instead, we can make a method that builds ColorTrans objects: we tell it how much to increase the red by, and it builds a ColorTrans that does it for us.

ColorTrans ampRed(final float amount) {
    return new ColorTrans() {
        color transform(color c) {
            color(red(c) * amount, green(c), blue(c));
        }
    };
}

ColorTrans aQuarterMoreRed = ampRed(1.25);
ColorTrans aThirdLessRed = ampRed(2/3);
ColorTrans noRedAtAll = ampRed(0);

(If you’re curious why amount is final, the short answer is “because the compiler says so,” but there’s a better answer2.)

This is pretty nice, because we can use this inside an animation loop, animating the amount of color amplification.

float theta = 0.0;

void setup() {
    filterImage("tattoo.jpg", noChange);
}

void draw() {
    float ampRedAmount = sin(theta) * 1.2;
    filterImage("tattoo.jpg", ampRed(ampRedAmount));
    theta += 0.1;
}

[Here's where I'd link to the applet, nicely hosted somewhere, if I had a hosting service that allowed applets. I'll try to find a place to put all the code, so you can try it yourself.]

Processing calls setup to initialize the animation, and calls draw once per “tick”, to advance the animation. Here, in each frame of the animation, a new ColorTrans is constructed by ampRed, with the amount tied to the sine wave function, oscillating between 0 and 1.2. When viewed, the amount of red in the image swells and falls, and back again3.

This is another big part of higher-order programming: writing functions that build other functions, based on some arguments. Combined with routines that take functions as arguments, it’s a handy way to break down some problems. If done well, the routines that take functions as arguments, and the functions that build those functions, can become a sort of mini-language, a fluent interface, or almost an embedded DSL.

Plugging filters together – filter composition

This is where it gets fun. Suppose you’ve created an ampBlue that works just like ampRed, and now you want to filter an image with both of them. One approach might be something like this:

void draw() {
    filterImage("tattoo.jpg", ampRed(sin(theta) * 1.2));
    filterImage("tattoo.jpg", ampBlue(cos(theta) * 1.2));
}

Using the sine and cosine functions, the image should pulse nicely through reds and blues. The only problem is that it doesn’t really work, because filterImage loads the image fresh from the filesystem each time, so you only get the effect of the ampBlue filter. So how can we apply multiple filters?

We plug them together. We want a filter that does the work of two other filters, and we want it to look like any other filter, so filterImage won’t know the difference. To get this, we can add a method to ColorTrans that returns a new ColorTrans, which calls first the one, and then the other.

class ColorTrans {
    ...
    public ColorTrans then(final ColorTrans applySecond) {
        final ColorTrans applyFirst = this;
        return new ColorTrans() {
	    color transform(color c) {
	        return applySecond(applyFirst(c));
	    }
	};
    }
}

filterImage("tattoo.jpg", grayscale.then(invert));

first grayscaled, then inverted

Combining filters becomes a matter of chaining them together through then. The red-and-blue example becomes:

void draw() {
   filterImage("tattoo.jpg",
        ampRed(sin(theta) * 1.2).then(
            ampBlue(cos(theta) * 1.2)));
}

Processing does it kind of this way, too

If you look at the source for Processing, in PImage.java on line 619, you’ll find code that looks kind of like this:

  public void filter(int kind) {
    loadPixels();

    switch (kind) {
      case BLUR: ...
      case GRAY: ...
      case INVERT: ...
      case POSTERIZE: ...
      case RGB: ...
      case THRESHOLD: ...
      case ERODE: ...
      case DILATE: ...
    }
    updatePixels();  // mark as modified
  }

It basically does just what I’ve been doing, except the operations are hard-coded into the source, rather than being separated behind a class interface. The filters aren’t composable directly, though you can call a number of them in a row:

filter(INVERT);
filter(THRESHOLD);
filter(DILATE);

One benefit of this approach is that it’s easy to see, line-by-line, exactly what’s happening. I’d bet it beats the pants off of the ColorTrans version in benchmarks, too. But filters aren’t composeable, and it’s certainly not extendable. When you’re doing computation-intensive graphics, every bit of speed is important; when you’re illustrating a programming idea, it’s not. Decide for yourself which is more important for your needs.

____________________________________


1. It may seem weird, if you know Java, that the parameter’s type is color — it’s not a java primitive, but it doesn’t follow the normal classname conventions. It’s just the way Processing does it. You can read more about the color constructor in the Processing reference. [back]


2. Taken from the AnonymousInnerClasses page on the Portland Patterns Repository, 2009-04-30:

AnonymousInnerClasses can also be used to create something like closures in the JavaLanguage. However they do not “close over” the lexical environment so they aren’t TrueClosures. (They can capture the value of local variables, but they do not have access to the variable binding so they can’t change the original variable. Which Java makes quite clear by only allowing InnerClasses to refer to local variables that have been declared final (so no-one can change them)).

[back]


3. The noChange filter returns the same color it was given — an identity function. filterImage is called inside setup only so the window size is set correctly, since setting the size inside draw has no effect. And theta is just a Greek letter often used for angles and trigonometry.[back]

Heading to the Int’l Lisp Conf, 2009

My next step on the road to lisp is at the International Lisp Conference in Cambridge, MA, this March.

A lot of people are surprised to hear I’m interested in Lisp, but I’ve been studying scheme informally for about 3 years, reading SICP, and finishing The Little Schemer last year. I’ve been interested in clojure for about 18 months, especially after seeing Rich Hickey talk about it last March.  Now I’m studying it in earnest with Stu Halloway’s Programming Clojure.

I don’t use lisps of any sort at work, so it’s not a “practical” language to study like, say, C# is.  But that’s short-term thinking.  Learning lisp is plenty practical, if you’re looking longer-term — even if it’s only three years out.  Learning lisp teaches you about some of the core issues of programming.

I like learning lisp because it’s a window into the workings of programming languages, being so close to the AST.  I want to learn more about meta-programming with macros, hygienic or not.

And for the record, the functional techniques in The Little Schemer have improved my Ruby, JavaScript, and C# in some really solid ways. Functional programming is making its way to the rest of the programming world, and lisp does functional programming.

If you’ll be at the conference, I’d love to hear from you.

Trading Space for Speed: Memoizing with Ruby Facets

Recently, I talked about a faster, cheaper way to calculate Fibonacci numbers. One of the optimizations I made was to remember the value of each Fibonacci number: since F(7) is always 13, instead of recalculating it each time N=7, we can stuff 7 -> 13 into a look-up table for future reference. The function builds up a cheat-sheet, to avoid doing the re-work. It remembers.

This is called memoization, and it’s a nice way to trade memory for performance. But it only works when the function always returns the same answer for a given set of arguments — otherwise it’s first-in wins, forever. This property of a function, returning the same answer for the same args, is called referential transparency.

A Sample Implementation

There are lots of ways you could memoize a function. Hash tables are a natural choice, since they map a key to a value, just like functions map arguments to a value. Even if you implement it differently, a hash table is a good working model for memoization.

Let’s briefly consider factorials. The regular version:

class Unmemoized
    def factorial(n)
        puts n
        if n < 1
            1
        else
            n * factorial(n-1)
        end
    end
end

unmemoized = Unmemoized.new

5.downto(1) { |i| puts "\t#{unmemoized.factorial(i)}" }

…and the memoized version:

class Memoized
    attr_reader :factorial_memo
    def initialize
        @factorial_memo = {}
    end

    def factorial(n)
        puts n
        unless @factorial_memo.has_key? n
            if n < 1
                @factorial_memo[n] = 1
            else
                @factorial_memo[n] = n * factorial(n-1)
            end
        end

        @factorial_memo[n]
    end
end

memoized = Memoized.new

5.downto(1) { |i| puts "\t#{memoized.factorial(i)}" }

puts memoized.factorial_memo.inspect

Printing the hashtable is especially telling: {5=>120, 0=>1, 1=>1, 2=>2, 3=>6, 4=>24} It reads like a look-up table for factorials.

Memoization in Facets

As relatively easy as that example is, it has its drawbacks: we need to track our previous results in a separate variable, the memoization code is mixed up with the actual calculation (the part we care about), we can’t easily use it with other functions, and the pattern only works for functions of one argument. Facets makes memoization trivial, and removes all these issues.

require 'facets/memoize'

class FacetsMemoized
    def factorial(n)
        puts n
        if n < 1
            1
        else
            n * factorial(n-1)
        end
    end

    memoize :factorial # <= HINT
end

facets_memoized = FacetsMemoized.new

5.downto(1) { |i| puts "\t#{facets_memoized.factorial(i)}" }

In case you missed it, this is just like Unmemoized above, except we added line 13, memoize :factorial…that’s it. Just like attr_reader and friends, you can pass a list of symbols to memoize, and it’ll work on functions with any number of arguments:

require 'facets/memoize'

class MemoizedMath
    def add(n, m)
        n + m
    end
    def mult(n, m)
        n * m
    end
    memoize :add, :mult
end

When You Might Use Memoization, and What to Avoid

There are a number of places where this is useful: calculating a value by successive approximation, finding the path to the root node in an immutable tree structure, finding the Nth number in a recursively-defined series, even simple derived values (like ‘abc’.upcase). In general, a function is a good candidate if it only looks at its arguments (no global, class, or member variables, no files or databases) — especially if those arguments are immutable.

Relying on side-effects (printing to standard out, writing to a database or file, or updating a variable) in memoized methods is a bad idea: they’ll only happen the first time your method is called with those arguments, which is probably not what you intend. (Unless you’re printing the arguments to illustrate how memoizing works.) On the other hand, relying on side-effects is generally a bad idea anyway. Even if you don’t use a functional programming language, you can still benefit from minimizing state changes.

Further Reading

If memoization sounds interesting to you, you might like Oliver Steele’s article about memoizing JavaScript functions. If you’re curious about immutability, you might like this Joshua Bloch interview. If you’re interested in functional programming, there are worse places to start than the excellent Structure and Interpretation of Computer Programs. And of course, there’s more where that came from, in Ruby Facets.

Ruby Facets: Symbol.to_proc, Class.to_proc

One pretty well-know idiom in Ruby, and Facets, is Symbol.to_proc. It lets you turn these:

[1, 2, 3].map { |num| num.next }  #=> [2, 3, 4]

%w[alpha beta gamma].map { |word| word.upcase }
#=> ["ALPHA", "BETA", "GAMMA"]

…into these:

[1, 2, 3].map(&:next)
%w[alpha beta gamma].map(&:upcase)

It’s a nice little trick, though it’s not to everyone’s taste. If you’re already comfortable with Symbol.to_proc, you can skip down to the Class.to_proc section. But if you’re not, it’s worth a minute of your attention to learn it. Read on…

How it’s done

When a method takes a block, you can call yield, to run the block.

def with_a_block(a_param)
    yield
end
with_a_block('param') {
    puts 'in the block'
}

Or, you can name the block as the last parameter to the method, and put an ampersand in front of it. The ampersand makes ruby convert the block to a procedure, by calling to_proc on it. (So any object with a to_proc method can work this way, if you want.) This example works just like the last one:

def named_block(a_param, &blk)
    blk.call
end
named_block('my_param') {
    puts 'in the named block'
}

Symbol’s to_proc method creates a procedure that takes one argument, and sends the symbol to it. Sending a symbol to an object is the same as calling a method on it: object.send(:method) works the same as object.method. In the earlier upcase example, each word is passed to a procedure that calls upcase on it, giving us a list of uppercased strings.

&:upcase
# becomes...
lambda { |obj|
    obj.send(:upcase)
}
# or...
lambda { |obj|
    obj.upcase
}

Class.to_proc

So Symbol.to_proc creates a function that takes an argument, and calls that method on it. Class.to_proc creates a function that passes its argument to its constructor, yielding an instance of itself. This is a welcome addition to the to_proc family.

require 'facets'

class Person
    def initialize(name)
        @name = name
    end
end
names = %w[mickey minney goofy]
characters = names.map(&Person)

puts characters.inspect

&Person
# becomes...
lambda { |obj|
    Person.new(obj)
}

Why it’s nice

  • It’s fewer characters — it semantically compresses your code.
  • It lets you think, makes you think, on a higher level. You think about operations on your data, rather than handling one item at a time. It raises your level of thinking.
  • It works with first-class functions, which are worth understanding. They give you new ways to elegantly solve some problems (well, new to some audiences). They’re not fringe anymore — they’ve been in C# since v2.0.

Continuations: a warm-up

Continuations and continuation-passing style (CPS) are introduced in The Little Schemer, chapter 8, using collectors: functions that collect values, through being repeatedly redefined. It was a tough chapter for me, but the idea is simple once you get it, so I’d like to leave some help for others. I’ll use Ruby for the examples, with some JavaScript and Scheme at the end.

In languages with first-class functions, you can assign functions to variables, and re-assign those variables. Consider this Ruby example:

func = lambda { |x| puts x }

['a', 'b', 'c'].each { |ch|
    old_func = func
    func = lambda { |x| old_func[x + ch] }
}

func['d']  #=> prints 'dcba'

By re-defining func in terms of old_func, we’re building up a recursive computation. It’s like normal recursion, but approached from the other side — without explicit definitions. Since a Ruby function is a closure, it remembers the value of the variables in scope when it was created; each layer of this recursion holds its own value for ch and old_func. When we call the last func, it sees ch = ‘c’ and x = ‘d’. It concatenates them, and calls its version of old_func…which sees x = ‘dc’ and ch = ‘b’, concatenates them, and passes it to its old_func, and so on.In fact, if we wrote it like this, the execution of all those lambdas would be exactly the same:

func_puts = lambda { |x| puts x }
func_add_a = lambda { |x| func_puts[x + 'a'] }
func_add_b = lambda { |x| func_add_a[x + 'b'] }
func_add_c = lambda { |x| func_add_b[x + 'c'] }
func_add_c['d']  #=> prints 'dcba'

We could calculate factorials this way:

def factorial(n, func)
    if n == 1
        func[1]
    else
        factorial(n - 1, lambda { |i| func[i * n] })
    end
end
factorial(3, lambda { |fact| puts fact })  #=> prints 6
  1. On the first call to factorial, n = 3, and func just prints its argument. But func isn’t called yet…since n isn’t 1, we recurse with n - 1 = 2, and a new function that calls func with its argument i times 3.
  2. On the recurse, n = 2, and func calls the original printer func with its argument i times 3. Since n still isn’t 1, we recurse again, with n - 1 = 1, and a new function that calls our func with its argument i times 2.
  3. On the final round, n = 1, so we (finally!) call func with 1, which…
  4. …calls the previous func with 1 * 2, which…
  5. …calls the original func with (1 * 2) * 3, which…
  6. prints 6.

As factorial recurses, it builds up a recursive tower of func calls. In factorial‘s base case, the last (and outermost) func is called, and we begin to climb down the func tower, to its bottom floor, the original func. It’s recursion in two directions.

In case Ruby isn’t your favorite language, here are versions in JavaScript and Scheme:

function factorial(n, func) {
    if (n == 1)
        func(1)
    else
        factorial(n - 1, function(i) {
            func(n * i)
        });
}

factorial(3, function(fact) { print(fact) })
; Too bad WordPress doesn't format Scheme or Lisp!
(define factorial
  (lambda (n func)
    (cond ((= n 1) (func 1))
          (else (factorial (- n 1)
                           (lambda (i) (func (* n i))))))))

; Here, the original func is just an identity function.
(factorial 4 (lambda (fact) fact))

Once this is clear, you can see many other applications:

  • You could find all the even numbers in a list: instead of passing a number to func, pass the list of even numbers, and add each even number in.
  • You could separate the numbers into evens and odds: instead of passing just one list to func, pass two lists, for evens and odds, and add each number to the correct list.
  • You could separate any list of items by any criteria: instead of hard-coding “is even?” into the function, pass a predicate function. (Maybe you want to extract all occurrences of ‘tuna’ from a list of words.)

That should be enough of a warm-up for chapter 8. See you in chapter 9, when they derive the Y-combinator!

Why Functional JavaScript?

I’m teaching myself functional programming (FP). I first noticed it in Ruby, even though it’s been in JavaScript all along. I’m working my way through Structure and Interpretation of Computer Programs (SICP), and The Little Schemer books, so I’m learning Scheme and Lisp too.

When studying FP, I generally use JavaScript and Scheme. My FP examples here are usually in JavaScript:

  • It’s available everywhere, and most programmers are comfortable reading it.
  • It’s closer to Scheme than Ruby is, so the examples translate better. In fact, Douglas Crockford notes: “JavaScript has much in common with Scheme. It is a dynamic language. It has a flexible datatype (arrays) that can easily simulate s-expressions. And most importantly, functions are lambdas. Because of this deep similarity, all of the functions in The Little Schemer can be written in JavaScript.”

I include Ruby or Scheme, though, if it seems appropriate.

I often use the JavaScript Shell, or its big brother, the JavaScript Development environment, because I haven’t found or built a JavaScript REPL as nice as Dr. Scheme.

Performance

Most current JavaScript implementations are slow with recursion and closures…two cornerstones of functional programming.

I don’t worry about this, because my examples are not meant to be dropped into production systems without thought and testing. I write production-ready code at work; here, I play and explore. We do use some functional JavaScript where I work, but it’s where the performance is acceptable, and the imperative alternative would be too unwieldly.

History seems to show that performance is a short-term concern, and better programming techniques are a long-term concern. It also seems that there are no inherent reasons JavaScript is slow; more performant implementations may be in our future.

Why not Haskell or Erlang?

…or OCaml, Scala, F#, Clojure? I’m getting there. SICP and The Little Schemer books are more than enough for me right now.

Functional Programming in JavaScript and Ruby

[UPDATE: I’ve been lucky enough to have some commenters who know much more about functional programming than I do. There’s some good reading in the comments, and you especially should read them before using this stuff in production.]

I’ve been playing with functional JavaScript tonight. It’s not the greatest of OO-functional hybrid languages, but it’s good to supplant my fledgling functional skills with something besides Ruby. Plus, I’m not the only one doing it, so I can compare notes. And who doesn’t love JavaScript, right? …right?

Before I get much farther, I should thank Adam Turoff for his post What’s Wrong with the For Loop. It gets at the root of the why we’d use a functional programming language instead of an OO or procedural one, and (bonus!) it helped me grok Ruby’s inject method (it’s the same as my new friend fold). Go read his post, it’s good for you. And if you like it, we recommend the 1981 SICP lectures. Robusto!

Here we go!

Introductions to functional programming usually discuss three methods: map, find, and fold. The names aren’t always the same, but those are the three amigos of functional programming. They all do something different to arrays (or lists, or collections, or whatever you want to call them):

  • find does what it says. You give it some criteria, it returns all the matching elements. The criteria is expressed as a function, a little bit of code that says “yes, I want this one,” or “no, skip it.” If we’re picking out the red gumballs, you could say (in Ruby) gumballs.find_all { |ball| ball.isRed? } find is also known as filter. [Ruby only calls it find_all because it uses find for returning just the first match.] Po-tay-to, po-tah-to.
  • fold takes each element, and “folds” it into a running total. Think of summation—you’re folding each new number into a running tally. In Haskell (and, it seems, many functional languages), it comes in two varietes, fold_left and fold_right, which just mean “start from the left” and “start from the right”. Ruby calls it inject, which confuses some people (like me).
  • map is the mathiest of them (don’t be scared, it’s easy!). In English, we’d say “change each item like this, and give me the new results.” Let’s down-case a list of words. “Change each word to lowercase, and give me the downcased words.” words.map { |word| word.downcase }. The name “map” comes from functions in math (surprise), where you map each input to one output. The whole y = f(x) thing…f is for “function”. Ruby also calls this collect.

Now, none of these comes predefined in JavaScript. How can this be? Well, all the JavaScript engines out there are in browsers, and we know that “when browser elephants battle, it is the JavaScript grass that suffers.” The browser developers are busy with other things. But this oversight means we have some easy examples to write. It’s boring to re-implement existing stuff, just for the exercise. So here we go—I’ll compare examples in JavaScript and Ruby.

A quick word about JavaScript’s open classes

JavaScript has open classes, just like Ruby. In other words, you can re-open a class definition, give it a method, and then start using that method on instances of that class. JavaScript’s OO is prototype-based, not class-based, so it looks a little weird:

Array.prototype.first = function() {
    return this[0];
}
[1, 2, 3].first();  // 1

Array.prototype.rest = function() {
    return this.slice(1);
}
[1, 2, 3].rest();  // [2, 3]

Array.prototype.isEmpty = function() {
    return this.length == 0;
}
[].isEmpty();    // true
[1].isEmpty();   // false

“For the prototypical Array, the Array from which all other Arrays spring forth, create a property called ‘first’, which shall be this function, which returns the first element of the Array…” Just a Biblical way of defining a method for a class.

Open classes is good news, because it’ll make our job of adding map, find, and fold possible, since they’ll be going into the Array class.

Find

find is the easiest, so we’ll start there. Let’s take a look:

Array.prototype.find = function(isAMatch) {
    var matches = [];
    for (i = 0; i < this.length; i++) {
        if (isAMatch(this[i])) {
            matches.push(this[i]);
        }
    }
    return matches;
}

find is a function, and it takes the function isAMatch as a parameter. One of the hallmarks of the functional programming style is that functions are first-class citizens in the language: they can be treated like any other variable, so they can be passed around as parameters, and returned from other functions. [Closures and anonymous functions are also major features.] isAMatch is a function that tells you whether we should include any given element of the Array. Use find like this:

var evens = [1, 2, 3, 4, 5].find(
    function(i) {
        return i % 2 == 0;
    }
);

function isOdd(i) {
    return i % 2 != 0;
}
var odds = [1, 2, 3, 4, 5].find(isOdd);

The first example uses an in-line, anonymous function; the second uses a named function. Both work fine, but here is where we start to see JavaScript’s awkward syntax get in the way. Consider the Ruby version:

# find_all comes pre-defined in Array, via the Enumerable module,
# but this is what it would look like...
class Array
  def find_all
    matches = []
    self.each do |item|   # Ruby says 'self', not 'this'.
      if yield(item)      # yield says "Call the block we were given"
        matches.push(item)   # Stuff item into matches
      end
    end
    return matches
  end
end

evens = [1, 2, 3, 4, 5].find_all { |i|
  i % 2 == 0
}

def isOdd(i)
  i % 2 != 0
end

odds = [1, 2, 3, 4, 5].find_all { |i|
  isOdd(i)
}

In Ruby, every expression returns a value, so return disappears. And Ruby’s blocks mean we don’t need to wrap our match condition inside function(i) { ... }. But Ruby’s find_all won’t take a reference to a method as a parameter:

def isOdd(i)
    i % 2 != 0
end

odds = [1, 2, 3, 4, 5].find_all(isOdd)
# gives error: `isOdd': wrong number of arguments (0 for 1) (ArgumentError)

Once you’ve defined a function in JavaScript, you can pass it around by name, like any other variable, but you need that function(i) { ... } syntax around your test. In Ruby, find_all takes a block instead of parameters, so you can’t pass a reference. Given how nice blocks are in Ruby, I guess this can be forgiven, but it’s a little weird.

Fold

Now we’ll get into the recursive guys. find is a pain to implement recursively in JavaScript, so I did it iteratively, but recursion works well for fold and map. Since recursion seems to be more idiomatic in functional languages, we’ll use it here.

I took two shots at fold in JavaScript (I’m learning). Here they are:

Array.prototype.fold_recursive = function(combineFunc, base) {
    if (this.isEmpty()) {    // I added isEmpty, first, and rest, as above
        return base;
    }
    else {
        return combineFunc(
            this.first(),
            this.rest().fold_recursive(combineFunc, base));
    }
}

Array.prototype.fold_iterative = function(combineFunc, tally) {
    if (this.isEmpty()) {
        return tally;
    }
    else {
        return this.rest().fold_iterative(
            combineFunc,
            combineFunc(this.first(),
                        tally));
    }
}

The first is straightforward recursion. If the list is empty, we’re done, so return the base value (zero, if we’re adding). Otherwise, combine the first value with whatever the rest of the items fold up to. [If you have trouble writing recursively, this is the canonical pattern you should probably follow: if done, do base case; else, do this element, then the rest of them.]

The second is a little different. You’ve got a starting base, the tally so far, and a combineFunc that folds each value into the tally. If the list is empty, we’re done, so return the tally. Otherwise, fold the first item into the tally for the rest of the list.

It the first, you hang around, waiting for the answer to the rest of the problem, before you add in your part of the sum. In the second, you push your part of the sum down into the next round of processing, so you don’t have to remember anything. When the answer comes back from the recursive call, it’ll already have your part of the sum in it.

[The first one is a “linear recursive process”, the second is “linear iterative process”, even though both are recursive procedures. If your interest is piqued, check out this SICP page, but it’s not needed for this article. For the rest of this post, I’ll be using the linear recursive version, because it’s conceptually clearer. Thanks to mfp for keeping me honest.]

Here’s how fold is used:

// A handy adding function
function add(a, b) {
    return a + b;
}

Array.prototype.sum_recursive = function() {
    return this.fold_recursive(add, 0);
}
[1, 2, 3].sum_recursive();  // 6

To sum the elements of an array, we want to fold the numbers together by add-ing them, starting at 0. Easy, isn’t it?

Here are two Ruby versions, based on fold_recursive…one that takes a function (called a “procedure object” in Ruby) as a parameter, one that takes a block:

class Array
  def rest     # We'll define rest, to keep the examples similar
    self[1..-1]
  end

  def fold_w_proc(combineFunc, base)
    if self.empty?
      base
    else
      # "func.call(args)" instead of JavaScript's "func(args)"
      combineFunc.call(
        self.first,
        self.rest.fold_w_proc(
          combineFunc,
          base)
        )
    end
  end
  
  def fold_w_block(base, &combineFunc)
    if self.empty?
      base
    else
      combineFunc.call(
        self.first,
        self.rest.fold_w_block(
          base,
          &combineFunc)
        )
      end
  end

  def sum_w_proc
    fold_w_proc(lambda { |a, b| a + b }, 0)
  end
  def sum_w_block
    fold_w_block(0) { |a, b| a + b }
  end
end

[1, 2, 3].sum_w_proc    # 6
[1, 2, 3].sum_w_block   # 6

Notice how similar fold_w_block and fold_w_proc are to the JavaScript fold_recursive. The thing that differentiates fold_w_block and fold_w_proc is how they’re used. The definitions themselves are nearly identical, except for the order of the parameters. Look at sum_w_proc and sum_w_blocksum_w_block is a bit clearer, isn’t it? But if you use blocks, you lose the ability to pass a function reference as a parameter.

Map

map looks a lot like fold.

Array.prototype.map = function(mapFunc) {
    if (this.isEmpty()) {
        return this;
    }
    else {
        return [mapFunc(this.first())].concat(
                this.rest().map(mapFunc));
    }
}

function cube(i) { return i * i * i; }

[1, 2, 3].map(function(i) { return i * i; });  // [1, 4, 9]
[1, 2, 3].map(cube);  // [1, 8, 18]

Again, it’s basic recursion…if we’re out of items, return the empty list (ie, this). Otherwise, make an array of the first mapped item, and concatenate it with the rest of the mapped items. Again, with JavaScript, you can pass your function in-line, or by reference.

Here’s a recursive definition of map in Ruby:

class Array
  def map(&mapFunc)
    if self.empty?
      self
    else
      [mapFunc.call(self.first)] + self.rest.map(&mapFunc)
    end
  end
end

[1, 2, 3].map { |i| i * i }  # [1, 4, 9]

As before, calling map with a block certainly looks nicer than by passing in functions, but you lose the ability to define a function somewhere, and pass it in by name, like we did with cube in JavaScript.

Wrap-up

If you want to explore functional programming, both JavaScript and Ruby are good candidates. They both have their goods and bads. Up to now, I’ve only used Ruby, but JavaScript certainly has its benefits, and exposure to both balances out my understanding.

I hope that, if you were curious about functional programming before, this was a helpful read. If you’re a functional programmer, and I got something wrong, please let me know…I’m still learning. For instance, I now better understand how recursive processes differ from linear recursive processes.