shimweasel

I've been watching the videos of "Structure and Interpretation of Computer Programs" on the way to work, and silently cheering every time Abelson and Sussman remove a barrier to abstraction. I was shocked and horrified, therefore, when they suddenly stopped short of the goal, and embraced list cells as a primitive, when they'd already defined functions! Granted, they might be a bit faster implemented in registers, but we're talking conceptual purity, right? Anyway, with no further ado: lists in Ruby without using anything but lambda.

def cons(a,b)
  lambda { |x| x ? a : b }
end

def car(l)
  l.call(true)
end

def cdr(l)
  l.call(false)
end

def fold(combine, acc, list)
  return acc if list == nil
  fold(combine, 
       combine.call(acc,car(list)), 
       cdr(list) )
end

def toRubyList(list)
  fold(lambda { |rl, element| rl.push(element) },
       [],
       list)
end

def fromRubyList(rl)
  l = nil
  rl.reverse.each { |el| l = cons(el,l)}
  return l
end

and in flight:

>> require 'fakelist'
=> true
>> l=fromRubyList([1,2,3])
=> 
>> car(l)
=> 1
>> l2=cdr(l)
=> 
>> toRubyList(l2)
=> [2, 3]

Mark hacks code, plays judo and goes to the beach as much as his accursed Northern European skin will allow.

He spent some time in Doha learning how to climb scaffolding and teaching metallic eagles how to flap their wings, and is currently working on a predictive text engine, a bridge between Ruby and a language even more esoteric, and a particularly gory iPhone game.

Every now and then he conducts perverse experiments on his body, like sleeping for half an hour in every four, and still claims that he remained lucid and charming in the month and a half he spent awake.

export PGOPTIONS='-c client_min_messages=WARNING' with thanks to afreshcup

I've hacked quite a bit of Ruby and Perl in my various day jobs, and one of the things that I like about them a lot is the specialised syntax for string interpolation. It would be very hard to find a self-respecting Ruby hacker who would write

sprintf "I have %d pieces of %s at $%d apiece", number, fruit, unit_cost

or worse,

"I have "+number+" pieces of "+fruit+" at $"+unit_cost+" apiece"

when it's possible to write

"I have #{number} pieces of #{fruit} at $#{unit_cost} apiece"

This is the sort of syntactic polish that Ruby excels at, and it's an area where Haskell lags a little: it's not a terribly sexy feature, semantically speaking, and for structured data it's inappropriate anyway - you should be defining a Show instance instead, or possibly Binary if it's large. For the cases it's good for, though, it's very good, and I miss it in Haskell.

Now, this feature is trivial to implement in a dynamically typed language. If it weren't already there, we could easily write code to parse out the #{ } references, and call "eval" to get their values in the current scope - after that, it's just a case of pasting it together. Statically typed languages, however, generally don't have eval, and while Template Haskell does allow you to do some static computation, it stops short of full 'eval' functionality.

