PaulBarry.com

Performance Testing with Httperf

mail@paulbarry.com (Paul Barry) — Tue, 10 Nov 2009 11:56:27 -0500

If you need to do some performance testing of your web app, one tool that is pretty easy to use is httperf. I recommend watching the Peepcode screencast on httperf to get some good tips on how to doing performance testing. There is also some reading material on httperf created by Ted Bullock available. These are great resources, but here's the quick and dirty on how to get httperf going.

First, to install httperf, if you are using Macports, you can simply do sudo port install httperf, which is what I did. Alternatively, you can get httperf from the httperf download page.

Once you've got it installed, make sure the site you are testing on is running with all the production settings turned on. The Peepcode screencast goes into detail about how to do that for a Rails app. Then, if you are trying to test the /profile page on myfancysocialnetwork.com, you would run a command like this:

httperf --server myfancysocialnetwork.com --port 80 --uri /profile --num-conns 100

This will hit the profile page 100 times and report back with statistics like the minimum response time, maximum response time and the average response time, including standard deviation. You will certainly want to adjust the --num-conns option based on the page you are testing. If it's a pretty slow page with response times over a second or two, then 100 is probably ok. If it's a more well behaved page that renders in a few hundred milliseconds, then a large number like 10000 might be better. The goal is to make sure that it runs long enough to generate enough samples to make the results statistically relevant. You'll also want to read the documentation/watch the screencast to get info on other options like rate to create different kinds of test scenarios.

How To Write A Spelling Corrector In Ruby

mail@paulbarry.com (Paul Barry) — Thu, 05 Nov 2009 02:06:58 -0500

If you haven't seen it before, Peter Norvig has a spelling corrector that is written in just 21 lines of Python code (not counting blank lines and the import). He also lists a few other implementations in other languages, include one in Ruby. The Ruby one was listed as 34 lines. I was surprised that it was that many lines more in Ruby, so I wanted to give it a try. I didn't look at the Ruby solution first and here's what I came up with:

require 'set'

def words(text)
  text.downcase.scan /[a-z]+/ 
end

def train(features)
  features.inject(Hash.new(1)){|model, f| model[f] += 1; model }
end

NWORDS = train(words(File.open('big.txt').read))

ALPHABET = 'abcdefghijklmnopqrstuvwxyz'.split //

def edits1(word)
  s = (0..word.size).map{|i| [word[0,i], word[i,word.size]]}
  deletes    = s.map{|a,b| !b.empty? ? a + b[1..-1] : nil}.compact
  transposes = s.map{|a,b| b.size > 1 ? a + b[1].chr + b[0].chr + b[2..-1] : nil}.compact
  replaces   = s.map{|a,b| !b.empty? ? ALPHABET.map{|c| a + c + b[1..-1]} : nil}.flatten.compact
  inserts    = s.map{|a,b| ALPHABET.map{|c| a + c + b}}.flatten
  Set.new(deletes + transposes + replaces + inserts)
end

def known_edits2(word)
  s = edits1(word).map do |e1| 
    edits1(e1).map{|e2| NWORDS.include?(e2) ? e2 : nil}.compact
  end.flatten
  s.empty? ? nil : Set.new(s)
end

def known(words)
  s = Set.new(words.find{|w| NWORDS.include?(w)})
  s.empty? ? nil : s
end

def correct(word)
  candidates = known([word]) || known(edits1(word)) || known_edits2(word) || [word]
  candidates.max{|a,b| NWORDS[a] <=> NWORDS[b] }
end

To run this, download the data file, put the code in a file called spelling.rb, then start up IRB:

$ wget http://norvig.com/big.txt
$ irb -r spelling -f --simple-prompt
>> correct "speling"
=> "spelling"
>> correct "korrecter"
=> "corrected"

This one weighs in at 30 lines. I tried to do this as close to the Python implementation as possible. I also tried to use idiomatic Ruby. You could shave the number of lines down below 21, but it wouldn't meet any reasonable Ruby style guidelines. I'm still probably cheating a little as a few of those lines are approaching 100 characters, but it's at least reasonable, in my opinion. Here are some things I noticed that caused the Ruby version to be longer or less clear:

end vs. significant indentation

