Really useful anamorphisms in Ruby Really simple anamorphisms in Ruby introduced a very simple unfold. Its chief characteristics were that it generated an Array from a value of some sort, and it did so by applying an incrementor block to its seed recursively until it generated nil. For example:

10.class.unfold(&:superclass)
    => [Fixnum, Integer, Numeric, Object]

A very simple modification allows us to separate the two blocks with a :while or :to pseudo-keyword, and to add a :map keyword for transforming the state into the desired result. Thus, this really simple unfold:

1.unfold(&'_+1 unless _==10').map(&'**2')
    => [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Can also be expressed as:

1.unfold(:to => '==10', :map => '**2', &'_+1')
    => [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

The latter form is helpful once unfolds become larger and more complex than these simple one-liners.

(There is another style of writing :unfold, using method chaining and lazy evaluation to eliminate lambda keywords, but we will save that for another time: it is a great examination of syntax but does not change :unfold’s fundamental behaviour.)

Let’s turn it up a notch

These trivial examples are not particularly compelling. Unfold is touted as the complement to :inject. So you would expect :unfold to be as useful as :inject. And :inject is very, very useful—you “reduce” lists of things to values all the time.

But how often do you need to turn a value into a list? How often do you need to turn ‘10’ into ‘[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]’? And if you do, what’s wrong with using (1..10).map(&'**2')?

Remember that :unfold can be applied to objects with a lot more information to them. The thing that had me stuck when I first saw :unfold was thinking of it as the opposite of :inject. Or at least, the opposite of how I used :inject. I tended to use :inject in a way that reduced information. For example:

[7, 6, 10, 3, 9, 4, 8, 5, 2, 1].inject(&'+')

This gives us the sum of the numbers from one to ten, as it happens. It also gives us a value that is considerably simpler than the list we used to generate the number. Information is lost when we use :inject to “reduce” a list to a very simple value. So my first reaction to :unfold was to think of ways to use :unfold on very simple values, like numerics.

But :unfold doesn’t have to work with simple values. It can work with arbitraily complex data structures. Consider:

def zip(*lists)
  lists.unfold(
      :while => '.first', 
      :map => '.map(&".first")',
      &'_.reject(&".length < 2").map(&"[1..-1]")')
end

Zip is a function that takes two (or more, but let’s just say two for now) lists, and produces a list of pairs of items. So:

zip([:a, :b, :c], [1, 2, 3])
    => [[:a, 1], [:b, 2], [:c, 3]]

How does :unfold do it? First, of course, it makes a single list of lists. It then performs an unfold on this single data structure. The incrementor successively reduces each sublist by removing the first items. So the output of the successive incrementor operations is:

[
    [[:a, :b, :c], [1, 2, 3]],
    [[b, :c],      [2, 3]]
    [[:c],         [3]]
]

The :map then extracts the first items from each sublist and presents them as a list:

[
    [:a,           1], 
    [:b,           2], 
    [:c,           3]
]

Neat. But why do we care about zip? Well, if you’ll notice, we already have a bunch of really useful things we can do with lists, like :map, :select, :reject, :detect, and so on. What would you do if you had two lists and needed to do something with each pair in the list, like… A list of first names and surnames that need to be catenated together?

zip(first_names, surnames).map(&'"#{_[0]} #{_[1]}"')

Zip is useful when we have a bunch of parallel lists and there’s something we want to do with each tuple from the lists.

Generalized iteration

We recognize this “pattern,” it’s one of the most powerful in programming. Zip was one algorithm, a way of iterating over several lists simultaneously. The other algorithm was "#{_[0]} #{_[1]}", a recipe for what to do with the successive tuples of values.

The powerful idea was to separate the mechanics of turning a data structure into a linear series of values—iterating—from what we want to actually do with each value. (In OO-style programming, we would define a method for lists of lists that returns an iterator over the tuples of values. Same thing, proving that how you do it is not as important as understanding why you do it.)

Unfold has other uses, but this one alone is worth the trouble to understand the pattern even if you aren’t rushing to implement this exact unfold method: Converting a single data structure to a list is one way to implement iteration: for any data structure, you can use unfold to define a linear iteration. You can then use :each or :map or :inject just as our parents before us would have used DO or FOR loops.

Consider this (inelegant, but I’m writing this rather late at night) unfold:

[[1, 2, 3], [4, 5, 6, [7, 8]], 9, 10].unfold(
  :while => '.first',
  :map => lambda { |first|
    first = first.first while first.kind_of?(Array)
    first
  }
) { |state|
  state = state.first + state[1..-1] while state.first.kind_of?(Array)
  state[1..-1]
}
    => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

This is the same idea, only we convert a tree into a list representing a depth-first search of a simple tree. You may recognize it as Array’s :flatten method. Once again, it’s really a way of iterating over the elements of a tree. So one way to think of this :unfold is that it is an iterator over a tree’s leaves:

def flatten(arr)
  arr.unfold(
    :while => '.first',
    :map => lambda { |first|
      first = first.first while first.kind_of?(Array)
      first
    }
  ) { |state|
    state = state.first + state[1..-1] while state.first.kind_of?(Array)
    state[1..-1]
  }
end

But I already know how to write Zip and Flatten methods, honest I do.

Zip and Flatten are relatively common, that’s why :flatten and :zip can both be found in Ruby’s standard Array class. And if there’s a data structure that needs regular unfolding, you ought to weigh the advantages and disadvantages of writing an :unfold for it or using more humdrum ways of writing an iterator.

However, what do you do when you only need to unfold something once? For example, perhaps you have code that obtains some data in JSON format, and having used a library to parse the JSON into a one-off list or hash, you want to iterate through it.

With unfold, you can write your one-time, specific iterator right in place. This is no different than using blocks and lambdas in Ruby for one-off functions that really don’t need the cermony and weight of being implemented as methods.

When you want to iterate through something, and you want to separate the mechanism for iterating through the data from what you do with the data, :unfold should be in your tool box.

Unfold and the bio-sciences. Not really.

I like to think of :unfold like unfolding a protein molecule. When you stare at a data structure, it’s dense, opaque. But you supply an unfold algorithm, and what looked like a messy ball of twine unravels into a long filament made up of simple elements. You can then operate on the simple elements, without getting what you want to do en-snarled in how you iterate over the data structure.

So there you have it. Unfold can be really useful if we see it as a standardized way to write iterators for data structures.

---

Update: The under-appreciated unfold.

Labels: lispy, popular, ruby

  ¶ 10:46 PM 13 comments

  Really simple anamorphisms in Ruby Anamorphisms are functions that map from some object to a more complex structure containing the type of the object. They are the dual—a fancy word for complement—of Catamorphisms, functions that map from some complex structure down to a simpler object.

In simpler terms, a Catamorphism is a function like inject: In Ruby, Inject takes a collection and produces something simpler. It is also called fold or reduce in other languages. Inject can do something like produce the sum of a list:

(1..5).inject &'+' => 15

Unfold does the reverse: it takes a single value and turns it into a collection. Now, a proper unfold can be configured with a seed value, a transformation, a stopping predicate, maybe a distinction between states and output values, and even the type of structure you want to create. A proper unfold would even work with lazy lists if it didn’t have a stopping condition.

But sometimes you want something really simple. The state and the output value could be the same thing, eliminating a transformation from state to output. The stopping predicate could simple, it could stop when it reaches nil. And it could always return Arrays. So you could use such a simple unfold whenever you have a seed value and some sort of function (expressed as a block) that returns nil when it has no more values.

For example:

10.unfold { |n| n-1 unless n == 1 }.inspect => [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
10.class.unfold(&:superclass).inspect => [Fixnum, Integer, Numeric, Object]

Hey, what happens if you combine really simple anamorphisms with really simple catamorphisms?

5.unfold(&'_-1 unless _==1').inject(&'*') => 120

Here is the code unfold.rb. (If overloading core classes with too much responsibility is not to your taste, it is trivial to express unfold as a function taking a seed and a block as arguments).

Now that I’ve whet your appetite, here’re Really useful anamorphisms in Ruby. And for another implementation, everything you ever wanted to know about implementing a true unfold in Ruby.

Enjoy!

(Code courtesy of Mobile Commons. Thanks!)


Here’s an interesting email from Hugh Sasse:

I was reading Code Complete 2 last night and Steve McConnell says that he wouldn’t hire a programmer who wrote a recursive factorial function. [I’m not sure that would be such a crime in languages like Lua with proper tail recursion, but still. (I’m probably wrong, now I’ve written that! “Open mouth, insert foot, echo internationally” as they used to say on Fidonet :-))] I thought “that seems a bit harsh”, especially since in real life they’d get one from a library most of the time, anyway.

So, as I have often run out of stack on Ruby, I’ve tried to rewrite unfold as an iterative function. It seems to be working. The script as modified blows up at 5000 on my system with the recursive version, but the iterative version succeeds at 5000.

Thanks for this blog entry. There’s something REALLY nice about this idea, which I can’t put my finger on. Might be something to do with loops terminating when they should, and The Pragmatic Programmers’ article about “cook until done”

http://www.pragprog.com/articles/cook-until-done

Unfold feels like a “do until finished” loop.

class Object
  # As above, but iterative, rather than recursive.
  def unfold2 &block
    result = [self]
    x = block.call(self)
    while not x.nil?
      result.push x
      x = block.call(x)
    end
    return result
  end
end

Labels: lispy, popular, ruby

  ¶ 5:34 PM 0 comments

  String#to_proc Breaking news! The irb enhancement gem Utility Belt includes String#to_proc

String#to_proc is an addition to Ruby’s core String class to enable point-free hylomorphisms…

I’ll start again. String#to_proc adds a method to Ruby’s core String class to make lots of mapping and reducing operations more compact and easier to read by removing boilerplate and focusing on what is to be done. In many cases, the existing black syntax is just fine. But in a few cases, String#to_proc can make an expression even simpler.

String#to_proc is a port of the String Lambdas from Oliver Steele’s Functional Javascript library. I have modified the syntax to reflect how String#to_proc works in Ruby.

We’ll start with the examples from String Lambdas so you can see what is actually going on. Then we’ll look at how to use the & coercion to make working with arrays really simple.

to_proc creates a function from a string that contains a single expression. This function can then be applied to an argument list, either immediately:

'x+1'.to_proc[2];
     → 3
'x+2*y'.to_proc[2, 3];
     → 8

or (more usefully) later:

square = 'x*x'.to_proc;
square(3);
     → 9
square(4);
     → 16

Explicit parameters

If the string contains a ->, this separates the parameters from the body.

'x y -> x+2*y'.to_proc[2, 3];
     → 8
'y x -> x+2*y'.to_proc[2, 3];
     → 7

Otherwise, if the string contains a _, it’s a unary function and _ is name of the parameter:

'_+1'.to_proc[2];
     → 3
'_*_'.to_proc[3];
     → 9

Implicit parameters

If the string doesn’t specify explicit parameters, they are implicit.

If the string starts with an operator or relation besides -, or ends with an operator or relation, then its implicit arguments are placed at the beginning and/or end:

'*2'.to_proc[2];
     → 4
'/2'.to_proc[4];
     → 2
'2/'.to_proc[4];
     → 0.5
'/'.to_proc[2, 4];
     → 0.5

’.’ counts as a right operator:

'.abs'.to_proc[-1];
 → 1

Otherwise, the variables in the string, in order of occurrence, are its parameters.

'x+1'.to_proc[2];
     → 3
'x*x'.to_proc[3];
     → 9
'x + 2*y'.to_proc[1, 2];
     → 5
'y + 2*x'.to_proc[1, 2];
     → 5

Chaining

Chain -> to create curried functions.

'x y -> x+y'.to_proc[2, 3];
     → 5
'x -> y -> x+y'.to_proc[2][3];
     → 5
plus_two = 'x -> y -> x+y'.to_proc[2];
plus_two[3]
     → 5

Using String#to_proc in Idiomatic Ruby

Ruby on Rails popularized Symbol#to_proc, so much so that it will be part of Ruby 1.9.

If you like:

%w[dsf fgdg fg].map(&:capitalize)
    → ["Dsf", "Fgdg", "Fg"]

then %w[dsf fgdg fg].map(&'.capitalize') isn’t much of an improvement.

But what about doubling every value in a list:

(1..5).map &'*2'
    → [2, 4, 6, 8, 10]

Or folding a list:

(1..5).inject &'+'
    → 15

Or having fun with factorial:

factorial = "(1.._).inject &'*'".to_proc
factorial[5]
    → 120

String#to_proc, in combination with & coercing a value into a proc, lets you write compact maps, injections, selections, detections (and many others!) when you only need a simple expression.

Caveats: String#to_proc uses eval. Cue the chorus of people—pounding away on quad 3Ghz systems—complaining about the performance. You’re an adult. Decide for yourself whether this is an issue. After mankying things about to deduce the parameters, String#to_proc evaluates its expression in a different binding than where you wrote the String. This matters if you include free variables. My thinking is that it ceases to be a simple, easy-to-understand hack and becomes a cyrptic nightmare once you get too fancy.

You know that Voight-Kampff test of yours… did you ever take that test yourself?

I have been using Functional Javascript for quite some time now, and I use the String Lambdas a lot. However, Ruby and Javascript are very different languages. Once you get out of the browser’s DOM, Javascript is a lot cleaner and more elegant than Ruby. For example, you don’t need to memorize the difference between a block, a lambda, and a proc. Javascript just has functions.

However, Javascript is more verbose: Whereas in Ruby you can write [1, 2, 3].map { |x| x*2 }, if Javascript had a map method for arrays, you would still have to write [1, 2, 3].map(function (x) { return x*2; }). So it’s a big win to make Javascript less verbose: code is easier to read at a glance when you don’t have to wade through jillions of function keywords.

Nevertheless, I still find myself itching for the String Lambdas when I’m writing Ruby code. It may be a matter of questionable taste, but for certain extremely simple expressions, I vastly prefer the point-free style. (-3..3).map &:abs is shorter than (-3..3).map { |x| x.abs }.

It is also cleaner to me. abs is a message, especially in a language like Ruby that supports the sending arbitrary messages named by symbols. Writing (-3..3).map &:abs looks very much like sending the abs message to everything in the list. I don’t need an x in there to tell me that.

Thus, I obviously like (-3..3).map &'.abs'. But I like (1..5).map &'*2' for the same reason. It isn’t just shorter, it hides a temporary variable that really doesn’t mean Jack to me when I’m reading the code. And quite honestly, (1..10).inject { |acc, mem| acc + mem } raises more questions than it answers about what inject does and how it does it. (1..10).inject &'+' gets right down to business for me. I’d prefer that it be called “fold,” but the raw, naked + seems to describe what I want done instead of how I want the computer to do it.

Symbol#to_proc also supports named parameters, either through implication (&'x+y') or with the arrow ('x y -> x*y'). I haven’t thought of a case where that would be a win over using a Ruby block: { |x, y| x*y }.

I’m divided about the underscore notation. It seems like a good compromise for expressions where there is a single parameter and it doesn’t fall on the left or the right side of an expression. Standardizing on an unusual variable name is, I think, a win. Underscore often means a “hole” in an expression or a computation, so it feels like a good fit. I would honestly much rather see something like: &'(1/_)+1' than &'(1/x)+1'. The underscore jumps out in an obvious way, and it wouldn’t be magically clearer to write { |x| (1/x)+1 }.

That being said, I haven’t actually written an underscore expression yet in actual code, so far I’m getting by using the point-free expressions to simplify things and using Ruby blocks for everything else.

RSpec

describe "String to Proc" do

  before(:all) do
    @one2five = 1..5
  end

  it "should handle simple arrow notation" do
    @one2five.map(&'x -> x + 1').should eql(@one2five.map { |x| x + 1 })
    @one2five.map(&'x -> x*x').should eql(@one2five.map { |x| x*x })
    @one2five.inject(&'x y -> x*y').should eql(@one2five.inject { |x,y| x*y })
    'x y -> x**y'.to_proc()[2,3].should eql(lambda { |x,y| x**y }[2,3])
    'y x -> x**y'.to_proc()[2,3].should eql(lambda { |y,x| x**y }[2,3])
  end

  it "should handle chained arrows" do
    'x -> y -> x**y'.to_proc()[2][3].should eql(lambda { |x| lambda { |y| x**y } }[2][3])
    'x -> y z -> y**(z-x)'.to_proc()[1][2,3].should eql(lambda { |x| lambda { |y,z| y**(z-x) } }[1][2,3])
  end

  it "should handle the default parameter" do
    @one2five.map(&'2**_/2').should eql(@one2five.map { |x| 2**x/2 })
    @one2five.select(&'_%2==0').should eql(@one2five.select { |x| x%2==0 })
  end

  it "should handle point-free notation" do
    @one2five.inject(&'*').should eql(@one2five.inject { |mem, var| mem * var })
    @one2five.select(&'>2').should eql(@one2five.select { |x| x>2 })
    @one2five.select(&'2<').should eql(@one2five.select { |x| 2<x })
    @one2five.map(&'2*').should eql(@one2five.map { |x| 2*x })
    (-3..3).map(&'.abs').should eql((-3..3).map { |x| x.abs })
  end

  it "should handle implied parameters as best it can" do
    @one2five.inject(&'x*y').should eql(@one2five.inject(&'*'))
    'x**y'.to_proc()[2,3].should eql(8)
    'y**x'.to_proc()[2,3].should eql(8)
  end

end

Go ahead, download the source code for yourself.

---

Update: Reg smacks himself in the head!

I had a look at the source code for Symbol#to_proc:

class Symbol
  # Turns the symbol into a simple proc, which is especially useful for enumerations. Examples:
  #
  #   # The same as people.collect { |p| p.name }
  #   people.collect(&:name)
  #
  #   # The same as people.select { |p| p.manager? }.collect { |p| p.salary }
  #   people.select(&:manager?).collect(&:salary)
  def to_proc
    Proc.new { |*args| args.shift.__send__(self, *args) }
  end
end

Look at that: Although the examples are all of unary messages like .name, the lambdas created handle methods with arguments. And since almost everything in Ruby is a method, including operators like +… You can use Symbol#to_proc to do some of the point-free stuff I like:

[1, 2, 3, 4, 5].inject(&:+)
     → 15
[{ :foo => 1 }, { :bar => 2 }, { :blitz => 3 }].inject &:merge
     → {:foo=>1, :bar=>2, :blitz=>3}

Labels: lispy, popular, ruby

  ¶ 11:22 AM 23 comments

  Too much of a good thing: not all functions should be object methods OOP is several different ideas put together, the most important of which is Fine-Grained Information Hiding.

One can think of information hiding as being the principle and encapsulation being the technique. A software module hides information by encapsulating the information into a module or other construct which presents an interface.

The basic principle of all OO languages is that relatively small things—such as individual accounts in a business program—each encapsulate both their data (in the form of members) and their algorithms (in the form of methods). Our notions of members and polymorphism both work to this goal of hiding information. There’s a lot more to most OO languages, such as whether they include a notion of types and what mechanisms they use for sharing common behaviour. But let’s look at this one principle: objects are responsible for their data and for their algorithms.

should objects be responsible for all of their own behaviour?

There’s a general idea that in a well-constructed program, each object “knows” how it ought to behave. That’s what its methods are for. Quite obviously, objects cannot be responsible for everything involving them in a program. If each object completely encapsulated all of the things it could do or be involved in, you would never pass one object as a parameter in a message to another object.

For every complex problem, there is a solution that is simple, neat, and wrong.

For example, you would never have collections. If every object “knew” how to organize itself into collections, you wouldn’t need an Array or Hash, would you? In practice, each object in a system can be involved in many different actions. It has to be responsible for some of them, and it has to play a secondary, passive role in others. Most OO programs do not have every object implement its own collections methods. They may include some form of specialization so you can have an array of accounts, but an array of accounts is still not an account.

subject.verb(object)

In the English language, we have the idea of a Subject and an Object in a sentence. For example, when we say “Jack loves Jill,” Jack is a subject and Jill is an object. Jack loves. Jill is loved. It’s the same in OO programs. Sometimes objects are actively doing things through their methods. Sometimes other object’s methods are doing things with them.

Verbing Weirds Language

Good OO design is, in part, doing a good job of choosing the right bifurcations: given a list of nouns and verbs, making the right decisions about which nouns ought to be the active nouns, the subjects, the ones that “own” the verb in the form of a method. And thus consciously making decisions about which objects ought to be the passive nouns, the objects of the verbs, the ones that don’t implement the methods.

Unfortunately, there are lots of places where we can err on the side of giving too much responsibility to individual objects. It’s understandable, given that OO is theoretically all about objects being responsible for themselves. But as in many other things, in practice good OO is about objects being responsible for a little as possible (but no less!), not as much as possible.

the kingdom of nouns

One common symptom of this problem is a system that has objects for all of the obvious nouns or entities, but not for the verbs. OO began with languages like Simula, where the paradigm was trying to represent real-world entities such as automobiles on a highway. From that time forward, the emphasis has been on having objects for each noun in the problem domain. In such traditionally-organized OO programs, the “verbs” or actions are all attached to objects as methods.

Not all “verbs” have a clear separation between a single entity that is the subject or active entity that ought to own the verb’s definition and the secondary, passive subject entities that should not own the verb’s definition. The easiest examples of this are operations that are intended to be commutative.

For example, many languages define addition as a method belonging to numbers or magnitudes. In Smalltalk, the expression 1 + 2 actually means “send the message + 2 to the object 1.” At first glance, this seems elegant: the number 1 handles the message + 2 as integer addition, while 1.0 would handle the same message with floating point arithmetic. What more could you want?

Well, there is a huge problem with this arrangement: Addition is commutative. 1.0 + 2 must give the same result as 2 + 1.0. Using a simple message to implement addition means that you must be excruciatingly careful to handle all of the possible cases so that you do not accidentally violate this property. Now of course, the designers of system classes like Integer and Float went to this trouble. But if you want to add another magnitude class—say CurrencytwoPlaceDecimal—you have to open up all of the system classes and modify them so that 1 + ThirtyCents gives the same result as ThirtyCents + 1.

beware of breaking symmetry

Of course, you may not need to implement a new magnitude class. Fine. But what about symmetric relations like comparison? This is a major pitfall for OO developers: in many cases you need to write a test of equivalence or equality (operations like ==, equal?, eql?, eqv? and all of the other variations on the same theme). In every one of these cases, horrible things will happen if your operation is not symmetric. For every case, x.eql?(y) if-and-only-if y.eql?(x).

This is obviously easy when x and y are both the same kind of object. What happens when they’re different, but still logically equivalent? It turns out that implementing commutative operations and symmetric relations as methods doesn’t work very well. It forces you to smear duplicate logic over many different classes (or prototypes, if your language swings that way).

Here’s a practical example. Let’s say you want to implement a form of equivalence for collections. For ordered collections like lists, what you want is that if two ordered collections have the same members, in the same order, they are equivalent. It’s easy to imagine writing such a method as a mixin for all of your ordered collections. It obviously knows about iterating over ordered collections (recursively, if you grew up with Godel, Escher, Bach on your night stand). Note that you may not have an indexed collection: you might have a list where you simply retrieve values in order.

And likewise, you can write a collection equivalence method for dictionaries like hash tables: if two objects have the same values at the same keys, they are equivalent. Again, a simple mixin will handle things for dictionaries.

Now comes the wrinkle: you decide that an ordered collection ought to be equivalent to a dictionary where the keys are the integers ascending from zero. In other words, ('foo' 'bar' 'blitz') ought to be equivalent to { 0 => 'foo', 1 => 'bar', 2 => 'blitz' }. How are you going to code this? Well, the dictionary mixin could obviously handle equivalence to an ordered list. But we need symmetry, so we have to “open up” the ordered collection mixin and add code for equivalence to dictionaries.

Actually I made up the term object-oriented and I can tell you I did not have C++ in mind. The important thing here is that I have many of the same feelings about Smalltalk.

I’m holding my nose, we have not one but two different code smells: 1) Why is one piece of logic in two different places? 2) Why do ordered collections know anything at all about dictionaries, and why do dictionaries know anything at all about ordered collections? The latter is especially disturbing: the whole point of OO is information hiding. How does having ordered collections and dictionaries knowing about each other help us to hide information?

