Thought-provoking read on using Mirrors for language reflection, via @joshsusser

@RonJeffries @zspencer today's reading is

RT @jakedonham: today is a great day to try OCaml

The mathematics used in OpenGL & co aren't actually very hard, just kinda weird. If you have taken an introductory course on linear algebra, that's pretty much all the knowledge you need (plus some trigonometry, probably, at least for a waving flag). You could for instance check out the linear algebra lectures on ocw.mit.edu with Prof. Gilbert Strang, he does a pretty good job at explaining the core concepts of things.
A GPU is basically (super-simplified) a matrix multiplication engine, so once you've understand how matrix-vector multiplication works, you've pretty much got the gist of things. Then you only need to add on top of that the weirdness that OpenGL actually uses four dimensions for everything, to keep track of translations. I think the only other hard thing is probably learning about u,v coordinates (aka texture coordinates), but it's not really that hard either.

While reading this article, I ran into a concept named Jackson Structured Programming (JSP). JSP is mainly a design technique (with its own diagram syntax and CASE tools), but one of its main insights is a very intuitive programming pattern. This is what I want to focus on in this post.

Consider the following problem:

A file is a sorted list of lines. We want to produce a report from this file, displaying each kind of line only once, along with a count of how many times it appears in the file.

For example, take this file:

aaaa
bbbb
bbbb
bbbb
cccc
cccc
dddd
dddd
dddd
dddd
eeee
ffff
ffff
gggg

The report produced from it would be:

aaaa: 1
bbbb: 3
cccc: 2
dddd: 4
eeee: 1
ffff: 2
gggg: 1

Michael A. Jackson, the original developer of the JSP technique, has an interesting paper on this subject called "Getting It Wrong – A Cautionary Tale" (PDF link), in which he explains the common way to solve this problem and its pitfalls. The code samples are in COBOL, but other than that the article is quite accessible. I encourage you to read it, or at least think about how you would write the code to solve this task before reading on.

There’s no catch here. The problem is very simple – there’s no magic algorithm that’s needed to solve it. This post deals with the particular implementation technique at the lowest level.

When one thinks about a solution, most likely the first line of thought is "OK, so we go over the file line by line, and for each line…". That’s correct, of course, but stated like this it hints at a code pattern. In Python, for example, such code is likely to be based on:

for line in stream:
# do something

Here’s the full implementation, translating the code sample in the Wikipedia page on JSP linked earlier into Python:

def process_normal(stream):
""" Process the stream using "normal" looping techniques
"""
count = 0
first_line_of_group = None
for line in stream:
if first_line_of_group and first_line_of_group != line:
print_line_with_count(first_line_of_group, count)
if not first_line_of_group or first_line_of_group != line:
count = 0
first_line_of_group = line
count += 1
if first_line_of_group:
print_line_with_count(first_line_of_group, count)

This code is, as far as I can tell, correct. However, it looks a bit complex. It’s not bad, and it’s not hard to understand, but there’s a better way.

Here it is. All it does is restructure the code a bit, deviating from the "normal" looping pattern, instead reading one line in advance and then keeping an invariant that when the main loop cycles it already has the next line handy in line:

def process_jsp(stream):
""" Process the stream using the JSP looping technique with read-ahead
"""
line = stream.readline()
while line:
count = 0
first_line_of_group = line
while line and line == first_line_of_group:
count += 1
line = stream.readline()
print_line_with_count(first_line_of_group, count)

I don’t know about you, but it just strikes me how much simpler this code is to comprehend. You can almost read the code aloud and just understand it. Simpler to comprehend, hence much less likely to contain bugs (which is the point Jackson is trying to make in his paper).

At this point I could stop and say – "oh, cool, a nice coding pattern that makes some problems more natural to express". But I’m not satisfied. I’m trying to understand what happened here. Why did such a seemingly simple code change make the algorithm much easier to express?

Here’s what I think. The "normal" approach just implements a state machine. "For each line…" we have a state. The loop body then just acts according to the state. Since the state is not entirely trivial, to handle it also requires more than a minimal amount of code.