I poked at the problem for a while and was about ready to give in when Matt Morrow (mmorrow on #freenode) posted a beautiful solution. Before I go into the solution, here's the interface:

fruit = "apple"
unit_cost = 2
number = 10
result=[$here|I have $(number) pieces of $(fruit) at $(unit_cost) dollars apiece, making $(unit_cost * number) dollars|]

Our syntax here is a little different because we're using Template Haskell, but we've kept all of the important parts: our references are still inline, and we can use expressions, not just variables.

Now, for the implementation: Matt's actually written a parser that can take an arbitrary string to the Template Haskell expression equivalent. The quasiquoter defined as 'here' takes the text inside the $( ) brackets, tries to build a Haskell expression out of it, and inserts it as a string into the result, concatenating them all together. The nicest bit is that this is completely typesafe, so we have no nasty surprises at runtime.

the code is here, but it's probably easier to grab it with

sudo cabal install haskell-src-meta

to use it, you'll need

{-# LANGUAGE TemplateHaskell, QuasiQuotes #-}
import Language.Haskell.Meta.QQ.HsHere

at the top of your file, and to include the package 'haskell-src-meta' in your cabal file (or on the ghci command line).

1. Flymake mode for Emacs and Haskell is very cool, but needs a bit of poking to get right for literate haskell files
2. Some of my Haskell from six months ago is … not very good. Every time I see a fromJust, I cringe a little inside

to my very great delight, Stephen Blackheath has taken my scrappy little patches and put in the hours to get dylibs working properly on Mac, all the way through. They're not in the main line yet, but they should be soon - if you'd like to play, they're listed on the bug tracker here and here. These make installing and running cabal packages on Mac pretty smooth, so I'll be splitting off the Haskell in Hubris into its own Cabal package and making a release as soon as I've ironed out a couple of bugs.

btw, all this hacking was brought to you from an extremely elegant hotel room in NY. Wish I'd brought a real camera rather than having to angle my laptop awkwardly and run PhotoBooth.

For those of you who've been following along, in our last episode, we'd _almost_ managed to build GHC HEAD on Mac. Since that time, the rts_builtin bug has been fixed, and GHC will now install cleanly. There are still a few nasty shims to add in before Hubris will do what you want, however. (I'm going to assume you're up to date with the awful hacks from the last post: let me know if they need expansion)

UPDATE: this looks to not be entirely necessary - I can leave the rpath parameter out and the code still links now. I'm leaving this in as a reminder if I hit the problem again. First, the -rpath argument to ld on Mac needs some special Leopard loving: anything less than 10.5 is insufficient. ticket is here

second, ghc HEAD installs its libraries in /usr/local/lib/ghc-$VERSION/, then expects to see them in /usr/local/lib. There might be a cleaner way of fixing it, but for the moment,

ln -sf /usr/local/lib/ghc-6.11.20090915/*.dylib /usr/local/lib

will do the trick. (Yes, I _do_ love that green on black text, thanks for asking.)

And, just to show I'm not completely full of it, in classic "Works On My Machine(tm)" style:

11:53 ~/projects/HubrisBuild % uname -srv
Darwin 9.8.0 Darwin Kernel Version 9.8.0: Wed Jul 15 16:55:01 PDT 2009; root:xnu-1228.15.4~1/RELEASE_I386
11:53 ~/projects/HubrisBuild % irb 
irb(main):001:0> require 'lib/hubris'
mkdir: /Users/mwotton/.hubris_cache: File exists
creating Makefile
=> true
irb(main):002:0> class Foo
irb(main):003:1> include Hubris
irb(main):004:1> end
=> Foo
irb(main):005:0> f=Foo.new
=> #
irb(main):006:0> f.inline("foo (T_FIXNUM n) = T_FIXNUM (sum [1..n])", { :no_strict => true })
=> true
irb(main):007:0> f.foo(10)
=> 55
irb(main):008:0> 

Patches to the github repo will be up as soon as i've cleaned them up.

Mac OS X needed a bit of love to get GHC HEAD to build on it, but it does seem possible. The secret sauce: first, apply this patch It's not very polished and almost certainly breaks the Linux build, but it'll work ok for Mac. Then, create a file "build.mk" in the root ghc directory, with the content

SplitObjs=NO
GhcLibWays=v dyn

finally, GMP seems to resent being ignored: it needs a special flag passed to GCC, namely -read_only_relocs suppress. I assume there's a good way to tell GHC to use the flag: I cheated, and used make -v to get the gcc line that was failing, copy-pasted it and added the flags. Inelegant, but it seemed to work. Anyway, this is as far as i've got so far - the make step works, but then 'make install' complains about the package 'rts' not having an 'inplace' suffix. Bizarre, but I'll keep digging.

So, Hubris has got to be a bit more of a serious tool since the last time I posted about it. In preparation for a talk at RORO Sydney, I've been hacking madly, and now have full support for all of the basic types but hashes and works with GHC HEAD (JHC crashes for arrays at the moment, as I'm monstrously abusing unsafePerformIO).

To steal from one of my RSpec tests, it can be used from Ruby like this:

  it "returns a haskell list as  an array" do
    t=Target.new
    t.inline("elts (T_FIXNUM i) = T_ARRAY $ map T_FIXNUM $ take i [1..]
elts _ = T_NIL" )
    t.elts(5).should eql([1,2,3,4,5])
    t.elts("A Banana").should eql(nil)
  end

The interface could be cleaned up a bit: currently, everything has to be marshalled into a Ruby value(whether that's an array, hash or primitive type.) It'd be nice not to have to use the T_FIXNUM wrapper to indicate the type of the Haskell function - using ghc-src-exts, I could discover the type of the underlying function and wrap it automatically. Next release, perhaps. Anyway, this all only works on Linux for the moment, as GHC's support for dynamic libraries on Mac has bitrotted a bit. While Duncan Coutt's got the Linux side running sweetly, Daniel Peebles is currently having a look at the dynlib support on Mac, and I'm going to try to help out in whatever limited way I can - with any luck it'll all be ready for 6.12, which is coming out Real Soon Now and is full of tasty treats like ThreadScope.

Under the hood, it's actually pretty simple. Once you have dynamic library support, it's reasonably easy to take a chunk of Haskell, collect the top-level identifiers, wrap them for access from C-land, and compile a library. Likewise, accessing dynamic libraries from Ruby is very old news indeed. There's a lot of plumbing involved, working out exactly what flags various tools need to build the libraries correctly, but you never see that it in operation: it's software that just disappears into the background.

Anyway, check it out, see what you think. Collaborators are always welcome, and there's still a heap of things to do.