Motivation

I’ve been using Monk with the armonk skeleton for the last couple of weeks to build a little app that monitors Craig’s List searches. Bebop aside, I’ve found it to be a really refreshing experience, but I knew when I started building the app that the vanilla routing DSL wasn’t going to meet my needs (it wasn’t built too!). I also knew I would end up missing the path helpers, targeted filters, resource nesting, and printable routing information from Rails. So! after mocking up a simple DSL and consulting some friends I built and tested this little Sinatra routing extension and dubbed it Bebop in honor of Thelonius Monk.

Examples

Once registered Bebop provides the resource class method on Sinatra::Base as the starting point for building your routes.

require 'sinatra'
require 'bebop'

class MyApp < Sinatra::Base
  register Bebop

  resource :foos do |foos|

    # GET /foos/hello
    foos.get '/hello' do
      'hello world'
    end

    # GET '/foos/goodbye'
    foos.get '/goodbye' do
      'goodbye'
    end
  end
end

Routing Helpers

As illustrated, Bebop can be used for nothing more than prefixing the routes generated by the normal dsl methods with a resource name (’/foos’ in this case). It also provides route helper methods that build RESTful routes for the actions index, new, create, show, edit, update, and destroy.

class MyApp < Sinatra::Base
  register Bebop

  resource :foos do |foos|

    # Get /foos
    foos.index {}

    # GET /foos/:foo_id
    foos.show {}

    # GET /foos/new
    foos.new {}

    # POST /foos
    foos.create {}

    # PUT /foos/:foo_id
    foos.update {}

    # GET /foos/:foo_id/edit
    foos.edit {}

    # DELETE /foos/:foo_id
    foos.destroy {}
  end
end

And if you want to nest your resources bebop handles prepending the routes correctly:

class MyApp < Sinatra::Base
  register Bebop

  resource :foos do |foos|

    foos.resource :bars do |bars|

      # Get /foos/:foos_id/bars
      foos.index {}

      # GET /foos/:foo_id/bars/:bar_id
      foos.show {}
    end
  end
end

Extras

Bebop also extends some of the basic Sinatra functionality like before and after filters and provides new functionality in the form of path helper methods. Filters can target specific routes based on identifier, all routes, or nested resource routes. The only stipulation is that the filters must be defined _before_ the filtered route in the body of the resource block.

class MyApp < Sinatra::Base
  register Bebop

  resource :foos do |foos|

    # To run a filter before all routes
    #
    foos.before :all do
      @all = 'all'
    end

    # To have your filter run before a specific route, the route must be one of the seven helper
    # routes (see example/routes.rb) or specify the :identifier parameter
    #
    foos.before :new do
      @new = 'new'
    end

    foos.new do
      "#{@all} #{@new}" # => 'all new'
    end

    # You can target the vanila methods by providing the :identifier hash option
    #
    # GET /foos/baz
    foos.get '/baz', :identifier => :new do
      @new # => 'new'
    end

    # You can also specify a before filter for nested routes by using the child resource name
    # 
    foos.before :bars do
      @bars = 'some bars'
    end

    foos.resource :bars do |bars|
      bars.get '/some_bars' do
        @bars # => 'some bars'
      end
    end

    foos.get '/bak' do
      @bars # => nil
    end

    # Finally you can specify many different methods in your filters by passing many identifiers
    # 
    foos.before :bak, :baz do
      @bak_baz = "bak 'n' baz"
    end

    foos.get('/something', :identifier => :bak) { @bak_baz }
    foos.get('/anything', :identifier => :baz) { @bak_baz }
  end
end

Path helpers follow a simple naming convention that starts with the original parent resource, all the child resources ordered by nesting, and finishing with the action identifier.

class MyApp < Sinatra::Base
  register Bebop

  resource :foos do |foos|

    foos.resource :bars do |bars|

      # GET /foos/:foo_id/bars/:bar_id/edit
      bars.edit do
        "foo: #{params[:foo_id]} bar: #{params[:bar_id]}"
      end 

      bars.get '/redirect' do

        # Redirects to /foos/1/bars/2/edit
        redirect foos_bars_edit_path(1, 2)
      end
    end
  end
end

Code