6 of the lines are just an end statement. Python uses indentation to end methods, so the end statements aren't needed in Python. This adds more lines, but has trade offs. I actually really like the idea of significant indentation, it's one of the reasons that I'm such a big fan of Haml. But it falls down in certain places. For example, Ruby has Embedded Ruby, which looks similar to JSP or PHP, but it's actually trivial to implement the basic cases. It truly is embedded Ruby, because the code between the <% %> and <%= %> tags is just ruby code. You commonly see things like this:
```
<% if logged_in? %>
  Welcome, <%= current_user.login %>
<% else %>
  Howdy Stranger!
<% end >
```
You can't do this in Python because of the lack of the end statement. This is why I'm surprised Haml was invented in Ruby and not Python. In Python, it fits with the language and is actually necessary, whereas in Ruby, significant indentation isn't part of the language and ERB is actually pretty good. There is a Python port of HAML, but I'm not sure how well that works or how widely it is used in the Python community.
List Comprehensions vs. Blocks

Python and Ruby, compared to C, Java, etc., have very powerful, concise syntax for iterating through and transforming collections, but they are very different. Python uses list comprehensions and Ruby uses blocks. As you can see above, there are certain cases where list comprehensions are very compact. List comprehensions can have a guard, which is a little cleaner than the Ruby equivalent where you have to return nil if the guard doesn't match and then compact that result. Also, when you want to iterate over two lists, you can do so with mutliple for statements, whereas in Ruby you do nested blocks and then flatten the result.
Collection Slicing

Python has a little cleaner, more consistent syntax for breaking up collections into sub collections. It also treats strings as a collection of characters more consistently.
Truthiness

In Python, many things are considered false. I'm not sure what the entire list is, but it seems to include empty collections (and therefore empty strings) as empty. Since Ruby only treats nil and false as false, we have to return nil instead of an empty set from the known and known_edits2 methods, so that the series of statements in the first line of the correct method will work correctly.

In summary, in this case, the Python code is shorter and clearer, but it's pretty close. I'm sure there are other code examples where the Ruby code would be a little shorter, but I do think in general, Ruby and Python are going to be pretty close in terms of code clarity and number of lines of code.

Ain't Nothing But A G Thang

mail@paulbarry.com (Paul Barry) — Fri, 09 Oct 2009 01:05:52 -0400

You've probably seen more than a few articles on the web showing how to build a Rack app. If not, here's a good one to start with. You'll quickly see that building a Rack app is really simple, which is why Rack is awesome, because it's simple. But what about writing a Rack-compliant server? Well it turns out that is pretty easy as well.

I just pushed a little Rack-compliant HTTP Server that I wrote using GServer to github. The whole thing is less than 200 lines of code. The core of it is short enough that I can explain how it works here.

First, GServer. GServer, which is short for "Generic Server" makes it pretty simple to create a multithreaded TCP Server. Taking out some error handling code, here's what the GServer looks like for our Rack HTTP Server:

module GThang
  class HttpServer < GServer

    attr_reader :port, :rack_app

    def initialize(options={})
      @port = options[:Port] || 8080
      @rack_app = options[:rack_app]
      super(@port)
    end

    def serve(socket)
      RackHandler.new(socket, rack_app, port).handle_request
    end

  end
end

So all there is to a GServer is basically a serve method. This will be called each time a client connects to the server. The argument to the method is the client socket connection. You read and write data from the socket as you see fit for your application. As you can see here, we just pass the socket, along with the rack app and the port to the RackHandler initializer and then call handle_request on that. We'll look at how you setup the rack app in a minute, but first let's take a look at the meat of what the RackHandler does. The handle_request method looks like this:

def handle_request
  return unless add_rack_variables_to_env
  return unless add_connection_info_to_env
  return unless add_request_line_info_to_env
  return unless add_headers_to_env
  send_response(app.call(env))
end

So what happens is the various add_ methods build up the rack environment. Once the environment is ready, we call the rack app. The rack app responds with the standard 3 element array, which we pass off to the send_response method, which writes the actual http response to the client. Take a look at the full code for this on github for the details.

Now the fun part is that we now have a fully functional HTTP server that is capable of acting as a file server or serving a Rails app. All we have to do is give the HttpServer the correct Rails app. If you look in the examples, you see this for the file server:

GThang::HttpServer.run(
  Rack::CommonLogger.new(
    Rack::Lint.new(
      Rack::Directory.new(root, Rack::File.new(root)))),
  :Port => 8080)

Now I choose to write it this way to make it clear what is actually happening. You will normally see the builder DSL used to configure a rack app, which would look like this:

use Rack::CommonLogger.new
use Rack::Lint.new
use Rack::Directory.new(root)
run Rack::File.new(root)

This is obviously a lot cleaner, but to understand how Rack works, you have to realize that all this is doing is what we see in the first example. A Rack app with Rack middleware is simple a chain of apps that call the next app in the chain, possibly modifying the environment or response before or after the rest of the chain is called.

So there you have it, beauty in simplicity.

ExtJS On Rails

mail@paulbarry.com (Paul Barry) — Wed, 23 Sep 2009 23:09:41 -0400

If you are looking to give ExtJS a spin, I've created a Rails Application Template to setup a Rails app with ExtJS installed. To use it, just do:

rails -m http://tinyurl.com/extjs-rb my-extjs-app

To see a sample of this in use, take a look at this Rails app. It is a port of Chapter 1 of ExtJS In Action to Rails. Assuming you have Rails 2.3.2 installed, you should be able to download the Rails app from that git repo, run script/server and then try out the app at http://localhost:3000.

UPDATE: This code actually refers to the code in the sample chapter on the Manning website. Chapter 1 in the latest version of the book has actually been completely re-written, so I've included the sample chapter in the git repo. Also be sure to check out the author's blog which covers the development of the book.

Why Rails 3 Will Require Ruby 1.8.7

mail@paulbarry.com (Paul Barry) — Mon, 14 Sep 2009 19:50:21 -0400

This past weekend I attended the Windy City Rails conference. It was in a great location in the heart of downtown Chicago and seemed to have a pretty good turn out. There were many great talks but this blog post will be focusing on a specific talk, and more precisely, part of a talk. Yehuda Katz gave a talk on the status of Rails 3. One of the things that he mentioned, which you may have already heard, is that Rails 3 will require Ruby 1.8.7 or higher, dropping support for Ruby 1.8.6. He also mentioned why they are doing this and I found the reason to be interesting. It's not that the Rails core team wants to try to take advantage of any specific new features, it's that Ruby 1.8.6 has a bug which has been fixed in 1.8.7.

To see the bug in action, I recommend that you install Ruby Version Manager (rvm). Once you have installed rvm, install Ruby 1.8.6 and Ruby 1.8.7.

The bug is that in Ruby 1.8.6, the hash method for Hash doesn't generate the same hash code for different hashes with the same values:

$ rvm use 1.8.6
$ irb
ruby-1.8.6-p383 > {:x => 1}.hash
 => 1313270 
ruby-1.8.6-p383 > {:x => 1}.hash
 => 1307060 
ruby-1.8.6-p383 > {:x => 1}.hash
 => 1296440 
ruby-1.8.6-p383 > {:x => 1} == {:x => 1}
 => true
ruby-1.8.6-p383 > h = {{:x => 1} => "foo"}
 => {{:x=>1}=>"foo"} 
ruby-1.8.6-p383 > h[{:x => 1}]
 => nil

So despite the fact that two hashes have the same values and are equal, you can't use a hash as a key in a hash, because that depends on the hash codes of the values being equal, which they aren't. This is fixed in Ruby 1.8.7:

$ rvm use 1.8.7
$ irb
ruby-1.8.7-p174 > {:x => 1}.hash
 => 327875 
ruby-1.8.7-p174 > {:x => 1}.hash
 => 327875 
ruby-1.8.7-p174 > {:x => 1}.hash
 => 327875 
ruby-1.8.7-p174 > {:x => 1} == {:x => 1}
 => true 
ruby-1.8.7-p174 > h = {{:x => 1} => "foo"}
 => {{:x=>1}=>"foo"} 
ruby-1.8.7-p174 > h[{:x => 1}]
 => "foo"

This is important because you could use a hash cache calls to a method that expects a hash, but only if you can use a hash as the key. This is one of the main reasons Rails 3 is going to require 1.8.7. They could make it worth for both 1.8.6 and 1.8.7 and higher, but why? It simplifies things to just require that you upgrade to Ruby 1.8.7 to use Rails 3. If you are using 1.8.6, this is probably a gotcha that you should be aware of.

