ruby.reddit.com Reddit is now experimenting with user-generated reddits, and one of the new ones is reddit for ruby hackers. For the three people who have never heard of reddit, this is a link aggregation site where you can vote on ruby articles, something like Digg and Dzone.



The Ruby reddit is important, and if you patronize link aggregators like this, I encourage you to please post good Ruby links, vote for the links you like, and perhaps even participate in the comments.

There is already a programming subreddit, but the Ruby reddit is appears to be an entirely distinct “space.” Posts can be in programming.reddit com and in ruby.reddit.com, and there are separate posts and comments. What this means is that Ruby programmers can vote for links and exchange comments without getting into tiresome flame-wars with people who do not care for Ruby.

Of course, you are still free to defend Ruby against Smug Haskell Weenies over in programming.reddit.com. It isn’t an all-or-nothing choice. I look forward to seeing you there!

Labels: ruby

  ¶ 12:39 PM

  Object#andand & Object#me in Ruby At Mobile Commons, we have to write a lot of code under time constraints. We also work on a fairly distributed basis, which means that writing readable code is not a luxury, it’s a necessity. We can’t afford to be clever for clever’s sake, but if a new idiom helps make our code easier for our colleagues to grasp in a hurry, we embrace it. Here’re some idioms we’ve recently created:

Object#andand

Ruby programmers are familiar with the two guarded assignment operators &&= and ||=. The typical use for them is when you have a variable that might be nil. For example:

@first_name &&= @first_name.trim
@phone ||= '612-777-9311'

You are trimming the first name provided it isn’t nil, and you are assigning ‘612-777-9311’ to the phone if it is nil (or false, but that isn’t important right now). The other day we were discussing the guards and we agreed that we wished there was a guarded method invocation operator. Here’s an example of when you would use it:

@phone = Location.find(:first, ...elided... )&&.phone

Meaning, search the location table for the first record matching some criteria, and if you find a location, get its phone. If you don’t, get nil. (Groovy provides this exact functionality, although Groovy uses ?. instead of &&.) However, &&. won’t work because &&. is not a real Ruby operator. So what do we write instead?

A feature is “powerful” when at least one of the following holds:

1. It can be used to implement something trivial in an pointlessly complicated way.
2. It can cause a lot of damage.

Seriously, it seems like 85% percents of the contexts where something is called “powerful,” it really means “useless and dangerous.”

How about:

@phone = (loc = Location.find(:first, ...elided... )) && loc.phone

Note that we need a local variable to make it work without extending the Object class. Note further that although we only need the local variable for one line of code, it is in method scope and we must be careful that we don’t clobber an existing loc variable. And when reading this code, we now have to look and see whether loc is used again to understand what this line does.

This is a scoping problem. if you are going to use variables, you want to restrict their scope as much as possible. It feels like half of what we do when programming is manage side effects like overwriting a variable you are using elsewhere, and the more you can restrict those side effects, the easier programming becomes. Java supports block scoping natively, and languages like Scheme solve this by providing a block scope macro, let. And you can roll your own in languages like Javascript that provide anonymous functions. But this seems to get the natural left-to-right order wrong:

@phone = lambda { |loc| loc && loc.phone }.call(Location.find(:first, ...elided... ))

Well, we are tinkerers and toolsmiths. So let’s roll our own. We can’t use &&. without rewriting the Ruby parser, and that seems drastic. So let’s use “andand” in the hope that our non-English-speaking colleagues will forgive us. We want to write:

@phone = Location.find(:first, ...elided... ).andand.phone

And get the same effect as @phone = ->(loc){ loc && loc.phone }.call(Location.find(:first, ...elided... )). This would be bloody trivial if we have a macro facility, but “If wishes were horses then beggars would ride.” Instead, we need to write a method that does some conditional evaluation for us. If the receiver (in this case the result of Location.find(:first, ...elided... )) is truthy, like an ActiveRecord model, we want andand to return it so we can use it. But if it is falsy, we want andand to somehow return something that takes any message you send it and returns itself without doing anything. In other words, we want a mock object of sorts. So that’s what we’ll do:

class Object
    def andand (p = nil)
      self or MockReturningMe.new(self)
    end
end

class MockReturningMe
  instance_methods.reject { |m| m =~ /^__/ }.each { |m| undef_method m }
  def initialize(me)
    @me = me
  end
  def method_missing(*args)
    @me
  end
end

Actually, there is more to it than this, for example the MockReturningMe class is enclosed in a module to minimize namespace pollution. Consult the source and RSpec (links below) for the latest particulars.

Note that because you accept any method using Ruby’s method invocation syntax, you can accept methods with parameters and/or blocks:

list_of_lists.detect { ...elided... }.andand.inject(42) { ...elided ... }

Some of the other solutions to this problem that use send change Ruby’s syntax. This solution emphasizes syntactic regularity: the goal was to make an “&&.” operation that worked like &&=. &&= looks just like normal assignment, you can use any expression on the RHS, only the semantics are different. The andand method also works just like a normal method invocation, only the semantics are modified.

Enhanced Object#tap

