Thinking algebraically: a functional-programming dividend that pays during your imperative-programming day job

Posted by Tom Moertel Thu, 21 Aug 2008 01:50:00 GMT

Although at work I code mostly in Python – a language from which lambda and map were nearly removed – I still find that functional-programming experience has its benefits. One of the “functional-programming dividends” I notice most often is insight gained from considering problems from an algebraic perspective.

Recently, for example, I had a small parsing problem. I had to write code that, given a simple grammar specification as input, emits a regular expression that matches the language generated by the grammar.

Here’s a simplified version of the problem. A grammar specification is limited to a series of one or more atoms. For example, “a b c” represents the atom “a”, followed by the atom “b”, followed by the atom “c”. To generate the grammar, the series of atoms is interpreted such that each atom (except the last) generates a production rule of the following form:

atom_rule ::=
  <the literal atom> (SPACE <the next rule> | NOTHING)

(SPACE represents literal white space and NOTHING represents an empty string.) The grammar as a whole is rooted in the first atom’s rule.

Thus the specification “a b c” represents the following grammar:

grammar ::= a_rule
a_rule  ::= "a" (SPACE b_rule | NOTHING)
b_rule  ::= "b" (SPACE c_rule | NOTHING)
c_rule  ::= "c" 

Note that the final atom’s production matches only the literal atom itself: it has no following rule on which to chain.

The grammar, in turn, generates the following language:

a
a b
a b c

Thus, given the grammar specification “a b c”, my code had to produce a regular expression that would match “a”, “a b”, or “a b c”.

At this point, please stop for a moment and think about this little programming exercise. Do any solutions leap to mind? How would you approach the problem? Form your opinions now, because I’m going to ask you about them later. (If you’re feeling especially caffeinated, try coding a solution before reading on.)

Read more...

Posted in
Tags , , ,
20 comments
no trackbacks
Reddit Delicious

Oleg's great way of explaining delimited continuations

Posted by Tom Moertel Mon, 05 May 2008 13:58:00 GMT

There’s a great way to explain delimited continuations in the notes of Oleg’s Continuation Fest talk on using delimited continuations for CGI programming. Just so it doesn’t get overlooked, here it is:

I’m obsessed in pointing out that every programmer already knows and understands the delimited continuations; they might not know that word though. Everyone knows that when a process executes a system call like read, it gets suspended. When the disk delivers the data, the process is resumed. That suspension of a process is its continuation. It is delimited: it is not the check-point of the whole OS, it is the check-point of a process only, from the invocation of main() up to the point main() returns. Normally these suspensions are resumed only once, but can be zero times (exit) or twice (fork).

I especially like the final part about exit and fork, which drives home the notion that something more subtle than returning from a typical function call is going on. If anybody is confused over what suspended means, that last part ought to clear things up.

The next time I need to explain delimited continuations, I know how I’m going to do it.

Posted in
Tags , ,
no comments
no trackbacks
Reddit Delicious

Composing functions in Ruby

Posted by Tom Moertel Fri, 07 Apr 2006 15:55:00 GMT

One of the things I miss when coding in Ruby is inexpensive function composition. In Haskell, for example, I can compose functions using the dot (.) operator:

inc        = (+1)
twice      = (*2)
twiceOfInc = twice . inc
Because of Ruby’s open classes, however, I can easily add the feature to the language. In the code below, I introduce Proc.compose and overload the star (*) operator for the purpose:
# func_composition.rb
class Proc
  def self.compose(f, g)
    lambda { |*args| f[g[*args]] }
  end
  def *(g)
    Proc.compose(self, g)
  end
end

And that’s all it takes:

$ irb --simple-prompt -r func_composition.rb

>> inc = lambda { |x| x + 1 }
=> #<Proc:0x00002aaaaaad7810@(irb):1>

>> twice = lambda { |x| x * 2 }
=> #<Proc:0x00002aaaaabd2d18@(irb):2>

>> inc[1]
=> 2

>> twice[2]
=> 4

>> twice_of_inc = twice * inc
=> #<Proc:0x00002aaaaab32458@./func_composition.rb:3>

>> twice_of_inc[1]
=> 4

>> twice_of_inc[2]
=> 6

Now, isn’t that refreshing?

Update: Vincent Foley pointed out on comp.lang.ruby that Ruby Facets has a nearly identical implementation that also uses the star operator for composition. (Its version of compose, however, is an instance method whereas my version is a class method.)

Posted in ,
Tags , ,
2 comments
no trackbacks
Reddit Delicious