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

  map(&"(1.._).inject(&'*')") Some working Ruby code:

 (1..3).map(&'*2') => [2, 4, 6]
 (1..3).map(&'[-1, _, 0]') => [[-1, 1, 0], [-1, 2, 0], [-1, 3, 0]]
 (1..3).map(&'x -> y -> x * y').map(&'[2]') => [2, 4, 6]
 (1..5).select(&'>2') => [3, 4, 5]
 (1..3).map(&'x -> y -> x * y').map(&'.call(2)') => [2, 4, 6]
 [5].map(&"(1.._).inject(&'*')") => [120]

See String#_to_proc.

Labels: lispy, ruby

  ¶ 10:53 PM 5 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

  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

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. If you see a variable declared inside a block, you know it is only used inside the block. If you see a variable with the same name outside the block—a regrettable occurrence—you know that moving or changing the block will not affect the code working with variables outside of the block.

You probably know that you can put a function inside of a function in Javascript:

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

And this is a good thing, it keeps the function factorial_acc inside of factorial. Since that’s the only place you need it, why declare it anywhere else? The fact that you can put a function inside of a function implies that you can put a function inside of a block as well:

var proven = (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);
})();
alert(proven);

If you only need the functions n_plus_1_squared and sum to do this one job, in this one place, why should they be defined at top level cluttering up your code? Why force other programmers to search through your code figuring out where they are used before making changes?

Block structure may seem unfamilar at first, but give blocks a try and see whether you start finding the code even easier to read and refactor with blocks. Like me, you will find that structuring your code with blocks puts the things you use right where you use them.

update: Ruminations about the performance of anonymous functions in naive Javascript implementations.

Labels: lispy, popular

  ¶ 10:08 PM 8 comments

  How to Run Javascript on the JVM in Just Fifteen Minutes what and why

This post is about executing Javascript inside the JVM without using a browser. Besides the fact that people are talking about running Javascript on the server (again, and again), here’s why my colleagues and I used it on a recent project:

We have some logic that needs to run on the server and on the client, depending on when the application applies it. There is like an incredibly complex form validation involed. Think of a loan application, for example. Zillions of rules like “at least five years at current location or at most three locations in ten years or owns current location for at least one year.” The whole thing forms a big logical expression that needs to be evaluated in such a way that we can report which pieces are missing or do not meet requirements (Declined because income is insufficient and does not state purpose of loan).

There are a couple of ways to handle this. One is to submit the form back to the server for validation. Another is to write everything in Java, but use a sophisticated tool to render the Java into Javascript. Naturally, our team chose a third option, The Rails Way (available for pre-order).

We have a Domain-Specific Language for describing the rules. Business users use the DSL, and another tool writes code from that. We could, in theory, write Java methods for the server and write Javascript for the client. We chose to start with Javascript, and we’ll write Java for the server if running Javascript on the server turns out to be unperformant slow.

In the mean time, we decided that having some Java make a simple function call to a Javascript function and process a simple result was a reasonable first step. As a side benefit, we run all our server-side Javascript unit tests in Java test suites alongside our Java unit tests.

And after some fiddling around, we got Javascript working on the JVM. My bet is that you can get it working too, and it won’t take more than fifteen minutes.

Care to try it?

step zero: the Java Virtual Machine (JVM)

You’ll need JDK 1.5 or 1.6 from Sun. If you already have this, move on to step one. Still reading? You’ll need to do a big install before we go further.

Go to the downloads page and download the latest thing they have on offer with the words “JDK” in it. You won’t need JEE (the framework formerly known as J2EE) for this exercise, but if you know what it is you know enough to decide whether to download it.

Right now, you want JDK 6u2. Go get it and suffer through the installation process.

Step one: Bean Scripting Framework

Java6 has a new framework for running “scripting” languages, and it’s built into Java6. We’re not going to use it today, just because some of you may still need to make stuff work with JDK 1.5 in production. Instead, we’re going to go get the Jakarta Bean Scripting Framework (BSF). You can download it here. We’ll need bsf.jar.

step two: fix gotchas

YMMV, but I found that I couldn’t get BSF working without including the Jakarta Commons-Logging jar. So if you don’t have this floating around, go here and download it. I experimented, and I could ignore everything except commons-logging-1.1.jar. If that was missing, BSF kakked.

step three: Rhino

Since we’re going to run Javascript, we need an interpreter. Rhino to the rescue. Download it. We’ll need js.jar.