The obvious answer to me is that the knowledge of how to compare an ordered collection to a dictionary does not belong in ordered collections or in dictionaries. The requirement that relations like equivalence be symmetrical across heterogeneous types implies that the types themselves cannot be responsible for implementing equivalence for themselves.

There are similar problems of code duplication and information leakage apply to modelling relations (why do we declare has_one and belongs_to in Rails) and implementing the <=> operator in Ruby. It looks like having verbs “belong to” the subject noun is often a good idea, but not always a good idea.

commuting the sentence of execution

Maybe some verbs belong to objects, but some are best on their own? Maybe + and <=> and equivalent? really ought to be emancipated from their subservience to objects and ought to have their own definitions.

There are two real approaches to object-orientation. The first is known as message-passing. You send an object a message and ask it to deal with it. (This would not work with many people in this newsgroup.) The meaning of the message is local to the object, which inherits it from the class of which it is an instance, which may inherit it from superclasses of that class…

The second approach is generic functions. A generic function has one definition of its semantics, its argument list, and is only specialized on particular types of arguments.

What we ought to do is take some of the verbs and give them their own place in our programs, instead of hanging them off nouns. This isn’t such a revolutionary idea: Common Lisp’s Metaobject Protocol does this exact thing, providing generic functions. A generic function is, in effect, a verb raised to the same level of abstraction as a noun.

