The Church Code

You may have heard of the lambda calculus, in which everything is a function. And you may have asked yourself, as I have, ok that's great, but I how do I do anything with just functions? How do I create all those datastructures I've become acustommed to? Do I need to build the datastructures I've become accustomed to? If so, how do I do it?

One answer to this question, is the Church encoding, named after Alonzo Church who first came up with the idea. So how do you use Church encoding?

Well, before I get into that I'm going to describe the environment I'm going to use. I'm going to use the ruby programming language, because it's familar to me, and Haskell's type system makes it difficult to use Church encoding. Secondly I'm gonna define a convience method in ruby called curry:

def curry(&l)
  lambda { |a| lambda { |b| l[a,b] } }
end

curry takes a block of two arguments and transforms it into a Proc w/ a single argument that returns another Proc of a single argument. This is just to save me typing later.

Now that that's out of the way we can start talking about how to turn our functions into values. Consider one of the simplest values in most programming languages, true and false.

# we are going to use the names ctrue and cfalse because
# ruby takes exception to our using true and false
# as variables
ctrue = curry { |a,b| a }
cfalse = curry { |a,b| b }

Now if you didn't stop reading a while ago because you already know all about this stuff, you may be wondering, how are those functions true and false? Actually, let's just make sure that curry method makes sense first.

curry { |a,b| a } -->
lambda { |a| lambda { |b| a } }
# So to call ctrue we'd do the following:
ctrue[1][0] #=> 1

The reason for currying all these functions should become clear fairly soon. Now that that's out of the way, how does this give us true and false? Well, think about an if statement. Now imagine if was defined as a function, like the following:

cif = lambda { |condition| curry { |true_branch, false_branch|
  condition[true_branch][false_branch] } }

Now we can for instance write not:

cnot = lambda { |cond| cif[cond][cfalse][ctrue] }

Now if you've picked up on what's going on with cif you've realized that it's not really necessary. ctrue and cfalse are true and false, and they are also if.

So we can write cnot as

cnot = lambda { |cond| cond[cfalse][ctrue] }

And if we cheat for a moment, we can discover which value a given church encoded boolean is by using the following function

cbool_to_rbool = lambda { |cond| cond[true][false] }

Now we can make sure our cnot method works

>> cbool_to_rbool[ctrue]
=> true
>> not_ctrue = cnot[ctrue]
=> #<Proc:0x02b9876c@(irb):1>
>> cbool_to_rbool[not_ctrue]
=> false

So now what? We've managed to come up with bools out of functions. Doesn't seem very useful yet, although maybe kind of entertaining.

Well we can now also define and and or. A and B is true if A is true and B is true. Put another way, A and B is true if neither A nor B are false.

cand = curry { |a,b| a[b][a] }

So let's walk through this function
if a is true, it will take a the left value and give us b. If b is true, we have true and true -> true, which is what we wanted. if b is false, we have true and false -> false which is again, what we wanted. If a is false, we get a so we had false and anything -> false, which is what we want as well.

Next we can define or.

cor = curry { |a,b| a[a][b] }

If is a true, we get a, if a is false we get b. Therefore we will only get a false result if both a and b are false. Now that we have and, or and not, we can build boolean operation (xor, etc.), and we've done it using only functions. No datastructures in sight.

The next thing we are going to try, is to create some datastructures out of pure functions. The first thing we will create is a pair, that is a list of two values.

cpair = curry { |a,b| lambda { |f| f[a][b] } }
cfst = lambda { |apair| apair[ctrue] }
csnd = lambda { |apair| apair[cfalse] }

cpair is a 3 argument function, it takes the first value for the pair, the second value for the pair, and a function that takes two arguments to use the pair.cfst will let us extract the first value from a pair, and csnd will allow us to extract the second value from a pair. Let's try it out:

>> pair_of_values = cpair["Ok"][5]
=> #<Proc:0x02b7ec40@(irb):12>
>> csnd[pair_of_values]
=> 5
>> cfst[pair_of_values]
=> "Ok"

Now you can see the purpose of using curried functions. It makes it easier for us to partially apply our functions so we can perform multiple operations with an argument of true, selecting the first value. You can also see that we can if we want create tuples of any arity. Since we already have true and false, one way to encode numbers could be to have an N-tuple of bits (true and false) and define the arithmetic operators in terms of logical operations on bits, like the way the ALU of a processor works. An interesting idea, but this is not how Church actually defined numbers with functions.

Instead, he represented natural numbers as the nth composition of a function with itself:

zero = curry { |f, x| x }
one = curry { |f,x| f[x] }
two = curry { |f,x| f[f[x]] }

Writing this definitions can be a bit tedius, so we can define a successor function:

succ = lambda { |n| curry { |f,x| f[n[f][x]] } }
three = succ[two]
four = succ[three]
.
.
.

We also define a function to convert our church numerals to ruby integers so we can see what's going on:

cnum_to_rnum = lambda { |n| n[lambda { |x| x + 1 }][0] }

>> cnum_to_rnum[two]
=> 2

What's happening is that n is composing the function lambda { |x| x + 1 } n times, so in the case of two, it is twice. We then feed it an initial value of zero, so 0 + 1 + 1 = 2.

We can also add our church numerals

plus = curry { |m,n| curry { |f,x| m[f][n[f][x]] } }

>> cnum_to_rnum[plus[two][four]]
=> 6

We can also define multiplication, a predecessor function etc. But I'm getting bored of church numerals so lets move on into how you create algebraic data types. This is going to allow us to create linked lists, trees, pretty much any data structure you can have in a pure functional language.

In Haskell, there is a type Maybe a, (ML has the same type, only they spell it 'a option). The definition in Haskell looks like:

data Maybe a = Just a | Nothing

That is, any value of Maybe Int for instance will either be Nothing or Just some integer value.

We can define this same data structure using just functions. Each constructor, Just and Nothing will be a function. Each value of Maybe a will be a function that takes a function (a -> b) and a value ( b ).

just = lambda { |value| curry { |f,x| f[value] } }
nothing = curry { |f,x| x } # if you recall this is also the definition of cfalse

Haskell also has a type Either a b whose definition looks like:

data Either a b = Left a | Right b

You may have noticed that Maybe a is just a special case of Either a b where we don't care about the second value. Again, we can define this type using only functions. We will have two functions left and right. Both will take a value, and return a function that takes two arguments, two functions, one from a to c and the other from b to c.

left = lambda { |value| curry { |f,g| f[value] } }
right = lambda { |value| curry { |f,g| g[value] } }

Given that an N-tuple can be represented in pairs, and that nested Eithers give us all the sum-types we need we can represent almost any datatype you can define in Haskell (barring things like strictness annotations, FFI, etc.) using pure functions.

For instance, we can define a linked list. In Haskell the definition might look like:

data List a = Cons a (List a) | Empty

Like maybe or either we will have two constructor functions cons, and empty
cons will take two inputs, a head and a tail and return a function taking two functions. The first one will take as parameters the head and the tail, the second will be a value to use if the list is empty. Empty will simple be a function that takes two functions, with the same parameters as the function returned by cons.

cons = curry { |h,t| curry { |cf, ev| cf[h][t] } }
empty = curry { |cf, ev| ev }

Now we can write first and rest to get the first item of the list
and the rest of the list:

first = lambda { |alist| alist[ctrue][nil] }
rest = lambda { |alist| alist[cfalse][nil] }

>> list = cons[1][cons[2][empty]]
=> #
>> h = first[list]
=> 1
>> t = rest[list]
=> #
>> first[t]
=> 2

We can also write the function map for instance:

map = curry { |f,l| l[curry { |h,t| cons[f[h]][map[f][t]] }][empty] }

>> l2 = cons[1][cons[2][cons[3][empty]]]
=> #<Proc:0x00002b1909def588@(irb):10>
>> l3 = map[lambda { |x| x.to_s }][l2]
=> #<Proc:0x00002b1909def588@(irb):10>
>> first[l3]
=> "1"
>> first[rest[l3]]
=> "2"
>> first[rest[rest[l3]]]
=> "3"

Given that we've defined church numerals earlier we can of course use them instead of
ruby numbers. Strings can be represented as lists of characters, and characters as integers, which again can be represented using church numerals. Basically, all you need are functions. I hope you've learned something, or were at least mildly entertained.

Let's eval some strings

List comprehensions are neat, but ruby doesn't have em. That's ok, we've got string eval!

module Enumerable
  def concat_map(&f)
    inject([]) { |a, b| a.concat(f.call(b)) }
  end
end


def guard( b )
  if b
    [nil]
  else
    []
  end
end

def r( v )
  [v]
end

def comp( s, b = binding )
  before_bar, after_bar = s.split("|")
  before_bar.gsub!(/\A\s*\[/, '')
  after_bar.gsub!(/\]\s*\z/, '')
  components = after_bar.split(/;/)
  gen_exprs, guard_exprs = components.partition { |e| e =~ /<-/ }
  final = "r(#{before_bar})"
  final = guard_exprs.reverse.inject(final) { |s, e| "guard(#{e}).concat_map { #{s} }" }
  final = gen_exprs.reverse.inject(final) { |s, e|
    var, expr = e.split("<-").map { |c| c.strip }
    "(#{expr}).concat_map { |#{var}| #{s} }"
  }
  eval(final,b)
  #final
end

See, easy?

Now we can do things like:

def factors( n )
   comp "[ [x,y] | x <- (1..n) ; y <- (1..n) ; x * y == n ]", binding
end

If we do factors 25 we get [[1, 25], [5, 5], [25, 1]].

We can also write "quicksort" (being that not so great list comprehension quicksort that I'm sure you've seen before:"

def qsort( a )
  if a.length < 2
    a
  else
    pivot = a.first
    tail = a[1..-1]
    b = binding
    qsort(comp("[ x | x <- tail ; x < pivot ]", b)) + [pivot] + qsort(comp("[ y | y <- tail ; y >= pivot ]", b))
  end
end

And of course we write a cartesian product function:

def cart_prod(a, b)
  comp "[ [x,y] | x <- a ; y <- b ]", binding
end

By the way the code that this expands to is:

(a).concat_map { |x| (b).concat_map { |y| r( [x,y] ) } }

Of course we could've written all these functions before, w/o list comprehensions but this was more fun.

Abuse: Is it ruby? Is it Haskell? It's both!

=begin

> puts = return ()
> main = do let (.) = flip ($)

=end
eval <<HERE.gsub(/^>/, '')

>           print([1,2,3].length)
>           puts

HERE

Save to somefile.lhs

Run with ruby something.lhs
runhaskell something.lhs

How Arrays Work In Ruby

WKC CCC wrote:

> unknown wrote:
> > WKC CCC wrote:
> >
> >>
> >> count = count + 1
> >> end
> >>
> >> puts one.inspect
> >
> > Array.new(array) copies the *array* but it does not copy its *elements*.
> > So tempArr[0] is another name for the very same object as one[0], and so
> > forth. m.
>
> If they are referring to the same object, why is it when
>
> tempArr = Array.new(one)
> one.clear
>
> results in tempArr still having the values originally assigned to array
> one?

Reread what I said. I didn't say that tempArr and one refer to the same
object; I said that tempArr[0] and one[0] (and so on) refer to the same
object.

Think of it this way. Items in an array are dogs. Arrays are people
holding leashes. Anyone can attach a leash to a dog. So I (tempArr) can
have a leash on Fido, and so can you (one). If you let go of your leash
(one.clear), Fido is still Fido; you just don't have a leash on him. But
if you cut off one Fido's legs (modify one[0]), that leg on my Fido
(tempArr[0]) is also cut off, because they are the same Fido.

m.

--
matt neuburg, phd = matt@tidbits.com, http://www.tidbits.com/matt/
Tiger - http://www.takecontrolbooks.com/tiger-customizing.html
AppleScript - http://www.amazon.com/gp/product/0596102119
Read TidBITS! It's free and smart. http://www.tidbits.com

Monads in Ruby Part 2: Maybe (then again Maybe not)

So here's when things start to get interesting. Today I'm going to discuss the maybe monad. In Haskell, the maybe type is used for computations that might fail. An example of this in ruby would be the #index method on arrays. In ruby index returns either the index of the passed in item in the array, or nil if the item is not in the array. Haskell is statically typed so variables can only hold one type of data. This means we can't return a 3 or a nil. Instead we have the maybe type which looks like data Maybe a = Just a | Nothing . So index would return a Maybe Integer. e.g:

index  "hello" ["world", "planet", "hello", "hi"] --> Just 2
index  25 [3,4,5] --> Nothing

What does this have to do with monads you may be wondering? Well, just like identity, the maybe type is a monad. In fact maybe is a monad with some extra features, an instance of MonadPlus. We'll come back to that. But first a detour in ruby land. You may have seen something like this:

class NilClass
   def method_missing(*args, &block)
      nil
   end
end

This is sometimes called the null pattern, and it makes Ruby's nil act like Objective-C's. That is, nil will just swallow messages it doesn't understand. The general opinion among the ruby community is that this is a Bad Idea (tm). I would tend to agree with that idea. It's also not as useful as it might initially appear, consider 1 + nil.

This pattern however is superficially similar to how Maybe works in Haskell as a monad. I mentioned earlier that maybe was an instance of MonadPlus. This means it supports two additional operations, mzero and mplus. mzero, acts as you might guess from it's name as a zero. mzero mplus anything will always be the anything. Likewise if you think of the bind operation (discussed last time) as a sort of multiplication, mzero bind f will always be mzero. For the maybe monad, Nothing is mzero.

So if I define

class Array
   def maybe_index( obj )
      i = index( obj )
      if i
         Maybe.Just( i )
      else
         Maybe.Nothing
      end
   end
end

I can now change the first 3 in an array for instance into a 4, with no need for error checking:

a = [1,3,5]
b = Maybe.m_bind( a.maybe_index( 3 ) ) { |i| a1 = a.dup; a1[ i ] += 1; Maybe.m_return( a1 ) }

So b will either be Just [1,4,5] or Nothing. Either way, we had no opportunity to index an array by nil, and no need to litter our code with if statements. (What we did litter our code with was quite a bit more verbose, but you win some you lose some.)

Now, you must be wondering, what about this mplus business? Well let's same you need to address someone. If you know their nickname, you'd like to use that, if you don't know their nickname, you'd like to use their first name, and if you don't know their first name, you'd like to use their last name (which you know you'll always have). So how do we do this? We get all three and mplus the results together:

class Hash
   def maybe_fetch( key )
      if has_key? key
         Maybe.Just(self[key])
      else
         Maybe.Nothing
      end
   end
end

person1 = { :nick => 'Big Joe', :first => 'Joseph', :last => 'Smith' }
person2 = { :last => 'Baggins' }

greeting1 = Maybe.mplus( Maybe.m_bind( person1.maybe_fetch( :nick ) ) { |nick| Maybe.m_return("Hey, #{nick}") },
                                         Maybe.mplus( Maybe.m_bind( person1.maybe_fetch( :first ) ) { |first| Maybe.m_return("Hi, #{first}") },
                                                               Maybe.m_bind( person1.maybe_fetch( :last ) ) { |last| Maybe.m_return("Hello, Mr. #{last}") }))

puts greeting1.from_just

greeting2 = Maybe.mplus( Maybe.m_bind( person2.maybe_fetch( :nick ) ) { |nick| Maybe.m_return("Hey, #{nick}") },
                                         Maybe.mplus( Maybe.m_bind( person2.maybe_fetch( :first ) ) { |first| Maybe.m_return("Hi, #{first}") },
                                                               Maybe.m_bind( person2.maybe_fetch( :last ) ) { |last| Maybe.m_return("Hello, Mr. #{last}") }))

puts greeting2.from_just

This is similar to something likep1[:nick] || p1[:first] || p1[:last] in your standard ruby idiom, but note how I also transformed each value differently. And this code won't misevaluate due to things like nil being false or "" being true. The effect is localized entirely to the semantics you give it. This also means that you won't easily run into the major problem of the null pattern in that it runs away with you. It's very easy to contain this to a small section of code.

Before I post the code, I'm going to make one small note. I've decided not to bother with writing "type-safe" versions of this monads anymore. a) They aren't really type-safe anyway and b) classes aren't types, especially not in Ruby. It's a losing battle, so I think that to use monads in ruby you'll unfortunately have to rely more on self-discipline and less on type-checking.

class Maybe
  def initialize(*args)
    if args.length > 1
      raise ArgumentError, "Expected 0 or 1 arguments, got #{args.length}"
    end

    @nothing = args.empty?
    @val = args.first
  end

  def nothing?
    @nothing
  end

  def from_just
    raise "Maybe pattern match failure" if nothing?
    @val
  end

  def self.Just( v )
    new(v)
  end

  def self.Nothing
    new
  end
end

# Monad stuff
class Maybe
  def self.m_bind(maybe_a)
    if maybe_a.nothing?
      Maybe.Nothing
    else
      yield(maybe_a.from_just)
    end
  end

  def self.m_return(v)
    Maybe.Just v
  end

  def self.mplus(a, b)
    if a.nothing?
      b
    else
      a
    end
  end
end

Monads In Ruby Part 1.5: Identity

So after chatting in #haskell on freenode it became apparent that my Identity monad was kind of a cheat. It wasn't a function from types to types. So I present here for comment, a modified version, that pretends that ruby has parametric types:

% cat identity.rb
$implementation_detail = {}
def Identity(klass)
  $implementation_detail[klass] ||= Class.new do
    define_method :initialize do |obj|
        @obj = obj
    end

    define_method :m_bind do |f|
      r = f.call( @obj )
      raise TypeError, "Bind did not type check" unless r.kind_of? Identity(klass)
      r
    end

    (class << self; self; end).class_eval {
    define_method :m_return do |obj|
      raise TypeError, "#{obj} not instance of #{klass}" unless obj.kind_of? klass
     self.new( obj ) 
    end

    define_method :name do
      "Identity(#{klass})"
    end

    alias_method( :to_s, :name )
    alias_method( :inspect, :name )
    }
  end
end

p Identity(Array).m_return( [1, 2, 3] ).m_bind( lambda do |a|
  Identity(Array).m_return( [3] + a[1..-1] )
end)




% ruby identity.rb
#<#:0x1eaff0 @obj=[3, 2, 3]>

Monads in Ruby Part 1: Identity

Just to get this out of the way, yes it's been done before: http://moonbase.rydia.net/mental/writings/programming/monads-in-ruby/00introduction.html

In order to better understand the various monads available in Haskell, I've been re-implementing them in Ruby. Thus far I've done Identity, List (well Array), Maybe and State. Today I'm going to show you the Identity monad. A monad is a framework of sorts for applying rules to a series of computations. A monad has at least two operations, bind and return. return takes a non monadic value and converts it to a monadic one, it has type:
(Monad m) => a -> m a
(I'm using Haskell type notation here because ruby doesn't have type notation ;) )

Bind takes a monadic value and de-monadifies it to feed it into a function that returns a monadic value. It has the type:
(Monad m) => m a -> (a -> m b) -> m b

Bind is where the magic happens. Haskell uses it's type system to ensure that every sequence of computations in a given monad goes through bind. Bind therefore lets the writer of the monad decide the rules for the little monadic world within a given program. (This is how Haskell deals with side-effects (IO) ).

So now without further ado, I present the Identity monad:

class Identity
  def initialize( val )
    @val = val
  end

  def self.m_return( a )
    Identity.new( a )
  end

  def self.m_bind(id_a, &f)
    f.call( id_a.val )
  end

  def val
    @val
  end
end

Short and sweet. All you can really do with an Identity monad is force evaluation order. Ruby is imperative so that doesn't really matter.

Here's some code using Identity:

Identity.m_bind( Identity.m_return( 1 ) ) do |x| # x is 1, we've sucked it out of the Monad.
  Identity.m_return( x + 1 )
end

This is quite verbose. In Haskell it would be return 1 >>= (\x -> return x + 1), where >>= is bind and (\x -> ... ) is analogous to lambda { |x| ... }. Haskell also has some syntactic sugar for monadic expressions like this. Using the the syntactic sugar it would look like:

let i = return 1 in
       do x <- i
            return x + 1

The real difference of course is the type checking. If I wrote return 1 >>= (\x -> x + 1) in Haskell it would not compile where ruby cares not a whit if we want to escape our monads. That combined with the fact that unlike Haskell we have no syntactic sugar for monads means it's going to be difficult to debug our ruby implementations. Hopefully I've whet your appetite, next time we'll tackle the Maybe monad, that allows us to handle computations that might fail.

Seen in #ruby-lang

[4:21pm] <tpope> blink, less +F
[4:21pm] <teferi> tpope: I just SUGGESTED that
[4:21pm] <blink> technomancy: ssh+screen+tail, and doing an escape to copy mode everytime i want tos croll back is a hassle.
[4:21pm] bingeldac joined the chat room.
[4:21pm] <tpope> well good for you
[4:22pm] <blink> teferi: oh, i thought you were referring to tail -F
[4:22pm] <technomancy> if you say so
[4:22pm] langenberg_ left the chat room. (Connection timed out)
[4:23pm] <LoganCapaldo> he
[4:23pm] <LoganCapaldo> it's funny how you can man less and search for tail and get relevant info
[4:23pm] <blink> teferi: heeeeee, it works in conjuction with the F command within less. thank you.
[4:23pm] <blink> LoganCapaldo: i didn't se anything, so i decided to ask some geeks :P
[4:24pm] <simplicoder> a manless search for tail?
[4:24pm] <blink> simplicoder: i do that all the time.

NextFest

So yesterday (9/30) I hit up nextfest with my compatriot Jimmy. Won a USB hub from the GeekSquad both. Saw a creepy creepy robot, that had Einstein's head attached to Asimo's body. (Well it wasn't really Asimo, It was Hubo, but it sure looked a lot like Asimo.) There was this planetary rover that's wheels were each independent robots (I use "independent" loosely because the whole time they were being controlled by guys with RC remotes). IBM can apparently move individual atoms now thru the magic of cut and paste.

After NextFest, we wanted to see The Prestige, so instead we saw The Illusionist. (The Prestige having not yet been released). It was ok. My friend remarked it was very The Usual Suspects there at the end.

Vi for Mac OS X eveverywhere!

So cruising freshmeat today, I came across the world's niftiest Input Manager, http://www.corsofamily.net/jcorso/vi/. It lets you use vi command mode commands anywhere that uses Mac OS X's text input doohicky, which is pretty much everywhere. TextEdit, Safari, etc. all now have Vi key-bindings. It's not perfect, every time I've tried to edit something in this window for instance, I haven't been able to see the cursor, but it does work admirably in TextEdit and Colloquy, which is good enough for me. Hopefully it will get better.

Picture of Me

For anyone whose ever wondered what I look like:

Two Friends at a Cafe

The following takes place at an outdoor table of the Jester's
Cafe in Kingstown, Mittelland. Sitting at this table is Mr. Arthur
Shortbush, a Kingstown business-man. He is taking his morning coffee
(where the morning is eleven A.M.), and reading the Kingstown
Informer, a paper chiefly for the entertainment of business-men.

We observe Mr. Shortbush for a while, he is like his namesake
short, barely four foot eleven inches. He does however have the
advantage of the most wonderful thick, and perfectly neat brown hair.
Many would say it was his most attractive feature. Mr. Shortbush is
not lazy to be up so late, but the Markets are closed today, and he
relaxes for the moment, sure that his investments are secure.

By-and-by we see Mr. Shortbush's good friend come up the
street and join Shortbush at the table.

"You still read that rag?" Mr. Shortbush's friend is of course
referring to the already mentioned Kingstown Informer. Mr. Shortbush
folds up the paper in response.

"I must keep up with my business affairs."

"Don't lie, I know you read that thing for fun." Lord
Southwell is of course completely correct. Lord Southwell being Mr.
Shortbush's friend. Lord Southwell is actually a relatively minor
personage, which no land worth speaking of. He is unfortunately tall,
undesirably lanky and not very handsome. His only saving grace as far
as the general populace was concerned was that that he had the
friendship and esteem of (the very rich) Mr. Shortbush.

"I would never lie to you Leon." We wonder whether Mr.
Shortbush is being genuine. "However, there was a rather interesting
article in today's 'rag'. It seems Southland man has received
permission and financing from the Westland monarchy to try a mad
expedition to the other side of the world."

"Ah yes. DeMerro is his name right? I wonder what he plans to
do when he gets to the other side of the world."

"Well considering the Southlander nature, I imagine he intends
to throw a ball." Lord Southwell laughs uproariously at Mr.
Shortbush's witticism. The other diners and people in the vicinity do
not think it nearly as clever.

Mr. Shortbush continues, "Yes, it says here he will have a
fleet of five ships. Is five really a fleet I wonder? My own merchant
fleet exceeds fifteen, although my ships don't appear to be nearly as
large as this madman's. Five ships will depart from southernmost port
in Westland, and travel west, all around the earth until they arrive
in the Distant East. It goes on and on about the minutiae of sailing,
not very interesting I should think.

"Fancy a card game?"

"I suppose I could do with a hand or two." replies Lord
Southwell.

Animal Crossing: WW

Well I just discovered this saturday is another Flea Market. I'm quite excited, the Flea Market is where you get to trip off the cool stuff from all the animals in your town, and sell some your crap. AC is very much like the non-combat addicting parts of an MMORPG, but without other people. This game is so great. I'll update on saturday with all the cool stuff I manage to yoink. (Is that how you spell "yoink!" ?)

Packrat parsers

Recently I've been reading up on the packrat parsing algorithm. I think I'm going to attempt to use it to create a parser-generator in Ruby. I've already written a very retarded recursive-descent-oh-dear-god-don't-make-me-backtrack-I-can't-do-it parser-generator in ruby. I'll stick the source code at the end of this post. I think it's time to up the ante, as it were. I figure it's a hell of a lot easier to do a packrat parser generator than an LALR(1) or similiar. Also, I think I will allow it to either use parser combinators or a yacc-esque .y file. Of course it will use PEGs instead of (E)BNF, and I'm going to try and make it self-hosting. We'll see.

% cat parser.rb
module Parser
  NoMatch = Object.new
  BadMatch = Object.new
  def Lit(*args)
    Parser::Lit(*args)
  end
  def self.Lit(val)
    LiteralMatcher.new(val)
  end
  def self.included(mod)
    s = self
    (class << mod; self; end).module_eval do
      define_method(:Lit) do |*args|
        s.Lit(*args)
      end
    end
  end


  mod = self
  (class << BadMatch; self; end).class_eval do
    define_method(:to_s) { "#{mod}::BadMatch" }
  end
  (class << NoMatch; self; end).class_eval do
    define_method(:to_s) { "#{mod}::NoMatch" }
  end


  module ParserHandlers
    attr_accessor :parse_succeeded_proc, :parse_failed_proc
    def on_parse(&block)
      self.parse_succeeded_proc = block
    end

    def on_error(&block)
      self.parse_failed_proc = block
    end
    def |(other_parser)
      Or.new(self, other_parser)
    end
    def >>(other_parser)
      Sequence.new(self, other_parser)
    end
    def _?
      ZeroOrOne.new(self)
    end
    private
    def post_parse(parse_results, current_token)
      case parse_reslts
      when NoMatch, BadMatch
        return parse_failed_proc.call(current_token) if parse_failed_proc
        parse_results
      else
        return parse_succeeded_proc.call(parse_results) if parse_succeeded_proc
        parse_results
      end
    end


  end
  class EndOfStream
    include ParserHandlers
    def initialize()
    end

    def parse(token_stream)
      if token_stream.end_of_stream? or token_stream.current == EOS
        post_parse(true, nil)
      else
        post_parse(NoMatch, token_stream.current)
      end
    end
  end
  class LiteralMatcher
    include ParserHandlers
    def initialize(const)
      @const = const
    end

    def parse(token_stream)
      token = token_stream.current
      if @const === token
        token_stream.advance
        post_parse(token, token)
      else
        post_parse(NoMatch, token)
      end
    end
  end


  class Or
    include ParserHandlers
    def initialize(first_choice, second_choice, *remaining_choices)
      @parser_choices = [first_choice, second_choice, *remaining_choices]
    end

    def parse(token_stream)
      result = NoMatch
      @parser_choices.each do |parser|
        choice_result = parser.parse(token_stream)
        if choice_result == BadMatch or choice_result != NoMatch
          result = choice_result
          break
        end
      end
      post_parse(result, token_stream.current)
    end
    def []=(index, value)
      @parser_choices[index] = value
    end
    def |(additional_choice)
      @parser_choices << additional_choice
      self
    end
  end

  class Sequence
    include ParserHandlers
    def initialize(parser_first, parser_second, *rest)
      @parsers = [parser_first, parser_second, *rest]
    end

    def parse(token_stream)
      first_parser, *remaining_parsers = @parsers
      results = []
      first_result = first_parser.parse(token_stream)
      if first_result != NoMatch
        results << first_result
      else
        return post_parse(NoMatch, token_stream.current)
      end

      remaining_parsers.each do |parser|
        result = parser.parse(token_stream)
        if result == NoMatch or result == BadMatch
          return post_parse(BadMatch, token_stream.current)
        end
        results << result
      end
      post_parse(results, token_stream.current)
    end
    def []=(index, value)
      @parsers[index] = value
    end
    def >>(other_parser)
      @parsers << other_parser
      self
    end
  end

  class ZeroOrOne
    include ParserHandlers
    def initialize(parser)
      @parser = parser
    end
    def parse(token_stream)
      result = @parser.parse(token_stream)
      if result == NoMatch
        post_parse(true, token_stream.current)
      else
        post_parse(result, token_stream.current)
      end
    end
  end

  class ZeroOrMany
    include ParserHandlers
    def initialize(parser)
      @parser = parser
    end

    def parse(token_stream)
      results = []
      loop do
        result = @parser.parse(token_stream)
        return post_parse(BadMatch, token_stream.current) if result == BadMatch
        break if result == NoMatch
        results << result
      end
      post_parse(results, nil)
    end
  end


  class ArrayTokenStream
    attr_accessor :array
    def initialize(source_array)
      @array = source_array.dup
    end

    def current
      return EOS if end_of_stream?
      array.first
    end

    def advance
      fail "Can't advance past end of stream" if end_of_stream?
      array.shift
    end

    def end_of_stream?
      array.empty?
    end
  end
  EOS = Object.new # End of stream constant
  def EOS.to_s
    "Parser::EOS"
  end
  EOSMatcher = EndOfStream.new # Matches the end of a stream
end

The above expects an argument to #parse that responds to #advance and #current and #end_of_stream? as demonstrated by the ArrayTokenStream class.

Morgan Pictures

Look at the Kitty Kat!

Write ransom notes with Flickr (plus macdevcenter commentary)

Here's a cool place I ran across whilst reading O'Reilly's MacDevCenter. It lets you type in some stuff and it uses Flickr to spell out the letters with various photos. Check it out.

Speaking of MacDevCenter it seems as though there is a dearth of actually macDEVcenter articles on it. I see information about an anti-virus frontend, flickr, an article titled "What is Preview? (and why you should use it)". Now, all these articles contain interesting info, but a lot of them don't actually have anything to do with development. And some of them hint at it, without really delivering.

For instance, the Flickr article describes how to setup and account with Flickr, mentions some Mac tools to use with it, and has a quote by one of the people who wrote a tool extolling the virtues of the Flickr API. However there was no information on this API, no tutorial no sample code, not even a pointer to more documentation. Just the offhand mention of the existence of said API. One would assume that a site like MacDevCenter would be well, targeted towards developers. I suppose I should stop complaining, O'Reilly has a lot of good stuff up there, and he articles aren't bad, and there are some actual developement articles, I just feel like the site name is a bit of a misnomer.

Binghamton 2

Well, Binghamton has been pretty typical for a trip to Binghamton. Couple of things. One, we stopped at a Chili's (you know...Baby back ribs), and I haven't been to a Chili's since I can't remember when. I ordered the Bleu Cheese Chipotle Bacon Burger, and what an awesome combo of tastes it was. Speaking of bleu cheese, if your a fan of bleu cheese and a fan of beef, as I am, try this: build your burgers around a chunk or two of bleu cheese. Now ideally, its supposed to turn into a melted bleu cheese filling, but most of the time it just seeps throughout the burger (which still tastes really good). Mmm-mmm. Also we visited a Dollar Tree. Dollar Tree is a chain of dollar stores, but they are really good dollar stores. You'll oftentimes find name-brand stuff in there. If you get the oppurtunity definitely check one out. I guess that's all for now, later.

Bing-HAM-ton

Today I travel up to Binghamton with my SO. She's getting ready for school, and I'm coming along for the ride. Should be interesting. Kind of Gilligan's island though...a three hour tour.

Dice Rolling Fun in Javascript

Well I finally managed to complete my javascript die rolling script. I created it so I could have "interactive" character and monster sheets, since I keep a lot of my DMing info in computers. Eventually I may use XML and XSL but until then this little script adds clickable die rolls to HTML documents. All you have to do is put

<span class="dieroll">1d8</span>

in your HTML and $EmerilSoundEffect you've got a clickable die roll, in this case one eight-sided die.

<html>
 <head>
  <script language="javascript" type="text/javascript">
   function addDiceProperties( ) {
    var dieElements = getDieElements( );
    var x = 0;
    for( x = 0; x < dieElements.length; x++) {
     dieElements[x].onclick = dieElements[x].onkeypress =
      dieRoller(dieElements[x].innerHTML);
    }
   }

   function getDieElements( ) {
    var spans = document.getElementsByTagName("span");
    var dieElems = [];
    var isaDieRoll = /\bdieroll\b/;
    for(j = 0; j < spans.length; j++) {
     if ( isaDieRoll.test(spans[j].className ) ) {
      dieElems[dieElems.length] = spans[j];
     }
    }
    return dieElems;
   }
   
   function dieRoller(txt) {
    var count;
    var sides;
    var count_sides = getDieArgs(txt);
    count = count_sides[0];
    sides = count_sides[1];
    return function( ) {
     return rollDie(count, sides);
    };
   }   

   function rollDie(count, sides) {
    var results = 0;
    var i = 0;
    for(i = 0; i < count; i++) {
     results += intRand(1, sides);
    }
    document.getElementById("resultsbox").value = results;
   }
   

   function intRand(mini, maxi) {
    var range = maxi - mini + 1;
    return Math.floor(Math.random() * range + mini);
   }

   function getDieArgs(txt) {
    var pat = /([0-9]+)d([0-9]+)/;
    var res = [];
    var match = pat.exec(txt);
    res[0] = parseInt(match[1]);
    res[1] = parseInt(match[2]);
    return res; 
   }

  </script>
  <style type="text/css">
   .dieroll {
    color: blue;
    text-decoration: underline;
   }

   #resultsdiv {
    position: fixed;
    right: 0;
    top: 0;
    border-style: dashed;
    border-width: 1px;
    background-color: white;
    padding: 1px 1px 1px 1px;
    margin: 1px 1px 1px 1px;
   }
   #resultsbox {
    width: 3em;
   }
  </style>
    
 </head>
 <body onload="addDiceProperties( )">
  <div id="resultsdiv">Die Results: <input type="text" id="resultsbox"></div>
  <div><!-- This is where the rest of your stuff goes -->
   <p>
    <ul>
     <li><span class="dieroll">1d4</span></li>
     <li><span class="dieroll">3d6</span></li>
     <li><span class="dieroll">1d8</span></li>
     <li><span class="dieroll">1d10</span></li>
     <li><span class="dieroll">1d12</span></li>
     <li><span class="dieroll">1d20</span></li>
     <li><span class="dieroll">1d100</span></li>
    </ul>
   </p>
  </div>
 </body>
</html>

EDIT: 5:45PM

Well it seems there are some bugs in the randomness code part. Doesn't look like we ever get natural 20s for instance. I get the feeling it has something to do with the chance of getting a 1 from Math.random( ). So I am going to fiddle with this code, and welcome any suggestions.

EDIT: 8:30 PM

Fixed it. Knew there was something fishy. Thanks to http://www.werelight.com/docs/JavaScript_Quick_Reference.htm

Webcomics Grab Bag

Today I'm going to give you all some links to some web-comics. And by you all, I mean no one. Never the less, here they are:

• Schlock mercenary

  This is my bread and butter as far as web-comics go, and everyone out there probably already knows about it, but hey, who knows.




• The Order of The Stick

  Another goodie, copious amounts of D&D humor. Speaking of D&D I have a thought for a little javascript which I may post later today or tomorrow.




• Gods of Arr-Kelaan

  Cool because everyone from earth has godly powers. Quite possibly one of the most interesting concepts I've ever come across.

Well, that's about all the ones I still check on a regular basis. Be seeing you, space cowboy.