The first day of the proper QCon conference started out with Sir Tony Hoare doing a keynote about the difference and overlap between the science and engineering of computing. Fairly interesting, but the questions and answers were much more interesting stuff. One of the more interesting points made by Hoare was that in his view, a full specification is a generalization of testing. After the keynote I started out my track called Emerging Languages in the Enterprise. I introduced this track, doing 15 minutes of talking about my views on programming languages. The slides for my piece can be found here: http://olabini.com/presentations/ELITE.pdf. My talk was made much more interesting by Tony Hoare being in the front row. That made the whole thing a bit more daunting, obviously… =)

I then spent the rest of the day in my track – which was very good. I am very happy with all the presentations, and felt the track was a great success. First of was Michael Foord, talking about IronPython, and how Resolver uses IronPython to create a great product. Some interesting lessons and information there.

After lunch Jonas Bonér talked about Real-world Scala. The presentation gave a good grounding in Scala without looking at all small details – instead Jonas talked about more high level concerns and styles.

After that, Rich Hickey did a great presentation about Clojure. Rich did a great presentation, talking about Clojure from the ground up. It was very well received.

Martin Fowler did a fantastic presentation on ThoughtWorks experience with Ruby. The room was packed for this.

The final presentation in my track was Attila Szegedi talking about JavaScript in the Enterprise. This was also a great presentation, and gave me some new insight into what you could achieve with Rhino.

All in all, the full track was excellent, and all the presentations achieved pretty much what I hoped from them. I learned a lot from all of them.

After the final session of my track, Martin Fowler and Zach Exley did the evening keynote, talking about how technology helped the Obama compaign. Very interesting stuff too. At the end of the day, a very good day at QCon.

1 Comment | By Ola Bini | In: blogging | tags: clojure, ironpython, javascript, presentations, qcon, qcon london, ruby, scala. | #

I spent some quality time today trying to hack together a continuation passing style system in Ruby, to clarify some of my thinking. I ended up with something that is more or less a very small interpreter for S expressions, that uses a trampolining CPS interpreter. The language is not in any way complete, such things as assignment isn’t there, there is only one global scope and so on, so the continuations in this system is really not useful for anything except for hacking with it to gain understanding.

As such, I thought people might find it a bit interesting. I wish I’d seen something like this 5 or 10 years ago… Note that this code is extremely hacky and incomplete and bad and whatnot. Be warned. =)

OK, first you need to “gem install sexp”. This provides dead easy parsing of S expressions. Since that wasn’t the main purpose of this code, doing it with a Gem was easier.

The first part of the code we need is the requires, and structures to represent continuations:

require 'rubygems'
require 'sexpressions'

class Cont
  def initialize(k)
    @k = k
  end
end

class BottomCont < Cont
  def initialize(k, &block)
    super(k)
    @f = block
  end

  def resume(v)
    @f.call(v)
  end
end

class IfCont < Cont
  def initialize(k, et, ef, r)
    super(k)
    @et, @ef, @r = et, ef, r
  end

  def resume(v)
    evaluate((v ? @et : @ef), @r, @k)
  end
end

class CallCont < Cont
  def initialize(k, r)
    super(k)
    @r = r
  end

  def resume(v)
    evaluate(v, @r, @k)
  end
end

class ContCont < Cont
  def initialize(k, v, r)
    super(k)
    @r, @v = r, v
  end

  def resume(v)
    evaluate(@v, @r, v)
  end
end

class NextCont < Cont
  def initialize(k, ne, r)
    super(k)
    @ne, @r = ne, r
  end

  def resume(v)
    evaluate(@ne, @r, @k)
  end
end

BottomCont is is what we use to do something at the end of the program. We could print something, or anything else. IfCont is used to implement a conditional. It’s quite easy – once we resume we check the truth value and evaluate the next part based of the result. CallCont will invoke some existing S expressions in a variable. It just takes the value and evaluates that. ContCont is a bit trickier. It will take a value, and then when asked to resume will assume that the parameter to resume is a continuation and invoke that continuation with the value it got earlier. Finally, NextCont is used to implement basic sequencing. It basically just throws away the earlier value and uses the next instead.

The actual code for evaluate and a helper function looks like this:

def evaluate_sexp(sexp)
  cont = BottomCont.new(nil) do |val|
    return val
  end

  env = {
    :haha => proc{|x| puts "calling proc"; 43 },
    :print => proc{|x| puts "printing" },
    :save_cont => proc{|x| puts "saving cont"; env[:saved] = x; true },
    :foo => 42,
    :bar => 33,
    :flux => "(call flux)".parse_sexp.first
  }

  c = evaluate(sexp, env, cont)

  while true
    c = c.call
  end
end

def evaluate(e, r, k)
  if e.is_a?(Array)
    case e.first
    when :if
      evaluate(e[1], r, IfCont.new(k,e[2],e[3],r))
    when :call
      evaluate(e[1], r, CallCont.new(k, r))
    when :continue
      p [:calling, :continue, e[1]]
      evaluate(e[1], r, ContCont.new(k, e[2], r))
    when :prog2
      evaluate(e[1], r, NextCont.new(k, e[2], r))
    end
  else
    case e
    when :true
      proc { k.resume(true) }
    when :nil
      proc { k.resume(nil) }
    when Symbol
      proc {
        if r[e].is_a?(Proc)
          k.resume(r[e].call(k))
        else
          k.resume(r[e])
        end
      }
    else
      proc { k.resume(e) }
    end
  end
end

Here evaluate_sexp is the entry point to the code. We first create a BottomCont that will just return the value. We then create an environment that includes simple values, a function (flux) that calls itself, and some procs that do different things. Finally evaluate is called, and then we repeatedly evaluate the thunk it returns. Since we know that the bottom continuation will return, we can actually invoke this part indefinitely. That is the actual trampolining part, right there.

The evaluate function will check if it’s an array we got, and in that case it will check the first entry and switch based on that, creating IfCont, CallCont, ContCont or NextCont based on the entry. If it’s a primitive value we do something different. As you can see we first check if the value is one of a few special ones, and then if it’s a symbol we look it up in the environment. If the value from the environment is a proc we invoke it with the current continuation, which means the proc can do funky stuff with it. The common thing for all the branches is that they wrap everything they do in a thunk, and inside that thunk call resume on the continuation with the value provided.

Finally we can try it out a bit:

p evaluate_sexp("123".parse_sexp.first) # 123
p evaluate_sexp("bar".parse_sexp.first) # 33
p evaluate_sexp("nil".parse_sexp.first) # nil

p evaluate_sexp("(if quux 13 (if true (if nil 444 555)))".parse_sexp.first) # 555
p evaluate_sexp("(if quux 13 (if true (if nil 444 haha)))".parse_sexp.first)

Here you can see that simple things work as expected.

What about calling the flux function, that will invoke itself?

p evaluate_sexp("(call flux)".parse_sexp.first)

This will actually loop endlessly. In effect, when we add trampolining to a CPS, we in effect get a stack less interpreter, in such a way that we get tail call recursion for free.

Finally, what about the actual continuation stuff? Another way of creating an eternal loop is to do something like this:

p evaluate_sexp("(prog2 save_cont (prog2 print (continue saved 33333)))".parse_sexp.first)

This piece of interesting code will actually loop forever. How? Well, first the prog2 will run the proc in save_cont. This will save the current continuation, and then return true from the proc. Then the next prog2 will be entered, running the print proc. Finally, the final part will be evaluating the continue form, which will take the continuation in saved, invoke that with the value 33333. This will in effect jump back to the first prog2, return 33333 from the call to save_cont and go into the next prog2 again. Looping…

If you use an if statement instead, and return nil from the inner call to the continuation, and add some printing to the IfCont#resume, you can see that that point will only be invoked twice:

p evaluate_sexp("(if save_cont (prog2 print (continue saved nil)) 321)".parse_sexp.first)

This will generate:

[:running, :if, :statement]
printing
[:calling, :continue, :saved]
[:running, :if, :statement]
321

Here it’s obvious that the if statement runs twice, and that the second time the evaluation turns into false, which makes the final continuation return 321