(Formerly called Object#me)

Ruby 1.9 includes Object#tap:

Location.find(:first, ...elided... ) do |location|
    puts location.inspect
end
   => location

Ruby On Rails includes a similar feature, the returning idiom:

returning(Location.find(:first, ...elided... )) do |location|
    ...elided...
end
   => location

Both return the location, not whatever happens inside the block. This is very useful, especially when chaining methods in a pipeline. Sometimes you want to do something for side effects, but continue on with the chain. For example:

returning([1, 2, 3, 4, 5]) do |arr|
    arr.pop
end.map { |n| n * 2 }
    => [2, 4, 6, 8]

There are going to be times that using a method instead of a function makes the code more consistent. So let’s imagine what that would look like:

Location.find(:first, ...elided... ).tap do |location|
    ...elided...
end…

This is much nicer when you are “injecting” some extra code into the middle of an expression, such as when adding some poor-man’s-debugging puts statements.

Would we ever want to go beyond a block and write Location.find(:first, ...elided... ).tap.some_method instead of Location.find(:first, ...elided... ).tap do ...elided... end? Of course we would! Quite often, we want to send several methods to the same receiver. In Smalltalk, the semicolon does this explicitly. In Ruby, we have to be very careful to make sure our methods return self to enable chaining. For example:

[1, 2, 3] << 4 << 5
    => [1, 2, 3, 4, 5]

But if a method doesn’t return the receiver, chaining doesn’t work. That’s why we had to use “returning” in the array example above:

[1, 2, 3, 4, 5].pop.map { |n| n * 2 }
    => NoMethodError: undefined method `map' for 5:Fixnum

That’s because [1, 2, 3, 4, 5].pop => 5, not [1, 2, 3, 4]. So instead, we write:

[1, 2, 3, 4, 5].tap.pop.map { |n| n * 2 }
    => [2, 4, 6, 8]     # or we write...
[1, 2, 3, 4, 5].tap { |arr| arr.pop }.map { |n| n * 2 }
    => [2, 4, 6, 8]     # both work

When you examine the source, you’ll see that tap looks a lot like andand. No surprise, we are doing similar things with slightly different semantics.

This implementation of Object#tap has two advantages over the implementation in Ruby 1.9: first, it works in Ruby 1.8. Second, it adds the ability to call another method (like pop) and not have to include a block.

Summary: andand & enhanced tap

andand and tap both provide the same two benefits: First, they either eliminate (in the case of a method call) or limit in scope (in the case of a block) a local variable. Second, they let you maintain a natural left-to-right order when writing pipelined expressions. They are simple and obvious enough that I feel any unfamiliarity for the reader will be more than outweighed by the cleaner, easier-to-digest code that results from their liberal use.

My suggestion is that these two benefits make it worth your while to add these methods to the Object class and use them regularly in your code.

Installation

sudo gem install andand. For the source and more information, http://andand.rubyforge.org.

---

Similar solutions:

1. Kernel#ergo in Ruby Facets
2. send_with_default
3. maybe
4. _?
5. if_not_nil (via François Beausoleil)
6. Groovy’s Safe Navigation Operators via Call by Name: "Yo Elvis"
7. try() and A better try

---

postscript: Inline Rescues

I have now seen two people asking about using an inline rescue instead of andand:

Location.find( …elided… ).phone rescue nil

Also, one of the alternate solutions seems to use this technique. Obviously, it works for many of the cases you want to try, and you don’t need to add a new method to Object. However, it is—to paraphrase Chalain—“Sneaking up on the Interpreter.”

It achieves what we want almost by accident, namely that it rescues NoMethodError, which by coïncidence gives us the result we want. However, it does not communicate our intent. It says that we want to transmute all exceptions into a value of nil. When someone glances at the code, will they think of NoMethodError? Or will they assume that we are trying to handle exceptions that the .phone method might throw?

And what if .phone actually throws something serious? In Rails, what happens if a migration is screwed up and there is no phone column? I think we actually want a NoMethodError in that case. The rescue clause will accidentally swallow the exceptions we are trying to catch.

I think if you are absolutely certain that you do not care about other exceptions and also if your team uses this idiom extensively so that it does not miscommunicate its intent, you can live a long and happy life using it. However, I would be hesitant to recommend it as a general-purpose solution. andand and some of the other solutions obviously require the code reader to learn a new method name, but after that they offer the exact functionality we need and clearly communicate their intent.

Labels: ruby

  ¶ 9:09 PM

  Ruby is soooooo 2002 I first heard about Ruby when Matz spoke at LL2 in November, 2002. I experimented with it on and off over the next few years, and I liked it. I also experimented with C#, Groovy, and a few others, but Ruby reminded me of Smalltalk, a language I used in the 80s and loved, so I stuck with it even though I seemed to be one of three people using Ruby without using Rails.

Lately, the internet echo chamber is souring on Ruby and moving from embracing it to hating it. I suspect that although people are quoting all sorts of technical reasons for their dislike, it comes down to cultural forces. Shrug.

I am reminded of the time I showed up in high school one September on a skateboard. To give you an idea of where skateboards were in those days, my model had clay wheels designed for wood-rink roller-skates, not the polyurethane we have today. Any ways, everyone laughed at me. The next Summer, everyone had one, and they were laughing at the fact that I didn't ride the latest model, even though I was a more accomplished free-styler and slalom rider. Then, the fad passed, and I was the iconoclast again, still riding my board while everyone embraced mopeds.

Guess what? There is no villain in the story. I was happy riding with my friends. The people who jumped on and off fads were happy, and they were learning important life skills about participating in human culture. And the fad was a big win: Early boards really weren’t very good, and the popularity brought money and manufacturing scale to skateboarding that improved the technology.

Paul Graham has said that the real world is nothing like high school. I’m not so sure.

---

I often use Ruby for code examples. What do you think: Should I continue using Ruby, or should I use another language for examples? If I continue using Ruby, should I try to show idiomatic Ruby or should I try to focus on general ideas that can be applied elsewhere?

Code examples should be:
	Ruby-specific
	Anything but Ruby
	Ruby, but general
	A mix of specific and general ideas
pollcode.com free polls

Labels: ruby

  ¶ 11:12 AM

  Why Rubinius Matters to Ruby's Future I am a long-time fan of self-hosted languages. In that post I listed the reasons I thought that a language should be mostly or entirely written in itself. Here’s another reason writing a language in itself is important: If a language’s core libraries and frameworks are written in that language, it is possible for every programmer to improve on them.

Ruby’s core libraries are written in C. Here’s the source for Ruby’s collect method:

/*
 *  call-seq:
 *     array.collect {|item| block }  -> anarray
 *     array.map     {|item| block }  -> anarray
 * 

 *  Invokes block once for each element of self. Creates a 
 *  new array containing the values returned by the block.
 *  See also Enumerable#collect.
 * 

 *     a = [ “a”, “b”, “c”, “d” ]
 *     a.collect {|x| x + “!” }   #=> [“a!”, “b!”, “c!”, “d!”]
 *     a                          #=> [“a”, “b”, “c”, “d”]
 */
static VALUE
rb_ary_collect(ary)
    VALUE ary;
{
    long i;
    VALUE collect;

    if (!rb_block_given_p()) {
    return rb_ary_new4(RARRAY(ary)->len, RARRAY(ary)->ptr);
    }

    collect = rb_ary_new2(RARRAY(ary)->len);
    for (i = 0; i < RARRAY(ary)->len; i++) {
    rb_ary_push(collect, rb_yield(RARRAY(ary)->ptr[i]));
    }
    return collect;
}

Perhaps you like working with Haskell-style fold and unfold rather than the Smalltalk-style collect, select, and detect. No problem, you can hack your own in Ruby, like this:

class Object
  def unfold options = {}, &incrementor
    return [] unless options[:while].nil? || options[:while].to_proc.call(self)
    transformed = options[:map] && options[:map].to_proc[self] || self
    return [transformed] if options[:to] && options[:to].to_proc.call(self)
    incrementor.call(self).unfold(options, &incrementor).unshift(transformed)
  end
end

One hitch: your fold and unfold are hundreds of times slower than Ruby’s built-in-C methods and classes. It reminds me of Newton programming. Apple gave us a really cool language—NewtonScript—for writing applications. Except, the built-in applications were written in C, and the C compiler was only for Apple engineers.

The good news about Ruby is that you can write your own classes in C if you want to. But that is a significant barrier to entry for many programmers, shrinking the available pool of programmers who will enhance the language.

Having core libraries in C is a great choice for implementing a language that is to be used for other things like building web applications. But it is not a great choice for a language that is to be used to build other languages. And “building other languages” is exactly what Bottom-Up Programming or Meta-Linguistic Abstractions are all about. In other words, writing the core libraries in C is not a great choice for a language where programmers write their own abstractions.

Now for many things, the speed penalty of writing your own abstractions in Ruby is negligible. But not everything. So there is always going to be this class of things—and I think collection manipulation is one of those things—where you need to be able to write stuff that is as good as what comes out-of-the-box.

If new stuff is an order of magnitude slower, you might be able to use it for non-critical things, but your chances of persuading anyone else to use it are very low. Which means that the language as a whole progresses slowly because real progress can only happen in areas where performance doesn’t matter. Like database-bound web applications.

Having an implementation where the built-in stuff is on the same footing as your stuff opens up the doors for actual progress. It forces the language itself to be Good Enough, and it makes it possible for every Ruby programmer to improve the language.

what we can learn from java, whoops smalltalk

Java has this incredibly powerful and popular IDE, Eclipse. It is so powerful that many people feel it is impossible to write production Java code without it. Why is it so powerful?

One of the major reasons it is both powerful and popular is the availability of plug ins. It seems to support the language, UML diagrams, source code control, and everything up to (I’m pretty sure) time tracking for client billing. Naturally, the plug ins are written in Java, just like the almost all of the built-in functionality.

Clara Creative can write her own plug in and it won’t be a second-class citizen. And since it is a tool for Java programmers, Clara Creative already knows how to write plug ins, she doesn’t need to drop into another language.

Wow, that is neat. And it does help explain why Eclipse has so many plug ins, and why they are popular: there is no low-level language barrier, and they all on an equal footing with each other.

This shouldn’t surprise you. Eclipse evolved from IBM VisualAge Micro, which was written by Smalltalk programmers in Smalltalk. And of course, Smalltalk is a language where almost everything is written in Smalltalk itself. Smalltalk programmers expect to be able to extend the language and environment without penalty.

In the end, the choice of whether to implement core features in C or Ruby will always be difficult. The temptation to optimize for speed will always be strong, especially when the language is fighting for mind share. But extensibility and variety is also a win, and Ruby fights with its libraries and features as much as with its performance.

Perhaps we won’t all be using fold and unfold instead of collect, select, and detect. But if we aren’t, it ought to be because we prefer the originals, not because the replacements are crippled in comparison, or because the kind of person who likes inventing new tools prefers to write them in Ruby instead of in C.

---

I’m looking forward to hearing more from the Rubinius team. I really think they hold the key to the future. Thanks, Ezra, for your comment.

Labels: ruby

  ¶ 5:05 PM

  The Grinch Who Stole the Ruby Jobs A reader was kind enough to point out that making statements about jobs being advertised could be misconstrued as a statement about the policies of the companies doing the hiring.

I do not speak for any hiring company, and I’m sure that hiring companies do not particularly want me articulating their policies for them.

Therefore, my policy hereforward is that when I wish to describe a job, I will provide links to open positions or name companies hiring. If I quote something, it is partially or fully information provided by the company and it will be indicated as such in quote marks.

I know, what a bother. Sheesh. But there you have it, that seems to be the way the world works. Roll with it and let’s move on.

---

mdlogix, a rapidly growing medical research software company is seeking Ruby on Rails developers for our downtown Toronto office.

We're looking for passionate developers who love Rails and want to make the world a better place by supporting clinical research!

For more information, visit http://www.mdlogix.com/aboutUs/jobSoftwareEngineerToronto.html or speak to us at the next Rails pub night!

Hewitt Associates is looking for a “P/A with Ruby on Rails experience,” possibly in Toronto (No link: they use an HR application for job listings that supports nice searches but mightily resists bookmarking).

GigPark is a Toronto-based web startup that's growing fast
Built with Ruby on Rails and hosted on EC2
We develop iteratively and release weekly
We care about quality - our code is well-designed and tested
We work hard, but smart. We believe less code is better and simple UI design is key We're not religious about technology. We believe in using the right tool for the job

http://www.gigpark.com/page/jobs

Mobile Commons is looking for “junior and senior hackers”.

Labels: ruby

  ¶ 2:41 PM

  Utility Belt Utility Belt is a grab-bag of tricks, tools, techniques, trifles, and toys for IRB, including convenience methods, language patches, and useful extensions. It also includes a couple command-line widgets. Its primary inspirations were an awesome gem called Wirble and a blog post by Amy Hoy called “Secrets Of The Rails Console Ninjas”.

INSTALL

sudo gem install utility_belt

FEATURES

• Interactively edit IRB code in your preferred text editor


• Read from and write to OS X clipboard


• Post your code to Pastie with one command (OS X only)


• Kick-ass Unix-style history buffer


• Write command history to file or vi


• Grep classes and methods for strings


• Verbosity controls for regular IRB and Rails console


• Finder shortcuts for Rails console


• Upload shortcut for Amazon S3


• Command-line Amazon S3 upload script


• Command-line Google shortcut (OS X only)


• Auto-indentation


• _ special variable (like Unix shell var !!)


• Extremely basic themes for Wirble syntax coloring


• Pascal/JavaScript-style “with” statement


• String#to_proc


• Grammatically-correct is_an? method - no more “is_a? Array” statements


• One-character exit command

---

Who can resist publicizing a grab-bag gem that just happens to contain some code you snarfed from someone else? Not me! It’s like one of those vanity books of poetry: your poem is included provided you buy twenty copies for your friends and family…

Labels: ruby

  ¶ 7:51 PM

  Fun with Symbol#to_proc

If you want a golden rule that will fit everything, this is it: Have nothing in your houses that you do not know to be useful or believe to be beautiful.

Most people love Symbol#to_proc sugar in Ruby:

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

And Googling around, all of the examples I could find were for unary methods like this. But what about binary methods like :merge? If Symbol#to_proc supported binary methods, you could do things like:

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

Or:

[{ :foo => 1 }, { :bar => 2 }, { :blitz => 3 }].inject &:merge
    → {:foo=>1, :bar=>2, :blitz=>3}

That would be brilliant.¹ And the implementation can’t be that hard in a language like Ruby, can it? Let’s have a look at the source code (I don’t have the Ruby 1.9 source, but I do have Symbol.rb from the Rails Core Extensions):

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

Would you look at that, Symbol#to_proc already handles methods with arguments. And indeed, the examples above work right out of the box in Rails. I expect them to work in Ruby 1.9 as well.

You still can’t do some of String#to_proc’s other point-free tricks like collection.map(&'*2'), but quite frankly this is a really nice feature that deserves more publicity. So… don’t forget that Symbol#to_proc handles your unary and binary methods.

Cheers!

1. I know what you’re thinking, but try to remember that the other meaning of the word “brilliant” is shiny and sparkling.

p.s. You’re wondering where I get the time to think up stuff like this? Actually, I’m lucky enough use stuff like this for a living. I needed to fold a collection of hashes together, and my first thought was that I’d like to write .inject(&:merge) to do it. This is the principle of least astonishment in action…

Labels: ruby

  ¶ 8:52 PM

  How I've been spending my time off work lately The weather being fine, and in the flagrant pursuit of happiness, I’ve managed to get a few holes in this week (using Ruby of course). Here’s my scorecard:

 palindrome =  (+(+[] | +[-:_] | ((-'[0]' >> -:ends) & (-'[1..-2]' >> -:p) 
               & (-'[-1]' >> -:ends) & -:_)) >> (-:'{}' >> -:p)).call
(palindrome =~ []).should_not be_nil
(palindrome =~ [:fish]).should_not be_nil
(palindrome =~ [:fish, :dog]).should be_nil
(palindrome =~ [:fish, :dog, :fish]).should_not be_nil
(palindrome =~ [:fish, :fish, :fish, :fish]).should_not be_nil
(palindrome =~ [:fish, :fish, :fish, :fish, :fish]).should_not be_nil
(palindrome =~ [:fish, :dog, :dog, :fish]).should_not be_nil
(palindrome =~ [:fish, :dog, :cat, :dog, :fish]).should_not be_nil
(palindrome =~ [:fish, :dog, :cat, :fish]).should be_nil

Perhaps Guido has a point, indentation matters:

palindrome = (
    +(                            # we'll start by creating a pattern
        +[]    |                  # match the empty list, or:
        +[-:_] |                  # match a list containing anything
                                  # (-:_ matches any one entity), or:
        (                         # alternative three:
            (-'[0]' >> -:ends)  & # extract the first element and
                                  # bind it to 'ends'
            (-'[1..-2]' >> -:p) & # and everything from the second to the
                                  # second-last will be matched against a
                                  # pattern :p
            (-'[-1]' >> -:ends) & # and the last element must match whatever
                                  # was bound to 'ends' above.
                                  # it's equally effective to include
                                  # -'_[0].eql?(_[1])', same thing.
            -:_                   # if all that matches, match the entire array
                                  # so that the result is the entire array, not
                                  # whatever part of the array we were just
                                  # matching
        )                         # therein ends the pattern
    ) >> (-:'{}' >> -:p)          # pass the pattern to a closure-maker (-:'{}')
                                  # and then bind it to 'p' so that the pattern
                                  # is now recursive: this pattern matches an
                                  # empty list, a list with one element, or
                                  # a list with the first and last elements eql?
                                  # to each other and whatever is in-between them
                                  # matching the palindrome pattern bound to 'p'.
).call

Hmmm. Still doesn’t make any sense. I guess home-brew programs are like babies: they appear to be delightful and impart a sense of wonder in the mysteries of the universe to their creators, but are noisy and obstreperous to everyone else.

f = (
    +(
      (-'==0' >> -'0') | 
      (-'==1' >> -'1') |
      (-'n>1' >> -'n * f[n-1]') ) >> (-:'{}' >> -:f)).call
f[0].should == 0
f[1].should == 1
f[2].should == 2
f[3].should == 6
f[4].should == 24
f[5].should == 120

Labels: ruby

  ¶ 3:42 PM

  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

  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

  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

  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

  Java is the right answer to the wrong question, Ruby is the wrong answer to the right question

Large code bases are the problem, not the language they’re written in. Find a way to break/decompose big code bases into little ones.

Can we please stop calling each other silly names over the languages we choose and move on to calling each other silly names over our choices for writing literate programs, eliminating redundancy, decoupling modules from each other, and so forth?

The very next time you find yourself being drawn into a debate about Java vs. Ruby, try saying something obscure, such as, Java is the right answer to the wrong question, Ruby is the wrong answer to the right question and see if you can redirect the energy towards exploring new ground instead of stagnating in the same old tired place.

Do not follow in the foot steps of the Sages. Seek what they sought.

When we argue Java vs. Ruby, or testing vs. type checking, we are arguing about foot steps. Take the debate to the next level. What is it we are trying to accomplish with those features? What are we seeking?

My favourite example of this is the subject of automatic refactoring. My current text editor doesn’t perform automatic refactoring (ducks). Are you about to blast a flaming comment or perhaps an entire blog post explaining what a dunderhead I am for not using an IDE that can move a method with a single dialog box?

Stop for a moment. Why do we move methods? What are we trying to accomplish? What is it about our code after we have refactored that makes the code better? Now you have a really juicy comment to make, a deep and insightful point of view to bring to a discussion. Let’s talk about that quality of good code first, and then we can talk about how to get there later, if ever.

So the next time you read that “Strong, static typing is superior because it enables the IDE to provide automatic refactoring support,” take a deep breath. Don’t nod and agree. Don’t shake your head and disagree. Ask a polite question: What are we trying to accomplish with automatic refactoring? And when told that “Unit tests are superior to compiler type checking for catching bugs,” don’t settle for “catching bugs” as axiomatic. Ask what quality really means for code.

Nothing is going to save us from talking ourselves to death. But at least we can debate at a higher level of abstraction.

Labels: ruby

  ¶ 7:02 AM

  Breaking News: Write a Ruby function. Win a $100 Bounty! I just spotted this on the Toronto Ruby on Rails mailing list:

---

/me thinks it’s too quiet here. Time for a Sunday afternoon ruby
challenge!

$100 for the best implementation, good until 6pm tonight (September 16, 2007).

THE PROBLEM

Marcel’s Amazon S3 gem presents files stored in a bucket as an object
which exposes a key attribute that conceptually map to the idea of a
file in a filesystem. You can fake a folder hierarchy by uploading 0
byte files with a key ending in a / (eg. folder1/ )

Your mission is to convert the objects array of an S3 bucket to a
Hash, so that we can present a tree view to the user. It should
support an arbitrary depth, and make good use of Ruby best practices.

THE TEST DATA

Let’s assume you have a bunch of items in a bucket, and if you iterate
through the item keys, you’ll get this list:

folder1/
folder2/
folder2/folder4/
folder2/folder5/
folder2/folder5/temp6.txt
folder2/temp3.txt
folder2/temp4.txt
folder2/temp5.txt
folder3/
folder3/temp7.txt
temp1.txt
temp2.txt

This covers all cases; a hierarchy of files in folders, including
files in the root and empty folders.

THE SOLUTION

results = {
 "temp1.txt" => #<AWS::S3::S3Object:0x31ab7bc>,
 "temp2.txt" => #<AWS::S3::S3Object:0x31ab7bc>,
 "folder1" => {},
 "folder2" => {
   "temp3.txt" => #<AWS::S3::S3Object:0x31ab7bc>,
   "temp4.txt" => #<AWS::S3::S3Object:0x31ab7bc>,
   "temp5.txt" => #<AWS::S3::S3Object:0x31ab7bc>,
   "folder4" => {},
   "folder5" => {
     "temp6.txt" => #<AWS::S3::S3Object:0x31ab7bc>
   },
 },
 "folder3" => {
   "temp7.txt" => #<AWS::S3::S3Object:0x31ab7bc>
 }
}

In other words, for each item in the hash, the name is the key without
any preceding path, and the value is the AWS::S3::S3Object that the
key points to. (I just pasted the same object in the example.)

And… go!

Pete Forde, unspace.ca

---

Do you want to win the $100? Pete told me that your solution is eligible to win provided you post it to the TorROR mailing list by 6PM, September 16th, 2007 (EST). For more details, see the TorROR Google Group.

Labels: ruby

  ¶ 2:07 PM

  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 you to learn their interface.

They are right in your face, especially if they are very brief. Consider:

BlogPost.find_or_create_by_name('From Abstraction to Zipf').comments << Comment.new('bleh!', 'anonymous')

Don’t bother searching for the find_or_create_by_name method or the comments<< method in the code base.

All the same, syntactic abstractions are just like functional abstractions. You get some wins, and you pay some costs in understanding and potential “leakiness.”

Zipf to the rescue

So should we zealously abstract everything we can? Or should we conservatively avoid “magic” like syntactic abstractions?

Every abstraction has a fixed learning cost. That cost is amortized over all of the instances we’ll encounter. So you need to learn how has_many works just once, and then you benefit every time you read it or write it. This is why abstractions built into a programming language are big wins: you amortize their cost over every program written in the language. Isn’t that why Java and C# look so much like C++ which looks so much like C? They were offering abstractions that have been paid up for years.

Zipf’s law tells us that each application only needs a very few new kinds of abstractions to get most of the benefits. There are only a few low-hanging fruits, but each is plump and juicy.

An abstraction built into a framework like Rinda or MapReduce is amortized over fewer programs. A domain-specific abstraction for a single organization is amortized over a very few programs, and an abstraction built into one program is only amortized over instances in the one code base. Unsurprisingly, opportunities for abstraction follow the Zipf distribution.

Of course, that distribution is self-similar: the abstractions within a program follow the same distribution as the abstractions within an organization. So even if you aren’t inventing a new programming language, Zipf can help.

Quite simply, it pays to aggressively abstract the few things that are encountered the most frequently. In a CRUD web application, schema relationships like belongs_to are incredibly frequent. There’s a big win from creating a syntactic abstraction, even if the learning curve looks daunting to newcomers. Creating a domain-specific language for database schema changes is also a big win.

Note that we aren’t saying that has_one, belongs_to, and has_many appear more than 50% of the time. They may be quite infrequent. The point is that they are far more frequent than something else you could abstract, and the other thing will take just as much time to learn to read but will pay off far less often.

But should you create a DSL for list comprehensions in your CRUD application or just use the language’s built-in collections? I would say, you would need an application that uses an awful lot of lists before a syntactic abstraction for lists is a win.

It might be, but the nice thing is, it probably won’t be close: Zipf’s law tells us that each application only needs a very few new kinds of abstractions to get most of the benefits. There are only a few low-hanging fruits, but each is plump and juicy.

…Omega

I think it is a win to use aggressive abstraction techniques like metaprogramming, but only if you restrain yourself to abstracting the very few things that appear most frequently in your code base. The things that are used less frequently should be abstracted using less aggressive techniques.

The resulting program may not be magically 50% shorter than an unabstracted program, because the “long tail” of idioms and patterns are simply not worth abstracting away even though we have the tools for doing so.

You can probably tell whether a program has the proper level of abstraction just by checking its distribution.

If you find a big abstraction framework for one thing while frequently used idioms are expressed using patterns instead of abstractions, you are probably looking at an improperly abstracted program. You have to wade through verbiage to read everything, and the one time you don't need to abstract the code away, you have to chase definitions through indirection.

And in a well-written program, I would expect that the things that occur most frequently are expressed at the highest and most powerful levels of abstraction, while things that happen infrequently are expressed in a more direct and explicit way. Such a program would be easy to read throughout.

---

1. Why Abstract? is a delightful and wonderfully brief book that explains the appeal of abstract art in a simple and direct way. It’s one of the treasures on my bookshelf and I urge you to find a copy through a used book seller.


2. Suprised? There is no footnote two. But if there was, it would be to mention that Paul Graham’s incredible book On LISP: Advanced Techniques for Common LISP is freely available online. This is a must read for anyone interested in composing syntactic abstractions in any language.

Labels: lispy, ruby

  ¶ 12:52 PM

  An Approach to Composing Domain-Specific Languages in Ruby Whoa! This looks like a long post with a lot of code snippets. Am I going to have to do a lot of hard thinking, or can I just relax and enjoy a good rambling essay?

This is a bit long, probably (like all my posts) 200% longer than necessary. If you just want to see a neat DSL that implements Haskell and Python’s List Comprehensions written in Ruby, just scroll to the bottom.

If I do bother to read it all, will I learn some neat hacks?

Yes, but you could learn them just as well by reading the source code directly.

So the benefit of reading the whole thing is...?

The List Comprehensions DSL is the what. The source code is the how. But the essay is the why.

Reading the whole thing will take you through some of the pitfalls of writing DSLs and explain why I chose my particular workarounds.

Furthermore, there are a lot of corners in Ruby where you can easily assume that things work one way, but really they don’t. If you actually try the snippets on your computer, you’ll have a much better chance of remembering where the pitfalls are. That’s why I tried to give a working example for every point, rather than just explaining things in words.

Of course, if you have no interest in writing your own Domain Specific Languages in Ruby just yet... this isn’t meant as a popular essay, rather it’s meant as an experience report for fellow practitioners. And honestly, there’s a world market for maybe five tools for writing DSLs in Ruby.

But since you’re here, the essay starts below!

---

An Approach to Composing Domain-Specific Languages in Ruby

Ruby is often touted as a good language for writing Domain-Specific Languages (“DSLs”). There are a few arguments in favour of writing a DSL as part of an application.

The first argument that comes to mind is that if the application’s domain experts have a specific natural language or jargon of their own, writing a DSL makes it easy for programmers and domain experts to collaborate. While it is rare to find substantial applications entirely written by non-programmers at this time in any language, it is quite feasible for non-programmers to write or validate portions of an application representing its “business rules” or domain logic, while programmers maintain its infrastructure.

    include StarbucksDSL
    order = latte venti, half_caf, non_fat, no_foam, no_whip
    print order.prepare

—Building Domain Specific Languages in Ruby

Another argument in favour of a DSL is that even when non-programmers are not involved directly in coding an application, the programmers themselves often have a jargon of their own to describe entities, algorithms and data structures in the application. Having portions of the application written in a language closely resembling the programmer’s own jargon makes it easy for them to read each other’s work and understand its intent.

Successful examples of DSLs embedded within existing languages and frameworks include Ruby on Rails’ ActiveRecord, where statements such as:

    has_and_belongs_to_many :Bar
    validates_presence_of :blitz
    some_bars = Bar.find_by_tavern_license(license_number)

Are self-documenting to anyone familiar with relational models.

The final argument I’ll repeat here is that a DSL is a very effective way to separate the what from the how of an algorithm. Separation of concerns is a desirable property of good programs, and DSLs provide this separation very clearly. In the ActiveRecord examples above, the exact mechanisms of relating tables, validating records, and performing searches is “abstracted away” from the code where the programmer declares how she would like the results used.

Freedom is Slavery

DSLs can be hacked together quickly in Ruby (whether they can be made sufficiently robust for your production needs may require considerably more care). Hacking a DSL together with little effort is a benefit, especially when prototyping: sometimes the best way to design a DSL is to try to use it, so you can discover what you need to express.

Some developers have raised the concern that extensive use of “magic” features leads to code that cannot be understood or maintained.¹ My own feeling is that DSLs lead to code that is easier to understand, not more difficult to understand. This leaves an argument about maintenance. Some techniques for meta-programming, such as extending core classes like Array, have what you might call “non-local effects.”

For example, two different pieces of code might try to extend the same core class, interfering with each other. Each works in isolation and passes all of its unit tests. But when plugged into a larger application that uses them together, they break.

Lispers are among the best grads of the Sweep-It-Under-Someone-Else’s-Carpet School of Simulated Simplicity.

—Larry Wall

Another problem occurs with extending the Kernel class or creating “top level” methods to be used as verbs in a DSL. You end up with name space crowding: you must be very careful that you do not redefine en existing method.

To fix this problem, the code that implements the DSL needs to be contained so that it does not interfere with other code. We can still implement verbs as methods, but we must implement those methods in separate objects, classes, or modules.

Zen in the Art of Program Maintenance

An established technique for implementing methods in objects is to define the methods and then execute a block of code using instance_eval so that it has access to the object’s methods.

I’m trying to get the Zen of building DSLs using Ruby. After reading a dozen or so pieces referenced by my favourite search engine, I have a feeling I’m still not quite getting it.

—Don Box

You know, code expresses an idea better than words express an idea… when the idea is about coding. Please try this example in irb. Don’t just skim the text and nod: there’s a powerful learning mechanism at work when you physically do things as you’re learning, even if it’s just copying, pasting, comparing the result in one window to the text in another, and so on:

def bjarne
    'Barney'
end

dsl = Object.new
def dsl.phred
    'Fred'
end

plus = ' plus '

print dsl.instance_eval {
    phred + plus + bjarne
}
##### "Fred plus Barney"

What does this show? Well, we have created a way to use a method defined in our dsl object, a local variable plus, and a top-level method bjarne. We can imagine scaling this up to defining a rich DSL in our DSL object and being able to mix verbs from the DSL with instance variables and other methods as we please.

Touching back on the subject of containment, we have defined bjarne in Kernel. Now bjarne is essentially global. If we already defined bjarne somewhere else, we just clobbered it. And if we later run a piece of code that defines bjarne, we’ll clobber our own version. phred is different. It’s defined inside of an object, and it doesn’t conflict with any other phred we define elsewhere.

Great! So… Can we cite a few examples of this technique in action (such as Jamis’ post where he calls phred and bjarne examples of Sandboxing and Top-level methods) and end the post here?

No. The code above looks fine. But there is a hidden problem with this sandboxing technique:

MyDsl = Object.new

def MyDsl.phred
    'Fred'
end

class ClientCode

    def bjarne
        'Barney'
    end

    def friends
        plus = ' plus '
        MyDsl.instance_eval { phred + plus + bjarne }
    end

end

ClientCode.new.friends
##### -:15:in `friends': undefined local variable or method `bjarne' for # (NameError) from -:15:in `friends' from -:20

WTF?! This looks just like our top-level example, but we’ve placed our code inside of a ClientCode method. And bjarne is a method in ClientCode: this way we can continue to separate concerns, keeping phred inside our DSL and bjarne inside of the class where we are using the DSL. But it doesn’t work.

Why instance_eval breaks (in tedious detail)

As you know, everything in Ruby is either a variable or a method (how it figures out the difference is a major irritation). When you invoke a method, you are actually sending a message to a receiver.² Sometimes you name the receiver (some_object.a_method), and there is no ambiguity.

But when you just name the method (like bjarne), Ruby tries to find the method for itself. It does so by looking to see whether it is an instance method, in which case it behaves like self.bjarne. If not, it looks to see whether bjarne is top-level, in which case it calls that method in the Kernel. See for yourself:

def foo
  'top level foo'
end

def bar
  'top level bar'
end

class Test
  def bar
    'instance method bar'
  end
  def test
    p foo
    p bar
  end
end

Test.new.test
##### "top level foo" "instance method bar"

See? It looks for instance methods and then for top-level methods if it can’t find anything. (Again, we are hand-waving over the pesky problem with instance variables in the case where we don’t use ()). What’s the problem? Well, I actually mis-described what happens. Here it is again, with more precision:

It looks for methods defined in the object self, and then for top-level methods if it can’t find anything. Of course, self is the current object. Unless it isn’t: That’s what instance_eval does: it evaluates a block but it changes self to point to its receiver instead of the object where the code is executing. Everything else stays the same. One more example to show the mechanism:

def foo
  'top level foo'
end

def bar
  'top level bar'
end

class Test
  def bar
    'instance method bar'
  end
  def blitz
    'current object blitz'
  end
  def test
    p foo
    p bar
    o = Object.new
    def o.blitz
        'redefined self blitz'
    end
    p o.instance_eval { blitz }
    p o.instance_eval { 'bar within o gives: ' + bar }
  end
end

Test.new.test
##### "top level foo" "instance method bar" "redefined self blitz" "bar within o gives: top level bar"

Now we see: when we use instance_eval, we route around our current object and all of our methods are ignored within the block. Ruby really only has two levels of scope: whatever belongs to self and whatever belongs to Kernel.

This state of affairs is unsatisfactory: we would like to introduce a DSL in such a way that we retain access to all of our methods without kludges (like storing the current object in an instance variable).

Nesting Scopes

You can think of the current scope as being nested inside of the top-level scope. instance_eval doesn’t change the scope for things like local variables, it just points self elsewhere.

What we want is a new scope for our DSL nested inside of the current scope. So when we search for a method, we should check the DSL. If we don’t find it there, check the current object’s scope. If we don’t find it there, check the top-level.

Those who do not learn from the History of Lisp are doomed to repeat it.

Oops. John McCarthy called from 1960. He wants Lisp’s dynamic scoping back. Yes, our new feature is almost fifty years old. This is why either a through grounding in CS theory or a hobbyist’s interest in the history of programming are important for programming: much of what we want to do has already been done before, and sometimes in unexpected contexts. Who would have thought that a technique for helping programmers collaborate with Bond Traders has roots in Lisp 1.5?

Here’s an implementation of a nested scope construct that does exactly what we want. You declare a new class that extends DomainSpecificLanguage, and then you can use methods from your DSL, from your current object, and from the top-level (if you so choose). For example:

require 'dsl'

class MyDSL < DomainSpecificLanguage

  def bjarne
    'Barney'
  end

end

class TheGreat

  def phred
    'Fredrick'
  end

  def test
    plus = ' plus '
    MyDSL.eval { p phred + plus + bjarne }
  end

end

TheGreat.new.test
##### "Fredrick plus Barney"

This does exactly what we want with methods.

There's also a single extension to kernel, the method with. with replaces the eval method so you can also say:

    with MyDSL do
      p phred + plus + bjarne
    end

The eval method creates a new instance of your DSL class, so you can track state within an evaluation. For example:

class Censor < DomainSpecificLanguage
  attr_reader :ok_on_tv

  def initialize (given_binding)
    super(given_binding)
    @ok_on_tv = true
  end

  def say something
    something.split.each do |word|
      @ok_on_tv = false if ['feces', 'urine', 'love', 'pudendum', 'fellator', 'oedipus', 'mammaries'].include?(word)
    end
  end

end

class GeorgeCarlin
  def test
    Censor.eval {
      say "People much wiser than I have said, I'd rather have my son watch a film with two people making love than two people trying to kill one other."
      say "And I of course agree. I wish I know who said it first, and I agree with that."
      ok_on_tv
    }
  end
end

p GeorgeCarlin.new.test
##### "false"

let

The first obvious drawback of this approach is that the blocks we pass to eval cannot take parameters. For this reason, rumour has it that a method called instance_exec will be added to Ruby in 1.9. (There are some implementations available that work in Ruby 1.8 if you would like to experiment.)

The second is that you don’t get anything like nested local variables, a ‘la Pascal, Scheme, or any other language with block structure. Block structure is very powerful: You can use a variable within a particular scope and nowhere else. Here’s a trivial example:

with Let do
  let :x => 0, :y => 1 do
    assert_equal(1, x + y)
    let :x => 2 do
      assert_equal(3, x + y) 
    end
    assert_equal(0, x)
  end 
end

We're using the with syntax. In the Let DSL, there’s a new method called let. let creates a new DSL within Let. You can see that re-declaring x does not clobber the value in the outer scope. That is because when let wrote a new DSL, it added x and y as methods.

So really, that block of code says “Write a new DSL where x and y are methods returning zero and one. Execute some code in that new DSL. That code will create another DSL where x is a method returning two.”

Because let defines methods and not local variables, bad things happen when you try to override real local variables. It’s best to use Let for some things and local variables for others, but not mix the two.

Like what, you ask?

List Comprehensions in Ruby

A List Comprehension is syntactic sugar that lets you build collections using set-like notation. For example, S = [ x | x<-[0..], x^2>3 ] is a list comprehension in Haskell.

Here is a List Comprehensions DSL in Ruby. Let’s say we’re building up a multiplication table. We want tuples of the form [x, y, x * y] given x is in the range 1..12 and y is in the range 1..12. Let’s write that:

require 'comprehension'

class MultiplicationTable
  def twelve_by_twelve
    with Comprehension::DSL do
      list { [x, y, x * y] }.given(:x => 1..12, :y => 1..12)
    end
  end
end
p MultiplicationTable.new.twelve_by_twelve
##### [[1, 1, 1], [1, 2, 2], [2, 1, 2], [1, 3, 3], [2, 2, 4] ...

(In everyday use, you don’t need a class and a method for each comprehension: the important bit is list { [x, y, x * y] }.given(:x => 1..12, :y => 1..12). I just wrote it this way so you could see that comprehensions work fine inside of methods. You can also use more than one comprehension inside of a single with Comprehension::DSL do... end block: see the unit tests for examples.)

The expression in the block doesn’t have to be a tuple:

class MultiplicationTable
  def twelve_by_twelve
    with Comprehension::DSL do
      list { "#{x} times #{y} is #{x * y}" }.given(:x => 1..12, :y => 1..12)
    end
  end
end
p MultiplicationTable.new.twelve_by_twelve
##### ["1 times 1 is 1", "1 times 2 is 2", "2 times 1 is 2", "1 times 3 is 3", "2 times 2 is 4", ...

And you can stick a “where” block on the end:

class MultiplicationTable
  def twelve_by_twelve_odds
    with Comprehension::DSL do
      list { "#{x} times #{y} is #{x * y}" }.given(:x => 1..12, :y => 1..12) { (x % 2 == 1) && (y % 2 == 1) }
    end
  end
end
p MultiplicationTable.new.twelve_by_twelve_odds
##### ... 3 times 5 is 15", "5 times 3 is 15", "7 times 1 is 7", "1 times 9 is 9", ...

Would you like to nest them? Your expression is the interpreter’s command:

class MultiplicationTable
  def odds_times_evens
    with Comprehension::DSL do
      list { "#{x} times #{y} is #{x * y}" }.given(
          :x => list { x }.given(:x => 1..12) { x % 2 == 0 } , 
          :y => list { x }.given(:x => 1..12) { x % 2 == 1 } )
    end
  end
end
p MultiplicationTable.new.odds_times_evens
##### ... "2 times 11 is 22", "4 times 9 is 36", "6 times 7 is 42", ...

List Comprehensions and Let

What is the relationship to Let? Well, Let builds the scopes needed for evaluating the where clause and the block defining the elements of the list. Yes, we’ve built a DSL on top of a DSL on top of a DSL. Does this seem like weird trickery? I don’t know why. Do you have any idea how many levels of abstraction are responsible for you reading this essay right now?

This is what we humans do: we build tools on top of tools. Your browser runs on an OS, possibly in a VM, perhaps in a hypervisor, on top of a BIOS, and on and on. This is the normal state of affairs, not an exception.

Closing Remarks

It is possible to build DSLs in Ruby to facilitate cross-functional teamwork and separation of concerns. Care must be taken to avoid polluting the top-level name space, but it is possible to work within sandboxes and still have access to the current object’s context.

Oh yes, and programming is fun as always

Source Code

Update: The copy of dsl.rb has been updated to the latest version. I had committed a rather typical manual synchronization error: I copied the latest file to the wrong directory when I first posted this. Thanks, Justin!

• DomainSpecificLanguage and Let


• Comprehension

How to try it for yourself: Open DomainSpecificLanguage and Let. Save the text only (not the HTML) as dsl.rb. Open Comprehension. Save the text only as anything you like, as long as it is in the same directory as dsl.rb: I use comprehension.rb. Run comprehension.rb.

---

1. I generally call “Bullshit!” on any line of reasoning that sets up a straw man argument just to knock it down. So read on with skepticism!


2. Alan Kay has said that he regrets popularizing the notion of “Object-Oriented” programming, and that he should have called it “Message-Oriented” programming.

Labels: lispy, popular, ruby

  ¶ 12:19 PM

  Coming soon...

require "test/unit"

class TestComprehension < Test::Unit::TestCase
  
  def test_simple_cases
    with Comprehension::DSL do
      assert_equal(
          [1, 2, 3],
          list { x + 1 }.given(:x => 0..2) )
      assert_equal(
          [[0, :a], [0, :b], [1, :a], [1, :b]],
          list { [x, y] }.given(:x => [0, 1], :y => [:a, :b]) )
      assert_equal(
          [2, 4, 6, 8, 10],
          list { x }.given(:x => 1..10) { x % 2 == 0 } )
    end
  end
  
  def plus_seven num
    num + 7
  end
  
  def times_maker num
    lambda { x * num }
  end
  
  def test_closure_cases
    two = 2
    triple = times_maker(3)
    with Comprehension::DSL do
      assert_equal(
          [2, 4, 6],
          list { x * two }.given(:x => 1..3) )
      assert_equal(
          [3, 6, 9],
          list(&triple).given(:x => 1..3) )
      assert_equal(
          [8, 9, 10],
          list { plus_seven(x) }.given(:x => 1..3) )
    end
  end
  
end

March 16, 2007: An Approach to Composing Domain-Specific Languages in Ruby

Labels: ruby

  ¶ 12:45 AM

  Why Why Functional Programming Matters Matters I recently re-read the amazing paper Why Functional Programming Matters (“WhyFP”). Although I thought that I understood WhyFP when I first read it a few years ago, when I had another look last weekend I suddenly understood that I had missed an important message.¹

Now obviously (can you guess from the title?) the paper is about the importance of one particular style of programming, functional programming. And when I first read the paper, I took it at face value: I thought, “Here are some reasons why functional programming languages matter.”

On re-reading it, I see that the paper contains insights that apply to programming in general. I don’t know why this surprises me. The fact is, programming language design revolves around program design. A language’s design reflects the opinions of its creators about the proper design of programs.

In a very real sense, the design of a programming language is a strong expression of the opinions of the designer about good programs. When I first read WhyFP, I thought the author was expressing an opinion about the design of good programming languages. Whereas on the second reading, I realized he was expressing an opinion about the design of good programs.

Can we add though subtraction?

It is a logical impossibility to make a language more powerful by omitting features, no matter how bad they may be.

Is this obvious? So how do we explain that one reason Java is considered “better than C++” is because it omits manual memory management? And one reason many people consider Java “better than Ruby” is because you cannot open base classes like String in Java? So no, it is not obvious. Why not?

The key is the word better. It’s not the same as the phrase more powerful.² The removal or deliberate omission of these features is an expression about the idea that programs which do not use these features are better than programs which do. Any feature (or removal of a feature) which makes the programs written in the language better makes the language better. Thus, it is possible to make a language “better” by removing features that are considered harmful,³ if by doing so it makes programs in the language better programs.

In the opinion of the designers of Java, programs that do not use malloc and free are safer than those that do. And the opinion of the designers of Java is that programs that do not modify base classes like String are safer than those that do. The Java language design emphasizes a certain kind of safety, and to a Java language designer, safer programs are better programs.

“More powerful” is a design goal just like “safer.” But yet, what does it mean? We understand what a safer language is. It’s a language where programs written in the language are safer. But what is a “more powerful” language? That programs written in the language are more powerful? What does that mean? Fewer symbols (the “golf” metric)?

WhyFP asserts that you cannot make a language more powerful through the removal of features. To paraphrase an argument from the paper, if removing harmful features was useful by itself, C and C++ programmers would simply have stopped using malloc and free twenty years ago. Improving on C/C++ was not just a matter of removing malloc and free, it was also a matter of adding automatic garbage collection.

This space, wherein the essay ought to argue that Java compensates for its closed base classes by providing a more powerful substitute feature, left intentionally blank.

At the same time, there is room for arguing that some languages are improved by the removal of harmful features. To understand why they may be improved but not more powerful, we need a more objective definition of what it means for a language to be “more powerful.” Specifically, what quality does a more powerful programming language permit or encourage in programs?

When we understand what makes a program “better” in the mind of a language designer, we can understand the choices behind the language.

Factoring

Factoring a program is the act of dividing it into units that are composed to produce the working software.⁴ Factoring happens as part of the design. (Re-factoring is the act of rearranging an existing program to be factored in a different way). If you want to compare this to factoring in number theory, a well designed program has lots of factors, like the number 3,628,800 (10!). A Big Ball of Mud is like the number 3,628,811, a prime.

Composition is the construction of programs from smaller programs. So factoring is to composition as division is to multiplication.

Factoring programs isn’t really like factoring simple divisors. The most important reason is that programs can be factored in orthogonal ways. When you break a program into subprograms (using methods, subroutines, functions, what-have-you), that’s one axis of factoring. When you break an a modular program up into modules, that’s another, orthogonal axis of factoring.

Programs that are well-factored are more desirable than programs that are poorly factored.

In computer science, separation of concerns (SoC) is the process of breaking a program into distinct features that overlap in functionality as little as possible. A concern is any piece of interest or focus in a program.

SoC is a long standing idea that simply means a large problem is easier to manage if it can be broken down into pieces; particularly so if the solutions to the sub-problems can be combined to form a solution to the large problem.

The term separation of concerns was probably coined by Edsger W. Dijkstra in his paper On the role of scientific thought.

—Excerpts from the Wikipedia entry on Separation of Concerns

Programs that separate their concerns are well-factored. There’s a principle of software development, responsibility-driven design. Each component should have one clear responsibility, and it should have everything it needs to carry out its responsibility.

This is the separation of concerns again. Each component of a program having one clearly defined responsibility means each concern is addressed in one clearly defined place.

Let’s ask a question about Monopoly (and Enterprise software). Where do the rules live? In a noun-oriented design, the rules are smooshed and smeared across the design, because every single object is responsible for knowing everything about everything that it can ‘do’. All the verbs are glued to the nouns as methods.

In a game design where you have important information about a rule smeared all over the object hierarchy, you have very poor separation of concerns. It looks at first like there’s a clear factoring “Baltic Avenue has a method called isUpgradableToHotel,” but when you look more closely you realize that every object representing a property is burdened with knowing almost all of the rules of the game.

The concerns are not clearly separated: there’s no one place to look and understand the behaviour of the game.

Programs that separate their concerns are better programs than those that do not. And languages that facilitate this kind of program design are better than those that hamper it.

Power through features that separate concerns

One thing that makes a programming language “more powerful” in my opinion is the provision of more ways to factor programs. Or if you prefer, more axes of composition. The more different ways you can compose programs out of subprograms, the more powerful a language is.

Do you remember Structured Programming? The gist is, you remove goto and you replace it with well-defined control flow mechanisms: some form of subroutine call and return, some form of selection mechanism like Algol-descendant if, and some form of repetition like Common Lisp’s loop macro.

Dijkstra’s view on structured programming was that it promoted the separation of concerns. The factoring of programs into blocks with well-defined control flow made it easy to understand blocks and rearrange programs in different ways. Programs with indiscriminate jumps did not factor well (if at all): they were difficult to understand and often could not be rearranged at all.

Structured 68k ASM programming is straightforward in theory. You just need a lot of boilerplate, design patterns, and the discipline to stick to your convictions. But of course, lots of 68k ASM programming in practice is only partially structured. Statistically speaking, 68k ASM is not a structured programming language even though structured programming is possible in 68k ASM.

Structured Pascal programming is straightforward both in theory and in practice. Pascal facilitates separation of concerns through structured programming. So we say that Pascal “is more powerful than 68k ASM” to mean that in practice, programs written in Pascal are more structured than programs written in 68k ASM because Pascal provides facilities for separating concerns that are missing in 68k ASM.

For example: working with lists

Consider this snippet of iterative code:

int numberOfOldTimers = 0;
for (Employee emp: employeeList) {
    for (Department dept: departmentsInCompany) {
        if (emp.getDepartmentId() == dept.getId() && emp.getYearsOfService() > dept.getAge()) {
            ++numberOfOldTimers;
        }
    }
}

This is an improvement on older practices.^{5, 6} For one thing, the for loops hide the implementation details of iterating over employeeList and departmentsInCompany. Is this better because you have less to type? Yes. Is it better because you eliminate the fence-post errors associated with loop variables? Of course.

But most interestingly, you have the beginnings of a separation of concerns: how to iterate over a single list is separate from what you do in the iteration.

Try calling a colleague on the telephone and explaining what we want as succinctly as possible. Do you say “We want a loop inside a loop and inside of that an if, and…”? Or do you say “We want to count the number of employees that have been with the company longer than their departments have existed.”

One problem with the for loop is that it can only handle one loop at a time. We have to nest loops to work with two lists at once. This is patently wrong: there’s nothing inherently nested about what we’re trying to do. We can demonstrate this easily: try calling a colleague on the telephone and explaining what we want as succinctly as possible. Do you say “We want a loop inside a loop and inside of that an if, and…”?

No, we say, “We want to count the number of employees that have been with the company longer than their departments have existed.” There’s no discussion of nesting.

In this case, a limitation of our tool has caused our concerns to intermingle again. The concern of “How to find the employees that have been with the company longer than their departments have existed” is intertwined with the concern of “count them.” Let’s try a different notation that separates the details of how to find from the detail of counting what we’ve found:

old_timers = (employees * departments).select do |emp, dept|
  emp.department_id == dept.id && emp.years_of_service > dept.age
end
number_of_old_timers = old_timers.size

Now we have separated the concern of finding from counting. And we have hidden the nesting by using the * operator to create a Cartesian product of the two lists. Now let’s look at what we used to filter the combined list, select. The difference is more than just semantics, or counting characters, or the alleged pleasure of fooling around with closures.

* and select facilitates separating the concerns of how to filter things (like iterate over them applying a test) from the concern of what we want to filter. So languages that make this easy are more powerful than languages that do not. In the sense that they facilitate additional axes of factoring.

The Telephone Test

Let’s look back a few paragraphs. We have an example of the “Telephone Test:” when code very closely resembles how you would explain your solution over the telephone, we often say it is “very high level.” The usual case is that such code expresses a lot more what and a lot less how. The concern of what has been very clearly separated from the concern of how: you can’t even see the how if you don’t go looking for it.

In general, we think this is a good thing. But it isn’t free: somewhere else there is a mass of code that supports your brevity. When that extra mass of code is built into the programming language, or is baked into the standard libraries, it is nearly free and obviously a Very Good Thing. A language that doesn’t just separate the concern of how but does the work for you is very close to “something for nothing” in programming.

But sometimes you have to write the how as well as the what. It isn’t always handed to you. In that case, it is still valuable, because the resulting program still separates concerns. It still factors into separate components. The components can be changed.

I recently separated the concern of describing “how to generate sample curves for some data mining” from the concern of “managing memory when generating the curves.” I did so by writing my own lazy evaluation code (Both the story and the code are on line). Here’s the key “what” code that generates an infinite list of parameters for sample beziér curves:

def magnitudes
  LazyList.binary_search(0.0, 1.0)
end

def control_points
  LazyList.cartesian_product(magnitudes, magnitudes) do |x, y|
    Dictionary.new( :x => x, :y => y )
  end
end

def order_one_flows args = {}
  height, width = (args[:height] || 100.0), (args[:width] || 100.0)
  LazyList.cartesian_product(
      magnitudes, control_points, control_points, magnitudes
  ) do |initial_y, p1, p2, final_y|
    FlowParams.new(
      height, width, initial_y * height,
      CubicBezierParams.new(
        :x => width,          :y => final_y * height,
        :x1 => p1.x * width,  :y1 => p1.y * height,
        :x2 => p2.x * width,  :y2 => p2.y * height
      )
    )
  end
end

That’s it. Just as I might tell you on the phone: “Magnitudes” is a list of numbers between zero and one created by repeatedly dividing the intervals in half, like a binary search. “Control Points” is a list of the Cartesian product of magnitudes with itself, with one magnitude assigned to x and the other to y. And so forth.

I will not say that the sum of this code and the code that actually implements infinite lists is shorter than imperative code that would intermingle loops and control structures, entangling what with how. I will say that it separates the concerns of what and how, and it separates them in a different way than select separated the concerns of what and how.

So why does “Why Functional Programming Matters” matter again?

The great insight is that better programs separate concerns. They are factored more purely, and the factors are naturally along the lines of responsibility (rather than in Jenga piles of abstract virtual base mixin module class proto_ extends private implements). Languages that facilitate better separation of concerns are more powerful in practice than those that don’t.

WhyFP illustrates this point beautifully with the same examples I just gave: first-class functions and lazy evaluation, both prominent features of modern functional languages like Haskell.

WhyFP’s value is that it expresses an opinion about what makes programs better. It backs this opinion up with reasons why modern functional programming languages are more powerful than imperative programming languages. But even if you don’t plan to try functional programming tomorrow, the lessons about better programs are valuable for your work in any language today.

That’s why Why Functional Programming Matters matters.

---

1. And now I’m worried: what am I still missing?


2. Please let’s not have a discussion about Turing Equivalence. Computer Science “Theory” tells us “there’s no such thing as more powerful.” Perhaps we share the belief that In theory, there’s no difference between theory and practice. But in practice, there is.


3. I am not making the claim that I consider memory management or unsealed base classes harmful, but I argue that there exists at least one person who does.


4. The word “factor” has been a little out of vogue in recent times. But thanks to an excellent post on reddit, it could make a comeback.


5. So much so that we won’t even bother to show what loops looked like in the days of for (int i = 0; i < employeeList.size(); ++i).


6. Another organization might merge employees and departments, or have each department “own” a collection of employees. This makes our example easier, but now the data doesn’t factor well. Everything we’ve learned from databases in the last forty years tells us that we often need to find new ways to compose our data. The relational model factors well. The network model factors poorly.

Labels: java, lispy, popular, ruby

  ¶ 10:21 PM

  Haskell, Ruby and Infinity Languages like Haskell support lazy evaluation. In principle, you only compute what you actually need, everything else just goes away. If you usually need everything you compute, this may seem like a frill: elegant, even interesting, but having little practical importance. I find it is very much like Tail Call Optimization: if you don’t have it, you code around it. Often it makes no difference, but from time to time there is a case where your code will be clearer and more maintainable if you express yourself succinctly and let the compiler do the work of making it efficient.

This post is a switch from mumbling about Y Combinators and using trivial cases to explain interesting ideas: I’m going to show some actual code I’m writing. I apologise in advance if this adds so much background that it obscures the message about lazy evaluation: extremely simplistic examples sometimes work against the argument because it is too easy to think of other ways to accomplish the needed results.

I don’t apologise at all for the unpolished nature of the code. This isn’t a textbook. And besides:

Anybody can say you can’t write. Let no one say you don’t.

—Ken Rand, courtesy of Chalain

---

I’ve been hacking some naïve code to cluster data sets.

In computer programming, a hacker is a software designer and programmer who builds elegant, beautiful programs and systems… For some, “hacker” has a negative connotation and refers to a person who “hacks” or uses kludges to accomplish programming tasks that are ugly, inelegant, and inefficient.

—Wikipedia

The clustering algorithm requires a very large, fixed set of curves.¹ I wrote the initial curve generation by building a gigantic list of parameter tuples, and then processing the list into records. Once the “search space” grew beyond a trivial size, the program began to eat enormous amounts of memory. The problem was that I was trying to write the generation code as clearly as possible, and that created a massive thicket of objects that all resided in memory simultaneously.

I rejected the idea of a rewrite into looping, imperative form, I wanted to separate the “list comprehension” code from the “make it run in less than a gigabyte” code. Instead, I chose to use lazy evaluation: the principle is that although the code defines a huge data structure that takes up gigabytes, we only actually evaluate things as we need them, and we discard them when we are done, so the total memory footprint for the lazy form is about the same as the memory footprint for an imperative form.

The easiest way to perform the refactoring—besides a rewrite in Haskell—was to switch all of the arrays I used for a lazy list data structure. A lazy list is a linked list composed of head and tail tuples (known as cons cells). Where a normal linked list holds an element and the rest of the list, a lazy list holds an element and a function for computing the rest of the list (SICP calls them “streams.”)

If a modicum of care is taken not to pin objects down, you can build fantastically large lazy lists and process them at will. In fact, lazy lists can be infinitely large if you provide the appropriate function for generating the list

For that reason, you should never append one lazy list onto another lazy list. Consider odd = LazyList.unfoldr(1) { |n| n + 2 } and even = LazyList.unfoldr(0) { |n| n + 2 }. If you append odd onto even, the resulting list in theory has both even and odd numbers. But in practice you can never reach the odd numbers because there is an infinite quantity of even numbers at the front of the list.

Instead, merge them together to produce a lazy union of the two lists. Merge interleaves alternating elements from each list, so the resulting lazy list contains all the elements of each list, and if you take a finite sample, such as the first 1,000 elements, you get 500 of each. even.merge(odd) => (0 1 2 3 ...). (Other interesting operations that work with infinite lists include cons, pairwise and product.)

Any sufficiently complicated Lisp or Ruby program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Haskell.

My current version of a LazyList class in Ruby is here. As soon as I switched from the “eager” code using arrays to the “lazy” code using lazy lists, memory use went down and performance went up. Not as much as a switch to imperative (and not even close to writing a better clustering algorithm), but enough that I can move forward.

Here is an example of a function using arrays to enumerate choices (distribute(2, 1..4) -> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]):