Most of the above examples are borrowed from the examples directory in the gem if you are interested. The repo can be found at github, and you can install the gem right now as long as gemcutter.org is one of your sources. As suggested by Damian Janowski I’ll be adding some template helpers and some other goodies soon.

As always feedback and suggestions are welcome!

A friend of mine recently covered deterministic and non-deterministic finite state machines (automata for the cool kids) in one of his classes and passed along a sample problem for me to figure out. Informally, build a dfa that will match a given string against another string in the provided alphabet. An example of this class of problem would be to build one that matches ‘aab’ in any string for the alphabet [ab] (’aaba’ would match, ‘aba’ would not).

To help with visualizing the answer for this example I’ve built a graph of the states and edges that make up our dfa (yay graphviz):

At each state the machine follows the edge that matches the next input from a given string. If it ever hits the fourth state, it’s found a match. Checking the string “baab” for “aab” (for which our machine is built), starting at state one it would take the path 1 -b-> 1 -a-> 2 -a-> 3 -b-> 4, and conclude that “aab” was in fact contained within “baab”.

After doing this on paper I thought it might be fun to use haskell and put together a function that took a dfa, a string to match, and produced a boolean result. The first step I took was to define a data type that represented the dfa.

type Dfa = [State]
data State =  State { identifier :: Int , edges :: [Edge] }
           | FinalState { identifier :: Int, edges :: [Edge] }
data Edge = Edge { action :: (Char -> Bool), edge_identifier :: Int }

This is an informal representation (you can find the formal one here) but here, a dfa is a set of States, a State is an identifier and a set of Edges, and an Edge is a function to determine if it is the edge to follow for a given input and its target state. If this looks a bit clunky at first a cleaned up version is further down.

With my types in place I went ahead with building the functions to traverse a DFA for a given input:

match :: State -> Dfa -> String -> Bool
match current_state _ [] = is_final current_state
match current_state dfa (x:xs) = match next_state dfa xs
                           where next_state = traverse dfa current_state x

traverse :: Dfa -> State -> Char -> State
traverse dfa state = (find_state dfa) . (next_id $ edges state)

is_final (FinalState x y) = True
is_final (State x y) = False

find_state :: Dfa -> Int -> State
find_state (st:sts) state_id  | identifier st == state_id = st
                              | otherwise = find_state sts state_id

next_id :: [Edge] -> Char -> Int
next_id (e:es) input | (action e) input = edge_identifier e
                     | otherwise = next_id es input

The short explanation is that for each input it checks the current state for where it should go next, having determined the destination state’s id it finds that state in the dfa and then proceeds with the rest of the input.

Now, to test a sample graph:

state1 = State 1 [ Edge is_a 2, Edge is_b 1]
state2 = State 2 [ Edge is_a 3, Edge is_b 1]
state3 = State 3 [ Edge is_a 3, Edge is_b 4]
state4 = FinalState 4 [ Edge is_a 4, Edge is_b 4]

graph = [state1, state2, state3, state4]

is_a = (== 'a') 

is_b = (== 'b') 

You’ll note that state4 refers to itself no matter the input so that the match function can operate exhaustively on the input string.

And it works! But the best part of this whole exercise (for me at least) was yet to be realized because this whole first definition has been done in a very inelegant manner by failing to make use of haskell’s lazy nature and recursive data types.

Improved

The first, and easiest, thing to improve is how the Edges reference their destination states. Before, an integer was defined corresponding the identifier of the target state, but in haskell types can be defined recursively:

type Dfa = [State]
data State =  State { edges :: [Edge] }
           | FinalState
data Edge = Edge { condition :: (Char -> Bool), destination :: State }

For reference:

type Dfa = [State]
data State =  State { identifier :: Int , edges :: [Edge] }
           | FinalState { identifier :: Int, edges :: [Edge] }
data Edge = Edge { action :: (Char -> Bool), edge_identifier :: Int }

Not only is the new definition much cleaner, but its also more intuitive. An edge simply hands off the _actual_ state its pointing at. No need to go find it. As a result the code necessary to operate the state machine is also significantly simplified:

match :: State -> String -> Bool
match FinalState _ = True
match (State _) [] = False
match current_state (x:xs) = match next_state xs
    where next_state = traverse (edges current_state) x

