This post in the PAIPr series will be a little bit different. In fact it won’t contain any “real” AI code of any sort. Instead the chapter it’s based on (Chapter 6, Building Software Tools) is more about generalizing some of the code written before and adding a few needed searching tools to the tool box.

This is also the one chapter that provide quite difficult to port. In many cases the solutions is based on the Common Lisp functions in such a way that the resulting Ruby code ended up a bit clunky in some places. You specifically see this where a piece of code need to take more than one code argument. This is where the Common Lisp sharp-quote is really useful, and the Ruby symbol is not at all as useful. I’ll point out some examples of this when we touch on that code.

A generic REPL

But first let’s get started on the Eliza command line we created in the last post. This part of the chapter starts out with a lock at the interactive prompt for Lisp, and the main equivalent for Ruby would be IRb. But it’s quite easy to do something small that works more or less correctly. Basically it would read a string of text, call eval on that and then inspect the result and print it. The first stab at something generic that would do the same could look like this (lib/ch06/inter.rb):

def interactive_interpreter(prompt)
  while true
    print prompt
    puts(yield(gets))
  end
end

Nothing much happening. We expect a prompt of some kind, and a transformer. In the Lisp code the transformer is another lambda, but in the Ruby code it makes sense to send in a block.

Now that we have it, it’s a snap to use it to create a Ruby interpreter from it (lib/ch06/inter.rb):

def ruby
  interactive_interpreter '> ' do |str|
    eval(str)
  end
end

In the same manner the Eliza interpreter can be written like this (lib/ch06/inter.rb):

$:.unshift '../ch05'
require 'eliza2'

def eliza
  interactive_interpreter 'eliza> ' do |str|
    Eliza.eliza_rule(str.downcase.split,
                     Rule::ELIZA_RULES2)
  end
end

It would be a simple thing to add history and other convenient parts to this generic REPL framework.

In the Lisp code there is a need to flatten input after the Eliza rules have been used – due to some differences in the way Eliza was implemented, this is not necessary for our code. For posterity I’ll still display two versions of the compose-function Norvig gives. These are sufficiently different in Ruby to be interesting (lib/ch06/inter.rb):

def compose(first, second = nil, &block)
  second ||= block
  lambda do |*args|
    first[second[*args]]
  end
end

class Proc
  def +(other)
    lambda do |*args|
      self[other[*args]]
    end
  end
end

In the first example the composition looks a bit like the Lisp one, except that I allow the possibility to use either two procs or one proc and one block. The second example is maybe more idiomatic, adding a plus operator to Proc. This more or less matches the semantics of addition (or maybe composition is more like multiplication? hmm…)

A second version of the interpreter, with some more advanced features, look like this (lib/ch06/inter2.rb):

def interactive_interpreter(prompt,
                            transformer = nil,
                            &block)
  transformer ||= (block || proc { |arg| arg })
  while true
    begin
      case prompt
      when String
        print prompt
      when Proc
        prompt.call
      end
      puts(transformer[gets])
    rescue Interrupt
      return
    rescue Exception => e
      puts ";; Error #{e.inspect} ignored, back to top level"
    end
  end
end

def prompt_generator(num = 0, ctl_string = "[%d] ")
  lambda do
    print ctl_string%[num+=1]
  end
end

interactive_interpreter(prompt_generator)

This code does some funky things. First of all, it really tries HARD to give you a default transformer. You can use either proc as an argument, or give it a block. If you don’t do any of those it will use an identity proc instead. This is what that first line full of line noise does.

After that it tries to decide what to do with the prompt. If the prompt is a proc it calls it each loop, if it’s a string it just uses it. Finally it calls the transformer on the result of gets and then puts it. Notice the rescue blocks. I wanted to rescue any error condition, so I choose to use Exception. Otherwise you could crash the interpreter by calling a non-existing method for example. But it was a bit funny to be reminded the hard way that Ctrl+C actually generates an exception of type Interrupt. Since I was ignoring all exceptions I didn’t have any way of shutting down the ruby process. Only kill -9 worked. So that’s why the rescue of Interrupt needs to be there.

What about prompt_generator? This is a higher order method that makes it possible to give a prompt with ascending numbers each time a new prompt is created. It does this in a classic closure way, by incrementing the num argument every time it’s called. Notice the use of sprintf style formatting here. It’s generally much more capable than doing dynamic string interpolation.

Pattern matching revisited

It’s time to get back to the pattern matching tools we developed for Eliza and see if we can make them a bit more general. This turned out to be a bit complicated for some of the matching operations that is provided in the book, specifically since the Lisp reader makes reading patterns very easy compared to Ruby. Before we can get into the code ported from the book though, a small piece of the puzzle need to be fixed. Remember that we used ?x and *x as ways to represent variables in the matching pattern? The problem is that these aren’t general enough. So the first code to write is to be able to parse a Ruby string like “I think that (?* ?x) flurg” into the array [“I”, “think”, “that”, [“?*”, “?x”], “flurg”]. The code in lib/ch06/pat_read.rb accomplishes this:

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

  class << self
    def from_string(str)
      result = []
      str.scan(/(\(\?.*?\))|([^[:space:]]+)/) do |f|
        if f[1]
          result << f[1]
        else
          result << f[0][1..-2].split
        end
      end
      Pattern.new result
    end
  end
end

This makes use of a small regular expression that either matches stuff between parenthesis or chunks of non-space. This regular expression will not handle nested lists correctly, but except for that it will work quite all right for our current needs.

OK, back to the chapter. The code we need to write is all about adding more powerful matching operations to the language, and also making it extensible. As a typical example of the kind of patterns we might want to match is “?x (?or < = >) ?y” against “3 < 4”.

I’m not reusing any of the pattern matching code from Eliza. I’ve copied and modified pieces from that code though, but the differences are larger than the similarities in such a way that inheritance is not really practical.

The first part of the code for Pattern matching looks like this (lib/ch06/pat_match.rb):

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

  def match(input, bindings = {}, pattern = @pattern)
    case
    when !bindings
      nil
    when variable?(pattern)
      match_variable(pattern, input, bindings)
    when pattern == input
      bindings
    when segment_pattern?(pattern)
      segment_matcher(pattern, input, bindings)
    when single_pattern?(pattern)
      single_matcher(pattern, input, bindings)
    when pattern.is_a?(Array) && input.is_a?(Array)
      match(input[1..-1],
            match(input[0], bindings, pattern[0]),
            pattern[1..-1])
    else
      nil
    end
  end
end

This code follows the same pattern as earlier, checking for different types of entries in the pattern and matching based on that.

The simple variable matching is first, and looks like this (lib/ch06/pat_match.rb):

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

  def match_variable(px, i, bindings)
    (!bindings[px] && bindings.merge(px => i)) ||
      (bindings[px] == i && bindings)
  end

Nothing much have changed here.

The main difference in the structure of this code is that we won’t hard code which method to use for matching a specific type. Instead we’ll add a Hash of available matchers, and have them describe what to call to actually do the matching. In Common Lisp Norvig uses the fact that you can set properties on symbols for this. Although you can do the same thing in Ruby it doesn’t feel right at all, and I opted for a dictionary approach instead (lib/ch06/pat_match.rb):

  SINGLE_MATCH = {
    "?is"  => :match_is,
    "?or"  => :match_or,
    "?and" => :match_and,
    "?not" => :match_not
  }

  SEGMENT_MATCH = {
    "?*"  => :segment_match,
    "?+"  => :segment_match_plus,
    "??"  => :segment_match_?,
    "?if" => :match_if
  }