I hope this little excursion into CPS land was interesting for someone. It’s a quite useful technique to know about, once you wrap your head around it.

2 Comments | By Ola Bini | In: blogging | tags: continuations, cps, programming language design, ruby. | #

OK, I’ve hinted and talked about in several contexts that I have some projects going on that haven’t been announced.  So today I’m going to just mention two of them (so that they will be released at some point). (And no, ioke won’t be on this list).

Xample

This one I have real hopes for. It’s already functioning to a degree. So what does it do? Well, I call it example-driven DSLs. Instead of writing a parser/regexps for handling external DSLs, Xample will take some examples and then derive code to do something based on those examples. It’s one of those things that will not do everything, but it might solve 80% of all the simple DSLs. Those cases where the overhead of creating the DSL framework would not be worth it. Xample will help in those cases in making it really easy to create quite sophisticated DSLs. It’s in Ruby, and I have plans that include a generic work bench for handling these DSLs. Since you have examples of how they should look, you can use the information in all kinds of cool ways.

I have just made the Xample repository public on github.

Antlr-ELisp

This is probably one of the worst cases of yak shaving I’ve ever started on. But it’s a good and worthwhile project. And now that I’ve mentioned it to Terence I guess there’s no way of getting away from it… =)

So, simple, Antlr-ELisp is a backend for Antlr, that allows you to create parsers for Emacs Lisp. This should make it quite easy to get Emacs modes written for a language, without having to resort to all the awful hacks Emacs generally does to handle different languages. This one is really in the infant stage right now, but it looks like it shouldn’t be too hard. Of course I’m not sure what performance will be like, but I’m trying to use as much macros as possible so the low level operations can still be efficient without looking ugly.

This project is also on github right now.

So, now I’m stuck – talking about these things on my blog means I will actually have to get both of them to a release, really soon now!

No Comments | By Ola Bini | In: blogging | tags: antlr, domain specific languages, dsl, elisp, emacs lisp, ruby, xample. | #

Eliza is probably one of the most famous AI programs ever made; it was first described in 1966. It’s interesting to note that after we have looked at the implementation it’s obvious that there isn’t much intelligence in this program at all, even though it does feel a bit spooky sometimes when having conversations with it.

The understanding Eliza displays is a result of quite simple pattern matching rules and have nothing to do with understanding. It’s also pattern matching that will take up most of this blog post. The algorithm implemented here is quite basic and something more advanced will be prepared for later chapters.

The Ruby code will have some differences compared to the original Lisp code, and I’ll note these as we go along. The most important one is that I’ll represent patterns and input strings as arrays of strings that are separated using split. Norvig uses (READ) so the Lisp code works on Lisp lists and atoms. This Ruby code will be a bit more complex in some cases due to this.

The file lib/ch05/pat.rb contains a first stab at simple pattern matching:

require 'enumerator'

class Pattern
  def initialize(pattern)
    @pattern = pattern
  end

  # Does pattern match input? Any variable can match anything
  def match(input, pattern = @pattern)
    pattern.enum_for(:zip, input).all? do |p, i|
      (p.is_a?(Array) && i.is_a?(Array) && match(i, p)) ||
        variable?(p) ||
        p == i
    end
  end

  def variable?(pattern)
    pattern.is_a?(String) && pattern[0] == ??
  end
end

Also note the cute trick combining zip and all?. The Enumerable#zip method will allow you to combine two or more arrays, and getting an enumerator for it makes it possible to first combine the array and then call all? on it. This should be quite efficient too. This will match simple patterns against input, using variables that begins with a question mark. This version really only returns true or false. To use it, do something like this:

p Pattern.new(%w(I need a ?X)).match(%w(I need a vacation))

At this stage, really simple matching works, but anything complicated will fail. We also need a way of getting hold of the variables captured in the matching, so that we can replace them in answers from Eliza.

The second version (in lib/ch05/pat2.rb) uses the same algorithm, but captures variables:

require 'enumerator'

class Pattern
  def initialize(pattern)
    @pattern = pattern
  end

  # Does pattern match input? Any variable can match anything
  def match(input, variables = [], pattern = @pattern)
    pattern.enum_for(:zip, input).all? do |p, i|
      (p.is_a?(Array) && i.is_a?(Array) && match(i, variables, p)) ||
        (variable?(p) && (variables << [p, i])) ||
        p == i
    end && variables
  end

  def variable?(pattern)
    pattern.is_a?(String) && pattern[0] == ??
  end
end

As you can see, the main difference is that match takes an optional array for variables. If the match succeeds it returns all variables, otherwise false. So something like this:

p Pattern.new(%w(I need a ?Y)).match(%w(I need a vacation))

would return [[“?Y”, “vacation”]].

The next version will also include a primitive form of unificiation, which makes it possible to match the same variable twice (lib/ch05/pat3.rb):

require 'pat2'

class Pattern
  # Match pattern against input in the context of the bindings
  def match(input, variables = {}, pattern = @pattern)
    pattern.enum_for(:zip, input).all? do |p, i|
      match_recurse(p, i, variables) ||
        match_variable(p, i, variables) ||
        p == i
    end && variables
  end

  def match_recurse(p, i, bindings)
    p.is_a?(Array) && i.is_a?(Array) && match(i, bindings, p)
  end

  def match_variable(p, i, bindings)
    variable?(p) &&
      ((bindings[p].nil? && (bindings[p] = i)) ||
       bindings[p] == i)
  end
end

This version is different mainly in that it returns a Hash instead of an Array. Norvig uses Lisp lists for this, but it doesn’t really make sense to define lots of extra functions for working with it when we already have a nice Hash in Ruby. Using a Hash also makes it really easy to check for previous examples of the same variable. Try it with a pattern such as %w(?Y should be ?Y).

The algorithm is slightly tricky, specifically since it actually modifies the hash as it recurses. This could easily bite you, but it’s still a step in the right direction.

Now, for making Eliza work out well enough for us, we actually need to have segment matching. This will allow matching of none or several atoms in a sweep. Adding this functionality actually transforms the code quite a lot, so let’s take a look at a first stab for this (lib/ch05/pat4.rb):

require 'pat3'

class Pattern
  # Match pattern against input in the context of the bindings
  def match(input, variables = {}, pattern = @pattern)
    case
    when variables.nil?
      nil
    when variable?(pattern)
      match_variable(pattern, input, variables)
    when pattern == input
      variables
    when segment_pattern?(pattern)
      match_segment(pattern, input, variables)
    when pattern.is_a?(Array) && input.is_a?(Array)
      match(input[1..-1],
            match(input[0], variables, pattern[0]),
            pattern[1..-1])
    else
      nil
    end
  end

  def match_variable(p, i, bindings)
    (bindings[p].nil? && bindings.merge(p => i)) ||
      (bindings[p] == i && bindings)
  end

  def segment_pattern?(p)
    p.is_a?(Array) && p[0][0] == ?*
  end

  def match_segment(pattern, input, bindings, start = 0)
    var = "?#{pattern[0][1..-1]}"
    pat = pattern[1..-1]
    if pat.nil? || pat.empty?
      match_variable(var, input, bindings)
    else
      pos = input[start..-1].index(pat[0])
      return nil unless pos
      b2 = match(input[(start+pos)..-1], bindings, pat)
      if b2.nil?
        match_segment(pattern, input, bindings, start+1)
      else
        match_variable(var, input[0...(start+pos)], b2)
      end
    end
  end
end

Here we aren’t modifying the Hash anymore, instead using a recursive version with match_variable merging a new array. Note how functional in style match_variable is. No modifications at all are happening there.

There are now several different cases to keep in mind. The first decision I made was to mirror Norvigs original algorithm that walks through the head of each array, instead of zipping everything up. Since we’re working with stuff that will be able to match even though the length of arrays are different, zip is really not the way to go anymore.

Another difference is the addition of the segment_pattern? and match_segment. Norvig uses a representation that includes a nested list such as (?* ?Y) to denote a segment. Since I don’t want to parse text, I decided to make a much easier choice, such that *Y denotes a segment, that will save into the ?Y variable. In my opinion, it makes both the code and the specifications easier to read.