traverse :: [Edge] -> Char -> State
traverse (e:es) input | (condition e) input = destination e
                      | otherwise = traverse es input

Notice the type signature of traverse is very intuitive:

traverse :: [Edge] -> Char -> State 

Given a list of edges and an input it will give you the resulting state. Not the id, which would then be used to search for its corresponding state. Finally, the actual graph:

state1 = State [ Edge is_a state2, Edge is_b state1]
state2 = State [ Edge is_a state3, Edge is_b state1]
state3 = State [ Edge is_a state3, Edge is_b state4]
state4 = FinalState 

is_a = (== 'a') 

is_b = (== 'b')

Simplified

By leveraging the recursive reference to another state in the destination field of the Edge type the code shrinks by 3 functions and an enormous amount of complexity. In addition the ability to exhaust the input string or return early on a match with the FinalState constructor allows for a much more readable definition of the match function and the graph itself (no more self referencing weirdness).

I had a lot of fun thinking this through and I would be excited to see some further refinements in the comments from those who know haskell!

I think technically this counts as an application of my readings from Algebra of Programming. Satisfied.

class Cons
  include Enumerable
  attr_accessor :child, :value

  def self.[](value, child=:empty)
    new(value, child)
  end

  def initialize(value, child)
    @value, @child = value, child
  end

  def each
    x = self
    while( x != :empty)
      yield x
      x = x.child
    end
  end
end

x = Cons['MWA', Cons['HAHA', Cons['HAHA']]]
puts x.inject(''){ |acc, x| acc+=x.value  }

As a side note, I hope that someone finds this page looking for a list of negative things about ruby. Maybe if you run the code you’ll find something >:]

[Update: Nick Quaranto was kind enough to respond to my twitter message, and the issue has been resolved. Many thanks Nick!]

So I went to publish RQuery to gem cutter but I got this lovely tidbit:

Pushing gem to Gemcutter...
You do not have permission to push to this gem.

I figured someone had clearly come up with a similar name and applied it to their gem so I went and searched and found:

http://gemcutter.org/gems/rquery

Needless to say I was a little bit bummed, but I thought it odd that its was just a dot one version higher than my last release, and then I noticed that the homepage link points back to none other than my page about the darn gem!

What that hell man, gimme my gem name back!

Inverses are (horrible)^-1

This section gives an introduction to the extremely interesting concept of implementing a function as the inverse of another with zip and unzip as the examples. First, the goal is to build out our zip and unzip functions to satisfy the equation

zip . unzip = id

A couple of notes here. Previously everything has been defined in terms of Haskell, but this is simply an equation. Also, if you’re coming from a non-functional background, id is a function that gives you back the same thing you pass to it. No matter what.

In this case the equation is meant to point out that, if you give unzip a list of pairs (two element tuples) and give that result, a tuple of two lists, to zip, in the end you’ll get back the original list of pairs. So zip compose unzip is equivalent to the id function. You get back just what you gave it.

zip $ unzip [(1,2), (3,4)] = [(1,2), (3,4)]

Before we get into why this is immediately useful lets define the two functions as the book does, but with Haskell.

data Listr a = Empty | Cons (a, Listr a) deriving Show 

foldr' c h Empty = c
foldr' c h (Cons (a, x)) = h a $ foldr' c h x

Our old friends the Cons list and foldr here. If you’re new to these you can check out more information on them here.

unzip' :: Listr (a, b) -> (Listr a, Listr b)
unzip' = foldr' emptys conss
        where emptys = (Empty, Empty)
              conss (a, b) (x, y) = (Cons (a, x) , Cons (b, y))

unzip_' :: Listr (a, b) -> (Listr a, Listr b)
unzip_' Empty = (Empty, Empty)
unzip_' (Cons ((a,b), x)) = (Cons (a, left $ unzip_' x), Cons (b, right $ unzip_' x))
                           where left (x, y) = x
                                 right (x, y) = y

unzip’ and unzip_’ represent two possible ways of unzipping a list of pairs. Of interest here is the fact that my own, much less efficient, implementation involves two “folds” over the data structure, and the one implemented in the book only requires one. Apparently, any and all functions defined by a pair of folds can be defined in terms of a single fold (to be demonstrated later in the book).

zip' :: (Listr a, Listr b) -> Listr (a, b)
zip' (Empty, _) = Empty
zip' (_, Empty) = Empty
zip' (Cons (a, x), Cons (b, y)) = Cons ( (a, b) , zip' (x, y) )

