# 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)}" }&#91;/sourcecode&#93;

...and the memoized version:

&#91;sourcecode language='ruby'&#93;
class Memoized
def initialize
@factorial_memo = {}
end

def factorial(n)
puts n
unless @factorial_memo.has_key? n
if n < 1
@factorial_memo&#91;n&#93; = 1
else
@factorial_memo&#91;n&#93; = n * factorial(n-1)
end
end

@factorial_memo&#91;n&#93;
end
end

memoized = Memoized.new

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

puts memoized.factorial_memo.inspect&#91;/sourcecode&#93;

Printing the hashtable is especially telling:  <code>{5=&gt;120, 0=&gt;1, 1=&gt;1, 2=&gt;2, 3=&gt;6, 4=&gt;24}</code> It reads like a look-up table for factorials.
<h4>Memoization in Facets</h4>
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.  <a href="http://facets.rubyforge.org/">Facets</a> 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)}" }&#91;/sourcecode&#93;

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

require 'facets/memoize'

class MemoizedMath
n + m
end
def mult(n, m)
n * m
end
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.

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.

# Hartford Ruby Brigade starts with a tour of Ruby Facets

As Rob Bazinet has said, the Hartford Ruby Brigade is having its first meeting on March 24. You can get all the details from his post. Come join us! There’s even a book raffle.

I’ll be giving the first presentation, a tour of Ruby Facets. Facets is a pretty huge library (even after they moved some really neat parts into their own projects), and it’s crazy to think we could cover it all in one night. I’ll quickly touch on the simple features, just to let you know they’re there, and I’ll spend more time with some of the interesting parts. If you’re stuck, it’s a good chance Facets has what you need; the trick is knowing it’s there, and where to look — I want to point out enough of Facets to help you with that.

I’ll also start a Tour of Facets series here, starting with this post. I’m aiming for two to four posts a month, and will cover everything in the presentation, and then some. So, on with the tour…

compare_on and equate_on

Remember the first time you saw `attr_reader` and `attr_writer`? These tiny helpers got me excited about ruby, not just because they meant less typing and DRY-er code, but because they meant I could make helpers to generate methods, too, if only I could think of a reason to do it.

Facets has a great example of why you’d want to do that: `compare_on` and `equate_on`.

Most ruby programmers know you can make your objects sortable by defining `<=>`, the spaceship method, on them. Typically, you wind up delegating to some attribute:

```class Person
def initialize(fname, lname)
@fname, @lname = fname, lname
end
def <=>(person)
@lname.<=>(person.lname)
end
end```

Facets adds `compare_on`, which generates the spaceship method for you, based on that attribute. Not only that, but you can `compare_on` multiple fields, and it handles the hairy logic for you automatically:

```require 'facets/compare_on'

class Person
def initialize(fname, lname)
@fname, @lname = fname, lname
end
compare_on :lname, :fname
end

people = []

Correctly implementing the spaceship operator isn’t too hard, but object equality gets tricky in any language. Facets helps you here by implementing ruby’s main three equality methods for you: `==`, `eql?`, and `hash`.

```require 'facets/compare_on'

class Person
Again, you can equate on multiple attributes (`fname` and `lname`), and it handles all the details for you. Hope to see you at the Hartford Ruby Brigade!