def distribute choices, range
  spots = (range.end - range.begin) + 1
  return [] if choices <= 0 || choices > spots
  remaining_choices = choices - 1
  if remaining_choices == 0
    return range.to_a.map { |spot| [spot] }
  else
    (range.begin..(range.end - remaining_choices)).to_a.inject([]) { |acc, first_spot| acc + (distribute(remaining_choices, (first_spot + 1)..range.end).map { |remaining_distribution| remaining_distribution.unshift(first_spot) }) }
  end 
end

And rewritten with lazy lists:

def distribute choices, range
  spots = (range.end - range.begin) + 1
  return LazyList.new() if choices <= 0 || choices > spots
  remaining_choices = choices - 1
  if remaining_choices == 0
    LazyList.from_range(range).map { |spot| LazyList.from_element(spot) }
  else
    LazyList.from_range(range.begin..(range.end - remaining_choices)).mapr(:merge) do |first_spot|
      distribute(remaining_choices, (first_spot + 1)..range.end).map do |remaining_distribution| 
        LazyList.cons(first_spot, remaining_distribution) 
      end
    end
  end 
end

It’s almost identical. LazyLists replace arrays, mapr replaces accumulating a list with inject, and cons replaces unshift, but otherwise it’s the same code. Mission accomplished: we’ve changed the behaviour without having to change the way we express our algorithms. Had we wanted to, we could have supported enough array syntax that Lazy Lists look exactly like arrays, but that isn’t necessary.