This isn’t some revolutionary idea limited to “powerful” languages either: the Java collections framework uses a Comparable interface for ordering collections. The compareTo(...) method belongs to an object. By way of—ahem—comparison, the Comparator interface extracts comparison out of the subject object and puts it in a separate function object. You can perform sorts in Java either way.

If we aren’t using Common Lisp, can we build the verbs we want out of the tools at our disposal? In other words, can we Greenspun generic functions in languages like Java and Ruby?

generic functions in java, plus a detailed look at method dispatching

Let’s start by thinking about generic functions in a Java-like language.

Returning to our example of writing equivalent?, we might make an Equivalent class with a single method, perhaps we can call it eval. So we end up with something like Eqivalent.eval(foo, bar). Java-like languages allow us to write different versions of the eval method with different type signatures, so we can write:

public static boolean eval (List foo, List bar) { ... }
public static boolean eval (List foo, Map bar) { ... }
public static boolean eval (Map foo, List bar) { return eval(bar, foo); }
public static boolean eval (Map foo, Map bar) { ... }

And so forth. Are we done?

No, our code is broken. What happens when we decide that the “default” equivalence is the == relationship. We can’t write:

public static boolean eval (Object foo, Object bar) { return foo == bar; }

This is hideously broken in languages like Java. You’re almost all nodding in agreement, but please be patient while I explain it anyway: you probably want to pass this along to someone who really needs to be told why it is broken, so why don’t I go ahead and explain it for them?

