Programming During Recess

Employed Again!

2010-09-25T16:58:00.001-04:00

The short story: I got a job as a Senior Rails Developer at a company named Centro in downtown Chicago starting October 4.

The Longer Story

Two years ago, I decided to leave teaching at the college level. I had spent six years "teaching" during grad school and ten years at the college level (at liberal arts schools). I found myself loving the software development that I did, and I found reasons to develop more software if I could justify it pedagogically (and sometimes even when I couldn't). Eventually I decided that a career change was in order.

I had fallen in love with agile software development—Extreme Programming in particular and Test-Driven Development especially. My programming skills were best in Java and Ruby on Rails. While my Java skills are quite good, I'm not familiar with the common frameworks that Java shops love to use. So my job search has focused on Ruby on Rails jobs since I've worked on two such projects that have gone into production, and it was easiest to demonstrate my skills. Plus, I really enjoy programming in Ruby with the Rails framework.

I few weeks ago I came across a job advert on Github entitled "'Rock Stars' and 'Ninjas' Need Not Apply":

Centro’s technology team is building a web application for streamlining digital media placement. We are seeking talented developers with experience working with Javascript, Coffeescript, SproutCore, JQuery, Ruby, Sinatra, Rails, MongoDB and Postgres. We’re not throwing those in there so we show up in more searches, we actually use all of it in varying amounts.
If you know SmallTalk or Lisp we’d probably also like to talk to you. Folks who send resumes formatted with LaTeX are guaranteed a phone screen.
Centro is a great company to work for — we were listed by Crain’s as one of the best places to work in Chicago. We hire people with zeal for writing excellent code.
If you’ve got something awesome up on GitHub we’d love to have a look.

Those of you who know me and recognize the tech-speak understand why this advert made me very happy. First paragraph: they use a lot of cool technologies and actively look to use others; that's my kind of company! Second paragraph: I got the guaranteed phone screen without trying, and my Scheme experience in grad school counted for LISP experience. Third paragraph: Cool. Fourth paragraph: you can see my resume in LaTeX form on Github—and a lot of other projects I've worked on (with varying degrees of awesomeness).

After a phone screen and a day-long on-site interview, they recognized how well I fit what they are looking for; so, starting on October 4, I will be working as a Senior Rails Developer at Centro in downtown Chicago.

Centro serves as a middleman between advertisers and websites. I could try to explain specifically what they do, but if a picture is worth a thousand words, a video is worth a million: check out the demo video for Transis. Transis is only a fraction of the software that's being worked on at Centro, but it gives a good idea for what Centro does and (at a meta level) the quality of their work.

I'm really looking forward to my new job and new career.

Funny Code Comments

2010-09-18T12:16:00.001-04:00

"Top funny source code comments" by Vinícius Krolow at cObaia.net is worth your time. There are some straight up jokes (like the comments about recursion) and some about the code (e.g., "They made me write it, against my will.").

I'm Male and 26--35 Years Old, and I Write Happy

2010-09-10T18:15:00.001-04:00

Apparently, I write like I'm male and 26--35 years old. A bit off on the age (by five years, let's say). My writing is also "personal and happy"; if you say so...