On the other hand, in the JSP approach, most of the state is implicitly encoded in the code itself. Let me repeat that in other words – the state is still there, but it’s implicit. Splitting the line reading to two places and keeping the invariant on the main loop allows us to express the state in the flow itself, instead of with explicit conditions.

And I have Déjà vu here, because I’ve already written about something like this – in the article "Co-routines as an alternative to state machines". That article explains how, by using co-routines, we can avoid an explicit state machine and thus considerably simplify the code. By writing the code in a certain way, the state becomes implicitly encoded in the control flow instead.

To be frank I’m not yet 100% sure on the connection – after all, the code presented in process_jsp is not really a co-routine. But I can’t escape the hunch that these concepts are related. If you have any insights on this, please share them!

Another familiarity I see here is with the method of coding recursive-descent parsers (I’ve written a few posts on RD parsers in the past, for example this one). When implementing an RD parser, the code consists of a set of mutual-calling functions that represent grammar structures (for example "Statement", "Identifier", "Binary operation", etc.) Each such function assumes the current token is available, without it having to read it from the input. When the parsing of a construct finishes, the next token is read – for the sake of the next parsing function, not this one. Trying to code a RD parser differently – having each parsing function getting its own token prior to looking at it – results in much more complicated code. I think this is somewhat similar to the pattern presented here.

To conclude, "a-ha!" moments can often come from examining the simplest things. Personally I feel that understanding the coding pattern presented in this post helps me see things more clearly, and helps understand other concepts a bit better. I was aware for a long time that simply changing the order of operations in such algorithms (i.e. process first, then read next input) may make the code simpler, and also used the technique myself, but I feel that only now I also understand why this is so. I hope I have managed to get the point across

Related posts:Parsing C: more on #line directives In a previous post I discussed a few issues that...lesson for today: caveat in C++ line-reading How many times have you written this code in C++:...

Multi-language REPL running in-browser using EMScripten

A functional/logic programming language

Occam-PI - a CSP-inspired language

Interesting series of C-to-Go translations.

A lovely strange loop of a post: a literate program about literate programming. Thanks to Larry Marburger for pointing it out to me.

Ruby doesn’t have overloaded methods, which are methods with the same name, but different signatures when you consider the argument lists and return values. This would be somewhat challenging to support in a dynamic language with very flexible options for method argument handling.

You can “simulate” overloading by parsing the argument list and taking different paths of execution based on the structure you find. This post discusses how pattern matching, a hallmark of functional programming, gives you powerful options.

First, let’s look at a typical example that handles the arguments in an ad hoc fashion. Consider the following Person class. You can pass three arguments to the initializer, the first_name, the last_name, and the age. Or, you can pass a hash using the keys :first_name, :last_name, and :age.

require "rubygems"
require "spec"

class Person
attr_reader :first_name, :last_name, :age
def initialize *args
arg = args[0]
if arg.kind_of? Hash # 1
@first_name = arg[:first_name]
@last_name = arg[:last_name]
@age = arg[:age]
else
@first_name = args[0]
@last_name = args[1]
@age = args[2]
end
end
end

describe "Person#initialize" do
it "should accept a hash with key-value pairs for the attributes" do
person = Person.new :first_name => "Dean", :last_name => "Wampler", :age => 39
person.first_name.should == "Dean"
person.last_name.should == "Wampler"
person.age.should == 39
end
it "should accept a first name, last name, and age arguments" do
person = Person.new "Dean", "Wampler", 39
person.first_name.should == "Dean"
person.last_name.should == "Wampler"
person.age.should == 39
end
end

The condition on the # 1 comment line checks to see if the first argument is a Hash. If so, the attribute’s values are extracted from it. Otherwise, it is assumed that three arguments were specified in a particular order. They are passed to #initialize in a three-element array. The two rspec examples exercise these behaviors. For simplicity, we ignore some more general cases, as well as error handling.