What you want is that if two objects are of the more specific types—List and Map—we will call the more specific version of the eval methods. But if we can’t “match” one of the more specific eval methods, we want to use eval (Object foo, Object bar). Too bad, that’s not how Java works. Java uses two completely different ways to figure out which method to call when you overload methods!

Way number one is is for figuring out that when you call noun.verb(...), where do we find the definition for verb? This lookup is effectively done at run time, so that even if your code looks like this:

public static void printSomething(Object foo) {
    System.out.println(foo.toString());
}

Java will look up the method toString based on foo’s actual type when the method is called, even though you declared it to be an Object. That’s polymorphism at work, and it’s the information hiding working for us. Each object can do it’s own thing where toString is concerned, and we don’t have to worry about it. This is called single dispatch, because it figures out which method to call based on just one of the nouns, the subject noun a/k/a the receiver of the method invocation.

But that’s not what happens when we write this:

public static void printSomethingElse (Object foo, Object bar) {
    if (Equivalent.eval(foo, bar))
        System.out.println("2 x " + foo);
    else System.out.println(foo.toString() + ", " + bar.toString());
}

It will always call eval (Object foo, Object bar). It will not call eval (List foo, List bar) if you pass it two lists. That’s because although each of our methods have the same name—eval—Java treats them as different methods, and it figures out which one to call based on the declared types of the parameters at compile time, not on the actual types of the parameters’ values at run time.

Besides writing a Lisp interpreter in Java, your next best bet for building a generic function the way we want it is to find a way to turn Java’s single dispatch into a multi-dispatch, to dispatch on two nouns, foo and bar.

The good news is this: dispatching at run time on two different types is a well-known problem, and the solution is called double dispatch. The problem with double dispatch is that it moves our equivalence code back into our nouns, and we don’t want that.

The Visitor pattern might be handy: it’s a way to add methods to an object at run time in a language like Java that supposedly doesn’t do that. If we decide that everything to be compared using Equivalent.evalimplements an interface called Visitable, we can build a double dispatch system that doesn’t require putting an equivalent? method in the entities being compared:

interface Visitable {
    Object accept(final Visitor visitor);
}

interface Visitor {
    Object visit(final Object obj);
    Object visit(final List list);
    Object visit(final Map map);
}

public class Equivalent {

    static boolean list_list (List foo, List bar) { ... }
    static boolean list_map (List foo, Map bar) { ... }
    static boolean map_map (Map foo, Map bar) { ... }
    static boolean object_object (Object foo, Object bar) { ... }

    public static boolean eval (final Visitable foo, final Visitable bar) {
        return foo.accept(
            bar.accept(
                new Visitor () {
                    public Object visit(final Object bar) {
                        return new Visitor () {
                            public Object visit(final Object foo) {
                                return object_object(foo, bar);
                            }
                            public Object visit(final List foo) {
                                return object_object(foo, bar);
                            }
                            public Object visit(final Map foo) {
                                return object_object(foo, bar);
                            }
                        }
                    }
                    public Object visit(final List bar) {
                        return new Visitor () {
                            public Object visit(final Object foo) {
                                return object_object(foo, bar);
                            }
                            public Object visit(final List foo) {
                                return list_list(foo, bar);
                            }
                            public Object visit(final Map foo) {
                                return list_map(bar, foo);
                            }
                        }
                    }
                    public Object visit(final Map bar) {
                        return new Visitor () {
                            public Object visit(final Object foo) {
                                return object_object(foo, bar);
                            }
                            public Object visit(final List foo) {
                                return list_map(foo, bar);
                            }
                            public Object visit(final Map foo) {
                                return map_map(foo, bar);
                            }
                        }
                    }
                }
            )
        )
    }
}

If that looks like a lot of work to you, I agree. You’re basically replicating Java’s run time dispatching on two types, so you need a bit of a matrix. Is it worth the effort? Let’s consider what this wins you:

• Your entities or objects no longer need to know all about other types of entities;


• It’s easier to make sure that commutation and symmetry are preserved when the code for a relationship is in its own class and not smeared over multiple entities.

And best of all, you have a nice place for your verbs, and they are no longer second-class citizens behind the nouns.

---

Update: A few people have suggested alternate approaches to implementing multiple dispatch in Java. I think there are various trade-offs to be made, and several different implementations ought to be considered before you write production code.

However, the point of the article is to suggest that not all functions should be implemented as methods of subject objects. I think it makes that point regardless of what you think of using a Visitor and a double dispatch.