And when running the entire generator, the memory footprint is dramatically lower. For example, this small routine quoted above no longer generates an array of arrays: it generates a structure that can generate the lists when needed. Switching the data structure changes the evaluation behaviour of the generator code: it gets us 80% of having an imperative structure without having to tie the code to the implementation.

This is exactly what separation of concerns is all about: green code here, yellow code there.

Lazy evaluation is the red pill

It’s great to make a change to the code’s behaviour without changing the way we think about the solution to our problem. But you know what? It isn’t interesting. In fact, if lazy optimization was something we needed on a regular basis, we ought to switch to a language that does it for us. Implementation details ought to be left to libraries, compilers, and virtual machines. That’s what they’re for.

A language that doesn’t affect the way you think about programming, is not worth knowing.

—Alan Perlis

Now that we hold in our hands a tool for making infinitely long lists, the question to ask is, “how does that affect the way we think about generating sample curves?”

The first thing that comes to mind is to ask why the set of sample curves we generate is finite. It isn’t really finite, there are an infinite number of curves. (And not just any infinity, it’s Aleph One, the children’s book One Two Three… Infinity explained that forty years ago.)

What we really want is a finite sample of that infinite set of curves. Now let’s zoom in and think about a single parameter, the y value for one of the control points on a curve. Let’s say it’s a rational number between 0.0 and 1.0 inclusive. It’s relatively easy to generate a list of rationals in that range. Say we generate 0.0000...00001 (with jillions of zeroes elided: we want the smallest number our computer can represent), followed by 0.0000...00002 (the second smallest), and so on.

If we leave the computer running for a few months or years, we should get all of the numbers between 0.0 and 1.0 that our computer can represent. That shouldn’t be hard. But even taking into account the finite limitations on a computer’s representation, that list is infinitely long.

Useful samples

We need to take a finite sample of all of the infinite possibilities in that list.

When working with an infinite list, what we want is that the front part of the list, the part we can access before the heat death of the Universe, contains a useful sample. If we were sampling a list like (0.0000...00001 0.0000...00002 0.0000...00003 0.0000...00004 ... ) for control points, the first values are not useful at all. We’d just get a line along the x access.

There are various strategies for generating a more useful list. We could create an infinite list of random values. I’ll outline another method below. But the take-away idea is this: we need lists where the most useful values are first. Working with infinite lists encourage us to think of infinitely sized sets of samples, ordered by usefulness.

Let’s say that when we generate y, we devise a list like (0.0 1.0 0.5 0.75 0.25 ... ). We’re successively bisecting the intervals (which is why the library method is called binary_search). We can stop at any time and we have decent distribution. (And we can pipe dream that in the future, we can train our generator to favour points more likely to be useful to us.) That is much more useful!

Here’s some Lazy List code that does just that: given two seeds and an optional bisection block, it generates an infinite list of values:

def binary_search seed1, seed2, &block
  bisection_block = block || lambda { |x, y| (x-y)/2 + y }
  LazyList.cons(
    seed1,
    LazyList.new(
      seed2,
      delay {
        bisect(seed1, seed2, &bisection_block)
      }
    )
  )
end

# infinitely bisects a space, exclusive of the seed values

def bisect seed1, seed2, &block
  return EMPTY if seed1 == seed2
  half = block.call(seed1, seed2)
  LazyList.new(
    half,
    delay {
      merge(
        bisect(seed1, half, &block),
        bisect(half, seed2, &block)
      )
    }
  )
end

And indeed, LazyList.binary_search(0.0, 1.0) -> (0.0 1.0 0.5 0.75 0.25 ... ).

The Grand Hotel

What happens when we try to combine two infinite lists? For example, we want a list of (x, y) tuples, generated as the Cartesian Product of our binary search list with itself. If we use a typical breadth-first or depth-first algorithm, we’re sunk. We get ( (0.0 0.0) (1.0 0.0) (0.5 0.0) (0.75 0.0) (0.25 0.0)... ). That has a nice distribution along one axis but still useless. What we need is a way of combining two infinite lists such that they give us a nice useful sample when we take a finite number of elements off the front.

Here’s a table describing how the ‘breadth-first’ algorithm for generating the product of two lists works. Consider two lists of three elements each. In the table below, columns represent one list and rows the other. The numbers represent the order that the product of the lists is generated:

Breadth-first mapping from elements to integers
1	2	3
4	5	6
7	8	9

This works fine for finite lists, but as we saw above it is useless for infinite lists. But looking at it in table form is useful. The product of two lists is tabular, the problem with a traditional algorithm is the order that we select elements from the table, not that the elements are tabular. Just as we solved the problem of how to sample y magnitudes by changing the order in which we selected rationals between 0.0 and 1.0, what we need to do with Cartesian Products, what we need to do is select the products in an order that provides useful results.

As it happens, there’s an order that generates useful finite samples when dealing the product of two infinite lists: Instead of generating rows and appending them to each other, it generates diagonals and merges them with each other. The first diagonal is 1, 5, 9. The second is 4, 8. The third is 2, 6. And so on. The advantage of this algorithm is that if given two infinite lists, it starts in the upper left-hand corner and supplies values, working its way right and down.²

Here’re the first four values of the product of two binary searches with each other: [{:x=>0.0, :y=>0.0}, {:x=>0.0, :y=>1.0}, {:x=>1.0, :y=>0.0}, {:x=>0.0, :y=>0.5}]. And the next four: [{:x=>1.0, :y=>1.0}, {:x=>1.0, :y=>0.5}, {:x=>0.5, :y=>0.0}, {:x=>0.0, :y=>0.25}]. And the next eight: [{:x=>0.5, :y=>0.5}, {:x=>0.5, :y=>0.25}, {:x=>0.5, :y=>1.0}, {:x=>1.0, :y=>0.25}, {:x=>0.25, :y=>0.25}, {:x=>0.25, :y=>0.75}, {:x=>0.25, :y=>0.0}, {:x=>0.0, :y=>0.75}].

We can take as many samples as we want, and more sample give us more “resolution.” We now have the tools we need to get rid of all of the limits and finite combinations and focus on describing what we’re trying to generate without intermingling a lot of generating code.

And I’m thinking about eternity
Some kind of ecstasy got a hold on me

—Bruce Cockburn, Wondering Where The Lions Are

Now that we can generate an infinite list of useful magnitudes, plus we can combine infinite lists in a useful way, we can define an infinite list of sample curves. Here’s the exact definition of an infinite list of partial beziérs (there are only three control points because the origin of the beziér is always the terminus of the previous beziér in the curve we are generating):

def sample_cubic_beziers
  magnitudes = LazyList.binary_search(0.0, 1.0)
  control_points = LazyList.cartesian_product(magnitudes, magnitudes) do |x, y|
    { :x => x, :y => y }
  end
  LazyList.cartesian_product(control_points, control_points, control_points) do |p1, p2, p3|
    {
      :p1 => p1,
      :p2 => p2,
      :p3 => p3
    }
  end
end

That’s really simple, and really easy to understand.³ The domain-specific code that defines a cubic Beziér is concise and readable. And the infrastructure code that handles combinatorics is shunted away out of sight where it doesn’t clutter up our thinking.

So what have we seen?

1. Lazy evaluation solved a performance problem without needing an extensive rewrite of our generation code;


2. Taking the red pill, infinite lists allowed us to radically simplify the original code.

Are there some opportunities to steal an idea like lazy evaluation from other languages and use them to simplify your code?

---

1. The data is a set of (x,y) tuples where x is time and y is a magnitude. The effort remaining in a sprint backlog is an example of this kind of data set. I need a function that computes the distance between any two data sets. I already have a function that computes the distance between a curve through the xy space and a data set, so if I build a lot of curves and then take the distance between each curve and each data set, I can find the distance between pairs of data sets by searching for the curve with the lowest total distance.
   
   This operation is On², but that’s why we invented distributed processing. Also, this operation is done infrequently relative to operations making use of the clusters, something like Google’s indexing being far less frequent than searching Google. And of course, when my MacBook overheats and burns its way through my desk, I can come back and replace the brute force operation with something more intelligent.
   
   Well, all this requires generating the sample curves. I have code that makes curves out of Beziérs, provided I supply coördinates for the control points. the curves are actually ActiveRecord models. So all I needed was some simple code that generates all of the possible combinations and then write them to the database. It’s the kind of thing candidates write in job interviews where employers actually care about their stone cutting skills.


2. This problem is congruent to the proof that the set of all points on a plane is the same size as the set of all points in a line.


3. And it could be simpler yet: a “list comprehensions” DSL for lazy lists is on the wish list would make things far more readable.

Labels: lispy, ruby

  ¶ 1:49 PM

  Programming Language Stories C

A fellow needs a dog house, so he hires a contractor. This guy is a C programmer who’s between jobs at the moment, and he says forget those wimpy “agile” wooden dog houses, he can build the dog house out of bricks, it will last forever and is stronger than any wood structure.

The client is doubtful, but that sounds very impressive, and the contractor says this is how all the real-world dog houses are made, so he agrees. Well, it takes forever: it seems every time the contractor thinks it’s finished, they discover there’s a chink between the bricks and there’s a leak. With wood you just trim to fit, but with bricks you have to plan everything in advance so that the bricks line up just right.

But Spring turns to Summer turns to Autumn, and the job is done. The client pays up, and the contractor’s about to leave when he stops and thinks for a moment before speaking.

“Hey,” the contractor says, “You paid for a pallet of bricks, and I used all but one. It’s a shame if it goes to waste. Why don’t I see if I can use it somewhere?” The client asks like what, and before you know it the contractor has scored a contract to build a brick path for the dog from the back door to the dog house. He orders some more bricks, gets to work right away, and this time things go a little better.

The contractor is now doing C++ on the side. And he uses some new bricklaying techniques he learned from Effective C++: there are these funny angle braces everywhere thanks to his path building templates. Soon that job is done and the contractor collects his fee. He’s about to leave, but he reaches into his tool chest and pulls out a brick.

“Hey,” the contractor says, “You paid for another pallet of bricks, and I used all but one on the path. It’s a shame if it goes to waste. Why don’t I see if I can use it somewhere?” The client is happy with the path, asks like what, and before you know it the contractor has scored another contract, this time to build a brick wall enclosing the yard. He orders some more bricks, and gets to work right away.

Meanwhile, the contractor has become a Visual C++ programmer and reads MSDN magazine religiously. He applies his new skills to building the wall: he has all these fancy tools that can put up sections of scaffolding when you push a button. of course, there are huge holes you have to fill in yourself, and the scaffolding has all these crazy joins and angles, it’s hard to change anything or understand how the entire wall fits together, but it feels like you’re getting a lot done because the system seems to move a lot of bricks for you.

Well, the wall takes forever, and it doesn’t look that good when it’s finally done. But the client pays up and the contractor is ready to leave. But he stops for a moment and pulls a brick out of his tool chest.

“Hey,” the contractor says, “You paid for two more pallets of bricks for the wall, and I used all but one. It’s a shame if it goes to waste. Why don’t I see if I can use it somewhere?”

The client has had enough of this, and he decides he’s going to show the contractor how he feels. “Give me that brick,” he orders. The surprised contractor hands it over. “I don’t give a rat’s ass about this brick” the client huffs, and he throws the brick clear out of his yard.

“I need to get work done, not talk to contractors all day about bricks. And besides, I’ve talked to the big landscape contracting companies, and they all say nobody is using bricks, everyone has switched to sharp tools and netting. Now get out.”

Ruby on Rails

Just inside the gates of heaven, St. Peter sits at a desk checking people in.

Peter: “Welcome to heaven. Programming language?”

The man at the front of the line says, “Smalltalk.”

Glancing at his clipboard, Peter says, “Room 33. Be very quiet as you pass Room Six.”

The process repeats itself with the next person in line:

Peter: “Welcome to heaven. Programming language?”

Person #2: “Common Lisp.”

Peter: “Room 17. Be very quiet as you pass Room Six.”

The next person moves to the front of the line with a look of curiosity on her face.

Peter: “Welcome to heaven. Programming language?”

Person #3: “Python.”

Peter: “Room 54. Be very quiet as you pass Room Six.”

Person #3: “Why do you keep telling us to be quiet as we pass Room Six?”

Peter: “Because the Ruby on Rails People are in Room Six, and they think they’re the only ones here.”

—Snarfed from Eric Sink’s Baptists and Boundaries

Java

A mother was preparing the pot-roast for Sunday’s big family dinner. Before searing it and placing it in the pan, she carefully sliced the ends off. Her three year-old daughter asked “Mommy, why do you cut the ends off the roast?”

She answered, “My mom taught me to do it that way, and it’s delicious, so it must be a good idea. Maybe the juices from the meat mix with the vegetables?”

Everyone sits down for dinner, and when Father is serving the roast, the daughter remembers her question. She turns to Grandma and asks, “Grandma, why did you teach Mommy to cut the ends off the roast?”

Grandma thinks for a moment and says, “What a delightful question! I always used to cut the ends off the roast, it’s how my mother taught me. I don’t know why she did that, there must have been a good reason.” Grandma sits for a moment, remembering her mother. “Well,” she continues, ” there must have been a good reason. Now eat your dinner before it gets cold!”

The holidays roll around, and they’re having dinner at Grandma and Grandpa’s house. “Hey!” Grandma says to the little girl, “You know what, I was going through your great-grandmother’s things, and I found the old roast pan. We sure made some good pot roast in it. Let’s make pot roast with it tonight in her honour!”

They get out the pan and wash it up. It’s old, and well-seasoned. Grandma looks it over. “It’s smaller than I remember. I was a little girl, and everything looks bigger when you’re small!”

They put the roast on the counter before searing it. Just then, Grandpa walks by. “Do you want me to cut the ends off the roast?” he asks. “It’s the only way you’ll get it to fit in that small pan.”

Grandma and the little girl look at each other. And they smile.

Scheme

A fellow is on vacation, and he decides to ride one of those “scenic” double-decker buses that drive around from attraction to attraction. The upper level is open-air, and he’s the only one up there. He looks around, and decides that instead of re-reading his copy of The Little Schemer, he’s going to really enjoy himself: he lights a cigar.

No sooner has he lit the cigar when a woman comes huffing and puffing upstairs, carrying one of those sub-miniature dogs people use as fashion accessories. She takes one look at our man and demands he put the cigar out: it is offensive to the dog.

“Madam,” our man asserts, “this cigar is not offensive. Let me tell you its secrets.”

“Eschewing inferior mass-market tobacco, I order whole, functional leaves—at great expense and with difficulty—from a small collective in Cuba that still grow cigar tobacco the old-fashioned, original way.”

“Unsullied by automatic rolling machines or other push button devices, I roll each cigar, myself, by hand. Using secret tobacco-macro techniques that are impenetrable to the typical ignorant cigarette smoker, I am able to pack as much smoking pleasure into a single cigar as would take a carton of cigarettes—nay, it is impossible to enjoy a smoke from regular cigarettes as much as I enjoy the elite, exclusive flavour of my cigars.”

The woman is not impressed. “If your cigars are so good, how come nobody smokes them?” she asks. “If your cigars are so good, how come so many clubs and restaurants permit cigarettes but forbid cigars?”

Our fellow is so irate he begins to splutter. “If you or your dog are unable to understand that the purity, the perfection achieved long ago on a remote island far from consumerism and mass productio—” But he is unable to finish, for the woman imperiously sweeps the cigar from his mouth and flings it over the side of the bus.