Another approach that is more flexible is to use duck typing, instead. For example, we could replace the line with the # 1 comment with this line:

if arg.respond_to? :has_key?

There aren’t many objects that respond to #has_key?, so we’re highly confident that we can use [symbol] to extract the values from the hash.

This implementation is fairly straightforward. You’ve probably written code like this yourself. However, it could get complicated for more involved cases.

Pattern Matching, a Functional Programming Approach

Most programming languages today have switch or case statements of some sort and most have support for regular expression matching. However, in functional programming languages, pattern matching is so important and pervasive that these languages offer very powerful and convenient support for pattern matching.

Fortunately, we can get powerful pattern matching, typical of functional languages, in Ruby using the Case gem that is part of the MenTaLguY’s Omnibus Concurrency library. Omnibus provides support for the hot Actor model of concurrency, which Erlang has made famous. However, it would be a shame to restrict the use of the Case gem to parsing Actor messages. It’s much more general purpose than that.

Let’s rework our example using the Case gem.

require "rubygems"
require "spec"
require "case"

class Person
attr_reader :first_name, :last_name, :age
def initialize *args
case args
when Case[Hash] # 1
arg = args[0]
@first_name = arg[:first_name]
@last_name = arg[:last_name]
@age = arg[:age]
else
@first_name = args[0]
@last_name = args[1]
@age = args[2]
end
end
end

describe "Person#initialize" do
it "should accept a first name, last name, and age arguments" do
person = Person.new "Dean", "Wampler", 39
person.first_name.should == "Dean"
person.last_name.should == "Wampler"
person.age.should == 39
end
it "should accept a has with :first_name => fn, :last_name => ln, and :age => age" do
person = Person.new :first_name => "Dean", :last_name => "Wampler", :age => 39
person.first_name.should == "Dean"
person.last_name.should == "Wampler"
person.age.should == 39
end
end

We require the case gem, which puts the #=== method on steroids. In the when statement in #initialize, the expression when Case[Hash] matches on a one-element array where the element is a Hash. We extract the key-value pairs as before. The else clause assumes we have an array for the arguments.

So far, this is isn’t very impressive, but all we did was to reproduce the original behavior. Let’s extend the example to really exploit some of the neat features of the Case gem’s pattern matching. First, let’s narrow the allowed array values.

require "rubygems"
require "spec"
require "case"

class Person
attr_reader :first_name, :last_name, :age
def initialize *args
case args
when Case[Hash] # 1
arg = args[0]
@first_name = arg[:first_name]
@last_name = arg[:last_name]
@age = arg[:age]
when Case[String, String, Integer]
@first_name = args[0]
@last_name = args[1]
@age = args[2]
else
raise "Invalid arguments: #{args}"
end
end
end

describe "Person#initialize" do
it "should accept a first name, last name, and age arguments" do
person = Person.new "Dean", "Wampler", 39
person.first_name.should == "Dean"
person.last_name.should == "Wampler"
person.age.should == 39
end
it "should accept a has with :first_name => fn, :last_name => ln, and :age => age" do
person = Person.new :first_name => "Dean", :last_name => "Wampler", :age => 39
person.first_name.should == "Dean"
person.last_name.should == "Wampler"
person.age.should == 39
end
it "should not accept an array unless it is a [String, String, Integer]" do
lambda { person = Person.new "Dean", "Wampler", "39" }.should raise_error(Exception)
end
end

The new expression when Case[String, String, Integer] only matches a three-element array where the first two arguments are strings and the third argument is an integer, which are the types we want. If you use an array with a different number of arguments or the arguments have different types, this when clause won’t match. Instead, you’ll get the default else clause, which raises an exception. We added another rspec example to test this condition, where the user’s age was specified as a string instead of as an integer. Of course, you could decide to attempt a conversion of this argument, to make your code more “forgiving” of user mistakes.

Similarly, what happens if the method supports default values some of the parameters. As written, we can’t support that option, but let’s look at a slight variation of Person#initialize, where a hash of values is not supported, to see what would happen.