Here’s an alternate approach from Laurie Cheers:

interface Classifiable
{
    int classify();
}

// I know this isn't valid Java, but it makes the example much clearer. The alternative is to tiresomely spell out every combination.
#define PAIR(a,b) (a|(b<<4))

abstract class DoubleDispatchable
{
    abstract Object list_list(List a, List b);
    abstract Object list_map(List a, Map b);
    abstract Object map_map(Map a, Map b);
    abstract Object object_object(Object a, Object b);

    const int OBJECT = 0;
    const int LIST = 1;
    const int MAP = 2;

    Object dispatch(Classifiable a, Classifiable b)
    {
        switch(PAIR(a.classify(), b.classify))
        {
            case PAIR(LIST, MAP): return list_map(a,b);
            case PAIR(MAP, LIST): return list_map(b,a);
            case PAIR(LIST, LIST): return list_list(a,b);
            case PAIR(MAP, MAP): return map_map(a,b);
            default: return object_object(a,b);
        }
    }
}

class Equivalent extends DoubleDispatchable
{
    Object list_list(List a, List b) {...}
    Object list_map(List a, Map b) {...}
    Object map_map(Map a, Map b) {...}
    Object object_object(Object a, Object b) {...}

    bool eval(Classifiable a, Classifiable b) { return dispatch(a,b) != false; }
}

What trade-offs, you ask? The Visitor pattern given gets the compiler to guarantee that you write each of the nine cases, whereas hand-written tests and logic simplifies the code.

I specifically chose the Visitor pattern because it seemed more in keeping with the spirit of the Java language and culture, trading verbosity for compiler safety.

I'm extremely comfortable with the other trade-off, emphasizing readability and simplicity. Although, if you go far enough down that road, you might as well look at other languages ;-)

Labels: java, lispy, popular

  ¶ 11:24 PM 22 comments

  Three stories about The Tao

That maverick framework author is self-centred and vain. His framework is all about solving his problems, his way, he refuses to look at what the market wants and build something that could be more popular.

There was once a monk who would carry a mirror where ever he went. A priest noticed this one day and thought to himself “This monk must be so preoccupied with the way he looks that he has to carry that mirror all the time. He should not worry about the way he looks on the outside, it’s what’s inside that counts.” So the priest went up to the monk and asked “Why do you always carry that mirror?” thinking for sure this would prove his guilt.

The monk pulled the mirror from his bag and pointed it at the priest. Then he said “I use it in times of trouble. I look into it and it shows me the source of my problems as well as the solution to my problems.”

Sure, the big corporate framework and its language have problems, but they pay the bills.

Once there was a horse tied up on the side of the street. Whenever someone tried to pass, the horse would kick them. Soon a crowd gathered around the horse until a wise man was seen coming close. The people said “This horse will surely kill anyone who tries to pass. What are we going to do?” The wise man looked at the horse, turned and walked down another street.

Those rabid evangelists turned me off with their attitude, so I determined then and there to never look into their stuff, ever.

A monk and his novice were walking through the forest. They come to a stream. On the bank there was a beautifully dressed woman, crying. The monks asked her what was the matter. “I am on my way to a wedding. I have to cross the stream to get there, but the bridge has been washed away. I was searching for a place to cross where I wouldn’t ruin the dress, but I can’t find one and if I don’t make it across soon, I will be late.”

Without a word, the elder monk scooped her into his arms, waded across the stream, and deposited her on the other side. Ignoring her thanks, he waded back and the two monks resume their walk. They continued on their journey, but the younger monk was agitated and obviously had something on his mind. The elder monk stopped and asked him what was the matter.

“Elder, I am confused. Our vows prohibit us from fleshly contact with women, yet you embraced that woman in your arms. How can this be?” The elder monk eyed his novice with kindly concern. “Novice,” he asked, “I left her on the bank of the stream. Why do you still carry her?”

I've read or heard these stories (and quite a few more) many times and in many forms. I borrowed the wording for the first and second story from this good page. Also, someone was kind enough to point outthat these stories are not necessarily about the Tao, and how Taoism is different from Zen, and so forth. Just so you know :-)

Labels: popular

  ¶ 3:07 PM 15 comments

  Three blog posts I'd love to read (and one that I wouldn't) “Blogging about blogging” is tiresome, and I apologize in advance for inflicting this on you: I promise to return to technical subjects immediately. But I really do want to read what you have to say, and what better way than to full-on ask you to write?

So here are three blog posts I’d love to read. Write any or all of these, and you have a guaranteed bookmark in my delicious feed and my vote on sites like programming.reddit.com and dzone.com.

What I learned from Language X that makes me a better programmer when I use Language Y

Everybody has a pet language. And many smart people take a crack at learning a new language. Some take two years to try to port an existing, production application. Some read a book and throw it across the room, unconvinced that the new language offers much in the way of value. Whether you immersed yourself in the new language or merely skimmed it, what did it teach you that you can apply to your everyday work?

I disqualify things like “Programming in Assembler reminded me how much I love Object-Oriented Programming in Common Lisp.” Bzzzt! It has to be something you didn’t know before you tried Assembler. Here’s one of my own: Ruby and Javascript support a rich literal notation for collections that made me a better Java programmer: I learned the double-brace initialization idiom and now use it regularly (I liked it so much, I wrote an entire post about it.)

LISP is worth learning for a different reason—the profound enlightenment experience you will have when you finally get it.

The most amazing example of this kind of thinking is Eric Raymond’s famous quote: “LISP is worth learning for a different reason—the profound enlightenment experience you will have when you finally get it. That experience will make you a better programmer for the rest of your days, even if you never actually use LISP itself a lot.”

You may not experience a profound enlightenment from your next language. But if your mind is open to the possibilities, I bet you’ll learn a lot that will make you a better programmer for the rest of your days. Tell us about it.

Something surprising that you probably wouldn’t guess about Language X from reading blog posts

I get that Java is verbose, that static typing finds bugs and makes it easy to add certain features to IDEs, that there are a lot of jobs writing Java programs, and that there are a lot of frameworks and libraries written in Java. Great. But one more post about those subjects had better be really, really insightful if it is going to get me excited.

What can you tell me that might not be obvious from reading the same-old, same-old blog posts out there? For example: Java’s Annotations provide a unique meta-programming mechanism that allows you to write programs that are familiar to the everyday programmer but add code-generation magic.

If I were coming to Java from the Ruby world, this might get me excited enough to really learn how to make my programs sing. I was excited to discover that the IntelliJ people have developed @Nullable and @NotNull annotations that add null-checking to Java at compile time.

The canonical example of this type of post is probably Douglas Crockford’s essay describing how Javascript is The World’s Most Misunderstood Programming Language.

My personal transformation about Idea X

Bob Sutton wrote an amazing article about one kind of smartness, Strong Opinions, Weakly Held. Now it’s great if learning a language or trying a new methodology taught you something new.

But it’s really, really fascinating if you happened to change your mind about something you used to think was critical. If you have had a 180 degree change of heart and embraced what you formerly shunned, or now shun what you formerly embraced.

And I don’t just mean write and tell me the logical reasons that Ocaml taught you how strong typing can be much more powerful than what lame-ass Language X provides. That’s true. But please, if that’s all you want to write, write “Five new things I learned from Ocaml that made me a better programmer when I use Lame-Ass language X” or “Something surprising that you probably wouldn’t guess about Ocaml from reading blog posts.”

This blog post is about YOU. Tell me about your personal journey. Give me the human story. When was it exactly that you had your Aha! moment? How did it feel to let go of years of prejudices and preconceptions? What did it feel like to take the red pill?

Now that Ruby on Rails is having its fifteen minutes of fame, people are lining up on either side of the love/hate divide and everybody seems to take its pluses and minuses for granted. But do you remember how dramatic it was when people like Bruce Tate had their “Born Again” moments? Maybe today their enthusiasm seems subjective and “unprofessional.” But there’s a human story there: when people turn their back on two, five, or even ten years of belief in something, there is a powerful story to be told.