Infinite Recursion

mail@paulbarry.com (Paul Barry) — Wed, 02 Sep 2009 01:17:31 -0400

A few days ago I posted an article on Tail Call Optimization. One really quick way to determine if any language/VM/interpreter performs Tail Call Optimization (TCO) is to write a function that calls itself, in other words, creating an infinitely recursive function. If the function just runs forever and doesn't return, the interpreter is doing TCO, otherwise you will get some sort of stack overflow error. So I decided to test a variety of languages to see what happens when you write an infinitely recursive function. First up is ruby:

def forever
  forever
end

forever

It was no surprise to me that running this results in this error:

run.rb:2:in `forever': stack level too deep (SystemStackError)
    from run.rb:2:in `forever'
    from run.rb:5

Ruby doesn't have TCO, I knew that. Next up, Python:

def forever(): forever()

forever()

This has a similar result, but the stack track is a little more revealing:

Traceback (most recent call last):
  File "run.py", line 3, in <module>
    forever()
  File "run.py", line 1, in forever
    def forever(): forever()
  File "run.py", line 1, in forever
    def forever(): forever()
...
  File "run.py", line 1, in forever
    def forever(): forever()
  File "run.py", line 1, in forever
    def forever(): forever()
RuntimeError: maximum recursion depth exceeded

This shows pretty clearly what is going on, the stack frames are pilling up and eventually it gets to the point where the Python interpreter says enough is enough. Interestingly enough, this mailing list thread shows that it's completely feasible to add TCO to Python and Guido just doesn't want to add it.

JavaScript is no surprise either, but we can write our infinitely recursive function with an interesting little twist:

(function(){ arguments.callee() })()

Yes that's right, it's an anonymous recursive function! Running this with SpiderMonkey results in InternalError: too much recursion. So how about Java:

class Run {
  public static void main(String[] args) {
    Run run = new Run();
    run.forever();
  }

  public void forever() {
    forever();
  }
}

The stack trace for this one looks a bit like the Python one, we see a stack frame for each iteration:

Exception in thread "main" java.lang.StackOverflowError
    at Run.forever(Run.java:8)
    at Run.forever(Run.java:8)
    at Run.forever(Run.java:8)
    at Run.forever(Run.java:8)
...

So that means no TCO on the JVM. So Scala doesn't have TCO, right?

def forever : Unit = forever

forever

Wrong. This one runs forever. Scala does TCO with some bytecode tricks which Nick Wiedenbrueck explains really well in this blog post.

Clojure is a functional Lisp saddled with the problem of no-TCO on the JVM, but it gets around it in a slightly different way than Scala. If you write a tail recursive function like this:

(defn forever [] (forever))

You will get a java.lang.StackOverflowError just as you do in Java. Instead, Clojure provides a language level feature to do recursion:

(defn forever [] (recur))

Calling recur in the function makes it call the function again. recur also checks that it is in the tail recursive position, which ends up being an interesting feature because you have to explicitly say "I expect this to do TCO". In other languages that do it transparently, you might think TCO is happening, but it might not be and you won't find out until you get a stack overflow error. Also, this construct allows us to have recursive anonymous functions:

((fn [] (recur)))

Erlang, being a function language, has TCO as well:

-module(run).

-compile(export_all).

forever() ->
  forever().

Now one thing all of these functional languages that have TCO; Scala, Clojure and Erlang, all have in common is that while the infinitely recursive function runs, it essentially does nothing, but it will peg your CPU utilization to nearly 100%. This next language, Haskell, being the mother of all functional langauges, of course has TCO. Here's the function:

forever = forever

Yes, that's a function. And if you call it with forever, it just sits there and runs forever. But here's the crazy thing, it uses no CPU. My guess is that it has to do with lazy evaluation, but I'm not sure. Any ideas?

Active Record Random

mail@paulbarry.com (Paul Barry) — Sun, 30 Aug 2009 22:28:21 -0400

Are you looking for a way to select a random record that plays nice with named scope in your Rails app? Throw this into config/initializers/active_record_random.rb:

class ActiveRecord::Base
  def self.random
    if (c = count) > 0
      first(:offset => rand(c)) 
    end
  end
end