step four: keeping things organized

Ready to code? Let’s start with a directory for all of our stuff. Call it hello_javascript. For the sake of keeping thing simple, set up the sub-structure as follows:

hello_javascript
hello_javascript\lib

You may be using a fancy IDE, you may be using a text editor and have to graft your classpaths together with chicken wire. The important thing is that your classpath, besides including all of Java’s required stuff, and your own Java classes, also includes bsf.jar, commons-logging-1.1.jar and js.jar.

We’ll put all three in the lib subdirectory:

hello_javascript\lib\bsf.jar
hello_javascript\lib\commons-logging-1.1.jar
hello_javascript\lib\js.jar

step five: “Hello, Javascript”

Let’s write some Java: create the following subdirectories and put a file called HelloJavascript.java in it:

hello_javascript\com\raganwald\public\HelloJavascript.java

Let’s give it some code:

package com.raganwald.public;

import org.apache.bsf.BSFManager;

public class HelloJavascript {
    public static void main (final String[] argv) {
        final BSFManager manager = new BSFManager();
        final Object jso = manager.eval("javascript", "(java)", 1, 1, "'hello, Javascript'");
        System.out.println(jso.toString());
    }
}

Run your new Java application. Did you see that? It interpreted some Javascript in the JVM without a browser. Check your watch. Did you need more than a quarter of an hour? I didn’t think so.

You can try more ambitious code:

 manager.eval(
    "javascript", "(java)", 1, 1, 
    "var f = function (what) { return 'hello, ' + what; }; f('Javascript);");

including other files is an exercise left for the reader

I didn’t find an easy way to get Javascript files to include other Javascript files. This isn’t the worst thing in the world, but you certainly don’t want to write anything substantial inside of Java strings. So try experimenting with reading javascript files right off the classpath.

I created a subdirectory called javascript:

hello_javascript\javascript

And you can read Javascript into your strings or Stringbuffers with some fairly simple code, thanks to a utility built into BSF:

import org.apache.bsf.util.IOUtils;

// ...

static String readScript(final String fileName) throws Exception {
    final FileReader in = new FileReader(fileName);
    return IOUtils.getStringFromReader(in);
}

That reads some script into a string. You can then prepend it to whatever you want to evaluate. Note that if you want to set up some sort of simple checking to make sure that you don’t “include” the same file twice, you will need to write yourself a little framework for that, perhaps using a Set to keep track of what you’ve already loaded.

garbage in, garbage out

This is nice, and with a little work you could make a program that reads paths to Javascript files off the commend line and executes them. But to make things really interesting, you want to find a way to get Java data into your JavaScript and do something useful with the results, not just print it as a String.

BSF provides a way to inject objects into the scripting language’s environment, so you could use that facility. When writing automated unit tests for that particular project, I chose a simpler route: I serialized the data into JSON and used that to call a Javascript function directly via BSF:

manager.eval("javascript", "(java)", 1, 1, 
    "myJavascriptFunction(" + myJSONString + ");");

This is a really bad idea if your JSON is handed you from an insecure source, such as a public web page calling you back via XMLHttpRequest, but if you trust your source, this works wonderfully.

Now what do you do with the result? If you are generating something esoteric like a Javascript function, I have no idea. In my own case, I return all values as simple trees of Hashes (Javascript objects without any special methods) and Arrays. I convert those into Java trees of Maps and Arrays:

import org.mozilla.javascript.NativeArray;
import org.mozilla.javascript.ScriptableObject;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// ...

static List unwrapNativeArray (final NativeArray na) {
    return new ArrayList<Object> () {{
        for (int i = 0; i < na.getLength(); ++i) {
            add(unwrapNative(na.get(i, null)));
        }
    }};
}

static List unwrapPrototypeArray (final ScriptableObject sObj) {
    return new ArrayList<Object> () {{
        final List<Object> sObjIds = Arrays.asList(sObj.getAllIds());
        for (int i = 0; sObjIds.contains(i); ++i) {
            add(unwrapNative(sObj.get(i, null)));
        }
    }};
}

static Map unwrapObject (final ScriptableObject sObj) {
    return new HashMap<String, Object> () {{
        for (Object id: sObj.getAllIds()) {
            put(id.toString(), unwrapNative(sObj.get(id.toString(), null)));
        }
    }};
}