Since we’re doing a recursive algorithm, the variables parameter is used for the base case of failure – if anything returns false or nil for variables, we fail match immediately.

So what is match_segment doing, really? This is the most tricky bit. Basically it needs to check what the next part of the pattern is to match (you can’t have two segments after each other without anything in between). Once that’s been found, match_segment tries to run the rest of a full match on the rest of the text. If that fails it tries to eat one more atom and recurses, otherwise it associates the current stretch of atoms with the variable.

You can try it out like this:

p Pattern.new(%w(*p need *x)).
  match(%w(Mr Hulot and I need a vacation))
p Pattern.new(%w(*x is a *y)).
  match(%w(what he is is a fool))

The first example shows the simple case, while the second one needs to do some backtracking. But the current version is not totally correct. Specifically, a case such as this would fail:

p Pattern.new(%w(*x a b *x)).
  match(%w(1 2 a b a b 1 2 a b))

The problem is that the algorithm successfully matches the first part of the string but can’t do anything with the rest, since ?X has different values unless the segment matching proceeds further. The fix is to first call match_variable so we can try to match the segment again in the worst case. It looks like this (lib/ch05/pat5.rb):

require 'pat4'

class Pattern
  def match_segment(pattern, input, bindings, start = 0)
    var = "?#{pattern[0][1..-1]}"
    pat = pattern[1..-1]
    if pat.nil? || pat.empty?
      match_variable(var, input, bindings)
    else
      pos = input[start..-1].index(pat[0])
      return nil unless pos

      b2 = match(input[(start+pos)..-1],
                 match_variable(var, input[0...(start+pos)], bindings),
                 pat)

      if !b2
        match_segment(pattern, input, bindings, start+1)
      else
        b2
      end
    end
  end
end

With this code the previous example works fine.

That is all the code there is to the pattern matching for our version of Eliza. Now for the actual implementation. Remember that this version is slightly less complicated compared with the original version. The list of rules in this code is not a full set either. (lib/ch05/eliza1.rb):

require 'pat5'

module Enumerable
  def some?
    self.each do |v|
      result = yield v
      return result if result
    end
    nil
  end
end

class Array
  def random_elt
    self[rand(self.length)]
  end
end

class Rule
  attr_reader :pattern, :responses

  def initialize(pattern, *responses)
    @pattern, @responses = pattern, responses
  end

  ELIZA_RULES =
    [
     Rule.new(Pattern.new(%w(*x hello *y)),
              "How do you do. Please state your problem"),
     Rule.new(Pattern.new(%w(*x I want *y)),
              "What would it mean if you got ?y?",
              "Why do you want ?y?",
              "Suppose you got ?y soon"),
     Rule.new(Pattern.new(%w(*x if *y)),
              "Do you really think it's likely that ?y? ",
              "Do you wish that ?y?",
              "What do you think about ?y?",
              "Really-- if ?y?"),
     Rule.new(Pattern.new(%w(*x no *y)),
              "Why not?",
              "You are being a bit negative",
              "Are you saying \"NO\" just to be negative?"),
     Rule.new(Pattern.new(%w(*x I was *y)),
              "Were you really?",
              "Perhaps I already knew you were ?y?",
              "Why do you tell me you were ?y now?"),
     Rule.new(Pattern.new(%w(*x I feel *y)),
              "Do you often feel ?y?"),
     Rule.new(Pattern.new(%w(*x I felt *y)),
              "What other feelings do you have?")
    ]
end

module Eliza
  class << self
    def run(rules = Rule::ELIZA_RULES)
      while true
        print "eliza> "
        puts eliza_rule(gets.downcase.split, rules)
      end
    end

    def eliza_rule(input, rules)
      rules.some? do |rule|
        result = rule.pattern.match(input)
        if result
          switch_viewpoint(result).
            inject(rule.responses.random_elt) do |sum, repl|
            sum.gsub(repl[0], repl[1].join(" "))
          end
        end
      end
    end

    def switch_viewpoint(words)
      replacements = [%w(I you),
                      %w(you I),
                      %w(me you),
                      %w(am are)]
      hash = {}
      words.each do |key, val|
        hash[key] = replacements.inject(val) do |sum, repl|
          sum.map { |val| val == repl[0] ? repl[1] : val}
        end
      end
      hash
    end
  end
end

if __FILE__ == $0
  Eliza.run
end

This is quite a lot of code, so let’s take it in chunks. First off I need some methods we defined in earlier chapters, namely Enumerable#some? and Array#random_elt. I’ve re-added them here for ease. Then we have the definition of a Rule, which is a pattern and a list of possible responses. It’s a very simple class definition, that takes all the arguments as parameters. Finally, there is the definition of a choice of rules from the original Eliza program. As you can see there are several variations in most cases, so the program can vary in its output.

The Eliza module has three different methods. The run-method takes the rules to use and goes into an infinite loop where it first prints a prompt, then reads a line of input, downcases this and finally splits it, sends it into the eliza_rule method and prints the result.

The eliza_rule method tries to match against at least one rule. If it succeeds in matching it first calls switch_viewpoint on the result (remember that the result here is a Hash of extracted segments from the input). It then replaces all instances of variables in one of the rules replacement text with the variable information.

The switch_viewpoint method just makes sure that the extracted strings from variables is turned into the other viewpoint, replacing “I” with “you”, “me” with “you”, etc.

The last lines of code just runs the Eliza program if this is the main program file that’s running. Try it out!

Now, wasn’t that quite easy? The magic really disappear once you’ve looked at this tiny implementation. And it’s obvious that there are many things that don’t work as well as it should. Pattern matching solves many problems, but you need a quite comprehensive suite of rules to make it really believable.

Eliza was one of the first programs to try to look like it understood English. But really understanding English is a much harder problem that is still at the core of AI.

For some more fun, I’ve encoded the full set of Eliza rules in lib/ch05/eliza2.rb.

6 Comments | By Ola Bini | In: paipr | tags: AI, artificial intelligence, eliza, paipr, ruby. | #

This is a typical conversation from the Ruby version of Eliza with full rule set I’ve just pushed to github. I’ll describe it in another blog post soon:

eliza> Hello there
How do you do. Please state your problem
eliza> I want to see if you work
Really-- if I work?
eliza> Yeah. You're a computer program that I need to check.
What do you think machines have to do with your problem?
eliza> Well, you're a machine, right?
Go on
eliza> And since you're a machine and I need to check you, you are quite relevant to this discussion.
What makes you think I am quite relevant to this discussion.?
eliza> That you are a computer program
What do you think about machines?
eliza> They are evil. They want to kill me
Possibly they are evil. they want to kill you
eliza> Yeah.
Please continue
eliza> No
You are being a bit negative
eliza> Yes
I understand
eliza> I don't think you do
Do you feel strongly about discussing such things?
eliza> Yes, I really feel strongly about it
What does that suggest to you?
eliza> That you are a fake
What makes you think I am a fake?
eliza> Just intuition
Please continue
eliza> What's your name?
Do you feel strongly about discussing such things?
eliza> What is your name?
What do you think?

Quite funny indeed, although there are some obvious glitches.

No Comments | By Ola Bini | In: paipr | tags: AI, artificial intelligence, eliza, paipr, ruby. | #

Not sure how known this antipattern is. I’ve seen some libraries that are very good at not doing it, but I’m also seeing lots of Ruby code that does use it without reason.

What I’m talking about here is the common usage of using instance_eval on a block to make it possible to use other methods inside of that specific block. If you want to do stuff based on method_missing inside of a block, this is the way people generally use.

So what’s the problem with it? Well, the problem is that blocks are generally closures. And you expect them to actually be full closures. And it’s not obvious from the point where you write the block that that block might not be a full closure. That’s what happens when you use instance_eval: you reset the self of that block into something else – this means that the block is still a closure over all local variables outside the block, but NOT for method calls. I don’t even know if constant lookup is changed or not.

Using instance_eval changes the rules for the language in a way that is not obvious when reading a block. You need to think an extra step to figure out exactly why a method call that you can lexically see around the block can actually not be called from inside of the block.