-- > let x = zip' . unzip'
-- > x  $ Cons ((1, 'a'), Cons ((2, 'b'), Empty))

-- Cons ((1,'a'),Cons ((2,'b'),Empty))

-- > let y = zip' . unzip_'
-- > y  $ Cons ((1, 'a'), Cons ((2, 'b'), Empty))

-- Cons ((1,'a'),Cons ((2,'b'),Empty))

Finally we have an exhaustive (can handle lists of different lengths) definition of zip’ and the results of composing zip’ with unzip’ and unzip_’ using ghci.

Testing with maths

If you know how zip and unzip work its not imperative (though it is fun) to walk yourself through how each of them operates as defined here. What is important is the result we’ve gotten out of ghci. We’ve composed our two functions, and as stated above in our original equation we’ve gotten back the very same thing we put in. Just as though it were the id function.

I had originally wanted to build my own “foldrless” version of unzip_ in the hopes that it would be easier to see the “inversity” in the code itself. Unfortunately its not incredibly clear, and whats worse the implementation isn’t extremely efficient. BUT! Its not a total loss, because in order to satisfy myself that my hack was working properly, all I had to do was run the results BACK through zip and see if I got the original Cons list out the other side to satisfy our original assertion.

And that’s really the sweet spot here. While its not a formal proof of the functionality, it provides us with a lot of confidence that our functions are working properly. By defining the function as the inverse of another function we get a way to build it and test it. Incredible.

Lists

The third section of chapter one covered some basic functional programming concepts. Namely Cons lists, their mirror Snoc lists, and the functions built to operate on them. Particularly the adaptations of the foldn function from the previous section which operated over Nat.

data Listl a = Nil | Snoc (Listl a, a) deriving Show
data Listr a = Empty | Cons (a, Listr a) deriving Show 

foldl' c h Nil = c
foldl' c h (Snoc (x, a)) = h (foldl' c h x) a

foldr' c h Empty = c
foldr' c h (Cons (a, x)) = h a $ foldr' c h x

As you can see in the definition of both Cons and Snoc they are identical to the previous sections definition of natural numbers save for an addition bit of information, whatever you are storing in your list. Also, Cons and Snoc are only different in the position of their recursive self reference. It’s only the general understanding of the position by those using the type and the functions created for them ( : as an example ) that makes it behave the way it does. If you were, without prior knowledge, to examine the types by themselves it wouldn’t be clear that they were operated upon in significantly different ways when adding new elements (other than the difference in the names of the data constructor). As an example we could redefine the haskell infix cons operator to work with Snoc lists just as it would a Cons list (Note: I’ve been informed that in practice this isn’t possible, but the purpose of the example still holds).

data Listl a = Nil | Snoc (Listl a, a) deriving Show

(:) :: a -> Listl a -> Listl a
x : y = Snoc (y, x) 

example = 1 : Snoc(Snoc(Nil, 3), 2)
          --  Cons(2, Cons(1, Nil)) would be the norm

Also of interest in this chapter is the myriad of operations that can be defined in terms of foldr for Cons lists and foldl for Snoc lists, much as with Nat. From two of the excercises:

--Excercise 1.7
convert :: Listl a -> Listr a
convert = foldl' Empty h
    where h x y = Cons(y, x)

--Excercise 1.8
catconv :: Listl a -> Listr a -> Listr a
catconv m n = foldl' n h m
    where h x y = Cons(y, x)

Or a quick implementation of map’ for Cons lists built atop our extremely reusable foldr’

map' f = foldr' Empty h
    where h x y = Cons (f x, y)

-- > map' (+2) $ Cons (1, Cons(2, Empty))
-- Cons (3,Cons (4,Empty))

Further Work

I’m getting a lot of joy from rehashing these basic data structures and the implications of understanding them at a relatively low level are obvious. Lists make up such a huge portion of the programming that we do and understanding the types of lists that make the most sense for use within code for both comprehension and performance can provide real value. Also, in fooling around with some little coding challenges on the side (examples to be posted soon I hope) in haskell I’ve noticed my ease with maps and folds becoming greater.