require "rubygems"
require "spec"
require "case"

class Person
attr_reader :first_name, :last_name, :age
def initialize first_name = "Bob", last_name = "Martin", age = 29
case [first_name, last_name, age]
when Case[String, String, Integer]
@first_name = first_name
@last_name = last_name
@age = age
else
raise "Invalid arguments: #{first_name}, #{last_name}, #{age}"
end
end
end

def check person, expected_fn, expected_ln, expected_age
person.first_name.should == expected_fn
person.last_name.should == expected_ln
person.age.should == expected_age
end

describe "Person#initialize" do
it "should require a first name (string), last name (string), and age (integer) arguments" do
person = Person.new "Dean", "Wampler", 39
check person, "Dean", "Wampler", 39
end
it "should accept the defaults for all parameters" do
person = Person.new
check person, "Bob", "Martin", 29
end
it "should accept the defaults for the last name and age parameters" do
person = Person.new "Dean"
check person, "Dean", "Martin", 29
end
it "should accept the defaults for the age parameter" do
person = Person.new "Dean", "Wampler"
check person, "Dean", "Wampler", 29
end
it "should not accept the first name as a symbol" do
lambda { person = Person.new :Dean, "Wampler", "39" }.should raise_error(Exception)
end
it "should not accept the last name as a symbol" do
end
it "should not accept the age as a string" do
lambda { person = Person.new "Dean", "Wampler", "39" }.should raise_error(Exception)
end
end

We match on all three arguments as an array, asserting they are of the correct type. As you might expect, #initialize always gets three parameters passed to it, including when default values are used.

Let’s return to our original example, where the object can be constructed with a hash or a list of arguments. There are two more things (at least …) that we can do. First, we’re not yet validating the types of the values in the hash. Second, we can use the Case gem to impose constraints on the values, such as requiring non-empty name strings and a positive age.

require "rubygems"
require "spec"
require "case"

class Person
attr_reader :first_name, :last_name, :age
def initialize *args
case args
when Case[Hash]
arg = args[0]
@first_name = arg[:first_name]
@last_name = arg[:last_name]
@age = arg[:age]
when Case[String, String, Integer]
@first_name = args[0]
@last_name = args[1]
@age = args[2]
else
raise "Invalid arguments: #{args}"
end
validate_name @first_name, "first_name"
validate_name @last_name, "last_name"
vali[…]

Over at Seldo.com, there’s a handy table of HTTP codes, their official meanings and their everyday office culture conversational equivalents. Here are some examples:

Code
Status
Conversational Equivalent

100
Continue
Uh-huh…

101
Switching protocols
Let’s take this offline

200
OK
OK

201
Created
I wrote you an email about that

300
Multiple choices
You can get that from Bob, John or Sue

301
Moved permanently
That’s Bob’s job

401
Unauthorized
You’re not allowed to know that

402
Payment required
Maybe a twenty would refresh my memory

404
Not found
I have no idea what you’re talking about

406
Not acceptable
Maybe when you’re older

500
Internal server error
Drooling from side of mouth

503
Service unavailable
I am way too busy to deal with your shit

Technorati Tags: HTTP,HTTP codes,funny,photo,LOLcats,office culture

A critique from the maintainability standpoint.

I've lately been thinking about Twitter. I wanted some way to quickly post tweets from the command line. But I also wanted to be able to receive them in a non-intrusive way on all my machines. And I wanted to work with Twitter and Identi.ca both.

Nothing quite existed to do that, so I wrote Twidge.

Twidge is a command-line Twitter client. It can be run quite nicely interactively, with output piped through less. Or you can run it as a unidirectional or bidirectional mail gateway. Or you can use its parser-friendly output options to integrate it with shell scripts or other programs.

It's got an 11-page manual (which is also its manpage). User-friendly in the best tradition of command line programs.

And it's released today. The source packages include the debian/ directory for you to use for building them, but I've also posted an i386 binary that runs on etch and sid on my webpage, until it gets out of NEW.