There are ways around instance_eval usage in a library – you can always assign self to a local variable outside of the block, and then call methods on that local variable. How ugly does that sound?

In almost all cases, if a block needs to handle method calls on a specific object, it should send that object in to the block as an argument. Take a look at routes in Rails – they could have been defined with instance_eval, but they’re not. There is no reason to use instance_eval for this case. Rails send in a route instead. File.open doesn’t use instance_eval with the block. It could, but instead it sends in the file. This is because there is no need to use instance_eval, and sending in the object as an argument gives the definition more power.

This doesn’t mean instance_eval should never be used. That’s not true, it’s a hugely useful feature, but it should definitely be used with good taste. If you’re unsure when to use it, don’t!

5 Comments | By Ola Bini | In: Uncategorized | tags: good taste, instance_eval, instance_exec, ruby. | #

In the last post I described a simple version of the General Problem Solver. This post will take a look at a more complete version that fixes some of the problems I discussed earlier. The first problem to solve is that it can sometimes be a bit hard to debug the output from our solver. If it fails we only know that it failed, not how far it got, and so on. So lets begin by creating a custom debug framework for us (lib/ch04/dbg.rb):

$dbg_ids = []

def dbg(id, format, *args)
  if $dbg_ids.include?(id)
    $stderr.puts(format%args)
  end
end

def debug(*ids)
  $dbg_ids = ($dbg_ids + ids).uniq
end

def undebug(*ids)
  $dbg_ids -= ids
end

def dbg_indent(id, indent, format, *args)
  if $dbg_ids.include?(id)
    $stderr.print "  "*indent
    $stderr.puts(format%args)
  end
end

This code uses a global variable to decide which debug statements should be used. We can turn on and off specific ids using the debug and undebug methods, while we can use dbg and dbg_indent to actually write something out.

Notice that I’ve used the sprintf operator (%) to make formatting of strings built into the system itself.

At this point it’s time to look at GPS2, which provide solutions for the “running around the block”, “prerequisite clobbers sibling”, “leaping before you look” and “recursive subgoal” problems.

One of the more interesting changes is that this version will not print anything, but instead return a status list that describes the actions taken. This will allow some more flexibility in how the code is used, later on.

Before starting out there are some things we need to add to make the output reasonable. We do that by representing operations a little bit differently, by including in the add-list a composite action that will include the symbol executing, and the name of the action. We also need an equivalent of the some-function. Finally, we need to have something that can create new operations including the execution part in the add list.

This code can be seen in lib/ch04/gps2.rb:

require 'gps'
require 'gps_no_clobber'
require 'dbg'

module Enumerable
  def some?
    self.each do |v|
      result = yield v
      return result if result
    end
  end
end

class GPS::Op
  def convert!
    unless self.add_list.any? do |l|
        l.is_a?(Array) && l.first == :executing
      end
      self.add_list << [:executing, self.action]
    end
    self
  end
end

GPS::SCHOOL_OPS.each do |op|
  op.convert!
end

class GPS2 < GPS
  class << self
    def op(action, parts = {})
      GPS::Op.new(action,
             parts[:preconds],
             parts[:add_list],
             parts[:del_list]).convert!
    end
  end
end

In this case I’ve chosen to make a subclass of GPS2, and use the existing helpers in gps and gps_no_clobber, although at the end most methods will be overridden.

I define the method some? on Enumerable; it’s actually really similar to a Ruby version of find/detect. The only difference is that we need to save the result of the block and actually return that instead of the value we sent in to the block.

I open up the GPS::Op class and add convert!. Notice that I’ve named it with a bang, since it will possibly modify the current instance. I’ve also decided to not follow convention by returning nil from a bang method. Instead I return self because it makes some of my code a bit simpler later on. The convert! method will check if the add-list already contains an array where the first element is :executing, otherwise it will add one of these. This will be more interesting later.

The gps2 file also converts all the available school operations.

Finally we provide a new method called GPS2::op, that will create a new converted operation for us. Notice that I’m using the convention of opening up the self class with class << self. I almost always prefer this way.

The next step is to take a look at the new solve-method. This will become slightly different since now all methods will take a state argument to keep track of where in the evaluation we are. The only place that doesn’t take a state is the solve-method, since it uses the initial state given to the initialize method. All methods except solve will also take a parameter for the current goal stack, that will help us keep track of which goals we have achieved so far.

The method solve looks like this (lib/ch04/gps2.rb):

  def solve(*goals)
    achieve_all([[:start]] + @state, goals, []).grep(Array)
  end

The original Lisp code uses remove-if #’atom to filter out all noise from the state, but the Ruby is much simplified by just using grep and sending in an Array. You did know that grep can take as argument anything that implements ===, right?

To keep track of the fact that we have started, we add the list [:start] to the front of the current state.

There are three more methods that need to be updated to make this implementation run. The first two are achieve_all and achieve (lib/ch04/gps2.rb):

  def achieve_all(state, goals, goal_stack)
    current_state = goals.inject(state) do |current_state, g|
      return [] if current_state.empty?
      achieve(current_state, g, goal_stack)
    end
    if goals.subset_of?(current_state)
      current_state
    else
      []
    end
  end

  def achieve(state, goal, goal_stack)
    dbg_indent(:gps, goal_stack.length, "Goal: %p", goal)

    if state.include?(goal)
      state
    elsif goal_stack.include?(goal)
      []
    else
      @ops.find_all do |op|
        appropriate?(goal, op)
      end.some? do |op|
        apply(state, goal, op, goal_stack)
      end || []
    end
  end

These are a fair bit more complicated than the first implementation. This is because we need to handle some things that the first implementation really didn’t handle well at all.

The achieve_all method is definitely a bit more messy. That’s because we need to update the current state for each call to achieve. In Norvig’s book, the implementation actually used a state variable that was updated after each iteration, but I felt that explicit modification didn’t feel right here, especially not in the presence of inject, which is really a perfect tool for this kind of updating. The only complication is that we want to halt everything if any call to achieve returns an empty state (this means that it couldn’t continue). If a goal couldn’t be achieved, it’s obvious we can just jump out directly.

The use here of inject is a bit different since it doesn’t explicitly build up something, but instead creates a new variable each time that is a modified version of the original. This is a refactoring that I would like to see in more code bases, since it’s a very nice way of getting rid of explicit mutation.

After building up the current state by calling achieve on all goals, we also need to make sure that all goals are still part of the current state. We do this using the subset? method defined in the code for the first GPS version.

The achieve method is the first place we use our debugging system. The length of the goal stack gives us an obvious indentation parameter, since it will get longer and longer the deeper we recurse. I use %p instead of %s since I really want to get the inspected output here.

There are three ways achieve can go. The first is if the goal is already in the current state. That means we have already achieved that goal, and all is fine.

If the goal is in the goal stack, that means we are in the second iteration of a recursive goal search – not good. That means we have failed that goal, so we return an empty array.

Finally, if none of the above situations are true, we need to find all appropriate operations for the current goal – using the same appropriate? method as the first GPS. We then use some? on all appropriate operations. The difference between find/detect and some? is obvious here – if we’d used find, the result would be an instance of Op, while some? will return the current state returned from the apply-method called inside the block.

At the end of the evaluation, if some? doesn’t find anything, it’s necessary to return an empty array instead of nil, since I’m using the empty array to represent failure every. (I will discuss this in more detail in a comparison post between Common Lisp and Ruby).

The missing method in GPS2 is now apply. It looks like this (lib/ch04/gps2.rb):

  def apply(state, goal, op, goal_stack)
    dbg_indent(:gps, goal_stack.length, "Consider: %p", op.action)

    state2 = achieve_all(state, op.preconds, [goal] + goal_stack)

    unless state2.empty?
      dbg_indent(:gps, goal_stack.length, "Action: %p", op.action)
      (state2 - op.del_list) + op.add_list
    end
  end

