Condition system in Ioke

Continuing in the series of “standing on the shoulders of giants”, I will in this post talk a little bit about one feature I always miss in “modern” languages. A condition system. According to Wikipedia, Smalltalk also had one, but I’m only familiar with the Common Lisp and Dylan versions. And that’s where my inspiration is coming from.

So what is a condition system, you might ask? Isn’t that just conditionals? Nope, not really. It’s actually totally different. Conditions are a generalization of errors. This means that errors are a kind of conditions, but you can also do other things with conditions. The main difference is that invoking a condition doesn’t necessarily mean that the stack will be unwinded. Instead, the code handling the condition can choose to do different things depending on the condition. Conditions can have different severity and different default actions. So most real errors would probably end up unwinding the stack if no handler was defined for it. But warnings can also be conditions – and the default warning action might depend on a command line flag. Or maybe you want to have a handler for a specific warning that should be an error in your code. Etc. The possibilities are quite literally endless, and when you can define your own conditions, the power of this mechanism should be apparent. (And if you’re thinking continuations, that’s not exactly it, but almost.)

Common Lisp allow you to disregard some exceptions. You can also restart the code involved that threw an exception, if you think it’s likely to be intermittent. And the handler for this doesn’t need to be lexically close to the place that caused the problem. Instead, the place that raised a condition will give you a couple of options on what to do, commonly called restarts. Restarts are lexical closures that can change the environment that caused the exception, which means it’s possible to fix things quite neatly. Most (all?) Common Lisp implementations have a default exception handler that drops you into the interactive debugger, which is invoked with the lexical closure of the point where the exception happened. You might want to read that last sentence a few times over if it didn’t make sense the first time.

You might ask yourself if this magic is some kind of Lisp trick? That’s a good question, since it seems to mostly be available in Lisp systems, such as Common Lisp and Dylan. (Smalltalk is obviously very Lispy too. =)

There is nothing technical standing in the way for other languages to adopt a condition system. Ruby would do well with it for many things, although I don’t think it would be a great thing to graft it on at this point.

I’m pretty sure I can implement it easily in Ioke, on top of the JVM. The interesting point will be to see how I can make it interact with Java exceptions…

Since I haven’t implemented it yet, I don’t know the exact syntax, but I do have some ideas.

  noSuchCell: block(c, c asText println),
  incorrectArity: block(c, c asText println),
  # code that might cause the above conditions

  somethingHappened: block(c, invokeRestart(useNewValue, 24))
    value = 1
      useNewValue: block(val, value = val),
      quit: block(break),

      value println

These examples show a small subset of what you will be able to do – define handlers for specific conditions, and in these handlers call restarts. I will probably provide some way to collect all handlers for a condition, so Common Lisp style interactive choices can be made. I will try to keep the system a bit easier than the Common Lisp version, but hopefully I’ll be able to retain it’s power.

Language generation

This post is the first in a series of posts about PAIPr. Read here for more info about the concept.

Today I would like to start with taking a look at Chapter 2. You can find the code in lib/ch02 in the repository.

Chapter 2 introduces Common Lisp through the creation of a series of ways of doing generation of language sentences in English, based on simple grammars. It’s an interesting chapter to start with since the code is simple and makes it easy to compare the Ruby and Common Lisp versions.

The first piece to take a look at is the file common.rb, which contains two methods we’ll need later on:

require 'pp'

def one_of(set)

class Array
  def random_elt

As you can see I’ve also required pp, to make it easier to print structures later on.

Both one_of and Array.random_elt are extremely simple methods, but it’s still nice to have the abstraction there. I’m retaining the naming from the book for these two methods.

The first real example defines a grammar by directly using methods. (From simple.rb):

require 'common'

def sentence; noun_phrase + verb_phrase; end
def noun_phrase; article + noun; end
def verb_phrase; verb + noun_phrase; end
def article; one_of %w(the a); end
def noun; one_of %w(man ball woman table); end
def verb; one_of %w(hit took saw liked); end

As you can see, all the methods just define their structure by combining the result of more basic methods. A noun phrase is an article, then a noun. An article is either ‘the’ or ‘a’, and a noun can be ‘man’, ‘ball’, ‘woman’ or ‘table’. If you run sentence a few times you will see that you sometimes get back quite sensible sentences, like [“a”, “ball”, “hit”, “the”, “table”]. But you will also get less interesting things, such as [“a”, “ball”, “hit”, “a”, “ball”]. At this stage the space for variation is quite limited, but you can still see a simplified structure of the English language in these methods.

To create an example that involves some more interesting structures, we can introduce adjectives and prepositions. Since these can be repeated zero times, or many times, we’ll use a production called PP* and Adj* (pp_star and adj_star in the code). This is from simple2.rb:

require 'simple'

def adj_star
  return [] if rand(2) == 0
  adj + adj_star