static Object unwrapNative (final Object obj) {
    if (obj instanceof NativeArray) {
        return unwrapNativeArray((NativeArray) obj);
    }
    else if (obj instanceof ScriptableObject) {
        final ScriptableObject sObj = (ScriptableObject) obj;
        final List<Object> sObjIds = Arrays.asList(sObj.getAllIds());
        if (sObjIds.contains("keys")) { // a prototype enumerable/hash
            return unwrapObject(sObj);
        }
        else if (sObjIds.contains("flatten")) { // a prototype enumerable/array
            return unwrapPrototypeArray(sObj);
        }
        else return unwrapObject(sObj);
    }
    else return obj;
}

Check your watch. Are you still under fifteen minutes? Great!

Labels: lispy, popular

  ¶ 4:58 PM 8 comments

  A parable illustrating the importance of the differences between Scheme and Common Lisp in a world where Java is the Lingua Franca of Programmers An encounter on a bridge.

Labels: java, lispy

  ¶ 1:13 PM 2 comments

  Style Matters

Art Matters

Giles Bowkett has written an entertaining opinion piece, wherein he argues that the gulf between sophisticated programmer and fundamentalist programmer is far, far wider than the hairline between fundamentalist programmers that use different programming languages.

You know, blog posts with sufficient depth (anything more than “How to call a COM+ object on Windows 2000 Server using CORBA over SOAP from IE 7”) are Rorschach Blots. If you’re predisposed to affinity, you read your own thoughts in them. And indeed, I immediately liked the article, because I thought he was saying that fundamentalist programmers use Blub, and that when he talks about the limitations of languages he was saying that people matter more than tools.

Of course, he’s actually saying a little of that but also a little of something else, and what’s really important to me are the ways in which what he says are different than the things I was already thinking. A mirror is a dangerous tool for experiencing the universe!

And then I read Andrew Norris’ reply, and what struck me was that Andrew may have had the opposite reaction to Giles’ opinions: he seemed to fixate on the differences between what Giles was saying and what Andrew was thinking. But closely reading Andrew’s impassioned response, I recognize so many similarities to the two points of view that I’m shocked they aren’t both the same person.

As a colleague used to say, these two men are in violent agreement. Giles is talking about the importance of the programmer’s deep understanding, and Andrew is talking about the importance of the programmer’s deep understanding as well!

They both seem to agree without reservation on the utter dead-endedness of the fundamentalist, “all innovation stopped with the invention of language X” thinking, for all values of X (including Lisp!). You can sort out the differences for yourself, they pale in comparison.

Styling

What I find most valuable (in the sense of expanding my own thinking, not just confirming what I already thought I knew) about Giles’ post is his assertion on the value of a personal style, of having a voice, on finding something unique to contribute, something that shines through the specific language and platform you use.

Isn’t that related to the entire meta-programming/DSL thingie? This idea that the language is a platform for a program so personal it deserves its own programming language?

Isn’t that exactly what both Giles and Andrew are promoting? Giles says “develop your personal style that is independent of the programming language.” Andrew says “use the tool that fits the job.” Well, what could be more personal than bending a tool to become a new tool customized for the problem? What could be more “polyphonic?”

And Giles’ example of Avi Bryant brings up an important component of developing a personal style. Giles pointed out the common thread in Avi’s work. he suggests it is Avi’s style, and it is. But Avi can’t use that style on any arbitrary problem. To a certain extent, Avi selects problems that fit his style.

To develop a style, you must be ready to apply it to problems, and you must also be prepared to walk away from problems where it really doesn’t apply. Otherwise, you will become the jack of all trades but the master of none. of course a great programmer can use shell scripts, C, and Python. But the programmer who has equal facility with all three problem domains is inferior to the programmer who “knows enough to be dangerous” in most domains but has obtained mastery in a very few of them.

So, Develop your style. Choose problems wisely. And learn your tools deeply, so that you may choose the right tools to express your style.

Labels: lispy

  ¶ 9:27 AM 2 comments

  Steve's road into the godawful swamp

You’ve all read about the Road to Lisp. I was on it for a little over a year. It’s a great road, very enlightening, blah blah blah, but what they fail to mention is that Lisp isn’t the at the end of it.

Lisp is just the last semi-civilized outpost you hit before it turns into a dirt road, one that leads into the godawful swamp most of us spend our programming careers slugging around in.