As you can see, we use dbg_indent in two different places here to make it obvious what’s happening while actually applying an operation. This is also the place where we first recurse to make sure all the operations preconditions have been satisfied. If we get back a state that is not empty, we can return a new state that is modified by the delete-list and then the add-list.

Wow, that was a bit more complicated, but not too bad. Let’s take a look at how this version works with the problems we established for GPS earlier (lib/ch04/gps2_problem1.rb):

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_needs_battery,
                :have_money,
                :have_phone_book],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_school)

If you run it, you’ll see that the result matches more or less the steps we got from the first GPS. I use pp to display the result of the operation. The main difference is that the start condition is in there too.

Something very simple, like lib/ch04/gps2_problem2.rb also works fine:

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_works],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_school)

The problem the last version used to get wrong now works correctly (lib/ch04/gps2_problem3.rb):

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_needs_battery,
                :have_money,
                :have_phone_book],
              GPS::SCHOOL_OPS)
pp gps.solve(:have_money, :son_at_school)

and lib/ch04/gps2_problem4.rb:

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_needs_battery,
                :have_money,
                :have_phone_book],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_school, :have_money)

Leaping before you look also fails as it should (lib/ch04/gps2_problem5.rb):

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home,
                :car_needs_battery,
                :have_money],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_school)

Really simple problems that require no action also works fine (lib/ch04/gps2_problem6.rb):

require 'gps2'
require 'pp'

gps = GPS2.new([:son_at_home],
              GPS::SCHOOL_OPS)
pp gps.solve(:son_at_home)

Monkey and bananas

So that we can see that the G in GPS is there for a reason, let’s see if we can apply the new version of GPS to a new domain. This problem is a classic AI problem – monkey and bananas. The basic idea is that a monkey is standing at the doorway to a room, there are bananas hanging from a rope in the middle of the room – out of the monkeys reach – and there is a chair near the door that the monkey can push into the room and stand upon to reach the bananas. The first thing we need to do is define the operators for this domain (lib/ch04/gps2_monkey1.rb):

require 'gps2'
require 'pp'

$banana_ops = [
              GPS2::op(:climb_on_chair,
                       :preconds => [:chair_at_middle_room,
                                     :at_middle_room,
                                     :on_floor],
                       :add_list => [:at_bananas, :on_chair],
                       :del_list => [:at_middle_room, :on_floor]),
              GPS2::op(:push_chair_from_door_to_middle_room,
                       :preconds => [:chair_at_door,
                                     :at_door],
                       :add_list => [:chair_at_middle_room,
                                     :at_middle_room],
                       :del_list => [:chair_at_door, :at_door]),
              GPS2::op(:walk_from_door_to_middle_room,
                       :preconds => [:at_door, :on_floor],
                       :add_list => [:at_middle_room],
                       :del_list => [:at_door]),
              GPS2::op(:grasp_bananas,
                       :preconds => [:at_bananas, :empty_handed],
                       :add_list => [:has_bananas],
                       :del_list => [:empty_handed]),
              GPS2::op(:drop_ball,
                       :preconds => [:has_ball],
                       :add_list => [:empty_handed],
                       :del_list => [:has_ball]),
              GPS2::op(:eat_bananas,
                       :preconds => [:has_bananas],
                       :add_list => [:empty_handed, :not_hungry],
                       :del_list => [:has_bananas, :hungry])
             ]

Nothing really strange here, really. So let’s use it and see if GPS works for it (lib/ch04/gps2_monkey1.rb):

gps = GPS2.new([:at_door,
                :on_floor,
                :has_ball,
                :hungry,
                :chair_at_door],
               $banana_ops)
pp gps.solve(:not_hungry)

This will generate the expected output:

[[:start],
 [:executing, :push_chair_from_door_to_middle_room],
 [:executing, :climb_on_chair],
 [:executing, :drop_ball],
 [:executing, :grasp_bananas],
 [:executing, :eat_bananas]]

And since we didn’t make any changes to the GPS problem, the claims of being generic does have some validity.

Maze searching

Another classic AI problem is maze searching. We can easily define a maze as numbered squares where one numbered square can lead to zero or more other squares. To make definitions really easy, we define a few simple methods that make it simple to define the operations for us (lib/ch04/maze.rb):

require 'gps2'
require 'pp'

module Maze
  class << self
    def make_ops(pair)
      [make_op(pair[0], pair[1]),
       make_op(pair[1], pair[0])]
    end

    def make_op(here, there)
      GPS2::op([:move, :from, here, :to, there],
               :preconds => [[:at, here]],
               :add_list => [[:at, there]],
               :del_list => [[:at, here]])
    end
  end

  Ops = [[1,2], [2,3], [3,4], [4,9], [9,14], [9,8],
         [8,7], [7,12], [12,13], [12,11], [11,6],
         [11,16], [16,17], [17,22], [21,22], [22,23],
         [23,18], [23,24], [24,19], [19,20], [20, 15],
         [15,10], [10,5], [20,25]].inject([]) do |sum, obj|
    sum + make_ops(obj)
  end
end

Here we first have make_ops, that just make all passages from one square to another symmetric – meaning we won’t have to define the passage from 1 to 2 AND the one from 2 to 1. The make_op method make use of some interesting properties of our code that was there without any real thought given to it. Namely that goals can be represented as arrays instead of symbols. In fact it doesn’t matter how you represent the goals, as long as you always use the same representation for the same goal. You can mix and match strings, symbols, regexps and arrays if you would like too. In this case the only goals we have are of the form [:at, 1], but it gives us a bit more representation power to do it like this.

Finally, a large array of pairs of numbers is transformed into operations using inject and calls to make_ops. The end result is all the operations we need to define this particular maze.

So, a first problem for this maze would probably look at how to get out of it, so lets see it (lib/ch04/maze_problem1.rb):

require 'maze'

gps = GPS2.new([[:at, 1]],
               Maze::Ops)
pp gps.solve([:at, 25])

The initial state is simple, we are at the first square, and want to get to the last (which is number 25). The output from running this problem gives us this output:

[[:start],
 [:executing, [:move, :from, 1, :to, 2]],
 [:executing, [:move, :from, 2, :to, 3]],
 [:executing, [:move, :from, 3, :to, 4]],
 [:executing, [:move, :from, 4, :to, 9]],
 [:executing, [:move, :from, 9, :to, 8]],
 [:executing, [:move, :from, 8, :to, 7]],
 [:executing, [:move, :from, 7, :to, 12]],
 [:executing, [:move, :from, 12, :to, 11]],
 [:executing, [:move, :from, 11, :to, 16]],
 [:executing, [:move, :from, 16, :to, 17]],
 [:executing, [:move, :from, 17, :to, 22]],
 [:executing, [:move, :from, 22, :to, 23]],
 [:executing, [:move, :from, 23, :to, 24]],
 [:executing, [:move, :from, 24, :to, 19]],
 [:executing, [:move, :from, 19, :to, 20]],
 [:at, 25],
 [:executing, [:move, :from, 20, :to, 25]]]

Except for that spurious [:at, 25], everything looks like we would expect here. We have a start move and then moving from square to square until we get to the last square.

The problem with the extra element is that the way we defined solve leaves everything that is an Array in there. What we really want to do is to leave everything that denotes an action in there. As you can see in lib/ch04/gps3.rb:

require 'gps2'

class GPS2
  def action?(x)
    x == [:start] || (x.is_a?(Array) && x.first == :executing)
  end

  def solve(*goals)
    achieve_all([[:start]] + @state, goals, []).find_all do |state|
      action?(state)
    end
  end
end

We first define what an action is and then find everything that satisfies that criteria.

What’s interesting with the current representation of the GPS, and also the way our maze domain looks like is that we can use the output for several different things. Say for example that we want to get a list of the path to the exit. Then we can use the code in lib/ch04/find_path.rb:

require 'maze'
require 'gps3'

module Maze
  class << self
    def find_path(start, finish)
      results = GPS2.new([[:at, start]], Maze::Ops).
        solve([:at, finish])
      unless results.empty?
        [start] + ((results - [[:start]]).map do |action|
          destination(action)
        end)
      end
    end

    def destination(action)
      action[1][4]
    end
  end
end