Here you see that there are two types of matchers. Things that only can match one element of something, and matchers that can eat zero or more tokens. These need to be handled differently and are thus defined in different places.

The glue for getting all of this working looks like this (lib/ch06/pat_match.rb):

  def segment_pattern?(pattern)
    pattern.is_a?(Array) &&
      pattern.first.is_a?(Array) &&
      SEGMENT_MATCH[pattern.first.first]
  end

  def single_pattern?(pattern)
    pattern.is_a?(Array) &&
      SINGLE_MATCH[pattern.first]
  end

  def segment_matcher(pattern, input, bindings)
    self.send(SEGMENT_MATCH[pattern.first.first],
              pattern,
              input,
              bindings)
  end

  def single_matcher(pattern, input, bindings)
    self.send(SINGLE_MATCH[pattern.first],
              pattern[1..-1],
              input,
              bindings)
  end

Nothing surprising – we just get the symbol name from the hash and then send it to ourselves. This implies that these methods need to be instance methods on Pattern for it to work. That’s the only constraint on adding new kinds of matching operators.

First up, the single token matchers. They look like this (lib/ch06/pat_match.rb):

  def match_is(var_and_pred, input, bindings)
    var, pred = var_and_pred
    new_bindings = match(var, input, bindings)
    if !new_bindings || !self.send(pred, input)
      nil
    else
      new_bindings
    end
  end

  def match_and(patterns, input, bindings)
    case
    when !bindings
      nil
    when patterns.empty?
      bindings
    else
      match_and(patterns[1..-1],
                input,
                match(patterns[0],
                      input,
                      bindings))
    end
  end

  def match_or(patterns, input, bindings)
    if patterns.empty?
      nil
    else
      new_bindings = match(patterns[0], input, bindings)
      if !new_bindings
        match_or(patterns[1..-1], input, bindings)
      else
        new_bindings
      end
    end
  end

  def match_not(patterns, input, bindings)
    if match_or(patterns,input,bindings)
      nil
    else
      bindings
    end
  end

All of them follow the same pattern. All except for match_is are interestingly recursive, defining themselves in terms of one another.

The segment matching is quite a lot more complicated, and we even need to add a new helper method to find the right place. This is because we need to have general back tracking (lib/ch06/pat_match.rb):

  def segment_match(pattern, input, bindings, start = 0)
    var = pattern[0][1]
    pat = pattern[1..-1]
    if !pat || pat.empty?
      match_variable(var, input, bindings)
    else
      pos = first_match_pos(pat[0], input, start)
      return nil unless pos

      b2 = match(input[pos..-1],
                 match_variable(var, input[0...pos], bindings),
                 pat)
      return b2 if b2
      segment_match(pattern, input, bindings, pos+1)
    end
  end

  def first_match_pos(pat1, input, start)
    input = [] unless input
    case
    when !pat1.is_a?(Array) && !variable?(pat1)
      (vv = input[start..-1].index(pat1)) && vv + start
    when start < input.length
      start
    else
      nil
    end
  end

Having first_match_pos makes it possible to write patterns that are not separated by literal tokens.

This test code from lib/ch06/pat_match.rb makes it obvious what kind of complicated segment matchings can be handle by this code:

  require 'pat_read'
  p Pattern.from_string("a (?* ?x) d").
    match(%w(a b c d))
  p Pattern.from_string("a (?* ?x) (?* ?y) d").
    match(%w(a b c d))
  p Pattern.from_string("a (?* ?x) (?* ?y) ?x ?y").
    match(['a', 'b', 'c', 'd', ['b', 'c'], ['d']])

Finally, matching one or more expressions, or matching zero or one expression is easily achieved using segment_match (lib/ch06/pat_match.rb):

  def segment_match_plus(pattern, input, bindings)
    segment_match(pattern, input, bindings, 1)
  end

  def segment_match_?(pattern, input, bindings)
    var = pattern[0][1]
    pat = pattern[1..-1]
    match(input, bindings, [var] + pat) ||
      match(input, bindings, pat)
  end

The main difference between the Common Lisp implementation of matching and the Ruby version is that there is no obvious way of embedding Ruby code there. If any Ruby code is added that has parenthesis in them the regexp reader will bail out. That’s why I decided to not actually implement match_if for now. We’ll have to live without it. Obviously it can be done using Ruby code, but a different representation might have to be chosen. I leave this as an exercise to the reader. =)

Another small nitpick is that it might be a good thing to be able to provide an abbreviation facility. Especially for patterns like “foo (?* ?x) bar” it would be nice to say “foo ?x* bar” instead. The final version of lib/ch06/pat_read.rb provides for this:

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

  class << self
    def from_string(str)
      result = []
      str.scan(/(\(\?.*?\))|([^[:space:]]+)/) do |f|
        if f[1]
          result << f[1]
        else
          result << f[0][1..-2].split
        end
      end
      Pattern.new expand(result)
    end

    attr_accessor :expansions

    def match_abbrev(symbol, expansion)
      self.expansions[symbol.to_sym] = expand(expansion)
    end

    def expand(pat)
      if !pat.is_a?(Array)
        if self.expansions[pat.to_sym]
          self.expansions[pat.to_sym]
        else
          pat
        end
      elsif pat.empty?
        pat
      else
        [expand(pat[0])] + expand(pat[1..-1])
      end
    end
  end

  self.expansions = { }
end

The final look at Eliza in Norvig’s book looks at how to generalize the rule based Eliza tool into a more general version. If I would do this I would probably go a totally different route than the one shown in PAIP, and provide something flexible based on mixins or inheritance. I couldn’t figure out a clean way of implementing the code in this part based on the current work we’ve done, so I decided to leave that out too.

Searching tools

In this section Norvig talks a bit about different tools for implementing search. Search can be characterized by four features. The start state, the goal state/states, the successor states and the ordering strategy. The four pieces will be part of all the search implementations presented here, in some way.

A simple way to do search is tree-searching. The algorithm can be used to implement several search tools with different characteristics. In lib/ch06/search.rb you can find tree_search:

    def tree_search(states, successors, combiner, &goal_p)
      dbg :search, ";; Search %p", states
      return nil if !states || states.empty?
      if goal_p[states.first]
        states.first
      else
        tree_search(combiner[successors[states.first], states[1..-1]],
                    successors,
                    combiner,
                    &goal_p)
      end
    end

Here we see the inconvenient way Common Lisp translates to Ruby. The arguments successor, combiner and goal_p are all blocks of code, but one of them can be sent as a block while the other has the be regular parameters. I’ve tried to be consistent and always put the goal predicate as the block parameter. The actual code does surprisingly little. It returns nil on failure (when the current states are empty or nil). It then checks if the first element of states matches the goal criteria, and then returns that element. On failure it calls itself recursively after finding the successors for the first element and combining them with the rest of the available states. To see how this works in practice, consider simple depth first (lib/ch06/search.rb):

    def depth_first(start, successors, &goal_p)
      tree_search([start],
                  successors,
                  proc{ |x, y| x+y },
                  &goal_p)
    end

The combining function uses simple addition of arrays. Before testing the code we need some simple helper methods to make the invocations look better (lib/ch06/search.rb):

module Trees
  class << self
    def binary(x)
      [2*x, 2*x + 1]
    end

    def finite_binary(n)
      proc do |x|
        binary(x).select { |child| child<=n }
      end
    end
  end
end

def is(value)
  lambda { |x| x == value }
end

With the help of these we can define the first test of depth first search (lib/ch06/eternal_search.rb):

require 'search'

debug :search
Search.depth_first(1,
                   proc{|v| Trees.binary(v)},
                   &is(12))

This code will run until you abort it, and it shows one of the problems with depth first search.

