Currying and Partial Function Application

August 21, 2009

Two related but different concepts that you will run into when doing functional programming are currying and partial function application. People often don't understand the different between the two, I didn't myself until recently, but I think I've got a handle on in now. Currying and partial function application are two different things, but they go together like peanut butter and jelly.

First, let's start with currying. Currying is the process of transforming a function that takes n arguments into a function that takes n-1 arguments and returns a function. What the hell does that mean? Let's look at an example in everyone's favorite functional programming language, JavaScript.

Here's a simple function that returns true if the first argument is greater than the second argument:

function gt(x,y) {
  return x > y
}

Pretty basic. If we call gt(3,2), that will obviously return true. If we call gt(2) though, we get false, because it ends up evaluating the expression 2 > undefined, which is false. So our gt function is pretty useless unless you pass it two arguments.

Now what if we write it like this:

function gt(x,y) {
  if(arguments.length > 1) {
    return x > y
  } else {
    return function(z) {
      return z > x
    }
  }
}

Now there is a lot of crazy lambda calculus going on here. If you pass two arguments to gt, it works as before, returns true if x is greater than y. But if you pass just one argument, this function creates a function that takes one argument and returns true if the argument is greater than x.

This is an example of a closure. We say the function that is returned "closes over" x, which just means that the function remembers what the value of x was at the time it was created, so when you call it later, it still uses that value.

So if we call gt(2), the result we get back is a function that returns true if the argument to it is greater than 2. This is called partial function application.

In functional programming, the correct term is actually not "call a function", but "apply a function to a set arguments". That's why in JavaScript when you want call a function with arguments that you have in an array, you use the apply function, like this:

gt.apply(null,[3,2]))

The first argument to apply is the object that the reference this should point to during the function call, and in this case we just pass null because we don't care about the this reference. The next argument is the set of arguments, 3 and 2, which become the first and second arguments to the call to gt.

So now the term partial function application makes sense, because we are applying a partial list of arguments to the function. Now it should be clear why currying and partial function application go together hand-in-hand. When you partially apply a function that is curried, you get something useful back. Partially applying a function that is not curried isn't usually useful, as we saw in the first example, where calling gt(2) resulted in evaluating the expression 2 > undefined, which is just silly.

So in the case of our curried version of gt, is the result of partially applying actually useful? Sure it is, when we combined it with other functional concepts. All good functional programming language have some kind of filter function, and JavaScript (well, JavaScript 1.6. Better late than never) is no exception.

