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 functional programming
Tags folds, fp, haskell, python
20 comments
no trackbacks
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 functional programming
Tags continuations, fp, oleg
no comments
no trackbacks
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?
Posted in functional programming, ruby
Tags fp, functional_programming, ruby
2 comments
no trackbacks
readers