See the homepage for more info.

Oh, it's written in Haskell, by the way.

To use an idiom that Bryan Liles effectively coined at this year's Ruby Hoedown, at Hashrocket, we "pair all the fucking time". It is a vital part of The Hashrocket Way, our internal philosophy of how to most productively service our clients:


The photo above captures a normal morning at Hashrocket headquarters, where every desk is set up for effective pair-programming: 30" monitor, dual keyboards, dual mice. Carmelyne Thompson and Wes Gibbs are the pair in the foreground.
Veez Remsik, my inspiration for this post and one of Hashrocket's Rescue Mission experts, gives us a must-read personal account of pair-programming as a way of life:
Hashrocket has a few core philosphies that are essentially required for team members. Agile development processes, an adherence to ruby and rails best practices and idioms, and a firm belief in pair programming are three of the biggies. Of these three, pair programming is the technique that has changed me most, and required the most change in my thinking. And not surprisingly, pair programming has proven the most critical to my success at Hashrocket.
Veez has a traditional software development background (unlike the one that several of us 'rocketeers cultivated at places like Thoughtworks). I like the way he describes himself pre-Hashrocket: "You know, the one who does his best work in the morning with his headphones on and drinking an obscenely large coffee. The guy who types madly for a few select hours a day and, during those few hours, produces as much as regular-speed developers do over the course of a day."


Durran Jordan and Matthew Bass pair on our latest 3-2-1 Launch project. Quite often, one of the keyboard/mouse sets is replaced by an actual MacBook Pro in conjunction with the most excellent teleport utility from abyssoft.
Most Rails people I know profess adherence to Agile practices and principles, yet judging from the anecdotal evidence I've collected at conferences and comments made by our guest stars, pair-programming is still very much the exception. Make that real pair-programming, in the extreme programming sense, where all production code is produced by two developers sharing control of one workstation.


Getting a chance to truly pair for the first time is turning out to be one of our "guest stars" favorite experiences at Hashrocket. In the pic above, I captured Paul Barry and Hampton Catlin getting their first taste of pair-programming the way it's supposed to be done.
There are certainly challenges to making pair-programming part of normal business practices. Starting with the fact that it implies keeping an even number of people assigned to a project on a daily basis. Even at ThoughtWorks, where Agile is an important part of the culture, management did not necessarily make this aspect of pairing easy for us — as the principle "resource manager" of Hashrocket, I have to juggle the financial needs of our clients with our need to work in pairs. It's occasionally very tricky, but when you do it all the time, I assure you it gets easier.
I'm trying to get back into blogging on a regular basis. The "Hashrocket Way" is a term that has gotten much traction for us internally as a catch-all description of what makes us special, and I plan to write about different aspects of that as much as possible.

Google (my current employer) has finally open sourced protocol buffers, the data interchange format we use for internal server-to-server communication. The blogosphere’s response? “No wireless. Less space than a Nomad. Lame.”

Aaaaanyway…

Protocol buffers are “just” cross-platform data structures. All you have to write is the schema (a .proto file), then generate bindings in C++, Java, or Python. (Or Haskell. Or Perl.) The .proto file is just a schema; it doesn’t contain any data except default values. All getting and setting is done in code. The serialized over-the-wire format is designed to minimize network traffic, and deserialization (especially in C++) is designed to maximize performance. I can’t begin to describe how much effort Google spends maximizing performance at every level. We would tear down our data centers and rewire them with $500 ethernet cables if you could prove that it would reduce latency by 1%.

Besides being blindingly fast, protocol buffers have lots of neat features. A zero-size PB returns default values. You can nest PBs inside each other. And most importantly, PBs are both backward and forward compatible, which means you can upgrade servers gradually and they can still talk to each other in the interim. (When you have as many machines as Google has, it’s always the interim somewhere.)

Comparisons to other data formats was, I suppose, inevitable. Old-timers may remember ASN.1 or IIOP. Kids these days seem to compare everything to XML or JSON. They’re actually closer to Facebook’s Thrift (written by ex-Googlers) or SQL Server’s TDS. Protocol buffers won’t kill XML (no matter how much you wish they would), nor will they replace JSON, ASN.1, or carrier pigeon. But they’re simple and they’re fast and they scale like crazy, and that’s the way Google likes it.

The Sinatra framework has a fairly unmapped deployment landscape.  The standard answer is to use Thin or Mongrel, and have a reverse proxy (lighttpd, or nginx, or even Apache) point to your bundle of servers.

But of course that isn’t always possible.  Cheap shared hosting (like Dreamhost) won’t let you run Thin or Mongrel, or setup reverse proxies (at least on the shared plan).

Luckily Rack supports various connectors, including CGI and FastCGI.  Unluckily for us, FastCGI doesn’t quite work with the current Sinatra git HEAD.

To get a dumb “hello world” Sinatra application up and running on dreamhost involves pulling down the current Sinatra code, and hacking at it a bit.  Don’t worry, it’s mostly just commenting out a few lines, and tweaking another line.

Files needed:

.htaccess
dispatch.fcgi
Tweaked sinatra.rb

.htaccess

RewriteEngine on
 
AddHandler fastcgi-script .fcgi
Options +FollowSymLinks +ExecCGI
 
RewriteRule ^(.*)$ dispatch.fcgi [QSA,L]

dispatch.fcgi

#!/usr/bin/ruby
 
require 'sinatra/lib/sinatra.rb'
require 'rubygems'
 
fastcgi_log = File.open("fastcgi.log", "a")
STDOUT.reopen fastcgi_log
STDERR.reopen fastcgi_log
STDOUT.sync = true
 
set :logging, false
set :server, "FastCGI"
 
module Rack
class Request
def path_info
@env["SCRIPT_URL"].to_s
end
def path_info=(s)
@env["SCRIPT_URL"] = s.to_s
end
end
end
 
load 'test.rb'

sinatra.rb - Replace this function with the new version here.

def run
begin
#puts "== Sinatra has taken the stage on port #{port} for #{env} with backup by #{server.name}"
require 'pp'
server.run(application) do |server|
trap(:INT) do
server.stop
#puts "\n== Sinatra has ended his set (crowd applauds)"
end
end
rescue Errno::EADDRINUSE => e
#puts "== Someone is already performing on port #{port}!"
end
end

Hopefully that helps somebody get up and running, check out #sinatra on freenode.org to ask questions, but be patient, we’re friendly, but work day jobs.

 

An intro to PLT Scheme via graphics programming.

Tom is a software environment for defining transformations in Java.

It's a common misconception that dynamic languages inherently have to be slow. This seems to be a deeply ingrained reflex nowadays. Probably trained by years of suffering from simplistic implementations, often helped by bad language design decisions.

Dylan is an advanced, object-oriented, dynamic language which supports rapid program development. When needed, programs can be optimized for more efficient execution by supplying more type information to the compiler. Nearly all entities in Dylan (including functions, classes, and basic data types such as integers) are first class objects. Additionally Dylan supports multiple inheritance, polymorphism, multiple dispatch, keyword arguments, object introspection, macros, and many other advanced features

XMF is an industry strength extensible programming language designed for Language Oriented Programming. All aspects of XMF can be easily extended or redefined at run-time allowing the dynamic construction of domain specific languages (DSLs) which can be used either standalone or weaved into existing DSLs.

This is the first episode in a tutorial series on building a compiler with the Parrot Compiler Tools.

Parallel Each (for ruby with threads)

Neko is a high-level dynamically typed programming language which can also be used as an embedded scripting language. It has been designed to provide a common runtime for several different languages. Neko is not only very easy to learn and use, but also has the flexibility of being able to extend the language with C libraries. You can even write generators from your own language to Neko and then use the Neko Runtime to compile, run, and access existing libraries.

Why programming language design repeats itself.