“That’s what I think of your pompous cigar.” She tells him.

He glares at her for a moment, then years of oppression, of being forced to live with the hated cigarettes against his will, bring him to a boil and he commits an unthinkable act. With a wrench, he seizes the dog and flings it after his cigar. There is a moment of uncomprehending shock, and then the woman begins to howl.

Well, the bus driver hears all this and slams on the brakes. For a moment everything is higgledy-piggledy, and just as the woman’s wails return to their full volume, everyone is shocked to see the dog come trotting up, unharmed.

And what do you know: the dog has—nestled gently in its mouth—the most unexpected thing:

Gur Oevpx.

---

If you enjoyed these stories, you may also like Why You Need a Degree to Work For BigCo and more recently, A Venture Capitalist passes away peacefully, and....

Labels: java, lispy, ruby

  ¶ 3:10 PM

  Why Ruby is not an acceptable implementation of Lisp The other day, while actually writing software (as opposed to talking about writing software), I wrote the following:

distance = lambda do |given_scale|
  (magnitudes.map { |pair| 
    (pair.evidence - (pair.flow * given_scale)) ** 2 
  }).inject { |acc, distance| acc + distance }
end

If you are curious, distance is a function that computes the distance between a curve (called a ‘flow’) and some evidence, given a float that scales the flow. It’s used for finding a curve that ‘looks like’ a set of data points.

Can you spot the bug? I’ll expunge all of the excess and give you some code you can try yourself:

require 'test/unit'

class TestRubyNames < Test::Unit::TestCase

  def test_lambda_clobbering
    foo = lambda { (1..3).map { |foo| foo ** 2 } }
    assert_nothing_raised(NoMethodError) { foo.call() }
    assert_raise(NoMethodError) { foo.call() } # WTF?
  end

  def test_local_clobbering
    foo = [1, 4, 9]
    bar = lambda { (1..3).map { |foo| foo ** 2 } }
    bar.call
    assert_equal(3, foo) # WTF?
  end

end

Is this what you expect? Ruby looks like a nice, block-structured language with lexical scope. But its standard implementation has serious issues. I believe these are well-known and understood issues, but issues nonetheless.

One more example. I swore I wouldn’t write anything else about fixed-point combinators for a very long time, but try this exercise at home. Here’s my curry combinator:

require 'test/unit'

class ExempliGratia < Test::Unit::TestCase

  CURRY = lambda { |f, a| lambda { |*b| f.call(a, *b) } }

  def test_clean_up_loose_ends
    maker = lambda { |f|
               lambda { |func_with_me| CURRY.call(func_with_me, func_with_me) }.call(
                    CURRY.call(lambda { |inner_func, me, *args|
                                inner_func.call(CURRY.call(me, me)).call(*args) }, f)) }

    factorial = maker.call(
      lambda { |f| lambda { |n| n.zero? && 1 or n * f.call(n-1) } }
    )
    assert_equal(120, factorial.call(5))
  end

end

Looks good. Now let’s prove that CURRY is referentially transparent by replacing every CURRY variable with the lambda:

maker = lambda { |f|
           lambda { |func_with_me| (lambda { |f, a| lambda { |*b| f.call(a, *b) } }).call(func_with_me, func_with_me) }.call(
                (lambda { |f, a| lambda { |*b| f.call(a, *b) } }).call(lambda { |inner_func, me, *args|
                            inner_func.call((lambda { |f, a| lambda { |*b| f.call(a, *b) } }).call(me, me)).call(*args) }, f)) }

factorial = maker.call(
  lambda { |f| lambda { |n| n.zero? && 1 or n * f.call(n-1) } }
)

begin
  factorial.call(5)
  puts 'fine'
rescue SystemStackError
  puts 'wtf?'
end

Hunh? Ruby looks like a nice language supporting anonymous functions, but sometimes they work and sometimes they don’t. I strongly suspect that this issue has something to do with the fact that with the ‘naked’ lambdas we’re creating new functions with every call, whereas the version using a CURRY variable re-uses the same function, so the system stack overflows in one case and not the other.

Update: Mike Harris proved that this second problem is the same as the first problem: once again, variables are clobbering each other all over the place. In Ruby 1.8, blocks do not create new scope, at all.

Here's Mike's submission, indented to fit:

def test_full_anonymity
  assert_equal(120, (lambda { |f0|
                       lambda { |func_with_me| 
                         (lambda { |f1, a1| 
                           lambda { |*b1| f1.call(a1, *b1) } 
                         }).call(func_with_me, func_with_me) 
                       }.call(
                            (lambda { |f2, a2| 
                              lambda { |*b2| f2.call(a2, *b2) } 
                            }).call(
                              lambda { |inner_func, me, *args|
                                inner_func.call(
                                  (lambda { |f3, a3| 
                                    lambda { |*b3| f3.call(a3, *b3) } 
                                  }).call(me, me)).call(*args) 
                              }, f0)) 
                    }).call(
    lambda { |f| lambda { |n| n.zero? && 1 or n * f.call(n-1) } }
  ).call(5))
end

Stop your sobbing

I’m not saying Ruby is an unacceptable Ruby.

I’m especially not saying “See, that’s why we should stick with language X.” If language X doesn’t even try to support this kind of programming, it’s a lame argument to say that it’s a better choice. That’s like saying that your 1972 Pinto is safer than my 2004 MX-3 because the Pinto doesn’t have air bags, and air bags can injure small children if they are sitting in the passenger seat.

If you try to bend Ruby to do Scheme-ish things, you will run into some corner cases, some places where it does the unexpected. Can you figure them out and avoid them (some people will say avoiding corner cases makes for a Leaky Abstraction)?

I think if you’re writing Ruby code in Ruby, you can easily avoid these problems. That’s why Ruby is an acceptable Ruby.

Why isn’t Ruby an acceptable implementation of Lisp?

But why isn’t Ruby an acceptable implementation of Lisp? (Besides the lack of support for hygienic macros, of course!)

The problem is that Lisp or Lisp-style programming is all about metaprogramming. Code that writes code. Code that evals code. It’s easy to look at something like the curry combinator and say “no programmer would ever write that convoluted a function in production.” But macros and code generators routinely combine snippets of code to produce monstrosities that a human wouldn’t even considering writing.

When writing a piece of code that writes code, you are heavily dependent on the underlying implementation being regular and corner-case free. The whole point of writing code-writing code is that you intend for it to generate variations and combinations on your templates or scaffolds. And it’s only a matter of time before you are combining template A with generator B and meta-programming method C.

When the underlying language is robust, none of this matters. The result works. If you look at it under the hood, you’re horrified at the result. But frankly, that isn’t an argument against meta-programming, it’s an argument for it: let the machine do the dirty jobs we don’t want to do, and let us deal with a nice abstraction like A plus B plus C that just works, never mind what the code looks like.

(Don’t even think about arguing that we should do away with code that writes code. That debate was won by the code generation folks back when COBOL and FORTRAN and ALGOL were young. From time to time you’re welcome to pull out your assembly if you like, but we use High Level Languages because we want the machine to write the messy crap for us.)

My fear is that code that writes code might one day write code that clobbers a variable. Or code that writes code might write some nested lambdas that overflow the stack.

And that’s why Ruby is not an acceptable implementation of Lisp.

---

Well, ok, I confess: the title is a bit of muckraking. Ruby is a pretty good implementation of Lisp, and anyone who has two brains to rub together can point out that the issue is not whether there’s some corner case “gotcha,” but whether using Ruby is, on the whole, more beneficial than not using Ruby.

For what it’s worth, I consider corner cases like this a strong endorsement of trying new languages like Ruby: it’s like finding out that your sailplane has a tendency to go into an inverted flat spin when you loop at an unacceptably slow speed. It’s terrifying when it first happens, but you get through it and then you realize that the only reason you got into trouble was that you were pushing yourself hard.

Labels: lispy, ruby

  ¶ 3:03 PM

  Guest Blogger: Tom Moertel derives the Y combinator in Ruby In a comment on But Y would I want to do a thing like this?, Tom Moertel derived an elegant version of the actual Y combinator in Ruby. I reproduce his words here with permission.

Tom uses the alternate syntax for call, [...]. I avoided this to keep clear of a tiresome debate about operator overloading. (On one side: those who hate it. On the other side: those that hate Ruby disallowing overloading (...)).

Ok Tom, take it away!

---

Here’s my original Ruby definition:

def y(&f)
    lambda { |*args| f[y(&f)][*args] }
end

To get rid of the recursive call y(&f), let’s replace it with a variable yf, whose value we’ll say is magically equivalent to the result of the recursive call. To effect the binding of yf, we’ll need to wrap the method body in a new lambda expression and pass in the magic value:

def y(&f)
    lambda { |yf|
        lambda { |*args| f[yf[yf]][*args] }
    }[ <<< placeholder for yf: we'll fill this hole next >>> ]
end

So, what value should we pass in for yf? Because the variable represents the value that would have been computed by calling y(&f), which is just the body of the y method, we can fill the hole with a duplicate of the body:

def y(&f)
    lambda { |yf|
        lambda { |*args| f[yf[yf]][*args] }
    }[ lambda { |yf| lambda { |*args| f[yf[yf]][*args] } } ]
end

And we have our Y combinator:

fac = y { |rec| lambda { |n| n < 2 ? 1 : n * rec[n-1] } }
fac[5] # ==> 120

While the combinator works, its implementation repeats itself: there are two copies of the lambda expression

lambda { |yf| lambda { |*args| f[yf[yf]][*args] } }

in the method body. To factor them out, let’s let the variable x represent this expression. Then the method body simplifies to x[x], which is very satisfying. To set x to the correct value, however, we need to add a wrapper lambda that binds x to the original expression. Putting it all together, we arrive at the final version:

def y(&f)
    lambda { |x| x[x] } [ 
        lambda { |yf| lambda { |*args| f[yf[yf]][*args] } } ]
end

And it, too, works:

acc_fac = y { |rec| lambda { |n,acc| n < 2 ? acc : rec[n-1, n*acc] } }
tail_fac = lambda { |n| acc_fac[n, 1] }
tail_fac[5] # ==> 120

Cheers! —Tom

Labels: lispy, ruby

  ¶ 12:58 PM

  But Y would I want to do a thing like this?

Choose life. Choose a job. Choose a starter home. Choose dental insurance, leisure wear and matching luggage. Choose your future. But Y would I want to do a thing like that?

Writing about first-class functions and their compatibility with object-oriented programming naturally leads to the Y combinator. And that is the point where eyes glaze over and soft, snoring sounds rise from RSS readers everywhere.

But please bear with me, this essay is not really about the Y combinator, it’s about learning new things and expanding our capacity to think.

Sharpening the saw

Years ago I picked up Steven Covey’s book The 7 Habits of Highly Effective People. If the book is a test out of seven, I really wasn’t doing very well.

If you’ve read the book, you probably remember that he talked about “Sharpening the Saw,” investing in your own abilities. That’s incredibly important, but I don’t need to tell you that. If you exercise with programming katas, or learn a new programming language once a year, or pick up a book like The Reasoned Schemer and actually go through the exercises, then you are already in the top 1% of software developers for personal skills improvement. (Sorry, certifications don’t count. They are the classic case of doing the wrong thing for the wrong reason!)

New ideas—by which I mean, new to you—are an important way to sharpen your saw. If for no other reason than this: the brain needs regular exercise to perform at or near its potential. Learning new things keeps you sharp, even if you don’t directly use the things you learned.

Others have suggested that learning Lisp is beneficial to your programming skills in its own right. That’s one good way to sharpen your saw. But I add to that an important caveat: to obtain the deepest benefit from learning a new language, you must learn to think in the new language, not just learn to translate your favourite programming language syntax and idioms into it.

Think different

The interesting thing about that is that almost by definition, if you see something in, say, Lisp that solves a problem you already have, you won’t learn much from the Lisp code. It is tempting to think that Lisp (or any other language) will somehow do what you’re already doing in some wonderfully magic way that is obviously better. But no, that isn’t how it really works.

For your problems are tuned to your existing tools. You simply can’t imagine problems that your tools can’t solve well, much less can’t solve at all. That’s why there are so few continuation-based web servers. Who’s going to invent one unless they have a programming paradigm with continuations?

And worse, when a new tool is applied to a problem you think you know well, you will probably dismiss the things the new tool does well. Look at how many people dismiss brevity of code. Note that all of the people ignore the statistics about the constant ratio between bugs and lines of code use verbose languages. Look at how many people dismiss continuation-based servers as a design approach. Note that all of them use programming languages bereft of control flow abstractions.

Thus, to truly learn a new tool, you must not just learn the new tool, you must apply it to new kinds of problems. It’s no good learning to replace simple iteration with first-class functions: all you’ve learned is syntax. To really learn first-class functions, you must seek out problems that aren’t easily solved with iteration.

The Why of Y

Which leads me back to fixed point combinators. They appear to have no practical (as in making money) use. And that’s why I’m suggesting to you that you figure out how to make one in your language of choice. The very fact that the problem is far outside of your realm of “practicality” guarantees that you will learn something. You won’t be simply applying your same-old, same-old techniques and patterns to a slightly new problem.

Start your research with Richard P. Gabriel’s The Why of Y. Try porting his examples directly to your favourite programming language. If what you want to use is too brain-damaged to support closures, you may need to do a little greenspunning and build a little functor infrastructure.

Don’t be dissuaded if you have to follow the functor route: you are learning far more about your language and about programming in general than the shmoes that settle for learning five new buzzwords related to the latest WS-* interoperability with XPath 3.x.

If you prefer a fun approach to learning, you can do not better than Raymond Smullyan’s To Mock a Mockingbird: an enjoyable romp through the world of combinatory logic. After reading this book, you will have mastered the S, K, I, Y, and other combinators. Added bonuses include a safe that can only be opened by applying Gödel’s Incompleteness Theorem to its combination. How can you read this book and not learn?

Eating my own dog food

I thought of a few things to say along these lines last week and then I abruptly realizing I was asking you to “Do as I say, not as I do.” What good is recycling problems I first encountered in University textbooks two decades ago? I put this post aside and set to work on a problem of my own.

I set out to write a function for making recursive functions—a function extensionally equal to the Y combinator—in Ruby. The ultimate goal is to take something like:

lambda { |f| lambda { |n| n.zero? && 1 or f.call(n-1) } }

And be able to have it call itself recursively. In this case, to compute the factorial function.

This is trivial, given that Ruby supports named recursion, but if you want to write a fixed-point combinator you want to write a function that makes recursive functions without using the host language’s support for named recursive calls. In other words, you are bootstrapping named recursion out of anonymous first-class functions.¹

There are important theoretical implications of being able to do this, but the killer reason to try it is to learn.

I started my quest for a function for making recursive functions with a rather trivial observation based on OO programming and the Curry function:

require 'test/unit'

class ExempliGratia < Test::Unit::TestCase

  CURRY = lambda { |f, a| lambda { |*b| f.call(a, *b) } }

  def test_recursive_curry
    maker = lambda { |func_with_me|
      CURRY.call(func_with_me, func_with_me)
    }
    assert_equal(120, maker.call(lambda { |me, n| n.zero? && 1 or n * me.call(me, n-1) }).call(5))
  end

end

In OO some language implementations, this (or self) is a hidden parameter passed to each method. Thus, there’s a parameter—me in the example code—that is added for handling recursion. If you write a recursive function—like the venerable factorial—with the extra me parameter, a trivial currying operation evaluates it recursively without any need for names.

This is obviously deficient. As noted above, we want to write factorial like so:

lambda { |n| n.zero? && 1 or f.call(n-1) }

We’ll need an f from somewhere, and just as our Scheme colleagues do, we’ll bind one as a parameter in an enclosing lambda. So we want to write:

lambda { |f| lambda { |n| n.zero? && 1 or f.call(n-1) } }

And somehow this should be transformed into a working factorial function. For the test-driven crowd, we want to write:

def test_clean_up_loose_ends
  maker = ...

  factorial = maker.call(
    lambda { |f| lambda { |n| n.zero? && 1 or n * f.call(n-1) } }
  )
  assert_equal(120, factorial.call(5))

  iterative_factorial = maker.call(
    lambda { |f| lambda { |n, acc| n.zero? && acc or f.call(n - 1, n * acc) } }
  )
  tail_factorial = lambda { |n| iterative_factorial.call(n, 1) }
  assert_equal(120, tail_factorial.call(5))
end

Of course, we need some code for maker. And the iterative_factorial case shows that maker works for functions with more than one parameter. The solution I came up with is:

CURRY = lambda { |f, a| lambda { |*b| f.call(a, *b) } }
maker = lambda { |f|
       lambda { |func_with_me| CURRY.call(func_with_me, func_with_me) }.call(
            CURRY.call(lambda { |inner_func, me, *args|
                        inner_func.call(CURRY.call(me, me)).call(*args) }, f)) }

The source code with each transformation from beginning to end is here (I strongly suspect that this “curry combinator” is actually the Y combinator with a huge amount of cruft hanging off it).

Unique or derivative, crap or craft, the process of getting it to work has enriched my mind by forcing me outside of my usual problem space. I still can’t think of a practical application for what I’ve just written. But I know I’ve stretched myself.

And now back to you: perhaps you’re rushing off to try to implement a fixed-point combinator from first principles. Perhaps your plan is to code the canonical examples in your usual language. Those are both good paths. But whether you follow them today or not, remember the underlying principle exemplified by the fixed-point combinator:

Do not dismiss impractical or weird problems. While you may not have an immediate application for the code you write to solve such problems, you are maximizing your learning when you venture outside of your usual problem space.

---

1. Named recursion is stuff like foo = lambda { |...| foo.call(:bar) }. It takes advantage of the host language’s variable binding to recurse. If you want anonymous recursion, you should be able to assign the same lambda to another name and have it work just as well, as in: fufu = lambda { |...| foo.call(:bar) }. That won’t work if you are relying on Ruby’s name for foo.

p.s. Don’t miss Tom Moertel’s derivation of the Y combinator in Ruby.

Labels: lispy, passion, popular, ruby

  ¶ 12:06 AM

  Closures and Higher-Order Functions There has been a great deal of interest in closures lately, driven in great part by the fact that there is talk of adding some form of anonymous functions to the Java. Most of the time, people talk about “adding closures” to Java, and that prompts a flurry of questions of the form “what is a closure and why should I care?”

The discussion around closures tends to go on and on about the “closing over” of free variables and only lightly touch on the biggest change to Java: functions as first-class objects with a lightweight syntax for creating them. Making it easy to do something basic like define a new function is more than just a little syntactic sugar: it makes it easy to do new things with functions that were impractical when you needed a lot of boilerplate to make anything work.

Without understanding functional programming, you can’t invent MapReduce, the algorithm that makes Google so massively scalable.

I’m going to try to explain first class functions using Ruby (it is possible to write code that does exactly the same thing using the current Java feature set, however the result is so wordy that it obscures the basic idea being presented: call it accidental complexity, or perhaps yellow code.)

Ruby is a good language for demonstrating features that ought to be in Java. Like Java, Ruby uses squiggly brace syntax. Like Java, everything in Ruby is an object—whoops, Java has primitives. Okay, like Java, functions are represented as objects.

In Java you write:

interface IFromIAndI {
   Integer call(Integer a, Integer b);
}

IFromIAndI add_two_integers = new IFromIAndI() {
   public Integer call(final Integer a, final Integer b) {
      return a + b;
   }
};

(The Java convention is to name things in lowerCamelCase, but we’ll ignore that. If you need to print this essay on a dot-matrix printer you may want to make some changes first.)

In Ruby you write the function as:

add_two_integers = lambda { |a,b| a + b }

Later on, when you want to call your function in Java, you write:

add_two_integers.call(35, 42);

And if you like semicolons, you write the exact same thing in Ruby:

add_two_integers.call(35, 42);

You can do the same thing with multiplication:

multiply_two_integers = lambda { |a,b| a * b }

First Class Functions

In the examples above, functions look a little like methods. The Java version is obviously implemented as a method. But what we did in both cases was assign the resulting function to a variable. In Java, assigning a method to a variable is not particularly easy (it is possible using reflection).

Anything that can be assigned to a variable is a value. If it can also be passed as a parameter or returned from a method (or function), we say it is a first class value. Functions as first class values, or first class functions, are very interesting. For example, what can we do passing a function as a parameter to another function?

Hmmm. Well, I am breaking a cardinal rule of selling something. We’re talking about shiny new toys without identifying a problem to be solved. Let’s talk about my favourite problem: writing the same thing more than once, violating the DRY principle.

Here are two pieces of similar Ruby code:

adder_wth_acc = lambda { |acc, list|
   if list.empty?
      acc
   else
      adder_wth_acc.call(acc + list.first, list[1..-1]) # [1..-1] returns a copy of the list without the first element
   end
}
adder = lambda { |list|
   adder_wth_acc.call(0, list)
}
adder.call([1, 2, 3, 4, 5])

And:

multiplier_with_acc = lambda { |acc, list|
   if list.empty?
      acc
   else
      multiplier_with_acc.call(acc * list.first, list[1..-1]) # [1..-1] returns a copy of the list without the first element
   end
   }
   multiplier = lambda { |list|
   multiplier_with_acc.call(1, list)
}
multiplier.call([1, 2, 3, 4, 5])

What do they both do? Pretty much the same thing: they accumulate the result of some binary operation over a list of values. adder accumulates addition, and multiplier accumulates multiplication. You could call this a “Design Pattern.” If you did that, you would use the exact chunk of code everywhere. I would call that retrograde. Didn’t our predecessors invent the subroutine so we could eliminate writing the exact same piece of code over and over again?

Why can’t we do the same thing? Well, we can. A subroutine does the same thing over and over again, but it takes different parameters as it goes. What is different between adder and multiplier? Ah yes, the adding and multiplying. Functions. What we want is a function that takes a function as a parameter.

Well, we said that with first-class functions, functions are values and can be passed as parameters. Let’s try it:

folder = lambda { |default_value, binary_function, list|
   fold_with_acc = lambda { |acc, list|
      if list.empty?
          acc
      else
          fold_with_acc.call(binary_function.call(acc, list.first), list[1..-1])
      end
   }
   fold_with_acc.call(default_value, list)
}

Now we can use our function that takes functions as a parameter:

folder.call(0, add_two_integers, [1, 2, 3, 4, 5])
folder.call(1, multiply_two_integers, [1, 2, 3, 4, 5])

This is much better. When functions can take functions as parameters, we can build abstractions like folder and save ourselves a lot of code. Note that this would be a lot harder to read if we had to surround all of our functions with Object boilerplate in Java. That’s one of the key reasons why ‘syntactic sugar’—making it brief—is a big win.

And you know what? Functions are values, not just variables that happen to hold functions. These work just as well:

folder.call(0, lambda { |a, b| a + b }, [1, 2, 3, 4, 5])
folder.call(1, lambda { |a, b| a * b }, [1, 2, 3, 4, 5])

There’s just one problem (actually two, but I’m saving one for later): everywhere you use our new folder function, you need to remember that add_two_integers needs a default value of zero, but multiply_two_integers needs a default value of one. That’s bad. Sooner or later you will get this wrong.

What we need is a way to call folder without having to always remember the correct initial value. Should we extend our understanding of a function to include a default initial value for folding? If we’re thinking in Java, maybe our IFromIAndI interface needs a getDefaultFoldValue? I think not. Why should a function know anything about how it’s used? And besides, as we build other abstractions out of functions we’ll need more stuff.

If we aren’t careful, we’ll end up implementing the Visitor pattern on functions, and all of our brevity will go out the window. No, what we want is this: in one place we define that folding addition starts with a default value of zero and in another place we say we want to fold, say, [1, 2, 3, 4, 5] with addition. Then when we want to fold something else with addition, like [2, 4, 6, 8, 10], we shouldn’t have to say anything about zero again.

Adding Curry

What we need is a function that folds addition. Didn’t we say that functions are values that can be returned from functions? How about a function that makes a folding function? We should pass it our initial value and our binary function, and it should return a function that performs the fold without needing an initial value as a parameter:

fold_coder = lambda { |default_value, binary_function|
   fold_with_acc = lambda { |acc, list|
      if list.empty?
          acc
      else
          fold_with_acc.call(binary_function.call(acc, list.first), list[1..-1])
      end
   }
   lambda { |list|
      fold_with_acc.call(default_value, list)
   }
}

Now we can do the following:

adder = fold_coder.call(0, lambda { |a, b| a + b })
adder.call([1, 2, 3, 4, 5])
adder.call([2, 4, 6, 8, 10])

No more remembering that addition starts with a default of zero.

Actually, there’s a far simpler way to avoid having to remember the default value when you want to fold over addition. But let’s just play along so that we don’t have to come up with an entirely new set of examples to demonstrate the value of functions as first-class values.

Functional programmers (as opposed to the rest of us dysfunctional programmers) will recognize this as currying our folder function. Currying is when a function takes more than one parameter and you combine one of the parameters and the function to produce a function that takes fewer parameters.

Here’s a currying function in Ruby:

curry = lambda { |fn,*a|
   lambda { |*b|
     fn.call(*(a + b))
   }
}

(This is an improvement on an earlier version, thanks to Justin's comment.)

So you can use our new function to create an increment function out of our adder and a treble function out of our multiplier:

plus_one = curry.call(add_two_integers, 1)
times_three = curry.call(multiply_two_integers, 3)

If you are ever asked, “what good is currying?,” I hope I’ve given you an example you can use to explain why currying matters, and why people do it all the time (possibly without explicitly naming it). Although it doesn’t look like much when looking at trivial examples like functions that multiply by three, it’s much more useful when creating folders and mappers where you want some of the parameters to remain constant.

Composition

Our examples combined functions and non-functions to create new functions. Here’s an example from a recent post, Don’t Overthink FizzBuzz, where I give a method for composing two functions. The idea is that if you have multiple functions that each take one argument, you can combine them using compose. I also have a method that generates functions, carbnation:

# fizzbuzz.rb

def compose *lambdas
  if lambdas.empty?
    lambda { nil }
  elsif lambdas.size == 1
    lambdas.first
  else
    lambda do |n|
      lambdas.first.call(compose(*lambdas[1..-1]).call(n))
    end
  end
end

def carbonation(modulus, printable_form)
  i = 0
  lambda do |n|
    (i = (i + 1) % modulus) == 0 && printable_form || n
  end
end

print(((1..100).map   &compose(     carbonation(15, 'FizzBuzz'), carbonation(5, 'Buzz'), carbonation(3, 'Fizz'))).join(' '))

The simple explanation of how it works is that carbonation generates functions that replace every so many elements of a list with a printable string. Compose composes any two or more methods together. So if you want to print out 100 numbers, but replace every third number with “Fizz,” every fifth with “Buzz,” and all those that are third and fifth with “FizzBuzz,” you generate a function for each replacement, compose them together with compose, and then map the numbers from one to one hundred to the resulting überfunction.

When you look at this today, it seems weird and unreadable by Java standards. I wonder if adding first-class functions with simple syntax to Java will lead the Java community to a place where code like this will not appear out of place?

Just one more thing

So we started by saying that people are getting hung up on what makes a closure a closure, and there has been less emphasis on the benefits of using functions as first-class values. Did you notice that our folder function actually includes a non-trivial closure?

If you look at the fold_with_acc function, it makes use of binary_function, a variable from its enclosing lexical scope. This is not possible with the current version of Java: if you translate this to Java, when you make fold_with_acc and anonymous inner class, you will have to copy binary_function into a final member to use it. It simply won’t compile if you try an idiom-for-idiom translation, even adding explicit types.

And then if you look at the anonymous function it returns, lambda { |list| fold_with_acc.call(default_value, list) }, that anonymous function uses default_value,another variable from the enclosing lexical scope. Once again you will have to fool around with final variables to make this work, or perhaps declare full-fledged object with constructors.

(If you try writing this simple example out in Java, you quickly find yourself inventing a lot of classes or interfaces. And they have some complicated types, like a function taking an integer and a function taking two integers, returning a function taking a list of integers and returning an integer.

After twenty minutes of that, you understand why the ML and Haskell communities use type inference: If the types are that complicated, it’s incredibly helpful to have the compiler check them for you. Yet if the types are that verbose, it’s incredibly painful to write them out by hand. Even if your IDE were to write them for you, they take up half the code, obscuring the meaning.

You also get why the Ruby on Rails community doesn’t care about type checking: types for CRUD applications are way less complicated than types for first-class functional programs.)

That’s Interesting

Part of the interest in closures is in simplifying the syntax around functions, and part of the interest is in the way that access to enclosing scope would simplify a lot of code. There’s a whole debate around the value of simplification in a world where all serious languages are Turing Equivalent.

I hope you’re convinced, by now, that programming languages with first-class functions let you find more opportunities for abstraction, which means your code is smaller, tighter, more reusable, and more scalable.

For me, simpler is just nicer until something reaches a certain tipping point: when it becomes so simple that the accidental complexity of using it goes away, I will start using it without thinking about it. Tail optimization is like that: as long as recursion is slower than iteration and sometimes breaks, I have to think about it too much. But when I’m not burdened with “except…” and “when performance is not a factor…” it becomes natural.

And then something interesting happens. It changes the way I look at problems, and one day I see a whole new way to do something that I never saw before. Functions as first class values are definitely one of those things that change everything.

Further Reading

If this has whet your appetite for more, Structure and Interpretation of Computer Programs is the book on higher-order functions and how they can be used as building blocks to create more elaborate abstractions such as object-oriented programming.

The Seasoned Schemer devotes an entire book to the uses of functions. Although the examples are in Scheme, the language is dead simple to learn and the techniques in the book can be applied to Ruby and Java (or at least to a future version of Java where you do not need functors).

The second edition of Programming Ruby is an indispensable guide. Even if you will not be using Ruby immediately, pick it up and discover why so many people are lauding the language's simple, clean design and powerful Lisp-like underpinnings.

As the author says, “Higher-Order Perl: Transforming Programs with Programs is about functional programming techniques in Perl. It’s about how to write functions that can modify and manufacture other functions.

“Why would you want to do that? Because that way your code is more flexible and more reusable. Instead of writing ten similar functions, you write a general pattern or framework that can generate the functions you want; then you generate just the functions you need according to the pattern. The program doesn’t need to know in advance which functions are necessary; it can generate them as needed. Instead of writing the complete program yourself, you get the computer to write it for you.”

It’s worth reading even if you have no intention of using Perl: the ideas span languages, just as SICP is worth reading even if you don’t use Scheme at work. And be sure to read Higher-Order JavaScript and Higher-Order Ruby. They translate HOJ’s ideas to other languages.

Notable Follow-ups:

Some useful closures, in Ruby: “The Dylan programming language included four very useful functions for working with closures: complement, conjoin, disjoin and compose. The names are a bit obscure, but they can each be written in a few lines of Ruby.”

From Functional to Object-Oriented Programming: “OO allows a traceable connection between the conceptual design level and the implementation level. Concepts have names, so you can talk about them, between programmers and architects.”

HOF or OOP? Yes!: “First-class functions are a natural fit with OO, as evidenced by their presence in OO languages that aren’t glorified PDP-11 assemblers with some OO stuff bolted on the side.”

But Y would I want to do a thing like this?: “To truly learn a new tool, you must not just learn the new tool, you must apply it to new kinds of problems. It’s no good learning to replace simple iteration with first-class functions: all you’ve learned is syntax. To really learn first-class functions, you must seek out problems that aren’t easily solved with iteration.”

Labels: java, lispy, popular, ruby

  ¶ 11:55 PM

  The shortest post yet written on the realtionship between Ruby Metaprogramming and slavish adherence to the Gospel of the GoF Ruby Metaprogramming elevates the Decorator Pattern from a useful tool to a core idiom for creating idioms.

Labels: ruby

  ¶ 3:19 PM

  Don't Overthink FizzBuzz I noticed some traffic coming to my post on juggling from Using FizzBuzz to Find Developers who Grok Coding. Like me, the author is having trouble with the fact that 199 out of 200 applicants for every programming job can’t write code at all. I repeat: they can’t write any code whatsoever.

UPDATE: If you think that I just claimed that 199 out of 200 working programmers cannot code, stop immediately and either read my follow-up explaining the math, or read Joel’s article on why companies aren’t as picky as they think they are. Thank you.

So the author has decided to set the bar ridiculously low. As the post says:

I’ve come to discover that people who struggle to code don’t just struggle on big problems, or even smallish problems (i.e. write a implementation of a linked list). They struggle with tiny problems.

He gives an example of a “tiny” problem that is quite suitable for a phone interview:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

One of the nice things about using a tiny problem is that anyone who has written actual code in the last six months will solve it in less than ten minutes. This is good because (a) it leaves more time for talking about important things, and (b) if the candidate can’t solve the problem you will find out right away and save yourself a lot of grief.

As you can imagine from a post like this, quite a few people have stepped forward with creative solutions. Here’s mine:

# fizzbuzz.rb
# see http://weblog.raganwald.com/2007/01/closures-and-higher-order-functions.html

def compose *lambdas
  if lambdas.empty?
    lambda { nil }
  elsif lambdas.size == 1
    lambdas.first
  else
    lambda do |n|
      lambdas.first.call(compose(*lambdas[1..-1]).call(n))
    end
  end
end

def carbonation(modulus, printable_form)
  i = 0
  lambda do |n|
    (i = (i + 1) % modulus) == 0 && printable_form || n
  end
end

print(((1..100).map
   &compose(
     carbonation(15, 'FizzBuzz'), 
     carbonation(5, 'Buzz'), 
     carbonation(3, 'Fizz'))).join(' '))

Right away I think you want to be careful if you ever trot a solution like this out in an actual interview. Here are some of the things that could go wrong:

• The interviewer merely wanted to go through the motions of demonstrating you could program. Now she’s going to have to get into a discussion with you about how your solution works, which is irritating and wastes time that could have been invested more profitably on a design question;


• The interviewer might presume that you will always find the most indirect route to the destination and decide you belong in an ivory tower;


• The interviewer might not understand your solution at first glance but will make up for this by “bikeshedding” and grilling you about some minor nit like the failure modes of using && and || instead of the if statement or the ternary operator;


• The interviewer might have just finished The Seasoned Schemer and grill you over why your solution doesn’t use the Y Combinator to implement compose (snap!).

Of course, some interviewers are just looking for an excuse to talk about technical issues and will not prejudge you in any way. Speaking for myself, I would laugh if you wrote something like this out. But then again, I once worked for someone who had won the second International Obfuscated C Contest.

Update: Don’t Overthink the Interview Either

If you are conducting an interview and you receive a cryptic answer, or an impossibly concise one-liner, or perhaps something like the above that is redolent of Higher Order Functions, do you embrace the candidate as a genius? Or perhaps avoid them as someone who cannot write clear, maintainable code?

I suggest the best answer is neither. Stay on track: you asked the question for the purpose of eliminating the 199 out of 200 that have absolutely no hope of ever producing working software. You have just identified that this person is the one in two hundred applicants who can actually code. Mission accomplished. You aren’t trying to get to HIRE or NO HIRE over the phone.

Invite them in for an interview: that’s the place where you can drill down and obtain their views on professional programming. Remember, this is a toy problem. Unless you load the question down with requirements that their answer resemble production code, why should you have any expectation that the candidate only knows one way to write software?

This is like trying to hire programmers who know both languages, FORTRAN and COBOL.

If you do ask them for production code, don’t be surprised if the best candidates decide not to work for you: they will rightly point out that FizzBuzz is not a realistic example of a production problem.

Overall I think the best approach as an interviewer is the simplest: pose the simple question. Indicate it is a screener designed to confirm that they are the person described on the resume.

If anything, tell them that there is no need for production artifacts like documentation and unit tests, you just want working code in as little time as they are able. The no-hopers won’t get it no matter how simple the question, and the good people won’t waste a lot of time with JavaDoc and xUnit.

And then make your decision based on one objective fact: does the code run and produce the desired output. Everything else is superfluous to the question of whether the candidate should be asked into your office for a face-to-face meeting.

Update: a response to some of the criticism.

Labels: jobs, lispy, ruby

  ¶ 9:49 PM

  Where were you on Saturday, November 9, 2002? Had you dropped by MIT on November 9th, 2002, you might have seen a rather large collection of hackers, academics, tool vendors, and programming language enthusiasts gathering for the LL2 conference. It was rather like taking the current readership of Lambda the Ultimate and programming.reddit.com—no, I am wrong.

It was rather like taking the top couple of hundred of the people who write papers and blogs cited on Lambda the Ultimate and programming.reddit.com and gathering them in an auditorium together to talk about programming languages.

As the rather Spartan LL2 web page explains, the theme of the conference was:

How to get usable and useful programming tools into the hands of programmers, minimizing dogma, and maximizing flexibility.

Like any other conference, there were speakers. The speakers talked about the languages they had invented, and about how and why people ought to use them.

Had you been there, what would you have thought about the first speaker, Joe Armstrong, and his language, Erlang? Just another weird language for embedded telephone switches? Or an important language that is powering diverse applications such as a distributed, replicating database?

Joe spent a lot of time talking about unreliability. About how computers and programming languages are always designed as if everything always worked and that not working was the exception case, rather than the rule. And about how you can’t build systems out of dozens, hundreds, or thousands of pieces without assuming that everything is unreliable, all of the time.

And how there ought to be a programming language that builds that right into the system. Like Erlang. Would your eyes have glazed over? Or would you have thought about MapReduce and grid computing and would you have taken notes furiously?

Would you have thought that two different talks (one about persistence and another about asynchronous exceptions) were too much for an obscure language called Python? Would you have marked Python down as “One to Watch”?

And what would some random guy know about inventing “the next big programming language”? Oh, he was managing Microsoft’s Programming Languages Systems group. Well, there you go, one guy that Corporate America might care about. I wonder how many of his predictions about the next big programming language have come true? Good thing his talk is on line, we can check…

After lunch, some random guys talk about getting an un-typed language running on top of the Java Virtual Machine. I mean, really, who the hell would think that would ever become important?

Next up, the organizers had flown Yukihiro Matsumoto in to talk about Ruby. Yes, in 2002 the organizers wanted a bunch of Lisp-heads—the Q & A for absolutely every talk included at least one question about when macros would be added to the speaker’s language—to hear from someone who had designed a language known at the time as the most popular scripting language in Japan. Had you heard of Ruby in 2002? Did you care?

And what was with him constantly talking about making programming fun and comfortable? As if a programming language was a user interface for programmers. Everyone knows that programmers love idiosyncratic tools like Emacs, right? Who designs a language for usability? Who indeed.

There were other talks. They were all good, just as good. There was a spirited exchange of ideas over lunch in the lobby, again upstairs in the MIT researchers’ offices, and continuing late into the night at a nearby pub. It was a phenomenal gathering.

Were you there?

That isn’t important right now. If you were there, good for you, and I hope in the four years since you have taken some of those ideas, and a lot of that enthusiasm, and rolled it into what makes this industry great. The fact that anyone—even some guy from the other side of the world—can make something that other people like and use. Whether it’s free or for pay, whether it’s a language, a tool, an application, or a piece of hardware.

But even if you were there, that was then and this is now. 2007. Here’s the important question: Where is LL2 this year?

I asked “where is LL2 this year.” Actually, it may not be a Lightweight Languages conference. It might have nothing to do with programming languages. But somewhere in the world, somewhen in 2007, there is going to be a conference. Or a gathering. Maybe it’s this year’s Startup School. Maybe it’s a DemoCamp in your city.

Wherever, and whenever it is, you are going to see and hear things that are going to matter to you over the next five years.

They may not look like much in 2007, but they’re the seeds of the next Big Thing, the thing that will be big four or five years hence, in 2012.

Finding the conference

In 2002, LL2 didn’t look like much. You probably couldn’t find a job using any of the languages discussed at the conference. Unless you wanted to work on telephony. The lone representative of a mainstream company—Microsoft—wasn’t talking about their products, he was talking about things that would disrupt their products.

So if you’re looking for the right conference in 2007, there are two clues: the agenda isn’t going to include anything you can use to make money, and it isn’t going to feature anybody trying to make money off of you.

That’s right: no consultants, no white papers, no thinly veiled sales pitches. That knocks most Ruby conferences out. Maybe not all, but most. The right conference isn’t going to be about building CRUD applications on top of MySQL with AJAX goodness. That may not be out of date, but it’s so 2007, and we’re looking for 2012.

In 2002, the audience was highly interactive. Most of them were working on their own projects. They were practitioners, not tourists. They weren’t there to get a job, or goof off work. They were there to learn stuff for themselves and share what they knew with others.

In 2007, you should be looking for the same thing. For a conference that will be attended by people who are, as Joel would say, Smart and Get Things Done. Lacking a way to check the door before you show up, how do you find out?

Naturally, you find out by talking to other would-be attendees before going. LL2 had LL1’s active mailing list. In 2005, Startup School had a wiki. I don’t know what the right conference in 2007 will have, but I will bet on this: if there’s no community building in advance around a wiki, a list, or some other peer-to-peer communication, it isn’t the right conference.

The kind of conference where there is a one-way exchange between you and the organization—they tell you where to show up and you send them money—is not the right kind of conference. Look for the conferences that are built on top of active communities.

And when you find the community, pay attention to the action-to-talk ratio. I’m terrible at this, I always have to push myself to work and stop goofing off on my blog. But you know what’s worse? People who don’t have any work to begin with, it’s all just entertainment to them. They are tourists, and they are a liability to a conference.

Here’s why.

When tourists reach critical mass, the organizers start to cater to them. That means safe topics and safe speakers. Consultants. People with a good “patter” but not much to say that would disturb anyone.

Also, the tourists tend to ask the wrong questions, because they aren’t the market for anything new and interesting. Say a tourist raises her hand. She’s going to ask about something she imagines might concern a user, but you know what? She isn’t a user and she really has no idea how a user thinks, because she’s not the type to learn anything new until it’s already popular, and she doesn’t have any idea how such people think.

I think the root of your mistake is saying that macros don't scale to larger groups. The real truth is that macros don't scale to stupider groups.

So she asks something irrelevant. Like about language performance. Or bindings to Oracle. Or whether there is an Eclipse plug-in. Or how it will scale to larger programming teams.

But when a practitioner asks a question, it’s a smart question, it’s important. The speaker learns something important about their tool and the rest of the audience learns too. The next thing, someone asks a smarter question, and the energy builds.

If there are too many tourists, you can’t learn anything significant in the Q & A, and that’s a shame, because Q & A is where the action is.

So, my advice for finding the right conference is, avoid anything to do with either you or the presenters making money, find a conference built on top of an active community, and go the the conference with the highest density of practitioners.

And my question really ought to have been, will you be at this year’s important conference? and better still, will you be presenting?

Labels: passion, ruby

  ¶ 4:57 PM

  A Ruby, Io, and Ocaml Programming Pattern

Every 5 minutes you spend writing code in a new language is more useful than 5 hours reading blog posts about how great the language is.

Labels: passion, ruby

  ¶ 1:38 PM

  If Sneetches with Stars use Java, and Sneetches without Stars use Ruby, who uses ML? ML is a programming language featuring type inference: you don’t have to encumber your code with type declarations, the compiler can figure them out for you. So… are type inference languages like ML for Sneetches with or without stars? Or another kind of Sneetch entirely?

Now, the Star-Belly Sneetches had bellies with stars.
The Plain-Belly Sneetches had none upon thars.
Those stars weren’t so big. They were really so small
You might think such a thing wouldn’t matter at all.

Update: More than a few people have written that Steve Yegge's association of static typing with neatness and dynamic typing with slovenliness runs opposite to their impressions of the kinds of people who strongly prefer one or the other. I used Steve's terms in the original post, partly because I thought people would get the same joke I thought Steve was making. It looks like they don't, nobody wrote to say "LOL." I have changed the terms to something that represents what I think of the cultural divide between programmers who like Java and programmers who like Ruby.

Let’s review. Sneetches with stars like to use a colour-coded label maker to label the drawers, boxes, and files in their office. Once glance at everything and you know what it holds. Sneetches with stars add extra labels even when you don’t need them. For example, if a box is labeled ‘tax receipts’, each piece of paper inside has a post-it note saying tax receipt’, even if it’s obviously a tax receipt and lives inside the tax receipts box.

What is Stariness?

Sneetches with stars like these languages we say are statically typed. What do we mean by the word static? We mean it can be resolved at compile time. Other words for this idea are invariant or constant. Sneetches with stars like languages where the type of each entity can be resolved at compile time.

Some people are always critical of vague statements. I tend rather to be critical of precise statements; they are the only ones which can correctly be labelled "wrong."

Let’s dive into this a little deeper. (My apologies to my readers who were actually paying attention to the stuff in first year computer science that isn’t a requirement for getting a job at BigCo.) What does it mean when we say “something can be resolved at compile time”? That expression is laden with implementation details like assuming we’re using a compiler. But it’s a convenient short-hand for saying something about the program that is true every time you run the program.

Consider the final declaration in Java. If you write:

final String snafu = "situation normal...";

We know that the variable snafu always holds a reference to the constant string "situation normal...". No matter what data you feed to your program and how you mangle it, snafu will always be "situation normal...". Do you agree? (Joe Campbell, put your hand down. Yes, there is a back door way you can change the contents of a String in Java.)

Java can take advantage of this to perform constant propagation. Everywhere you write snafu, Java can substitute "situation normal..." and throw away the variable lookup. To get away from arguing about back doors in the String class, let’s consider one of the primitive types, a boolean. If you write:

final boolean foo = true;
    // code without assignments to foo
    if (foo) {
        // do something
    }
    else {
        // do something else
    }

Wouldn’t you agree that the compiler can get rid of the variable lookup and the if statement? The path through the code is always through the // do something path every time you run the program.

Now back to the word stariness. We really mean the amount of stuff about the program that can be resolved at compile time, or if you prefer, the amount of stuff that is true every time you run the program.

In the example above, the compiler can figure out which branch the program will follow at compile time, because that variable is true every time you run the program.

Stuff that is always true is useful. For most programs, we have an idea in our head about “correctness.” What we mean when we talk about a program being correct is that it produces desirable results every time you run the program.

A formalist is one who cannot understand a theory unless it is meaningless.

Stariness is thus similar to correctness. And that’s why a lot of people, the Sneetches with stars, are obsessed with it. Being able to “prove” something about their program (“the method call foo.bar(5) never throws a MethodNotImplemented exception”) feels a lot like being able to prove that their program is correct.

It feels a lot like it, but it isn’t the same thing. The reason it isn’t the same thing is that while its true that a program throwing MethodNotImplemented exceptions is probably not correct, it’s not true that a program that doesn’t throw such exceptions is correct. It just feels, somehow, more likely to be correct because we’ve thrown out one of the infinite ways it can be incorrect.

Now that we’ve dispatched that logically, let’s be clear about something: just because stariness does not enforce correctness, it doesn’t mean that stariness isn’t useful. Stariness is useful. Period, no debate.

Back to inferences

Type inference is also for Sneetches with stars. A language with type inference resolves the type of each entity at compile time by inspecting the program and figuring the types out through inspection. It’s a lot like the way a compiler can look at the Java code above and figure out that you always // do something and you never // do something else. The code looks sorta like you could go either way, but the compiler knows better.

Languages with type inference look like variables can have any type, but the compiler knows better. Remember the labels that the verbose declaration Sneetches with stars love? Type inference languages still have labels, but the labels are hidden inside of the files and boxes where you can’t see them.

Remember when manufacturers used to put their labels inside clothes instead of right across the front? Same thing. The rules for what goes where are strictly enforced, it’s just that if you can figure out what goes where with a bit of common sense, you don’t need a label or a post-it note.

Compare these two snippets of Java:

final String[] words = { "foo", "bar", "blitz" };
final int word_length = words.length;
final String[] anagrams = new String[word_length];

…and…

final words = { "foo", "bar", "blitz" };
final word_length = words.length;
final anagrams = new String[word_length];

Hey, if a variable is final, we can figure out its type in Java through simple inspection. Making that work in the compiler is something an intern ought to be able to do over a Summer work term!

(Frank Atanassow pointed out that techniques exist for inferring the types of nearly all Java variables through inspection of programs. But this simple case is enough for our purposes.)

So if we take a valid Java program and simply erased type declarations whenever we could logically deduce the type of the variables (using our simple scheme), but left them in whenever we were not sure of the final type of the variables, we would have exactly the same program. Nothing about it has changed except it has fewer symbols. It’s just as starry, it is just as static, it is no more or less correct than it was before we erased some symbols.

And you over there itching to say something about IDE refactorings and auto-completions: None of those go away either. You can rename things and move things and press command-tab to get an object’s methods whenever you like. So… would you agree that type inference of this sort doesn’t change a starry program into a starless program? This isn’t about stariness versus starlessness, it’s about the obsessive-compulsive desire to label everything.

The bottom line: type inference does not change a statically typed language into a dynamically typed language. It’s still starry.

So why can’t the Sneetches without stars use type inference?

Think of types as being like values and objects like variables. A statically typed language is one where there are no type re-assignments. Some languages enforce this. But if you write a program in a static way, you can still reason about it. This is why lots of people think that we can “neaten up” languages like Ruby by adding type inference to the compiler: they're thinking about programs that are neat to begin with, but we happen to have written them in a language for Sneetches without stars.

And whenever someone talks about a refactoring IDE or an auto-completing IDE for a dynamic language, they’re talking about performing some type inference on Ruby programs that are written in a static way. So… what’s the holdup? We said we could add type inference to Java in a Summer. Where’s the intern to add it to Ruby?

Programmed. In me somewhere, he thought, there is a matrix fitted in place, a grid screen that cuts me off from certain thoughts, certain actions. And forces me into others. I am not free. I never was, but now I know that; that makes it different.

The problem is that the set of all programs that are "starry" is a subset of the set of all programs that parse correctly. So either not all starless programs are neat, or not all portions of a starless program are neat, or both.

Let’s compare back to our Java snippet. Remember:

final boolean foo = true;
// code without assignments to foo
if (foo) {
    // do something
}
else {
    // do something else
}

The compiler could infer that we always follow the first branch because it knows that final variables are not reassigned. They’re immutable. What happens if we erase the final keyword as well:

boolean foo = true;
// code that might have assignments to foo
if (foo) {
    // do something
}
else {
    // do something else
}

Now the job is much harder. We have to examine all the code in between the declaration and the use of foo. If there are any assignments involving things we can't know until runtime, we can't know the value of foo until runtime.

For a very large class of programs, we cannot infer the contents of a variable with less runtime complexity than running the program for every possible input. This is why compilers have limitations on the optimizations they can perform, and humans still need to do some thinking about writing fast programs.

This exact same thing happens with types. In statically typed languages, types are never re-assigned. Whether explicitly declared or inferred, they're immutable. But in languages like Ruby where methods can be added and removed dynamically, where messages can be forwarded dynamically, where we can even send messages dynamically, the types of objects are fully mutable.

In starless languges, there is no final keyword on the types of objects. We can no longer infer the type of a variable in any but the simplest, degenerate cases.

The type inference problem in dynamically typed languages is exactly the same as the inferring the possible contents of a variable problem. The inferring the contents of a variable problem is doable for a restricted set of programs. And the way we tell the compiler that a variable is a member of this restricted set is with the final keyword.

Likewise, the way we tell a compiler that the type of a variable is also restricted is that we use a language where the type of every variable is final. It’s the same thing: we don’t reassign final variables and we don’t change types on the fly.

Starlessness is not about writing programs without labels. Starlessness is when you write dynamic programs. Dynamic doesn’t mean ‘unlabeled’. As I showed above, if the final keyword is there, the label is mostly optional. But if you don’t have final, you’re writing dynamic programs.

Truly starless programs have dynamic types: types that change at run time. they are not always one thing or another. For example, what if you write an Object-Relational Mapper (“ORM”) that reflects on the database structure at run time. That is, you can change columns in a database table and you get new getters and setter methods in your program. Without recompiling.

In a fully static language (with or without type inference), you can’t do that. Think of Java’s JDBC: you have to fool around with methods that get values and pass a column name as a parameter. Or maybe you create a hash. And C# is getting this capability, but of you look closely you still have to define the “type” of a query through the LINQ syntax.

Are Sneetches with stars ever starless?

A dynamically typed language lets us define an object holding a database row with methods for each column. But we can’t know at compile time whether our program will throw a MethodNotImplemented exception because we don’t know whether someone will monkey with the database structure. That sounds bad.

But what happens if you write the same thing in a neat program? Aha! a SQLException! it seems that there are dynamic things that must be dynamic no matter what you do.

This is a specific case of Greenspunning. There are some facilities of dynamic languages that you are going to need. If you don’t have them built into your static language, you will build them yourself or use a framework that has already built them for you. Other examples I have seen in Java programs include:

Spring and Hibernate;
Any use of Class.forName(...);
Any use of dynamic proxies;

In essence, you’re being a Sneetch without a star but twisting your starry language to permit starlessness. And for those portions of the program that are no longer nice, starry bundles that can be examined at compile time for invariant behaviour, you are indeed in dynamic territory and have to live with the risks.

In my experience, all non-trivial starry programs contain this kind of starlessness. To my admittedly inexperienced eyes, starlessness is the hallmark of expert programming in starry languages ("expert" does not necessarily mean "more desirable," especially in the minds of those who believe that programs should be written and maintained by mediocre developers).

Eating cake

So… can we say that since you can write starless programs in neat languages, you can have the useful benefits of stariness when you need it and the flexibility of starlessness when you need that too? Isn’t that better?

Yes, you can say that. And you may be right, for you. The Boo people believe that: their language has a duck keyword for when you feel like a Sneetch without a star. Be aware that at this moment in history, languages designed for Sneetches without stars seem to have much better features for writing starless programs than languages for Sneetches with stars. So my observation is this:

If you dislike the verbosity of starry languages like Java but like the feeling of safety, try a type inference language. Don’t go to a starless language if you don’t intend to actually write dynamically typed programs.

My experience is that if you are frustrated by the amount of work you have to do to express the algorithms in your head, you should look at a language that removes your frustration. If you're using Java and don't like the verbosity, find a language that celebrates brevity while preserving static typing. But if you're using Java and find yourself pushing more and more logic out of java because its type system is too static or too inflexible, you should consider a language with a different approach to typing.

Computer languages differ not so much in what they make possible, but in what they make easy.

Why would the Sneetches without stars use starless languages?

Writing starless programs on top of neat languages is exactly the same thing as writing automatic memory management routines on top of a manually managed programming language or writing functional programs on top of a noun-centric object-oriented language.

You can take that statement as an argument in favour of specialized languages for Sneetches without stars or as an argument against them. My guess is that the above statement is true and a Rorschach Inkblot: You will interpret it as confirmation of your existing prejudices.

Labels: java, popular, ruby

  ¶ 3:34 PM

  Anything "Ridiculously Easy" is going to attract some Ridicule Recently, Lucas Carlson announced Starfish, an ultra-lightweight distributed processing framework, and map_reduce, his own implementation of distributed mapping and reducing based loosely on Google's famous MapReduce.

Almost immediately, people pointed out that what he had created looked to them like a toy. Some people pointed out that although its map is fully distributed, its reduce is centralized in the supervisor process. Others pointed out that fault tolerance was not built-in. Some even pointed out that it looked like a thin wrapper around other services (as if free software is sold by the pound).



I agree that map_reduce is not MapReduce. That's a good thing. After all, the world already has MapReduce. If you want to use MapReduce just the way it is, go work for Google. Don't wait.

You know, all the comparison to MapReduce has a strangely familiar ring. What do the following systems have in common?

Minicomputers, microcomputers, personal computers, laptop computers, 5 1/4" disc drives, 3 1/2" disc drives, 1.8" disc drives, client-server computing, PC databases, Unix, C, Ruby, Java, television, colour television, automatic transmissions, iPods, ...

Must I go on? History is replete with inventions that are simplified, scaled-down versions of things that have come before (I know, Java-haters will find it hard to remember a time when Java was the new kid on the block that represented a simplified, scaled-down language compared to C++). It seems that every time some such thing comes out, somebody points out that it is a toy, not suitable for serious use.

My personal favourite example of dismissing advancement is the television. When it came out, old time radio people dismissed it as a toy. Nice call. But wait, we aren't done. When colour television came out, the black and white television people dismissed it as unneeded. Somebody, as they say, wasn't dancing with the innovation they brought to the ball.

And what happens? Come on, you know where this is going, it's practically a cliché: first the new, simpler, less powerful thing lives in a weird niche where people have a special need that overrides the bountiful impracticalities of the new thing. Then whole new markets are discovered where the new thing offers the perfect balance of features and before long, the new thing takes over the old markets.

It's pretty obvious to me that when a lot of people dismiss something as being too simple, too underpowered, and lacking the wide variety of features and options of its predecessors, the right thing to do is to take a closer look and suspend final judgment. Right now there's a world market for maybe five full-text web search engines. If you are one of those five people trying to index the entire web, you can dismiss map_reduce immediately.

Everyone else might want to look at map_reduce (and everything else considered too wimpy for serious work) and instead of listing all the ways it falls short of the status quo, ask yourself in what ways does the status quo falls short of mass-market appeal.

At first glance, map_reduce looks like it makes it really easy to distribute analysis, especially of things living in your database. Hmmm. Thousands of Rails users put things in one database. Will it scale to 2,000 systems? How many of you have 2,000 systems? Next question.

Now how many Rails programmers just ordered a shiny new Mac Pro with four cores? Nice to see a sea of hands. Guess what? You are all people who could benefit from map_reduce right now. Do you have a few spare Macs or PCs in your office? All the better, put them to work while you're at it.

I'm not in a position to recommend using map_reduce until I've tried it myself. But I can say without hesitation that there is a need for ridiculously easy distributed processing on Ruby, and it doesn't need to scale to 2,000 machines to be useful.

Update: Lucas posted a working example from a production system: How I sent emails 10x faster than before. Updated again to link to his explanation for how reduce works in map_reduce.

Hot news!

"How many of you have 2,000 systems?" The answer is: all of you. Amazon's Elastic Compute Cloud lets you run applications on thousands of machines and pay only for compute time and bandwidth outside of the cloud. Note to my sharp-witted readers (again, all of you): this is not a license to write and say "because I might run an application on 2,000 servers, I'm dismissing Starfish without another thought." The correct thing to write is "I have written an application that runs on 2,000 servers, and..."

Labels: ruby

  ¶ 1:04 PM

  Dynamic is the opposite of Static, not of Explicit I recently read a post where the author said he does not care for Ruby's dynamic typing.

When people start talking about types in programming languages, the terms fly around in a rather fast and loose manner. Here's a rather extensive and balanced discussion: the article on Type Systems in Wikipedia.

Notice that Ruby is dynamically typed (it's types are determined at run time and can change at run time), strongly typed (it does not allow an operation to succeed on arguments which have the wrong type), and type-safe (it does not allow operations or conversions which lead to erronous conditions).



(There's another school of thought about how to name the properties of type systems. More on that at the bottom.)

Proponents of explicit types may say that Ruby is not type safe because it is possible to compile programs that contain errors which will not be detected until the program is run and the erroneous condition is detected.

Statically typed languages such as C# can detect a class of such errors at compile time. Some Ruby enthusiasts argue that they do not like the boilerplate associated with explicit typing and feel that the extra error checking does not outweigh the additional overhead.

Both arguments are mistaken. Sorry about that. If Explicit and Implicit were the issues, we could add Type Inference to Ruby and it would have the low overhead of implicit types as well as some extra error-checking (work on Soft Typing for languages like Scheme and Erlang aims to provide compile-time checking for implicitly typed languages). However, type inference is a feature of statically typed languages.

The trouble is that Ruby is dynamically typed. Specifically, Ruby contains extensive dynamic meta-programming constructs. Type inference works with statically typed languages. The compiler must be able to infer the type or set of types possible for any variable.

Consider a Ruby application that modifies classes and objects at run time. The simplest example is Ruby's built-in accessor methods: attr_accessor :foo is a class method that actually creates two instance methods at run time, foo and foo=. What happens when attr_accessor is called with a variable as its argument, like attr_accessor my_attribute?

If the type inference engine later looks at a call such as bar.blitz = 'bash', how does it know whether attribute_accessor was ever called with 'blitz' or :blitz as an argument? Dynamic meta-programming makes the type inference problem undecidable.

A lucid argument is that Ruby's dynamic typing makes it difficult to detect type errors statically. The correct counter-argument is that Ruby's style of dynamic typing makes it possible to use dynamic meta-programming, such as Ruby on Rails' ActiveRecord, not that Ruby's implicit typing is more productive.

Once you've made these arguments, you can decide for yourself whether the benefits of dynamic meta-programming do or do not outweigh the advantages of static type checking.

(Updated to use the expression "dynamic meta-programming" to distinguish features like define_method from static meta-programming features like macro systems, courtesy of the well-informed Lambda the Ultimate).


p.s. Ward's Wiki seems to use the term static typing to mean the same thing as explicit and strong typing. I prefer that the term static means that it doesn't change. The same wiki seems to use the term dynamic typing to mean the same thing as implicit and strong typing. It includes the possibility that a program is what I would call strongly, statically and implicitly typed: the checking is done at run time but the types of variables never change. The commentary suggests the phrase semantic dynamic typing for the quality of dynamic typing that encompasses dynamic meta-programming. If you like these terms, please substitute "semantic dynamic typing" for "dynamic typing" above.

p.p.s. And there's another argument that dynamic meta-programming, like macros, should be considered harmful. I'm saving my reply for a rainy day.

Labels: lispy, ruby

  ¶ 11:11 AM

  car and cdr have had their fifteen minutes of fame In response to Six Things I Dislike About Ruby (and Four I Don't), someone quipped:

while we are stamping out those silly ungrammatical C++-isms like "puts", can we also get rid of those silly lispisms of 'car' and 'cdr'?

Yeah, sister (or brother, as the case may be)!

car and cdr are historical anachronisms. They are like secret handshakes: their only remaining value is to help a small cadre of enthusiasts bond around a shared collection of obscure trivia.



I wouldn't be suprised if Lispers have droppped these from production systems in favour of the logo-isms first and rest. But then again, I wouldn't be surprised if some Lispers hang onto them either. After all, if every textbook uses them as examples, they become familiar through repetition, even if their names no longer make any sense whatsoever.

The last time I checked nobody was running Lisp on IBM 704s any more. These names really deserve a quiet retirement in a shady home where they can share war stories with puts while they listen to goto complain about what happened when call/cc made him obsolete.

All that being said, car and cdr were rather prolific parents: Lisp implementations usually support a special syntactic sugar called composition where you can make up a function with the following form: (/c[ad][ad]*r/ ...) and this is executed as if you types a series of nested cars and cdrs. For example, (caddr foo) has the same effect as (car (cdr (cdr foo))).

I really like composition. We can sort of get that with dot notation and messages in languages like Ruby. But I secretly admire the way the German language lets you compose entirely new nouns by sticking smaller nouns together.

I think car and cdr's composition has a spiritual descendant in Ruby's metaprogramming style. For example, dynamic finders in Rails. Person.find_all_by_username_and_password really feels like caddaddr. Uh, maybe not.

But it's nice to see that some of the good ideas from Lisp thrive in new homes.

Labels: ruby

  ¶ 9:06 AM

  Six things I also dislike about Ruby (and four that I don't) 10 Things Elliotte Rusty Harold "Hates" About Ruby:

1. initialize

To create a new object in Ruby you invoke the new class method like so: c = Car.new("Toyota") Naturally you think the constructor would be defined in a method called new, right? Or just maybe a method called Car like in Java? But no, instead it has to be called initialize.

Right on. That's annoying.

2. Weak typing

Ahhh... I have promised not to write the same essay more than four times in any twelve-month period. Let's agree that Ruby would be even better if there was some sort of type inference system that doesn't require type declarations everywhere.

4. Global variables

Didn’t somebody tell me Ruby was an object-oriented language?

5. puts

Do we have to copy C’s most ungrammatical, pointless method names?

Matz was clearly in Raymond Chen mode when he put all the perlisms in the language. As an application developer, I don't use any of them. But I'll accept it on faith that there are people using Ruby as a scripting language who like them.

But I don't have to like them.

6. Zero-based arrays

C arrays began at zero to match memory addressing. In a weakly typed scripting language, there’s exactly no reason to do this. There hasn’t been for decades. Can’t we please start the arrays at 1 where God intended? Hasn’t anyone read Numerical Recipes? Aren’t we tired of fencepost errors yet?

See above. But with extra pursing of the lips. Zero-based arrays are a perfect example of a leaky abstraction. Back in the days when programmers all wore beards and C was the new kid on the programming block, zero-based arrays were really just a funny kind of macro for performing a multiply and add on an integer that you hope is a pointer.

No really, it's true. Go ahead, look it up. I'll wait.

Okay, I agree with Rusty and then some. I'm perfectly okay with a new language using 1-based indexing. I think I can get over the momentary unfamiliarity as I untrain my brain to stop doing this unnatural zero-based thing.

7. elsif

Sorry. “elsif” is not a word in the English language, and it shouldn’t have been one in Ruby. Would typing one extra letter have been so onerous?

Getting this wrong is almost a rite of passage when learning Ruby. Annoying. But not fatal, fortunately. At least Ruby doesn't assume elseif is a new variable declaration. I hope.

8. $_

Global variables suck. Did I say that already? Global variables you didn’t actually create and that pop up out of nowhere suck even worse. And global variables whose names are indistinguishable from line noise suck still more. Java’s verbose, but that verbosity is in the service of legibility. Ruby’s compactness all too often serves only to obfuscate.

See above, again. I really suspect that the Perl-style stuff is of value when writing one-liners on the command line. It probably doesn't belong in an application longer than a page.

I would normally say "so don't use them," but there is a small problem with globals: at least one, $=, affects the default behaviour of a kernal function: regular expression matching. For that reason, I consider it a little dangerous.

I can live with built-in global variables that are, essentially, syntatic sugar for functions. But I'd rather that they not be syntatic sugar for method calls that change global state. No doubt you cannot have one without the other and thus I dislike them as well.

Now about the lack of object orientation. It looks like other langauges have exactly the same problem. What's with all the singletons out there? And what happens when you call java.lang.System.setProperty(...)?

It seems that programmers like this stuff, no matter how bad it is for them. Which reminds me, ribs for lunch today?

9. Methods are public by default

I personally don't care one way or the other about what the default access is, but I think Rusty has been perfectly cogent when presenting his argument in favour of restricting APIs as much as possible. And he goes further to suggest that restriction should be the default.

Shrug. After all, you can choose what you want. Is there something drastically wrong with assuming that if a programmer writes a method with the default (public) visibility, that the programmer knows what she is doing and wants it that way?

Uh, oh. I think I've also written this essay before. Let's move on.

But I'll put this one down as a tie. I think Ruby would be a perfectly fine language if you had to take more care to make methods public.

By the way, is there a resonance between this perspective and with the way you can declare that certain Rails controller actions must be invoked with PUTs or via XmlHttpRequest?

10. No package access or friend functions.

There’s no access in-between public and private. All too often different classes in the same library/application/codebase need more detailed access to their other parts than the general public should have. Ruby provides no way to manage this.

(Something I find quite interesting: most of the Java programmers I have met do not use Java's 'default' visibility. But back to the subject at hand.)

There are a lot of security measures you have to put in place if your objective is to hobble programmers. Even then you may find they are motivated to work around the constraints you are attempting to impose:

Just about every developer at some point has used a library or a component developed by someone else. Just about every developer at some point has also gotten frustrated with the library to the point of being willing to find the guy who decided to make a method private and talk some sense into him. Well, most of us wouldn't go that far, but it would certainly be nice to be able to change things that make our lives miserable. It's not that libraries are written by mean people; it's just that even the brightest designers are unable to foresee all the possible ways that other developers would want to use their code.

--Hacking Java Libraries

In addition to providing various access constraints, you also have to put together security mechanisms like enforcing sealed packages. Within the Java world, researchers are also proposing sealed classes and even sealed methods.

Now I'm not going to say that just because someone can hack around your mechanisms that the mechanisms are bad. I'm perfectly okay with a language that gives you nothing better than a glorified annotation, the equivalent of a post-it note on your ham sandwich saying "mine! don't touch!!"

It's useful to document your intentions, even if perfect enforcement is elusive. That being said, I'd like to close with the wise words of another: Less is More. For some people, fine-grained access control is important. But adding that feature is not free.

Given the current culture of Ruby programming, I'd say that additional access control would be expensive if you go down the rabbit hole of trying to stop people using Ruby's meta-programming strengths to hack around your restrictions.

However, lightweight mechanisms for access control and managing name spaces could be useful.

Conclusion:

As I suspected before I wrote this, I agree with more than half of Rusty's observations. Isn't this always the way? Most people have far more in common with each other than not.

One of the reasons I read Rusty's work so carefully is that he has a markedly different viewpoint than my own. It's nice to read all the nice affirmation from people who seem to value the same things I value, but there is always an opportunity to learn something profound when looking at the same things from a different perspective.

Labels: ruby

  ¶ 11:36 AM

  Finding the Signal-to-Noise Ratio in the Never-Ending Language Debate Once again the web is buzzing with one of the most boring debates ever, namely "what's the best programming language?" I will not rehash the arguments. I'll try to restrain myself to stating my position, giving my reasons, and then toss in speculation on why a certain web framework is growing like wildfire.

My position is simple: the language operating at the highest level of abstraction while not suffering from project-killing defects is the one I want to use. My algorithm is simple: throw away languages that will scuttle my project, and pick the highest level language out of those that remain. (I'm not going to discuss defects. They are a matter of taste and lead us down an unhappy path.)

I believe that programming is an idiomatic activity. We learn idioms and then apply a kind of pattern-matching to recognise problems that can be solved with an idiom we already know. Some idioms are easier to express than others in each programming language. (Does the Weak Sapir-Whorf Hypothesis apply to programming?)

Sure, all languages are Turing Complete and therefore equivalent in theory, but in practice you might find that the only way to express an idiom from Language A in Language B is to write a A->B compiler or interpreter in B.

Greenspun's Tenth Rule of Programming: "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."

Does that sound too academic? Consider this: how would you write a continuation-based framework (like Seaside) in Java?

This, incidentally, is why the language debate will never end. Programmers naturally learn and know the idioms afforded by their language. So when you say "In my language I can very easily do X and Y," the programmers using other languages always say "But nobody needs X or Y. We're busy doing Z."

So let's talk about idioms instead of so-called features like syntax. What does it mean for one language to be "higher level" than another? To have a "higher level of abstraction"? My own interpretation is simple:

One language is higher-level than another if it expresses more idioms in fewer bits than the other language. Or fewer lines of code. Or fewer symbols. There's a really simple language idiom for this: Programs in a higher-level language have a high signal to noise ratio.

For example, there are these "design patterns" that all of the COBOL^H^H^H^H^H Java programmers like to use. One of these is called Visitor: "One key advantage of using the Visitor Pattern is that adding new operations to perform upon your data structure is very easy. All you have to do is create a new Visitor and define the operation there. This is the result of the very distinct separation of variant and invariant behavior in the Visitor pattern. The invariant behaviors are represented by the data structure elements and the abstract Visitor. The variant behaviors are encapsulated in the concrete Visitors."

Got that? How many lines of code do you need in Java? Here's how you express the Java idiom of the Visitor pattern in Ruby:

concrete.each { |thingy| visitor.visit thingy }

Do you think I'm making this thing about brevity up?

Here's something I found this morning. This fellow is explaining why interviewees can use any language they like to solve a problem, provided it's black:

When I interview someone, I usually let them use the language of their choice with between C, C++, C# and Java... It's not that I have something against Ruby or other fourth generation languages, but I found that these languages work at a level of abstraction that is a little too high to give me a meaningful insight on the candidate for a forty-five minute interview. There are plenty of very interesting problems that are hard to solve even in Ruby or Python (and actually, it's quite likely this is the kind of problem that the candidate will be struggling with if she gets hired), but formulating the question and writing the solution would take several hours.

The Language of Interviews

Let me see if I can condense this: there is a class of problems that are non-trivial to solve in C# and Java but are trivial in Ruby and Python. Hot damn, I could have skipped writing this whole thing and simply posted the quote.

(By the way, do you buy that something non-trivial to solve in Ruby must necessarily require hours to explain and to write out? Neither do I. I am not bashing the post here. That point is really a very small aside. But I don't have any trouble thinking of Ruby, Python, or Lisp problems that would require only a few minutes to explain and would be appropriate for an interview.)

Now, there's some idea that you can build your own idioms in any programming language. We have various names for the technique (like procedures, subroutines, objects, modules, and macros), but the argument is that you can build up a library or framework of idioms and then you can ultimately express yourself with startling brevity.

So some state that all languages are equal because if something is difficult to express you build your new idioms into the language and presto, you have a high signal-to-noise ratio in your programs.

This argument has a major, glaring, flaw: the mechanism for building idioms in each language is an idiom itself, and it tends to be the most rigidly limiting idiom on the language. C++ is a language for defining abstract data types that look just like built in types. In SmallTalk everything is an object that belongs to a class. And so on. Let's call this the language's "meta-idiom."

The argument about idioms applies to meta-idioms. So if you want to build new idioms in a language, you need to use its meta-idioms. Some languages provide higher signal-to-noise on meta-idioms than others. Some languages make it easier to construct your own idioms than others. So even though all languages may provide some mechanism for raising the signal-to-noise ratio, not all are equal when it comes to using their mechanisms.

So, I've written that I believe that not all languages are equal. I've written that I believe that an important metric for comparing languages is the signal-to-noise ratio, as measured by the brevity of expressing idioms. Now I will conclude by revisiting the affordances argument.

Some languages make it easier to express some idioms than others. How? See the paragraph above about signal-to-noise ratio. Given that some things are easier than others in each language, wouldn't you expect that there will be a very few languages that can express an order of magnitude more idioms in an order of magnitude less code than the 'average' language?

(If you don't think so, why not? Doesn't practically everything you've ever seen operate on a power law distribution? Why should programming languages be different?)

So, I expect that some languages will do a better job of expressing a larger set of idioms than others. Now, here's the key question: does the number of idioms that a language affords matter?

I diverge from the wise men who write essays on this topic. I think it matters to me, but it is unlikely to sway anyone's decision. My simple observation is that programmers develop and use idioms that are easy to express in their language. They 'cut with the grain.'

When considering one language over another, my first consideration, naturally, is with the idioms I already know. Does the new language help? This consideration is exactly like almost any other "upgrade" consideration. When considering an upgrade, the first thing you want to do is solve an existing problem.

When I purchased an iMac for my home, I had no need for playing DVD's. So I was very close to buying the 17" model. Luckily, I purchased the 20" model so I would have more desktop for programming. I already had a 17" monitor on my development box, and it was starting to feel cramped. Now that I have the 20" iMac, I love watching DVD's on it and I'm very happy I didn't settle for the model that seemed to suit what I thought I would need.

Once you're satisfied that the upgrade meets your needs and solves a problem, you go ahead. Later on, you'll discover a whole new world of features. These grow on you, until one day you ask yourself how you ever lived without them.

And so it is with programming languages. I can write about meta-programming in Ruby and Scheme for six more posts, but if you aren't meta-programming now, my guess is that you won't switch. You simply don't think in terms of that idiom, so you perceive it to be a "nice to have," but not essential.

What will get you to move up the ladder is when someone shows you how to solve an existing problem in fewer bits. This, you can recognise. Did I say signal-to-noise? Imagine your favourite music on AM radio in your grandparents' car. Now imagine you hear it on a beautiful stereo. More signal! Less noise!

But you aren't going to switch because someone says "if you think listening to music is fantastic, just wait until you hook up a keyboard and use GarageBand to compose music..." That simply doesn't mean anything to you until you've already bought your new iMac.

So although I fervently believe that a better language will allow you to express more idioms than you are currently using, I know that you are unlikely to switch for that reason. So I'm not going to write about how cool it is that someone could add "acts_as_versioned" to the Rails framework. You probably only care about whether "acts_as_versioned" saves you a ton of boilerplate versioning data in your application.

Speaking of Rails, I'm going to conclude with my take on one reason why Rails is taking off and Seaside is not. Rails allows programmers to express the idioms they already know (relational databases, web-backed MVC, stateless event handling plus a global session store) in fewer bits.

Seaside provides a whole new idiom, continuations, that IMO is more powerful. I think you end up with an even higher signal-to-noise ratio with a Seaside app than with a Rails app. Why? Because continuations afford you a much higher degree of controller reuse.

Now, here's the catch: if you try to imagine your current application running on both Rails and on Seaside, you probably won't see much difference between the two (although they'll both be an order of magnitude better than ASP.NET). They will look the same because you designed your application with idioms that both Rails and Seaside support.

To get a big win, you'd have to rethink your application's flow and logic. You'd have to "think in Seaside." And you're not going to do that. So you pick Rails, like so many others have picked it, because it looks just like your ASP app, only all the noise has gone away. It's all signal, baby.

Now, do you see the thing here? Ruby has been around for a while, but nobody switched. Why? Because they couldn't see how its new idioms would help them. Every time a programmer considered switching from Blub to Ruby, she was presented with all these new idioms, like dynamic types. None of this meant anything to her, because they didn't appear to make the idioms she already knew more compact. No win.

But now she looks and she sees her existing web idioms, and she sees them expressed with way fewer bits, and she is suddenly prepared to learn this Ruby thing if it will let her say:

class Language < ActiveRecord::Base
has_and_belongs_to_many :idioms
end

Happy New Year!

Labels: popular, ruby

  ¶ 12:24 PM

  Repost: Closures in Ruby

(I wrote the original version of this page in 2002. I've made a few minor edits and added a comparison with Java's anonymous inner classes)

I briefly worked with a team that used Perl to implement high availability web applications. When discussing the language with the team’s technical lead, I pointed out that I was impressed with the fact that Perl implemented closures. Having written a Scheme interpreter, I considered closures a fundamental component of modelling procedures.

This led to a discussion of what was a closure, and what was it good for?

A closure encapsulates the execution of a one or more operations for side effects and/or the return of a value in the environment of the function’s definition where the closure was created.

From this definition, all functions, procedures, and methods in languages such as Java and Visual Basic are closures. When a programmer refers to a language as implementing closures, (s)he is really saying that the language permits the creation of arbitrary closures at run time. Scheme aficionados would say that languages like Perl, Lisp, and Ruby support first class closures: closures can be arbitrarily created and assigned as values to variables or returned from functions.

Since contemporary programming languages are lexically scoped, the environment of the function refers to the variables in scope at the time the function is defined. This includes temporary variables, variables that are normally created on some sort of stack and discarded when they “go out of scope.” When a closure is created, variables in scope must be preserved until the closure itself ceases to exist.

Here’s a Ruby closure demonstrating the fact that it ‘captures’ a variable in the scope of its definition:

def makeCounter
var = 0
lambda do
var +=1
end
end

c1 = makeCounter
c1.call
c1.call
c1.call

c2 = makeCounter

puts "c1 = #{c1.call}, c2 = #{c2.call}"

The two important things from this example are:

1. Although var is no longer in scope once makeCounter returns, Ruby saves it for use in the closure.

2. Each invocation of makeCounter creates a different var. The two counters do not interfere with each other.

What can you do with closures? Here’s something a bit more useful, a call-by-need thunk factory:

def delay(&procToDelay)
value = nil
return lambda do
if value.nil?
  value = procToDelay.call()
else
  value
end
end
end

def force(thunk)
thunk.call()
end

foo = delay do
puts "thinking about foo"
"fu"
end

bar = delay do
puts "thinking about bar"
"british american racing"
end

puts force foo
puts force bar
puts force foo
puts force bar

In this example, you have a simple facility for memoizing closures: they can be called repeatedly, but they only evaluate their operations once (provided the retun value is not nil). Obviously, this should not be combined with the previous example: call-by-need thunks are useful when there are no side effects of their evaluation.

Why Java's Anonymous Inner Classes do not implement closures

At first glance, an anonymous inner class in Java looks like it captures an environment. It has access to its enclosing instance's members. That looks an awful lot like the way a closure captures its environment.

But an anonymous inner class cannot access method variables or parameters. This is a crippling limitation. Consider:

interface Transformer {
    int transform (int what);
}

class TransformerConstructionKit {

public static Transformer makeMultiplier (int timesWhat) {
   return new Transformer () {
      public int transform (int what) {
          return what * timesWhat;
      }
  };
}

}

This is illegal in Java for some reason. Ok, I know what the reason is. But I don't have to like it, do I?

Labels: lispy, ruby

  ¶ 8:49 PM