pp Maze.find_path(1, 25)
pp Maze.find_path(1, 1)
pp(Maze.find_path(1, 25) == Maze.find_path(25,1).reverse)

Running this first gives us the paths from 1 to 25, then from 1 to 1, and finally shows that our expectations of reversing the path is correct:

[1, 2, 3, 4, 9, 8, 7, 12, 11, 16, 17, 22, 23, 24, 19, 20, 25]
[1]
true

The blocks world

A final domain that probably has gotten more attention than any other in AI circles is the blocks world. The basic point of it is that you have a child’s set of building blocks on a table. The problems usually involve moving them in different ways, putting them on top of each other in different order, and so on. The assumption for our current modeling of it will be that you can only have one block on top of another. The only action you can take in this world is to move a block that has nothing on top of itself on top of either the table or on top of a block that has nothing on top of it.

First of, creating the operators for this domain (lib/ch04/blocks.rb):

require 'gps3'

module Blocks
  class << self
    def make_ops(blocks)
      ops = []
      blocks.each do |a|
        blocks.each do |b|
          unless a == b
            blocks.each do |c|
              unless [a, b].include?(c)
                ops << move_op(a, b, c)
              end
            end
            ops << move_op(a, :table, b)
            ops << move_op(a, b, :table)
          end
        end
      end
      ops
    end

    # Make an operator to move A from B to C
    def move_op(a, b, c)
      GPS2.op([:move, a, :from, b, :to, c],
              :preconds => [[:space, :on, a], [:space, :on, c], [a, :on, b]],
              :add_list => move_ons(a, b, c),
              :del_list => move_ons(a, c, b))
    end

    def move_ons(a, b, c)
      b == :table ? [[a, :on, c]] :
        [[a, :on, c], [:space, :on, b]]
    end
  end
end

This implementation is trickier than the others. The style of operations we want is something along the lines of “Move block A from TABLE to B”. This code accomplishes all available variations, while checking that there are spaces on top of A and B, and that A is on top of TABLE. The guards in make_ops need to make sure that we don’t create operations from a block to itself.

Now that we can make operators, lets see a simple problem. We have two blocks a and b, that lie on a table, and we want to put a on top of b. That would look like this (lib/ch04/blocks_problem1.rb):

require 'blocks'
require 'pp'

gps = GPS2.new([[:a, :on, :table],
                [:b, :on, :table],
                [:space, :on, :a],
                [:space, :on, :b],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b]))

pp gps.solve([:a, :on, :b], [:b, :on, :table])

This gives us the expected output:

[[:start], [:executing, [:move, :a, :from, :table, :to, :b]]]

Lets consider the case where we have a on top of b, and want to move it so b is on top of a. This time with debug output (lib/ch04/blocks_problem2.rb):

require 'blocks'
require 'pp'

gps = GPS2.new([[:a, :on, :b],
                [:b, :on, :table],
                [:space, :on, :a],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b]))

pp gps.solve([:b, :on, :a])

This also gives us what we expect:

Goal: [:b, :on, :a]
Consider: [:move, :b, :from, :table, :to, :a]
  Goal: [:space, :on, :b]
  Consider: [:move, :a, :from, :b, :to, :table]
    Goal: [:space, :on, :a]
    Goal: [:space, :on, :table]
    Goal: [:a, :on, :b]
  Action: [:move, :a, :from, :b, :to, :table]
  Goal: [:space, :on, :a]
  Goal: [:b, :on, :table]
Action: [:move, :b, :from, :table, :to, :a]
[[:start],
 [:executing, [:move, :a, :from, :b, :to, :table]],
 [:executing, [:move, :b, :from, :table, :to, :a]]]

One of the more interesting features of my implementation compared to Norvigs is that he has some ordering problems that needs extra code in achieve_all to handle. I haven’t figured out why, but my code doesn’t have that problem, so I’ll not show the fixed code (since there was no need to fix it). An example that caused these problems for Norvig looks like this with the Ruby code (lib/ch04/blocks_problem3.rb):

require 'blocks'
require 'pp'

gps = GPS2.new([[:a, :on, :b],
                [:b, :on, :c],
                [:c, :on, :table],
                [:space, :on, :a],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b, :c]))

pp gps.solve([:c, :on, :b], [:b, :on, :a])

This problem represent a block world where a is on top of b, b is on top of c and c is on top of table, and you want to reverse the ordering of them.

Another problem Norvig has that doesn’t show up in this code is a few examples that do to many operations to achieve something. The file lib/ch04/blocks_problem4.rb is one of those:

require 'blocks'
require 'pp'

gps = GPS2.new([[:c, :on, :a],
                [:a, :on, :table],
                [:b, :on, :table],
                [:space, :on, :b],
                [:space, :on, :c],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b, :c]))

pp gps.solve([:c, :on, :table])

Where the optimal solution takes one action, the lisp code does two actions (moving c from a to b, and then from b to table). This is because of ordering problems. Topological sort might solve it, for example. There is another example that takes four operations instead of two (lib/ch04/blocks_problem5.rb):

require 'blocks'
require 'pp'

gps = GPS2.new([[:c, :on, :a],
                [:a, :on, :table],
                [:b, :on, :table],
                [:space, :on, :b],
                [:space, :on, :c],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b, :c]))

pp gps.solve([:c, :on, :table], [:a, :on, :b])

But as mentioned before, it doesn’t seem like the Ruby code exhibit this problem, so I decided to not implement Norvigs fixes for them.

Interestingly, there are problems that can’t be solved no matter which order you put the goals. Take the example where b and a is on the table, and c is on top of a. You want to have c on the table, b on top of c and a on top of b. The current GPS implementation can’t handle this no matter which order you try (lib/ch04/blocks_problem6.rb):

require 'blocks'
require 'pp'

gps = GPS2.new([[:c, :on, :a],
                [:a, :on, :table],
                [:b, :on, :table],
                [:space, :on, :c],
                [:space, :on, :b],
                [:space, :on, :table]],
               Blocks.make_ops([:a, :b, :c]))

pp gps.solve([:a, :on, :b], [:b, :on, :c])
pp gps.solve([:b, :on, :c], [:a, :on, :b])

This is called the Sussman anomaly, and solutions will be covered later in the book.

Conclusion

It’s obvious that this version of GPS is much more powerful than the original one. But there is also some things that still show up as problems. Even though we introduced several measures there are still cases where a correct solution can’t be found. For example, we can take a look at the getting a child to school problem again, adding a new operator for taking a taxi there. Say that we want to get the son to school without using any money and define it like this (lib/ch04/gps2_problem7.rb):

require 'gps3'
require 'pp'

gps = GPS2.new([:son_at_home,
                :have_money,
                :have_works],
              GPS::SCHOOL_OPS +
               [
                GPS2::op(:taxi_son_to_school,
                         :preconds => [:son_at_home,
                                       :have_money],
                         :add_list => [:son_at_school],
                         :del_list => [:son_at_home,
                                       :have_money])
               ])
debug :gps
pp gps.solve(:son_at_school, :have_money)

Here something funny happens. If you look at the debug output:

Goal: :son_at_school
Consider: :drive_son_to_school
  Goal: :son_at_home
  Goal: :car_works
  Consider: :shop_installs_battery
    Goal: :car_needs_battery
Consider: :taxi_son_to_school
  Goal: :son_at_home
  Goal: :have_money
Action: :taxi_son_to_school
Goal: :have_money
[]

There are two ways of solving this: first solve the have_money goal and then the get son to school. In that case the have_money goal is solved trivially, and then the money is spent on a taxi. If the other ordering is tried the child is taxied to school and then the have_money goal fails. There is a valid solution (driving the son to school) but it’s never tried.

Another problem with the approach is that the descriptive power is not general and powerful enough. The conditions we use for operators in GPS is not really abstract enough.

GPS also assumes that you know everything about the world (“perfect information”), and that everything is either true or false. Probability is nowadays one of the better approaches available for AI, and the GPS doesn’t take fuzzy knowledge into account.

Finally, interacting goals, where you have several active goals at the same time is something most people have, but GPS takes one goal at a time.