One bit that I have to revisit is the proof from the middle of the section that the ++ operation is associative and that nil is the left and right unit. I was never very good with proofs, I’ve long since lost the terminology, and I would like to complete the exercise that requires that knowledge.

[update] you’ll notice I corrected the title to represent the section I went through. Not clear how I got the idea this was the whole first chapter.

My wife, bless her heart, heard me talking about Algebra of Programming after it was recommended to my by the fine people in #haskell and she went out and ordered a print on demand copy. You can do the same for yourself here (Note: the price at amazon.ca is much better than amazon.com).

Since my new job is working with Ruby, my free time can be devoted to other languages/projects and I’ve fallen under the spell of Haskell. As an example, Unraverl’s partial application parse transform for Erlang grew out of my time spent learning about Haskell, and how useful partial application can be. And as a natural sort of progression I’ve gotten interested in how mathematics can play a larger roll in my programming.

Starting Out

I was initially a bit worried that I would be out of my depth with this book but I was also determined to do whatever was necessary to fill in the gaps of understanding. Luckily the first bit hasn’t been too difficult, as most of my questions have been around terminology which were quickly answered thanks, once again, to #haskell. As an aside, if you’re on the fence about which functional language to learn spend a couple minutes in haskell’s irc channel. Huge thanks to heatsink, c_wraith, and others.

Recursive Data Types

The second section of the first chapter is where things started to get exciting and dense. The first example of recursive data types they provide, that make the basis for the rest of the chapter, is natural numbers (all integers >= 0). In haskell it would look something like

data Nat = Zero | Successor Nat

To further explain how this can represent any natural number consider the following possible definitions of a function that represents the value 3

-- What we would normally do
three = 3

-- Another "unrolled" recursive definition using the + function
three = (1 + (1 + (1 + 0)))

-- Using our data type
three = (Successor (Successor (Successor Zero)))

When I attempted an explanation of this to my wife her question was a frustrating “Why?”. Of course, “because its cool” didn’t persuade her. First, it’s a definition for a set of numbers which involves no actual numbers, only the structure of our new data type. We’ve structurally defined natural numbers. Second, because we have a recursive representation we can define recursive functions for this data type, and more generic functions for other types that are similarly recursive.

The rest of the chapter is devoted to presenting the foldn function that provides a very generic way to perform operations over recursive data types like Nat.

-- In terms of numbers as you would use them normally
foldn c h 0 = c
foldn c h (n + 1) = h (foldn c h n)

-- In terms of our Nat data type
foldn c h Zero = c
foldn c h ( Successor n ) =  h (foldn c h n)

It should be noted here, as it confused me initially, that by providing (n + 1) or (Successor n) in the head of the function, n represents a value of one less than that which is passed in. So in the case that foldn was called with some c, some h and 6, n has the value 5 (since (5 + 1) is 6).

The fun part about this is that is provides a method by which you can define functions for addition, subtraction and exponentiation (and others) in terms of foldn. From the book:

-- Addition
plus m n = foldn m Successor n

-- Subtraction
mult m n = foldn 0 (plus m) n

-- Exponentiation
expn m n = foldn 1 (mult m) n

-- The more point free ("point-less"?) version, would be without the n's. 

If you’re a ruby developer you’ll recall the Comparable mixin. Each of the methods in Comparable is defined in terms of the method < =>, and once you’ve done that you get skads of additional functionality for free. Similarly here we’ve defined one function, significantly more generic than < =>, that can be used as the basis for many other functions.

Exercises

I’ve actually completed all the exercises save for the 1.4 and 1.6. For the first, I simply couldn’t provide h which requires knowing how to add n times in such a way that it results in the square of a number. As for the second, I haven’t taken the time. You can actually download the answers here, which has been wonderful for checking my answers and allowing me to enjoy the satisfaction of my failures and triumphs.

Elementary

Obviously this is only the first chapter and relatively simple (though not for me), but being able to go through it and grasp the concepts explained was extremely gratifying. Even more, seeing how those concepts apply to every day development gave me confidence that I can really get something out of this to apply to my personal projects. I hope to post here on each of the chapters so that I’m forced to verify my understanding of the material. Any corrections are greatly welcomed in the comments!