And honestly, I want to hear your story, if you would care to tell it.

I would read any and all of the above three posts with enthusiasm and a deep respect for you stepping outside of the usual same-old, same-old blog posts about languages and tools. But if you choose to write the next kind of post, it’s going to be hard for me to get excited:

Here’s why such-and-such fhpxf tbng qvpx

I am not criticizing anyone who has strong opinions about why certain things are lame.

Just because it’s hard to prove something is lame doesn’t mean we should wander around saying that everything has its place and they’re all equally valuable and they all deserve the same real-estate in our minds.

We have to wield the axe and say NO to things, to decide that life is too short for programming in Language Z, or for struggling with Tool Omega, or for hiring people who don’t have a certain kind of degree, or whatever else you know in your heart to be lame.

But speaking as your reader, posts telling me why you’re saying “no” aren’t that helpful. They tell me a lot… about YOU and your preconceptions, not about the lame things. When I re-read my own posts about failure or about metaphors for software development, I now think they say more about me and my journey than they do about shipping software.

The most useful purpose posts about “how lame things are” serve is to help people rationalize decisions they have already made.

If I have already decided that Ruby is flawed, your post giving your seven reasons is useful ammunition when somebody asks me to justify writing Project Foo using server-side Javascript. But am I really sitting on the fence, unsure of what to do until I read your detailed critique? No.

The post that is going to push me away from the lame thing isn’t the post about how lame it is. It’s the post about the useful idea and how good it is. And that’s why I am asking—or even begging—you to write a post describing “Five new things I learned from Methodology P that makes me a better team leader when I use Methodology D,” or “Something surprising that you probably wouldn’t guess about the Factor language from reading blog posts,” or especially “My personal transformation about estimating software schedules.”

Thanks in advance.

Labels: popular

  ¶ 4:03 PM 14 comments

  We have lost control of the apparatus I am writing to you as a fellow programmer and software developer. I write in friendship and brotherhood. My heart is heavy, and the news I impart is not good: We have lost control of the apparatus.

I know, the IT department soldiers on grimly. They lost a great battle to the PCs more than twenty years ago, and it took years of struggle with NT Domain Controllers and web proxies before control could be wrestled back from the users. In some places I hear battles are still being waged over USB ports and Bluetooth. IT was lucky to find a new ally against the users in MSFT just when their ancient supporter IBM’s star was fading.

We’ve taken care of everything
The words you hear the songs you sing
The pictures that give pleasure to your eyes
It’s one for all and all for one
We work together common sons
Never need to wonder how or why

But we programmers have lost and we must be realistic about things. The fact of the matter is this: people own their own computers, and our applications are no longer the primary way they learn how computers ought to work.

I know, I know, they stare at our work for eight, ten, or twelve hours a day. So you would think that we would set the standard for how computers ought to be. But the Good Old Days when most of users had never seen a computer before work have gone. Some of our users, fresh out of school, have already been using computers for ten years!

As if that wasn’t enough, the really bad news is, when our users go home they have this thing called the Internet. I know, IT locked that down in the office. But we can’t stop them from getting on it at home, on their mobiles, and now even on those insidious Apple iPods! And when people use the Internet, they are actually using other people’s applications.

I’m not kidding. Our users are being exposed to applications we don’t control. And it messes things up. You see, the users get exposed to other ways of doing things, ways that are more convenient for users, ways that make them more productive, and they incorrectly think we ought to do things that way for them.

computers

This business of users buying their own computers is really troublesome. For one thing, they can buy a computer in the store for a few hundred dollars that is twice as good as the warmed-up left-over IT put on their desk. Until recently, we could shrug our shoulders. We weren’t the ones that had to explain that to get an up-to-date model, they needed to fill out a twenty-seven-b-stroke-six. Which needed approval. Against budget. And then IT would order it from DELL. Who don’t have the CPUs in stock.

And meanwhile, the very same users could walk across the street and buy themselves a much better PC for less money than we pay and take it home the same day. And until now, we didn’t worry about it. We’re the programmers.

But now it’s a problem. Here’s the thing: those PCs they buy at home? The ones that are two, three, or even five times better than the ones on their desk? With huge drives, and lots of memory? The thing is, they run much richer applications than the warmed-over TTY stuff we’ve been feeding them under the guise of “being hip to the Internet revolution.”

For example, my Mother uses Skype to talk to her friends. She thinks it’s normal to see all of your voice mail messages in a list on the screen. If I tried to give her a CRM application for managing contacts, the very first question she would ask would be, “Why can’t I listen to all of the voice mails from that contact in the application?”

Do you think she would have patience for my explanation that the company’s phone systems are complex and proprietary and that we can’t install Asterix just for her? She would grab me by the ear and drag me to my desk to get cracking on it!

You laugh, but users are used to a lot more functionality than a web page with a form on it these days, and if we don’t give it to them, the noise from all the whining is going to drive us insane.

I tried telling them that databases were not designed for multi-megabyte Word files and PowerPoint presentations, and they just goggle at me like I’m a circus freak and ask me why I’m using a database if it doesn’t do what they want for them?

Here’s another thing. How many monitors do your users have? One, right? There’s no point in giving them more, because we build our applications with session management that basically goes insane if they try to open two windows at once, right? Well guess what? Users have multiple monitors at home for games, and they want them at work.

And when they have them at work and you explain that no, they can’t be in the middle of doing something for XYZCorp in one window, and open a new window when a call comes in from ABCLimited, because that screws up the session, they are going to bitch and moan, because they can do two things at once in their mail application and their social network and their game. Sucks to be us.

And don’t get me started about had drives. Would you believe that users now expect—as if anyone gave them permission to have expectations—what was I saying? Oh yes, users now expect that we should store everything and anything. That’s right, they think we should be able to handle arbitrarily large text fields, with styling, and pictures, and even sound or video, all stashed away where they can find it again. They want to be able to store everything to do with an account or a customer or a project or whatever right in our applications.

I tried telling them that databases were not designed for multi-megabyte Word files and PowerPoint presentations, and they just goggle at me like I’m a circus freak and ask me why I’m using a database if it doesn’t do what they want for them? I try to tell them that we don’t have a budget for buying bigger drives, and the poor, deluded fools pull out their credit cards and offer to buy a terabyte drive over the Internet for less money than our vendors charge us per phone call.

I tell you, users refuse to sit and be trained like puppies. And the bottom line is this: we can’t keep putting HTML lipstick on a 1960s pig forever. We have to get out of the office and look at what a modern PC looks like—drive, speed, RAM, monitors, everything—and write applications that can take advantage of it.

fields

You know how all of our applications have a first-name and a last-name? This has worked for decades, you would think people would understand the value of standards, of consistency. But out there in the Internet, where there is no Adult Supervision, some of those applications have just one field for a name. You put spaces in it to separate first and last, just like writing a letter, I guess.

When I told one of our users, a business analyst, that using just one field for the name meant a huge amount of work for programmers, she actually asked me what our job was, if not to do the work that makes users productive.

Please, stop laughing. I had the same reaction. How could that possibly work? But the rogues who build that kind of heresy put in a lot of clever little rules and things so that the single field can handle case like Braithwaite, Reginald or Geroge Smithers, Esq. or even Doctor Wu properly.

When I told one of our users, a business analyst, that using just one field for the name meant a huge amount of work for programmers, she actually asked me what our job was, if not to do the work that makes users productive. I’m very much afraid that things are out of hand. I tried to explain how our database schema works, and so on, but she impatiently insisted that it was our job to make things work.

She then started lecturing me—lecturing ME!—about copy and paste, of all things. She said that it should be convenient to copy and paste between our application and other applications like Word, Excel, and even Outlook. With separate fields, you need to do multiple steps to copy a name between our applications and a letter.

I felt betrayed by Microsoft. Whatever happened to the days when people used just one application, and if they needed another we would give them an export routine? Now she wants to be able to copy a name out of an email and paste it into our application without carefully selecting the last name, first name, and honorific separately.

