[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!

I’ve gone back and knocked off a couple of big todos in rquery. Namely, removing the Symbol capability, and using instances of the new OperationCollector in place of the global class variable + mutex required by the Symbol alterations. Also, as a consequence, I was able to remove the Declarations methods ( .is, .is_not ) previously required for use with overloaded operators like ==.

No More Symbols

Previously there were two DSLs coexisting in the library. One opened up the Symbol class and added the declaration methods.

User.where { :age.is == 12 }

This, in my opinion, was an interesting hack and fun to implement but required both global storage for the results of the executing statements and the pollution of the Symbol class. The library’s better half used a block parameter that represented a collection of the attributes provided by ActiveRecord.

User.where { |user| user.age.is == 12 }

In removing support for the Symbol based syntax, the block based version became much cleaner both externally and internally. Externally there’s no longer a need for the .is and .is_not declarations while the from, between, in and contains methods remain the same.

User.where do |user|
  user.age == 12
  user.name.contains "George"
  user.weight.between 160..180
end

Though, because of Ruby’s restriction on overloading the != operator it now looks like:

User.where do |user|
  user.age.not = 12
end

Simple Internals

The internals have been simplified as well. At a glance, there is now a single class that handles the organization of the calls to the adapter for serialization, OperationCollector. In addition every time the where method is called, a new instance of this class is created so there’s no need to have the mutex to prevent race conditions. Please take a look at the newness for more details.

What is it?

Last weekend I hacked partial application into my parse transform for erlang, unraverl. The rules are very simple but the implications are interesting if nothing else.

In other functional languages, haskell as an example, there’s nothing inherently wrong with defining a function that requires two arguments but giving it one.

add x y = x + y
example = add 1
{- => \y -> 1 + y -}

The result is a lambda where the supplied argument is applied across the code in the function.

Unraverl’s implementation?

Using the initial example in Erlang

add(x, y) -> x + y.

example() -> add(1).

the parse transform sees that there are no local (only) functions named ‘add’ with an arity of 1. It then finds the next highest arity definition and changes the call to accommodate

%% roughly
example() -> fun(y) -> add(1, y) end.

So while haskell applies whatever arguments are available to the actual function (internally I’m not sure how its implemented), unraverl simply wraps a call to the actual function in a new fun requiring the remaining arguments.

To make use of this feature in your own applications simply add the compiler directive

-compile([{parse_transform, unraverl}]). 

and make sure the library is in the code path.

As yet, it doesn’t have a makefile or unit tests so use at your own peril.

Been mulling over my next project after I finish a small Rails app for my friend. I’m not sure I’ll have the time in the near future but here are the ideas that are competing in my head for… well literally… mind share.

Both use Erlang. Unraverl is the beginnings of a meta programming/parse transform library for Erlang. At this point it only implements before/after filters with method chains. Grove is a JSON Query to set comprehension library for use with Mnesia.

• Unraverl
  1. add partial application
  2. runtime function definition from funs
  3. add pure/impure designation attribute/checking
• Grove
  1. Make use of MochiWeb
  2. Rework the JSON query structure
  3. Move JSON Query to Set Comprehension logic out into separate module/project

Clearly Unraverl is the most flashy, and likely the most interesting bit of hacking, but whether it becomes useful later or not remains to be seen. I still think that Being able to use Mnesia from Rails or from rich clients would be really very awesome.

On top of those things I need to take the time to learn org-mode, and build at least one gen_server or gen_fsm based app.

Either way code will result!

I’ve been getting rid of my TODO’s in my mini bootstrapping library whilst focusing on my Sinatra app and the config file looks a lot less crappy now. It even looks a tiny bit awesome. Its doesn’t do everything (still need to put my app/* directories in here) but it serves my purposes and remains flexible:

BootStraps::Initializer.configure do |config|

  #Use the vendor directory
  config.vendored = true
  config.default_env = 'production'

  #require each gem
  config.gem 'activerecord'
  config.gem 'sinatra'
  config.gem 'json'
  config.gem 'haml'
  config.gem 'twitter'
  config.gem 'nakajima-rack-flash'

  #action taken when config.db.connect is called
  config.db.connect_action do
    ActiveRecord::Base.establish_connection(
        :adapter => 'sqlite3',
        :dbfile =>  File.join(config.root, 'db', "#{config.env}.sqlite3" ))

  end

  #Sinatra settings
  config.framework.set :environment, config.env
  config.framework.set :views, File.join('app','views')
  config.framework.set :server, 'mongrel'
  config.framework.use Rack::Session::Cookie, :domain => 'localhost'
  config.framework.use Rack::Flash, :sweep => true
end

No more string literal library names (holy cow that was bad), a nice flexible block for defining the db connection code, and little method missing spice to run whatever methods on whatever framework I’m using.

Using the config has been simplified as well:

require 'config/bootstraps'

module MyMod
  class MyApp < Sinatra::Base

    configure do
      Straps.db.connect
      Straps.framework.apply_settings!(self)
    end

  end
end

Thinking about rolling it into a gem just to save myself time down the road.

In an effort to simplify my Sinatra app startup and configuration process I’ve built out a very simple bootstrapping library. It’s robust enough to cover the needs for a small to mid size app, but simple enough that it’s not overkill for use with Sinatra.

boostraps.rb

In my config directory I have two files: bootstraps.rb and environment.rb.

The former contains three classes DataStore, Configuration, and Initializer. When you invoke the class method boot! on Initializer it pulls in the environment.rb, loads up the configured gems and then loads up all the files in whatever library directories have been specified.

Use within your Sinatra::Base subclass takes the form:

require 'config/bootstraps'

module MyModule
  class App < Sinatra::Base

    configure do
      Config = BootStraps::Initializer.config
      Config.db.connect
      bar = Config.global[:foo]
    end
  end
end

Environment.rb

The above is nice and quiet as it should be. Behind the scenes we’ve told ol’ BootStraps a bunch of stuff about what our app looks like:

BootStraps::Initializer.configure do |config|

  #Configure the db library and settings
  config.db.lib = 'ActiveRecord::Base'
  config.db.init_method = :establish_connection
  config.db.init_args = {
    :adapter => 'sqlite3',
    :dbfile =>  "#{config.root}db/#{config.env}.sqlite3"}

  #default our environment to production
  config.default_env = 'production'

  #require a ActiveRecord on boot
  config.gems['activerecord'] = '>=2.2'

  #arbitrary setting
  config.global[:foo] = 'bar'

end

Other stuff

The best part that you don’t see here is the ability to add libraries to app/[models,ext]/ or lib/ and have them required for you. Again, the point is to limit the knowledge/effort needed to contribute new code to the app.

kinks

It’s quirky in some places (you have to specify something for a gem version even if its nil) but its a relatively clean app boostrapping solution. You can check out my current use case in more detail here so long as you ignore the rest of the app :D.

Things I’d like to see in OS 11:

• True micro-kernel architecture
• 64 bit all the way down
• MacRuby support for desktop apps (Apple should adopt this project immediately)
• Automatic window arrangement like XMonad/Ion

That is all.