I discovered these wonderful facts from URL AI (see my blog's report from URL AI).

Tar Archive Problems Upgrading RVM to 1.0.2

2010-09-04T12:09:00.001-04:00

When I tried to upgrade RVM yesterday and this morning, I got this result:

$ rvm update

rvm 1.0.1 by Wayne E. Seguin (wayneeseguin@gmail.com) [http://rvm.beginrescueend.com/]

info: fetching rvm-1.0.2.tar.gz

info: Extracting rvm-1.0.2.tar.gz ...

error: Error running 'gunzip "/Users/jdfrens/.rvm/archives/rvm-1.0.2.tar.gz" | tar xf - -C /Users/jdfrens/.rvm/src', please check /Users/jdfrens/.rvm/log/extract*.log

info: Installing rvm-1.0.2...

error: Error running 'builtin cd /Users/jdfrens/.rvm/src/rvm-1.0.2/ ; ./install', please check /Users/jdfrens/.rvm/log/install*.log

And .rvm/log/extract.error.log contains entries like this:

[2010-09-03 10:06:05] gunzip "/Users/jdfrens/.rvm/archives/rvm-1.0.2.tar.gz" | tar xf - -C /Users/jdfrens/.rvm/src
tar: This does not look like a tar archive
tar: Exiting with failure status due to previous errors

Thinking it was maybe the gnuzip from MacPorts causing the problem, I renamed it to use the system-wide gnuzip from Apple. Didn't help. So I renamed the MacPorts version back to gnuzip.

RVM had been updated in my system-wide Ruby (from MacPorts); this is how I knew 1.0.2. was out. So I ran /opt/local/bin/rvm-install hoping that it would simply update my RVM. It worked!

Strangely, it seems to have fixed the update process itself:

$ rvm reload      # to load the version from the rvm-install update
$ rvm version

rvm 1.0.2 by Wayne E. Seguin (wayneeseguin@gmail.com) [http://rvm.beginrescueend.com/]

$ rvm update

rvm 1.0.2 by Wayne E. Seguin (wayneeseguin@gmail.com) [http://rvm.beginrescueend.com/]


info: fetching rvm-1.0.2.tar.gz

info: Extracting rvm-1.0.2.tar.gz ...

info: Installing rvm-1.0.2...
$ rvm reload
$

Just in case this is helpful to someone else out there...

LaTeX Anecdote #2: My Dissertation

2010-09-03T20:34:00.001-04:00

This is a continuation of my series on LaTeX (introduction and anecdote #1). Much of this particular article is based on a rant I had on my webpages at Calvin.

One Minute LaTeX

I used emacs and LaTeX to write my dissertation. There's an emacs package called AUCTeX that allowed me to hit two keys while editing my LaTeX document, and emacs would process my document. The package is smart enough to know when to run LaTeX multiple times to generate cross-references as well as when and how to run BibTeX.

At any time, I could process and view my dissertation within a minute. Complete with cross references (e.g., "See Figure 5.") and a very well formatted bibliography. Formatted as required by Indiana University.

A minute.

Twelve Hour Word

Sue, a friend of mine in the Chemistry Department at Indiana University, helped a friend of hers print out her dissertation. This friend had written the dissertation in Microsoft Word, each chapter in a different file. It included pictures and graphs written with other commercial software. It took them twelve hours to get the dissertation to look right.

Twelve hours.

When Sue went to print her dissertation a few months later, she planned for twelve hours, but it took her only eight hours.

Yeah... only eight hours! That's insane! Who would, given a choice, pick a program that demands you fuss around with it for eight hours to get your document to print correctly?

What about Today?

Sue and her colleague printed their dissertations with MS Word between 1996 and 1998. I wonder if they could print their dissertations today with MS Word. I seriously doubt they would look right.

I finished my dissertation in 2002, and I haven't really tried to regenerate it from the original source files since then. But it seemed dishonest of me to rant like this without giving it a try. So I tried.

Fifteen minutes.

Why so long?

I had to remember the latex and bibtext and dvips commands I needed. This was because I've been using makefiles lately to process my LaTeX files, but my dissertation was always processed with AUCTeX, not makefiles. This was actually pretty easy for me to figure out.
I had to convert some figures into EPS (encapsulated PostScript). I used xfig to create figures in my dissertation, and xfig has its own format which LaTeX doesn't recognize. I wasn't exactly eager to convert the 32 figures by hand, so I spent some time finding some way to automate the process. I discovered fig2dev which did a great job.
I originally used a tweaked BibTeX format for my bibliography. (My advisor was very picky about bibliographies and their formats.) It appears I don't have that style file anymore, so I switched to a standard format. But then it also appears I don't have BibTeX set up quite right on my system, but I found a way to get it to work.

I could create a makefile to handle the latex and bibtex and other commands and to process the xfig files with fig2dev. I could spend another 15 minutes or so to get BibTeX to work the way it should. And I'd be exactly where I was when I was working on my dissertation: a minute to generate a perfect PDF of my dissertation.

Next Time

I will talk about LaTeX Beamer and creating presentations.

LaTeX Anecdote #1: The Large, Multi-Author Document

2010-08-31T20:16:00.001-04:00

This is a continuation of my series on LaTeX.

I Hate MS Word

One of the biggest frustrations I ever experienced was putting together a rather large document (over 100 pages) for the Computer Science Department when I was at Calvin College. The document had to follow a particular format, and we were given a starter Word document. I really wanted to turn it into LaTeX, but most of my colleagues were Word users. Plus, the college administration would prefer Word documents, not PDFs. It seemed easier to go with Word.

Over the course of a couple of weeks, my colleagues would send me contributions to this document. Each contribution was formatted a little differently; and as I added those documents to the master document, those formatting changes affected the format of my master document. Of course, most of the contributions came in the last week and last day before it was due, and so I spent a very late night trying to get the document to look halfway decent and consistent. It didn't go very well, and I ended up taking my frustration out on my office door by kicking it forcefully a few times. Fortunately, I didn't break the door, just scuffed it up pretty seriously. And in the end, the formatting on the document was rather inconsistent, but not grossly so. It was only ever good enough.

Part of the problem was the amount of time spent on integrating the documents, but my door-kicking problem was the mind-numbing frustration trying to get the document to behave. Word was usually unhelpful or too helpful with it's own corrections.

Should Have Used LaTeX

Okay, so this post is really a "I frakin' hate MS Word!" Word failed me, and I didn't try the document in LaTeX. I thought about converting the document into LaTeX many time, especially when I took my frustration out on my office door, but I didn't.

What would it have gained me? First, it would have had a consistent look, and I could have a rather bland consistent look without too much trouble. Second, to spruce it up (highlight the structure of the document) would have taken very little work: add some LaTeX environments and style them (tweak the font faces and sizes perhaps).

Most of the document was plain text, and converting from Word into text wouldn't have been difficult at all. As I recall, there were few (if any images), but they're easy to include in a LaTeX document. There were definitely a few tables, and they might have been harder to convert, but there are compromises that would result in good-looking tables without too much difficulty.

Next Time

In my next entry on this topic, I have an anecdote when LaTeX did win.

Typesetting with LaTeX

2010-08-30T17:44:00.001-04:00

When I taught at Calvin College, I had some web pages where I discussed my love of LaTeX (and my hatred of Microsoft Word). Since those web pages are no more and since the material would work better on a blog anyway, I'm spreading my love here.

In this blog post, I'm going to talk very briefly about what LaTeX is. In future blog posts, I'll give some anecdotes why I love LaTeX so much (and hate MS Word), and I'll talk about using LaTeX Beamer to replace PowerPoint.

Me and LaTeX

I started using TeX for writing documents (mostly for a topology course) when I was a senior in college (around 1992). When I started grad school, I moved on to LaTeX and used it for nearly all of my written assignments. As a teacher, I used it for writing all my tests and printed assignments for my students. As a researcher, I wrote several conference papers and my dissertation with LaTeX. I also used LaTeX for classroom and conference presentations.

What Is LaTeX?

These webpages came to my attention recently:

"The Beauty of LaTeX" by Dario Taraborelli. This is an awesome article about the technical typesetting details that LaTeX does just right.
"LaTeX isn't for everyone, but it could be for you" by Andy Roberts. Roberts provides a good list of reasons to use LaTeX and includes some links to some tutorials.

In short, LaTeX is TeX with more features and defaults. A LaTeX document is a text document (entered into a text editor). The LaTeX text file is processed by the LaTeX executable into a DVI, PostScript, or (these days) PDF file.

I'll date myself with this comparison, but LaTeX (and TeX) is like writing a document with Word Perfect's Reveal Codes permanently turned on. A more modern equivalent would be raw HTML.

But better than Reveal Codes or raw HTML, LaTeX is really a programming language, and so you have the power of abstraction to make writing your document easier.

Additionally, LaTeX is based on logical formatting (which I've blogged about before). The idea is that you describe the structure (the logical format) of your document in the document, and then specify the look (the physical format) separately.

Examples

Roberts provides this example:

% hello.tex - Hello world Latex example
\documentclass{article}

\begin{document}
Hello World!
\end{document}

Where does the document begin? Where does it end? LaTeX's logical formatting tells exactly how to answer these questions. Its abstraction mechanism provides the definitions (size of margins, type of font, etc.) for the document environment.

Here's another example (my own):

\documentclass{article}

\title{Artists Queued in My iTunes DJ}
\author{Jeremy D. Frens}

\begin{document}
\maketitle
\begin{itemize}
  \item Sufjan Stevens
  \item Glenn Gould
  \item Devo
  \item The Black Keys
\end{itemize}
\end{document}

What's the title of the document? Who wrote it? If I tell you that itemize is just LaTeX's name for a bulleted list, what's the content of the document?

There are properties of itemized lists that can be easily controlled globally. How would you change all of the bulleted lists in a Word document? Find each one, and tweak it. In LaTeX, you change some settings before you begin the document (where I set the title and author). If you wanted to change just one list, you can do that, too. If you want to change some lists but not others, you can create your own abstractions.

I have a lot of abstractions in my curriculum vitae. (You can find my resume in that same repository, but it's rather messy.) The intent of each section is very clear from the structure of that document, and the logical formatting of that structure comes from the vita document class that I access at the very beginning of the document.

Next Time

Next time I'll describe my experience trying to write a lengthy document with multiple authors with MS Word.

Upgrading to Rails 3 and RSpec 2, Part 5: Cucumber

2010-08-27T20:05:00.002-04:00

My final part of my series on upgrading a Rails app to Rails 3 and RSpec 2 describes some of the issues encountered when upgrading Cucumber.

I upgraded to cucumber 0.8.5 and cucumber-rails 0.3.2.

Goodbye, Webrat. Hello, Capybara.

On a from-scratch Rails 3 app, I already knew this meant switching from webrat to capybara. So in my upgrade, I found it best to run this:

ruby script/rails generate cucumber:install --rspec --capybara

I replaced what should be safe to replace (e.g., features/step_definitions/web_steps.rb) and did a hand merge on others (e.g., paths.rb and env.rb in features/support). This wasn't difficult.

I'm still getting used to capybara, and my sample app probably isn't the best place to learn about it (at least not yet). I got hooked on selecting with XPaths, and later I discovered the ways to use CSS selectors which would have made the webrat-to-capybara translation much easier.

Rename Method

In the step definitions, the most significant change is a name change: page instead of response. Of course, cucumber is happy to complain about this for you, although a project-wide search-and-replace might speed up the refactoring. (You may actually want to restrict the search to just the features folder.)

I like the change. "Page" reflects a bit better what's being testing in a Cucumber scenario.

Date and Time Selection

One other painful change involves selecting dates and times.

Rails has helper methods for forms: form.datetime_select and form.date_select. This generates several select inputs (with the select HTML element) for the various components of the date and/or time. For example, form.date_select generates three select inputs for the year, month, and day. They get goofy (but easily parsed) names like event[start_1i] for the year component of a start attribute of an event object.

Old versions of Cucumber and webrat provided a web_steps.rb with a step that allowed me to select dates and times generated with these form helpers. The new Cucumber and capybara do not.

After some advice discovered through a Google search, I ended up with a satisfactory steps for selecting my date and datetime. The result of my Google search is referenced at the top of that file, and it provides a much more general solution (although it didn't quite work for me). I tailored the code to my domain, but generalizing it wouldn't be too difficult.

It works okay, but I suspect that I'll be changing the way I enter dates and times. HTML 5 has data and time input fields. While only Opera 9.0 support these input types, other browsers default to a textfield. For those other browsers for the time being, I can use a JavaScript data/time selector for the fancy input. Either way, for testing purposes it would suffice to send a string for the input field. (See the relevant section of the HTML 5 specification if you don't believe me.)

Next Time

Well, I don't have a next time planned. Of course, I'm still working on my app, and perhaps something Rails 2-to-3 might come up, but until then, this is it for my series. I have a couple other blog articles queued up for me to blog on, so I'll be turning my attention there next week.

Upgrading to Rails 3 and RSpec 2, Part 4b: Recursive Rendering

2010-08-20T15:08:00.001-04:00

Today's "upgrading to RSpec 2 for Rails 3" episode is a direct continuation from the previous episode on upgrading the view specs. That post got quite long, and this part seemed the best to pull out into its own post.

The topic of discussion is calling render recursively.

Recursive Renders

"Extract partial" is essentially the view's version of "Extract method" in a model or controller. I pull out part of the view into a partial view so that the views are simpler, easier to reason about, and easier to test.

For example, the app that I upgraded displays the details of a professor. There's a lot of variation that goes into this: how many schools did they go to? do they have research interests listed in the database? do they have an office phone (that they want listed)? do they have a special status (e.g., "department chair")? etc. I don't want to test these variations all in one show.html.erb_spec.rb. Instead, I call a bunch of partials (slightly modified here):

<div id="full_name_header">
  <h1><%= @user.full_name %></h1>
</div>
<%= render 'pages/image' %>
<%= render 'job_title' %>
<%= render 'contact_information' %>
<%= render 'education' %>
<%= render 'interests' %>
<%= render 'profile' %>

The partials can use the data in @user, so there's no need to pass in any local variables.

To test this show.html.erb, I only need to make sure that the partials are being rendered:

view.should_receive(:render).with('job_title').and_return("job title")
view.should_receive(:render).with('pages/image').and_return("image")
view.should_receive(:render).with('contact_information').and_return("contact")
view.should_receive(:render).with('education').and_return("education")
view.should_receive(:render).with('interests').and_return("interests")
view.should_receive(:render).with('profile').and_return("profile")

In specs for _profile.html.erb, I can make sure that a profile section is generated (complete with a header) when the user has a profile, but generates nothing (not even a header) when @user.profile is blank.

This creates a lot more files, but I find that a fair tradeoff for the simpler code and simpler tests.

It's Broken!

However, mocking out render is hopelessly broken in RSpec 2. I understand why it's broken, and it's a really good reason, but I struggled with a solution.

It's broken because I have to call render in order to execute the test.

it "should render" do
  view.should_receive(:render).with("some_partial").and_return("some result")
  render
end

I immediately get an expectation error: expected a call to render with a bunch of arguments (i.e., :partial => "some_partial"), but got a call to render with no arguments. Yes, the call right in the spec there! It's been mocked out!!!

Earlier versions of RSpec would actually help us mock out the recursive calls to render and still let us make the call at the heart of the spec. Unfortunately, this required knowledge and monkey patching of the Rails internals, and when those internals changed, RSpec would have to be updated. I completely understand why the RSpec developers don't want to do this any more, so I'm not faulting them.

But I am struggling for a satisfying solution.

Solution #1: Helper Methods

On a Rails-3-from-scratch project, I discovered that many of these "Extract partials" were really better implemented as "Extract into helper method". I'm then forced to pick a descriptive name which can easily be mocked.

So mocking becomes easy without any awkward changes:

user = mock_model(User)
assign(:user, user)
view.should_receive(:render_profile).with(user).and_return("profile")
render

The view just needs to call render_profile(@user) to meet this expectation.

render_profile itself lives in a helper module, and its specs live in the test file for that helper module.

One tip: pass in your full object to the helper method, not a component object. For example, render_profile(@user), notrender_profile(@user.profile). If I pass in the profile, I have to stub or mock that attribute in the view test; given enough helper methods for many attributes, all this mocking becomes tedious. I haven't found this to be a problem in the helper methods.

Solution #2: Create an Alias

When I really want to call render recursively (because there's a lot to render or because I'm already doing it that way), I defined this helper in app/helpers/application_helper.rb:

def render2(*args)
  render(*args)
end

For the record: I loathe this name. I tried render_rec for "render recursive", but that's worse.

All this does is set up render2 as an alias for render. (You can't use alias because render isn't always declared, like when you run your non-view specs.)

But now I can set these expectations:

view.should_receive(:render2).with('job_title').and_return("job title")
view.should_receive(:render2).with('pages/image').and_return("image")
view.should_receive(:render2).with('contact_information').and_return("contact")
view.should_receive(:render2).with('education').and_return("education")
view.should_receive(:render2).with('interests').and_return("interests")
view.should_receive(:render2).with('profile').and_return("profile")

And change the view to use render2 to satisfy these expectations.

As I mentioned, I really hate the name render2. But otherwise I find this to be a satisfactory solution, although I suspect that relying more on helper methods might be an even better solution.

Next Time

I upgrade Cucumber features and scenarios.

Upgrading to Rails 3 and RSpec 2, Part 4a: Views

2010-08-19T19:26:00.001-04:00

I continue my series on upgrading the RSpec examples for a Rails 3 app. Today it's about testing the views. (Previously: an introduction, controller specs, and router specs.) I have a lot to say about RSpec 2 and testing views, so I've had to split this up into two separate posts.

Many developers have strong opinions against testing views; other like to test them with their controllers. I like testing views separate from controllers, and I try to test the rendered content, not the rendered look. For example, here are some questions my specs try to answer: does the title of the book actually appear in the output? is the title in an h1 header? does the book's authors appear? are the authors listed in the correct order?

In this post, I'll talk about these topics:

how to refer to the template and the response in your spec (brand new names!);
how to assign values to instance variables for the view (big change!);
how to render your template DRYly (with and without local variables); and
how to mock new records.

In my next post, I'll talk about recursive rendering.

New Handles

What you knew as template and response are now view and rendered, respectively:

it "should have a login link when no current user" do
  view.should_receive(:current_user).and_return(nil)
  render
  rendered.should have_selector("a", :href => login_path, :content => "log in")
end

A project-wide search-and-replace is a great way to upgrade. Some tips:

Search for "template." and "response." (with a real period, not a regex period!) as your search terms.
Include the period on the replacement text, "view." and "rendered.".
Use response in your controller, so be selective in what you change!

I'm not sure why this change was made, but the new names make a bit more sense to me.

Completely New Way to Assign Instance Variables

Views make heavy use of instance variables set in the controller. RSpec 1.x had an assigns hash that you set before rendering:

# old RSpec 1.x code!
it "should display a title" do
  book = mock_model(Book, :title => "Dune")
  assigns[:book] = book
  render
  response.should have_selector("h1", :content => "Dune")
end

This simulates assigning a (mocked) book to the @book variable in the view template. In Rspec 2, there's an assign(variable, value) method:

it "should display a title" do
  book = mock_model(Book, :title => "Dune")
  assign(:book, book)
  render
  rendered.should have_selector("h1", :content => "Dune")
end

I'm not sure what the benefit of this change is, but it's a change you can't avoid. The view and rendered changes are deprecations, but this is a show-stopper. You'll have to change your assigned variables before the specs will run. Unfortunately, a global search could help you find the code that must change, but a global replace will only help with part of the change.

Render Without an Argument

If you specify a full path to the template in the description of the describe block, you do not have to repeat it when you render the view for the spec. For example:

describe "books/show.html.erb" do
  it "should render" do
    render    # renders "book/show.html.erb"
  end
end

As a case of "Don't Repeat Yourself", this is a win. Consider multiple it blocks, each one rendering the same template. It saves just a little bit of typing and reduces the risk of typing one of them wrong. Better yet, if you were to refactor the code: rename the template or the controller, you have to change just the one description, not each call to render.

This may be an old feature of RSpec that I stumbled on. I had been using abbreviated names for template like "show" or "books/show". When I did my Internet searches to find out why these weren't working, I discovered canonical examples which used render without arguments.

Render Without an Argument with Locals

Some views have local variables passed to them:

# in a controller
render "show", :locals => { :foo => value_for_foo }

To test this, I mock out foo as a method call on the view:

it "should use the value in foo" do
  view.should_receive(:foo).any_number_of_times.and_return("rendered foo")
  render
  rendered.should contain("rendered foo")
end

If I don't mock the local variable this way, I have to specify the template and the local variable in the call to render, but as I pointed out in the previous section, I don't want to mention the template.

There's an ambiguity in Ruby when an identifier seems to be used as a local variable: it could be a local variable, or it could actually be a method call to a method with no arguments. (I've blogged about this before.) What's really wacky here is that the ambiguity persists throughout the app's execution up until each time foo is evaluated. It's a bit complicated to fully explain how this ambiguity is pulled off in Ruby, but suffice it to say that mocking out the local variable this way works just fine.

Just keep in mind that local variables are often called more than once, so using any_number_of_times or at_least(:once) is strongly advised.

The more I think about it, the more this should be abstracted out into a helper for the spec_helper file:

def local_variable(variable, value)
  view.should_receive(variable).any_number_of_times.and_return(value)
end
...
local_variable(:foo, "rendered foo")

It's a bit more expressive.

New Records

When I render a form, I want to make sure my submission button indicates whether submitting the form will create new data ("Create Book") or update existing data ("Update Book"). I also wanted to make sure that the right RESTful method was being used (POST or PUT). I used to stub new_record? on my mock objects as appropriate. That does not seem to be sufficient now, but there's an easy solution.

First, a mocked model is not new by default. So objects that need to be updated are really easy to create!

Second, new objects are also easy to create when you know the right incantation:

book = mock_model(Book).as_new_record

This method might be old, but I was forced to discover it because my old tricks weren't working with RSpec 2.

It's worth pointing out that labeling the button with "Create" or "Update" is handled by Rails 3, so I'm slipping into testing Rails, not really my code. But there are other situations where have a mocked model which thinks it's a new record is important.

Next Time...

Next time I'll look at the problem of mocking out recursive calls to render.

Parallel Programming the Functional Way

2010-08-18T16:56:00.001-04:00

I've got two presentations to recommend. The first one I watched a few weeks ago, and it's an interesting watch to see how parallelism can be done in Haskell pretty easily. The second presentation was cited by the first, and it's absolutely awesome—and not just because it validates my dissertation! I'm going to elaborate on the second presentation because it is a much more general conclusion and because it relates so well to the work that I've done.

Multicore Programming in Haskell

"Multicore Programming in Haskell" (PDF of slides) by Simon Marlow describes the how-to and how-done of parallel programming in Haskell. As someone who's dabbled in Haskell programming in the past, this talk made me very interested in trying some more Haskell coding.

You can get a good idea of the content from the slides, but the talk itself is quite good. I'd recommend it to someone familiar or just curious about Haskell. If you're doing parallel programming you should be interested in Haskell, and this talk will help you see why.

Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful

Marlow cited "Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful" (PDF of slides) by Guy Steele in his talk. Again, you can get the feel for the content from the slides, but some of the slides are packed with very dense content (both code and prose). The pacing of the talk helped me to digest the content better, and Guy Steele is just a great speaker, too.

Steele's concluding slide is this: "Get rid of cons!" For those unfamiliar with LISP, this is translated as "Get rid of linked lists!" For parallelism, we want balanced divide-and-conquer structures, not one-element-and-rest-of-structure. For example, to compute the length of a list with linked lists, one would write this:

length [] = 0
length (x : xs) = 1 + length xs

The expression x:xs represents a linked-list node with the value x as the value and xs pointing to the rest of the list. In LISP, we call this a cons box (: is the cons operator in Haskell).

We're forced to compute the length of the list element by element through the list, one after the other. There's no parallelizing this.

But if we change the representation a bit:

length EmptyList = 0
length (SingletonList x) = 1
length (BinaryList left right) = length left + length right

We worry about three cases: empty, singleton, and recursive split. In this case, the two recursive calls to length could be done in parallel. Further recursive calls can also be done in parallel. If the splitting is done evenly, the height of the parallel execution tree drops from linear to logarithmic.

My dissertation research involved the recursive decomposition of matrices into quadtrees. A one dimensional structure (a linked list or array) turns into a binary tree with two branches at the recursive case; a two dimensional structure (a matrix, a two-dimensional array) has a four-way branching in the recursive case.

What I found interesting is that my research reenforced Steele's observations and conclusions. Almost as an aside, he mentioned that this recursive decomposition results in three cases: an empty case, a singleton case, and a recursive case. Quadtrees have a zero matrix, a scalar matrix, and a recursive quadtree. Observation reenforced.

I can also reenforce Steele's engineering optimization on Slide 73:

Optimized representations of singleton lists. My singleton case was a scalar value (a double-precision floating-point number) in an array. That's about as optimized as one can get!
Use tree branching factors larger than 2. It was really useful for me to split my matrices into four subtrees (although any power of four would work). Larger branching factors means more parallelism earlier in the computation but at a cost of extra complexity. (It would be interesting to see if the extra complexity could be handle by a program transformation by a compiler or interpreter.)
Use self-balancing trees (2-3, red-black, ﬁnger trees, . . . ). I sort of had this. Matrices would get padded out with zeros to make the number of rows and columns a power of two, then the quadtree splitting could be carried out very nicely. There was never more than a logarithmic number of zeros to deal with, so they didn't cause too much of a problem overall, but some quadrants had more zeros than others (at the top of the representation). The extra zeros made balancing the parallel dispatches quite interesting, but once an algorithm had a dense quadrant, it could really crank out computations in parallel.
Use sequential techniques near the leaves. Yes!!!! This is to keep the processors pipeline as busy as possible with real computations (not computations for navigating the data structure). My advisor worked a lot on this. He unfolded and re-rolled the singleton base cases, turning the general recursion into for loops and switch statements. (We didn't consider this cheating since compilers should be able to make these transformations for us.) It helped us keep our FLOPS level up.
Have arrays at the leaves. Decide dynamically whether to process them sequentially or by parallel recursive subdivision. This is an issue of contiguous memory, and Steele is absolutely right. His conc boxes (which are just re-interpreted cons boxes) is a linked structure, and this can kill cache coherency when you get to the leaves. In my research, I worked with a contiguous chunk of memory and superimposed a tree structure above it, so I already had arrays in contiguous memory at the leaves.
When iterating over an integer range, decide dynamically whether to process it sequentially or by parallel recursive subdivision. Never applied to me, but it's wise council.

Overall, this is a great talk, and if you're not using data structures that support parallelism with recursive decomposition (and you think you're doing parallel programming), you have to give this approach a try. This talk may not convince you (especially because the examples get so dense in the end), but it'll give you a place to start.

And if the Fortress code examples scare you, meditate on them for a while, and come back to them later.

Use Prerelease Mongrel with Rails 3 Release Candidate and Ruby 1.9.2

2010-08-16T15:03:00.001-04:00

The official, stable release of Mongrel seems to work fine with Rails 3 and Ruby 1.8.7. On one of my projects, I'm using Rails 3 with Ruby 1.9.2, and then you need the prerelease of Mongrel:

gem "mongrel", ">= 1.2.0.pre2"

For Google searches, here are the errors I got without the prerelease version:

Installing mongrel (1.1.5) with native extensions /Users/jdfrens/.rvm/rubies/ruby-1.9.2-rc2/lib/ruby/1.9.1/rubygems/installer.rb:483:in `rescue in block in build_extensions': ERROR: Failed to build gem native extension. (Gem::Installer::ExtensionBuildError)

/Users/jdfrens/.rvm/rubies/ruby-1.9.2-rc2/bin/ruby extconf.rb 
checking for main() in -lc... yes
creating Makefile

make
gcc -I. -I/Users/jdfrens/.rvm/rubies/ruby-1.9.2-rc2/include/ruby-1.9.1/x86_64-darwin10.4.0 -I/Users/jdfrens/.rvm/rubies/ruby-1.9.2-rc2/include/ruby-1.9.1/ruby/backward -I/Users/jdfrens/.rvm/rubies/ruby-1.9.2-rc2/include/ruby-1.9.1 -I. -D_XOPEN_SOURCE -D_DARWIN_C_SOURCE   -fno-common -O3 -ggdb -Wextra -Wno-unused-parameter -Wno-parentheses -Wpointer-arith -Wwrite-strings -Wno-missing-field-initializers -Wshorten-64-to-32 -Wno-long-long  -fno-common -pipe  -o http11.o -c http11.c
http11.c: In function ‘http_field’:
http11.c:70: warning: format not a string literal and no format arguments
http11.c:71: warning: format not a string literal and no format arguments
http11.c:77: error: ‘struct RString’ has no member named ‘ptr’
http11.c:77: error: ‘struct RString’ has no member named ‘len’
http11.c:77: warning: left-hand operand of comma expression has no effect
http11.c: In function ‘request_uri’:
http11.c:102: warning: format not a string literal and no format arguments
http11.c: In function ‘fragment’:
http11.c:113: warning: format not a string literal and no format arguments
http11.c: In function ‘request_path’:
http11.c:124: warning: format not a string literal and no format arguments
http11.c: In function ‘query_string’:
http11.c:135: warning: format not a string literal and no format arguments
http11.c: In function ‘header_done’:
http11.c:172: error: ‘struct RString’ has no member named ‘ptr’
http11.c:174: error: ‘struct RString’ has no member named ‘ptr’
http11.c:176: error: ‘struct RString’ has no member named ‘ptr’
http11.c:177: error: ‘struct RString’ has no member named ‘len’
http11.c: In function ‘HttpParser_execute’:
http11.c:298: error: ‘struct RString’ has no member named ‘ptr’
http11.c:299: error: ‘struct RString’ has no member named ‘len’
http11.c:307: warning: format not a string literal and no format arguments
make: *** [http11.o] Error 1

Upgrading to Rails 3 and RSpec 2, Part 3: Router

2010-08-15T21:20:00.001-04:00

I my continuing series about upgrading RSpec for Rails 3 (previously: "Part 1: Introduction" and "Part 2: Controllers"). Today, it's testing my routes.

But first, I finally pushed my rails3 branch to github. You can easily compare the last Rails 2 version and the first useful Rails 3 version with Github's awesome comparison view.

The New DSL

It's awesome. I find it much more expressive. Here are some resources if to help you with the upgrade on the Rails side:

"The Rails 3 Router: Rack It Up" by Yehuda Katz
"The Lowdown on Routes in Rails 3" by Rizwan Reza.
"Rails Routing from the Outside In" from the RailsGuides.

I used the second and third resources a lot in my upgrade. I include the first resource because it got me excited about the changes in the first place.

`:as` versus `:path`

For some reason, I didn't find the difference between these two settings as clear as I would have liked from those resources.

:path changes the path used to access a resource. For example:

resources :pages, :path => "p"

The path to access the "pages" resource is /p, not /pages. I test this with specs like this:

it "should recognize page routes" do
  { :get => "/p/foo" }.should route_to(
      :controller => "pages", 
      :action => "show", 
      :id => 'foo')
end

it "should use /p abbreviation path to a page" do
  page = Factory.build(:page, :identifier => "foobar")
  page_path(page).should == "/p/foobar"
end

:as changes the name by which you refer to the resource (or route) in your app. I use this only for some simple routes:

match '/users/login' => 'users#login', :as => :login
match '/users/logout' => 'users#logout', :as => :logout

This results in helpers like login_path and logout_url.

Testing a Route

The old techniques for testing a route with RSpec seem to be gone. Instead, they should use a route_to matcher as seen in the first spec above.

In addition to testing my :path setting, I also recognize pages by their identifier, not the id number that's assigned by the database. My RSpec spec demonstrates and ensures these features.

I don't actually test every route since it begins to feel like testing Rails instead of testing my app. This spec is good because I've overridden some defaults.

Testing `_url` and `_path` Helpers

Because of the changes I made to the defaults for routing "pages", I also wanted to test the pages_path and page_path(@page) helper methods as seen in the second spec above.

I discovered that the new standard for testing routes is to put the spec file(s) in a spec/routing subdirectory. When I did this, I got "page_path method undefined" errors. So I moved my tests back to the spec/controllers folder. I don't have that many routes to check, so moving them to another folders isn't so urgent to me.

Next Time...

Next time we'll look at the significant and frustrating changes to testing views.

Upgrading to Rails 3 and RSpec 2, Part 2: Controllers

2010-08-12T18:17:00.001-04:00

In Part 1, I pointed out some resources to upgrade a Rails app to Rails 3. In this part, I'm going to talk about the some of the changes I had to make to my controllers and their specs.

One important suggestion: run just the controller specs with rake spec:controllers.

Arel in Controllers

I still have to go through and switch to Arel (or is it "ARel"?). I don't anticipate problems with this. Check out these resources if you'd like to know more:

"Active Record Query Interface 3.0" by Pratik Naik at the "has_many :bugs, :through => :rails" blog.
"Active Record Queries in Rails 3" a Railscast by Ryan Bates.
"Advanced Queries in Rails 3" another Railscast from Ryan Bates.

Since I use a lot of mocking in my controllers, I imagine I'll have to make more than a few changes, but I also anticipate they'll all be straightforward. (I'll be sure to let you know if they aren't.)

Integer Params in Controller Specs

To serve up the appropriate object, an action like show or edit has you finding the object by id:

it "should find image to edit" do
  image = mock_model(Image)
  Image.should_receive(:find).with(image.id).and_return(image)
  get :edit, { :id => image.id }, user_session(:edit)
  assigns[:image].should == image
end

The image.id (an Integer) in the Image.find expectation used to be image.id.to_s because Rails (or the RSpec framework) would massage the data values in the params hash into strings. It appears that this data conversion doesn't happen any more. It works fine the way I have it above; it also works if both calls to image.id are changed to image.id.to_s; it fails if only one is changed.

I'm still debating what's better. Using strings seems more honest, but is it really necessary? I'm probably going to keep it simple without the to_s conversion, but if this causes problems later on, I'm willing to switch.

Params in Unhappy-Path Tests

In the spec above, the call to user_session(:edit) is a helper method to set up a session with an editor logged in. Only editors get to edit images. But what if some random guest tries editing an image? I make sure the app redirects to the login page:

it "should redirect when not logged in" do
  get :edit, { :id => 1234 }
  response.should redirect_to(login_path)
end

If you are using only RESTful routes, then you must to include an :id entry in the params hash. The :id is used by the router to find the appropriate route.

If you include the default route (with or without RESTful routes), then the router will route get :edit to the right place even without an :id. Since the params[:id] is ignored when you're not logged in, it seemed like a nice simplification.

I started my app before RESTful routes were a Thing, and apparently when I switched to RESTful routes, I didn't drop the default route until now, and this issue bit me. It's not hard to fix: include the :id even when params[:id] is ignored for show, edit, update, and destroy actions.

Next Time...

In my next article, I'll describe some of the issues I ran into with setting up and testing my router.

Upgrading to Rails 3 and RSpec 2, Part 1: Introduction

2010-08-10T19:17:00.001-04:00

Over the last couple of days I've been upgrading a Rails app from 2.3.8 to the 3.0 release candidate. (Update, August 15: see the Rails 3 branch itself and a comparison of the Rails 3 branch with the last Rails 2 version.) The web has plenty of useful resources for Rails 3 itself and Rails 3 upgrading, but there's little to nothing on upgrading RSpec and Cucumber. I'm going to write a few posts outlining what I did in my upgrade, concentrating on RSpec and Cucumber upgrades since Rails 3 itself is covered so well.

First, you have get the upgrade itself going. I recommend:

Build a Rails 3 app from scratch. It really helped to know how a Rails 3 app was supposed to look and work. I started a whole new project, but a toy app (e.g., a blogging system or to-do list) would be just as good. (Work through the Ruby on Rails Tutorial by Michael Hartl.) Just make sure to build the app honestly: including tests! It would also help to experiment with gems and plugins you use on other projects.
Watch Railscasts. Ryan Bates does a fantastic job every week in his Railscasts screencasts. The last two weeks he's done screencasts on upgrading to Rails 3:
- Part 1 is on the upgrade itself: creating a Gemfile, installing the plugin, re-generating the app.
- Part 2 is on upgrading the RSpec specs.
Use the plugin. The rails_upgrade plugin is great. It shows many false positives on my project, but it's not difficult to get past them. The rake tasks the plugin provide are pretty self-explanatory; but if you want to see a useful workflow with the plugin, Ryan Bates shows how to install and use the plugin in the Railscasts listed above.

The first Railscast episode on the Rails 3 upgrade is by far the most important resource I've listed here. You can probably find the same information on any number of blogs as well.

I used Jeremy McAnally's Rails 3 Upgrade Handbook, and I cannot recommend it completely. If you've completely ignored Rails 3 up to this point, the handbook would be great for you. I've read many blog posts and watched many presentations by Yehuda Katz, so I didn't need to know changes I was upgrading through. If you're familiar with Rails already and the changes in Rails 3, then the Railscasts listed above are more than sufficient. (Of course, this doesn't mean you can't buy the handbook anyway to "give back to the community"; McAnally did write the plugin!)

In my next post, I'll describe the changes I had to make to my controllers and controller specs.

Tab Candy for Firefox

2010-07-30T14:53:00.001-04:00

It's a bad name because it's not just about making things look good. "Tabs on Steroids" would be better. Whatever we call it, it looks awesome.

Tab Candy is a way of organizing tabs in the Firefox browser. You create groups of tabs, and Firefox will show you just one group at a time. I might create groups for "Communication" (with GMail, Reader, Facebook, and LinkedIn tabs), for "Hobbes Compiler" (with tabs open to the Java API and Parrot PIR references), for "Rails Project" (with tabs open to my development server and to references for Ruby, Rails, MongoDB, and MongoMapper), etc. When I want to do email, I open up the "Communication" group, and my current tabs are replaced by Gmail, Reader, Facebook, and LinkedIn tabs. When I want to go back to work on my Hobbes compiler, I switch that group, and its tabs replace the "Communication" tabs.

I tend to work with many tabs open at a time (right now I have 14 open), although I tend to organize them into separate windows (right now I have 1 open and 2 minimized). The separate windows aren't a good organizational tool, but Tab Candy offers two huge benefits over separate windows: named groups and spatial identities. Just like a folder, a group can be given a name. Can you imagine navigating a file system without named folders? It's a simple feature that's incredibly powerful. Being able to place those folders in a particular place is also very powerful. A friend of mine in grad school did some research on Netscape's buttons on its toolbar. (This was in the mid 1990s, so Netscape was cutting edge.) It turned out that the size of the buttons, the icons on the buttons, and the words on the buttons did not matter nearly as much as the location of the buttons. Once users got use to Netscape, you could tweak the icons and text, and the users would still be as productive, but if you changed the order, the users would have to spend extra time finding right button.

Tab Candy is presently in alpha testing/release, but they promise more features (in meh-to-cool-to-awesome order):

Colors and background images for decorating your groups. (While names and spatial position are essential, some decoration can help.)
Share tab groups in various ways.
Save tabs for later. (Presumably this would unload these tabs from memory preventing Firefox from bloating.)
Search your tabs.
Multiple profiles so that you can log onto the same website with different logins. (As a developer, this is very appealing.)

I can't resist pointing you at this video for more information:

An Introduction to Firefox's Tab Candy from Aza Raskin on Vimeo.

Strangely, Tab Candy is being presented as a new "OS-like interface". I suppose, but here's my question: is Tab Candy more like the folder/file structure that you see in the Mac OS X Finder or like the virtual screens of Spaces on Mac OS X? Of course, the answer is "both", but then what's the blend? Or is there a better metaphor?

Tab Candy looks really cool; the only problem is that I'm presently a Google Chrome user. Might Tab Candy be the feature to bring me back to Firefox?

(via ZDNet, via DZone)

"Calling a method in Rails::Application is deprecated..."

2010-07-28T17:01:00.001-04:00

I already described how I got rid of a DEPRECATION WARNING when upgrading from a Rails 3 beta to the latest release candidate. That DEPRECATION WARNING involved the router DSL, and I'd like to point out that the Rails 3 generator (from a beta release) generated the map parameter for me.

Similarly, the Rails 3 generator is responsible for this DEPRECATION WARNING:

DEPRECATION WARNING: Calling a method in Rails::Application is deprecated, please call it directly in your application constant Reviews::Application. (called from method_missing at /Users/jdfrens/.rvm/gems/ruby-1.9.2-rc2@Reviews/gems/railties-3.0.0.rc/lib/rails/application.rb:77)

I love how it tells me where the deprecation is reported, not where it's committed. (Stack trace, anyone?) Instead it was a guessing game (after Google searches failed) to discover that the Rakefile in the app's root directory is at fault. Change this:

Rails::Application.load_tasks

to this:

Reviews::Application.load_tasks

Of course, use the name of your own app, not "Reviews".

But I Am Using the New Routing DSL!!!

2010-07-26T18:56:00.001-04:00

I upgraded a Rails 3 app to the first release candidate. I got this error running my tests:

DEPRECATION WARNING: You are using the old router DSL which will be removed in Rails 3.1. Please check how to update your routes file at: http://www.engineyard.com/blog/2010/the-lowdown-on-routes-in-rails-3/.

I've been very careful to use the new DSL, so this kind of disappointed me. What could I possibly be doing wrong? I tried commenting out various directives in the routes.rb file, but I kept getting the warning. Then I changed this:

Reviews::Application.routes.draw do |map|

to this:

Reviews::Application.routes.draw do

Deprecation warning all gone.

More Fibers for Rails

2010-07-26T18:21:00.001-04:00

I have to recommend yet another video talk: "No Callbacks, No Threads & Ruby 1.9" by Ilya Grigorik

Basically, the idea is to use Fibers to implement concurrency in existing frameworks (with minimal, behind-the-scenes changes), and you get to write the code you want. I'm thinking that Fibers could be quite useful...

I mastered call/cc back in grad school (at least to get me through one test), but I didn't do much with coroutines. Fibers are closer to coroutines, and fortunately that makes them easier to pick up.

Here are some Fiber-related articles to get familiar with Fibers before watching this video:

"Pipelines Using Fibers in Ruby 1.9" by Dave Thomas
"Pipelines Using Fibers in Ruby 1.9—Part II" by Dave Thomas
"Ruby 1.9 adds Fibers for lightweight concurrency" by Werner Schuster at InfoQ

(via Gregg Pollack on the EnvyLabs blog)

Parrot (PIR) Tutorial

2010-07-24T19:32:00.001-04:00

I stumbled on a nifty tutorial on programming in Parrot, the virtual machine for Perl 6: "Parrot Babysteps" by Brian Wisti.

You get variable/register basics, data types (ints, floats, and strings), data structures (arrays which act as stacks and queues and iterators), and basic control structures (i.e., if and goto). By the end of the tutorial, Wisti does some file I/O. I would have preferred to know more about PMCs and method dispatch (especially multiple dispatch), but then I'm not the one writing the tutorial. Wisti does a really good job, and I wish I'd had this when I was teaching my Programming Languages course.

String, StringBuilder, StringBuilder, and Performance

2010-07-21T17:28:00.001-04:00

Earlier today I came across as article "StringBuilder vs. StringBuffer" on the Java J2ee Planet blog. Real quickly: both StringBuilder and StringBuffer are mutable String classes; StringBuffer's mutators are synchronized for multiple threads while StringBuilder's are not.

Piquing Claim

The article makes one claim which piqued my interest. Given this loop:

String result = s;
for (int i=1; i<times; i++) {
  result = result + s;
}

The article makes this claim:

If called to duplicate a string 100 times, it would build 99 new String objects, 98 of which it would immediately throw away! Creating new objects is not efficient. A better solution is to use StringBuffer.

I don't dispute the math; I dispute this: "Creating new objects is not efficient." Years ago some researchers took a look at the objects created in typical programs, and they determined that a large majority of objects had very short lifetimes. This is why generational garbage collection is so effective (and hence widely used).

Performance Experiment

I implemented the code from the article to test out the claim. It's available as gist, and I encourage you to give it a quick scan at least. Basically it takes the loop above, a duplication algorithm, and implements it six times: duplString(), duplStringConcat(), duplStringBuilder(), duplStringBuilderAllocated(), duplStringBuffer(), duplStringBufferAllocated(). The names of the methods indicate what types of object were used in the duplication. duplStringConcat() uses String#concat(String) to duplicate the string. The Allocated versions use a constructor that pre-allocated the space for the final string (e.g., new StringBuilder(s.length * times)).

On my MacBook (OS X 10.5, 2 GHz Intel Core 2 Duo, 4 GB 667 MHz DDR2 SDRAM), I got these very unscientific results for 1000 duplicates:

String	190 ms
String#concat(String)	77 ms
StringBuilder	26 ms
StringBuffer	31 ms

Curious! First, pre-allocating space in the result didn't matter significantly, shaving only a couple seconds off the time. Second, the synchronization of StringBuffer doesn't add that much overhead. Sure, it's 5 ms difference in my tests, but these are hardly scientific. Before we run more tests to decide this issue, I'd ask you why you need a StringBuffer shared between concurrent threads—but that's a whole different can of beans to argue about.

By far the most curious thing is that the String version is significantly worse! This is why we run experiments and not rely solely on analytical arguments (based on what we think the API and system docs say). In my defense, the String version shouldn't be that bad. The best-case scenario would be a compiler that recognizes that the intermediate results never leave the loop (let alone the function), so it gets compiled into a StringBuilder version. If nothing else, the intermediate Strings could be allocated on the stack, never taxing the garbage collector.

Lessons Learned from Source Code

I poked around the source code and discovered a few things. First, the JavaDoc for String indicates that concatenation with + "is implemented through the StringBuilder(or StringBuffer) class and its append method." So for every executed + there are StringBuilders created, append()s applied, and conversions to String. Yikes!

Second, String#concat(String) uses the low-level methods of String (which use System.arrayCopy()) to create the new String. I figured this would get me closer to StringBuilder performance, but it only cuts the time in half.

Third, StringBuilder uses its own char[] to store the characters. I wonder if arrays are not quite as heavy as other objects in Java? Probably not, but it's something to consider. StringBuilder can and does use System.arrayCopy() as often as possible, and this certainly makes a difference.

Finally and I suspect most importantly, StringBuilder uses an optimal algorithm for allocating incremental storage. Whether using + or concat(), String will always allocate just enough space for the new string. So in the example above with 100 duplications, there are at least 99 array allocations, each one s.length() longer than the previous. StringBuilder, on the other hand, uses a char[] larger than the official length of the "string" it stores. When the char[] fills up, a new array twice as big is allocated. This means that the number of allocations is proportional to the log (base 2) of the final length. Instead of 99 char[] allocations, there's fewer than 7 allocations!

What to Use

Normally, my advice is to avoid premature optimizations. But it seems to me that if you're building up a lot of Strings, using StringBuilders is good practice. This begs the question: when you are you building up a lot of Strings? As always, profiling your app should tell you what to concentrate on.

On the other hand, programming to the StringBuilder interface is still pretty natural, especially if you actually program to the Appendable interface. I am a strong proponent of programming to interfaces, and this is a good motivating example. If you pass around a StringBuilder throughout your code, you can easily retype it as an Appendable without losing anything. You still get all of the efficiency benefits of StringBuilder, plus you can now use all the same code with a wide range of Writers (to screens, files, pipes, and streams) without changing a thing and still reap the efficiency benefits (for free) provided by the implementing class.

Updated MongoDB cleaning

2010-07-11T18:34:00.001-04:00

I just posted a better version of my code to clean up a MongoDB database after each RSpec and Cucumber test.

MongoDB was complaining during my Cucumber tests that I was trying to remove a system collection. It seems to be just a complaint in the log file, so I don't thin the change was critical, but I prefer a clean log file.

MongoDB wasn't complaining about the same thing with my RSpec tests. Turns out that the cleanup wasn't running because of the :type => :model filter on the config.after(:each) call. I dropped the filter, and the cleanup now runs after each test. It's not optimal, but that's not particularly a problem right now.

Cleaning up a MongoDB Database after RSpec and Cucumber

2010-06-30T18:34:00.002-04:00

UPDATE: added conditional to not delete system collections. MongoDB only complained about this, so it isn't disastrous without it.

UPDATE #2: dropped :type => :model from the RSpec settings.

Last week, I posted my configuration for a Rails 3 app using MongoDB, RSpec, and Cucumber. (I'm also using jQuery, Ruby 1.9.2, and now HAML, but they don't matter for today's blog post.)

The app is for keeping track of the books that I own. When chasing down a bug, I poked around my testing database, and discovered it had a lot of entries for the book Dune (my primary testing example).

These multiple entries were not related to the issue I was having, but it will be a problem in the future. I figured I should solve it now. My Google searches didn't reveal any direct solutions, but I was able to piece something together.

My solution is to remove all collections from the database after each test. I have efficiency warnings going off in my head, but I have some time before it's actually a problem (if it ever is).

Cleaning a MongoDB Database for RSpec

In spec/spec_helper.rb within the Rspec.configure block:

config.after(:each) do
  MongoMapper.database.collections.each do |collection|
    unless collection.name.match(/^system\./)
      collection.remove
    end
  end
end

~~The :type => :model restriction runs the cleanup only after model tests, not controller or view tests.~~

Cleaning a MongoDB Database for Cucumber

In a new file features/support/mongodb_clean.rb:

After do |scenario|
  MongoMapper.database.collections.each do |collection|
    unless collection.name.match(/^system\./)
      collection.remove
    end
  end
end

Legos for Adults

2010-06-25T17:47:00.001-04:00

I've got another TED talk to share: "Legos for grownups" by Hillel Cooperman. It's a rather short talk...

My Rails 3 App with jQuery, MongoMapper, RSpec, Cucumber, and Ruby 1.9.2

2010-06-22T18:00:00.001-04:00

I've been interested in starting a new Ruby on Rails project for keeping track of the movies, books, and video games that I've watched, read, played, and own. I love new shiny things like Ruby 1.9 and Rails 3; I already use RSpec and Cucumber; I've fallen in like with jQuery; and I'm very curious about MongoDB and MongoMapper.

My Sources

I hardly had to do any real work to get this working. These sources told me what to do:

"Getting Rails 3 Edge with jQuery, RSpec and Cucumber using RVM" from Mikel Lindsaar
"Rails 3 - Getting Started" from the MongoDB documentation

Mostly, this is a rehash of Lindsaar's HOWTO with a MongoMapper twist. I've written my HOWTO as a blunt and raw "these are the commands I used" with an explanation afterwards. I'm happy to elaborate on anything if I don't explain it in enough detail.

Creating the App

rvm use ruby-1.9.2
rvm gemset create Reviews
rvm gemset use Reviews
gem install rails --pre
rails new Reviews -OTJ
cd Reviews
echo "rvm ruby-1.9.2@Reviews" > .rvmrc

The first three instructions use rvm to activate Ruby 1.9.2 and to create (and use) a new gemset for this app.

The gem command will install the latest version of Rails 3. You don't need to install anything else yet.

The rails command creates a new app without an ORM (-O), without Test::Unit (-T), and without Prototype (-J).

The echo command tells rvm which version of Ruby to use with what gemset. (I'm not entire sure if this is working well.)

jQuery

mkdir public/javascripts/jquery
curl http://code.jquery.com/jquery-1.4.2.min.js > public/javascripts/jquery/
curl http://github.com/rails/jquery-ujs/raw/master/src/rails.js > public/javascripts/

This drops the jQuery library in its own subfolder. Feel free to drop jQuery plugins there. The rails.js is the wrapper around jQuery for Rails.

In head of app/views/layouts/application.html.erb:

  <%= javascript_include_tag 'jquery/jquery-1.4.2.min' %>
  <%= javascript_include_tag :all, :cache => true %>

Lindsaar puts these at the end of the body. I haven't done much with jQuery, so there may be good reasons for that.

Gems

This is my Gemfile.

source 'http://rubygems.org'

gem 'rails', '3.0.0.beta4'
gem 'rails3-generators'

gem "bson_ext"
gem "mongo_mapper"

group :test, :spec, :cucumber do
  gem "rspec"
  gem "rspec-rails",      ">= 2.0.0.beta"
  gem "nokogiri"
  gem "capybara"
  gem "cucumber"
  gem "database_cleaner"
  gem "cucumber-rails"
end

Then, bundle install to install the gems.

rails3-generators provides some useful generators.
bson_ext is a optional binary driver for handling BSON data for the mongo driver (which is a dependency of mongo_mapper).
I had a problem with webrat and cucumber and Rails 3 (and apparently others have, too), so I used capybara. (This may make nokogiri unnecessary.)
I assume the other gems are obvious; if not, let me know.

In config/application.rb,

config.generators do |g|
  g.orm             :mongo_mapper
  g.template_engine :erb
  g.test_framework  :rspec
end

Mongo

A new file, config/initializers/mongo.rb:

MongoMapper.connection = Mongo::Connection.new('localhost', 27017)
MongoMapper.database = "#Reviews-#{Rails.env}"

if defined?(PhusionPassenger)
   PhusionPassenger.on_event(:starting_worker_process) do |forked|
     MongoMapper.connection.connect_to_master if forked
   end
end

This was stolen completely from the MongoDB documentation except for the database name. Feel free to use your own database name!

A second file, lib/tasks/mongo.rake:

namespace :db do
  namespace :test do
    task :prepare do
      # Stub out for MongoDB
    end
  end
end

Generate Testing Frameworks

rails generate rspec:install
rails generate cucumber:install --capybara --rspec --skip-database

Ready to Go!

The app I have now seems to be ready for development. If I run into any problems, I'll post an update.

Happy with My Backup Service

2010-06-21T14:29:00.001-04:00

Way back in March, I tweeted my thoughts about the backup service I was using. Since I've found a good replacement, I figured I should report on it.

Mozy, You're Okay

I originally picked Mozy for my backups because I had heard good things about them, and a few months after trying them out, I also picked them for my parents' computer. My parents have actually had pretty good service from them, but then they have only a couple of gigabytes to back up on a WinXP machine.

I have a MacBook with over 140 GB of data to backup.

Mozy's support for Macs always seemed to a second thought. When a friend and I tested them out one afternoon several years ago, restoring a file on a Windows machine was really easy, but on a Mac it was really obnoxious. Occasionally, I'd have problems which would require opening the Console app to get at an error message, and once I even had to reinstall Mozy and wipe my configuration from my Library folder.

As for my data needs, the amount of data should really only be a problem with the initial backup. Incremental backups after that shouldn't amount to much.

Mozy, You Suck

A few weeks before my tweet, Mozy updated itself on my MacBook. Once the update was finished, it decided that all 140 GB of data that it had been backed up just fine had to be backed up from scratch from my computer to their servers.

Now, I can imagine scenarios where this might be necessary. A secret encryption key lives on my computer, and only that key can be used to encrypt and decrypt the files off the server. And maybe they upgraded their servers with a new encryption algorithm, so to keep the secret key on my computer and not in their grubby hands the backup had to be redone from my computer.

But couldn't you have told me this when I did the upgrade? Better yet, you couldn't preserve some backwards compatibility?

On the day of my tweet, Mozy updated itself again. And it decided to back everything up again from scratch. We can speculate why it was necessary this second time, but none of the scenarios make me happy—either the people at Mozy are lazy or stupid.

However, if starting over from scratch was the only problem I had, I probably would have stayed with Mozy, and my tweet would have been a mild profanity-free complaint.

Mozy, You Really Suck

After the first upgrade, I had the Mozy status screen open, and I noticed it wanted to back everything up again. It didn't make me happy, but I figured I'd let it run overnight, and I'd decide how to handle this in the morning.

The next morning, my internal hard drive was full, RAM was maxed out, and my MacBook was in a bad way. I shut down programs as best I could and rebooted. It came back fine until Mozy started another backup process. Then the RAM filled up, the hard drive got full, and my MacBook was again in a bad way.

This time I only told Mozy to stop its back up process, and I got my RAM and hard drive back. So I tried an experiment. Instead of backing up all 140 GB of my data, I told it to back up just one small folder. No problem. So I added a couple more folders. No problem. I tried a much larger folder. Problem!!!! Okay, fine, I'll add just a few folders at a time. I followed this procedure for several weeks.

Meanwhile, figuring this was a serious flaw in their backup algorithm, I shot an email to Mozy support. I mean, I'm doing a computation to make the backup algorithm work better. It's not a difficult computation either (i.e., "pick a few small folders, back them up"), so it has to be their problem. Nope! The response I got back from Mozy's tech support was that's the way things worked, and I'd have to add folders myself from time to time to get everything backed up again.

And then Mozy updates again, and I have to start this whole process over again. This is where profanity laced tweets come from.

Crashplan, You Seem to Be Awesome

After my tweet, I started looking for other online backup services. I had heard good things about Carbonite, but I never got around to trying them out.

A couple people recommended CrashPlan to me. So far, it's been working very well.

Obviously, it had to back up everything from scratch, and this took a couple of weeks, but it went very smoothly. I specified all of the folders I wanted backed up, and it backed them up without overwhelming my computer or network.

I've restored files from the online backup, and this goes smoothly and fairly quickly. I believe I've gone through at least one software update without problems.

CrashPlan is available on Windows and Linux(!) platforms. Plus, you can backup to other computers, to your own or even to a friend's.

So after several months of using CrashPlan, I'm willing to say that CrashPlan is awesome.

Functional Programming for Dummies

2010-06-03T21:09:00.002-04:00

Here's how you write factorial in Haskell:

factorial n = product [1..n]

Boy, that is hard to read.

Give Me Some Context, Please!

I was going to let this pass: "Why Functional Programming Will Not Take Over The World - A Square Peg In A Round Hole" by Alex Turner. Turner is the genius who determined that Ruby was dead because it dropped 0.6% in popularity over the last year. This dropped it out of the top ten, so therefore the "knife was out" and "Ruby is doomed".

Now he's complaining about functional programming. His stated complaint is that people think iteratively, not functionally. So functional languages won't take over the world. (Who knew that was their goal? Did I miss a memo?) His actual complaint is that he doesn't think that he thinks functionally or recursively, so therefore everyone must think iteratively.

Now, granted, I'm horribly biased here. My dissertation dealt with FP and high-performance computing: using structural and functional decomposition to get the most out of the memory hierarchy (caches, RAMs, virtual memories) and out of multiple processors. These days, I write Java and Ruby code, and most (if not all) of my OO programming is functional: I never write setter/mutator methods, and I often encode algorithms in their own objects (essentially closures).

In short, I like functional programming.

Turner Is the Round Hole

Tuner's argument comes down to three snippets of code. First, the oh so unreadable ML version of factorial:

fun fac 0 = 1
  | fac n = n * fac (n-1)

It's identical to the definition you'd find in any mathematics textbook. I think it's immensely readable. The Haskell version at the top of this article is even more readable.

Turner's favorable alternatives micromanage the computation. First, he writes it in VSPL:

1 !r 
2,?n,{ ,?r:Prod !r }:Repeat

WTF? Really? That's better than the ML or Haskell versions? Granted, I'm reacting mostly to the syntax here, but if you're going to pull out an example of how iteration is better, you go for this? A C++ version would be better. Why not Pascal? When I read this code, I actually thought Turner was writing satire because I can't imagine how this is better than the ML version, and I even now I can't shake this suspicion...

Turner does marginally better with a COBOL version:

move 1 to r
perform varying i from 2 by 1 until i>n
    multiply r by i giving r
end-perform

COBOL tends to read like really awkward, pedantic English, so this is at least readable. (I know that the result ends up in r.) But the COBOL syntax still gets in the way of the readability.

But let's push the syntax to the side. Turner summarizes his COBOL version like this:

The above COBOL is quite close to how one might think of a factorial calculation and so needs almost no mental translation.

That's how one might think about it if they're worried about machine registers or memory locations. Notice how the iterative version need an explicit accumulator, namely r? The functional versions don't. Now compare this to a natural, English description of factorial: "n! is the product of the numbers 1 through n". Where's the accumulator? Where's the iteration variable i? Which code matches that description better? (Answer: Haskell!)

Reading between the lines, I claim that Turner is the one with the misconception. I've encountered too many colleagues who've been warped by FORTRAN (or C or Pascal) and the iterative mindset. At a certain point (the age of the person, the depth of the mindset), they can't do functional programming, especially recursion. These people start to believe that iterative thought is the natural way we think of computations.

My Take

First, what's with the melodrama? FP won't "take over the world"? Well, here's a news flash: iterative and OO won't take it over either. Neither will AOP, logic programming, or esoteric programming. Each of these paradigms have their own niches, and they'll flourish just fine there (especially esoteric programming).

Second, I hate factorial (or Fibonacci) as the go-to FP example. And in this case it works completely counter to Turner's argument. The ML and Haskell versions are perfectly readable, and much better than his iterative alternatives. If you're going to make any arguments for or against FP, use some code that proves to me that you've actually programmed in the language yourself, not copied code out of another blog post.

Third, there's a constructive case to be made for FP. Ruby and Python already support a functional paradigm since closures are first-class citizens. Other languages (Java, C++, C#, PHP) are looking to add them. These features are not needed, but because programmers are thinking functionally, they want FP tools.

Finally, where's the cognitive research on this topic? Turner is ultimately making a claim that iterative is better, although he starts by posing that FP cannot be mapped onto our brains. These are questions for psychologists and cognitive scientists doing real studies, not some guys saying, "I don't get it, so no one else can."

Not Interested

I'm not interested in arguments against FP based on syntax (e.g., whitespace in Haskell, parentheses in LISP/Scheme) or based on orthogonal features of a language (e.g., Haskell's type system). You can dislike a language because of these things, but those are separate issues. They have nothing to do with the value of functional programming.

Update: I fixed the most important link I had in my entire article.

The Future of UI

2010-06-01T13:42:00.002-04:00

Another TED talk...

John Underkoffler got to show off his UI research in Minority Report. I don't know how much was mocked up in that movie (which is eight years old now), but Underkoffler takes on the ultimate live demo in this talk. He shows off what his system can do now, and it's quite impressive.

One thing that concerns me regarding these newfangled interfaces is that hand gestures get you only so far. Way back in 1996, Don Gentner and Jakob Nielsen wrote an article "The Anti-Mac Interface" for the Communications of the ACM. The most important observation for me from this article was that the mouse and GUI reduced our communication to the grunts and crude gestures of cavemen.

Underkoffler's system is better: hand gestures are more expressive than a mouse; he's got an extra spacial dimension to play in; the network awareness is really cool. But at some point you have to describe complicated business rules to the system, and these require at least some words. I'm curious how that input works and how well it works. Underkoffler mentions that the system is in use now on real problems with real users, so the ability must be there, I'm just curious how well it works.

Can't Copyright Fashion

2010-05-25T15:29:00.002-04:00

I've got another video to share today. Perhaps I found this really interesting since I've been avidly watching the last few seasons on Project Runway, but this TED talk from Johanna Blakely on copyright and fashion design is really interesting:

My summary: fashion can't be copyrighted, but that's okay. It encourages more and better design; it makes us a lot of money. Blakely talks about other arts and technologies that can't be copyrighted, like car designs and food recipes. But she gets software copyrights wrong.

She mentions open source software as not having a copyright, and that's not quite correct. It has a copyleft: copy and modify my code, but preserve its pedigree. Plus, it's voluntary. There are plenty who copyright their software in traditional ways.

This talk of copyright reminded me of a recent Internet conversation the science fiction community has had over fan fiction. I only sampled a bit of the conversation, and mostly from George R. R. Martin. I don't have much love for fan fiction, probably because the first piece I read was a Star Trek Next Generation episode with way, way, way too much exposition in its opening scene. It also doesn't help when the quality of official spin-off books aren't well written either. (I'm looking at you, Timothy Zahn and your Thrawn trilogy. Lu-uke, indeed.) As Martin points out, there's something very damaging to the original property when a follow up isn't as good.

I find it very curious how I come to very different conclusions on the copyright issue in these three domains. Fashion seems to have done quite well without copyright protection, and the legal reasoning for no copyright (clothing is too utilitarian) seems sound to me. So no copyright for them. I still believe that open source is the best way to develop software, certainly for certain types of software. But I also use and love some copyrighted software: Mac OS X, Civilization IV, RubyMine, iTunes, MarsEdit, TextMate, Things—just to name a few that I'm running now or would like to. So make copyright an option for them. George R. R. Martin and Bill Watterson (of Calvin & Hobbes fame) want to protect their worlds and characters, and derivatives dilute their creations. So allow them lots of copyright.

MongoMapper

2010-05-10T16:45:00.001-04:00

I watched a presentation from John Nunemaker today about his MongoMapper Ruby gem. I've been interested in MongoDB and a Ruby ORM, and I tried out MongoMapper in my spike. John's presentation really encourages me to keep with MongoMapper. It works very well, and the plugin architecture is really simple and powerful. Here's the presentation: And you might want these slides while watching and listening:

MongoMapper - Mapping Ruby to and from Mongo

View more presentations from John Nunemaker.

Should I Use "Should" to Describe What an RSpec Example Should Expect?

2010-04-27T18:33:00.001-04:00

Chris O'Sullivan opined on his blog today: "Get real with your specs, punk". He poses the same question I started thinking about last week: should "should" be used in an RSpec description?

For example (mine, not his):

describe "/home/index.html.erb" do
  it "<b>should render</b> the home page"
end

versus

describe "/home/index.html.erb" do
  it "<b>renders</b> the home page"
end

I may have convinced myself to drop the "should" in the description. It's more terse and less repetitive. (And more like Clint Eastwood, as O'Sullivan points out.)

Should Phrasing in JUnit Assertions

Several years ago while writing JUnit assertions, I discovered the very important power of the word "should". When I wrote a JUnit assertion, I would include a descriptive message. I found that when an assertion failed that descriptive message was very helpful in figuring out what when wrong. I discovered, though, that if the message were positive, it was confusing.

Stretching my example:

assertEquals("renders the home page", "<html>...</html>", indexPage.render());

When this fails, JUnit displays "renders the home page". I'd have to process it: "Wait?! It displays the home page? Then what's the matter? Ohhhh! It should render the home page!"

assertEquals("should render the home page", "<html>...</html>", indexPage.render());

The message still works as a comment for the code itself (this is what I intend by this assertion) and now as an appropriate error message (this should have happened, but didn't).

Error Messages from RSpec

The primary error message comes from an RSpec matcher, and its API is really good at producing excellent error messages. And the should method, which triggers the matcher, self-documents the code very nicely. So that's where the "should" phrasing belongs.

But perhaps the description gets in the way? Fortunately, no, as a quick experiment proved to me.

An Experiment

My example is taken from a project I've been working on, and it was an easy way to run a experiment. I tweaked my code so that an expectation would fail.

In RubyMine, the should method produces an obvious error message in its own window, and the example's description is in a separate panel only to give context. Perfectly fine.

When I ran the specs on the command line, I got this output:

'/home/index.html.erb renders the home page' FAILED
expected following output to contain a <img src="/images/foobar.jpgXXXX" /> tag:

Using the word "FAILED" so clearly in the output makes it clear that the rendering failed. The should method and the matcher do their part to specify exactly what went wrong.

RSpec Report

Actually, an example description can be used when the example passes: an RSpec report. RSpec allows you to run all the tests and outputs the description for all the examples, passing and failing. But it turns out that's okay, too:

/home/index.html.erb
- renders the home page

It's not any better or worse with a "should" phrasing unless this report is somehow being used for the client, and the client really wants "should" phrasing.

Presentation about MongoDB

2010-04-06T17:26:00.001-04:00

I've been playing around with MongoDB lately, and I watched a presentation from RubyConf 2009: "Getting Non-Relational with MongoDB" by Michael Dirolf. It's a good talk, and if you know little or nothing about MongoDB or document databases, it's well worth a watch. If you want a quick look, check out the slides for his talk.

I also recommend "NoSQL: Death to Relational Databases" by Ben Scofield. It's an overview of non-SQL database systems. Since he has only 45 minutes, he doesn't spend much time on any one system, but he does a good job of categorizing and analyzing them. He gives some great code snippets that highlight how each system is used for their particular strength. (That is, his example for Redis is much different for Neo4J since the former is just a key-value store and the latter is a graph database.)

Collatz Numbers (Project Euler Problem 14)

2010-03-24T18:57:00.001-04:00

Problem 14 of Project Euler deals with the Collatz conjecture. In particular, how long does it take for a particular integer to be reduced to 1? Here's my solution in Erlang:

collatz(1) -> 1;
collatz(N) ->
  if
    N rem 2 == 0 ->
      1 + collatz(N div 2);
    true ->
      1 + collatz(3 * N + 1)
  end.

This is what I'm calling a "Collatz number". Problem 14 is to find the number less than a million which has the largest Collatz number.

If a problem screamed "Memoization!!!", this is it. Except that it shouldn't. It does help (which we'll get to), but it turns out to not be necessary.

Brute Force Solution

To find the maximum Collatz number in Erlang, I used this function (with the one above):

maximum_collatz_under(N) ->
  {_, Index} = max(map(fun (X) -> {collatz(X), X} end, seq(1, N))),
  Index.

seq(1,N) returns a list of integers. The function I map over this list returns a tuple of both the original number and its Collatz number. I need to take the maximum over the Collatz numbers, but I need to return the original number. Erlang's tuple data-structure is really helpful here; I love how tuples are ordered (as they are in Haskell).

There are many ways in which this should be really inefficient. First, the original collatz(N) function repeats a lot of computations: to compute collatz(32), it would be helpful if I already know collatz(16). And to compute collatz(5), it also helps to known collatz(16). This is where memoization would help. And it does, but we'll get to that.

There's another inefficiency in the maximum search. First, seq() creates a list of all integers in the sequence. The call to map() creates another list, this one of tuples of integers. Then max() goes through that list. However, none of the intermediate lists are necessary. The Collatz number can be computed as part of maximum search like so (in Python):

def maximum_collatz_under(n):
    if n == 1:
        return 1
    maximum = 0
    maxIndex = 0
    for i in range(1, n+1):
        collatzOfI = collatz(i)
        if collatzOfI > maximum:
            maximum = collatzOfI
            maxIndex = i
    return maxIndex

In Haskell, this could be done with a foldl:

maximumCollatzUnder_with_foldl_and_maximum n = index
  where (_, index) = foldl' f (0, 0) [1..n]
        f acc i = maximum [acc, (collatz i, i)]

Actual Efficiencies

You may be asking yourself, "Why not show off your list-avoiding Erlang solution?" My answer: "I don't need one." It's the fastest non-memoizing solution I have! It runs around 13.3 seconds. Without memoization and without the explicit lists, Haskell runs in just over 19 seconds, Python around 100 seconds. Erlang for the win!

However, if you know my polyglot tendencies, you'll notice I haven't mentioned one language yet: Ruby. No, I'm not embarrassed by Ruby since Ruby produced the fastest solution of all my languages.

Memoization For the Real Win

I actually created by Ruby solution first for this problem, back when I thought I had to use memoization.

For my first attempt, I memoized everything. This failed miserably.

When computing a Collatz sequence, the numbers can get larger than the original number (e.g., collatz(999,999) = 1 + collatz(2,999,998)). That's a lot of memory to allocate to this problem, and given the problems constraints, very little of the memoization space between collatz(1,000,000) and collatz(2,999,998) would be used.

I also allocated the memoization space dynamically. That is, I accessed the Ruby array as if it were infinitely long. So when I accessed an array element that hadn't been created yet, the array had to grow. There are ways so that the growth is managed sensibly, so I don't think this was a huge problem, but it doesn't help when you're talking about 3,000,000 element arrays (or larger).

So for my second attempt, I memoized only collatz(1) through collatz(999,999). I allocated just one array for those values. When computing the Collatz number of an integer larger than 999,999, I just used the standard recursion, falling back on the memoization when possible. Here's the code:

class Integer
  @@collatz = Array.new(10000000)

  def collatz
    if self >= @@collatz.length
      self.raw_collatz
    else
      @@collatz[self] ||= self.raw_collatz
    end      
  end

  def raw_collatz
    if self == 1
      return 1
    elsif self.even?
      (self / 2).collatz + 1
    else
      (3 * self + 1).collatz + 1
    end
  end
end

The array never has to grow, so that overhead isn't a problem. Most computations can use the memoization, so it delivers a real benefit. Raw recursion is used only for original computations and for the occasional extra-large value for n. This solution runs in around 6.7 seconds with Ruby 1.8.7; it drops to 2.7 seconds if I use the Ruby 1.9 interpreter!

Declaring a Winner

The real winner here is not Ruby itself, but the memoization. I couldn't get memoization to work in Haskell. (I'm going to have to think about it some more.) I'm really not sure how to do memoization in Erlang, but a quick Google search presented some solutions. It should be easy enough to memoize in Python, but I didn't try. I have no problem imagining that its running time could come down to 7 seconds or less (maybe even Ruby 1.9's 2.7 seconds).

If a language is to be declared a winner, I nominate Erlang. To get that kind of performance when the code implied explicit arrays, I'm impressed.

There's a Reason Logorama Won an Oscar

2010-03-18T16:06:00.001-04:00

It's frickin' awesome! From the clip I saw during the Oscars, I got the feeling it was a long music video, but there is a story. Or a series of stories (all in 15 minutes).

The animation is quite cool. It amazes me how many logos they worked in. Be sure to look for "stealth logos", logos that are right in front of you but aren't immediately recognized as logos. (I'm guessing that's one of the purposes of the short.)

Logorama from Marc Altshuler - Human Music on Vimeo.

Darwin Weighs in on the Computer

2010-03-08T14:12:00.001-05:00

I've been following the 2D Goggles blog, which is a comic about Charles Babbage and Augusta Lovelace. I find it quite amusing, especially Lovelace's pipe smoking. Today's entry directed me to this letter from Charles Darwin to Charles Lyell. I find this comment from Darwin quite amusing:

what a grievous pity it is that [Babbage] should be so implacable, & if one might so call the calculating machine, so very silly.

What a rude thing to say about the machine that's proving your theory, Mr. Darwin! (And what great insight and progress 150 years provide!)

In an aside, just how many scientists back then were named "Charles"?

Uh, Yes I DID Define that Cucumber Step!

2010-03-03T16:22:00.001-05:00

A couple months back I blogged about putting Cucumber features for a Ruby on Rails project into subfolders. I finally got around to doing this, and I decided to organize by controller (not by user).

One reason that it took me a while to make this change was that it didn't work too well the first time I tried it. Running all the Cucumber features worked fine, but running just one feature file would result in a lot of "step not defined" errors—Cucumber couldn't find my files in the support folder.

More recently, Cucumber added a feature where it keeps track of the scenarios that fail, and when you rerun the cucumber rake task, just those scenarios are run. It's a cool feature, but it too broke when I put my feature files into subfolders.

Now I should admit that I'm using RubyMine. I'm not ashamed of using it; far from it! It's awesome! However, my problem might be a RubyMine issue, although I doubt it.

The solution was to tweak the config/cucumber.yml file. Here's mine:

The change is adding -r features/support -r features/step_definitions to the std_opts. I suspect this might mean that those files are included twice when Cucumber is run normally, but that hasn't been a problem yet.

Programming with Screenshots

2010-01-25T14:45:00.001-05:00

I'm really not sure what to think about this yet: Sikuli "is a visual technology to search and automate graphical user interfaces (GUI) using images (screenshots)". In the demo on their homepage, they use Sikuli to configure the IP settings on a Mac going through the standard System Preferences app.

While the underlying technology is Jython (Python running on the JVM), Sikuli is much more visual: whenever they need to specify a target of a click, they take a screenshot.

There are somethings in iTunes I'd like to automate, but I'm not quite sure this is the solution. It's kind of intriguing, though.

And, officially I'd like to tag this under "awesome?", but I'm not sure I want both "awesome" and "awesome?" tags.

Null Objects and Black Holes

2010-01-22T15:54:00.001-05:00

The latest issue of PragPub (January 2010, available in other formats) has an article in it about nil, null objects, and black holes. The article is called "Much Ado about Nothing", and it's by Paolo Perrotta. Perrotta presents a problem where a data item might be nil:

  CONFIGURATION.current_user.device

What if device returns nil? Any method applied to the device will result in "method not found" errors.

Perrotta's null-object solution is to return a null device with empty methods:

class NullDevice
  def flash; end
  def ring; end
end

  # original code becomes...
  CONFIGURATION.current_user.device || NullDevice.new

I don't like this solution for two reasons. First, is it really fair to let flash and ring go through a null device as if they succeeded? It seems to me that if I ring a device, then the owner of that device has been notified of some event. If the current user doesn't have a device, he can't be notified. If being notified is Very Important, that's a big problem!

My second dislike is an extension of my first: if you're getting a nil or a null object, there's a problem. The "method missing" errors in Ruby and NullPointerExeceptions in Java are great because they tell me that something is wrong. They're terrible because they're so generic. I'd prefer to define ring and flash to throw exceptions with descriptions of their context.

Perrotta's final solution (after a couple more iterations) is to do away with the NullDevice and inject new behavior into the standard NilClass:

class NilClass
  def method_missing(*); self; end
end

This is what is called a "black hole". Once you're in, you can't get out:

nil.ring.ring.ring.flash.flash

While I've been known to add new methods to standard classes like Integer and String and Array, messing with NilClass and especially overriding method_missing seems really dangerous to me. I find it really dangerous since now all nils everywhere in your program will gracefully ignore any method sent to it.

All I'm going to say is: if you get a nil early in your computation, good luck debugging that!

Installing Parrot on Mac OSX

2010-01-20T13:17:00.002-05:00

Parrot is the virtual machine for Perl 6 (and other front ends). I've been using it as a target for my compiler. The Parrot people released 2.0.0, so I decided to install it. I always have to remind myself how I installed it last time, so I figured I'd slap my process up on my blog so that I can find it again (and maybe help out someone else).

A few notes:

The MacPorts version of Parrot is kind of old; I played with the Portfile for a while (even helped get it up to version 1.0.0), but there are really odd linking issues. I've just found it easier installing by hand.
I am using gmake from MacPorts. I believe I ran into an issue once where this was important.
I use /usr/local (the default) as the installation prefix. I use /usr/local/src as my compilation area.
I've tried other configuration flags like --jitcapable and --execcapable. I believe that the former isn't recommended at all (the JIT compiler is in a state of flux); I forget why I stopped using the latter.
The Parrot libraries of a previous installation confuses the new compilation. Hence, I remove all the libparrots I can find.

Here are commands I executed this last time:

cd /usr/local/src/
mv ~/Downloads/parrot-2.0.0.tar.gz .
tar xvzf parrot-2.0.0.tar.gz 
cd parrot-2.0.0
sudo rm /usr/local/lib/libparrot.*
perl Configure.pl --optimize
gmake
gmake test
sudo gmake install

Not a Num Instance?

2010-01-14T13:02:00.000-05:00

I've presented Haskell code for quadtree-matrix operations addition and multiplication. I implemented these algorithms as an instance of the Num typeclass. Haskell is strongly typed, and type classes provide overloading (a.k.a. ad hoc polymorphism). For example, a numeric type will most likely want to use the + operator. Haskell manages the different definitions of + (one for integers, one for floating-point numbers, one for complex numbers, etc.) through instances the Num class. The Integer type is a Num instance by using an integer addition instruction; the Double type is a Num instance by using a floating-point addition instruction; the Complex type is a num instance by recursively calling + on the real and imaginary components of the complex numbers.

The problem I have with making my Matrix type a Num instance mostly comes down to all of the functions that need to be declared: +, *, -, negate, abs, signum, and fromInteger.

The first three functions can be defined just fine on matrices.
Negating a matrix isn't quite as obvious, but multiplying all of the elements of the matrix by -1 seems reasonable. But is it useful? I doubt it.
What about abs? What is the absolute value of a matrix? There are some possibilities (maybe the determinant), but none are pleasing.
signum (is the number less than, equal to, or greater than zero) is impossible to define in a meaningful way.
fromInteger isn't too bad: turn the integer into a scalar matrix (or the zero matrix).

The Num class only deals with matrix-matrix operations. I would also like to have scalar-matrix and vector-matrix and matrix-vector operations. Implementing a Num instance wouldn't preclude these other types of operations, but it feels a bit awkward to me. (It's worth noting that the Num class forces the operands to + to be the same type, e.g., both matrices, not a matrix and a vector.) I suspect I'll grapple with this issue more as I delve more into bigger, higher level algorithms.

I'm not completely ready to abandon Matrix as an instance of the Num class because of what I might lose. That is, thousands of other Haskell programmers have implemented algorithms that rely solely on the Num type class. For me to plug in my Matrix type without any extra work, I need to implement Matrix as an instance of the Num class.

Matrix-Matrix Multiplication with Quadtrees in Haskell

2010-01-13T13:01:00.000-05:00

The last time I spent a recess break on quadtree matrices, it was mostly to present matrix-matrix addition. Today I present matrix-matrix multiplication.

The Algorithm

C = A * B is often presented at the element level. That is, c_ij is computed by multiplying the elements of row A_i by the elements of column B_j and adding those products together. Wikipedia presents a good description with pictures. The cool thing is that this works at the quadtree level. To compute C_nw, you multiply A_nw by B_nw and A_ne by B_sw, then add those products together.

Instance of the Num Class

instance (Eq a, Num a) => Num (Matrix a) where
  ZeroM * _ = ZeroM
  _ * ZeroM = ZeroM
  ScalarM a * ScalarM b = ScalarM (a*b)
  QuadM (nwA, neA, swA, seA) * QuadM (nwB, neB, swB, seB) =
    normalize $ QuadM (nwA * nwB + neA * swB
                      ,nwA * neB + neA * seB
                      ,swA * nwB + seA * swB
                      ,swA * neB + seA * seB)
  _ * _ = error "invalid arguments"
  -- other Num definitions

Again, normalize is supposed to normalize the representation, making sure all "zero matrices" are represented by a ZeroM. There's a potential bug here if we use numbers very close to zero; multiplying two numbers really close to zero results in a product that's really close to zero. So close, we might want to consider it zero. This is easily fixed by adding a call to normalize in the scalar case.

I actually implemented it a bit differently in my actual code. The difference is in the scalar case:

  QuadM a@(nwA, neA, swA, seA) * QuadM (nwB, neB, swB, seB) =
    normalize $ QuadM $ zipQuads (+) (zipQuads (*) x y) (zipQuads (*) a z)
      where x = (neA, nwA, seA, swA)
            y = (swB, neB, swB, neB)
            z = (nwB, seB, nwB, seB)

There are those zipQuads that I've suggested mean "parallelism!!!". I find the quadrant shuffling here a bit confusing though.

Next time I'll talk about why I dislike implementing the quadtree Matrix type as an instance of the Num class.

Apache Errors on a MacBook

2010-01-11T13:59:00.001-05:00

If the default Apache server on your OS X machine isn't working and if /var/log/apache2/error_log isn't showing any errors, check the Console app. It'll tell you if a configuration file has a syntax error in it. I expected syntax errors to show on the command line when I start/restart (as they do on most Linux systems).

Live and learn. Avoid my pain.

Possibly Useful Use Case for RCapture

2010-01-10T13:10:00.000-05:00

I blogged the other day about a blog post from Christoph Heindl on his new Ruby gem, RCapture. I lamented a bit that I've not found aspect oriented programming to be useful in general, and the debugging and logging use cases are not impressive to me.

However, RCapture might have a use case I can get behind since it takes advantage of Ruby blocks. In developing some of my Ruby libraries, I've tried to deal with constructors that need to take a lot of arguments. Should initialize have fifteen positional parameters? Then I have to remember the order of those parameters. Initialize with an options hash? That makes calling the method more work (unless there are a lot of default values). I've fallen in love with a pattern where initialize yields to the block passed to it, passing in self as an argument. RSpec lets you specify a rake task using this approach:

Spec::Rake::SpecTask.new do |t|
  t.warning = true
  t.rcov = true
end

I like the syntax of this block, and I find myself using this more and more. I get frustrated when a library doesn't define initialize to work this way. But now, RCapture allows me to add it. Suppose my library defines this:

class X
  attr_accessor :name  # and 14 more reader/writer attributes
  def initialize(options={})
    @name = options[:name] || "foobar"
    # 14 other initializations from options
  end
end

All the programmer would have to do is add yield self if block_given? at the end of initialize to make me happy. But instead, I'm stuck using the options hash, and this syntax is not as nice. Until I use RCapture:

require 'rcapture'

class X
  include RCapture::Interceptable
end

X.capture :class_methods => :new do |ci|
  ci.block.call(ci.return) if ci.block
end

jdfrens = X.new do |x|
  x.name = "jdfrens"
end

jdfrens.name  # => "jdfrens"

I get to use the syntax I like. Of course, it's not foolproof. I'm now relying on the default values as specified in initialize before I override them, and if they create objects or do any significant work, that's a problem. I could balance this out by specifying some things in the hash and the others in the block. Also, this trick won't work (easily) for positional parameters; they'll still have to be given as arguments.

This is certainly not a "killer use case" for RCapture, but it makes me wonder what other uses it might have.

Frakkin' Amazing Animation

2010-01-09T13:03:00.001-05:00

Is 12 minutes too long for a recess break on Saturday? Make time for this (HD available on Vimeo, well worth it):

The Third & The Seventh from Alex Roman on Vimeo.

All CG. No really, that's what the person behind this video claims. Certainly some of the scenes at the end are pretty unbelievable, but I challenge you to find a flaw in his trees. Amazing.

If you have the time, check out this compositing breakdown (3 minutes):

Compositing Breakdown (T&S) from Alex Roman on Vimeo.

Aspect Oriented Programming in Ruby

2010-01-08T13:01:00.000-05:00

My Twitter feed delivered this article to me: "Introducing RCapture" by Christoph Heindl. RCapture, without really admitting it, is a library for some basic aspect oriented programming (AOP) in Ruby.

The basic idea behind AOP is that you add aspects to your code which are executed before or after (or during?) existing methods. Aspects are written separately from the original code. Let me use an RCapture example (slightly modified from Heindl's post):

Array.capture_post :methods => [:push] do |cs|
  puts "#{cs.args.first} was pushed to array #{cs.sender}"
end

capture_post is the RCapture method. Called on the Array class, this says that after ("post") the push method is called, the block should be executed. cs, the argument of the block, holds the environment for the method call, which is used in the output message.

The best use cases I've heard for AOP is for logging and debugging. The example above is a debugging example. It would be just as easy to use a logger instead. But why not add the debugging and logging code to Array#push itself? That's the power of AOP: separation of concerns. Separate out the debugging and logging from the business logic. It keeps the code cleaner, and makes the aspected code optional (just don't include that module).

I've played around with AOP, but it's never struck me as something that useful. For my favorite use cases, debugging is better done with a debugger, and logging is not really a terrible clutter in business logic.

The one weakness I see with RCapture is its limited pointcuts language. A pointcut is a description of when and where an aspect is to be triggered. RCapture has the simplest possible: name a class, name some methods, indicate "pre" or "post". AspectJ, an AOP extension to Java, has a very expressive language for pointcuts. For example, execution(* set*(*)) is an AspectJ pointcut for an aspect during the execution of any method that begins with "set" that has one argument of any type and returns a value of any type.

I'm not sure that this is a bad weakness, though. RCapture does have a filter option for refining when an aspect should be triggered. AspectJ's language for pointcuts seems a little too powerful to me, that it'd be too easy to write a pattern that matched too many points.

Barbara Liskov's Turing Award Talk (at OOPSLA)

2010-01-07T13:04:00.000-05:00

Another presentation for you to watch during recess: The Power of Abstraction by Barbara Liskov. Liskov won the Turing Award in 2008. The presentation comes from InfoQ; here's their summary:

In a reprise of her ACM Turing Award lecture, Barbara Liskov discusses the invention of abstract data types, the CLU programming language, clusters, polymorphism, exception handling, iterators, implementation inheritance, type hierarchies, the Liskov Substitution Principle, polymorphism, and future challenges such as new abstractions, parallelism, and the Internet.

CLU. Much of the talk is a historical account of why and how CLU came about. I get the feeling that the 1970s were a really heady time for programming languages based on the papers she listed as motivation (including Djikstra's "GOTO Statement Considered Harmful", see a near-complete list of papers collected Ralph Johnson).

CLU did have some interesting features (for the early 1970s): exception handling and iterators. I wish I had been taught exception handling from the very beginning since it's such as easier way to handle edge cases. And I hate FORTRAN and C for foisting their counting for loops on us for array processing; I much prefer iterators.

Reading Programs. One observation she made, more than once at different times in the talk and during the Q&A, in the 1970s it was important to make programs easier to write, but today we must make programs easier to read. (Based on how strongly she felt about this, I'm not surprised that CLU's syntax is no longer used... not readable!) I've heard this "code must be readable" more and more, especially from the Ruby community. It was nice hearing Liskov reiterating this issue from a historical perspective.

LSP. Liskov then spends some time on the Liskov Substitution Principle (LSP). She makes a very important observation: inheritance is used for two different things, (1) implementation and (2) type hierarchies. At the time she wrote her paper, people were really confused over type hierarchies; someone wrote a paper that said stacks and queues were subtypes of a common type! The base type had "add" and "remove" actions; the stack and queue implementations would do their own things. Based on the LSP, the cumulative behaviors of "add" and "remove" are very different (e.g., add two items, remove one, different answers!), and so this overabstraction is judged invalid. Fortunately, it seems really odd to me now that people were confused over this.

I've blogged briefly on the implementation violation of LSP ("Square Does Not Extend Rectangle!"), and it bugs me how often I encounter this type of violation, at least when I was in the academic world. There's a question at the very end of the Q&A session directly on this point. A recent graduate commented that she had been taught the bad hierarchy in class, and she was set straight at an internship. Liskov describes what she does at MIT (teaching LSP in a second semester course in Java), but she didn't address the issue of how to stop these evil professors and textbook authors from foisting yet another shape or employee hierarchy on students.

It's a good talk, and if you have 80 minutes to spend, it's worth your time.

Eat Some More Cucumbers

2010-01-06T12:01:00.000-05:00

Here's yet another presentation on Cucumber, a DSL and framework for acceptance tests. This comes from Joseph Wilk (from the Cucumber core) at FutureRuby.

If you haven't heard the elevator pitch for Cucumber yet, shame on you. Remedy this by watching this relatively short intro (30 minutes).

He reminded me of something: Cucumber works with JRuby and therefore the JVM. I'm wondering how difficult this would be for some of my Java projects...

Cucumber Features in Folders

2009-12-26T12:56:00.001-05:00

For today's recess break, I'm thinking about organizing my Cucumber tests in a Ruby on Rails project.

The webapp has a user system to keep the riffraff from changing content they have no right to change. I'm using Cucumber for my acceptance tests, and while I only have 15 features files so far, more are likely.

Folder Organization

I can (apparently) create subfolders in my features folder to organize them better. So my question is this: organize them by type of user (administrator versus guest) or by controller?

By user? Won't it help me mentally separate the two different roles?

By controller? This is how the rest of the Rails app is organized, especially the app/views folder.

I'm inclined to organize by controller. Usually I'm working on one controller at a time, switching between the different types of users.

Granularity of Features

When is a feature file too big? When do you split a feature file up? How?

Splitting based on users is required by the role and purpose in the opening narrative. Might one split based on RESTful actions? That seems too fine grained, although if there a lot of sad paths, a split or two might be prudent as well.

Terminology

Is anyone else bothered by my use of "folder" instead of "directory"? Seventeen years of teaching college students who didn't want to learn basic computer usage or "already knew it" has forced me to look for the best metaphors. "Directory" means nothing to them. "Folder" does.

Original Quadtree-Matrix Algorithms

2009-12-23T17:11:00.001-05:00

For this recess break, I'm going to present the quadtree-matrix algorithm for matrix-matrix addition.

Thinking about the Quadtree-Matrix Algorithm

To add two matrices, you add the elements component-wise. Same thing with quadtree matrices, although you base your definition on the recursive definition of a quadtree matrix:

If either matrix is zero, return the other.
If they're both scalars, return their sum.
Otherwise, add the northwest, northeast, southwest, and southeast quadrants recursively, and return those sums as a new quadtree matrix.

Haskell's `Num` Class

Haskell has classes. Just like Java and most object-oriented languages. And completely unlike them. I'm not going to get into the nitty-gritty of type classes in Haskell in this recess break, but suffice it to say that it allows one to overload operators, like +.

Algorithm Implemented as Part of `Num` Instance

Here's the code. I'll deconstruct it below.

instance (Eq a, Num a) => Num (Matrix a) where
  ZeroM + m = m
  m + ZeroM = m
  ScalarM a + ScalarM b = normalize $ ScalarM (a+b)
  QuadM a + QuadM b = normalize $ QuadM $ zipQuads (+) a b
  _ + _ = error "invalid arguments"
  -- many other Num definitions omitted

normalize (ScalarM 0) = ZeroM
normalize (QuadM (ZeroM, ZeroM, ZeroM, ZeroM)) = ZeroM
normalize q = q
 
zipQuads f (nw1, ne1, sw1, se1) (nw2, ne2, sw2, se2) =
  (f nw1 nw2, f ne1 ne2, f sw1 sw2, f se1 se2)

You can see a fuller implementation in Quadtree.hs from an early commit in my GitHub repository.

I'm not going to explain much of this code. (I'll do that in future recess breaks.) Let me point out the highlights:

instance Num (Matrix a) means that a Matrix is an instance of the Num type class, and we have to write a version of + for Matrixs.
The definition of + uses pattern matching. Instead of asking the first argument if it's zero with a predicate, I write what looking like an actual invocation: ZeroM + m = m.
ScalarM and QuadM are type constructors. they construct (and pattern match) Matrixs. So ScalarM a + ScalarM b is a pattern for "If the two arguments are scalars...". ScalarM (a+b) constructs a new Matrix consisting of the sum of the two scalars.
The normalize function normalizes non-standard representations of zero like ScalarM 0 and QuadM (ZeroM, ZeroM, ZeroM, ZeroM).
zipQuads applies a function to the quadrants of two general quadtree matrices, quadrant-wise. Generally, when you see map and zip in a functional language, think: "This could be done in parallel!"

Now we can quibble about Haskell syntax and all that, but this Haskell code seems more straightforward to me than the nested loops we write for row/column thinking in C/C++/Java. And I get parallelism "for free" with the use of zipQuads.

I'll spend some time exploring the Haskellisms in this code, in particular: the syntax and the Num class (and why I don't like it for my quadtree matrix). And I'm going to have to justify calling Haskell's type classes similar to Java classes.

Quadtree Matrices

2009-12-22T14:03:00.001-05:00

Matrices

I'm going to assume that you know what a matrix is. (Insert stupid "not a virtual reality created by robot overlords" and "not a Gallifreyan computer for Time Lord memories" jokes here.) If you need a refresher, look up matrix at Wikipedia.

The important thing to know for this recess break is that matrices are a grid of numbers (or other algebraic entities like polynomials).

Quadtrees

The Wikipedia article on quadtrees focuses mostly on geometry applications. The data structure is the same as for matrices, it's just a matter of what's stored at the leaves.

Quadtree Matrices

Quadtree matrices are recursive. The simple base case is that a single number, a scalar, is a quadtree matrix, a leaf node.

The general, recursive case is to take a general matrix, and split it into quadrants: split the matrix in half horizontally and vertically. Consider this example from my dissertation:

Look how the quadrant in the upper left, what we call the northwest quadrant, is found as the first subtree of the quadtree. The northwest quadrant of that quadrant (the 2.1) is the first subsubtree of the subtree. Similarly, the northeast quadrant is second, followed by the southwest and southeast.

This example also demonstrates what we do with matrices that aren't easily chopped in half all the way down. We'd like every matrix to have an order which is a power of 2, but that's just not going to happen. Instead, we pad out each matrix with zeros on the east and south to get the order to a power of 2. In the example above, it means only adding one column and one row of zeros, but in general many columns and rows of zeros may be added. But notice in this example that the 0.0 scalars in the original matrix are turned into special leaf nodes, labeled "Z" for "zero", of course. While all scalars will appear on the same level of the quadtree matrix, a zero leaf can appear anywhere (as another base case), and the space we use is only a log (base 2) compared to storing all of the raw 0.0s.

Haskell Code

We represent a quadtree matrix in Haskell as an algebraic type.

data Matrix a = ZeroM | ScalarM a |
  QuadM (Matrix a, Matrix a, Matrix a, Matrix a)
    deriving (Show, Eq)

As described above, a quadtree matrix is either a zero matrix, a scalar matrix, or a quadtree node of four quadtree matrices.

The Power of Metaphor

2009-12-19T09:00:00.000-05:00

Today's recess break (if I can use my own metaphor for my blog) is a TED talk that was just released about metaphors:

Just about every TED video is worth watching, but this one has some implications for Extreme Programming and good programming in general. One of the XP practices is picking a good metaphor for your code. In this TED talk, James Geary revels in the power of metaphor.

One observation that shook me up: we have a hard time denying a metaphor even if it's literally false. Geary gives this as an example: "Some jobs are jails." It's literally false, but for some of us it's very metaphorically true. To recognize and say that it's literally false takes some time and effort. (More time and effort than it takes to say that "Some squares are round" is false.)

Now I don't think we have to worry about literal-versus-metaphorical truthiness in our programming, but this shows how very important and powerful metaphors are.

Installing Passenger on My MacBook

2009-12-18T12:45:00.003-05:00

I'd like to play around with Passenger on my MacBook, running Snow Leopard and MacPorts. Passenger is an Apache module for Ruby on Rails apps; it's supposed to make deploying a breeze. But I can't get it installed.

The Problem

When I install the Passenger module for Apache, I get this output:

Checking for required software...

 * GNU C++ compiler... found at /usr/bin/g++
 * Ruby development headers... found
 * OpenSSL support for Ruby... found
 * RubyGems... found
 * Rake... found at /opt/local/bin/rake
 * rack... found
 * Apache 2... found at /usr/sbin/httpd
 * Apache 2 development headers... found at /usr/sbin/apxs
 * Apache Portable Runtime (APR) development headers... found at /usr/bin/apr-1-config
 * Apache Portable Runtime Utility (APU) development headers... found at /usr/bin/apu-1-config

--------------------------------------------
Compiling and installing Apache 2 module...
cd /opt/local/lib/ruby/gems/1.8/gems/passenger-2.2.8
/opt/local/bin/ruby -S /opt/local/bin/rake clean apache2
# /opt/local/bin/ruby -S /opt/local/bin/rake clean apache2
(in /opt/local/lib/ruby/gems/1.8/gems/passenger-2.2.8)
rm -rf ext/apache2/libboost_oxt.a ext/apache2/libboost_oxt
rm -rf ext/apache2/libpassenger_common.a ext/apache2/ApplicationPoolServerExecutable ext/apache2/libpassenger_common
rm -rf ext/apache2/Configuration.o ext/apache2/Bucket.o ext/apache2/Hooks.o ext/apache2/mod_passenger.o ext/apache2/mod_passenger.so
rm -rf ext/nginx/libboost_oxt.a ext/nginx/libboost_oxt
rm -rf ext/nginx/libpassenger_common.a ext/nginx/libpassenger_common
rm -rf ext/nginx/HelperServer
rm -rf test/libboost_oxt.a test/libboost_oxt
rm -rf test/libpassenger_common.a test/ApplicationPoolServerExecutable test/libpassenger_common
rm -rf test/oxt/oxt_test_main test/oxt/*.o test/CxxTests test/*.o
rm -r pkg
cd ext/phusion_passenger && make clean
rm -f ext/phusion_passenger/Makefile
mkdir -p ext/apache2/libpassenger_common
g++ -Iext -Iext/common -fPIC -DDARWIN -DSIGPROCMASK_SETS_THREAD_MASK -I/usr/include/apr-1 -I/usr/include/apr-1 -I/usr/include/apache2 -arch i386 -arch ppc -arch x86_64 -arch ppc64 -D_REENTRANT -I/usr/local/include -Wall -g -DPASSENGER_DEBUG -DBOOST_DISABLE_ASSERTS -o ext/apache2/libpassenger_common/Utils.o -c ext/common/Utils.cpp
In file included from ext/boost/config/no_tr1/utility.hpp:21,
                 from ext/boost/config/select_stdlib_config.hpp:20,
                 from ext/boost/config.hpp:40,
                 from ext/boost/thread/detail/platform.hpp:14,
                 from ext/boost/thread/tss.hpp:9,
                 from ext/oxt/system_calls.hpp:28,
                 from ext/common/Utils.cpp:26:
/usr/include/c++/4.2.1/utility:65:28: error: bits/c++config.h: No such file or directory
In file included from /usr/include/c++/4.2.1/bits/stl_algobase.h:70,
                 from /usr/include/c++/4.2.1/memory:53,
                 from ext/boost/shared_ptr.hpp:23,
                 from ext/boost/thread/pthread/tss.hpp:10,
                 from ext/boost/thread/tss.hpp:13,
                 from ext/oxt/system_calls.hpp:28,
                 from ext/common/Utils.cpp:26:
/usr/include/c++/4.2.1/iosfwd:45:29: error: bits/c++locale.h: No such file or directory
/usr/include/c++/4.2.1/iosfwd:46:25: error: bits/c++io.h: No such file or directory
In file included from /usr/include/c++/4.2.1/memory:54,
                 from ext/boost/shared_ptr.hpp:23,
                 from ext/boost/thread/pthread/tss.hpp:10,
                 from ext/boost/thread/tss.hpp:13,
                 from ext/oxt/system_calls.hpp:28,
                 from ext/common/Utils.cpp:26:
/usr/include/c++/4.2.1/bits/allocator.h:53:31: error: bits/c++allocator.h: No such file or directory
In file included from /usr/include/c++/4.2.1/bits/basic_string.h:46,
                 from /usr/include/c++/4.2.1/string:54,
                 from ext/common/CachedFileStat.hpp:35,
                 from ext/common/Utils.cpp:34:
/usr/include/c++/4.2.1/ext/atomicity.h:39:23: error: bits/gthr.h: No such file or directory
/usr/include/c++/4.2.1/ext/atomicity.h:40:30: error: bits/atomic_word.h: No such file or directory
In file included from /usr/include/c++/4.2.1/bits/basic_ios.h:44,
                 from /usr/include/c++/4.2.1/ios:50,
                 from /usr/include/c++/4.2.1/ostream:45,
                 from /usr/include/c++/4.2.1/iterator:70,
                 from ext/boost/next_prior.hpp:15,
                 from ext/boost/utility.hpp:16,
                 from ext/boost/thread/pthread/thread.hpp:12,
                 from ext/boost/thread/thread.hpp:17,
                 from ext/boost/thread.hpp:12,
                 from ext/common/SystemTime.h:28,
                 from ext/common/CachedFileStat.hpp:39,
                 from ext/common/Utils.cpp:34:
/usr/include/c++/4.2.1/bits/locale_facets.h:47:30: error: bits/ctype_base.h: No such file or directory
/usr/include/c++/4.2.1/bits/locale_facets.h:1533:31: error: bits/ctype_inline.h: No such file or directory
/usr/include/c++/4.2.1/bits/locale_facets.h:3040:33: error: bits/time_members.h: No such file or directory
/usr/include/c++/4.2.1/bits/locale_facets.h:4599:37: error: bits/messages_members.h: No such file or directory
In file included from /usr/include/c++/4.2.1/utility:66,
                 from ext/boost/config/no_tr1/utility.hpp:21,
                 from ext/boost/config/select_stdlib_config.hpp:20,
                 from ext/boost/config.hpp:40,
                 from ext/boost/thread/detail/platform.hpp:14,
                 from ext/boost/thread/tss.hpp:9,
                 from ext/oxt/system_calls.hpp:28,
                 from ext/common/Utils.cpp:26:
/usr/include/c++/4.2.1/bits/stl_relops.h:74: error: expected constructor, destructor, or type conversion before ‘(’ token
In file included from /usr/include/c++/4.2.1/new:45,
                 from /usr/include/c++/4.2.1/bits/stl_construct.h:65,
                 from /usr/include/c++/4.2.1/memory:55,
                 from ext/boost/shared_ptr.hpp:23,
                 from ext/boost/thread/pthread/tss.hpp:10,
                 from ext/boost/thread/tss.hpp:13,
                 from ext/oxt/system_calls.hpp:28,
                 from ext/common/Utils.cpp:26:
/usr/include/c++/4.2.1/exception:40: error: expected declaration before end of line
lipo: can't figure out the architecture type of: /var/tmp//ccPAGdXv.out
rake aborted!
Command failed with status (1): [g++ -Iext -Iext/common -fPIC -DDARWIN -DSI...]
/opt/local/lib/ruby/gems/1.8/gems/passenger-2.2.8/Rakefile:172:in `define_common_library_task'
(See full trace by running task with --trace)

--------------------------------------------

It looks like something went wrong

Please read our Users guide for troubleshooting tips:

   /opt/local/lib/ruby/gems/1.8/gems/passenger-2.2.8/doc/Users guide Apache.html

If that doesn't help, please use our support facilities at:

   http://www.modrails.com/

We'll do our best to help you.

I'm using the defaults from Apple except for Ruby and rake; they come from MacPorts. The error messages seems to be a problem with the system g++.

They're Not Missing

For the record, the "missing" headers files are not missing:

$ locate bits/c++config.h
/Developer/SDKs/MacOSX10.5.sdk/usr/include/c++/4.0.0/i686-apple-darwin9/bits/c++config.h
/Developer/SDKs/MacOSX10.5.sdk/usr/include/c++/4.0.0/powerpc-apple-darwin9/bits/c++config.h
/Developer/SDKs/MacOSX10.5.sdk/usr/include/c++/4.0.0/powerpc64-apple-darwin9/bits/c++config.h
/Developer/SDKs/MacOSX10.5.sdk/usr/include/c++/4.0.0/x86_64-apple-darwin9/bits/c++config.h
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.0.0/i686-apple-darwin10/bits/c++config.h
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.0.0/powerpc-apple-darwin10/bits/c++config.h
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.0.0/x86_64-apple-darwin10/bits/c++config.h
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/i686-apple-darwin10/bits/c++config.h
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/powerpc-apple-darwin10/bits/c++config.h
/Developer/SDKs/MacOSX10.6.sdk/usr/include/c++/4.2.1/x86_64-apple-darwin10/bits/c++config.h
/opt/local/include/gcc43/c++/x86_64-apple-darwin10/bits/c++config.h
/opt/local/var/macports/software/gcc43/4.3.4_0/opt/local/include/gcc43/c++/x86_64-apple-darwin10/bits/c++config.h
/usr/include/c++/4.0.0/i686-apple-darwin10/bits/c++config.h
/usr/include/c++/4.0.0/powerpc-apple-darwin10/bits/c++config.h
/usr/include/c++/4.0.0/x86_64-apple-darwin10/bits/c++config.h
/usr/include/c++/4.2.1/i686-apple-darwin10/bits/c++config.h
/usr/include/c++/4.2.1/powerpc-apple-darwin10/bits/c++config.h
/usr/include/c++/4.2.1/x86_64-apple-darwin10/bits/c++config.h
/usr/local/nacl/googleclient/native_client/tools_bin/mac/sdk/nacl-sdk/nacl/include/c++/4.2.2/nacl/bits/c++config.h

gcc might not be configured to use those directories, though (which does qualify as missing). When I did a Google search for the error message, I get references to a "boost" library, but most of the hits are in a foreign language and seem to have nothing to do with Passenger.

Try a Different gcc?

If MacPorts is good for Ruby and rake, why not gcc? First, gcc-4.2 doesn't install on Snow Leopard.

Second, gcc-4.3 does install, but results in this error message:

mkdir -p ext/apache2/libpassenger_common
g++ -Iext -Iext/common -fPIC -DDARWIN -DSIGPROCMASK_SETS_THREAD_MASK -I/usr/include/apr-1 -I/usr/include/apr-1 -I/usr/include/apache2 -arch i386 -arch ppc -arch x86_64 -arch ppc64 -D_REENTRANT -I/usr/local/include -Wall -g -DPASSENGER_DEBUG -DBOOST_DISABLE_ASSERTS -o ext/apache2/libpassenger_common/Utils.o -c ext/common/Utils.cpp
cc1plus: error: unrecognized command line option "-arch"
cc1plus: error: unrecognized command line option "-arch"
cc1plus: error: unrecognized command line option "-arch"
cc1plus: error: unrecognized command line option "-arch"

This might just need a tweak of the Passenger rakefile.

Third, I tried LLVM gcc-4.2:

g++ ext/common/ApplicationPoolServerExecutable.cpp -o ext/apache2/ApplicationPoolServerExecutable -Iext -Iext/common  -fPIC -DDARWIN -DSIGPROCMASK_SETS_THREAD_MASK -I/usr/include/apr-1 -I/usr/include/apr-1 -I/usr/include/apache2 -arch i386 -arch ppc -arch x86_64 -arch ppc64 -D_REENTRANT -I/usr/local/include -Wall -g -DPASSENGER_DEBUG -DBOOST_DISABLE_ASSERTS ext/apache2/libpassenger_common.a ext/apache2/libboost_oxt.a  -lpthread 
ld: warning: in /usr/lib/crt1.10.5.o, missing required architecture ppc64 in file
ld: warning: in /usr/lib/libpthread.dylib, missing required architecture ppc64 in file
ld: warning: in /Developer/usr/llvm-gcc-4.2/lib/gcc/powerpc-apple-darwin10/4.2.1/libstdc++.dylib, missing required architecture ppc64 in file
ld: warning: in /Developer/usr/llvm-gcc-4.2/lib/gcc/powerpc-apple-darwin10/4.2.1/libgcc.a, file is not of required architecture
ld: warning: in /usr/lib/libSystemStubs.a, missing required architecture ppc64 in file
ld: warning: in /usr/lib/libSystem.dylib, missing required architecture ppc64 in file
Undefined symbols for architecture ppc64:
  # deleted 6853 lines of error messages

No, that's not a typo. Six-thousand eight-hundred fifty-three lines of error messages! Awesome. I mean, I didn't expect it to work, but... wow.

Things I'm Left Trying...

As I write this, I'm compiling the boost library with MacPorts. I don't think this will help with the Apple-installed gcc, and boost wasn't a problem for any of the MacPort-installed compilers, so I don't think this will do me any good. Update: it didn't help.

The only other thing I can think to try is to get rid of the -arch option in the compilation command.

I'll post any fixes or further frustrations as they arise.

Going Back to My Dissertation

2009-12-16T14:50:00.001-05:00

My dissertation was on quadtree matrices.

The quadtree entry in the Wikipedia provides maybe one sentence about "quadtree matrices". And it's probably my fault there isn't more since I'm one of about a dozen people in the world who has published papers on quadtree matrices. So I'm going to spend a blog entry or two introducing the topic. (Maybe I can turn this introduction into a Wikipedia article.)

I'm motivated to do this now because I've returned to the Haskell code that started my quadtree-matrix work. I'm coming across issues as I'm relearning and perfecting my Haskell skills, and discussing problems like these on my blog has helped me in the past.

So, hopefully, I'll have a series of posts about my adventures in Haskell, implementing quadtree matrices and some interesting algorithms.

Testing Redirection and Rewrite Rules with RSpec

2009-07-08T15:50:00.002-04:00

One the websites that I maintain has quite a few interesting Redirect and RewriteRules in its Apache configuration. Up until yesterday, I was testing them with Selenium; today I'm testing with RSpec.

The website is for the Computer Science department at Calvin. Most of it is a Rails app for a CMS. However, there were portions of the old site that I wanted to leave in the hands of my former colleagues; there were other paths into the site that needed to be redirected.

Selenium, Not Such a Good Idea for This Problem

I really like Selenium for writing website tests in a browser, and I've seen how useful it can be for developing Rails apps. I applied it to this rewrite-and-redirect problem, and it was more than a bit of overkill. In my role as "website developer", I just needed to make sure the redirects were in place. With Selenium, though, I found myself testing other features, like content on pages or in directories that I wasn't really in charge of.

The Selenium tests also ran slow since it used Firefox itself to access the website.

I also found the tests hard to maintain. This is mostly on me because I saved and edited them in an HTML format. It would have been better to use Ruby. But if I was going to rewrite the tests in a format that was easier to use, why not also go for something faster and more targeted?

Ruby and RSpec

Ruby has libraries to access URLs through HTTP... core libraries. I can write expectations in RSpec. I can write expectations about the HTTP responses.

This was all theoretically possible until I came across "Test Drive mod_rewrite Rules with Test::Unit" by Patrick Reagan. Someone had done it already (as I figured) with Test::Unit. Instead of using Patrick's solution wholesale, I decided to tailor it more towards my needs, especially towards RSpec.

My mod_rewrite Expectations with RSpec

Here's what one of my expectations looks like:

it "should redirect curriculum pages" do
  get("/curriculum/bcs.php").should redirect_to("/p/bcs")
  get("/curriculum/bacs.php").should redirect_to("/p/bacs")
  get("/curriculum/bais.php").should redirect_to("/p/bais")
  get("/curriculum/bada.php").should redirect_to("/p/bada")
end

We had a few pages for the the different computing degrees at Calvin College: an ABET-accredited Bachelor's of Computer Science and plain BAs in Computer Science, Information Systems, and "Digital Arts". We definitely wanted all links to the old pages go to the new.

get(path) is my method:

def get(url)
  RedirectCheck.new(ResourcePath.new("http://cs.calvin.edu" + url))
end

Yes, I've hard-coded the server in this test. It keeps the rest of the code simpler, and it solves the problem I have now.

The two classes used here are based on classes of the same name by Patrick. You can see my versions in the GitHub repository. I mostly just simplified the code for my purposes.

The really important class is RedirectCheck. It accesses the URL, saves the response, and then parses it for queries like success? and redirect? and redirected_path.

success? allowed me to write expectations like this without any extra work:

it "should have a books activity" do
  get("/activities/books/").should be_success
  get("/a/books/").should be_success
end

redirect? and redirect_path make the redirect_to(path) matcher easy:

Spec::Matchers.define :redirect_to do |redirection|
  match do |redirect_check|
    redirect_check.redirected?.should == true
    redirect_check.redirected_path.should == redirection
  end
end

For some reason, redirect_check.should be_redirected triggers an undefined error for be_redirected.

redirection is the redirection path (i.e., the expected path). redirect_check is a RedirectCheck object created by get(path).

Performance

It takes about 3 seconds to run 15 examples, so it's not the speediest RSpec suite around (by a long shot). But these aren't tests to be run often. Plus, the original Selenium tests never ran that fast!

So, given the problem I was trying to solve, I really like this solution. It'll be easy to add more expectations if I need to. It's really easy to run them, too. I'll save Selenium for a problem that really requires it!

Converting from Test::Unit to RSpec in a Rails App

2009-07-06T12:52:00.001-04:00

I'm going to write my process turning the Test::Unit tests into RSpec examples for another Rails app in realtime. The app is called "YAGS" (Yet Another Genetics Simulatr), for simulating the genetics of fruit flies for a college-level biology course. I did this transformation once before; this app is a little bit more than a CMS for my former CS department.

My post for the department CMS transformation was organized topically. I'm organizing this one chronologically.

Measure the State of the App

# unit tests
124 tests, 758 assertions, 0 failures, 0 errors
Test suite finished: 5.091451 seconds
# functional tests
164 tests, 1311 assertions, 0 failures, 0 errors
Test suite finished: 6.700129 seconds
# integration tests?! we don't need no stinkin' integration tests!

Install RSpec and RSpec-Rails in the App

While I'm at it, I think I'll also get Cucumber set up. (The last time in my "state of the app" is a lie; everyone needs integration tests!)

I drop these into my config/environments/test.rb file:

config.gem "rspec", :lib => false, :version => ">= 1.2.7"
config.gem "rspec-rails", :lib => false, :version => ">= 1.2.7"
config.gem "aslakhellesoy-cucumber", :lib => "cucumber", :version => ">= 0.3.11"
config.gem 'webrat'

These may be useful for a limited time only (especially getting cucumber from GitHub). I run these shell commands:

# I don't bother to install since I know they're installed
rake gems:unpack RAILS_ENV=test
rake gems:unpack:dependencies RAILS_ENV=test
./script/generate rspec
./script/generate cucumber

Question for Rails experts: with the gems tasks (like install and unpack), is it necessary or even desirable to add the gems to version control? Can't you have your deploy script do the installing and unpacking? I'd really appreciate feedback on this.

I run the spec and features tasks, and they both run without errors. Cucumber at least reports "0 scenarios, 0 steps"; RSpec is mute.

Copying Tests Over

mkdir spec/models
mkdir spec/controllers
mkdir spec/views
mkdir spec/fixtures
cp test/unit/*.rb spec/models/
cp test/functional/*.rb spec/controllers/
cp test/fixtures/*.yml spec/fixtures/

I have to make the directories because I haven't generated any examples for RSpec directly. When I finish with these steps, I discover why the spec task didn't seem to do anything: it didn't find any specs because the filenames of specs end in _spec.rb, not _test.rb. I wish I could give a command-line solution for this, but I haven't been able to find a way to get mmv (multiple mv) installed on my Mac. Coincidentally, I just discovered NameChanger today, and it does a very nice job at renaming the files.

I suppose this might work:

# run in spec/models, spec/controllers
for i in *_test.rb; do
  mv $i ${i%%_test.rb}_spec.rb
done

(After I finished the whole Test::Unit-to-RSpec transformation, I discovered that mmv is available in MacPorts! The name of the packge is mmv. I'm too lazy now to figure out what the right mmv command would be, but it's not to hard to figure out.)

Can't Find Test Helpers

no such file to load -- ./spec/controllers/../test_helper (LoadError)

That's because they're spec helpers now!

I use RubyMine's "Search > Replace in Path..." to replace the test_helper requires with spec_helper requires.

I know the next problem: helpers that I haven't copied over to spec_helper!

nokogiri Gem Acting Up

Two minutes later... I'm wrong, of course! I'm not having troubles with the helper methods yet. I'm having troubles with nokogiri and/or webrat. The basic error message is this:

no such file to load -- nokogiri/nokogiri

The spec task also spits out a lengthy stack trace and concludes that webrat isn't installed. Well, newsflash! webrat is installed, and so is nokogiri. But there isn't a lib/nokogiri/nokogiri.rb file anywhere that makes sense out of the error message. Even more frustrating, my other Rails app isn't having a problem with webrat and nokogiri

There is, however, a difference between the two apps: I do not have webrat and nokogiri in vendor/gems in the CMS app. They have been unpacked in the YAGS app.

rm -rf vendor/gems/webrat-0.4.4
rm -rf vendor/gems/nokogiri-1.3.2

Problem solved. I won't say I'm happy with the solution since it begs the question why it works, but webrat (and Cucumber) have been in enough flux lately that I don't worry if I have to do something out of the ordinary to get them to work for a while. As far as "out of the ordinary" goes, deleting the gems from vendor/gems isn't going to cause me to lose any sleep.

And I get my predicted error: methods defined in test_helper.rb that aren't in spec_helper.rb.

Adding to Spec helpers

I start moving methods over. One bad thing we did in test_helper.rb was to define the helper methods at the top level. So I'm putting them into modules, and then using config.extend and config.include for class and instance methods, respectively. (I believe I learned about this from the RSpec book. There should be documentation online for this as well.)

One thing I notice is that I'm not requiring webrat in spec_helper.rb, and I did require it explicitly in my CMS app. Requiring in the YAGS app doesn't revert me to the nokogiri/nokogiri error from before, so I'll leave the require in.

However, I get one method moved over, and suddenly I'm getting a complaint about shoulda's should_have_many.

Shoulda Gem with RSpec and Test::Unit

undefined method `should_have_many' for UserTest:Class

After fighting with this for a while, here's what I've figured out. The excellent shoulda gem is being loaded; the context method works just fine. So it's not a load path problem or other directory issue. Poking around in the code, shoulda.rb itself asks this question: defined? Spec and loads different libraries depending on what you pick. That is, you can have shoulda code for RSpec or Test::Unit, but not both!

Keep in mind that while I'm converting to RSpec, the tests themselves are still very much in a Test::Unit form. RSpec is supposed to handle them without too many problems.

Perhaps there are some games I could play with requiring files myself, but I'm not sure how compatible the RSpec and Test::Unit versions are, and I figure: why not start the true coversion to RSpec now? So I end up moving the should_have_many assertion to a new describe block:

describe User do
  it { should have_many :vials }
end

I also drop the underscore between should and have_many. (I'm fudging a bit on the chronology here because iI discovered this problem later.) I'm actually not sure if the describe block is completely necessary after this change, but since I want to move in that direction anyway, I'm going to keep going in that direction.

I keep this in the same file as the Test::Unit test case. Works fine, and so I go on to fix all of these shoulda problems.

`should` Is a Reserved Word

Well, not really, of course. Actually, the problem is that both shoulda and RSpec have it as a "reserved word", but the meaning is different. (I suppose this might be a definition of a Object- or Kernel-level method: a keyword whose meaning can be changed. It should (pardon the pun) be treated as a keyword, but it's meaning can be changed due to which class it's added to.)

All the old shoulda tests that use should "X" have to be turned into it "should X". Time for Replace in Path again!

There are only a few to change, and now finally the specs all run and 186 out of 288 fail! It appears I have more methods to move to spec_helper.

Smelly Code

Along the way, I discover that some of the helper methods are quite stinky. Or some of the tests that they "inspire" are quite stinky. The biggest stink comes from black-box testing the associations and their dependencies. That is, for example, we had tests that would use the fixture data to make sure the right vial had the right flies in it. And if we deleted that vial, the right flies would also go. shoulda and RSpec make this much easier:

it { should have_many(:flies).dependent(:destroy) }

It reads short and sweet, and it doesn't involve any data checking.

Finishing Is Only the Beginning

How poetic. Gag!

287 examples, 0 failures, 287 passed
Finished in 12.497872 seconds

If you look at where I started with my tests, there were 288 unit and functional tests. I've added some new ones, and deleted old ones, so 287 examples sounds pretty good to me.

I'm not finished with the conversion, of course. I've discovered quite a few unit tests for models that still have only their default "test true" stub! Also I plan to separate the controller and view examples; this I typically do when needed though.

I need one set of view examples soon: I "ignored" a assert_standard_layout helper method. This method did a lot of looking at the HTML generated by the standard layout. It gets called several times throughout the tests. This was always overkill, but it seemed like a good idea to me to make sure that each action was using the standard layout and wasn't screwing it up. RSpec allows one to separate out the rendering from the controlling, so for the RSpec examples, for the time being, I just wrote a version of the method that does nothing. I need to write targeted view examples that will make the same assertions about the standard layout and then not worry about the standard layout anywhere else in the examples.

Biggest Mistake

Realistically, this isn't a huge mistake, but it was sloppy: I forgot to create a git branch for all of this work; I've been doing it all on master! Consequently, I've been afraid to make commits along the way since I try to keep the master green on every commit (or merge).

Worse yet, I realized this mistake somewhat early on, and did nothing about it. I believe that there are ways to stash what you're working on, create a new branch, and use the stash on the new branch. (I believe it's even git-stash that let's you do this.) Even if that didn't work, would it have been so terrible to revert all of my changes, create a new branch, and start over from scratch? Even if I did that now, would it be that much work?

Empirical Evidence: Learn Haskell

2009-07-03T11:03:00.001-04:00

I read this morning an article by Lera Boroditsky, "How Does Our Language Shape the Way We Think?". Very interesting read.

I've often wondered if I should have become a linguist instead of a computer scientist (or mathematician). One idea that's intrigued me is the Sapir-Whorf hypothesis. According to that Wikipedia article (as of today), the hypothesis is

the idea that the varying cultural concepts and categories inherent in different languages affect the cognitive classification of the experienced world in such a way that speakers of different languages think and behave differently because of it.

Boroditsky's article suggests that there is something to the Sapir-Whorf hypothesis. The Wikipedia article (which I only scanned), seems to agree. The lingering questions, though, are how does it work and to what degree does it apply?

I've been interested in the hypothesis when teaching a Programming Languages course. Students will often complain about having to learn Scheme, Haskell, or Prolog (when they've been raised on Java and C++). The recursion in these languages is often a serious shift for the students (especially when other instructors tell them that they don't get recursion). Haskell has the extra "hassle" of a type system that's unlike type systems they've seen before. And Prolog is completely declarative, and even I find the data flow tricky.

Too often, if students talk about learning a new language, they're really looking to learn an old language with a new syntax. For the record, these are all pretty much the same language: Java, C++, C, PHP, Perl, C#, etc. While learning a couple of these will certainly improve a resume, it won't really make you a better programmer, just better skilled.

Scheme and Haskell made me think differently, especially Haskell. I picked up a LISP book when I was in high school, and I actually understood most of it (without running any of the code). Learning Scheme in grad school made me realize how deficient that LISP book was. Haskell made me appreciate composing functions, type systems, and pattern matching. Prolog got me into a declarative state of mind.

It'll be interesting to see where languages like Ruby and Python take us. I'd label both of these as "object-oriented languages with strong functional-programming influences". Can programmers learn the FP features? Will they embrace them? Would learning Scheme or Haskell first help? Hurt?

Well, whatever you think about these larger issues, read Boroditsky's article.

Upgrading Rails 1.2 to 2.3

2009-07-01T09:44:00.003-04:00

While I reel from the terrible error in my previous post, I thought I'd post about my recent experience updating a Rails app from version 1.2 to 2.3. (BTW, the error is Andy's last name. I'm still right about the anti-if campaign.)

I had a real fun time upgrading a Rails app for my department's website (now on GitHub), and by "real fun time" I mean "lots of pain and suffering". More recently (like this past March) I discovered this wonderful guide by Peter Marklund. So when I went to upgrade a second app (also on GitHub), I went through his process.

Let me say this up front: I'm quite sure that Peter's instructions will work for you. They're good instructions: they tell you the steps to take and the pitfalls to watch for. Whatever they don't tell you, Rails will tell you.

However, the process took me a couple days to complete. Somehow I broke Rack. Once I reached the step of running some rake tasks, I was told that Rack::Request was an undefined constant. Um... that's a Rails internal (sort of); I really don't think that's my responsibility!

Long story short: I had my own Rack model in the app! That Rack class was shadowing the Rack module that's now part of Rails. Yesterday I spend 70 minutes refactoring my app to rename my Rack (to Shelf, thanks for asking), and it's working fine (at least according to the tests).

Short story long: one of the keys in debugging this problem is that after being frustrated by the error for quite a while and trying to debug what was so terribly wrong with my load path, I decided to take smaller steps. Instead of going from version 1.2 to 2.3, why not upgrade to 2.1 first? That didn't work too well either, but I forget why now. Since it didn't cost much at that point, I tried to upgrade to 2.2. If that failed, I could try for 2.1 or even 2.0 for a smaller step; if it worked, then I wouldn't complain. Fortunately, the upgrade to 2.2 went fine.

I didn't immediately remember that Rack was added in 2.3, but that was a key insight when I finally realized the problem. I believe the tipping point came when I did a full text search of the whole project in RubyMine. Then all the references to the Rack model jumped out and screamed at me.

This makes me wonder what would have happened if I had looked over the app before upgrading. I had forgotten that the Rack model even existed. Would five minutes of scanning the models and controllers at the beginning have made this problem easier (even trivial) to debug?

Anti-If Campaign

2009-06-27T13:04:00.000-04:00

A few days ago, I tweeted this:

Only reading the tagline on the homepage, this seems like a campaign I can get behind: http://www.antiifcampaign.com/

This is actually a theme I've had in my head while teaching Programming Languages the last two years. (I say "in my head" because I was always coy about this, presenting the issues rather than making a blanket statement: ifs are evil!)

Andy Meneeley, a former student and friend of mine, responded:

@jdfrens Sounds intriguing, but they only have one (trivial!) code example, then the rest of the site is just promo: a typical Agile smell.

The slam against agile ("Agile", really? capitalized?) was to get my hackles raised. Well, raised they are! I tried composing a Twitter reply, but 140 characters doesn't do justice to my hackles.

Smackdown

Here's the thing: if you want a non-trivial example, if you want multiple examples, look at any object-oriented program which uses polymorphism! That's not using an if. I'm beginning to re-think my choice of introductory programming language; maybe we should go back to Pascal so that students can appreciate OOP!

Polymorphism just says: invoke this method, and the object will know what to do when the time comes. Ruby (and other dynamic OO languages) take this to an extreme: just call the method; no one's going to check on it until it's actually invoked. Java forces you to promise the behavior through interfaces, classes, and type checking, but when it comes down to me writing a polymorphic call, Java doesn't really care where that method is coming from. Just call it! What could be an easier way to program?!

When implementing the polymorphic methods, all you have to consider it a very restricted context. Again, what could be easier?

ifs are necessary to kick things off. Some code has to actually create the objects which will later make the polymorphic dispatches, but how much of your code consists of creating new objects? It could probably be delegated to a couple of factories if you really wanted to, and then the "if problem" would be localized.

If X < Y

One question does intrigue me: mathematics. My dissertation involved matrix operations, and I took a couple of scientific computation classes in grad school. Could I write a QR factorization without ifs? Could it be done in a more OO way? This I'm not sure of. Perhaps the more mathematical the domain, the more ifs?

Not Just OO

One thing that gets ignored in these arguments is functional programming. There are a couple ways that FP languages avoid ifs: case analysis, pattern matching, object-oriented extensions, and type classes. OO extensions are the least interesting in this list because, well, we're already talking about eliminating ifs with OOP. Case analysis is the "if problem", but a case analysis is possibly a misuse of a FP language. Pattern matching and type classes offer interesting solutions, but they're proving to tickle my interest more than I thought they would. I'll have to think about the FP solutions to the "if problem" and blog about it later.

During the meanwhile, all (and especially Andy) should contemplate the precedence and associativity of the phrase "former student and friend". (Too harsh? Too bitter?)

Why haven't I wondered about this before?

2009-06-04T19:00:00.002-04:00

I came across this article from InfoQ today: "Original Sin" (Would Java be Better Off Without Primitives?). I've been very impressed and happy with Ruby's commitment to making everything an object. I had been indoctrinated into ignoring primitive-versus-pointer distinctions by Scheme and Haskell, so to revert to Fortran/C thinking when I picked Java up was kind of annoying. My question after reading the article was why I assumed that Java had to have primitive data types.

There are some cool tidbits about Java in that article that make it worth reading. I'll spoil the coolest one: Java exists because Sun couldn't license Smalltalk. What could have been!

Name your variables, stop picking on the string class, and call methods symmetrically

2009-05-22T16:22:00.002-04:00

Actually, the talk is "What the Ruby Craftsman Can Learn from the Smalltalk Master" by Philippe Hanrigou. In his talk, Philippe covers these three issues because they're interesting in themselves and also to demonstrate what others have discovered before us. The "others" in this case is Kent Beck and his Smalltalk Best Practice Patterns book.

Naming variables. Philippe discusses Beck's take on variables: name them after their roles. I couldn't agree more. I've ranted here about this before (haven't I?), but I'm convinced that a sign of a good programmer is the ability to find the right names for classes and variables. I'm almost convinced that this ability is sufficient and necessary to be a good programmer. (And, please, no one look at my CIAT project and some of the class names there. I'm really unhappy with them.)

It saddens me the number of students I've seen who'll use the variable names that first come to mind or are generated by Eclipse. (My Programming Languages students might want to look over their code for any arg0 variables that are being used in useful methods before I turn in grades next week.) I've found that a lot of the time that a good variable name is based on the data type. For example, I've been writing a lot of interpreters lately. When I have an integer object that needs to be interpreted, isn't integer an obvious name? It does bother me a bit that it's also the data type of the object, IntegerETIR ("integer expression tree-intermediate-representation"). I can see an argument that I should call the variable "expression" or even "program". Perhaps a good starting point is to use a variation on the data type for the variable name, and if that's too ambiguous or misleading, find a better name for the role.

Giving the string class too much responsiblity. Philippe points out all of the methods are being added to the String class for data conversions: to_f (meh), to_yaml (maybe...), to_date (yikes!), to_blob (what the...!), etc. This means to be able to use a string, you'll need all of these other classes.

The solution is to turn these "to" methods into "from" methods. Put from_string into Date, YAML, Float, and Blob classes. Haskell, too, uses "from" functions. My understanding is that this is more about the type system, but then I wonder if the type system is telling us something!

Symmetry. Philippe ends with an example of a method invoking three other methods. Here's an example of my own:

def foo()
  dog()
  @zoo.bat()
  cow()
end

It comes down to the readability of the code. Instead of figuring out what the code is doing, you're asking yourself, why the one instance variable? I'm reminded of poetry and music where the artist is supposed to follow a particular form. The second line of this method is like a limerick of six lines or a haiku with 20 syllables. "Why did you do that?" While this might be dramatic in a poem, this kind of drama is not wanted in code!

Bad breathalyzer code

2009-05-20T20:38:00.002-04:00

Ed Brayton, author of one of my most favorite blogs Dispatches from the Culture Wars, posted something about bad code today: "Why Breathalyzer Companies Won't Release Code". Ed's blog entry is almost entirely a quote of a summary of a court finding. There you'll find an PDF of the code review.

I gave that document a quick scan, and it seems really interesting to me. There's a little bit of pride in me, thinking "oh, I'd never do that!" But there's also quite a bit of shame, too, since whenever some software developer does a bad job it reflects poorly on us all.

"Outside-In Development with Cucumber"

2009-05-20T14:59:00.003-04:00

I just got done watching an excellent talk from Mountain West Ruby Conference 2009: Outside-In Development with Cucumber" by Ben Mabey.

The worst thing you could do is think this is just a talk about Cucumber.

Yes, there's quite a bit about Cucumber in the talk, and if you aren't impressed with it technically, this talk should convince you. (At least watch until he presents the alternative language options in Cucumber.)

What I found so great about Ben's talk is that he does a great job giving the motivation for why, when, and how to use Cucumber and RSpec (or TestUnit or whatever). Even if you're not interested in Ruby or Rails (let alone Cucumber), I'll guarantee you'll get something out of this talk, or your money back. (Of course, you'll have to pay me first in order to get anything back...)

I'm really impressed with the way Ben put all this material together.

Programming Languages final exam

2009-05-19T12:04:00.003-04:00

Here's the final exam that I gave to my Programming Languages students this morning:

Consider the three languages that we studied this semester and their representative paradigms:

Ruby (or Java, if you like) for object-oriented programming

Haskell for functional programming

Prolog for logic programming

Pick one of the following:

Write one (or more) haiku for each language.

Write one (or more) limerick for each language.

Write one sonnet for each language. (This one might be worth extra credit.)

Write one short story about the three languages (or one story per language).

Whichever literary form you pick, be sure to highlight the strength of each language.

One student wanted to know if a ballad was okay. I offered extra credit if it could be set to a Scorpions song. (Not that I'm a huge Scorpions fan, but for some reason they define the ballad genre for me.) Personally, I'm hoping for a bawdy limerick or three.

It's due by the middle of next week. I may share some of the good ones here. Feel free to contribute your own in a comment.

Opinions on RSS and Atom feeds and Rails

2009-05-16T13:16:00.002-04:00

I'm getting ready to implement RSS and/or Atom feeds for my (soon to be former) department, and I have a few questions that I hope some of you can help answer:

RSS 1.0 or 2.0 or both?
Atom or RSS or both?
Any good Rails plugins for generating feeds?

One issue I have is that the feed will include not only news items (e.g., "Student X won an award!", "IT jobs on the rise!"), it will also include announcements of talks and other department-related events (e.g., "Jimmy talking tomorrow!", "Picnic next week!").

Is it a good idea to mix event announcements in with the news items?
How often can I make the announcement? My thought is to add it to the feed a week before and again the day before. (This is when we send out email announcements.)

And, yes, all of our news and events are so exciting that they deserve exclamation points all the time!

Minimal Palindrome, Efficiency of My Haskell Code

2009-05-09T08:00:00.000-04:00

One thing I do rely on in my Haskell code to compute a minimal palindrome is the lazy evaluation of Haskell.

My first computation in the body of the function makeMinimalPalindrome (which I'll abbreviate "mmp") is to map a list-duplicating function over n numbers (where n is the length of the list). This sounds like an n² algorithm. I concatenate the original list with all of those lists. That could also be quadratic in n (depends how concatenation is implemented). Find just the palindromes, quadratic. Return the first element of that list (constant time, but who cares by now!). Total time: quadratic.

That's if you're in a naive language like C.

Lazy evaluation bottles up those computations until they're known to be needed. And, in turns out, that this ends up reversing what's "done first".

So who needs those mmp computations? Well, I'm running unit tests, and my driver will print an error if an assertion failed and will count successes and failures. So all of my assertions for mmp need to be computed. Let's consider one of them: mmp [1, 2, 1]. You'd expect this to waste time with the different suffices just to discover it's already a palindrome.

The outermost function call of mmp is considered first. head only requires the first element of its argument to be evaluated. Already at this point you should see the savings. The code will not compute every palindrome candidate. The head call requires the filter to find just the first palindrome. filter will trigger the two maps only enough times to find that first palindrome.

I'm making this sound like the functions are passing their need along. But it's really the functions evaluate their arguments until they produce the data that they need.

Consider the running time of mmp [1, 2, 1]. head is constant time. The filter should stop on the very first result, and checking that it's a palindrome is linear time. Both of the maps will have to be triggered only once, and the functions they map are linear as well. Finally, constructing ns is also linear.

You can't do better in any other language, not at the this big-O level. Just to check to make sure you have a palindrome is linear time. The constants on their linear complexities will definitely be different, but then we get into issues of implementation and adeptness of wielding a language.

The original problem is so academic (easy to understand but impractical in any real program) that I'm not sure it's worth analyzing much further.

Minimal Palindrome, My Natural Haskell Code

2009-05-08T13:30:00.002-04:00

In my previous post, I wrote about my Haskell code to compute a "minimal palindrome". I don't want to belabor this one example because it's really not that useful a computation, but a few things do strike me. In this blog post, I'm going to talk about the natural flow of my algorithm. In the next post, I'll talk about the efficiency of the algorithm.

So... I find this solution natural. What do I mean by that? How can I get most of you to stop laughing? First, I'm not saying that it's natural to any program as written. A reasonably experienced Haskeller (with two semesters of programming experience?) could make sense of it without troubles. For those using other languages, it might help if the code were rewritten with some crutch... I mean... helper variables:

makeMinimalPalindrome list = 
  let
    suffices = map makeSuffix ns
    allLists = map (list++) suffices
    palindromes = filter isPalindrome allLists
  in
    head palindromes
      where ns = reverse [1..length list]
            makeSuffix n = drop n $ reverse list^D

By the way, I know that this code works because I have unit tests, and they still pass after these refactorings. If you start with the idea that you're going to try every possible suffix to create the minimal palindrome, this is a natural order to build up the code.

I'd wager, though, that most of you indoctrinated early with Pascal or C or C++ or Java are still shaking your heads. But take a step back. What solution are you imagining in your head? There's a loop or two and arrays, right? Index operators? Why work with the data at that level? That's not how you'd describe the algorithm to your mom (unless she's a C programmer, too). The more I play with Haskell and Ruby, I find I get more power out of them when I try to write the most hand waving algorithms I can. "Concatenate these lists." How? I don't know; I don't care! "Reverse this list." Just do it!

Much of this "hand waving" attitude is just a desire to use higher and higher abstractions. That's what high-level programming has been about all along, right? But I'm really beginning to question whether a student in a CS1 course should even know how to index an array. Use a list and higher level operators (where I'd include Java's "foreach" a "high level operator").

Back to this particular code. The real kicker is that many of you are quite worried about all of those lists I'm creating with the reverses and dropping and concatenating. What happens if list is already a palindrome? Your C code would recognize this immediately and stop, right? So will this code.

Okay, that's a bit of a lie, but I wanted a good teaser for you to look forward to my next blog post!

RubyMine for Rails development

2009-05-08T11:52:00.001-04:00

I saw a version of IntelliJ in action two years ago, and I wasn't particularly impressed. It is a great IDE, but it didn't seem to offer anything over Eclipse. (The version I was using was also quite buggy, but I'm trying not to hold that against it.)

But the Ruby on Rails support in Eclipse (and Aptana) have greatly disappointed me. NetBeans is good, but more than a big sluggish. TextMate doesn't seem like quite enough for me for Ruby on Rails. So I thought I'd give RubyMine from the IntelliJ guys (JetBrains) a try.

First impression: pretty slick! It runs nice and speedy on my MacBook (2.0 GHz with 4 GB of RAM). The first time I started it, it took some time to get acquainted with my environment, but it's been reasonably speedy ever since.

"Slick" also means "eye candy". It's not iPhone-level eye candy (which would count against it), but it's good and appropriate IDE eye candy. RSpec (and, I assume, Test::Unit) runs in a special green-bar/red-bar window. Syntax highlighting is good with the default colors.

One place where RubyMine really excels is with code navigation. It seems to understand the Rails defaults so that it knows what view to jump to when you're in a particular controller action. It also knows what all to rename with a Rename refactoring (watch the rename refactoring demo).

RubyMine also has excellent version-control support for CVS (I think), subversion, and git (oooo!).

The primary complaint I have is that there's apparently no cucumber support yet. The little Googling I did seemed to indicate that cucumber support is on its way, but not until this fall. Boo!

But if you're looking for a Rails IDE, I'd certainly recommend trying out RubyMine. It might even be worth it's $99 price tag. (I'm working on open-source projects right now, so I could get it for free.)

Minimal Palindrome, My Haskell Code

2009-05-07T15:13:00.001-04:00

A couple weeks ago I proposed a programming challenge: write a Haskell function to compute a "minimal palindrome" without using explicit recursion. One of the things I've tried to get my programming-language students to appreciate this semester is the true power of functional programming: functions as first-class values.

So, back to the challenge. A minimal palindrome is taking [1, 2, 3] and returning [1, 2, 3, 2, 1] (the 3 is not repeated). It's also taking [1, 2, 1] and returning [1, 2, 1].

I already had this function to recognize a palindrome:

isPalindrome list = list == reverse list

Now there might be a clever algorithm using a string matching algorithm for computing the minimal palindrome, but I went more brute force. I started with this observation: if pal is returned by makeMinimalPalindrome list, then

pal == list ++ (drop n $ reverse list)

for the smallest n. (For those thrown by the syntax, drop n $ reverse list can be rewritten as drop n (reverse list). It's a handy operator once you get used to it.) My brute-force algorithm was to try every possible n, from length list down to 1. (I don't have to try 0 because 1 is guaranteed to give me a palindrome.) From this list of results, I filter out the palindromes and return the one with the smallest n.

The code:

makeMinimalPalindrome list = 
  head $ filter isPalindrome $ map (list++) $ map makeSuffix ns
    where ns = reverse [1..length list]
          makeSuffix n = drop n $ reverse list

ns are the ns from length list down to 1. makeSuffix computes a reversed suffix for the palindrome. Reading the real body of the function from right to left, the first map creates all of the suffices; the second adds them onto the original list; the filter finds only the palindromes; and head returns the first one in the list (of lists). Since I start ns at length list, I'm guaranteed to get the minimal palindrome.

There are some more things to say about this code, but I'm going to save them for some future blog entries.

Seven Stages of Unit Testing

2009-04-29T07:56:00.002-04:00

Came across an interesting list this morning: "The 7 Phases of Unit Testing". It does a pretty good job of describing the phases I went through. Get started now, because phase 7 is great!

Testing Smells

2009-04-28T12:35:00.002-04:00

Came across this blog post from Jake Scruggs "Smells of Testing (signs your tests are bad) ". I would have loved to be at this talk. I've been thinking of some of these smells myself, and they seem to have started on some good ideas here. One idea I'd like to throw into the mix: some of these smells indicate problems with the computation code, not the tests.

Monads in Ruby

2009-04-22T13:20:00.002-04:00

Yes, Ruby. Monads. In Ruby.

I came across a blog entry by Bill Six called Functional Patterns in Ruby: Monads. I won't repeat what Bill has written there; I'm just curious what Haskellers think of this.

What I find really interesting is that like all type issues, the move from Haskell to Ruby means moving their resolution from compile type to run time. But I get the sense from this monad library that these Ruby monads are just as reliable as Haskell's.

BTW, Firefox didn't like how I was spelling "monads". It recommended "nomads" or "gonads" instead. (And in my next post, I'll tell a fart joke.)

Programming challenge: minimal palindrome

2009-04-14T18:06:00.003-04:00

I gave my Programming Language students a challenge to write a Haskell function that computes a "minimal palindrome". A "computed palindrome" is reversing the list and appending it to the original list: makePalindrome [1,2,3] results in [1,2,3,3,2,1]. It amounts to one line of code in Haskell.

After computing a few of these, you'll notice that the middle elements of the computed palindrome (there are always two in the middle) are the same. That's just a property of the computation. However, what's the computed palindrome of [1,2,1]? If there's an official standard, I'd like to know, but I've taken it to be [1,2,1,1,2,1] because it's really easy to compute.

But then the idea of computing a "minimal palindrome" is kind of interesting. The minimal palindrome is the shortest list that is a palindrome and contains the original list as a prefix. So the minimal palindrome of [1,2,1] would be [1,2,1]!

It turned out this was trickier to do in Haskell (without using explicit recursion) than I had thought. But it's still quite doable. I came up with a solution that's three lines of code, and I believe because of Haskell's lazy evaluation is fairly efficient.

I'm curious what others might come up with before I reveal my solution.

Test::Unit Tests as RSpec Examples

2009-04-07T18:30:00.003-04:00

I've been doing (or trying to do) a bit of Ruby on Rails, and I end up looking up information more than once as I'm learning new techniques and solving new problems. It occurs to me that if I'm having trouble with some of these things, maybe others are as well. And through the magic of Google and Yahoo searches, maybe they'll find my solutions helpful—but only if I post them here!

Plus, if I've done something really stupid (or even mildly stupid), other can correct me.

For this blog post, I'm trying to switch from using Test::Unit in my Rails apps to RSpec. Presumably, Test::Unit-style testing can be embedded in RSpec examples. Unfortunately, Chelimsky's post only says that it can be done, not exactly how, and RSpec for Rails makes it trickier. So I collected a few tips here. Some are relatively obvious, but I find myself worried if I come up with an obvious solution that might be too simple.

The Test::Unit to RSpec Transformation

I kept to Rails' testing standard: model-tests as "unit tests" and controller/view tests as "functional tests". So the first step was to copy from test/unit/ into spec/models/; the second was to copy from test/functional/ into spec/controllers. I figured that I'd refactor out of the controller tests into view tests as needed.

Running the specs resulted in many errors. Here's a mildly sorted list of errors and my resolutions:

Shoulda tests are not examples! This problem is silent. I used the fantastic Shoulda gem for my Test::Unit tests. Unfortunately, the should directive from Shoulda does nothing to trigger an example or an error. So they don't run, and you're never told! There's probably some clever way to deal with this, but I've been too lazy to figure it out. My solution: I ran each example file individually, and when I got only 1 example, I had some unconverted tests.

Incidentally, inheriting from Test::Unit::TestCase and writing normal test methods (starting with test_) works just fine. My model examples are still just Test::Unit tests. The problem here was with should from the Shoulda gem.

I thought I about grepping the files for "should", but I didn't imagine it would save me that much time. Perhaps the more clever solution would be to redefine should in some way.

RSpec can't find test_helper.rb. You don't want it to. Instead, require spec_helper.rb. At the same time, I dropped the redefinition of rescue_action(e) since it appears to be unnecessary for RSpec.

Helper methods from test_helper.rb can't be found. Well, duh! I moved some of them to spec_helper.rb. Others I rewrote or even dropped because they solved problems that I didn't have with RSpec. Take this as an opportunity to re-evaluate your helper methods: are they really necessary and helpful? is there a better RSpec way to do it?

response is undefined. I got this in my controller examples when I started using the RSpec API. This can be solved by using @response, but I don't think this is the best solution. See the next problem and solution

redirect_to (an RSpec matcher) is undefined. This frustrated me for quite a while, and it's the primary motivation for writing this blog entry because I'm quite sure I've had to look up the solution more than once. Again, this is in a controller example, and the problem is that controller-specific helpers provided by RSpec and RSpec for Rails aren't automatically available. So the solution was to change the class definition from

class FaqControllerTest < Test::Unit::TestCase

describe FaqController do

I also deleted the original Test::Unit setup method. This doesn't seem to be necessary, but it also doesn't break anything.

Missing fixtures. Copy the fixtures from test/fixtures/ to spec/fixtures/.

Controller examples failing on view expectations. By default, RSpec does not actually render the views when running a controller spec. Add integrate_views in the describe block for the controller spec.

Cucumber Stories?

Uh... well... you see... I don't really have any integration tests. Since my original apps weren't using mock objects, I don't find this to be a terrible thing, but I'm also not proud of it.

Trust me. From here on out, though, I'll be writing Cucumber stories for all new features (and for old features as need be).

Taming Side Effects

2009-04-05T19:52:00.003-04:00

This afternoon, I watched "Taming Effects with Functional Programming", a presentation by Simon Peyton-Jones. Peyton-Jones is wicked smart, and he gives a good presentation. Doesn't hurt that everything he says makes my dissertation relevant for today!

If you ever wonder why I or anyone else goes on and on about the benefits of functional programming (and Haskell), you must watch this presentation. If you're already convinced, you'll appreciate the confirmation.

Another Euler polyglot

2009-03-24T10:52:00.001-04:00

I came across someone else who's writing up Project Euler solutions in multiple languages.

lgastako (a.k.a. "John", if his GitHub profile is to be trusted) has an impressive list of languages: C, Clojure, Erlang, Java, Javascript, Common LISP, Lua, Pascal, Perl, Python, Ruby, Scheme, and Haskell. Our overlaps are interesting: Haskell, Ruby, Python, and Erlang. I'd go so far as to say these are probably the most important languages to learn these days. (Finding a job using these languages would be great, too, but the concepts they teach you are fantastic.)

The biggest difference seems to be that he isn't writing unit tests. That and his GitHub repository that gets him noticed by the GitHub people. (I'm not bitter, of course.)

For some reason, when I first read a description of Igastako's project, I thought he was working on a language translator. That is, he was writing a solution to a Project-Euler problem in one language which would produce solutions in other languages. I've thought about doing this myself, but it wouldn't give me the hands-on work that is needed to learn a language. On the other hand, I've grown tired of writing the unit tests in multiple languages. Perhaps that's a place where I could do some language generation.

I do offer this one bit of advice for Igastako: for the sake of everything holy, please do not try to use Prolog to solve these problems. Save yourself the pain and suffering. Syntactically, you'll get enough from Erlang. Semantically, Prolog offers nothing for the types of problems from Project Euler. Seriously, try Brainf*ck or Whitespace instead. Find different problems for Prolog.

Hacking Ruby's Default Parameters

2009-02-28T06:57:00.003-05:00

It's been quiet on this blog here for a while. ("Too quiet...") I just had to share this: Hacking Ruby's default arguments". Factorial defined in the parameter list. Yikes!

Language Performance on PE Problem #4

2008-12-21T13:00:00.001-05:00

In a previous blog post, I wrote about my solution to the fourth Project Euler problem. My brute force algorithm was quadratic, and with some clever mathematics I figured I could reduce the search space quite a bit. But the Project Euler website's question for Problem #4 could be solved in less than four seconds by my programs. So I never looked for a better algorithm.

But I became curious about the performance of my languages. So I timed each one to see how well they performed.

But first, let me reiterate my position on efficiency. I start with Knuth: "Premature optimization is the root of all evil." My policy is that if you want things faster, you have to use a profiler and optimize the bits that will give you the best payoff.

However, I'm not looking to improve my code. (In fact, I actually changed my Ruby solution and made it worse!) I was just curious how the languages compared to each other.

The Timing Results

The numbers below come from one set of trials. I ran several set of trials, and they all came out like this. Some things to note:

Interpreted versus compiled:
- Ruby and Prolog were always interpreted.
- Python seems to compile something the first time it runs.
- Erlang compiles to a byte code; Haskell compiles to native code; both compile before the timed execution.
I measured wall-clock time since it's the overall performance I'm interested in, not just processor time.

Language	Run/Running Time (in seconds)
Language	1st	2nd	3rd
Erlang	2.69	2.28	2.75
Haskell	0.43	0.40	0.40
Prolog	3.07	2.49	2.56
Python	3.72	1.06	1.31
Ruby	3.92	3.89	3.91
Ruby 1.9	2.34	2.35	2.34
Ruby	1.89	1.87	1.87
Ruby 1.9	1.03	0.98	0.95

Surprises and a Non-Surprise

Surprise #1: Haskell wins! Decisively! I'm not that surprised that it won, but I am surprised that it's so much better. So why did it win? Some must be due to compilation to native code. I also think that the GHC guys really know what they're doing!

Surprise #2: Erlang doesn't perform very well. For some reason, I thought it would do better. However, I may not be compiling it quite right; I may be partially interpreting it.

Non-Surprise #1: Prolog is slow! Even still, it didn't do that poorly. (The 3.07 on the first run seems to be a bit of an outlier.)

Surprise #3: Python. The first execution with new code, it runs a bit slow. But then it greatly improves every time after! If I clobber all non-source in the Python folder, it goes back to a slow execution followed by much faster executions. Python is dropping a problem004.pyc next to my original problem004.py, and I assume that it's some byte code. Unlike Haskell and Erlang, Python's compilation time is being held against it, and it that light it makes its first run a bit more impressive.

Surprise #4: Ruby sucks! Well, not really. Its performance on this one particular task isn't that good, but then I never expected it to be. On the other hand, I didn't expect it to be this bad. You'll notice that I have the running time for Ruby 1.9 as well. I've read that Ruby 1.9 is supposed to be making some serious performance improvements, and my numbers here seem to bear this out.

More Analysis of the Ruby Performance

There is something unfair about the Ruby and Prolog code. I used built-in list comprehensions in the other languages, and those languages can (and should) optimize them.

The code I posted previously is, I feel a more syntactically honest transliteration of the list comprehension into Ruby. But originally I wrote my Ruby solution with the palindrome assertion and maximum search in the body of nested loops. That did much better:

Language	Run/Running Time (in seconds)
Language	1st	2nd	3rd
Ruby	1.89	1.87	1.87
Ruby 1.9	1.03	0.98	0.95

From a "what gets executed" standpoint, this version of the Ruby code is probably closer to what the other languages compute. And of course this should be much faster since it doesn't have to remember on the order of 10000 products in a list! Now granted, Haskell, Erlang, and Python will have to remember all of the palindromes before it can compute the maximum, but that's still a pretty significant difference.

I don't see how to get Prolog to a more efficient list-comprehension level, but this must be because I'm just not in the Prolog groove yet.

State of my Mac

2008-12-20T17:01:00.003-05:00

Just an update on my MacBook. Previously, it looked like this. Here are its stats now:

Mac OS X 10.5.6
2 GHz Intel Core 2 Duo
2 GB 667 MHz DDR2 SDRAM

MacPorts version 1.7

Official Erlang version R12B-5
Glasgow Haskell Compiler version 6.10.1
SWI-Prolog version 5.6.63
Official Python version 2.6.1
Official Ruby (MRI) version 1.8.7

All languages come from MacPorts now.

Update: added a title.

PE Problem #4 in All Languages

2008-12-19T13:27:00.000-05:00

The Problem

Problem #4 is to find the largest palindrome that is the product of two three-digit numbers. You just need to come out with the product itself, not the factors.

I figured I'd go for the brute-force solution first: try every product x*y for x and y over the range 100 through 999. Grab the palindromes, and grab the maximum.

I figured there must be a clever way to reduce the search space. For example, I could just search where x <= y. But after I wrote my first version using the brute-force algorithm, it ran fast enough that I decided not to worry about it unless the programming language forced me. In the end, I implemented this brute-force algorithm in all five languages.

This blog entry turned out a little longer than I had intended, so I'm breaking it up into two different pieces. This entry will talk about my solution to the problem; the next entry will talk about some timing tests that I ran.

Recognizing a Palindrome

For some reason, I was not eager to write a divide-and-modulus algorithm to numerically determine if I had a palindrome. I went with a conversion solution: convert the number into a string, reverse the string, compare with the original string.

Even though I knew basically what I was searching for in the documentation, I found myself stuck a few times. But in the end, each of my languages had an "integer to string" conversion and a "reverse this string/list" function. Two of them were particularly surprising.

Python's solution has some wacky syntax: `n`[::-1]. The backticks convert a number into a string. (This is kind of ugly and definitely non-intuitive.) The wacky index operator [::-1] reverses the string. Without reading the documentation too deeply, I figure [n:m:s] would normally return a substring of the original. By leaving the first two arguments empty, it's assumed that I want the two ends of the string, and the -1 indicates "traverse this substring backwards".

The Prolog solution surprised me, but it shouldn't have. Prolog is a logic language, and so the whole idea of "is Reverse the same as Original?" is built into the language:

is_palindrome(N) :- name(N, S), reverse(S, S).

name turns an integer into a string (or a string into an integer). The wacky bit is reverse(S,S); unlike the other languages, there's no explicit equality test. This is because Prolog is always asking, "How can I logically satisfy these constraints?". Underlying "satisfaction" is the idea of equality, and what Prolog has to do to achieve satisfaction depends on what data and what variables are passed in.

Let's consider two calls to reverse. reverse([1, 2, 3], R) is satisfied by R = [3, 2, 1], and reverse(S, [3, 2, 1]) is satisfied by S = [1, 2, 3]. (It helps if you don't think about how Prolog might do this; just go with your intuition on the logic here: what does R or S need to be to satisfy the logic?)

No matter how we ask to have reverse satisfied, Prolog will figure out if and how it's possible. So a call like reverse([1,2,3], [3,2,1]) is just simply true; similarly reverse([1, 2, 3], [1, 2, 3]) is always false. Neither expression has free variables that have to be set in order to find satisfaction; Prolog just has to make sure it's consistent. This is the situation we have in is_palindrome(N), S is bound by the name(N,S) expression, so reverse(S,S) is there to give a true/false result.

(Incidentally, just evaluating reverse(S, R) does return something; in fact, it returns a lot of somethings! But I've already strayed away from my Project Euler problem. It's worth investigating, though, once you get into Prolog.)

Searching the Products for a Palindrome

Haskell once again provides the tightest solution:

findPalindromeProduct n =
  maximum [x * y | x <- range, y <- range, isPalindrome (x * y)]
    where range = [n..(n*10-1)]

Erlang and Python also have list comprehensions, and their solutions look quite similar. If you squint a bit, the Prolog version looks like a list comprehension. Ruby, though, forced me to make the loops explicit:

class Integer
  def find_palindrome_product
    products.select { |p| p.palindrome? }.max
  end

  def products
    products = []
    (self..(self*10-1)).each do |x|
      (self..(self*10-1)).each do |y|
        products << (x * y)
      end
    end
    products
  end
end

I really don't like the products method. A method like Enumerable#zip() will traverse multiple lists in lock step; I need a Cartesian-product kind of traversal. But this does provided a list-comprehension like feel (as good as it'll get in Ruby).

PE Problem #3 in All Languages

2008-12-14T18:21:00.002-05:00

Wow. It's been a very long time since I blogged here. It's been even longer since I worked on a Project Euler problem. But rather than start on the large pile of grading I need to do at the end of the semester, I decided to work on Problem #3.

The Problem

Problem #3 is to find the largest prime factor of a number. To get myself into the flow of things again, I started with a Haskell solution because I knew that Haskell's lazy evaluation makes a prime number list interesting and fun to write.

The Haskell Solution (and Erlang)

Let me jump to my punch line: you don't need to calculate any prime numbers.

Here's my Haskell solution:

gpfSearch f x | x == f      = x
              | divides x f = gpfSearch f (div x f)
              | otherwise   = gpfSearch (f+1) x
  where divides x y = mod x y == 0

I start this "search" at f=2, and as factors are found, they are factored out. Since each prime number is smaller than it's multiples, I only ever factor out prime numbers. (E.g., f=16 never divides x because even if 16 is a factor, f=2 would be factored out four times.) So by the time I factor the original number down to x==f, the number must be a prime factor and the largest.

The question on the Project Euler site forces you to use bigints, so I discovered the difference between Haskell's Int and Integer types (i.e., machine int and bigint, respectively).

Since this version ran as fast as my compute-primes-and-factor-with-them-only version, I tossed my prime-number code. Since my code takes about a quarter of a second to find the greatest prime factor of a 12-digit number, the simpler code wins. (On the other hand, looking forward to some of the future Project Euler problems, I probably should have kept it in a separate library.)

My Erlang solution was similar, just with a different syntax.

The Python Solution (and Ruby)

Erlang was actually my third language with this problem. My second language was Python, and I discovered a whole new problem that Haskell and Erlang fixed for me automatically: tail recursion.

Consider this: gpfSearch 2 n will try out (at worst) sqrt(n) different factors. The square root of a 12-digit number will be a 6-digit number. That's an awfully tall runtime stack! However, gpfSearch is tail recursive. I've talked about tail recursion before on this blog, so in a nutshell: since gpfSearch calls itself recursively as the last thing to do in each case, the function can be turned into a loop. And this is what Haskell and Erlang do, since they optimize tail recursion.

Python does not. So it runs out of stack space and whines.

I ended up with this solution:

def gpfSearch(n, f):
  while n != f:
    if divides(n, f):
      n = n / f
    else:
      f = f + 1
  return f

This is the code executed by Haskell and Erlang; I just have to do the optimization by hand in Python.

And in Ruby.

I'm struck by how much easier it is to read and understand the Haskell/Erlang solutions. The loop does not seem intuitive to me at all unless you start with the recursive version in your head.

The Prolog Solution

Once again, I got a bit frustrated with Prolog. And, again, I feel a bit bad about it because arithmetic is just not its thing. (I mean, there's a really good reason why I'm not doing these problems in SQL!)

I thought a compute-primes-first solution might actually work out better in Prolog:

greatest_prime_factor1(N, P) :-
  gpf_search(N, Factors), max_list(Factors, P).

gpf_search(N, Factors) :-
  N2 is ceil(sqrt(N)),
  primes2(N2, Primes),
  include(divides(N), Primes, Factors).

This gives the right answer, but it blows up on the 12-digit number. It also takes a long time to blow up. (Python and Ruby blew up very quickly with the recursive definitions.) The problem is with my primes2(N, Ps) predicate; when the Project Euler problems require that I actually compute prime numbers, I'll come back to this.

To get a version that works with the 12-digit number, I transliterated gpfSearch from Haskell. Since Prolog also optimizes tail recursion, the recursion over the large number isn't a problem.

I've started a second blog!

2008-08-30T20:24:00.002-04:00

'Cause I just didn't have enough to do:

Compiler Club

Three guesses what the new blog is about; first two don't count.

Dependency Injection with Guice

2008-08-25T15:35:00.003-04:00

I've been looking for a good tutorial on how to use Google Guice for dependency injection. I've been doing dependency injection by hand for a couple years now, but Guice crossed my radar recently, and I desperately needed to learn something new. (I mean, it would be a shame to start preparing for the fall semester a whole two weeks before it started!)

For some reason, the Guice User Guide wasn't that useful to me. I'm sure the necessary information I need is in there, but I couldn't (mentally) put together a complete example from it. A Google search revealed this tutorial. Very useful!

I also came across this Google Talk. I can't comment on it yet because I'm about to watch it now.

Just in case you were wondering...

2008-08-22T09:50:00.001-04:00

Created by OnePlusYou - Online Dating

Quite frankly, I don't believe it. Try it yourself.

Literate Programming

2008-08-11T11:49:00.002-04:00

Literate programming is an interesting phenomenon. I bought it to it strongly back in the 1990s. I wrote an entire technical report ("Matrix Inversion using Quadtrees Implemented in Gofer") using Noweb; I also used it for writing the code for my dissertation. In hindsight, I used Noweb as a strange macro system for my dissertation code ("strange" as in "not effective").

What intrigues me most about literate programming now (and then) is the technical side of it. How does one turn a literate document into code and into a printable document? Sure, it's just a variation on interpreting and compiling, but I love those topics, too.

As a tool for writing code, I'm much less keen on it. It still has the drawback of keeping the comments in line with the code, and that's a huge drawback. I did find myself more willing to write comments and keep them maintained with literate programming; I attribute this to the expressiveness of LaTeX (especially when it comes to mathematics).

Two things killed literate programming for me. First, Donald Knuth (the father of literate programming) bad mouthed unit testing and mock objects. How could I possibly take anything he says seriously?! No, seriously, that's not any reason at all. But some of you were thinking it of me... Knuth, just like anyone else, is welcome to his own wrong opinions.

Actually first, IDE support. Once I used Eclipse for a couple of hours, I gave up emacs and never looked back (at least for writing Java). emacs had minimal literate programming support; Eclipse had none. But the features I gained with Eclipse are worth anything I lost.

Second, unit tests and TDD. "Literate comments" are supposed to serve the same purpose as unit tests and TDD: drive the design. Unlike literate comments, though, unit tests can be executed to verify that your code matches your design. Then they serve as regression tests. You have to keep the unit tests up-to-date. Literate comments sit there and require a human to read them; they don't check your work; they don't stay up to date on their own.

Returning 'null' considered EVIL!

2008-08-10T19:24:00.005-04:00

I came across this article tonight: "Returning 'null' Considered Dishonest" by Andy P. I'm with you all the way, Andy, except that I'll go so far as to say that returning null is evil. I hate it.

Read Andy's article for a more rational, calmer analysis of the issues. I would just add that the Null Object pattern has worked very well for me in the past.

And now I see a link between Null Objects and monads has opened up to me. Yikes!

No side effects!

2008-07-28T12:23:00.003-04:00

Kevin Smith (the Erlang programmer, not the director) has a post up today on his blog Hypothetical Labs about "Erlang & Single Assignment: You’re Doing It Wrong". I got trained in grad school to program without side effects, and now I consciously avoid them like the plague (some hyperbole thrown in for the fun of it).

The real point of his article (in my mind) is to use the paradigm and features of your programming language. For my Project Euler solutions, I've been happy to use list comprehensions in Haskell and Python; I use map and select in Ruby since that's what it supports (not list comprehensions). My purpose for working on Project Euler with multiple languages has been to learn the features and paradigms of each specific language.

On the other hand, it's important to see how to implement a feature from one language in another. Some feature translations are easier than others, and some can be really, really powerful. I missed out on one of these opportunities on the second Project Euler problem which required computing Fibonacci numbers. Haskell allowed me to construct an infinite list which I could take off just the values that I wanted. In the other languages, I wrote a combination take-what-I-want and compute-Fibonacci-numbers recursive function. What I should have tried was to write a coroutine (e.g., Fiber in Ruby 1.9).

Read Smith's article. It's short and has some good specific observations.

/* No Comment */

2008-07-25T12:32:00.004-04:00

I've been working this week mostly on an acceptance-test system for compilers and interpreters. It's coming along well, but it means learning a few new things about Ruby and a lot of new things about git. I also had to spend time with my new toy. (Yeah, that picture scares me, too.)

Commenting on Not Commenting

As I was reading my blogs this morning, I can across an excellent post about not commenting code: Coding Without Comments by Jeff Atwood at Coding Horror.

Jeff gets at the heart of the matter: "the code already tells us how it works; we need comments to tell why it works" (emphasis his and mine). But even then, comments are the wimp's way out. Jeff goes on to say: "While comments are neither inherently good or bad, they are frequently used as a crutch. You should always write your code as if comments didn't exist." (emphasis his and mine) Refactoring is a very powerful tool, and for the clarity that Renaming and Extracting refactorings give us, it's insane not to do it early and often.

When to Comment

Never.

Sorry. That's too flip, but it will tick off the right people.

Jeff links to "Common Excuses Used to Comment and What to Do About Them" by Sammy Larbi at his wonderfully named blog "My Secret Life as a Spaghetti Coder". He lists some great objections with some greater rebuttals.

Sam lists four valid reasons for writing comments: Javadocs, truly complex code, TODOs, and design decisions (when the obvious implementation isn't used). I agree with all of these exceptions as long as they are truly exceptional.

For example, I wrote complete Javadocs for my ANTLR Testing library. It's a Java library for public consumption, and a library is code and documentation. (Libraries used internally can rely on unit tests for API documentation.) On the other hand, my No Latte interpreter has little to no Javadocs because it's primarily an executable system, not a plug-in library.

Complex code and non-obvious design decisions really don't come up that often. Certainly there's a lot of variance on this, and I'd expect embedded-system developers to say it comes up all the time. Perhaps. But considering how rapidly technology improves, stay vigilant! You might be able to simplify some code that "had" to be complex two years ago.

Teaching to Not Comment

The issue of comments in my classes is one I've struggled with. Javadoc is a valuable technology which my students need to know, so I've required it in the intro courses I've taught. (Although I haven't always been as strict with grading it as I should have.)

I'm beginning to see the value in doing code reviews in class. In a data-structures-and-algorithms class I taught a few years ago, I noticed that the top students in the class tended to write rather lengthy methods broken into chunks (separated by whitespace), and at the beginning of each chunk was a comment perfectly describing the "why" of the next chunk. It just screamed to me: Extract Method!!! The comment becomes the name of the method, and the code becomes self documenting. Since Eclipse (or any decent IDE) has the ability to do the refactoring for you, it becomes a no brainer! A code review or two would have been useful for all students to see the better way to write their code.

Unfortunately, all programmers tend to be fairly embarrassed about their code, so it might be difficult to get permission to do this in a large class.

There's also a need to have students read more code. We don't teach students how to write English essays by requiring them to write all of the time; we also have them read a lot. The same should be true about code (although maybe not in the same proportions). By reading more code, they get to see at least what does and doesn't work for them.

Buy a T-Shirt

The name of the post comes from my favorite t-shirt at ThinkGeek. Buy one for each member of your family. Get the word out. Get the comments out!

Use punctution?

2008-07-21T18:30:00.002-04:00

Ryan Bates, in his latest episode of the freakin' awesome Railscasts, defines a function with this name:

def can_edit_comment?(comment)

Seeing this after my last post here, I started wondering if the can_ prefix is necessary or should I get whiny about it, too? edit_comment? is sufficient and certainly succinct, but I'm not so convinced that I feel the need to get whiny.

Strangely, though, I'm more in favor of editable_comment?. To me it's clearer, although it has the same number of characters as the original.

Then I started wondering about _comment! If this were Java or some other language with overloading and compile-time typing, then I'd leave that _comment off: editable?. I'd let the type system prevent me from passing in the wrong kind of object. But in Ruby, with duck typing, that _comment adds a little bit of protection for me, but not so much that I feel whiny about it.

Hopefully, I'll have some less whiny posts for the rest of this week...

Use punctution!

2008-07-21T12:33:00.003-04:00

I'm presently reading over an IBM DeveloperWork's article "Developing iPhone applications using Ruby on Rails and Eclipse, Part 1: Serving content for iPhones". I'm trying to find out how are it is to optimize a website for an iPhone.

In the article, I came across this Ruby code:

def is_iphone_request?
  request.user_agent =~ /(Mobile\/.+Safari)/
end

Question: anything strike you as odd?

Hint: there's a redundancy.

Answer: why is the method named with a is_ and a ? suffix? The ? is a wonderful character to succinctly and clearly indicate the question posed by the method—better than is_ ever could.

I've done this myself, usually after coding in Java for a while, so I harbor no ill feelings towards the author of the code. But names really matter.

BarCamp Grand Rapids

2008-07-15T11:05:00.002-04:00

I'm guessing that anyone reading this blog in the Grand Rapids (Michigan) area already knows about BarCamp Grand Rapids, but it won't hurt for me to advertise. Here's an ad written by Kyle Adams, one of the organizers of BarCamp Grand Rapids:

BarCamp Grand Rapids, inspired by the Silicon Valley event that rocked the emerging technology world with its audacity and success, will take place on August 15-16 at Calvin College.

The original Palo Alto BarCamp was born out of frustration with the stifling atmosphere of most conferences. In a bold move, the founders decided to hold an "unconference" and let the attendees decide the schedule and topics to be presented. The organizers provided only a venue, a blank schedule board, and some overhead projectors: attendees were responsible for creating all the content, giving all the presentations, and having all the fun. The experiment was a resounding success, and BarCamps in Toronto, Amsterdam, and New York City soon followed. BarCamp Grand Rapids continues this proud tradition, for the third year running.

Calvin College is generously donating classroom space, including a space for a "campout" Friday night. Gordon Food Service, Subway, and Biggby Coffee will be providing food for the event, and SageTech will be hosting a get-together after the Friday night sessions. Elevator Up has also pitched in to help keep to conference free for all attendees.

For the latest information and registration, see http://barcampgr.org/.

I was a lot of fun last year, and I'm looking forward to this year's. I even planned a vacation around it!

Tail-recursive, linear-time Fibonacci in Haskell

2008-07-12T13:33:00.003-04:00

An article "Tail-Recursive, Linear-Time Fibonacci" by Shin-Cheng Mu popped up in a Haskell blog this morning. Looks like an interesting read.

Read it now!

Henderson Escher

2008-07-11T19:32:00.002-04:00

A quick follow-up from my previous post. If you'd like to see some code for the Henderson-Escher system, check out "Escher in LISP" from Bill Clementson.

Thinking Functionally

2008-07-11T19:28:00.000-04:00

Lecture 3a of Structure and Interpretation of Computer Programs is entitled "Henderson Escher Example".

"Escher" refers to "M.C. Escher", of course. The "Henderson" refers to "Peter Henderson" who wrote an article, "Functional Geometry", which describes a beautiful system of functions that generate Escher-like pictures.

Abelson and Susseman build up Henderson's system in LISP. Unfortunately, they don't have the technology to actually do the drawing (it was 1986!), but the ideas are clearly there.

I recently had a discussion with some friends about programming paradigms, and the idea of "it's how programmers/people think" came up. One friend (are you reading this, Zach?) was pretty convinced that OOP wins this battle. I know others who say the same thing for functional programming (John, you here?). I won't argue this whole issue now (since they're both right!), but this lecture puts forth a great argument that functional programming can clearly make the claim.

The design of this system was based on embedding the functional-geometry language within LISP. Abelson and Susseman first build up a library of basic objects: vectors (i.e., points) and line segments. They're represented by lists, but that's all hidden by the constructors and accessors. (Yes, OO fans, the functional people call them constructors and accessors, too!)

On top of that level, Abelson and Susseman build picture and rectangle representations along with functions to scale, rotate, and combine pictures (within rectangles). The result is amazingly elegant.

Abelson and Susseman start waxing philosophical in these lectures, that this ability to embedded another language is one of LISP's greatest strengths. By writing different layers of abstraction, it allows the programmer to change (or fix) functions at one level without having to deal with the other layers. Abelson and Susseman take a few shots at up-front design (and the waterfall method) since one design decision early in the process cannot help but affect others; so when one decision has to change, later decisions have to adapt as well. Yeah, LISP; boo, waterfall!

You can decide if their attack on up-front design is fair (after you watch the lectures). This is also not to say that OO (or other paradigms) can't isolate layers of an application. In fact, quite the contrary: OO uses private elements, module (package) systems, and design patterns to achieve the same results. (I couldn't help but think about model-view-controller and Ruby on Rails)

I highly recommend these lectures for those of you unfamiliar with the functional-programming paradigm.

Structure and Interpretation of Computer Programs

2008-07-10T22:24:00.004-04:00

In addition to the Project Euler problems, I've been watching lectures for Structure and Interpretation of Computer Programs by Hal Abelson and Gerald Jay Sussman. These videos were recorded in 1986 based on their textbook of the same name.

I've watched the first six lectures (1a through 3b) so far. Having learned, done, and taught "programming languages" for close to two decades now, there's not a lot new I'm learning, but it's cool seeing their observations presented clearly and refreshing seeing guys who really get it.

There were at least two things I noticed recently which I'll be blogging about in the next few days, but I figured I should give you all a heads up to get caught up with me!

New Layout

2008-07-10T16:38:00.002-04:00

I've been tweaking my blog the last few days, and the last step (I hope) is changing the layout. It's a fluid layout, so you can get my posts as wide as you like. I'll try to keep the code narrow so that it doesn't force you to go wide, but my previous layout was just way too narrow.

PE Problem #2 in All Languages (Part II)

2008-07-09T16:23:00.002-04:00

In my last post, I described the top-level function for adding up even Fibonacci numbers less than or equal to 4 million. The real kernel of the problem, though, is to compute Fibonacci numbers.

Naively, Fibonacci numbers are computed with an exponential algorithm. I had thought about writing this version because I suspect that even up to 4 million it wouldn't take that long (although in hindsight I'm less sure). Regardless, the challenge of writing a list-generating version sounded more interesting. (I've written the recursive, exponential algorithm too many times to count, so by definition it's not interesting.)

Haskell

How awesome is Haskell?

Don't worry. It's a rhetorical question. I already know that it "blinds you from over-exposure to pure awesomeness" (to paraphrase Po of Kung Fu Panda).

fibList = 1 : 2 : zipWith (+) fibList (tail fibList)

The : operator builds up a list; zipWith applies + to the two lists passed to it. Of course, if you look closely, those two lists are the same list being defined! This works because of Haskell's lazy evaluation. Not even the : operations execute until some other computation actually needs them. So by the time the zipWith is triggered, the first two elements of fibList exist.

To understand the zipWith, let's pretend that fibList is built up this far: [1, 2, 3, 5, 8, 13] (plus a commitment to build more which we'll ignore for now). So the zipWith expression turns into (by substitution):

zipWith (+) [1, 2, 3, 5, 8, 13] [2, 3, 5, 8, 13]

This applies + to each pair of elements from the two lists which results in: [3, 5, 8, 13, 21]. That's how the rest of the Fibonacci numbers are computed—including the elements in that expression!

This does beg the question: what triggers the computation of fibList? Answer: whatever the top-level output routine wants. The main routine (or the tests) request a particular fibSum; the fibSum computation requests Fibonacci numbers from fibList using this function:

takeFibs n = takeWhile (<=n) fibList

This function will only unravel fibList until the limit is reached.

Erlang

For the other languages, I combined the "take" and the "Fibonacci numbers" computations. Take a look at this:

takeFibs(N) ->
 if
   N == 0 -> [];
   true   -> takeFibs(N, 2, 1, [])
    end.

takeFibs(N, First, Second, Fibs) ->
 if
  First > N -> [Second | Fibs];
  true      -> takeFibs(N,
                               First + Second, First,
                               [Second | Fibs])
 end.

There are two versions of takeFibs (completely different functions because they have different numbers of parameters). The first version is to kick off the computation and deals with the low-limit base cases. The second version does the recursion. It uses an accumulator-passing approach to accumulate a list of Fibonacci numbers. The last two Fibonacci numbers computed are passed in First and Second to make it easier to recognize the base case and to compute the next number in the sequence.

There's something about this approach that doesn't quite satisfy me.

Prolog

How does this strike you?

takeFibs(N, L) :-
 N =:= 0 -> L = [];
 N > 0   -> takeFibs(N, 2, 1, [], L).

takeFibs(N, First, Second, Incoming, Outgoing) :-
 First > N  -> Outgoing = [Second | Incoming];
 First =< N -> Next is First+Second,
   takeFibs(N, Next, First, [Second | Incoming], Outgoing).

It's the same approach as with Erlang. Taking a play from the Erlang playbook, I like how the multiple cases work out this time. Since I'm using ->, unproductive paths through the logic are cut off so no checkpoints are left behind.

Ruby

class Integer
  def fibs_upto
    if zero?
      []
    else
      fibs_upto_helper(2, 1, [])
    end
  end

  private
  def fibs_upto_helper(first, second, fibs)
    if first > self
      [second] + fibs
    else
      fibs_upto_helper(first + second, first, [second] + fibs)
    end
  end
end

Same approach as the others. It seems less slick in Ruby.

Python

def fibs_upto(n):
    if n == 0:
        return []
    else:
        return fibs_upto_helper(n, 2, 1, [])

def fibs_upto_helper(n, first, second, fibs):
    if first > n:
        return [second] + fibs
    else:
        return fibs_upto_helper(n, first + second, first, [second] + fibs)

Same song, same verse. About as icky as the Ruby solution.

Options

As I've read up more about Fibonacci numbers, I suspect that a matrix approach might be a little more satisfying. The non-Haskell solutions could be improved if I used infinite-list solutions in those languages, and that would actually be really interesting to work out.

At this point, though, I'm willing to let this problem go since I do have it solved, and my solutions aren't bad.

PE Problem #2 in All Languages (Part I)

2008-07-08T17:15:00.004-04:00

I got busy last week with the holiday, some school obligations, and acting as a chauffeur for my grandma. I wasn't working on Problem #2 the whole time since my last entry, honestly!

Problem #2 of Project Euler is to add up the even Fibonacci numbers up to 4 million. It actually wasn't that hard to put together my solutions (except for the Prolog one).

I'm going to present my solutions in just two posts. In this post, I'll present the top-level functions in all of my languages. In the next post, I'll present the Fibonacci-number generators.

Overview

My take on this problem was to generate Fibonacci numbers in a list (to keep the computation time linear) and then filter out just the even numbers from that list and sum them up.

So the top level function has to call another function to generate the Fibonacci numbers, filter out the even Fibonacci numbers, and sum those numbers up.

Haskell

I started with Haskell because generating Fibonacci numbers are really cool in Haskell—but that's for the next post. The top level function is still pretty cool:

fibSum n = sum $ filter even $ takeFibs n

takeFibs generates a list of Fibonacci numbers less than or equal to n.

Erlang

I took on Erlang second.

fibSum(N) -> lists:sum(
  lists:filter(fun(E) -> (E rem 2) =:= 0 end, takeFibs(N))
  ).

The "even" function reads little odd to me, but otherwise I like this.

Prolog

Prolog was a bit annoying, but not this bit:

fibSum(N, Sum) :-
 takeFibs(N, Fibs),
 include(even, Fibs, EvenFibs),
 sumlist(EvenFibs, Sum).
even(N) :- N mod 2 =:= 0.

Most of this was cribbed from one of my Prolog solutions for Problem #1.

Python

I hate code that relies on indentation. Yuck. Maybe I'll get use to it. The code itself is okay.

def fib_sum(n):
    return sum(filter(even, fibs_upto(n)))
def even(n):
    return n % 2 == 0

I switched to "fibs_upto" since it made a bit more sense to me than "takeFibs".

Ruby

And, finally, Ruby!

class Integer
  def fib_sum
    fibs_upto.
      select { |n| n.even? }.
      inject(0) { |sum, n| sum + n }
  end
end

It's not bad, but kind of verbose.

PE Problem #1 in Erlang

2008-06-26T22:56:00.005-04:00

And now I finally get to Erlang. I actually wrote up the code this past weekend, but a few other things got in the way of this blog entry. I'm sure you were all waiting on pins and needles.

The Erlang Code

sum35(N) -> sum([X || X <- seq(0,N), interesting_number(X)]).
interesting_number(N) -> (N rem 3 == 0) or (N rem 5 == 0).

What surprised me the most was how much Erlang borrowed its syntax from Prolog. I had been alerted to this by a student who looked at the language for a programming languages course. I would have guessed that Erlang's syntax had been based more on Haskell (and Miranda and Clean).

As for the solution, it seems pretty straightforward with yet another list comprehension. I'm not sure if I like the || for the "such that" in the list comprehension, but that's fairly minor.

sum and seq come from the list library.

Problems with Erlang

The biggest problem I had with Erlang was getting a unit-testing library. My Erlang installation (from MacPorts) came with Erlang/OTP Test Server, but it's very, very heavyweight. eUnit, though, is very lightweight and very similar to the other xUnit libraries I've used. Unfortunately, it wasn't installed by default, and it took some time getting that right.

Otherwise, it was just the standard amount of time to figure out how to write and run the tests and command-line program.

What's Erlang good for?

Unfortunately, it's unlikely that the Project Euler problems will ever require me to use the distributed computing abilities of Erlang. It's still good to use Erlang for these problems so that I get practice with the syntax. (We'll see how long it takes me to change this tune!)

Next...

It's time to move on to Problem #2.

My Wordles

2008-06-25T16:04:00.004-04:00

On J. B. Rainsberger's blog this morning, he presented an artistic tag-cloud made at Wordle. It'll work off of your del.icio.us bookmarks or any text you enter in. I couldn't resist!

From the last couple of entries on this blog:

I like how the language names are so large as well as interestingNumber. I'm less happy seeing "think" so large because I think "I think" is used too much by me. (What an awkward sentence just for a bad joke!)

I also did up my del.icio.us bookmarks:

I like how big "java", "ruby", and "rails" are; I'm a bit surprised by how big "webdesign" is. I also like how "skepticism" kind of sticks out there on the left, but I'm surprised at how small it is.

Efficiency of cond statements

2008-06-24T16:47:00.006-04:00

"Premature optimization is the root of all evil." --Donald Knuth

This is the second point which Walz raised in a comment which I thought deserved a separate blog entry. (You can read the original comment and the first point I liked.)

Walz's second observation is about efficiency:

cond statements [in LISP are] merely a construction for neat multi-branching (as opposed to nested ifs, which get ugly fast with all the parenthesis) ... I would have gone on to assume that this constant time aspect was the fundamental reason for the restrictions on C family switch statements were it not for my experiences with more expressive case statements in Haskell.

He goes on to ask where Ruby's case statement lives in this spectrum.

I should admit up front that I have my own personal demons concerning the switch statement which I need to work out myself (partially through this blog). Walz is pretty much on target here.

Performance of C `switch`

The restrictions on C's switch statement are definitely for performance reasons. Several years ago I played around with switch and if statements to see how significant the difference was; I wrote up my results.

I plan to revisit those results sometime on this blog and rant further about the switch statement. There are ways to lift the restrictions and keep performance.

The `cond` expression

My experience with cond comes from Scheme, but I think it also applies to LISP in this case: cond is implemented as a macro which expands into the standard multibranch if. It certainly has those semantics, and so it'll have the same running time.

Scheme also has a case expression which is more along the lines of a C switch statement. (The main difference would be no fall-through behavior.) But even this is turned into a mutlibranch if with member? tests.

Pattern Matching in Haskell

I'm curious though about Walz's comment about Haskell. Are you claiming that pattern matching is expressive or efficient? It's wonderfully expressive, but it must be, in general, as expensive as a multibranch if.

That's because, in general, the patterns can be very, very nested. Since the nested components will be stored as pointers, it'll require traipsing through memory in order to find the proper match. It can't be codified in a simple look-up table (like a switch can).

Ruby's `case`

Ruby's case is wonderfully expressive, even beyond the cond expression.

case grade
  when 93..100 then "A"
  when 90..92  then "A-"
  when 87..89  then "B+
  ...

You can even put in regular expressions in for the when clauses.

Of course, all this expressiveness means the efficiency is like a multibranch if.

Back to efficiency

So the Scheme case and cond, Haskell pattern matching, and the Ruby case all run (I claim) as multibranch ifs. They don't have to. A clever compiler could recognize when these language features were being used like a switch and generate a look-up table.

The real power is in their expressiveness. Somehow the switch statement keeps us all looking at these constructs in terms of efficiency, and that's a huge double mistake.

It's a mistake because it stinks of "premature optimization" (hence my opening Knuth quote). If a cond is slow but could be made faster but executed only once when the program is started, you gain virtually nothing by optimizing it.

It's also a mistake because in the general, expensive situations, the C code won't be any faster (algorithmically). You just won't be able to use a switch statement.

In terms of expressiveness, they all win, certainly over the return guards—which is what started all this in the first place.

Programming During Recess

Employed Again!

The Longer Story

Funny Code Comments

I'm Male and 26--35 Years Old, and I Write Happy

Tar Archive Problems Upgrading RVM to 1.0.2

LaTeX Anecdote #2: My Dissertation

One Minute LaTeX

Twelve Hour Word

What about Today?

Next Time

LaTeX Anecdote #1: The Large, Multi-Author Document

I Hate MS Word

Should Have Used LaTeX

Next Time

Typesetting with LaTeX

Me and LaTeX

What Is LaTeX?

Examples

Next Time

Upgrading to Rails 3 and RSpec 2, Part 5: Cucumber

Goodbye, Webrat. Hello, Capybara.

Rename Method

Date and Time Selection

Next Time

Upgrading to Rails 3 and RSpec 2, Part 4b: Recursive Rendering

Recursive Renders

It's Broken!

Solution #1: Helper Methods

Solution #2: Create an Alias

Next Time

Upgrading to Rails 3 and RSpec 2, Part 4a: Views

New Handles

Completely New Way to Assign Instance Variables

Render Without an Argument

Render Without an Argument with Locals

New Records

Next Time...

Parallel Programming the Functional Way

Multicore Programming in Haskell

Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful

Use Prerelease Mongrel with Rails 3 Release Candidate and Ruby 1.9.2

Upgrading to Rails 3 and RSpec 2, Part 3: Router

The New DSL

:as versus :path

Testing a Route

Testing _url and _path Helpers

Next Time...

Upgrading to Rails 3 and RSpec 2, Part 2: Controllers

Arel in Controllers

Integer Params in Controller Specs

Params in Unhappy-Path Tests

Next Time...

Upgrading to Rails 3 and RSpec 2, Part 1: Introduction

Tab Candy for Firefox

"Calling a method in Rails::Application is deprecated..."

But I Am Using the New Routing DSL!!!

More Fibers for Rails

Parrot (PIR) Tutorial

String, StringBuilder, StringBuilder, and Performance

Piquing Claim

Performance Experiment

Lessons Learned from Source Code

What to Use

Updated MongoDB cleaning

Cleaning up a MongoDB Database after RSpec and Cucumber

Cleaning a MongoDB Database for RSpec

Cleaning a MongoDB Database for Cucumber

Legos for Adults

My Rails 3 App with jQuery, MongoMapper, RSpec, Cucumber, and Ruby 1.9.2

My Sources

Creating the App

jQuery

Gems

Mongo

Generate Testing Frameworks

Ready to Go!

Happy with My Backup Service

Mozy, You're Okay

Mozy, You Suck

`:as` versus `:path`

Testing `_url` and `_path` Helpers

Haskell's `Num` Class

Algorithm Implemented as Part of `Num` Instance