All of these problems made it problematic to continue to use the GPS approach. Another thing that had a large impact was the realization how NP-hard problems affected problem solvers like GPS. At the end of the day, GPS was an interesting early approach to solve the problem, and it’s definitely been part of AI heritage available today.

2 Comments | By Ola Bini | In: paipr | tags: AI, artificial intelligence, general problem solver, gps, paipr, ruby. | #

One of the earlier attempts to create a system capable of problem solving was given the grandiose name General Problem Solver. It was first developed in 1957 by Alan Newell and Herbert Simon. When GPS was first introduced it caused quite some excitement in the AI community. GPS never did live up to the expectations, but it’s still important from a historical perspective. The original GPS implementation was written in IPL and had some subtle differences to the program developed in PAIP. I’ll follow PAIP while developing the Ruby version. If you have an interest in the original version I suggest first finding a book explaining IPL (which is not a funny language at all).

GPS implements a version of something called means-ends analysis. The kind of thinking embodied by this analysis is quite common sense. In short, you have some goals, you then figure out what conditions need to be true for you to achieve that goal. If those conditions aren’t true, you need to figure out how to achieve those, and so on.

The way we’ll write the first version of GPS, there are several interesting properties. The most central ones are the starting state, the goals, and the available operations. At the moment I will represent the states and goals as symbols. An operation need to be a bit more complicated. First of all, it’s got a name so you can trace it. It has preconditions that details what needs to be true for this operation to be able to operate. And it has an add-list and a delete-list. The add-list tells which conditions are true after the operation has executed, and the delete-list details what is no longer true.

So lets take a look at the first version of the implementation. I have made some changes compared to Norvig’s Lisp-code. The most obvious one is that I’m not using global variables, instead opting to put everything into a class called GPS (this code can be found in lib/ch04/gps.rb):

class GPS
  Op = Struct.new(:action, :preconds, :add_list, :del_list)

  def initialize(state, ops)
    @state = state
    @ops = ops
  end

  # General Problem Solver main interface: achieve all goals using
  # defined operations
  def solve(*goals)
    goals.all? do |goal|
      achieve goal
    end
  end

  # A goal is achieved if it already holds, or if there is an
  # appropriate op for it that is applicable
  def achieve(goal)
    @state.include?(goal) ||
      (@ops.find_all do |op|
         appropriate?(goal, op)
       end.any? do |op|
         apply(op)
       end)
  end

  # An op is appropriate to a goal if it is in its add list
  def appropriate?(goal, op)
    op.add_list.include?(goal)
  end

  # Print a message and update state if op is applicable
  def apply(op)
    if op.preconds.all? { |cond| achieve(cond) }
      puts "Executing #{op.action}"
      @state -= op.del_list
      @state += op.add_list
      return true
    end
    false
  end
end

There are several components to this code so lets take them piece by piece. First of all, we create a class called GPS. Inside if it we immediately define a struct called Op. There is a symmetry between the Common Lisp defstruct operation and the Ruby Struct.new call that I like a lot. In this case it’s perfect since we don’t want Op to have any actual behavior right now. The Op consists of an action, the preconditions, the add-list and the delete-list.

The initialize method takes the current state and the available ops. The current state is an array of states, and the ops is an array of ops.

The actualy central piece of this code is the solve-method. This method corresponds to the GPS function in the original code. The main difference is that the GPS function takes the state, goals and ops as parameters, while we put these inside the object using the initialize method instead.

So what does it mean for us to solve goals? Basically we try to achieve all goals. If we can achieve all goals we have solved it, otherwise not. Norvig’s Lisp code handles this a bit differently, by returning the symbol ‘solved if it works. I decided to just return a boolean instead. This means that our usage of the solve method might be a bit more verbose.

The achieve-method tries to do two different things. First it checks if the current state already includes the goal. In that case we’re fine. Otherwise we first need to find all operations that are appropriate for this goal, and then check if any of those operations can be applied. Before taking a look at appropriate? and apply, it’s interesting to note that I’ve decided to use any? here, while Norvig uses the function called some. These two operations are actually a bit different, but right now that difference doesn’t matter. The difference is that while any? will always return true or false, some will actually return the non-nil value generated from the test method. Ruby doesn’t seem to have anything like that (Enumerable#detect/find returns the original value, not the value generated by the block). As you’ll see in the next post I’ll actually have to implement some at that point.

What is appropriate? then? First of all, it’s a method that might actually belong on the Op class instead of in the GPS class. At the moment it just checks that the operations add-list includes the goal – meaning that the operation can be used to achieve the goal.

Finally we have the apply method (this one is called apply-op in Norvig’s code). Apply is where the recursive elements of the algorithm come into play. Basically, for an operation to be applied, all of the preconditions of that operation need to be fulfilled. We use all? to try to achieve all of the preconditions and if it succeeds we print which action we executed, modify the state by removing the delete-list and adding the add-list, and finally return true.

And that’s really all there is to the general problem solver. Of course we should test it and see, right? The original domain used for GPS was about drvining to nursery school and we will use something similar to that for testing this implementation.

First of all we need to have some operations defined for this domain. You can find this code in lib/ch04/gps.rb too:

  SCHOOL_OPS = [
                Op.new(:drive_son_to_school,
                       [:son_at_home, :car_works],
                       [:son_at_school],
                       [:son_at_home]),
                Op.new(:shop_installs_battery,
                       [:car_needs_battery, :shop_knows_problem,
                        :shop_has_money],
                       [:car_works],
                       []),
                Op.new(:tell_shop_problem,
                       [:in_communication_with_shop],
                       [:shop_knows_problem],
                       []),
                Op.new(:telephone_shop,
                       [:know_phone_number],
                       [:in_communication_with_shop],
                       []),
                Op.new(:look_up_number,
                       [:have_phone_book],
                       [:know_phone_number],
                       []),
                Op.new(:give_shop_money,
                       [:have_money],
                       [:shop_has_money],
                       [:have_money])
               ]

As you can see, this domain gives a hint about what might play into the goals for this domain. So let’s begin by taking a look at a problem. The first one can be found in lib/ch04/problem1.rb:

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_money,
               :have_phone_book],
              GPS::SCHOOL_OPS)
if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

The current state says that the son is at home, the car needs battery and we have money and a phone book. The goal to solve is to get the son to school. If we run this code it generates this output:

Executing look_up_number
Executing telephone_shop
Executing tell_shop_problem
Executing give_shop_money
Executing shop_installs_battery
Executing drive_son_to_school
Solved

Well, that seemed to work out fine, right? What about the case where we have no phone book (lib/ch04/problem2.rb):

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_money],
              GPS::SCHOOL_OPS)

if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

This generates

Not solved

as we would expect. And if we take a simple example where the car already works (lib/ch04/problem3.rb):

require 'gps'

gps = GPS.new([:son_at_home,
               :car_works],
              GPS::SCHOOL_OPS)

if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

We get:

Executing drive_son_to_school
Solved

Nice. It seems to be quite good. So what are the problems with the current approach? First of all, it doesn’t solve some very easy problems. The representation is generally wrong for continous activities. Norvig calls this “The Running around the block problem”. It’s easy to define a goal to drive from home to school, but it’s a bit more tricky to represent running around the block. There are ways around it, of course, but the GPS operator doesn’t necessarily make it as natural as it could be.

Another, more serious problem is the clobbered sibling goal problem. In something like lib/ch04/problem4.rb, this version of GPS handle everything correctly:

require 'gps'

gps = GPS.new([:son_at_home,
               :have_money,
               :car_works],
              GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

But if we create a problem like this (lib/ch04/problem5.rb):

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_phone_book,
               :have_money],
              GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

This will incorrectly report the problem as solved – since GPS first solves the problem of having money, and then solves the problem of having the son at school. The way of handling this problem is to replace every instance that achieves every call with a call to a new method called achieve_all. That involves the solve and apply methods. You can see the code in lib/ch04/gps_no_clobber.rb:

require 'gps'

class Array
  def subset_of?(other)
    (self - other) == []
  end
end