Now you can call random the same way you would call first or all. That means you can do Widget.random to get a random widget or Widget.fancy.random, to get a random fancy widget, assuming you have defined the fancy named scope for Widget.

Tail Call Optimization

mail@paulbarry.com (Paul Barry) — Sun, 30 Aug 2009 16:20:06 -0400

Tail-Call Optimization (a.k.a Tail Recursion) is a technique often used in functional programming languages that promotes the use of recursion rather than imperative loops to perform iterative calculations. When I say imperative loops, I mean using a local variable that you change the value of as you calculate each step of the iteration. A generic term for this kind of variable is an accumulator, because it accumulates the new value at each step of the iteration.

Let's say you are hoping to become the next mega millionare and you want to know your odds of winning. Most lotteries consist of something like pick 5 numbers between 1 and 50. Each number can only come up once in the drawing and if you get all 5 numbers right, you win. The order isn't significant, you just need to get the 5 numbers.

Here's a JavaScript function written in an imperative style to get your odds:

function odds(n, p) {
  var acc = 1
  for(var i = 0; i < n; i++) {
    acc *= (n - i) / (p - i)
  }
  return acc
}

The parameters are n, the number of numbers you have to pick and p is the upper limit of all possible numbers to choose from. So the odds for the "pick 5 of 50" are 4.71974173573222e-7. That's expressed in decimal in scientific notation. To get the more traditional looking "1 in whatever" number, you simply take the inverse, 1/4.71974173573222e-7, which is 1 in 2,118,760.

The mega millions actually has a twist to it with the powerball. You pick 5 numbers of of 56 and then 1 number out of 46. A number that comes up in the first 5 can come up as the powerball. So that means the mega millions odds are 1/(odds(5,56) * odds(1,46)), which is 1 in 175,711,536.

One problem with our function is that it uses a mutable local variable and mutable local variables are evil. Some functional languages, such as Clojure, Haskell and Erlang, don't even allow you to use mutable local variables. So how can we do it without the accumulator? The answer is recursion:

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)
  }
}

This is a pretty elegant implementation of the function because it mirrors how you might think of the problem. This still works great but it breaks down if we try to calculate the odds of much larger numbers. For example, if you try to calculate the odds of picking 10,000 numbers out of 100,000 numbers with odds(10000, 100000), you will some kind of stack overflow / too much recursion error, depending on your interpreter.

The reason for this becomes clear when you walk through how the interpreter calculates the value. When you say odds(5, 56), the return value is (5/56) * odds(4, 55). The interpreter cannot evaluate this expression until odds(4, 55) is calculated. So the series of expressions that get evaluated are:

odds(5, 56)
(5/56) * odds(4, 55)
(5/56) * (4/55) * odds(3, 54)
(5/56) * (4/55) * (3/54) * odds(2, 53)
(5/56) * (4/55) * (3/54) * (2/53) * odds(1, 52)
(5/56) * (4/55) * (3/54) * (2/53) * (1/52) * odds(0, 51)
(5/56) * (4/55) * (3/54) * (2/53) * (1/52) * 1

As you can see, the lines get wider as the recursive calls build up. This is representative of how the interpreter works. As each recursive call is added, memory is temporarily used up. Once there are no more recursive calls, it can start evaluating the expressions and freeing up the memory. This works fine, but if you are performing the calculation on a large number that generates more recursive calls than the interpreter can hold in memory, then boom goes the dynamite. Most interpreters push each recursive call onto a stack, so when the stack runs out of memory, you get a Stack Overflow error.

So how can we possibly do calculations like this recursively? The answer to that is tail-call optimization. In order to do this, we are going to have to bring back the accumulator, but in this case, it's not going to be a mutable local variable, instead it will be a parameter to the function. Since we don't want callers of our function to have to pass in the initial value of the accumulator, we will define two functions, one "public" and the other "private":

(function(){
  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
    }
  }

  odds = function(n, p) {
    return odds1(n, p, 1)
  }  
})()