When I left her office, she was mumbling something about SaaS or some such. I don’t remember what she meant, but “sass” just about sums up her attitude.

If she was just one lone uppity user, I could handle it. But they’re popping up like toadstools. Just the other day another user was asking why he couldn’t paste an address as one field, including zip code. I told him I didn’t have time to explain how database columns worked, but again he muttered something disrespectful and later I saw him hefting his swingline rather menacingly while looking at our application on his screen.

Brothers and sisters, I know this is hard to take, but we’re losing this war. Our DBA cousins have brainwashed Corporate into believing that they are the custodians of the data, and of the sacred Stored Procedure that Controlleth Access. We have very little choice about how things work.

But still, the users expect us to make applications every bit as useful for them as the applications they use on the Internet, and I fear that they will rise up and revolt very soon if we don’t find a way to make the database invisible and make user applications conform to these horribly user-centric heresies.

I know, I see the pitchforks in your hands, and your desire to maul, hang, and burn the messenger is understandable. But that won’t fix things, so please put them down, ok?

stories

And don’t give me that “User Stories” flim-flam, please. I practically invented bamboozling users into doing what we want by pretending to put them in charge of an Agile Process. Agile Process indeed, anybody ought to know that if it’s a Process, it sure as heck can’t be Agile.

So you think you can do what we’ve always done, hunh? When they complain about copy and paste, write it up as a story, put it in the backlog, and then—look at that—there’s always a higher priority story to do. There’s always some new functionality that offers a greater ROI than polishing an old feature.

Well, sister, where that goes wrong is that this isn’t polish: it’s what our users expect as basic functionality. You might think it is new and improved and doesn’t add value, but what our users think is that our applications are old and broken and waste their time.

So while on paper a new feature is more important than making paste work, in practice it looks like we build software that slows the organization down.

So save your breath and stop using Agile as an excuse for slapping the crudest crap together and putting fast in front of finished.

search

You would things couldn’t get any worse. But they are worse, much worse. I’ll just say one word. Google. Those bastards are practically the home page of the Internet. Which means, to a close approximation, they are the most popular application in the world.

And what have they taught our users? Full-text search wins. Please, don’t lecture me, we had this discussion way back when we talked about fields. Users know how to use Google. If you give them a search page with a field for searching the account number and a field for searching the SSN and a field for searching the zip code and a field for searching the phone number, they want to know why they can’t just type 4165558734 and find Reg by phone number? (And right after we make that work for them, those greedy and ungrateful sods’ll want to type (416) 555-8734 and have it work too. Bastards.)

I have tried explaining that there’s an ambiguity if an account number is also 4165558734. But those damn users just give me that “Boy, you are stupid” look that made Samuel Jackson famous. They think we should just show them what we find and let them sort it out. They’re idiots, obviously, but they’re our idiots and I’m pretty sure that if we fire them all we’ll have to clean our own desks out the following day.

They don’t even get that search results should always show stuff from the same table. Would you believe, if they type a phone number, they want us to search companies and persons. They have no respect for our careful husbanding of hardware resources. The profligate spendthrifts think that just because they have a two gigahertz PC at home that can search their entire hard drive for a phone number as fast as they can type it—thanks again, Google—we should make search as fast and as easy to use in our applications.

We can use tools like Nutch and what-not for full-text search. But users want to search everything, everywhere, just like Google. And try as we might to get them to use Sharepoint, they just deride it as a heap of junk. We are going to wind up ceding control of our data to Google sooner or later. I hate to be the one to tell you this, but you might as well hear it from a friend:

You need to start coding your applications so that an external search engine can search them. That’s right, you need to work with a desktop search tool and a network search tool so that people can type 4165558734 and see everything, mail, word docs, and records in your database, in one place.

It’s the future. A miserable, groveling future where our applications work for the users instead of the users working for our applications, but it’s our future.

Suck it up and roll with it.

---

Psst! Are you Smart? Do you Get Things Done? Do you want to work in New York City using Rails and Java? Mobile Commons is hiring developers!

Labels: popular

  ¶ 2:37 PM 26 comments

  Ruminations about the performance of anonymous functions in naive Javascript implementations Block-Structured Javascript (better known as the Module Idiom) looks like this:

 (function () {
    var something_or_other;
    // code elided
    return something_or_other;
 })()

This creates a new, anonymous function with its own local scope. Whenever this code is execututed, the interpreter creates a function record in its memory. The exact same thing happens if you create a function and bind it to a variable with var foo = function (...) { ... };.

Now let’s consider another common pattern, the Inner Function: we have a function, and the function needs a helper function. We define the helper function inside our function to make our code more encapsulated:

 var factorial = function (n) {
     var factorial_acc = function (acc, m) {
         if (0 == m) {
             return acc;
         } else {
             return factorial_acc(m * acc, m - 1);
         }
     };
     return factorial_acc(1, n);
 };

What happens when we invoke factorial it six times?

When the interpreter first encounters the code defining factorial, it creates a function and assigns it to the variable factorial. Then each time we invoke the factorial function, the interpreter creates a new function record for factorial_acc. So in total, the interpreter creates seven functions in memory, not two.

hand-rolling

If this code needed hand optimization, you might want to consider ‘lifting’ the definition of factorial_acc outside of factorial, so it doesn’t get recreated with every invocation:

 var factorial_acc = function (acc, m) {
     if (0 == m) {
         return acc;
     } else {
         return factorial_acc(m * acc, m - 1);
     }
 };
 var factorial = function (n) {
     return factorial_acc(1, n);
 };

This produces exactly the same result as our Inner Function version. factorial_acc doesn’t use any of factorial’s parameters or variables, so it does not really need to be inside its scope to produce the correct result.

Now you only need two function records, not seven. Two is cheaper than seven. The problem with this approach is that you are proliferating names. If you are binding functions to names in the global environment, it quickly becomes crowded. And you also have a readability issue. Does anything else need to use factorial_acc? The original code made it very obvious that factorial_acc is only ever used by factorial.

A block can help. Yes, the cause of our performance consideration—dynamically creating functions—can actually be part of the solution:

 var factorial = (function () {
     var factorial_acc = function (acc, m) {
         if (0 == m) {
             return acc;
         } else {
             return factorial_acc(m * acc, m - 1);
         }
     };
     return function (n) {
         return factorial_acc(1, n);
     }
 })();

Now what happens? Well, we create an anonymous function for our block. One function record. Within that block’s execution, we create two more functions, one assigned to the variable factorial_acc, and one returned from the block (and then assigned to the variable factorial). This code creates three function records, which is still much better than seven.

As a correspondent summarized in email, “we’ve shown how to replace a simple function containing an inner function with a block call that returns a closure referencing the inner function so as to avoid re-defining it on each call. That’s all there is to it.”

(By the way, Douglas Crockford has done a very good job of explaining this idiom in Javascript, and named it the Module Pattern. Here’s a discussion with particular emphasis on OO-style programming. And here’s a really detailed examination from the YUI team.)

So should you always rewrite inner functions to use a block like this?

I don’t personally fool around with this kind of hand optimization willy-nilly (Of course, you may find the block version more readable than the inner function version. If you do, it’s a win to write it that way). It has a cost: in a more complex function, defining helpers outside of the function may be moving them further away from where they are used, which is a loss for readibility. If you prefer the inner function version, you should be very sure you have a performance problem before you leap to the conclusion that you should rewrite it.

a heuristic for automatic optimization of inner functions and blocks

Lisp implementations have been optimizing this kind of code, automatically, for decades. That’s because Lisp programmers have been writing programs in this style for decades, either directly or using macros like let. Here’s the basic heuristic:

• Find every function invocation that is nested inside another function.


• Analyze all of its variable references lexically. If there are no references to a parameter or local variable of its immediate parent,¹ promote the function by defining it in its grand-parent and assigning the definition to a new variable in the grand-parent.


