Chad Perrin: SOB

20 August 2008

Ruby and Tail Call Optimization

Filed under: Geek — apotheon @ 10:06

1.8.x is the current stable version of Ruby’s reference implementation. It, like its predecessors, does not support tail call optimization for recursive functions.

A couple times in recent months I set out to write something in Ruby and found myself thinking “I should do this with a recursive function.” Then I’d rattle around inside my head, trying to figure out why I can’t remember how to write tail recursive functions in Ruby. Finally, I’d realize “Oh, damn — that’s right! Ruby doesn’t support tail call optimization.” At that point, I’d just throw away my initial idea of how to write the code and reorganize the idea to use one of Ruby’s excellent block-fed iterators instead.

Ruby’s iterators that take blocks as parameters are beautiful things to behold, for what they are. Unfortunately, they are sometimes not the ideal solution — just the necessary solution if you don’t want to drag your code to a painstaking crawl, filling up all available RAM on your system, because there’s no tail call optimization. This is one of Ruby’s biggest, ugliest warts, in my opinion: the lack of support for tail call optimization. I wants my tail call optimization.

I started searching for information on future planned support for tail call optimization tonight, and found a Weblog post talking about how bare recursion is much faster in Ruby 1.9 than Python 2.5. This is not even tail recursive code in the example. Discussion in comments there suggests that Python 2.5 does not support tail call optimization, and whether Ruby 1.9 will support tail call optimization is essentially impossible to determine from this discussion, since support for tail call optimization wouldn’t make any difference in this case and the people involved in the discussion seem confused about the matter in any case.

I’ve searched around elsewhere on the Web for this information (though not exhaustively), and still found nothing that gives me any credible sense of whether Ruby 1.9 incorporates tail call optimization.

Is there someone out there who can answer this question for me?

Sucks-Rules-O-Meter Value Comparison

Filed under: Geek — apotheon @ 02:15

(note: There’s a newer version of the meter.rb program I use to munge Sucks-Rules-O-Meter data, which I discuss in another SOB entry titled meter.rb uses a linear function now.)

You may have heard of a “sucks-rules-o-meter” before this. There are a few of them on the Web. They’re basically collections of statistics gained by scouring the Web for instances of statements that something either “sucks” or “rules” (with “rocks” as a synonym for “rules”). The Chip’s Quips link post from August 18th mentions one I don’t recall seeing before: the Operating System Sucks-Rules-O-Meter.

I decided I wanted an ordered list of the OSes, from most loved to most hated. Toward that end I cobbled together a simple stats-munging script in Ruby to produce numbers no higher than 10, and the function used to translate the numbers produces a decelerating curve, rather than a linear scale as one might expect. I guess I did it that way because I was lazy. The results, in descending order from best to worst, are:

VMS : 9.99
FreeBSD : 9.94
MacOS X : 9.88
NetBSD : 9.75
OS/2 : 9.70
MVS : 9.59
Unix : 9.56
AmigaOS : 9.43
Linux : 9.30
Solaris : 9.01
OS/400 : 9.00
NetWare : 8.66
BeOS : 8.60
MacOS Classic : 6.70
OpenBSD : 4.98
Windows : 3.87

The following is the code for the statistics translation (edit — there’s a better version in comments now):

#!/usr/bin/env ruby
 output = File.open(ARGV[0]).readlines.collect do |line|
  stats_list = line.split(',')
  value = 10 - (stats_list[1].to_f / stats_list[2].to_f)
  [stats_list[0], value]
end
 output.sort! {|a,b| a[1] <=> b[1]}

output.reverse.each do |a|
  print a[0], ' : '
  printf("%.2f\n", a[1])
end

Actually, the version I’m using uses File.open(path) instead of File.open(ARGV[0]), and has this line between the shebang line and the File.open line:

path = "/usr/home/ren/etc/meter/#{ARGV[0]}.meter"

That way, I can store a bunch of sucks-rules-o-meter statistics files in the /usr/home/ren/etc/meter directory, and specify them with a very simple argument. For instance, I have the values from the OS Sucks-Rules-O-Meter stored in a file called os.meter, within that directory, and I use this program (which I called meter.rb) to translate the OS statistics like so:

meter.rb os

The format of the data file containing the statistics from the sucks-rules-o-meter looks like this:

AmigaOS,21,37
BeOS,443,317
FreeBSD,679,12270
Linux,252000,360000
MVS,54,131
MacOS Classic,2665,807
MacOS X,32800,283440
NetBSD,159,632
NetWare,146,109
OS/2,57,188
OS/400,14,14
OpenBSD,3050,608
Solaris,1890,1916
Unix,12600,28860
VMS,145,19240
Windows,557000,90800

Basically, I just have a comma separated list, three fields per line. The first field is the name of the OS, the second is the “sucks” value from the sucks-rules-o-meter, and the third value is the “rules, rocks” value.

. . . not that anyone else with a modicum of programming capability couldn’t do this, but what the hell — if it helps anyone else, here it is. It’s available under the same terms as the rest of the text in this SOB entry (the Public Distribution License as of this writing).

Moral of the story: FreeBSD is obviously the best OS available that makes a decent general-purpose “desktop” system.

All original content Copyright Chad Perrin: Distributed under the terms of the Open Works License