The alternative to depth first is breadth first search (lib/ch06/search.rb):

    def breadth_first(start, successors, &goal_p)
      tree_search([start],
                  successors,
                  proc{ |x, y| y + x },
                  &goal_p)
    end

The main difference here is that the combiner proc will actually focus on the rest of the states before looking at the successors of the current state. Using this version (lib/ch06/noneternal_search.rb):

require 'search'

debug :search
Search.breadth_first(1,
                     proc{|v| Trees.binary(v)},
                     &is(12))

will find the correct element quite quickly. Another way of getting around the problem above is to make sure to not generate an infinite successor function. If you try this (lib/ch06/noneternal_depth.rb):

require 'search'

debug :search
Search.depth_first(1,
                   Trees.finite_binary(15),
                   &is(12))

everything will work out right with the depth first search, since the finite_binary method will only generate a binary tree up to a specific N.

A problem with these algorithms is that they currently can’t take advantage of any specific knowledge about the problem space. They will trod along happily, either depth first or breadth first without any specific exceptions. One way of avoiding this behavior is to provide a cost function and some way of sorting based on cost. Once you have this you can implement best first search. If the problem space has any specific cost that means you’re getting closer to the value you’re looking for, this is a really good way of guiding a search (lib/ch06/guiding.rb).

require 'search'

module Search
  class << self
    def diff(num)
      lambda do |x|
        (x - num).abs
      end
    end

    def sorter(&cost_fn)
      lambda do |new, old|
        (new + old).sort_by do |n|
          cost_fn[n]
        end
      end
    end

    def best_first(start, successors, cost_fn, &goal_p)
      tree_search([start], successors, sorter(&cost_fn), &goal_p)
    end
  end
end

This code contains three different methods. The diff method will return a closure that in turn will return the distance to a specific number. The sorter method will return a closure that will sort the combination of it’s two arguments based on the cost of elements in the arrays. Finally, the implementation of best_first takes advantage of the sorter, takes a new cost function and generates a combiner based on the sorting and the cost function and promptly sends it along to the tree_search. All in all, best first basically just sorts the problem space based on cost before every iteration of a new search loop. If you look at the debug out put from code like this (lib/ch06/guiding.rb):

  debug :search
  Search.best_first(1,
                    proc{|v| Trees.binary(v)},
                    Search.diff(12),
                    &is(12))

you will see that it at every stage has the states closest to 12 at the front:

;; Search [1]
;; Search [3, 2]
;; Search [7, 6, 2]
;; Search [14, 15, 6, 2]
;; Search [15, 6, 2, 28, 29]
;; Search [6, 2, 28, 29, 30, 31]
;; Search [12, 13, 2, 28, 29, 30, 31]

If we know something about the successors, for example that all successors are greater than the current state, we can use that to give a cost function that provides an extremely high cost for numbers above the goal (lib/ch06/guiding.rb):

def price_is_right(price)
  lambda do |x|
    if x > price
      100000000
    else
      price - x
    end
  end
end

Using this code you will see that the debug output is quite different, even with the same parameters for the search (lib/ch06/guiding.rb):

  Search.best_first(1,
                    proc{|v| Trees.binary(v)},
                    price_is_right(12),
                    &is(12))

The debug looks like this:

;; Search [1]
;; Search [3, 2]
;; Search [7, 6, 2]
;; Search [6, 2, 15, 14]
;; Search [12, 2, 13, 15, 14]

Another variation on tree search is beam search. Beam search is based on best first search, but works on a limited “beam” of states at one time, by looking ahead and choosing a few best ways to proceed. Depending on the beam width you get different characteristics.

require 'guiding'

module Search
  class << self
    def beam(start, successors, cost_fn, beam_width, &goal_p)
      tree_search([start], successors, proc do |old, new|
                    sorted = sorter(&cost_fn)[old,new]
                    if beam_width > sorted.length
                      sorted
                    else
                      sorted[0...beam_width]
                    end
                  end,
                  &goal_p)
    end
  end
end

if __FILE__ == $0
  debug :search
  Search.beam(1,
              proc{|v| Trees.binary(v)},
              price_is_right(12),
              2,
              &is(12))

  # Search.beam(1,
  #             proc{|v| Trees.binary(v)},
  #             Search.diff(12),
  #             2,
  #             &is(12))
end

This code is a bit more complicated because the combiner proc is inlined in the call to tree_search. The commented code shows that different ways of working with beam search doesn’t necessarily yield perfect results. In the case of the second invocation it throws away the correct way of getting to the final state. If the beam width were set to 3 instead of 2 it would work fine.

OK, it’s time for a concrete search example. It concerns planning the flight of a small airplane where the longest distance it can fly is a 1000km. Based on this we want to be able to found routes for it between different American cities. First let’s look at the definition of some cities (lib/ch06/plan_flight.rb):

require 'beam_search'

City = Struct.new(:name, :long, :lat)

class City
  CITIES =
    [
     ['Atlanta',        84.23, 33.45],
     ['Boston',         71.05, 42.21],
     ['Chicago',        87.37, 41.50],
     ['Denver',        105.00, 39.45],
     ['Eugene',        123.05, 44.03],
     ['Flagstaff',     111.41, 35.13],
     ['Grand Junction',108.37, 39.05],
     ['Houston',       105.00, 34.00],
     ['Indianapolis',   86.10, 39.46],
     ['Jacksonville',   81.40, 30.22],
     ['Kansas City',    94.35, 39.06],
     ['Los Angeles',   118.15, 34.03],
     ['Memphis',        90.03, 35.09],
     ['New York',       73.58, 40.47],
     ['Oklahoma City',  97.28, 35.26],
     ['Pittsburgh',     79.57, 40.27],
     ['Quebec',         71.11, 46.49],
     ['Reno',          119.49, 39.30],
     ['San Francisco', 122.26, 37.47],
     ['Tampa',          82.27, 27.57],
     ['Victoria',      123.21, 48.25],
     ['Wilmington',     77.57, 34.14]
    ].map do |name, long, lat|
    new(name, long, lat)
  end
end

This code first defines a struct representing a City, then adds all American cities to a constant inside the class.

To be able to plan a trip, we really need to be able to find all the neighbors that are within a 1000km. This is an instance method on City (lib/ch06/plan_flight.rb):

  def neighbors
    CITIES.select do |c|
      c != self &&
        self.air_distance_to(c) < 1000.0
    end
  end

I’ll get back to air_distance_to in a while. Notice how nice select is to use like this. Another simple method needed is a way to find a city based on name. I decided to make that the indexing method for City (lib/ch06/plan_flight.rb):

  class << self
    def [](name)
      CITIES.find { |c| c.name == name }
    end
  end

Finally, the definition of the trip method, that gives back a routes, is also a class method on City (lib/ch06/plan_flight.rb):

  class << self
    def trip(start, dest)
      Search.beam(start,
                  proc { |c| c.neighbors },
                  proc { |c| c.air_distance_to(dest) },
                  1,
                  &is(dest))
    end
  end

As you can see it’s a beam search where the successors are all the neighbors of the city, and the cost for a city is the distance to the final destination.

Invoking trip with San Francisco and Boston looks like this (lib/ch06/plan_flights.rb):

if __FILE__ == $0
  debug :search
  City.trip(City['San Francisco'], City['Boston'])
  p "---"
  City.trip(City['Boston'], City['San Francisco'])
end

The trip from San Francisco to Boston looks like this:

;; Search [#<struct City name="San Francisco", long=122.26, lat=37.47>]
;; Search [#<struct City name="Reno", long=119.49, lat=39.3>]
;; Search [#<struct City name="Grand Junction", long=108.37, lat=39.05>]
;; Search [#<struct City name="Denver", long=105.0, lat=39.45>]
;; Search [#<struct City name="Kansas City", long=94.35, lat=39.06>]
;; Search [#<struct City name="Indianapolis", long=86.1, lat=39.46>]
;; Search [#<struct City name="Pittsburgh", long=79.57, lat=40.27>]
;; Search [#<struct City name="Boston", long=71.05, lat=42.21>]

While the equivalent one backwards look like this:

;; Search [#<struct City name="Boston", long=71.05, lat=42.21>]
;; Search [#<struct City name="Pittsburgh", long=79.57, lat=40.27>]
;; Search [#<struct City name="Chicago", long=87.37, lat=41.5>]
;; Search [#<struct City name="Kansas City", long=94.35, lat=39.06>]
;; Search [#<struct City name="Denver", long=105.0, lat=39.45>]
;; Search [#<struct City name="Flagstaff", long=111.41, lat=35.13>]
;; Search [#<struct City name="Reno", long=119.49, lat=39.3>]
;; Search [#<struct City name="San Francisco", long=122.26, lat=37.47>]

There is a different route in this code, based on the fact that the cost function is subtly wrong. The cost should not minimize the distance from the next city to the destination, but minimize the whole path.

Before fixing this problem though, let’s just quickly take a look at the tools needed for air distance (lib/ch06/plan_flight.rb):

  EARTH_DIAMETER = 12765.0

  def air_distance_to(city)
    d = distance(self.xyz_coords, city.xyz_coords)
    EARTH_DIAMETER * Math.asin(d/2)
  end

  def xyz_coords
    psi = deg_to_radians(self.lat)
    phi = deg_to_radians(self.long)
    [
     Math.cos(psi) * Math.cos(phi),
     Math.cos(psi) * Math.sin(phi),
     Math.sin(psi)
    ]
  end

  def distance(point1, point2)
    Math.sqrt(point1.
              zip(point2).
              map { |a, b| (a-b)**2 }.
              inject(0) { |sum, e| sum+e })
  end

  def deg_to_radians(deg)
    (deg.truncate + ((deg%1) * (100.0/60.0))) *
      Math::PI *
      1.0/180.0
  end

There is nothing really strange here. With this in place we can start taking a look at the second implementation of planning a trip, using the concept of paths (lib/ch06/plan_flight2.rb):

class Path
  attr_accessor :state, :previous, :cost_so_far, :total_cost

  def initialize(state = nil,
                 previous = nil,
                 cost_so_far = 0,
                 total_cost = 0)
    self.state = state
    self.previous = previous
    self.cost_so_far = cost_so_far
    self.total_cost = total_cost
  end

  def map(&block)
    res = [block[state]]
    if previous
      res + previous.map(&block)
    else
      res
    end
  end

  def to_s
    "#<Path to %s cost %.1f>" % [self.state, self.total_cost]
  end
end

class City
  class << self
    def trip(start, dest, beam_width = 1)
      Search.beam(Path.new(start),
                  path_saver(proc { |c| c.neighbors },
                             proc { |c, c2| c.air_distance_to(c2) },
                             proc { |c| c.air_distance_to(dest) }),
                  proc { |p| p.total_cost },
                  beam_width,
                  &is(dest, :state))
    end
  end
end

This code really does a lot. There is no point to have Path be a struct, since we need to give it default arguments. The Path.map method is needed later on, and we also provide a nice to_s implementation for it. The new trip implementation makes everything by Path’s instead of plain Cities. That makes the successor function slightly complicated. We also need a way of saying which key should be used by the is-method to decide if something is equal or not. path_saver and the new is looks like this (lib/ch06/plan_flight2.rb):

def is(value, key = nil)
  if key
    lambda { |path| path.send(key) == value }
  else
    lambda { |path| path == value }
  end
end

def path_saver(successors, cost_fn, cost_left_fn)
  lambda do |old_path|
    old_state = old_path.state
    successors[old_state].map do |new_state|
      old_cost = old_path.cost_so_far +
        cost_fn[old_state, new_state]
      Path.new(new_state,
               old_path,
               old_cost,
               old_cost + cost_left_fn[new_state])
    end
  end
end

def show_city_path(path)
  puts "#<Path %.1f km: %s>" % [path.total_cost, 
    path.map { |s| s.name }.reverse.join(' - ')]
end

With all this machinery in place, we can finally get back to planning those trips (lib/ch06/plan_flight2.rb):

if __FILE__ == $0
  show_city_path(City.trip(City['San Francisco'], City['Boston'], 1))
  show_city_path(City.trip(City['Boston'], City['San Francisco'], 1))
  show_city_path(City.trip(City['Boston'], City['San Francisco'], 3))
end

This gives these outputs:

#<Path 4514.8 km: San Francisco - Reno - Grand Junction - 
  Denver - Kansas City - Indianapolis - 
  Pittsburgh - Boston>
#<Path 4577.3 km: Boston - Pittsburgh - Chicago - 
  Kansas City - Denver - Grand Junction - 
  Reno - San Francisco>
#<Path 4514.8 km: Boston - Pittsburgh - Indianapolis - 
  Kansas City - Denver - Grand Junction - 
  Reno - San Francisco>

as expected.

A problem you might have noticed with the beam width in beam search is that it can fail to find something because of having the wrong width. Norvig calls the solution to this an iterative widening search, which does exactly what it sounds like – if it fails with one beam width it tries another, until it reaches a cutoff point. The code for this is in lib/ch06/iter_widening.rb:

require 'plan_flight2'

module Search
  class << self
    def iter_wide(start, successors, cost_fn,
                  width = 1, max = 100, &goal_p)
      dbg :search, "; Width: %d", width
      unless width > max
        beam(start, successors, cost_fn,
             width,
             &goal_p) ||
          iter_wide(start, successors, cost_fn,
                    width + 1, max, &goal_p)
      end
    end
  end
end

if __FILE__ == $0
  debug :search
  p Search.iter_wide(1,
                     Trees.finite_binary(15),
                     Search.diff(12),
                     &is(12))
end

This code will retry several times until it finds it’s goal or reaches the maximum width. Interestingly, the repeated work isn’t as large as you’d expect. This algorithm only wastes 10% of it’s time doing repetitive generations.

The two final search implementations we are going to look at all searches graphs instead of trees. The former implementations have actually also searched graphs, but in disguise. Tree searching can be applied to many kinds of graph searching too, albeit not as efficient in some cases.

A simple implementation of a graph search is a bit more complicated than the tree search (lib/ch06/graph_search.rb):

require 'iter_widening'

module Search
  class << self
    def graph(states,
              successors,
              combiner,
              state_eq = proc{ |a, b| a == b},
              old_states = [],
              &goal_p)
      dbg :search, ";; Search: %p", states
      return nil if states.empty?
      return states.first if goal_p[states.first]
      graph(combiner[new_states(states,
                                successors,
                                state_eq,
                                old_states),
                    states[1..-1]],
            successors,
            combiner,
            state_eq,
            old_states.find { |os| state_eq[os, states.first] } ?
              old_states :
              [states.first] + old_states,
            &goal_p)
    end

    def new_states(states, successors, state_eq, old_states)
      successors[states.first].select do |state|
        !(states.find { |s|
            state_eq[state,s]
          } || old_states.find { |s|
            state_eq[state,s]
          })
      end
    end
  end
end

The new_states method generates all the new states from the successors method, finding those that aren’t cyclic. The actual graph_search method is recursive in the same way the tree_search method.

The exercise it, we need a small method that generates two new nodes in a graph of numbers, and then we can see it in action (lib/ch06/graph_search.rb):

def next2(x)
  [x+1, x+2]
end

if __FILE__ == $0
  debug :search
  p Search.graph([1],
                 proc { |n| next2(n) },
                 proc { |x,y| y+x },
                 &is(6))
end

The final search algorithm to look at is A*. This code is substantially more complicated, but it’s also much more efficient. It uses paths to be able to find the best solution quickly. A* can be characterized as a general best-first graph search. The code looks like this (lib/ch06/a_star.rb):

require 'graph_search'

module Search
  class << self
    def a_star(paths,
               successors,
               cost_fn,
               cost_left_fn,
               state_eq = proc { |a, b| a == b},
               old_paths = [],
               &goal_p)
      dbg :search, ";; Search: %s", paths

      return [] if paths.empty?
      return [paths.first, paths] if goal_p[paths.first.state]

      path = paths.shift
      state = path.state
      old_paths = insert_path(path, old_paths)

      successors[state].each do |state2|
        cost = path.cost_so_far + cost_fn[state, state2]
        cost2 = cost_left_fn[state2]
        path2 = Path.new(state2, path, cost, cost+cost2)

        old = find_path(state2, paths, state_eq)
        if old
          if better_path(path2, old)
            paths = insert_path(path2, paths - [old])
          end
        else
          old = find_path(state2, old_paths, state_eq)
          if old
            if better_path(path2, old)
              paths = insert_path(path2, paths)
              old_paths = old_paths - [old]
            end
          else
            paths = insert_path(path2, paths)
          end
        end
      end
      a_star(paths,
             successors,
             cost_fn,
             cost_left_fn,
             state_eq,
             old_paths,
             &goal_p)
    end

    def find_path(state, paths, state_eq)
      paths.find do |p|
        state_eq[p.state, state]
      end
    end

    def better_path(path1, path2)
      path1.total_cost < path2.total_cost
    end

    def insert_path(path, paths)
      (paths + [path]).sort_by { |p| p.total_cost }
    end

    def path_states(path)
      return [] if !path
      [path.state] + path_states(path.previous)
    end
  end
end

if __FILE__ == $0
  debug :search
  p Search.path_states(Search.a_star([Path.new(1)],
                                     proc { |n| next2(n) },
                                     proc { |x,y| 1 },
                                     Search.diff(6),
                                     &is(6)).first)
end

In this case the algorithm is complicated enough that it might help to just look up a mathematical definition of it instead. It disappears a bit in the noise of Ruby.

As a small variation on the searches shown here, you can also quite easy make a search that returns every possible solution for a problem, provided that the problem space is finite. If it’s not… well, you’re on your own there. You can see code for search out all solutions in lib/ch06/search_all.rb:

require 'beam_search'

module Search
  class << self
    def all(start,
            successors,
            cost_fn,
            beam_width,
            &goal_p)
      solutions = []
      beam(start,
           successors,
           cost_fn,
           beam_width,
           &(proc do |x|
               solutions << x if goal_p[x]
               nil
             end)
           )
      solutions
    end
  end
end

The final pages of the section on search shows how to apply search to the GPS. Since GPS actually is search in disguise, using some of these algorithms might turn out to work well. The following code, from lib/ch06/search_gps.rb, successfully uses beam search to solve the Sussman anomaly:

$:.unshift '../ch04'
require 'gps3'
require 'blocks'
require 'beam_search'

class GPS2
  def successors(state)
    applicable_ops(state).map do |op|
      state.select do |x|
        !op.del_list.include?(x)
      end + op.add_list
    end
  end

  def applicable_ops(state)
    @ops.select do |op|
      op.preconds.subset_of?(state)
    end
  end

  def search(goal, beam_width = 10)
    Search.beam([[:start]] + @state,
                proc { |n| successors(n) },
                proc { |state|
                  state.select { |s| action?(s) }.size +
                  goal.select  { |con| !state.include?(con) }.size
                },
                beam_width
                ) do |state|
      goal.subset_of?(state)
    end.select do |s|
      action?(s)
    end
  end
end

if __FILE__ == $0
  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]))
  require 'pp'
  pp gps.search([[:a, :on, :b], [:b, :on, :c]])
end

Wow. That turned out to be a meatier chapter than I’d expected. It’s over now, at least, and we have some general tools to bring forward into the next chapters. Both searching and pattern matching will turn out to be really important for the coming approaches.

Next post it will be time to look at solving algebra problems. Interesting stuff.

1 Comment | By Ola Bini | In: paipr | tags: artificial intelligence, paipr, searching. | #

I have been asked a few times in different circumstances why I feel the need to create my own language instead of just working with Io. That is a very valid question, so I’m going to try to answer it here.

First of all, I like Io a lot. Ioke is close enough to Io that it will be obvious who the parent is. In my mind at least, the differences are in many ways cosmetic and in those that are not it’s because I have some fairly specific things in mind.

So what are the main differences? Well, first of all it runs on the JVM. I want it that way because of all the obvious reasons. The Java platform is just such a good place to be. All the libraries are there, a good way of writing extensions in a language that is not C/C++, a substrate that gives me threads, GC and Unicode for free. So these reasons make a big difference both for people using Ioke, and for me. I want to be able to use Ioke to interact with other languages, polyglot programming and all. And since I expect Ioke to be much more expressive than most other languages, I think it will be a very good choice to put on top of a stable layer in the JVM. Being implemented in C makes these benefits go away.

Of course I could just have ported Io to the JVM and be done with it. That’s how it all started. But then I realized that if I decided to not do a straight port, I could change some things. You have seen some discussions about the decisions I’m revisiting here. The whole naming issue, handling of numbers, etc. Other things are more core. I want to allow as much syntactic flexibility as possible. I really can’t stand the three different assignment operators. I know they make the implementation easier to handle, but having one assignment operator with pluggable semantics gives a more expressive language.

Another thing I’m adding in is literal syntax for arrays and hashes, and literal syntax for referencing and setting elements in these. Literals make such a difference in a language and I can’t really handle being without it. These additions substantially complicate the language, but I think it’s worth it for the expressive power.

A large difference in Ioke will be the way AST modification will be handled. Io gives loads of power to the user with regard to this, but I think there is more that can be done. I’m adding macros to Ioke. These will be quite powerful. As an example, the DefaultMethod facility (that gives arguments, optional arguments, REAL keyword arguments and rest argument) can actually be implemented in Ioke itself, using macros. At the moment this code is in Java, but that’s only because of the bootstrapping needed. The word macro might be a bad choice here though, since it executes at the same time as a method. The main difference is that a macro generally has call-by-name/call-by-need semantics, and that it will modify it’s current or surrounding AST nodes in some way. Yes, you heard me right, the macro facility will allow you to modify AST siblings. In fact, a macro could change your whole script from that point on… Of course Io can do this, with some trickery. But Ioke will have facilities to do it. Why? Doesn’t that sound dangerous… Yeah. It does, but on the other hand it will make it really easy to implement very flexible DSLs.

A final note – coming from Ruby I’ve always found Io’s libraries a bit hard to work with. Not sure why – it’s probably just personal taste, but the philosophy behind the Io libraries seem to not provide the things I like in a core library. So I will probably base Ioke’s core library more on Ruby than on Io.

There you have it. These are the main reasons I decided to not use Io. And once I started to diverge from Io, I decided to take a step back and start thinking through the language from scratch. Ioke will be the result, when it’s finished. (Haha. Finished. Like a language is ever finished… =)

4 Comments | By Ola Bini | In: ioke | tags: io, ioke, programming language design, programming languages. | #

One of my guiding principles for Ioke is that I want to try to at least think through most of the parts of it, including things that most other languages have/don’t have. One of the decisions I made quite far back but haven’t written about concerns numbers. I have decided to go back to PL/I and COBOL with regards to real numbers. Well, that’s not the whole truth. I’m simply not going to have a representation of for real numbers in Ioke. Instead something like “101.1” will result in a decimal number. They will have infinite range in Ioke, and they will always be exact. To me it’s never made sense to have float and double in a general purpose programming language. Or, it makes sense from a performance perspective, but most of the time these types just bite us in the behind.

How many times have you seen numbers represented as float or double in C, C++, Java, C# or any of the other languages that include floating points? If you want to do scientific computation or non-discrete math, Ioke is probably not the right language anyway. But since it runs on top of the JVM you can write that part of your application in Java…

So, to recap, the type (which I might call ‘Decimal’ or ‘Radix’) will be exact. It will have potentially infinite range both in the magnitude and the fraction. Ioke will not have NaN or +/-Inf.

Also going back to other languages (such as Scheme and Smalltalk), Ioke will have a numerical tower. That means things like rationals will be in the language. So will integers of course (and yes, they will also have infinite range). I’m still thinking about complex numbers. They might be there, but falling back on my reasoning for not having floats in the language, having complex numbers seem kinda inconsistent. So probably not. I will have magnitudes, units and quantities, since these are extremely useful features in a language. That means money will be a combination of a ‘Decimal’ and a Currency Unit. There might be support for syntax here, in the style of Kawa Scheme (a quantity is a number directly followed by a unit name, without any whitespace: 100.2dollar, 5kg, etc. Obviously, there will be expanded ways of calling these, such as: Units Currency dollar(100.2), Units Mass kg(5). I haven’t decided on the exact hierarchy or syntax right now, but I know I will not build it from scratch. Instead I’m going to use gnu.math from Kawa.
So that’s my thinking about numbers for Ioke. The other details will be mostly natural things. I haven’t decided which bases should be literals, or if I can do something like Common Lisp with this. We’ll see. (And in fact, I haven’t even added numbers to the parser yet… They haven’t been necessary.)

12 Comments | By Ola Bini | In: ioke | tags: floats, ioke, numbers, numerical tower, scheme. | #

JAOO was interesting this year. A collection of very diverse subjects, and many focusing on programming languages – we had presentations about functional programming, JavaScript, Fortress and JRuby. Guy Steele and Richard Gabriel did their 50 in 50 presentation, which was amazing. I’ve also managed to get quite a lot of work done on Ioke. The result of all this is that my head has been swimming with thoughts about programming languages. I’ve also had the good fortune of spending time talking about languages with such people as Bill Venners, Lars Bak, Neal Ford, Martin Fowler, Guy Steele, Richard Gabriel, Dave Thomas, Erik Meijer, Jim des Rivieres, Josh Holmes and many others.

It is obvious that we live in interesting times for programming languages. But are they interesting enough? What are the current trends in cutting edge programming languages? I can see these:

• Better implementation techniques. V8 is an example of this, and so is Hotspot. V8 employs new techniques to drive innovation further, while Hotspot’s engineers continuously adds both old and new techniques to their tool box.
• DSLs. The focus by some people on domain specific languages seem to be part of the larger focus on languages as an important tool.
• Functional semantics. Erik Meijers keynote was the largest push in this direction, although many languages keep adding features that make it easier to work in a functional style. Clojure is one of the new languages that come from this point, and so is Scala. The focus on concurrency generally lead people to the conclusion that a more functional style is necessary. From the concurrency aspect we get the recent focus on Erlang. Fortress aslo seems to be mostly in this category.
• Static typing. Scala and Haskell are probably the most representative of this approach, in trying to stretch static typing as far as possible to improve both the programmer experience, semantics and performance.

Is this really it? You can quibble about the specific categories and where the borders are. I’m not entirely satisfied with where I put Fortress, for example, but all in all it feels like this is what’s going on.

Seeing 50 in 50 reminded me about how many languages we have seen, and how different these all are. It feels like most of the innovation happened in the past. So why is the current state of programming languages so poor? Is it because other things overshadow the language itself? I really don’t believe that. I think a good enough language would enable better tools, more productivity and more successful projects. So why isn’t it happening? We seem to be stuck in a rut. Anders Hejlsberg said in his opening keynote that the last 10-15 years have been an anomaly. I really do hope so.

What is apparent from the list compiled above is that everything that currently happens is very much evolutionary in approach. Innovation is happening, but it’s mostly small innovation.

We need a language revolution. We need totally new ways at looking at programming languages. We need new innovation, unfettered by the failures and successes of times past. We need more language implementors. We need more people thinking about these things.

I don’t know what the new approaches need to be, but the way I see it the last 10 years have been quite disappointing. If programming languages really are important tools, why haven’t we seen the same kind of innovation in that field as we have in IDEs and tools? Why haven’t we seen totally new ideas crop up? Is it because language development is always evolutionary? Does it have to be? Or is everyone interested in the field already convinced that we are at the peak right now? Or that Lisp or Smalltalk was the peak?

What needs to be rethought? I’ve read Jonathan Edwards recently, and he writes a lot about revisiting basic ideas and conclusions. I don’t agree with everything he says, but in this matter he’s totally right. We need to revisit all assumptions. We need to figure out better ways of doing things. Programming languages are just too important. We shouldn’t be satisfied with the current approaches just because we don’t know anything better.

We need a revolution.

12 Comments | By Ola Bini | In: blogging | tags: future of programming, programming language design, programming languages. | #

Another part of naming that I’ve spent some time thinking about is what I should call the core concepts in the language. A typical example of this is using the word Object for the base of the structure. I’ve never liked this and I get the feeling that many languages have chosen this just because other languages have it, instead of for any good reason.

In a prototype based language it definitely doesn’t feel good. My current favorite name for the hierarchy base is right now Origin. Since everything is actually copied from this object, that word seems right.

Another naming issue that turns up quite quickly is what the things you store in an object is called. In JavaScript they are called properties. In Io they are called slots. It’s hard to articulate why I don’t like these names. Maybe this is a personal preference, but at the moment I’m considering calling them ‘cells’ in Ioke.

What about String? That does seem like an arbitrary choice too. A String is probably short for String of characters in most cases, and that’s really an implementation choice. What if you do like JavaScript engines where a String is actually a collection of character buffers stitched together? In that case String feels like a slightly suspect name. For Ioke I’m currently leaning towards just calling it Text. Text is immutable by default and you need a TextBuffer to be able to modify text on the fly.

Another thing that sometimes feel very strange in prototype based languages is the name you give the operation to create new instances. In Io it’s called clone. In JavaScript you use new. Here I’m really not sure what to do. At the moment I’m considering leaving it to ‘clone’ but provide two factory methods that will allow better flow while reading and also avoid the clone keyword. Say that you have something called Person. To create a new Person the code should look like this:

p = Person with(
  givenName = "Ola"
  surName = "Bini")

This code will first call clone, and then execute the code given to with inside of the context of the newly cloned object. This pattern should be quite common when creating instances. The other common person I see occurring is this:

tb = TextBuffer from("some text")

Maybe there are other useful cases, but with and from will work quite well for most purposes in the core libraries. What’s nice is that these methods are extremely easy to create and they don’t need any fancy runtime support. They are entirely composable from other primitives.

This is currently the kind of decisions I’m trying to make. If you have something that works nice instead of ‘clone’, do let me know.

16 Comments | By Ola Bini | In: ioke | tags: design, ioke, programming language design, programming languages. | #

I’ve been spending lots of time thinking about naming lately. What kind of naming scheme do you follow in your class names? How does your method names look like? Your variables? Do you use active words or passive? Should you use longer, descriptive names or shorter, more succinct? How can you best use symbolic freedom to allow better naming? What kind of names do you choose for your core classes? Does it matter or should you just go for Good ‘Ole ‘Object’?

These musings is part of my design thoughts about Ioke, and I’ll describe some of the decisions I’ve made.

I first want to start with something simple. What naming scheme do you follow for your class-like objects? I’m going to go the same way as Java here, using capitalized words. This will be a convention and not anything forced by syntax, since the class-like objects will actually not be classes since Ioke is a prototype based language.

So what about method names and variable names? First of all there is no distinction in Ioke. Everything is a message. There are several variations here that are quite common. I have opinions on all of them, of course.

• C#: A typical method might be called ‘ShouldRender’. The words are capitalized and put together without any separation characters. Most symbols aren’t allowed so method names are generally restricted to numbers, letters and underscore. This style doesn’t appeal to me at all. I find it really hard to read. That the naming convention is the same class names makes it hard to discern these names from each other. Having the words connected without any separation characters also doesn’t help.
• Java: The same as C# except that the first character is lower case: ‘shouldRender’. The same restrictions apply as for C#. I find it slightly easier to read than C#, since there is specific difference between class names and method names. But the train wreck style of putting together the words is still inconvenient.
• Ruby: With symbol freedom and small case separated by underscores, Ruby has a quite different style. The example would look like this: ‘should_render?’. The question mark is really nice to have there, and the under scores really make it easier to read. Of course, the difference between class names and method names is quite large which is both a good and bad thing.
• Lisp: Typical Lisp naming is all lower case and separated by dashes: ‘should-render?’. Lisp also has high degrees of symbolic freedom so you can use basically any character except for white space and close parenthesis in it. I like this style a lot. It’s eminently readable but the main problem is the dash. Allowing dashes in names in a language with infix operators means that you must use spaces around a minus sign which really would annoy me. So even though I like this style I don’t think it’s practical unless your language uses Lisp style notation for operator names.
• Smalltalk: This style of naming is definitely the most different. It tries to avoid words that run together by using keyword selectors. That means you interleave the arguments with the parts of the name of the method to call. For example: ‘render: “str” on: screen1’ is actually a method called ‘render:on:’. The method of naming have really nice reading benefits but there is also a high cost. Specifically, Ioke uses spaces to chain invocation, which means that if I used Smalltak style names I would need to surround all method invocations with parenthesis which won’t look good at all in this case. There are lots of good reasons for this naming but ultimately it doesn’t work.

Those are basically the naming styles I can think of right now. Everything else is mostly variations on it. So what will I use for Ioke? I don’t know exactly, but the two alternatives I’m considering right now is Ruby names and Java names + symbolic freedom. I’m leaning towards the Java naming. Adding more symbols will make it easier to use good names. Small things like question marks and exclamation marks really make a difference. Another reason for going with Java names is that it allows interacting with Java without doing name mangling (lke JRuby does). That’s highly attractive, even though the method names will be a bit more compact with this convention.

Any opinions on this?

8 Comments | By Ola Bini | In: ioke | tags: ioke, naming, programming language design, programming languages. | #

I’m sitting here at JAOO, waiting for the second day to start. The first presentation will be a keynote by Lars Bak about V8. It was a quite language heavy event yesterday too, with both Anders Hejlsberg and Erik Meijer keynoting about languages – plus there were introductions to both Fortress and Scala going on. And after the JVM language summit last week, I feel like the world is finally starting to notice the importance of programming languages.

So it seems only fitting that I’ve decided to go public with Ioke, the source code, what it is and where it’s going.

Ioke is a strongly typed, extremely dynamic, prototype based object oriented language. It’s homoiconic and got built in support for several kinds of macros. The languages that most closely influence Ioke is Io, Smalltalk, Self, Ruby and Lisp (Specifically Common Lisp).

The language is currently built on top of the JVM, but I’m currently considering compiling it down to JavaScript and run it on V8.

I have several goals with the language but the most specific one is to create a language that combines the things I like about Ruby and Lisp together. It turns out that Io already has many of the features I’m looking for, but in some cases doesn’t go far enough. I also wanted to have a language that is very well suited to express internal DSLs. I want to have a language that doesn’t get in my way, but also gives me loads of power to accomplish what I want. To that event I’ve designed a macro system that some people will probably find insane.

The current status of the implementation is that there isn’t any. I’m starting from scratch. I’ve already created two partial implementations to find the right way to implement the language, so with this blog post I’m starting the implementation from scratch. I know quite well what I want the language to look like and how it should work.

I’ve used Scala for the other two implementations but have decided to not do that for this implementation. The reason being one that Charles Nutter often talks about – that having to include the Scala runtime in the runtime for Ioke seems very inconvenient. So the implementation will initially use Java, but I’m aiming for the language to be self hosting as quickly as possible. That includes creating an Ioke Antlr backend, so it will take some time.

I’m going to post about Ioke quite regularly while I’m working on it, talking about design decisions and other things related to it. I will try to base me decisions in Ioke on what seems right, and not necessarily on the words chosen for representation in other language. I’ll try to talk about my reasoning behind choices like this.

And what about performance? Well, I know already that it will be atrocious. If you want to do scientific computing, maybe Ioke won’t be for you. The current design of the language will make it fairly hard to do any kinds of performance tunings, but I do have a plan for how to compile it down to bytecode at least. This still doesn’t mean it will perform extremely well, but my goals for Ioke specifically doesn’t include performance. I care about performance sometimes, but sometimes I don’t and Ioke is a tool I want to have for those cases where raw expressiveness power is what is most important.

You can follow the development in my git repository at http://github.com/olabini/ioke.

15 Comments | By Ola Bini | In: ioke | tags: future of programming, ioke, metaprogramming, programming languages. | #

I know I’ve mentioned Clojure now and again in this blog, but I haven’t actually talked that much about it. I feel it’s time to change that right now – Clojure is in the air and it’s looking really interesting. More and more people are talking about it, and after the great presentation Rich gave at the JVM language summit I feel that there might be some more converts in the world.

So what is it? Well, a new Lisp dialect for the JVM. It was originally targeting both the JVM and .NET but Rich ended up not going through with that (a decision I can understand after seeing the efforts Fan have to expend to continue providing this feature).

It’s specifically not an implementation of either Common Lisp nor Scheme, but instead a totally new language that’s got some interesting features. The most striking feature of it is the way it embraces functional programming. In comparison to Common Lisp who I characterize as being a multiparadigm language, Clojure has a heavy bent towards functional programming. This includes a focus on immutable data structures and support for good concurrency models. He’s even got an implementation of STM in there, which is really cool.

So what do I think about it? First of all, it’s definitely a very interesting language. It’s also taken the ideas of Lisp and twisting them a bit, adding some new ideas and refining some old ones. If I wanted to do concurrency programming for the JVM I would probably lean more towards Clojure than Scala, for example.

All that said, I am in two minds about the language. It is definitely extremely cool and it looks very useful. The libraries specifically have lots to say for them. But the other side of it for me is from the point of Lisp purity. One of the things I really like about Lisps is that they are very simple. The syntax is extremely small and in most cases everything will just be either lists or atoms and nothing else. Common Lisp can handle other syntax with reader macros – which end up with results that are still only lists and atoms. This is extremely powerful. Clojure has this to a degree, but adds several basic composite data structures that are not lists, such as sets, arrays and maps. From a pragmatic standpoint I can understand that, but the fact that they are basic syntax instead of reader macros mean that if I want to process Clojure code I will end up having to work with several kinds of composite data structures instead of just one.

This might seem like a small thing, and it’s definitely not something that would stop me from using the language. But the Lisp lover in me cringes a bit at this decision.

All in all Clojure is really cool and I recommend people to take a look at it. It’s getting lots of attention and people are writing about it. Stu Halloway is currently in the process of porting Practical Common Lisp to Clojure, and I recently saw a blog post about someone porting On Lisp to Clojure, so there is absolutely an interest in it. The question is how this will continue. As I’ve started saying more and more: these are interesting times for language geeks.

10 Comments | By Ola Bini | In: blogging | tags: clojure, lisp, programming, programming languages. | #

The final day of the language summit sported loads of interesting presentations, just like the first two days. I can’t over stress how well prepared these three days have been – especially with regards to the schedule. A huge thanks to Brian Goetz, John Rose and Charles Nutter, for being the main instigators and coordinators of this effort. Very nice work indeed.

The third day also marked a departure from being mostly JVM centered. The first presentation was Mads Torgersen from Microsoft, talking about LINQ. I hadn’t actually realized what a thin layer over regular closure syntax the LINQ infrastructure was. Quite impressive, although it still feels like one of those ideas that really makes sense in some cases, but not at all as many as was originally envisioned.

Per Bothner described his Kawa toolkits. If you didn’t know, Kawa is one of the older alternative language implementations for the JVM – but it’s not only an implementation of the Scheme language. It also contains parts of an Emacs Lisp, XQuery and Common Lisp implementations. As it turns out, Kawa has ended up being more of a general toolkit for building dynamic languages on top of the JVM. Very nice, and I’m seriously considering stealing parts of it for a few of my language projects. It was also a quite astute presentation with no unnecessary frills. Per ended his presentation with some thoughts about language design – and why so many languages seem to be dynamic just for the sake of being dynamic. I totally agree with his sentiment, even though ioke will be about as dynamic a language I can imagine.

Erik Meijer talked about Fundamentalist Functional Programming. Erik is always a hilarious speaker, and even if you don’t agree with everything he says, it’s great entertainment and loads of great quotes and soundbites. Eriks main point of view is that what is currently called functional programming is really nothing of the sort. The only way you can be really pure in a functional programming language is by specifying which parts of the implementation that has any side effects. If these are specified the side effects can be isolated and thus you can keep the rest of your system free from the taint of side effects. He showed several compelling examples of how side effects totally mess up calculations that look like the should have been correct and functional in approach. One thing he said that I really liked was when he talked about “types that lie”, where you have situations in many common languages that have static types but the types doesn’t actually tell you the whole truth. In that case Erik feels it’s better to just be dynamic, since dynamic languages at least doesn’t have dishonest types. Of course, the thrust of the presentation was Haskell, and how Erik is trying to sneak the benefits of Haskell into Visual Basic. He’s got his own group for fooling around with things like this, and it does sound extremely interesting. Oh, and he’s looking for people for his team. In another life, if I’d been more convinced about static typing, I might have applied.

I ended up spending most of the lunch/open space time working on my Antlr-ELisp system. It’s actually coming along really great. Simple lexing works and I have most of the DFA handling implemented too. It ended up being a really fun project although lack of lexical closure bites me over and over again. I’m just too used to it from Scheme and Common Lisp, and not having it makes my brain hurt sometimes.

Part of the open space time was also devoted to a quick introduction by Cliff Click to his Azul systems. Every time I see the kind of analysis he can do with that VM I’m astonished. It’s just so cool stuff. Everyone should have an account there. Really.

After lunch, Rene Jansen from IBM talked about NetRexx – one of those JVM languages that aren’t as well known, but lives a really successful life inside of company boundaries. I really wonder have many of those languages there really are.

Paul Phillips gave a presentation about Scalify – one of those funny, half way crazy projects. It aims to translate Java code to Scala, to make adoption for Scala easier. At first glance this sounds quite easy, but there are several complications to the approach, and Paul introduced it all in a candid and interesting way.

After that it was Neal Gafter’s turn (who is nowadays at Microsoft. Will the world ever start making sense? =). From the title of the presentation I got the impression it would mostly be about closure proposals, but instead he talked a lot about the impedance mismatch between different languages on the JVM, how you can handle that and what needs to be done to the core language to make it possible to interoparete better between languages. Closures is one of the things that Java really doesn’t have, and it’s very obvious from the design of the standard libraries. Very good and thoughtful presentation.

Cliff Click did one of his typical romps about the JVM and how well some of the alternative language translate to bytecode. Extremely entertaining and full of small factoids about the JVM (like the usefulness/lack of usefulness of the Integer.valueOf cache in some cases).

After that, I did a short presentation about Jatha, and tried to mention some generalities about the languages that haven’t succeeded so far, and what kind of support they might want to have from the JVM in the future.

The last talk of the day was about the Parrot VM. In this case there were a bit too much introductory material about dynamic languages, and not enough meat about how the Parrot VM actually works. I would have loved to get much more deep content here than I actually did.

All in all the Friday was an extremely strong day with regards to presentations. Loads of technical content but also some more high level musings that contained real insight about the current state of programming language implementations. I’m very happy with the whole JVM language summit, and it seems like it will happen again next year. If you have any interest in this area I recommend that you set aside the time to go. It will be worth your while.

And now I’m off to JAOO, which also seems to have lots of delicious content for a language geek like myself. We do live in very interesting times.

1 Comment | By Ola Bini | In: blogging | tags: jvm language summit. | #

I’m sitting here during the third day of the JVM language summit, and thought I’d summarize the second day a bit. Hopefully I’ll soon be able to write about this day too as soon as it’s over.

The second day started out with Gosling talking about some of his history and how that influenced the design and implementation of Java. Not extremely interesting, but a few funny soundbites. Best was probably the quote from Guy Steele: “Lisp is like a black hole”, meaning that if you design a language close enough to Lisp, Lisp ends up dragging it in and the language becomes Lisp.

After that Tom Ball talked about JavaFX script and javac. This was quite interesting, the challenges of compiling something using the javac compiler does seem to be fraught with problems.

Charles Nutter made a good talk about the internals and interesting parts of the implementation of JRuby.

After that it was lunch and some open spaces talk about language interoperability. This is really a large problem and it was obvious that we don’t really know how to do this well between different languages on the JVM. The one solution is always go through the Java types, but this has the problems that the Java types are quite poor in comparison to some of the other languages.

Eugene Kuleshov gave an introduction to the ASM bytecode generation framework, which was very helpful – as it turned out at least half the people in the room were already using it.

Rob Nicholson gave an intro to IBM’s work on PHP for the JVM which seems to have many of the same problem as we have faced with JRuby.

Attila talked about his MOP and the directions it will take in the future, and this looks really nice. I’m looking forward to having some time to play with it.

Rémi Forax talked about his backport of JSR-292. I’m totally in awe about this. I wouldn’t even know where to begin to implement it. Very cool.

Rich Hickey did a very inspired talk about Clojure. Definitely one of the best talks – it includes loads of information, introduced the language in a good way and was generally very cool. I do have some opinions about the language itself, but I’ll save that for another blog post.

The last two talks of the day was about Python. The first one was about gradual typing for Python – this is interesting work and long term it would be interesting to see how it turns out. The Jython internals talk by Frank was also very nice and gave at least me some new insight into how their implementation actually works.

All in all a very interesting day.

No Comments | By Ola Bini | In: blogging | tags: jvm language summit. | #