JavaScript doesn't really have a public/private mechanism, but we can use closures to accomplish the same thing. First this is an anonymous function that we create and then call immediately after we create it. This just gives us a local scope. If we didn't have this outer wrapping function, all variables would be global. Then we define a function and assign it to a local variable called odds1. Next we define a function and assign it to a global variable odds. The function odds is "closed over" the variable odds1, which means that it can reference that variable, even when the odds function is called outside the context it is defined in, even though the odds1 variable will not be directly available from that context. To test this out, simply try to print the value of odds and then odds1 from outside of this outer function. The interpreter will say odds is a function but it will say odds1 is undefined, which means odds1 is effectively private.

So when someone calls our function odds, it calls odds1 with an initial value of 1 for the accumulator and then returns that value. Since JavaScript does not have tail-call optimization, that is what actually happens. odds waits for the value of odds1 to be calculated and then returns that value once it gets one. If you look at odds1, it does the same thing, returning the value from a recursive call to itself. And since JavaScript does not have tail-call optimization, this still results in some sort of stack overflow with large enough values for n.

What a tail-call optimized language does is realize that the statement return odds1(n, p, 1) is saying call the function odds1 with the arguments n, p and 1 and then return value. What the language can do is have the odds function return immediately and tell the caller to call odds1 with the arguments n, p and 1 in order to get the value. The important distinction between these two is that the call to odds is eliminated from the call stack before odds1 is called.

The way I think of it is tail-call optimization almost like an HTTP redirect. The call to odds is simply redirected to odds1. Once odds has issued a redirect, it's out of the equation. Without tail-call optimization, the call to odds has to make a call to odds1. While the call it odds1 is being processed, both odds and the original caller are waiting for the response. If the chain of calls becomes to long, the call stack overflows.

This same idea can be applied to the recursive calls within odds1 itself. When odds(5, 56) is called, it will in turn call odds1(5, 56, 1). In odds1, the last thing it will do is call itself recursively, but this time the parameters will be odds1(4, 55, (5/56)). A function that returns a recursive call to itself as the last thing it does is said to be tail-recursive. Our original recursive odds function was not tail-recursive, because it needed to multiple the value of the recursive call by a value after the recursive call returned.

Since odds1 is tail-recursive, the call to odds1(5, 56, 1) can just say call odds1(4, 55, (5/56)) instead and take itself off the call stack. The series of calls looks like this:

odds(5, 56))
odds1(5, 56, 1)
odds1(4, 55, 5/56)
odds1(3, 54, 1/154)
odds1(2, 53, 1/2772)
odds1(1, 52, 1/73458)
odds1(0, 51, 1/3819816)

The value of the accumulator in each of these calls is the result of the multiplication of the previous value and the current n divided by the current p. As you can see here, the width of the expression doesn't increase for each iteration (well, except a little bit for the width of the accumulator value). If the interpreter actually evaluates the expressions this way there is no way to cause a stack overflow error. You can evaluate any of these expressions independently from the others, assuming you make odds1 public.

To see this in action, you will have to use a language with an interpreter that does tail-call optimization. Erlang is one such language. First let's write a non-tail-recursive implementation of the odds function:

-module(lotto).

-compile(export_all).

odds(0, _) -> 1;
odds(N, P) -> (N / P) * odds(N - 1, P - 1).

Now we can see that our function works using the Erlang interactive shell:

$ erlc lotto.erl
$ erl
Erlang R13B01 (erts-5.7.2) [source] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.2  (abort with ^G)
1> lotto:odds(5,56).
2.6179271462290333e-7
2> 1/(lotto:odds(5,56) * lotto:odds(1,46)).
175711536.0

So it turns out that you have to work really hard to get the Erlang VM to blow the stack on a non-tail-recursive call, but I managed to get an error eheap_alloc: Cannot allocate 1140328500 bytes of memory (of type "old_heap"). by trying to evaluate lotto:odds(100000000, 1000000000).. Let's re-write the function to be tail-recursive:

-module(lotto).

-export([odds/2]).

odds(N, P) -> odds(N, P, 1).

odds(0, _, Acc) -> Acc;
odds(N, P, Acc) -> odds(N - 1, P - 1, (N / P) * Acc).

You can see that Erlang gives us a couple of language features to make this a little cleaner than the JavaScript function. First, functions with different arities are completely different functions. Arity is the number of arguments to a function. So here we have two functions, odds/2 and odds/3.

Also, pattern matching is used to distinguish the two cases. The odds/3 function has two cases, one where N is 0 and the other to handle all other cases.