def pp_star
  return [] if rand(2) == 0
  pp + pp_star

def noun_phrase; article + adj_star + noun + pp_star; end
def pp; prep + noun_phrase; end
def adj; one_of %w(big little blue green adiabatic); end
def prep; one_of %w(to in by with on); end

Nothing really changes here, except that in both the optional productions we randomly return an empty array 50% of the time. They then call themselves recursively. The noun phrase production also changes a bit, and adj and prep gives us the two new terminals needed. If you try this one, you might get some more interesting results, such as: [“a”, “table”, “took”, “a”, “big”, “adiabatic”, “man”]. It’s still nonsensical of course. And it seems that this approach with randomness generates quite large output in some cases. To make it really nice there should probably be a diminishing bias in the adjectives and prepositions based on the length of the already generated string.

Another problem with this approach is that it’s kinda unwieldy. Using methods for the grammar is probably not the right choice long term. More specifically, we are tied to this implementation by having the grammar be represented as methods.

A viable alternative is to represent everything as a grammar definition – using a rule based solution. The first part of rule_based.rb looks like this:

require 'common'

# A grammar for a trivial subset of English
$simple_grammar = {
  :sentence => [[:noun_phrase, :verb_phrase]],
  :noun_phrase => [[:Article, :Noun]],
  :verb_phrase => [[:Verb, :noun_phrase]],
  :Article => %w(the a),
  :Noun => %w(man ball woman table),
  :Verb => %w(hit took saw liked)}

# The grammar used by generate. Initially this is $simple_grammar, but
# we can switch to other grammars
$grammar = $simple_grammar

Note that I’m using double arrays for the productions that aren’t terminal. There is a reason for this that will be more pronounced in the later grammars based on this. But right now it’s easy to see that a production is either a list of words, or a list of list of productions. Production names beginning with a capital is a terminal – this is a convention in most grammars. I didn’t use capital letters for the terminals when using methods because Ruby methods named like that causes additional trouble when calling them.

Now that we have the actual grammar we also need a helper method. PAIP defines rule-lhs, rule-rhs and rewrites, but the only one we actually need here is rewrites. (From rule_based.rb):

def rewrites(category)

And actually, we could do away with it too, but it reads better than an index access.

The final thing we need is the method that actually creates a sentence from the grammar. It looks like this:

def generate(phrase)
  case phrase
  when Array
    phrase.inject([]) { |sum, elt|  sum + generate(elt) }
  when Symbol

If what we’re asked to generate is an array, we generate everything inside of that array, and combine them. If it’s a symbol we know it’s a production, so we get all the possible rewrites and take a random element from it. Currently every production have one rewrite, so the random_elt isn’t strictly necessary – but as you’ll see later it’s quite nice. And finally, if phrase is not an Array or Symbol, we just return the phrase as the generated element.