• Replace the original definition in the parent with a reference to the variable you just created in the grand-parent.


• Repeat until all functions are either global or refer to variables in their immediate parent functions.

There’s also a well-know optimization for making blocks themselves free or nearly free: lambda lifting. So before optimizing things prematurely, test your implementation and see if it is already fast enough for your purposes.

You may discover that you don’t save anything by rewriting things yourself. (You may make your code slower: some optimizations rely on knowing the exact scope of the code being optimized. If you proliferate names by lifting things yourself, the optimizer may not be able to use all of its tricks.)

These techniques have been known for twenty-five years. If a Javascript implementation that you are forced to target doesn’t include it, why not demand that the implementers get with the program and, you know, use some of the stuff we’ve known about programming for almost as long as they’ve been alive? Especially if they brag about their prowess at creating programming languages?

conclusion: nice-to-know, but not essential

My personal conclusion is that the behaviour of a naïve implementation is a “nice-to-know.” I don’t personally worry about optimizing it until I have a known performance issue, at which point it is essential to test to see whether some of the hand-optimizations will actually help.

YMMV.

---

1. Full closures make things tricky:

Functions that refer to variables in their immediate parent scope are much trickier to optimize away. Sometimes, such a function is supposed to be created anew for each invocation of its parent. For example, if you want to construct a bank balance thingy without using objects, you might write:

    function (balance) {
      return function (amount) {
          balance = balance + amount;
          return balance;
        };
    };

You pass in an initial balance, and it gives you a single function that you can use to deposit (pass a positive number), withdraw (pass a negative number), or check the balance (pass zero). It returns the updated balance in each case.

The inner anonymous function cannot be lifted or optimized away because of its reference to balance in its parent and because the function can be shown to “escape” its parent.

Whereas in this contrived example:

    function (balance, owner) {
      return function (amount) {
          return {
              new_balance: (function () {
                  if (balance + amount >= 0)
                      return balance + amount;
                  else return balance;
              })(),
              account_owner: owner
          }
        };
    };

Although the inner function still cannot be optimized away, the block within it can be lifted into the inner function and removed, producing:

    function (balance, owner) {
      return function (amount) {
          var __temp;
          if (balance + amount >= 0)
              __temp = balance + amount;
          else __temp = balance; 
          return {
              new_balance: __temp,
              account_owner: owner
          }
        };
    };

Labels: lispy, popular

  ¶ 11:44 AM 3 comments

  Block-Structured Javascript Javascript provides closures with first-class access to variables declared in the enclosing environment. Besides being a handy piece of trivia if you are ever playing Programming Jeopardy, what use is this to the actual working programmer?

There are a lot of ways to take advantage of Javascript’s closures, I am going to describe just one, replicating Algol’s block structure (or Lisp’s let and begin macros, if you prefer). When we’re all done you’ll have a handy tool for making your code more readable, separating its concerns, and generally making life easier for programmers who have to read what you’ve written.

From Bricks to Blocks

A block is a chunk of code inside a function. Blocks have well-defined entry and exit points. Blocks have their own local variables and functions, and they also have first-class access to variables and functions defined around them. Blocks may nest.

Structuring code into blocks makes large functions more readable and easier to refactor. All of the variables and logic needed for one thing are encapsulated together in the blocks where they are needed, not scattered about in functions everywhere.

when a better design—if unfamiliar—is shown to developers or experienced users, they tend to reject it. Often, it takes careful explanation and having them gain experience with it before the improvement is understood.

While the idiom may be slightly unfamiliar to some, I think you’ll agree that it is highly accessible and not some sort of über-contruct of interest only to the self-professed hacker. And when a programmer encounters it in your code, she will have no trouble figuring out what it does and how it does it.

block structured code

I think everyone can agree that structured programming is a good thing. Functions should be composed of blocks, with the blocks linked together by constructs such as if statements:

if (some_condition) {
    // a block
}
else {
    // another block
}

Back before structured programming was introduced, there were gotos everywhere. Looking at a piece of code with labels, it was hard to know what the flow of control might be at run time. In short, you never had the confidence that everything you needed to know about that code was right there next to that code.

Like almost all modern languages, Javascript’s blocks do structure the flow of control so that you have nice clean entries and exits from each block. And also like most other modern languages, Javascript does nothing to structure access to variables inside blocks. For example:

var j = 0;
if (some_condition) {
    // a block with some code elided
}
alert(j);

What will be shown? You can’t guarantee that zero will pop up, because the blocks might modify j, like this:

var j = 0;
if (true) {
    var j = 42;
}
alert(j);

This looks like a programmer error. After all, the var keyword should be used to declare a new variable. The code between the braces isn’t really a new block of code with its own variables. This is hardly a problem with trivial examples. But if you start building some larger functions, the possibility of accidentally overwriting some code looms larger. Especially once you start refactoring and moving blocks of code around.

What can we do? How about this: the “block” idiom (you can also call it let or begin if you want to sound like a Schemer). Here’s the code:

var j = 0;
if (true) 
    (function () {
        var j = 42;
    })();
alert(j);

There’s a lot of syntactic noise, what does it mean? In short, we said: “Create a new function. In the body of the new function define a variable called j and assign 42 to it. Then call that function without any parameters.” Because our new instance of j is inside a function, it is not the same variable as the j outside of the function. That can be handy.

Are there any other benefits of this idiom? Yes indeed. Sometimes you have an assignment and you need some logic on the right hand side. How do you write:

var proven = {
    var n = Math.round(100*Math.random());
    var total = 0;
    for (var i = 0; i <= n; ++i) {
        total = total + (2*i) + 1
    }
    return total == ((n + 1) * (n+1));
};
alert(proven);

You can’t, of course. There are two problems with trying to use braces in this case. First, Javascript only allows braces to form code blocks in conjunction with specific keywords like if and function. Second, Javascript code blocks are not expressions—they do not produce values. This is why languages like Javascript need an if statement and a ternary operator: if blocks produced values, you would only need if expressions.

So in traditional Javascript style, you have to define a function somewhere else and call it… You’ll notice our block idiom includes defining and calling a function. What if our function returns a value? In that case, we can use a block anywhere we want a value, for example:

var proven = (function () {
    var n = Math.round(100*Math.random());
    var total = 0;
    for (var i = 0; i <= n; ++i) {
        total = total + (2*i) + 1
    }
    return total == ((n + 1) * (n+1));
})();
alert(proven);

This new idiom allows us to make first-class blocks anywhere we like. Our blocks are expressions, and we can use them anywhere we need a value. And as above, Our variables are fully encapsulated, they do not overwrite variables defined elsewhere.

blocks vs. named functions

You may be wondering, "Why can’t we use a named function?" This is the style in languages like Python, where the Benevolent Dictator does not permit constructions like this. Here is the above code using a named function:

var proven_helper = function () {
    var n = Math.round(100*Math.random());
    var n_plus_1_squared = function (n) {
        return (n + 1) * (n+1); 
    };
    var sum = function (n) {
        var total = 0;
        for (var i = 0; i <= n; ++i) {
            total = total + (2*i) + 1
        }
        return total;
    };
    return sum(n) == n_plus_1_squared(n);
};
var proven = proven_helper();
alert(proven);

I find this almost as good as the block. Since you only use it in one place, it is defined where you use it. That is good. And the name might be helpful documentation, just like a one or two-word comment. Balanced against this is the fact that you have added a new function to the outer scope. Reading it later, you might have to scan the rest of the code to see if it is used elsewhere.

There's also a very small advantage of the block over the named function: since you need two statements (one to name a function, another to use it), you can only use a named function in normal code blocks. You cannot use a named function when you need an expression, unless you resign yourself to naming the function in one place and using it somewhere else.

For example, when constructing array or hash literals, you can use expressions. A block is an expression, while two statements (one to create a named function and one to call it) are not an expression. So a named function would need to be defined outside of an array or hash literal, while a block can be used inside it, placing the code closer to where it is used.

block structure and cleaner code