Lastly, the export directive at the top says that we only want the odds/2 function to be public, so the odds/3 function is private to this module.

With this definition of the odds function, if we try to evaluate lotto:odds(100000000, 1000000000)., it will complete, although it will take some time. The original recursive odds function takes O(n) time and O(n) space, which means the amount of time and the amount of space it takes to evaluate the function increases linearly for larger values of n. Due to tail-call optimization, the function still takes O(n) time, but takes O(1) space, which means the amount of time it takes to evaluate the function still increases linearly with larger values for n increases, but the function always operates in a constant amount of space, regardless of the size of n.

So to summarize, tail-call optimization is a technique that is performed by the compiler/interpreter, usually transparently, to make tail-recursive functions operate in constant space. This is a necessary optimization in order to be able to use recursive functions to perform iterative calculations as opposed to imperative functions that use mutable local variables.

Currying and Partial Function Application

mail@paulbarry.com (Paul Barry) — Fri, 21 Aug 2009 09:26:36 -0400

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.

In Search Of Sharper Tools

mail@paulbarry.com (Paul Barry) — Tue, 21 Jul 2009 23:51:18 -0400

After reading the comments in my last post, one thing I realized that I neglected to do is define what I mean by metaprogramming. Rubyists probably already know what I mean, but people coming from other programming languages might have different ideas about what I mean by metaprogramming.

I've actually mentioned this in a few talks I've given about Ruby. I don't really like the word Metaprogramming, it's a little bit nebulous. I think a better term is dynamic code generation. I like that term because I think most programmers will have a pretty good mental model of what I am talking about when I say that. There are several features of Ruby that when combined together allow you to do almost anything to bend the language to your will. To understand how to do that, I recommend reading the book Metaprogramming Ruby, which is in beta right now.

I'll give a short, real world example of what I'm talking about. I'm working on a Rails app that uses a database that has bit field columns. I want to treat the boolean flags in the bit field as though they are regular boolean attributes throughout my code. So I wrote a Ruby gem has-bit-field, which generates all the methods necessary to work with the bit field columns. You define what is in the bit field in the most clear, simple, elegant way possible by just stating which column has the bit field and then what attributes should be generated for each bit:

class Person < ActiveRecord::Base
  has_bit_field :bit_field, :likes_ice_cream, :plays_golf, :watches_tv, :reads_books
end

This is the kind of abstraction that the metaprogramming capabilities of Ruby afford you. I threw this together, with tests, in an hour or so. Can you imagine the amount of nonsense you would have to go through in Java to create an abstraction equivalent to this?

This type of abstraction is what I think makes Ruby a great language, but I realize you are definitely walking a fine line with this kind of thing. It's possible for this sort of thing to go wrong quickly. The first way these things go wrong is when the abstraction is not intuitive and not documented. First of all, a good abstraction should be almost intuitive, requiring other programmers to be able to guess what is does. This is commonly referred to as the Principal of Least Surprise. This doesn't mean that you are excused from providing some sort of documentation explaining how it works, especially for more complex abstractions.

The reason why it's important that the abstraction is clear is that most of the time the code that defines the abstraction is dense at best, and downright ugly at worst. This isn't a problem specific to Ruby, as anyone who has worked with Lisp macros can attest to. But in the end I'd rather have a small chunk of code that is tested and documented that I don't really need to look at that enables me to make the code where the business logic is defined as clear as possible. If other programmers are constantly having to dive into the guts of the definition of these abstractions just to understand how the code works, you have officially created a mess. And this is no ordinary mess, this is meta-spaghetti, and is a mess on an order of magnitude not possible in statically typed languages.

So does this mean you shouldn't use Ruby? Not at all, and I think Glenn Vanderburg sums it up best:

Weak developers will move heaven and earth to do the wrong thing. You can't limit the damage they do by locking up the sharp tools. They'll just swing the blunt tools harder.

I think developers often associate "blunt tools" with static typing, because really they associate static typing with Java. I'm not sure that static typing is in fact a blunt tool. If static typing means I can't create these kinds of abstractions, then yes, it's a blunt tool. But can you do this kind of thing with Scala Compiler Plugins? How about with Template Haskell? What about with MetaOCaml? If you can, are those tools then sharper than Ruby? Or is there a way to define abstractions like these without metaprogramming at all?