I especially like the use of inject as a more general version of (mappend #’generate phrase). Of course, for readability it would have been possible to implement mappend too:

def mappend(sym, list)
  list.inject([]) do |sum, elt|
    sum + self.send(sym, elt)

But I choose to use inject directly instead, since it’s more idiomatic. Note that this version of mappend doesn’t work exactly the same as Common Lisp mappend, since it doesn’t allow a lambda.

Getting back to the generate method. If you were to run generate(:sentence), you would get the same kind of output as with the method based version – with the difference that changing the rules is much simpler now.

So for example, you can use this code from bigger_grammar.rb, which creates a larger grammar definition and then sets the default grammar to use it:

require 'rule_based'

$bigger_grammar = {
  :sentence => [[:noun_phrase, :verb_phrase]],
  :noun_phrase => [[:Article, :'Adj*', :Noun, :'PP*'], [:Name],
  :verb_phrase => [[:Verb, :noun_phrase, :'PP*']],
  :'PP*' => [[], [:PP, :'PP*']],
  :'Adj*' => [[], [:Adj, :'Adj*']],
  :PP => [[:Prep, :noun_phrase]],
  :Prep => %w(to in by with on),
  :Adj => %w(big little blue green adiabatic),
  :Article => %w(the a),
  :Name => %w(Pat Kim Lee Terry Robin),
  :Noun => %w(man ball woman table),
  :Verb => %w(hit took saw liked),
  :Pronoun => %w(he she it these those that)}

$grammar = $bigger_grammar

This grammar includes some more elements that make the output a bit better. For example, we have names here, and also pronouns. One of the reasons this grammar is easier to use is because we can define different versions of the productions. So for example, a noun phrase can be the same as we defined earlier, but it can also be a single name, or a single pronoun. We use this to handle the recursive PP* and Adj* productions. You can also see why the productions are defined with an array inside an array. This is to allow choices in this grammar.

A typical sentence from this grammar (calling generate(:sentence)) gives [“Terry”, “saw”, “that”], or [“Lee”, “took”, “the”, “blue”, “big”, “woman”].

So it’s easier to change these rules. Also believe that it’s easier to read, and understand the rules here. But one of the more important changes with the data driven approach is that you can use the same rules for different purposes. Say that we want to generate a sentence tree, which includes the name of the production used for that part of the tree. That’s as simple as defining a new generate method (in generate_tree.rb):

require 'bigger_grammar'

def generate_tree(phrase)
  case phrase
  when Array { |elt| generate_tree(elt) }
  when Symbol
    [phrase] + generate_tree(rewrites(phrase).random_elt)

This code follows the same pattern as generate, with a few small changes. You can see that instead of appending the results from the Array together, we instead just map every element. This is because we need more sub arrays to create a three. In the same manner when we get a symbol we prepend that to the array generated. And actually, at this point it’s kinda interesting to take a look at the Lisp version of this code:

(defun generate-tree (phrase)
  (cond ((listp phrase)
         (mapcar #'generate-tree phrase))
        ((rewrites phrase)
         (cons phrase
               (generate-tree (random-elt (rewrites phrase)))))
        t (list phrase)))

As you can see, the structure is mostly the same. I made a few different choices in representation, which means I’m checking if the phrase is a symbol instead of seeing if the rewrites for a symbol is non-nil. The call to mapcar is equivalent to the Ruby map call.

What does it generate then? Calling it with “pp generate_tree(:sentence)” I get something like this:

 [:noun_phrase, [:Name, "Lee"]],
  [:Verb, "saw"],
   [:Article, "the"],
    [:Adj, "green"],
   [:Noun, "table"],

which maps neatly back to our grammar. We can also generate all possible sentences for a grammar without recursion, using the same data driven approach.

The code for that can be found in generate_all.rb:

require 'rule_based'

def generate_all(phrase)
  case phrase
  when []
  when Array
  when Symbol
    rewrites(phrase).inject([]) { |sum, elt|  sum + generate_all(elt) }

def combine_all(xlist, ylist)
  ylist.inject([]) do |sum, y|
    sum + { |x| x+y }

If you run generate(:sentence) you will get back a list of all 256 possible sentences from this simple grammar. In this case the algorithm is a bit more complicated. It’s also using the common Lisp idiom of working on the first element of a list and then recur on the rest of it. This makes it possible to combine everything together. I assume that it should be possible to devise something suitably clever based on the new Array#permutations or possible Enumerable#group_by or zip.

It’s interesting how well the usage of mappend and mapcar maps to uses of inject and map in this code.

Note that I’ve been using globals for the grammars in this implementation. An alternative that is probably better is to pass along an optional parameter to the methods. If no grammar is supplied, just use the default constant instead.

Anyway, the code for this chapter is in the repository. Play around with it and see if you can find anything interesting. This code is definitely an introduction to Lisp, more than a serious AI program – although it does show the kind of approaches that have been used for primitive code generation.

The next chapter will talk about the General Problem Solver. Until then.

Paradigms of Artificial Intelligence Programming (in Ruby)

Since I never can get enough projects, I’ve decided to start on something I’ve thought about doing for a long time. There are several reasons for doing it, but foremost among them is that I want to get back to playing with AI, and I want to have a project with many small pieces that I can do when I have some time over. If it ends up being educational or useful for others at the same time, well, I’m not complaining!

So what is it?

Well, first I’d like to introduce a book. It’s called Paradigms of Artificial Intelligence Programming or PAIP for short. It’s written by Peter Norvig, who’s also written several other books about AI. Currently he’s the Director of Research at Google. PAIP is probably both my favorite book about AI, and my favorite book about Common Lisp. It’s a really great book. Really. If you have any interest in one of those two subjects you should get hold of it. PAIP doesn’t cover cutting edge AI, but rather takes the historic view and looks at several examples from different eras, going from the first programs to some later, quite advanced things.

I’ve read it numerous times, went through the code and tweaked it and so on. It’s lots of fun. But that was a few years ago. So basically, what I want to do is to go through the book again. But this time I’m going to write all the programs in Ruby – converting them from Common Lisp and then maybe tweak them a bit to make them more idiomatic. And I’m planning to post it here. Or rather, I’m going to post the actual source code to I’m going to blog about all the code I write. You don’t necessarily have to have the book, since I’m going to surround the code with some descriptions and explanations.

Once again then, why should anyone care? Well, I don’t know. No one might care. But for me personally it’s going to be an interesting experience converting idiomatic Common Lisp into idiomatic Ruby. It’s going to be fun to revisit the old approaches to AI. And it might serve as a good, code heavy introduction to the subject for anyone interested in it.

I do have the permission from Peter Norvig to do this. The Ruby code I write is covered by the MIT license, while any Lisp code posted as part of this exercise is covered by the license here:

Also note that I sometimes won’t write the most obvious Ruby – it will be good to have a few links to the original Lisp code.