I guarantee you there isn’t one single Lisp programmer out there who uses exclusively Lisp. Instead we spend our time hacking around its inadequacies, often in other languages.

Labels: lispy

  ¶ 7:20 AM 0 comments

  From Abstraction to Zipf Alpha…

Damien Katz raised an interesting question the other day: he wondered whether elements of computer programs followed a Zipf distribution. In other words, he wondered whether the most frequently used item occurred a lot more than the next most frequent, which occurs a lot more than the third most frequent, and so forth.

That’s an interesting question. Is it true? And if it is, what does that tell us about composing programs?

Looking at computer programs, some things seem to follow Zipf’s law and others don’t. In C++ programs, loop indices called i probably are an order of magnitude more common than those called j. Unless you use Apps Hungarian, of course. But are for loops that much more common than if statements? That might vary from place to place within a single program, but overall they might be roughly equal in frequency.

If we step up a level and look at idioms, my gut tells me that there is a strong Zipf distribution. Although each program will differ, some programs might make heavy use of lists, others of maps. Some might do a lot with closures, others with objects. These are fairly generic, of course.

If we have a look at the more domain-specific items in a program, we really see a Zipf distribution. Some things pop up again and again and again in a program, others are rare.

Why Abstract?¹

The most important tool we have for composing programs is abstraction. When we create an abstraction for something, we get one and a half wins (a sesqui-win).

The full win is that we get to take a common element and place its responsibility in once place. For example, if your language gives you a map function or method, there is one place for the code that applies a function to each element of a collection and produces a collection of the results. Unlike a “pattern,” you don’t have to re-implement map every time you use it, you just use it. The centralization of responsibility in a single place is very powerful way to separate concerns.

The half win is that we don’t need to understand its implementation, we only need to understand its interface. I honestly don’t know whether Ruby’s built-in map method applies itself to a collection one at a time from the start to the end or in some other order. I suspect it’s from start to end for ordered collections, but I don’t know and I don’t have to know.

This is only half a win, because for anything too complicated to explain on a PowerPoint slide where you are promising the newest silver bullet, abstractions have a nasty habit of leaking. Leaky abstractions force you to understand the implementation to use them.

There are some drawbacks to abstractions. As noted, sometimes the abstraction leaks. In that case, you often have to look up what an abstraction does. If there was no abstraction and the implementation was right there in the middle of your code, you wouldn’t have to look it up. So when you see:

class BlogPost << ActiveRecord::Base
    has_many :comments
    # ...
end

You obviously to need to know that has_many creates methods like comments, comment_ids= and comments<< automagically for you. In fact, that is kind of the point of has_many. But if you are doing anything non-trivial, you also need to know whether has_many actually defined comments, comment_ids= and comments<< or whether it has merely modified BlogPost to handle those messages. In that sense, the abstraction leaks.

You get much the same thing if you build a Java class hierarchy that is umpteen levels deep festooned with abstract base classes, factories, and dependency injection. In one sense you get a really tight abstraction. In another sense, you have a big leak: you need to know its internals to get any real work done.

Another drawback to abstractions fall out of their strength. If you haven’t seen a particular abstraction before, you don’t know what it does and how it works. Contrary to popular hype, self-documenting names are not enough. If you are a Rails user, raise your hand if you can tell me what all of the various options for has_many are and what they do. You have to learn each abstraction’s interface, just as you had to learn what a for loop does for you.

The win (not having to know how it works) is also a loss (not knowing what it does).

An abstraction is an abstraction is an abstraction

I think most people agree that named subroutines (or functions, or procedures) are an excellent abstraction. First-class functions and anonymous functions seem to be an acquired taste (just one taste, and your programs will quickly acquire them). Objects—in the strong sense of polymorphic programs—are well-regarded abstractions.

Macros, DSLs, and other means of writing your own mini-language provoke the wildest claims of productivity and equally baseless fears of unreadable, fragile, “magic” code built out of gossamer dreams.

What these all have in common is that these functional abstractions live happily within the syntax provided by the host programming language. They abstract function without abstracting syntax. For the most part, non-syntactic abstraction is uncontroversial.

There seems to be debate over syntactic abstraction. Macros, DSLs, and other means of writing your own mini-language provoke the wildest claims of productivity and equally baseless fears of unreadable, fragile, “magic” code built out of gossamer dreams. The basic “problem” with syntactic abstractions like has_many in Rails or let in Scheme is that syntactic abstractions force y