class GPS
  def solve(*goals)
    achieve_all goals
  end

  def apply(op)
    if achieve_all(op.preconds)
      puts "Executing #{op.action}"
      @state -= op.del_list
      @state += op.add_list
      return true
    end
    false
  end

  def achieve_all(goals)
    goals.all? do |goal|
      achieve goal
    end && goals.subset_of?(@state)
  end
end

Here I’ve decided to just open up the GPS class to provide this functionality. Another choice would be to subclass, but since this doesn’t substantially change the functionality I’ve decided to just do it like this. There are several things going on here. First I’ve decided to add an operator to Array, which mirrors the Common Lisp function subsetp. Array.subset_of? returns true if the current array is a subset of the argument array, so [].subset_of?([1]) == true, while [1].subset_of?([]) == false. The solve method is updated to just call achieve_all, and apply also calls achieve_all. The definition of achieve_all first makes sure we can achieve all goals, and then make sure that all of the goals to achieve are still in the current state.

If you execute lib/ch04/problem6.rb:

require 'gps_no_clobber'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_phone_book,
               :have_money],
              GPS::SCHOOL_OPS)

if gps.solve(:have_money, :son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

You will see that it executes several actions but then returns a not solved, since it’s not possible to achieve both goals.

Another problem with this implementation is based on the interleaving of planning and execution. Norvig calls it “The leaping before you look problem”. You can see it exemplified in the last execution – namely we do lots of things, but then realize that we haven’t solved the problem. At the end of the execution we have already fixed the car by giving the shop the money. That might not be that good. Since we only have one state variable, and this has already been changed, there is no way to go back.

There is one final problem, with recursive subgoals. That is, this version of GPS is not too good at handling the case where a goal depends on a goal that depends on the original goal. The file lib/ch04/problem7.rb exemplifies this:

require 'gps'

gps = GPS.new([:son_at_home,
               :car_needs_battery,
               :have_money],
              GPS::SCHOOL_OPS +
              [
               GPS::Op.new(:ask_phone_number,
                           [:in_communication_with_shop],
                           [:know_phone_number],
                           [])
              ])

if gps.solve(:son_at_school)
  puts "Solved"
else
  puts "Not solved"
end

We have removed :have_phone_book state from the initial state, and added a new operation to ask for phone number. This operation requires you to be in communication with the shop, and since you need the phone number to be in communication with the shop this will result in a SystemStackError in Ruby.

A final nuisance with the current implementation is that the result is just true or false. The only information we get is the printed output.

All of these are things that the final version of GPS will handle more correctly – at least in some cases. This post ended up long enough as it is, so GPS2 will have to wait until the next time.

2 Comments | By Ola Bini | In: paipr | tags: AI, artificial intelligence, general problem solver, gps, paipr, ruby. | #

I am currently sitting with Ribs, trying to decide how the definitions for associations should look like. I’ve also decided that I don’t want to use the current scheme for properties either. I also have some interesting constraints. First, I do not want to evaluate the block using instance_eval, so introducing nice method_missing hooks in the block context is out (so I can’t do anything like “has n” as DataMapper). Also, all definitions need to be able to take additional parameters in a hash. So something like “rib.has * :Posts” won’t work either.

I have come up with something that I’m reasonably happy with. It’s quite terse but definitely readable. It doesn’t pollute any namespaces. And hopefully it will only be used when the model need to differ from the conventions. I’m thinking about taking conventions a step further with Ribs and automatically try to figure out associations based on naming and foreign keys – but I haven’t decided about that yet.

All of these examples are supposed to be executed inside the Ribs! block, with r being the Rib parameter. I’ve decided to allow the table name as a parameter to the Ribs! method call instead of being something you set inside.

First of all, setting which property/properties are a primary key, I’m thinking about one or more of these alternatives – where track_id is the property name:

r.track_id :primary_key
r.track_id :primary_key => true
r.track_id = :primary_key
r.track_id.primary_key!

I’m skittish about the track_id= alternative, but the others I think can coexist quite well.

The next thing is to handle the mapping from one property name into a different column name (if no column name is specified, the property name will be used, of course):

r.title :column => :track_title
r.title.column = :track_title

Nothing very extraordinary here. I would probably like to have both alternatives here.

The next one is more interesting. I haven’t yet decided how to handle specifying primitive types. This code is supposed to handle the case that in ActiveRecord are covered with has_one and belongs_to. I don’t really see why they have to be different, really, so I’m thinking about doing something like this:

r.blog :is_owner
r.blog :is => Blog

I’m skittish about :is_owner, but it also feels slightly icky to have to specify the type of all single associations. This is definitely an area I would like to have some good ideas about.

Finally we come to the one-to-many and many-to-many associations. What makes this different is that I can have both a Set and a List (and also Map) since Hibernate handles these for me:

r.comments :list_of => Comment
r.comments :set_of => Comment
r.comments :is_set
r.comments :is_list

Once again I’m not sure how to handle it in such a way that you don’t have to write the name of the other entity in all definitions.

Anyway, this is what I currently have. I would appreciate innovative ideas here – especially if they are innovative within the constraints I’ve set for myself.

3 Comments | By Ola Bini | In: Uncategorized | tags: associations, hibernate, jruby, ribs, ruby. | #

I feel like I’ve been picking a bit on DataMapper in my recent posts, so I first want to say that I like most of what I see in DataMapper, and is generally just nitpicking. I’m also what I’ve noticed there to give examples instead of making up something. And actually, one of the reasons is that it was some time since I read much Ruby code, and DataMapper happens to be one of the things I’m looking a lot at right now.

Which brings me to something Sam Smoot said in the discussion about adding operator methods to Symbol. (In the blog post Simplified finders in DataMapper). What he said was this:

That might satisfy some, but it ranks pretty low on the “beauty” gauge. And that really does matter for adoption…

Now, the reason I’m bringing it up here is not to pick on Sam or DataMapper (Really!). Rather, it’s because an attitude that I’ve noticed all over the Ruby world lately. In most cases it’s not explicitly said like this, but I like Sam’s quote because it verbalizes exactly what it’s about. You really want your library to look nice. Beauty is really important in a Ruby framework. It really is important, and lots of focus is put on it. And one of the reasons for this is to drive adoption.

Since it’s been verbalized like this, I’ve realized that this is one of the things that really disturbs me with the Ruby communities fascination with making everything, absolutely everything into a DSL.

Now, I really do like thinking about DSLs and working with them. Being a language implementor brings that out in me. But a DSL really has it’s place. Why shouldn’t you make everything into a DSL? Why shouldn’t everything look nice? First of all, the initial development might just not be worth it. A DSL-like approach generally involves more effort, so maybe a regular API works fine? A DSL introduces cost, both in development and in maintenance. Everything you do needs to be balanced. My coworker Marcus Ahnve gave a very good example of this today. He wanted to use ctags with an RSpec file, but since ctags doesn’t understand “describe” and “it”, there was no way for it to extract any useful information from it. Now, this is a trade of the framework designer has to make, and in the case of RSpec I think that the DSL is totally justified, but in other cases it’s not.

So take the issue at hand. Adding a few methods to Symbol, so that finding information in a database will look a bit nicer. In real terms this involves polluting the Symbol namespace with methods that have a very narrow scope. The usage (that looks more or less like this: Exhibition.all(:run_time.lt => 3)) uses something that reads easily from an English/SQL perspective, but not necessarily from a Ruby perspective. The main question I have when seeing this is what the eventual cost down the line will be for having it. Is this approach expandable? Is there any possibility of clashes with other libraries? Will someone else easily maintain it?

Focusing on beauty to generate adoption seems like the wrong choice for me. You add things that might not be so good long term, to get a larger initial code base. I would prefer to make the right choices for the right reasons first, and then let adoption be driven by that.

In summary, be responsible when designing APIs. I know those are very boring words. But it’s a reality, and your users will thank you for it.

PS: Sam just wrote a new comment, saying that the Symbol operators will be optional in the next DataMapper release. Good choice.

2 Comments | By Ola Bini | In: Uncategorized | tags: datamapper, design, dsl, good taste, ruby. | #