Filter is a higher-order function (whew, we are busting out all the fancy functional programming words today, aren't we!). It is a higher-order function because it takes another function as it's argument. What filter does is allow you to take an array of elements and produce another array with only the elements than match some condition. The function that defines what the condition is is typically a predicate function.

So let's filter an array of number an only get the ones greater than 2. First we'll do it with an anonymous function as the predicate function:

[0,1,2,3,4,5].filter(function(e){
  return e > 2
})

That will result in an array with 3, 4 and 5 in it. That's a little wordy though. Let's use our curried gt as the predicate instead:

[0,1,2,3,4,5].filter(gt(2))

Ah, there we go, that's nicer. That's gives us 3, 4 and 5 as well. Of course you can just change the value of the argument to gt to filter for values greater than that number.

Now I should point that technically, our gt function is not in fact partially applied when we pass in less than two arguments, it just makes a new function. If we define gt like this:

function gt(x) {
  return function(y) {
    return y > x
  }
}

This means that gt always takes two arguments and returns a function that takes one argument. This still works the same in our filter example, [0,1,2,3,4,5].filter(gt(2)) does the same thing. But when you want to just call gt directly with two arguments, that doesn't fly. gt(3,2) now just ignores the second argument and returns a function the same way gt(3) would. If we want to simulate our two argument call, we have to make two function calls, like gt(2)(3), which looks hideous. Not only do we have two sets of parentheses, it is also has to be backwards. To ask is 3 > 2, we has to pass in 2 first in order to the "greater than 2" function, and then pass 3 to that.

Haskell has built-in syntactic sugar to make this look not hideous. Haskell is a statically-typed functional programming language. Being statically-typed means that variables are of a specifc type. JavaScript is the opposite, dynamically-typed. In JavaScript, when you have a variable or a function argument that is named x, x can hold any type of Object, a String, Number, Function, etc. In Haskell, when you define a variable or function argument, that must always be the same type. Haskell is actually pretty clever about it though. If you just say x = 42, it knows, ok, x is an Int. In other, less sophisticated statically-typed languages, you would have to say something like int x = 42.

When you look at the type signature of a function in Haskell, at first, it looks odd. For example, the type signature for our gt function might look like:

gt :: Int -> Int -> Bool

At first you think, what's with the arrows? Wouldn't something like this make more sense:

gt :: (Int, Int) -> Bool

Yeah, that matches what we are thinking. gt is a function that takes two Int values and returns a Bool. Well, even though you might think of it that way, that's not what it does in Haskell. In Haskell, all functions are curried. So our gt function is actually much closer to our last definition of gt in JavaScript, which looks like this:

function gt(x) {
  return function(y) {
    return y > x
  }
}

If you look at that for a minute, you'll agree that a type signature like this makes sense.

gt :: Int -> Int -> Bool

gt takes one argument and returns a function that takes one argument that returns a Bool. Unlike JavaScript, Haskell's syntax makes calling curried functions clean. So again, in JavaScript, we would have to do this to call our function:

gt(2)(3)

Which is the same as 3 > 2, but in Haskell if we want that, we simply just say 3 > 2. In Haskell, infix operators are actually function calls. 3 > 2 is syntactic sugar for (>) 3 2. Also in Haskell, you don't have to wrap the function call in parentheses to call it. The parentheses in this snippet are just the way of getting a reference to the infix function without calling it. If you could name a function > in JavaScript, the Haskell snippet (>) 3 2, or even 3 > 2, would be the equivalent of >(3, 2) in JavaScript.

So when we want to partially apply this function to get a function that returns true if the value is greater than 2, we just write (> 2). Haskell knows how to "do the right thing" with infix functions like greater than, so we don't have to deal with the problem of the arguments being backwards. So here's how we do the filter, and we can do it by partially applying the built-in greater than function (this is the advantage of > being a function, not an operator) to get the "greater than 2 function" to pass to filter:

filter (> 2) [0..5]

This, of course, results in the list [3,4,5]. So that's a whirlwind tour of a lot of functional programming concepts, but we can sum it all up with this:

A curried function is a function that will return a new function when it is applied to less arguments than it expects and applying a function to less arguments than it expects is called partial function application. So, stated even more succinctly, a curried function is a function that will return a new function when it is partially applied.

Posted in Technology | Tags Javascript, Currying, PartialFunctionApplication, Closures, Haskell, FunctionalProgramming | 4 Comments

This Just In: JavaScript is a Real Language

May 11, 2009

Some people think of JavaScript as that crappy language that runs inside of browsers. The truth is that the languages is not that bad, aside from a few warts (void, explicit return, global by default, I'm looking at you), it's pretty nice. I think it's gotten a bad rap for a few reasons.

First of all, the DOM. Before modern JavaScript libraries like jQuery and Prototype came along, developers were constantly pulling their hair out dealing with incompatibilities across different browser implementations of the DOM. Modern libraries have done a lot to normalize behavior across browsers and browser implementations have gotten better, but many developers still have bad memories of dealing with "JavaScript" back in the day. The truth was this wasn't really a problem in JavaScript the language, more so the DOM and browser implementations. If the language that Netscape put into the browser originally was Ruby, we would blame Ruby for all of these problems too.

Next, I think there was a whole class of Java developers upset that OO didn't work in JavaScript the way it did in Java. JavaScript wasn't considered a "real" OO language and was therefore inferior to Java. JavaScript has it's own way of dealing with OO and the sooner you understand how that works, the more comfortable you will be with JavaScript.

In the opposite way that many Java developers despised JavaScript, many Ruby developers, including Java developers converted to Ruby developers, started to appreciate JavaScript. JavaScript has anonymous functions just like Ruby has anonymous functions. Ruby makes ubiquitous use of anonymous functions through blocks. I think for many developers, Ruby was the first language they used that showed how useful anonymous functions can be. I think this is also the reason that you see some many Ruby developers interested other functional languages like Erlang, Haskell and Lisp.

Lastly, I think many developers don't see JavaScript as a general purpose language simply because it's trapped inside the browser. You can't run a JavaScript script from the command line just like you can run a Ruby, Python or Perl script.

Well, it turns out that last one isn't true and I want to show you how to get started writing some JavaScript as a "real" language, and specifically, a functional language.

The first thing you'll need is a JavaScript interpreter. There are many JavaScript interpreters available, such as:

  • SpiderMonkey, the C-based JavaScript interpreter for the Mozilla Gecko rendering engine
  • V8, the C++-based JavaScript interpreter for the Google Chrome browser
  • Rhino, the Java-based JavaScript interpreter.

Let's go with SpiderMonkey.

If you are on a mac and you want to get up and running with SpiderMonkey, the easiest thing to do is sudo port install spidermonkey.

If you want to build it from source, download the tarball and untar it somewhere on your machine. I did that in the src directory in my home directory. Then you go into the js/src directory and run the make command. Here's what that looks like:

cd ~/src
wget http://ftp.mozilla.org/pub/mozilla.org/js/js-1.8.0-rc1.tar.gz
tar xvzf js-1.8.0-rc1.tar.gz
cd js/src
make -f Makefile.ref

Now you should have a directory like Darwin_DBG.OBJ, it will be named differently if you aren't on a Mac. Inside that directory there is a js program you can run. To make life easier, add ~/src/js/src/Darwin_DBG.OBJ to your path, or create a symlink in /usr/bin to ~/src/js/src/Darwin_DBG.OBJ/js.

Now either way, whether you installed spidermonkey via mac ports or from source, you should be able to just type js from the terminal and be at an interactive JavaScript interpreter, with js> as the prompt:

$ js
js> print("Hello, World")
Hello, World

You can also run js my_awesome_script.js to run a script saved in a file. I have created a textmate bundle that has a run command for javascript files. If you install this, then you can press Cmd-R to see the output of the file.

So now let's write a little JavaScript. First things first, open a file called hello.js in Textmate and put this into it:

print("Hello, World!")

If you've created the command properly, you should see Hello, World! printed out. If you aren't using Textmate, then you will have to figure out how to get your editor to run the file. Even if you can't do that, it's as simple as running js hello.js from the command line.

Now we can write some real code. What we want to focus on doing is functional programming. Most of the basic functions for functional programming aren't defined in JavaScript by default, but it's easy enough to write our own that handle the basic things. Note that this kind of functional programming is going to be functional in that we are going to pass functions to and return functions from functions, a.k.a higher-order functions, but we aren't going to focus on other popular aspects of functional programming such as immutable data and pure functions. Baby steps. :)

So the first thing we need is some kind of implementation of an iterator function, because we're not writing for loops. Let's do something like Ruby's each:

function each(f, arr) {
  for(var i=0; i < arr.length; i++) {
    f.apply(null, [arr[i]])
  }
}

What this does is take a Function and an Array and applies the Function to each element of the Array. To test this out, let's also add this line of code to test it:

each(print, [1,2,3,4,5])

You can see that we can pass the print function to each and have it print the numbers from 1 to 5. Ok, next up is map, which takes a Function and an Array and returns a new Array which contains the result of applying the Function to each element of the Array.

function map(f, arr) {
  var result = []
  each(function(e) {
    result.push(f.apply(null, [e]))
  }, arr)
  return result
}

We can test that out with:

print(map(function(e){
  return e * e
}, [1,2,3,4,5]))

This time, we are passing an anonymous Function as the first argument to the map Function. This Function takes one value and multiplies it by itself, better know as square. Now for our last trick, we will do the functional programming equivalent of hello world, fibonacci:

function fib(n) {
  if(n <= 1) {
    return n
  } else {
    return fib(n-1) + fib(n-2)
  }
}

We can test this with:

each(print, map(fib, [1,2,3,4,5,6,7,8,9,10]))

Here's the entire code in one gist.

Now that JavaScript is being viewed as a "real" language, it's even got it's own conference! There's also some IRC channels devoted to JavaScript as well and of course, Stack Overflow. Happy JavaScripting!

Posted in Technology | Tags V8, Javascript, Rhino, SpiderMonkey | 6 Comments

Adding Your Own Methods to jQuery

November 21, 2008

Lately, when doing dynamic/AJAX JavaScript stuff, I've been using the jQuery library. It's pretty easy to use as a drop in replacement for Prototype in Rails. If you do start using jQuery, make sure to download the jquery api browser for offline browsing of the jQuery docs. Not only is it much faster and handy to have when you are offline, I've found the main jQuery documentation site to be somewhat unreliable. They're probably just having a hard time handling all the traffic they are getting to due to the increased popularity of the library. Also check out the most recent Railscast, which covers using jQuery with Rails.

In that episode, Ryan shows you how to define a jQuery function to make submitting forms with AJAX easier. I'm going to show a couple more function you can add to make manipulating drop-down menus (HTML select/option element) a little easier. What I'm doing is having the contents of one drop-down updated when the value in another drop-down changes. Here's the code with standard jQuery:

<% content_for :html_head do %>
  <script type="text/javascript">
    jQuery(function($){
      var categoriesByType = <%= CategoryType.category_map.to_json %>
      $("#category_category_type_id").change(function(){
        $("#category_parent_id option").remove()
        $.each(categoriesByType[$(this).val()], function(){
          var option = $(document.createElement("option"))
          option.attr('value', this[1])
          option.html(this[0])
          $("#category_parent_id").append(option)          
        })
      })
    })
  </script>
<% end %>

There's a lot going on, so I'll go through it step-by-step. But before I do that, let me explain what this code does. This is used on a form to create a new category. Each category has a parent and a type. The form has 2 HTML select elements (drop-down menus), one of the category types and another for the category parent. The list of possible parents should be limited to categories within the selected category type.

So, first we are using the Rails content_for method to have this whole chunk end up in the head of the HTML document. I have a <%= yield :html_head %> defined at the end of my HTML head in the layout. Next, we use the syntax jQuery(function($){ ... }) to define a chunk of JavaScript code that executes on the DOM is ready.

Inside that function, the first thing we do is create a variable that is a map (Strictly speaking, it is a JavaScript Object, but JavaScript objects act as an associative data type). We call a method on our Rails model to get the data, and then call to_json on it to format the data as JavaScript. The structure of this data is that the key is the category type id and the value is an array of array. Each array is the category path and category id. This structure makes it easy for us to replace the set of options in the parent drop-down each time the value in the category type is changed.

So we define a function to be executed on change of the category type drop-down. The first thing that function does is remove all of the options from the category parent drop-down. Then, for each value we get in the array that maps to the currently selected category type, we want to append an option tag to the category parent drop-down.

So all of this works as advertised, but the one thing I don't like is there is a lot of code, 4 lines, just to create and append a new option tag. Let's shorten that up, so our new syntax looks like this:

<% content_for :html_head do %>
  <script type="text/javascript">
    jQuery(function($){
      var categoriesByType = <%= CategoryType.category_map.to_json %>
      $("#category_category_type_id").change(function(){
        $("#category_parent_id option").remove()
        $.each(categoriesByType[$(this).val()], function(){        
          $("#category_parent_id").appendElement("option", this[0], {value: this[1]})
        })
      })
    })
  </script>
<% end %>

The only part that has changed is the body of the each. As you can see, we are going to define a new function that operates on a jQuery set of elements. jQuery refers to this as a method, just to give it a name to differentiate it from a typical function that is just in the jQuery namespace. So to implement this, we are going to actually define a function and a method. First, we define a function that simply creates a new DOM element, and second, a method that uses the same syntax, but appends the element to the jQuery set:

//You can call this a few ways:
//createElement('p') => "<p/>"
//createElement('p','hi') => "<p>hi</p>"
//createElement('p', {align: 'center'}) => "<p align="center"/>"
//createElement('p','hi',{align: 'center'}) => "<p align="center">hi</p>"    
$.createElement = function(tag_name, tag_value, tag_attrs) {
  var name = tag_name
  if(typeof tag_value == "object") {
    var value = null
    var attrs = tag_value
  } else {
    var value = tag_value
    var attrs = tag_attrs
  }
  var element = $(document.createElement(tag_name))
  if(attrs) {
    $.each(attrs, function(k,v) {
      element.attr(k,v)
    })
  }
  if(value) {
    element.html(value)
  }
  return element
}

$.fn.appendElement = function(tag_name, tag_value, tag_attrs) {
  var element = $.createElement(tag_name, tag_value, tag_attrs)
  this.append(element)
}

First there is the createElement function that is defined on $, then there is the appendElement method, that is defined on $.fn. The appendElement method isn't really needed, because you could accomplish the same thing with just append and createElement:

$("#category_parent_id").append($.createElement("option", this[0], {value: this[1]}))

But I just wanted to illustrate the different between a jQuery function and a jQuery method. A jQuery function is called on just $ object (which happens to be a function), whereas a jQuery method is called on the result of calling the $ function.

Posted in Technology | Tags Javascript, jQuery | 2 Comments

JavaScript: Global By Default

September 1, 2008

Here's a very simple JavaScript function that prints the sum of its arguments:

function sum() {
  s = 0;
  for(i=0; i < arguments.length; i++) {
    s += arguments[i];
  }
  return s;
}
document.write('sum = '+sum(1, 2, 3));

Looks simple enough. Translated directly into non-idiomatic Ruby, that would be:

def sum(*args)
  s = 0
  i = 0
  while i < args.length
    s += args[i]
    i += 1
  end
  s
end

So let's say you now want your sum function to return the sum of the factorial of each number. No problem:

function sum() {
  s = 0;
  for(i=0; i < arguments.length; i++) {
    s += factorial(arguments[i]);
  }
  return s;
}
function factorial(n) {
  f = 1;
  for(i=1; i <= n; i++) {
    f *= i;
  }
  return f;
}
document.write('sum = '+sum(1, 2, 3));

Oops. That prints 1, but the answer we were looking for was 9. Hmmm, let's translate it to ruby and see what we get:

def sum(*args)
  s = 0
  i = 0
  while i < args.length
    s += factorial(args[i])
    i += 1
  end
  s
end
def factorial(n)
  s = 1
  i = 1
  while i <= n
    s = s * i
    i += 1
  end
  s
end
puts sum(1, 2, 3)

Ok, so Ruby gives us 9. So what's up? The truth is that is not a direct translation. Here's the correct translation:

def sum(*args)
  $s = 0
  $i = 0
  while $i < args.length
    $s += factorial(args[$i])
    $i += 1
  end
  $s
end
def factorial(n)
  $s = 1
  $i = 1
  while $i <= n
    $s = $s * $i
    $i += 1
  end
  $s
end
puts sum(1, 2, 3)

This gives us the same result as the flawed JavaScript, which is 1. As you can see, in both functions, the variables s and i are declared as global variables, which you can tell by the $ sigil. But in JavaScript, variables are global by default. That's right, the simple little innocuous-looking i=0 in our JavaScript for loop defines a global variable. Here is the corrected JavaScript version:

function sum() {
  var s = 0;
  for(var i=0; i < arguments.length; i++) {
    s += factorial(arguments[i]);
  }
  return s;
}
function factorial(n) {
  var f = 1;
  for(var i=1; i <= n; i++) {
    f *= i;
  }
  return f;
}
document.write('sum = '+sum(1, 2, 3));

The moral of the story is always prefix your variable declarations with var. If you are a web developer who writes JavaScript and this is news to you, stop what you are doing an read Douglas Crockford's JavaScript: The Good Parts.

Posted in Technology | Tags Javascript | 2 Comments

Using Lowpro To Create Autotab using Unobtrusive JavaScript and Rails

April 19, 2008

In the last article, I showed how to use composed_of to create a class to handle phone numbers. In this article, I'll show how you can use Unobtrusive JavaScript to make a spiffy interface for entering phone numbers. So first, here's the code we want for phone numbers:

Phone Number
<% f.fields_for :phone_number do |pn| %>
  (<%= pn.text_field :area_code, :size => 3, :class => "autotab" %>)
  <%= pn.text_field :prefix, :size => 3, :class => "autotab" %>
  -
  <%= pn.text_field :line_number, :size => 4, :class => "autotab" %>
  ext
  <%= pn.text_field :extension, :size => 4 %>
<% end %>

This goes in the form view code for the users resource. What this does is render separate fields for each part of the phone number. If you've generated the scaffolding for the users resource, you should be able to stick this in there and be able to create users with phone numbers using this form.

So that's nice, but it would be neat if we could have the cursor automatically jump from one field to the next once the correct number of digits have been entered? We've already got the first step of that in there by putting the class "autotab" on each of the first 3 fields. That is as much code as we are going to add into the actual view. We are going to do the rest unobtrusively, some might even say, Ninja-style.

The first step is to download Lowpro and put it into your public/javascripts directly. Lowpro is a library that enhances Prototype to make unobtrusive JavaScript easier. Once you've got that, make sure to include the javascript libraries in your layout:

<%= javascript_include_tag :defaults, "lowpro", "autotab" %> 

Autotab is a JavaScript file that we are going to create specifically for the purpose of providing the "autotab" functionality, which is the name I'm giving to the feature where the cursor will automatically move to the next field once the correct number of characters have been entered. The correct number of characters is determined from the size attribute of the input field. For staters, make sure you have firebug installed and enter in this code to public/javascripts/autotab.js:

Event.onReady(function() {
  console.log("These are a few of my favorite things:");
  $$('input.autotab').each(function(e){
    console.log(e);
  });
});

When you load the form, you should see the output in the firebug console, with the 3 inputs that have the autotab class. This doesn't do anything interesting at this point, but just shows the basis of how unobtrusive JavaScript works. There are no event handlers directly inline in the HTML code, instead some JavaScript code execute once the page has finished loading and adds functionality to DOM elements based on something like their CSS class.

So in order to introduce the functionality we want, we'll use Lowpro's addBehavior method, which attaches an event handler to elements that match a given CSS tag. Replace the contents of public/javascript/autotab.js with this:

Event.addBehavior({
  'input.autotab:keyup' : function(e) {
    if(e.keyCode != 9 && e.keyCode != 16) {
      if(e.target.value.length == e.target.size) {
        e.target.next().focus();  
      }      
    }
  }
});

So once the page has loaded (or the DOM is "ready", I should say more correctly), this will attach this function to the keyup event handler of all of the elements on the page that match the CSS selector input.autotab. In the function, we first make sure the key being released isn't tab or shift. This is because if you are filling out the form and you press shift+tab to go back to the previous field, you don't want it to jump ahead, because you must want to edit that field if you are going back to it. After that if statement we just check to see if the length of the value in the input field matches its size. If it does, then we call next() on the target to get the next field, and call focus() to change the focus to that field.

Posted in Technology | Tags Javascript, Autotab, Ruby, Lowpro, Unobtrusive, Rails, CSS | 2 Comments

<< Newer Articles   Older Articles >>