// comments are lies!

Time to say bye bye!

2008-11-15T21:05:00.002+01:00

I've been thinking for quite some time now that maybe I should stop posting on this blog.

There are many reasons behind this decision and maybe I'll start another blog somewhere down the line. But I simply don't believe that this is the right format anymore (maybe it never was, I don't know) for whatever it is that I'm trying to achieve with // comments are lies! This will therefore be my last post here.

I want to thank everyone who participated in the discussions we've had here. I've learned a LOT. Thank you.

See you @ Twitter, SourceForge, Delicious, Github, Google Groups, Facebook, LinkedIn, ...

Google Flutrends and predictive data mining

2008-11-12T21:29:00.000+01:00

Google.org recently announced Flutrends, a web site that provides estimates of flu activity in the US based on search queries.

I'm not sure whether this is a good thing or just plain scary and I'm not surprised that they've found such a strong correlation between their data and the government's either. I am, however, quite interested in knowing what else is in there.

In Ian Ayres' book Super Crunchers: Why Thinking-by-Numbers Is the New Way to Be Smart it is mentioned that Wal-Mart use data mining techniques in order to match shelf space against predicted customer demand. Pretty cool. And they're not alone. But they use closed data sets. Their own, of course, and data that they buy from companies like Terabyte.

I hope that more companies and governments follow Google's example and open up (at least parts of) their data stores for public use. There are lots and lots of mash-ups available that show the potential of combining data sets and creating useful services to the public. Of course, for most companies they still have to find out that they actually have interesting data in their systems.

If the only tool you have...

2008-10-29T11:43:00.001+01:00

"If the only tool you have is a hammer, you will see every problem as a nail." - Abraham Maslow

This week, I've been experimenting with Monte Carlo methods for a Pentago AI player. I've written pattern-based AI players for Pentago before and (somewhere) I've got an unfinished implementation that uses Minimax as well.

I didn't really expect much from this little experimental player (it's only about 100 lines of Python code) but it has turned out to be "not too bad". Despite the fact that it only considers one game state at a time... maybe that says more about my other players though ;-)

I'll try to add MCTS (Monte Carlo Tree Search) during this week, maybe even UCT (Upper Confidence bounds applied to Trees) which ought to make the player quite a bit stronger.

Computer Go reference bots

2008-10-22T21:39:00.001+02:00

Interested in Computer Go? Then you probably already know about Don Dailey's excellent work on providing a number of Monte Carlo reference implementations. So far, he has managed to implement it in ~~two~~ three different languages (Java, C and some language called Vala).

The announcement is here and the Java bot is available here. It's not the prettiest Java code out there, but Don is a C programmer (I think) so he is excused. It was very interesting and educating to study the code. I've been reading a lot of the Monte Carlo Computer Go papers but I've always felt as if I've missed something fundamental since my understanding of how it works felt too... simple.

Now that I've seen the code I can say, with confidence, that it *is* quite simple. Implementing a Monte Carlo method, that is. Getting a decent (let alone, good) AI-player for 19x19 Go seems quite far from simple.

Pattern matching function declarations in Python part II

2008-10-19T12:44:00.000+02:00

Ok, so the pattern matching idea kind of backfired.

I was under the impression that a function's default arguments wouldn't be evaluated until the function was called. Which would have meant that I could've changed them, into valid Python code, in the decorator function. But... that's not the way it works.

My first attempt at something more interesting than matching a constant failed miserably. I wanted to use a variable to constrain that matching process. For example:

>>> @patternmatched
... def foo(lst = [__, var, var, __]):
...   pass

should match any lst which is a list and where there is, at least one, repeated element somewhere in it. Both [1,1,2,3,4] and [3,2,1,1,2] should match, whilst [1,2,1,3,1] shouldn't.

Unfortunately. Trying the above results in a NameError since both __ and var are unbound. And, seeing that, I remembered that this is *exactly* what happened about three years ago when I was trying out various syntaxes for PyRete. It's the reason I decided to put all of the matching in the if-statement instead of in the function arguments.

But, it's not quite time yet to give up. There are several possible ways to go about this. The "best" choice is probably to use Andrew's python4ply, or maybe PyPy. Either way, I'll get a chance to compare and contrast the work of implementing a DSL in Python versus Common Lisp.

Handling defrules in MPS, executing the RHS

2008-10-16T09:15:00.005+02:00

I've been rewriting the deftemplate code for MPS more or less from scratch... but I'll have to talk about that some other time. It's high time to focus on the defrule macro(s). I'll break this up into several posts and I'll start with the function for executing the RHS.

The MPS syntax (a subset of CLIPS') for defrule looks like this:

  defrule-construct
    ::= (defrule rule-name
          conditional-element*
          =>
          expression*)

  conditional-element
    ::= template-pattern-CE ¦ assigned-pattern-CE ¦
        not-CE ¦ and-CE ¦ or-CE ¦ test-CE ¦
        exists-CE ¦ forall-CE

  assigned-pattern-CE
    ::= single-field-variable <- template-pattern-CE

  not-CE     ::= (not conditional-element)
  and-CE     ::= (and conditional-element+)
  or-CE      ::= (or conditional-element+)
  test-CE    ::= (test function-call)
  exists-CE  ::= (exists conditional-element+)
  forall-CE  ::= (forall conditional-element
                         conditional-element+)

  template-pattern-CE
    ::= (deftemplate-name single-field-LHS-slot*)

  single-field-LHS-slot
    ::= (slot-name constraint)

  constraint ::= ?  connected-constraint


  connected-constraint
    ::= single-constraint ¦
        single-constraint & connected-constraint
        single-constraint ¦ connected-constraint

  single-constraint
    ::= term ¦ ~term

  term       ::= constant ¦ single-field-variable ¦
                 :function-call ¦ =function-call

  single-field-variable
    ::= ?variable-symbol

I'm quite far from having all of the above supported, but I've got enough to show how the function that executes the RHS of a rule works.

The defrule macro works by expanding into a series of macro calls which handle more and more specific cases in the processing. The macro itself is quite simple

(defmacro defrule (name &body body)
  (let ((rhs (cdr (member '=> body)))
        (lhs (ldiff body (member '=> body))))
    `(progn
       (compile-lhs ,name ,@lhs)
       (compile-rhs ,name ,@rhs))))

As you can see, it expands into two other macro-calls: compile-lhs and compile-rhs, where the first parses the conditional-elements and, in the process, creates two symbol-tables (fact-bindings and variable-bindings) with all of the variables it can find.

The second macro handles the RHS and looks like this:

(defmacro compile-rhs (name &body rhs)
  (when (null rhs)
    (setf rhs '(t)))
  `(defun ,(make-sym "RHS/" name) (activation)
     (let* ((token (activation-token activation))
            ,@(mapcar #'make-fact-binding (reverse fact-bindings))
            ,@(mapcar #'make-variable-binding (reverse variable-bindings)))
       ,@rhs)))

So, if we evaluate this:

MPS> (defrule foobar
       ?foo <- (foo (bar ?bar) (baz 1))
        =>
       (format t "~%~A ~A" ?foo ?bar))

it expands into this (among other things):

(DEFUN RHS/FOOBAR (ACTIVATION)
  (LET* ((TOKEN (ACTIVATION-TOKEN ACTIVATION))
         (?FOO (NTH 0 TOKEN))
         (?BAR (DEFTEMPLATE/FOO-BAR ?FOO)))
    (FORMAT T "~%~A ~A" ?FOO ?BAR)))

Most of the work is with figuring out how to assign values to each of the variables. I'm using a simple list as the structure for the tokens. WMEs (fact objects) are added in the order they appear in the list of conditional elements. Once all of the WMEs are bound, all of the variable-bindings are bound by using the automatically constructed accessor methods for those structs.

The actions in the RHS are simply spliced into the let* form at macro-expansion time which completes the function definition. It is then evaluated and stored with the rule's production node. Later, when that production node is left-activated, it creates an activation (with the WMEs and some additional meta-data like timestamps and such) and places it in the conflict-set. If that activation ever triggers a rule, it is passed as an argument to the RHS function.

Since I haven't got enough of "the rest" of MPS in place. We're going to have to mock an activation and call the function directly to see whether or not it works.

MPS> (rhs/foobar (make-activation :token (list (foo (bar 1) (baz 1)))))
#S(DEFTEMPLATE/FOO :BAR 1 :BAZ 1) 1
NIL
MPS>

There's really not much more to say about the RHS so I'll stop here. The LHS is a bit more complicated and I hope that I can show some of that code soon.

Pattern matching function declarations in Python

2008-10-13T15:32:00.004+02:00

All those who have tried to write a rules-based program know that there are, at least, two differences between "regular" programming and rules-based programming. The first is that you have no direct control over the flow of execution and the second is that, instead of specifying input parameters, you specify patterns that should be matched for a certain "function" (or rule) to be invoked.

The bit about giving up control is quite difficult for most programmers (at least the ones I know) and it doesn't translate well to other types of programming anyway. But it would be interesting to try and add pattern matching functions to a language such as Python and see whether it could be useful (or at least fun to experiment with).

It's not a new idea. The first language to support pattern matching this way was Snobol (version 4 I think) which was introduced in the late 60s/early 70s. Both Haskell and Erlang has it and there are a bunch of others as well, Qi and Prolog to mention a few.

I'm thinking about something along the lines of:

>>> from patternmatching import *
>>> @patternmatched
... def fac(n = 0):
...   return 1
...
>>> @patternmatched
... def fac(n = int):
...   return n* fac(n = n-1)
...
>>> fac(5)
120
>>>

The idea is that the first function would handle any calls to the fac function where the parameter n is 0 and the second function would handle any calls where the parameter n is an int (but not 0). And, yes. I've got the above working already. The tricky bits are providing more elaborate forms of pattern matching with the available syntax.

I'll be back shortly with some code...

When should I use a rule engine?

2008-10-09T19:53:00.000+02:00

This is an interesting question that I think about quite a lot. I consider myself somewhat of a rule engine evangelist and I've always felt a bit annoyed that it's so difficult to explain the benefits of a rules based approach to others.

The textbook answer to the question is that a rule engine should be used when the problem is ill-structured and the solution is difficult or impractical to describe with an algorithm or when the knowledge required to formulate a solution changes frequently. But that's just words.

I've tried to find an ill-structured problem that is small enough to use as an example but I'm not really sure one exists. The best I've got so far is the problem of translating a number to text, where 0 <= number <= 99. It's an ill-structured problem that is easy to grasp but still translates to an ugly implementation with a lot of special-cases-handling in most programming languages. Not that it translates to a very pretty CLIPS application either... but I guess that comes with the territory.

Anyone got a better idea?

CLIPS is not a Lisp

2008-09-28T17:48:00.003+02:00

In a recent thread on JBoss Drools' Rules Users mailing list, Mark Proctor writes:

... The Drools DRL language itself was designed as a more intuitive and less verbose language, this becomes increasinly important as you start to add more complex syntax which becomes harder to read with a lisp approach. I think most people in here would agree that the Drools DRL approach is an improvement over the lisp approach of clips/jess - apart from the die hard lisp fans.

I might be a die hard Lisp fan, but if you ask me, the problem is not that CLIPS (and Jess) are Lisp-like it's that they are Lisp-like.

CLIPS doesn't use a Lisp approach. It might look that way, but the similarities are only skin-deep. CLIPS lack one of the most fundamental requirements for being Lispy, namely, code as data. It lacks other things as well, but given that capacity (or in other words to be able to provide a higher level syntactical abstraction on top of CLIPS) there would be nothing wrong with CLIPS syntax that couldn't be fixed with CLIPS syntax. Yes. I know about build and eval but they'll only take you so far. It's not that I'm unhappy with CLIPS, but I honestly believe a Lisp-based CLIPS would be so much better.

My apologies to Mark. This rant has nothing to do with JBoss Drools. It's just that his post had the magic words in it ;-)

Updating my Common Lisp environment

2008-09-23T20:23:00.000+02:00

I've been using LispBox since Peter first announced it. At home I've got both a Mac OS X version (using OpenMCL) as well as a Windows version (using CLISP). I've also tried Lisp In A Box and Ready Lisp (using SBCL).

LispBox has worked great for me but it's time to take off the training wheels. So I've uninstalled all of my ready-to-go Lisp kits, downloaded a fresh snapshot of SLIME and installed a copy of Aquamacs. One day, maybe, I'll be enough hacker to compile Emacs from source but that's going to have to wait a while...and Aquamacs boasts about being so much better in a direct comparison so I've decided to give it a try. I've yet to become familiar with Emacs' way of handling the clipboard anyway so this seems a perfect fit at the moment (Aquamacs allows you to use the "usual" Mac shortcuts).

Installations were a lot easier than I thought. The only problem I ran into was actually that it took some time to get Finder to show the .emacs.d folder (I had to use the menu option Go to folder...). I've already got several CL implementations running (ECL, Clozure and SBCL) on my Mac so now I just have to figure out either how to get SLIME to connect to several Lisps or how to customize Aquamacs so that I can do M-x ECL to start SLIME with ECL.

Structuring data via behavioural synthesis

2008-09-16T11:53:00.003+02:00

I am one of the those who have been (and some still are, I guess) waiting for Geoff Wozniak to post a link to his thesis, Structuring data via behavioural synthesis, on his blog Exploring Lisp. To my surprise, it turns out that someone at the University of Western Ontario has published it already, only "bad" thing with that is of course that now I want to see the code even more.

Working out some kinks

2008-09-13T21:30:00.000+02:00

I've been a student of Lisp(s) for roughly five years now. Unfortunately, sometimes, pretty simple bugs show up and bite me. I'm a bit embarrassed to say this but... I haven't written anything about MPS for a while because I've had a problem with the proof-of-concept code. Or, so I thought. It turned out that the agenda function used mapcan instead of mapcar. Funny (well...) thing is that since I thought it used mapcar it took me quite a while to find it.

CrazyStone vs Aoba Kaori

2008-09-04T21:04:00.001+02:00

Yet another Computer Go program wins a handicap game (8 stones) against a professional Go player. Earlier today, CrazyStone (running on a PC with 8 processors) played Aoba Kaori (4P) at the FIT2008 conference (here are some photos) and won by resignation.

In a couple of weeks, MoGo plays Myungwan Kim (again) at the Cotsen Go Tournament. It will be interesting to see whether or not they can repeat the success from the US Go Congress. I have a feeling that Kim will have adapted to MoGo's playing style.

Roman numerals

2008-09-02T14:19:00.001+02:00

Yesterday we had another GothPy meeting. Apart from getting some formalities out of the way, Emily showed us how to do the FizzBuzz kata in just over 4 minutes. Quite impressive. This was one of the things she and Michael Feathers had done for the Programming with the Stars competition at Agile 2008.

We were also supposed to tackle a "new" kata, converting numbers to roman numerals, but a debate about what rules should be used to guide the conversion (for example, should 1999 be 'IMM' or 'MCMXCIX'?) got us into doing an english translation instead (converting numbers to english text). And as the smug Lisp weenie I have turned into I couldn't help but to inform everyone that the built-in format directives ~@R and ~R solves those problems quite neatly. The hard part is of course to write the Lisp implementation ;-)

Anyway, as usual, it turned out we thought about the problem a bit differently but we quickly converged around a "good enough" strategy even though it wasn't particularly pretty and we ended up with lots of code duplication. I learned a lot though. It put my previous solution in a different light and it's always interesting to see and hear how others tackle awkward problems like this.

And BTW. Here is my attempt at the Roman numerals kata (using doctest):

def as_roman_numeral(num):
   """
   Returns a string containing the roman numeral representation of num or
   None if num is outside of range(1,4000).
 
   >>> as_roman_numeral(4000) == None
   True
   >>> as_roman_numeral(1)
   'I'
   >>> as_roman_numeral(99)
   'XCIX'
   >>> as_roman_numeral(888)
   'DCCCLXXXVIII'
   >>> as_roman_numeral(1999)
   'MCMXCIX'
   >>> as_roman_numeral(2001)
   'MMI'
   """
 
   units       = [0, 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
   tens        = [0, 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
   hundreds    = [0, 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
   thousands   = [0, 'M', 'MM', 'MMM']
 
   if num in xrange(1,4000):
       th, mils = num//1000, num%1000
       h, cents = mils//100, mils%100
       te, u    = cents//10, cents%10
       return "".join(numerals[digit] for digit, numerals in [(th, thousands),
                                                              (h, hundreds),
                                                              (te, tens),
                                                              (u, units)] if digit > 0)
   else:
       return None

It works with numbers in range(1,4000) and it implements the rules as described on Wikipedia.

MPS inference engine, the rest of the implementation

2008-08-23T10:09:00.000+02:00

In the last post I mentioned a few of the design choices I've made for the Rete Network implementation. The rest of the engine is quite straight forward and simple. There's really not much to talk about but I'll show some code anyway ;-).

Another thing though, and a bit more interesting really, is that I have been thinking about whether or not I should try to stay true to CLIPS' behaviour and functionality in the misc engine functions as well.

For example, the agenda function currently returns a list of all activations on the agenda and CLIPS prints them but returns no value. Similarly there's facts which behaves like get-fact-list instead. Used at the REPL there's little difference in what the user sees but the reason I've made them different is because then I can write other functions on top of them.

Ok. As promised, some code. Here is the run function (which uses agenda):

|(defun run (&optional (limit -1))
|  (do* ((curr-agenda (agenda) (agenda))
|        (execution-count 0 (+ execution-count 1))
|        (limit limit (- limit 1)))
|       ((or (eq limit 0)
|            (= (length curr-agenda) 0)) execution-count)
|    (let* ((activation (first curr-agenda))
|           (rhs-func (make-sym "RHS-" (string (activation-rule activation))))
|           (prod-mem (make-sym "PRODUCTION-" (string (activation-rule activation)) "-MEMORY")))
|      (funcall rhs-func activation)
|      (store '- activation prod-mem))))

and here is the assert function (I'm shadowing the built-in assert function, still accessible as cl:assert though):

|(defun assert (&rest facts)
|  (incf timestamp)
|  (dolist (fact facts)
|    (store '+ fact 'working-memory)
|    (mapcar #'(lambda (node) (funcall node '+ fact timestamp))
|            (gethash (type-of fact) (gethash 'root rete-network)))))

I hope that they are at least somewhat readable to others.

I've now finished the functions that make up the inference engine implementation. And it works... as long as you manually divide your program into alpha, beta and production nodes and connect them properly in the Rete Network ;-)

Back at work

2008-08-18T20:49:00.004+02:00

The future is that way Mom (and it does pattern matching)!

Today was my first day back at work. The past eight months have been great! Eo and I have had a blast, but it's time to go on - facing new and exciting challenges and that means tackling a new business area for me and day care for Eo.

MPS inference engine, the Rete Network implementation

2008-08-15T14:28:00.000+02:00

It's difficult to talk about the MPS defrule macro and the code it expands to without first explaining the environment in which it is meant to run. So I'll try to explain and describe my current thoughts and ideas that make up the design of the MPS inference engine in this and following posts.

The engine is made up of some I/O functions (assert and retract), the Rete Network, a Conflict Resolver and an Execution Engine. The Rete Network is the most central part of the whole thing so I'll start there.

It is basically implemented within a hash-table. This is the simplest possible representation of a Rete Network that I can think of. There are, of course, a few helper functions to abstract away some of the book keeping details of this design choice. During rule compilation there are functions for adding a node/memory and connecting nodes/memories with each other and at run time there are functions to propagate facts/tokens, access contents of and store facts/tokens in memory.

A processing node (for example an alpha node) is implemented as a function and is stored in the hash-table as well. A very simple LHS construct like:

|(defrule foo
|  (bar (baz ?baz&:(> ?baz 10)))
|  =>)

would be represented in the Rete Network by the following function:

|(defun bar-baz->-10 (key fact timestamp)
|  (when (> (deftemplate/bar-baz fact) 10)
|    (store key fact 'bar-baz->-10-memory)
|    (propagate key fact timestamp 'bar-baz->-10)))

A join node is represented by two functions (one for left and one for right activation) and is slightly more complex (but not much). If we change the LHS to:

|(defrule foo
|  (bar-1 (baz ?baz))
|  (bar-2 (baz ?baz))
|  =>)

we would have to create a join node for joining facts on the ?baz variable. It would look something like this:

|(let ((left-memory  'bind-bar-1-memory)
|      (right-memory 'bind-bar-2-memory))
|  (defun join-bar-1-baz-and-bar-2-baz-left (key token timestamp)
|    (dolist (fact (contents-of right-memory))
|      (when (eq (bar-1-baz (nth 0 token))
|                (bar-2-baz fact))
|        (store key (append token (list fact)) 'join-bar-1-baz-and-bar-2-baz-memory)
|        (propagate key (append token (list fact)) timestamp 'join-bar-1-baz-and-bar-2-baz))))
|
|  (defun join-bar-1-baz-and-bar-2-baz-right (key fact timestamp)
|    (dolist (token (contents-of left-memory))
|      (when (eq (bar-1-baz (nth 0 token))
|                (bar-2-baz fact))
|        (store key (append token (list fact)) 'join-bar-1-baz-and-bar-2-baz-memory)
|        (propagate key (append token (list fact)) timestamp 'join-bar-1-baz-and-bar-2-baz)))))

As you can see variables are expanded into "positions" everywhere in the functions. Variables are, however, available and bound in the execution context of the production node's RHS function.

There are some more bits and pieces that are good to know. The root node, for example, is a hash-table. Each deftemplate-type is a key and the value contains a list of alpha nodes.

Compilation consists of (apart from expanding the rule's LHS into a number of functions) a series of calls to add-to-root and connect-nodes. Since each node is responsible for propagating as well as storing facts/tokens in memory we can connect the processing nodes to each other directly. The example above would be compiled with:

|(add-to-root 'bar-1 #'bind-bar-1) ; This might not be necessary! We should
|(add-to-root 'bar-2 #'bind-bar-2) ; be able to connect directly to the join.
|(connect-nodes 'bind-bar-1 #'join-bar-1-baz-and-bar-2-baz-left)
|(connect-nodes 'bind-bar-2 #'join-bar-1-baz-and-bar-2-baz-right)
|(connect-nodes 'join-bar-1-baz-and-bar-2-baz #'production-foo)

This is all theory, though. I don't actually have all of the defrule macro in place so the final version might very well expand into something different. But I hope this conveys the general idea of the Rete Network implementation.

Handling deftemplates in MPS

2008-08-11T13:24:00.002+02:00

There are three parts to my MPS (Minimal Production System) experiment, the "engine" itself and the deftemplate and defrule macros. So far, I've spent most of my time on the deftemplate macro. It turned out to be a bit trickier than I thought to implement. Mostly because I was stuck thinking about too complex macro expansions (which I never got to work).

Here is the syntax as BNF (well, sort of[1]):

|  deftemplate-construct
|    ::= (deftemplate deftemplate-name
|                     [comment]
|                     single-slot-definition*)
|
|  single-slot-definition
|    ::= (slot slot-name [default-attribute])
|
|  default-attribute
|    ::= (default ?NONE | expression) |
|        (default-dynamic expression)

It is a subset of CLIPS' deftemplate syntax. There are no multislots and no constraint-attributes for slots (types, ranges and such). But, apart from that, it is more or less the same[2]. And here's how it works:

|; SLIME 2007-03-14
|;;;; Compile file / [...] /mps. ...
|CL-USER> (in-package :mps)
|#[Package "MPS"]
|MPS> (deftemplate foo
|       (slot a-slot)
|       (slot a-default-slot (default 1))
|       (slot required-slot (default ?NONE)))
|FOO
|MPS> (foo)
|
|The slot: REQUIRED-SLOT in deftemplate: FOO requires an explicit value.
|   [Condition of type SIMPLE-ERROR]
|
|Restarts:
| 0: [ABORT] Return to SLIME's top level.
| 1: [ABORT-BREAK] Reset this process
| 2: [ABORT] Kill this process
|
|Invoking restart: Return to SLIME's top level.
|; Evaluation aborted
|MPS> (foo (required-slot 1))
|#S(DEFTEMPLATE/FOO :A-SLOT NIL :A-DEFAULT-SLOT 1 :REQUIRED-SLOT 1)
|MPS> (deftemplate bar
|       (slot default-gensym (default (gensym)))
|       (slot dynamic-gensym (default-dynamic (gensym))))
|BAR
|MPS> (bar)
|#S(DEFTEMPLATE/BAR :DEFAULT-GENSYM #:G31 :DYNAMIC-GENSYM #:G40)
|MPS> (bar)
|#S(DEFTEMPLATE/BAR :DEFAULT-GENSYM #:G31 :DYNAMIC-GENSYM #:G41)
|MPS>

The macro expands into a defstruct (deftemplate/foo) and another defmacro (foo) that is used as a constructor for the template. The reason it is a macro and not a regular function is because a function's arguments are evaluated whilst a macro's is not. And since there's no function named a-slot or a-default-slot etc. So we'd be thrown into the debugger if we tried to evaluate something like (foo (a-slot 1)).

Here's the macroexpansion of a simple template:

|MPS> (pprint (macroexpand-1 '(deftemplate foo
|                               (slot a)
|                               (slot b (default 1)))))
|
|(PROGN (DEFSTRUCT DEFTEMPLATE/FOO "" (A NIL) (B 1))
|       (DEFMACRO FOO (&REST SLOTS)
|         ""
|         (CALL-DEFSTRUCT-CONSTRUCTOR 'DEFTEMPLATE/FOO SLOTS)))
|; No value
|MPS>

Most of the code is spent checking that the template follows the syntax described in the BNF. The expansion itself is rather simple, almost trivial (it is the last progn below).

|(defmacro deftemplate (deftemplate-name &body body)
|  "
|  The deftemplate construct is used to create a template which can then
|  be used by non-ordered facts to access fields of the fact by name.
|
|  Examples:
|  (deftemplate object
|    (slot id (default-dynamic (gensym)))
|    (slot name (default ?NONE))           ; Makes name a required field
|    (slot age))
|  "
|
|  (macrolet ((signal-deftemplate-error (msg &rest args)
|               `(error (concatenate 'string "~&The deftemplate ~A contains at least one invalid slot-definition: ~S." ,msg)
|                       ,@args)))
|    (let ((comment "")
|          (defstruct-name (intern (concatenate 'string "DEFTEMPLATE/" (string deftemplate-name))))
|          (defstruct-slots '()))
|
|      ;; Extract the documentation string
|      (when (stringp (car body))
|        (setf comment (car body))
|        (setf body (cdr body)))
|
|      ;; Check syntax and extract slot-specifiers
|      (dolist (slot body)
|        (let* ((slot-name (cadr slot))
|               (curr-defstruct-slot `(,slot-name nil)))
|          (unless (eq (car slot) 'slot)
|            (signal-deftemplate-error "~&Expected SLOT instead of ~A."
|                                      deftemplate-name slot (car slot)))
|
|          (when (> (length slot) 2)
|            (dolist (default-attribute (cddr slot))
|              (unless (consp default-attribute)
|                (signal-deftemplate-error "~&Expected (default ?NONE|expression) or (default-dynamic expression) instead of ~A."
|                                          deftemplate-name slot default-attribute))
|              (unless (or (eq (car default-attribute) 'default)
|                          (eq (car default-attribute) 'default-dynamic))
|                (signal-deftemplate-error "~&Expected DEFAULT or DEFAULT-DYNAMIC instead of: ~A."
|                                          deftemplate-name slot (car default-attribute)))
|              (if (eq (car default-attribute) 'default)
|                  (if (eq (cadr default-attribute) '?NONE)
|                      (setf curr-defstruct-slot `(,slot-name (required ',slot-name ',deftemplate-name)))
|                      (setf curr-defstruct-slot `(,slot-name ',(eval (cadr default-attribute)))))
|                  (setf curr-defstruct-slot `(,slot-name ,(cadr default-attribute))))))
|
|          (setf defstruct-slots (append defstruct-slots (list curr-defstruct-slot)))))
|
|      `(progn
|         (defstruct ,defstruct-name
|           ,comment
|           ,@defstruct-slots)
|
|         (defmacro ,deftemplate-name (&rest slots)
|           ,comment
|           (call-defstruct-constructor ',defstruct-name slots))))))

and here are the functions used as helpers:

|(defun required (slot-name deftemplate-name)
|  (error "~&The slot: ~A in deftemplate: ~A requires an explicit value." slot-name deftemplate-name))
|
|(defun as-keyword (sym)
|  (intern (string-upcase sym) :keyword))
|
|(defun call-defstruct-constructor (defstruct-name &rest slots)
|  (let ((constructor (intern (concatenate 'string "MAKE-" (string defstruct-name)))))
|    (apply constructor (mapcan #'(lambda (slot)
|                                   `(,(as-keyword (car slot)) ,(cadr slot)))
|                               (car slots)))))

I should probably try to write a macro to abstract away all those (intern (concatenate 'string ...)) calls but otherwise, that's about it for deftemplate. Next up is getting all of the defrule construct working (which feels like a much tougher task).

[1] I hate that I still haven't found a good way of sharing code using Blogger. Tips and pointers are very welcome!

[2] The default and default-dynamic attributes in CLIPS take a variable number of expressions (at least according to the BNF found in the CLIPS Basic Programming Guide, Appendix H). I assume it assigns the value of the last as the default but I haven't tried. Anyway, if you want to evaluate several expressions in that place you're going to have to wrap it explicitly in a progn (effectively making it one expression).

Elvis R.I.P.

2008-08-08T15:00:00.000+02:00

Elvis, September 1, 2001 - August 8, 2008. He will be missed.

MoGo beats Myungwan Kim (8P) at US Go Congress

2008-08-08T09:10:00.008+02:00

From the AGA newsletter (via the ComputerGo mailing list):

COMPUTER BEATS PRO AT U.S. GO CONGRESS:
In a historic achievement, the MoGo computer program defeated Myungwan Kim 8P (l) Thursday afternoon by 1.5 points in a 9-stone game billed as “Humanity’s Last Stand?” “It played really well,” said Kim, who estimated MoGo’s current strength at “two or maybe three dan,” though he noted that the program – which used 800 processors, at 4.7 Ghz, 15 Teraflops on a borrowed European supercomputer – “made some 5-dan moves,” like those in the lower right-hand corner, where Moyogo took advantage of a mistake by Kim to get an early lead. “I can’t tell you how amazing this is,” David Doshay -- the SlugGo programmer who suggested the match -- told the E-Journal after the game.

“I’m shocked at the result. I really didn’t expect the computer to win in a one-hour game.” Kim easily won two blitz games with 9 stones and 11 stones and minutes and lost one with 12 stones and 15 minutes by 3.5 points. The games were played live at the U.S. Go Congress, with over 500 watching online on KGS. “I think there’s no chance on nine stones,” Kim told the EJ after the game. “It would even be difficult with eight stones. MoGo played really well; after getting a lead, every time I played aggressively, it just played safely, even when it meant sacrificing some stones. It didn’t try to maximize the win and just played the most sure way to win. It’s like a machine.”

The game generated a lot of interest and discussion about the game’s tactics and
philosophical implications. “Congratulations on making history today,” game organizer Peter Drake told both Kim and Olivier Teytaud, one of MoGo’s programmers, who participated in a brief online chat after the game. At a rare loss for words in a brief interview with the EJ after the game, Doshay wondered “How much time do we have left? We’ve improved nine stones in just a year and I suspect the next nine will fall quickly now.”

- reported by Chris Garlock

Amazing! Though, the last quote (by David Doshay) should probably be taken with a grain of salt.

[Update 2008-08-09] Apparently, David was misquoted.

A Minimal Production System

2008-08-02T18:58:00.004+02:00

I've been experimenting a bit with bits and pieces of a production system in Common Lisp for a few days now. It all started as a fun exercise in Common Lisp macrology (the idea was to convert CLIPS syntax into executable Common Lisp code) but since things have fallen into place so neatly. I thought maybe it would be worth implementing parts of CLIPS syntax and functionality. So now, the only question is: which parts to implement?

I'm not going to do anything about data types and built-in functions. I'll add support for ?variables but that's about it (no multifields and no globals) and as far as constructs go I'll manage with defrule and deftemplate (no implied/ordered facts). If it doesn't turn out to be too difficult I'll try to include connected constraints in defrule but I won't bother with slot constraints in deftemplates (types and such). I'm hoping to include all CEs but it depends on how hairy it gets.

So. What have I missed? Is there something unnecessary on the list?

[Update 2008-08-03]: Hm. I guess I forgot about a bunch of engine commands. So here goes. Assert and retract seem stupid to leave out, as does run. I'll probably be annoyed not to have facts so I guess that's in as well. Load, clear, reset and agenda feel necessary but I think I'll only work with one conflict resolution strategy (depth) though.

1, 2, 4, 8, 16, ...

2008-07-26T11:39:00.001+02:00

How far can you calculate the expansion of the series 1, 2, 4, 8, 16, 32, 64, ... in your head? And, no. You can't use pen and paper or anything.

Human-Computer 19x19 Go Showdown

2008-07-23T07:43:00.001+02:00

From the Computer-Go mailing list:

On Thursday, August 7, at 1:00 PM (Pacific time), Kim MyungWan 8p will take on MoGo, the world’s strongest computer Go program. MoGo will connect remotely from France, where it will be running on a supercomputer boasting over 3,000 processor cores. The game will be broadcast on KGS.

Sweet! I guess I'll get an answer to some questions quite a bit sooner than I expected.

AI -TV from 1984

2008-07-22T09:40:00.000+02:00

José of Programming Musings found a video with Daniel Bobrow explaining CLOS from 1987. Being somewhat of a history-geek, I really love this type of thing and I've managed to collect a few interesting links myself.

One that I can particularly recommend is Computer Chronicles: Artifical Intelligence (1984) which is a twenty minute TV show featuring, among others, John McCarthy and discusses AI in general, Expert Systems and Lisp.

Sling Blade Runner IV

2008-07-18T12:37:00.004+02:00

I've been doing some more work on my kōan, Sling Blade Runner. I've given up on the beam-stack search approach. I doubt it will improve results much. If any at all.

Instead I have spent some time on improving the extend method so that it can find more extensions. And it is becoming quite efficient in exploring the neighbourhood of any given pair of titles. Previously it was only looking for extensions between two adjacent titles in the chain but now it searches for extensions between end-points in a whole sequence of titles instead. Consider the chain [A,B,C,D,...]. Now, if there's an extension between A and C, other than, and that is longer than [B], the chain is extended with it.

This, simple, tweak makes the search slower (of course) but it also improves the lengths of almost all chains that are explored. It rarely ends up with a chain that is shorter than 235 titles and most end up longer than 250 (246 was the previous best) titles.

The longest chain found is now 265 titles:

1 THE GOSPEL
2 THE GOSPEL OF JOHN
3 JOHN Q
4 Q AND A
5 A RIVER RUNS THROUGH IT
6 IT HAPPENED AT THE WORLDS FAIR
7 FAIR GAME
8 GAME OF DEATH
9 DEATH BECOMES HER
10 HER MAJESTY MRS BROWN
11 BROWN SUGAR
12 SUGAR AND SPICE
13 SPICE WORLD
14 WORLD TRADE CENTER
15 CENTER STAGE
16 STAGE FRIGHT
17 FRIGHT NIGHT
18 NIGHT OF THE LIVING DEAD
19 DEAD BANG
20 BANG BANG YOURE DEAD
21 DEAD MAN WALKING
22 WALKING AND TALKING
23 TALKING ABOUT SEX
24 SEX AND THE OTHER MAN
25 MAN OF THE HOUSE
26 HOUSE OF DRACULA
27 DRACULA DEAD AND LOVING IT
28 IT HAPPENED ONE NIGHT
29 ONE NIGHT STAND
30 STAND IN
31 IN GODS HANDS
32 HANDS ON A HARD BODY
33 BODY AND SOUL
34 SOUL FOOD
35 FOOD OF LOVE
36 LOVE IS THE DEVIL
37 THE DEVIL RIDES OUT
38 OUT COLD
39 COLD FEVER
40 FEVER PITCH
41 PITCH BLACK
42 BLACK LIKE ME
43 ME WITHOUT YOU
44 YOU LIGHT UP MY LIFE
45 MY LIFE SO FAR
46 FAR FROM HOME THE ADVENTURES OF YELLOW DOG
47 DOG RUN
48 RUN SILENT RUN DEEP
49 DEEP BLUE
50 DEEP BLUE SEA
51 SEA OF LOVE
52 LOVE WALKED IN
53 IN OLD CALIFORNIA
54 CALIFORNIA SPLIT
55 SPLIT SECOND
56 SECOND BEST
57 BEST MEN
58 MEN WITH GUNS
59 GUNS OF THE MAGNIFICENT SEVEN
60 THE MAGNIFICENT SEVEN
61 SEVEN YEARS IN TIBET
62 TIBET CRY OF THE SNOW LION
63 LION OF THE DESERT
64 DESERT HEARTS
65 HEARTS OF DARKNESS A FILMMAKERS APOCALYPSE
66 APOCALYPSE NOW
67 NOW YOU SEE HIM NOW YOU DONT
68 DONT BOTHER TO KNOCK
69 KNOCK OFF
70 OFF THE BLACK
71 THE BLACK ANGEL
72 ANGEL EYES
73 EYES OF AN ANGEL
74 ANGEL BABY
75 BABY SECRET OF THE LOST LEGEND
76 LEGEND OF THE LOST
77 THE LOST BOYS
78 BOYS LIFE
79 LIFE OR SOMETHING LIKE IT
80 IT TAKES TWO
81 TWO MEN WENT TO WAR
82 WAR OF THE WORLDS
83 THE WORLDS FASTEST INDIAN
84 INDIAN SUMMER
85 SUMMER CATCH
86 CATCH ME IF YOU CAN
87 YOU CAN COUNT ON ME
88 ME MYSELF I
89 I WANT TO LIVE
90 LIVE FOREVER
91 FOREVER YOUNG
92 YOUNG SHERLOCK HOLMES
93 SHERLOCK HOLMES IN WASHINGTON
94 WASHINGTON SQUARE
95 SQUARE DANCE
96 DANCE WITH A STRANGER
97 STRANGER IN THE HOUSE
98 THE HOUSE OF THE DEAD
99 DEAD OF NIGHT
100 NIGHT AND THE CITY
101 THE CITY
102 CITY OF ANGELS
103 ANGELS WITH DIRTY FACES
104 FACES OF DEATH
105 DEATH WISH
106 WISH UPON A STAR
107 A STAR IS BORN
108 BORN TO BE WILD
109 WILD THINGS
110 THINGS TO COME
111 COME AND GET IT
112 IT RUNS IN THE FAMILY
113 THE FAMILY MAN
114 MAN ON FIRE
115 FIRE ON THE MOUNTAIN
116 THE MOUNTAIN MEN
117 MEN IN BLACK
118 BLACK HAWK DOWN
119 DOWN WITH LOVE
120 LOVE AND DEATH
121 DEATH WISH V THE FACE OF DEATH
122 DEATH SHIP
123 SHIP OF FOOLS
124 FOOLS RUSH IN
125 IN THE WINTER DARK
126 DARK STAR
127 STAR TREK IV THE VOYAGE HOME
128 HOME ALONE
129 ALONE IN THE DARK
130 DARK BLUE
131 BLUE CAR
132 CAR 54 WHERE ARE YOU
133 YOU CANT TAKE IT WITH YOU
134 YOU ONLY LIVE ONCE
135 ONCE IN THE LIFE
136 LIFE AS A HOUSE
137 HOUSE PARTY
138 HOUSE PARTY 3
139 3 NINJAS
140 3 NINJAS KNUCKLE UP
141 UP CLOSE AND PERSONAL
142 PERSONAL BEST
143 BEST OF THE BEST
144 BEST OF THE BEST 3 NO TURNING BACK
145 NO TURNING BACK
146 BACK TO SCHOOL
147 SCHOOL OF ROCK
148 ROCK STAR
149 STAR TREK THE MOTION PICTURE
150 PICTURE BRIDE
151 BRIDE OF THE MONSTER
152 MONSTER HOUSE
153 HOUSE OF FRANKENSTEIN
154 FRANKENSTEIN AND THE MONSTER FROM HELL
155 FROM HELL
156 HELL UP IN HARLEM
157 HARLEM RIVER DRIVE
158 DRIVE ME CRAZY
159 CRAZY AS HELL
160 HELL NIGHT
161 NIGHT FALLS ON MANHATTAN
162 MANHATTAN MURDER MYSTERY
163 MYSTERY ALASKA
164 ALASKA SPIRIT OF THE WILD
165 THE WILD
166 THE WILD ONE
167 ONE NIGHT WITH THE KING
168 THE KING AND I
169 I SPY
170 SPY HARD
171 HARD EIGHT
172 EIGHT MEN OUT
173 OUT OF THE BLUE
174 BLUE SKY
175 SKY HIGH
176 HIGH CRIMES
177 CRIMES OF PASSION
178 PASSION IN THE DESERT
179 DESERT BLUE
180 BLUE STEEL
181 STEEL DAWN
182 DAWN OF THE DEAD
183 THE DEAD
184 DEAD MAN ON CAMPUS
185 CAMPUS MAN
186 MAN TROUBLE
187 TROUBLE EVERY DAY
188 DAY OF THE WOMAN
189 THE WOMAN IN RED
190 RED EYE
191 EYE FOR AN EYE
192 EYE OF GOD
193 GOD TOLD ME TO
194 TO DIE FOR
195 FOR THE BOYS
196 THE BOYS
197 BOYS AND GIRLS
198 GIRLS WILL BE GIRLS
199 GIRLS GIRLS GIRLS
200 GIRLS OF SUMMER
201 SUMMER LOVERS
202 LOVERS AND OTHER STRANGERS
203 STRANGERS WHEN WE MEET
204 MEET JOE BLACK
205 BLACK AND WHITE
206 WHITE HUNTER BLACK HEART
207 HEART CONDITION
208 CONDITION RED
209 RED RIVER
210 RIVER OF NO RETURN
211 RETURN OF THE FLY
212 FLY AWAY HOME
213 HOME ALONE 2 LOST IN NEW YORK
214 NEW YORK NEW YORK
215 NEW YORK COP
216 COP LAND
217 LAND OF THE DEAD
218 DEAD END
219 END OF DAYS
220 DAYS OF HEAVEN
221 HEAVEN CAN WAIT
222 WAIT UNTIL DARK
223 DARK CITY
224 CITY OF JOY
225 JOY RIDE
226 RIDE THE HIGH COUNTRY
227 COUNTRY LIFE
228 LIFE WITH FATHER
229 FATHER OF THE BRIDE
230 BRIDE OF THE WIND
231 THE WIND AND THE LION
232 THE LION KING
233 KING OF THE JUNGLE
234 THE JUNGLE BOOK
235 JUNGLE BOOK
236 BOOK OF LOVE
237 LOVE LIFE
238 LIFE IS BEAUTIFUL
239 BEAUTIFUL PEOPLE
240 PEOPLE I KNOW
241 I KNOW WHERE IM GOING
242 IM GOING HOME
243 HOME ALONE 3
244 3 NINJAS KICK BACK
245 BACK TO THE BEACH
246 BEACH PARTY
247 PARTY MONSTER
248 MONSTER IN A BOX
249 BOX OF MOON LIGHT
250 LIGHT OF DAY
251 DAY FOR NIGHT
252 NIGHT MOTHER
253 MOTHER NIGHT
254 NIGHT ON EARTH
255 EARTH GIRLS ARE EASY
256 EASY MONEY
257 MONEY FOR NOTHING
258 NOTHING BUT TROUBLE
259 TROUBLE IN PARADISE
260 PARADISE ROAD
261 ROAD HOUSE
262 HOUSE PARTY 2
263 2 DAYS IN THE VALLEY
264 VALLEY GIRL
265 GIRL WITH A PEARL EARRING

The results vary a bit depending on search depth (not that surprising really) so there may still be some possible improvements by just modifying parameters.

[Update 2008-07-20] The longest chain found is now 268 titles long.

Using printout and readline in PyCLIPS applications

2008-07-14T09:00:00.004+02:00

I am trying to help a CLIPS user compile his application into a Windows executable (.exe) by following the description in one of my previous blog posts. But his application relies on the built in functions read and printout. And my blog post says nothing about that type of situation since all of the times I've done this before have been with applications that have GUIs and I've never had to bother with command line interaction.

The problem is, more specifically, that PyCLIPS consumes all calls to printout and read without printing to screen or requiring any user input. This may seem like a stupid design decision at first, but if you consider the many situations and environments that PyCLIPS can run in. It starts to feel like a rather sensible approach since it's obviously impossible to know what the right thing to do is. If you need user interaction via command line, you can provide Python functions that perform I/O for you.

So. Just to be clear. PyCLIPS does not constrain the possibilities for interaction with CLIPS in any way. It just doesn't make any assumptions about how it should best be done.

Ok. Fair enough. But, what to do?

First off. I don't want to have to maintain different versions of the application just to perform I/O. I need a way to dynamically dispatch I/O to either the built in functions (if it's run in CLIPS Dialog) or to my Python functions (if it's run in PyCLIPS).

Here is a simple application that uses printout and read:

|(deffacts start
|  (sum 0))
|
|(defrule calc-sum
|  ?sum <- (sum ?s)
|  =>
|  (retract ?sum)
|  (printout t "Enter a number or Q to quit: ")
|  (bind ?input (read))
|  (if (numberp ?input)
|   then (bind ?s (+ ?s ?input))
|        (assert (sum ?s))
|   else (if (or (eq ?input q)
|                (eq ?input Q))
|         then (printout t "Sum = " ?s crlf)
|         else (printout t "Invalid input: " ?input crlf)
|              (assert (sum ?s)))))

It works like this:

CLIPS> (load "sum.clp")
!!!$*
TRUE
CLIPS> (reset)
CLIPS> (run)
Enter a number or Q to quit: one
Invalid input: one
Enter a number or Q to quit: 9
Enter a number or Q to quit: 8
Enter a number or Q to quit: 5
Enter a number or Q to quit: Q
Sum = 22

When I first thought about how to make this program run (with as little effort as possible) in PyCLIPS, I didn't think that it would be very difficult. I was actually quite certain I'd be able to monkey-patch PyCLIPS with my I/O functions. CLIPS, however, was far from impressed with my attempt. So, a slap on the wrist later, I settled on (manually) replacing all function calls to printout, readline and read to deffunction wrappers (printout1, readline1 and read1) instead.

Here are the CLIPS deffunctions:

|(deffunction printout1 (?logical-name $?args)
|  (if (member$ python-call (get-function-list))
|   then (funcall python-call pyprintout ?logical-name $?args)
|   else (progn$ (?arg $?args)
|          (printout ?logical-name ?arg))))
|
|(deffunction readline1 ($?logical-name)
|  (if (> (length$ $?logical-name) 0)
|   then (bind ?logical-name (first$ $?logical-name))
|   else (bind ?logical-name t))
|
|  (if (member$ python-call (get-function-list))
|   then (funcall python-call pyreadline ?logical-name)
|   else (readline ?logical-name)))
|
|(deffunction read1 ($?logical-name)
|  (if (> (length$ $?logical-name) 0)
|   then (bind ?logical-name (first$ $?logical-name))
|   else (bind ?logical-name t))
|
|  (if (member$ python-call (get-function-list))
|   then (eval (funcall python-call pyread ?logical-name))
|   else (read ?logical-name)))

They look quite hairy. I know. But they're generic so it's not something you'd have to write and modify for each application that you want to be able to run in both CLIPS and PyCLIPS. There's also some Python boiler plate. It looks like this:

|import clips
|
|def pyprintout(*args):
|  for arg in args[1]:
|    if arg.cltypename().upper() == "SYMBOL":
|      if arg.upper() == "CRLF":
|        print
|      elif arg.upper() == "TAB":
|        print "\t",
|      else:
|        print arg,
|
|    else:
|      print arg,
|
|def pyreadline(*args):
|  return raw_input()
|
|def pyread(*args):
|  return raw_input()
|
|clips.RegisterPythonFunction(pyprintout)
|clips.RegisterPythonFunction(pyreadline)
|clips.RegisterPythonFunction(pyread)

Once we've got all of the above in place. We can load, reset and run from within a PyCLIPS script and have the application work directly in the Windows command line.

C:\...>python sum.py
Enter a number or Q to quit:  one
Invalid input:  one
Enter a number or Q to quit:  9
Enter a number or Q to quit:  8
Enter a number or Q to quit:  5
Enter a number or Q to quit:  Q
Sum =  22

C:\...>

The files sum.py and sum.clp contain the whole application if you're interested. The point of all this is of course to be able to compile the PyCLIPS application into an executable. Step for step instructions on how to do that can be found here.

[Update 2008-07-14] I just fixed the pyprintout function (in sum.py), so that it also prints symbols. The code I added is marked with red.

Common Lisp Reasoner

2008-07-11T08:23:00.000+02:00

I just found the SourceForge project Common Lisp Reasoner. It's a CLOS extension for AI applications like scheduling and diagnosis. I haven't had time to check it out, but it looks interesting. I wonder if it plays nicely with other CLOS extensions, like the production system Lisa for example.

What would you do with a thousand cores?

2008-07-10T08:00:00.001+02:00

Anwar Ghuloum's post Unwelcome advice has caused a bit of a stir recently. Probably not in the way he wanted though. The comments are full of questions and doubts about whether they (Intel) can back up their claims of soon-to-come-thousands-of-cores-processors. And, more importantly, if they *can* - programming in itself will be very different from how we do it today so it's meaningless to think about it in terms of how it's done now.

But, regardless of all that... More than a thousand cores in a single processor. What would *you* do with that? One area that I think looks particularly promising is Computer Go. That many cores may well be the tipping point of AI players in Go. Will they finally be able to move up into the (professional) Dan levels?

In the upcoming tournament at the European Go Congress (in Leksand, Sweden) they're provding hardware with 2 cores. If we ignore practical scaling problems for a minute, what would the effect of an additional 998 cores be? Many of the top players today (like MoGo and CrazyStone) rely on "easily" parallellizable statistical methods (see UCT and Monte Carlo methods for more info). And the more playouts you can perform within a given time the better the resulting play. At least in theory.

I may well be underestimating the problem. I know. But it would be very interesting to see how much of an improvement can be made by just adding more raw power.

My birthday

2008-07-06T22:22:00.001+02:00

If you're geeky and you know it, clap your hands.

Sling Blade Runner III

2008-07-02T11:35:00.008+02:00

Continuing work on my Sling Blade Runner solution has led me to improve the search algorithm a bit further. Instead of looking for good starting-points for a search, it now looks for good mid-points and searches both forwards and backwards. This should, in theory, be a better way to do it and it does improve the average length of chains. But it turns out that it doesn't make *that* big a difference on the longest one (roughly 10 titles). The longest chain found is now 246 titles long.

1 THE PRICE OF MILK
2 MILK AND HONEY
3 HONEY I BLEW UP THE KID
4 THE KID
5 THE KID AND I
6 I WENT DOWN
7 DOWN TO YOU
8 YOU ONLY LIVE ONCE
9 ONCE AROUND
10 AROUND THE BEND
11 BEND OF THE RIVER
12 THE RIVER
13 THE RIVER WILD
14 WILD THINGS
15 THINGS TO COME
16 COME AND GET IT
17 IT TAKES TWO
18 TWO EVIL EYES
19 EYES OF AN ANGEL
20 ANGEL HEART
21 HEART CONDITION
22 CONDITION RED
23 RED RIVER
24 RIVER OF NO RETURN
25 RETURN TO HORROR HIGH
26 HIGH SCHOOL HIGH
27 HIGH CRIMES
28 CRIMES OF PASSION
29 PASSION IN THE DESERT
30 DESERT HEARTS
31 HEARTS OF DARKNESS A FILMMAKERS APOCALYPSE
32 APOCALYPSE NOW
33 NOW YOU SEE HIM NOW YOU DONT
34 DONT BOTHER TO KNOCK
35 KNOCK OFF
36 OFF THE BLACK
37 THE BLACK ANGEL
38 ANGEL BABY
39 BABY SECRET OF THE LOST LEGEND
40 LEGEND OF THE LOST
41 THE LOST BOYS
42 BOYS AND GIRLS
43 GIRLS JUST WANT TO HAVE FUN
44 FUN AND FANCY FREE
45 FREE WILLY
46 FREE WILLY 2 THE ADVENTURE HOME
47 HOME ALONE 3
48 3 NINJAS
49 3 NINJAS KNUCKLE UP
50 UP CLOSE AND PERSONAL
51 PERSONAL BEST
52 BEST OF THE BEST
53 BEST OF THE BEST 3 NO TURNING BACK
54 NO TURNING BACK
55 BACK STAGE
56 STAGE FRIGHT
57 FRIGHT NIGHT
58 NIGHT MOTHER
59 MOTHER NIGHT
60 NIGHT FALLS ON MANHATTAN
61 MANHATTAN MURDER MYSTERY
62 MYSTERY ALASKA
63 ALASKA SPIRIT OF THE WILD
64 THE WILD
65 THE WILD ONE
66 ONE NIGHT WITH THE KING
67 THE KING AND I
68 I NEVER PROMISED YOU A ROSE GARDEN
69 GARDEN STATE
70 STATE FAIR
71 FAIR GAME
72 GAME OF DEATH
73 DEATH WISH V THE FACE OF DEATH
74 DEATH SHIP
75 SHIP OF FOOLS
76 FOOLS RUSH IN
77 IN PRAISE OF OLDER WOMEN
78 WOMEN IN LOVE
79 IN LOVE AND WAR
80 WAR OF THE WORLDS
81 THE WORLDS FASTEST INDIAN
82 INDIAN SUMMER
83 SUMMER CATCH
84 CATCH A FIRE
85 FIRE ON THE MOUNTAIN
86 THE MOUNTAIN MEN
87 MEN WITH GUNS
88 GUNS OF THE MAGNIFICENT SEVEN
89 THE MAGNIFICENT SEVEN RIDE
90 RIDE WITH THE DEVIL
91 THE DEVIL RIDES OUT
92 OUT COLD
93 COLD FEVER
94 FEVER PITCH
95 PITCH BLACK
96 BLACK AND WHITE
97 WHITE WATER SUMMER
98 SUMMER LOVERS
99 LOVERS AND OTHER STRANGERS
100 STRANGERS WHEN WE MEET
101 MEET JOE BLACK
102 BLACK HAWK DOWN
103 DOWN WITH LOVE
104 LOVE LIFE
105 LIFE IS BEAUTIFUL
106 BEAUTIFUL GIRLS
107 GIRLS GIRLS GIRLS
108 GIRLS WILL BE GIRLS
109 GIRLS TOWN
110 TOWN AND COUNTRY
111 COUNTRY LIFE
112 LIFE WITH FATHER
113 FATHER OF THE BRIDE
114 BRIDE OF THE WIND
115 THE WIND AND THE LION
116 THE LION KING
117 KING OF THE JUNGLE
118 THE JUNGLE BOOK
119 JUNGLE BOOK
120 BOOK OF LOVE
121 LOVE CRAZY
122 CRAZY AS HELL
123 HELL NIGHT
124 NIGHT ON EARTH
125 EARTH GIRLS ARE EASY
126 EASY MONEY
127 MONEY FOR NOTHING
128 NOTHING BUT TROUBLE
129 TROUBLE EVERY DAY
130 DAY FOR NIGHT
131 NIGHT OF THE LIVING DEAD
132 DEAD MAN
133 DEAD MAN WALKING
134 WALKING AND TALKING
135 TALKING ABOUT SEX
136 SEX AND THE OTHER MAN
137 MAN OF THE HOUSE
138 THE HOUSE OF THE DEAD
139 DEAD END
140 END OF DAYS
141 DAYS OF HEAVEN
142 HEAVEN CAN WAIT
143 WAIT UNTIL DARK
144 DARK STAR
145 STAR WARS EPISODE V THE EMPIRE STRIKES BACK
146 BACK TO THE BEACH
147 THE BEACH
148 BEACH PARTY
149 PARTY MONSTER
150 MONSTER HOUSE
151 HOUSE OF DRACULA
152 DRACULA DEAD AND LOVING IT
153 IT HAD TO BE YOU
154 YOU LIGHT UP MY LIFE
155 MY LIFE
156 LIFE OR SOMETHING LIKE IT
157 IT HAPPENED ONE NIGHT
158 ONE NIGHT STAND
159 STAND IN
160 IN THE HEAT OF THE NIGHT
161 NIGHT AND THE CITY
162 THE CITY
163 CITY BY THE SEA
164 SEA OF LOVE
165 LOVE WALKED IN
166 IN THE COMPANY OF MEN
167 MEN IN BLACK
168 BLACK LIKE ME
169 ME MYSELF I
170 I WANT TO LIVE
171 LIVE AND LET DIE
172 DIE MONSTER DIE
173 DIE MOMMIE DIE
174 DIE ANOTHER DAY
175 DAY OF THE DEAD
176 THE DEAD
177 DEAD OF NIGHT
178 NIGHT AND DAY
179 DAY OF THE WOMAN
180 THE WOMAN IN RED
181 RED EYE
182 EYE FOR AN EYE
183 AN EYE FOR AN EYE
184 EYE OF GOD
185 GOD TOLD ME TO
186 TO DIE FOR
187 FOR THE BOYS
188 THE BOYS
189 BOYS LIFE
190 LIFE AS A HOUSE
191 HOUSE OF FRANKENSTEIN
192 FRANKENSTEIN MEETS THE WOLF MAN
193 THE WOLF MAN
194 MAN TROUBLE
195 TROUBLE IN PARADISE
196 PARADISE ROAD
197 ROAD HOUSE
198 HOUSE PARTY
199 HOUSE PARTY 3
200 3 NINJAS KICK BACK
201 BACK TO SCHOOL
202 SCHOOL OF ROCK
203 ROCK STAR
204 STAR TREK IV THE VOYAGE HOME
205 HOME ALONE
206 ALONE IN THE DARK
207 DARK BLUE
208 BLUE CAR
209 CAR 54 WHERE ARE YOU
210 YOU CANT TAKE IT WITH YOU
211 YOU CAN COUNT ON ME
212 ME WITHOUT YOU
213 YOU SO CRAZY
214 CRAZY PEOPLE
215 PEOPLE WILL TALK
216 TALK OF ANGELS
217 ANGELS WITH DIRTY FACES
218 FACES OF DEATH
219 DEATH WISH
220 WISH UPON A STAR
221 A STAR IS BORN
222 BORN AMERICAN
223 AMERICAN DREAM
224 DREAM A LITTLE DREAM
225 DREAM MAN
226 MAN ON FIRE
227 FIRE IN THE SKY
228 SKY HIGH
229 HIGH SPIRITS
230 SPIRITS OF THE DEAD
231 DEAD BANG
232 BANG BANG YOURE DEAD
233 DEAD HEAT
234 HEAT AND DUST
235 DUST TO GLORY
236 GLORY ROAD
237 ROAD GAMES
238 GAMES PEOPLE PLAY NEW YORK
239 NEW YORK NEW YORK
240 NEW YORK COP
241 COP LAND
242 LAND OF THE DEAD
243 DEAD MAN ON CAMPUS
244 CAMPUS MAN
245 MAN ON THE MOON
246 MOON OVER PARADOR
Time: 00:49:32

This is still just a simple best-first search and I still have high hopes for a ~~beam search~~ beam-stack search to do a lot better.

[Correction 2008-07-02]: When I say beam search I mean beam-stack search.

Sling Blade Runner II

2008-06-23T22:34:00.006+02:00

In an effort to understand my heuristic's performance better I've compared the chains created by icefox's (312 titles) and my program (225 titles). Interestingly enough I've found several "gaps" in my chain that really shouldn't be there. Below is a snippet of icefox's chain (the number specifies the title's position in my chain):

219 ROAD GAMES
220 GAMES PEOPLE PLAY NEW YORK
--- NEW YORK NEW YORK
221 NEW YORK COP
222 COP LAND

New York Cop has a subtree of size 7 and since New York New York's subtree is only 6 titles in size, New York Cop will always be selected by my heuristic function. But apparently there's a blind spot in my find/extend function that makes it skip New York New York even though it's not used in my chain (indicated by ---). Terribly annoying.

[Update 2008-06-25]: Now that I've "fixed" (I changed a constant from 2 to 1 ;-) the code, the longest chain found is 233 titles. A small improvement, but still. Here's the list with the titles that have been added (the number specifies the title's position in my 225-length chain):

...
036 IT HAD TO BE YOU
--- YOU CANT TAKE IT WITH YOU
037 YOU CAN COUNT ON ME
038 ME MYSELF I
039 I LOVE YOU TO DEATH
--- DEATH WISH V THE FACE OF DEATH
040 DEATH WISH
...
077 ALASKA SPIRIT OF THE WILD
--- THE WILD
078 THE WILD ONE
...
082 LIVE AND LET DIE
--- DIE MONSTER DIE
083 DIE MOMMIE DIE
...
089 DEATH WISH 3
--- 3 NINJAS
090 3 NINJAS KNUCKLE UP
...
101 EYE FOR AN EYE
--- AN EYE FOR AN EYE
102 EYE OF GOD
...
120 THE JUNGLE BOOK
--- JUNGLE BOOK
121 BOOK OF LOVE
...
220 GAMES PEOPLE PLAY NEW YORK
--- NEW YORK NEW YORK
221 NEW YORK COP
...

[Update 2008-06-26]: Modifying a few parameters creates a chain with 237 titles.

Make a Peace-toy

2008-06-23T10:46:00.001+02:00

The Stockholm local group of the Swedish Peace and Arbitration Society (SPAS) has arranged a contest in designing "peace-toys". It's a very interesting idea, and a rather difficult one if you ask me, since peace is almost always defined negatively (i.e. peace is the absence of war). It will be very interesting to see what people come up with.

I suggested to Sofia that we should design a variant of the classic board game Risk modified to use non-violent techniques of conflict management. Obviously the game's ultimate goal cannot be world domination and it can't be something, like world democratization, where everyone is a winner either. It's probably going to be very difficult just to figure out the basis for the game. I haven't spent enough time thinking about it and I don't have much hope of participating since the deadline is 1/9 and I don't think Sofia and I will have much time to spend on it during summer but maybe if it rains a lot. Let's hope so ;-)

Testing CLIPS applications with TextTest

2008-06-18T22:56:00.000+02:00

I was recently re-introduced to TextTest - a tool for text-based functional testing. TextTest uses the same approach as is used to test CLIPS functionality and that has been suggested several times on the CLIPSESG mailing list for unit-testing CLIPS applications.

The benefits of using TextTest for your CLIPS testing is that you can automate the execution of the tests and that you get a nice summary of the differences between expected output and actual output. So if you're currently testing your application "manually" using the CLIPS Dialog window and a diff tool you should give TextTest a try. It may well save you some time.

Roots of Lisp II

2008-06-14T09:00:00.000+02:00

Since I wrote the post about Paul Graham's article Roots of Lisp about two weeks ago I've been searching for similar efforts to read, learn from and basically - steal. And I've got to say. There are some pretty impressive stuff out there.

Ur-Scheme is a self-hosting partial implementation of R5RS that runs on Intel x86 Linux.

The 90 minute Scheme to C compiler which is a presentation of how to write your own Scheme compiler (it takes 90 minutes to present, not to write the compiler).

The icbins Lisp to C compiler and interpreter in 10 pages of C by Darius Bacon. He's written an even smaller one (6 pages) but which doesn't include the interpreter.

Out of the three I suspect that icbins is what comes closest to answering my question (what kind of boiler-plate code would be required to support such an implementation) though I believe that it is written to support more (probably much more) than what is described in Graham's article or in the Lisp 1.5 Programmer's Manual.

Switching jobs

2008-06-11T15:02:00.002+02:00

After summer I'm going to start working for Nordea IT instead of Nordea Life & Pensions. It's a big change in many ways (new business area, new systems) and a very small one in others (same cubicle, same coffee machine, same people to go to lunch with).

Creating an .exe for a CLIPS application

2008-06-06T20:22:00.002+02:00

Every now and then someone (on CLIPSESG) asks about how to create a standalone binary (usually a Windows .exe) for a CLIPS application they wrote. The process for doing so is described in Section 5 of the CLIPS Advanced Programming Guide. But even though that may be the correct answer to such questions it isn't always what the poster wants to hear. At least that's the impression I get.

The problem is (probably, I'm guessing here), that the description is kind of brief, contains little or no examples and is written for an experienced (or at least decent) C programmer. Which, unfortunately, kind of misses the mark since it seems that most people that ask about how to create .exe files for their applications are (relatively) new programmers and probably feel a bit lost reading that section. I know I do.

Though I can see several reasons why distributing your CLIPS application as a binary file (in any format) is a bad idea. I also know that sometimes it's the only way, so I'm not going to question your motives or try to talk you out of it. Instead. Here is a step-for-step demonstration on how to do it using PyCLIPS.

Step 0. Know the difference.
I'm not sure whether or not the steps described in CLIPS APG Section 5 results in a binary that includes the CLIPS IDE (the Dialog window and other useful things). But what I am describing here does not! So if you rely on user input at runtime you're also going to have to create a GUI for your application. I've written about that before and all of those examples are also available as PyCLIPS downloads.

Step 1: Install the tools.
The first thing you need to to do is to get all of the tools needed. You're going to have to download and install Python, PyCLIPS and py2exe. If you also need a GUI or want to try either of the wxPython CLIPS demos you should get wxPython. Make sure to get the latest version of Python (2.5.2 as I'm writing this) and releases matching it (2.5) for the other projects. Installation should be very simple since all projects provide binaries and the installers pretty much take care of themselves.

When you're done with all of the installations you can make sure that everything went alright by opening up IDLE (it should be in your start menu) and try the following:

>>> import clips
>>> import py2exe
>>> import wx

If either of those raises an exception you're going to have to re-install. Installation instructions and trouble-shooting guidance can be found on the projects' websites and in their docs.

Step 2: Wrap your application in PyCLIPS.
Once you've got all the tools in place it's time to write a wrapper for your CLIPS application. I'll use the sudoku demo (sudoku.clp and solve.clp) as base for my example application.

I'll wrap it in a Python program that reads a file as input (containing an unsolved sudoku puzzle), triggers the CLIPS program to solve the puzzle, queries CLIPS for the answer and writes the solution to stdout.

The program is in essence a copy of the on_openfile and on_solve functions from the wxPython demo so I've copy-pasted most of it. You can download a .zip with the code here.

Step 3: Write a setup.py script.
The py2exe website has tutorials and examples on how to best use it so I'll be quite brief here.

In order to compile a Python program/script into a standalone Windows executable you're going to have write a small configuration file (setup.py) which specifies the options py2exe should work with. Py2exe is an extension to distutils so you should read those docs as well.

The setup.py which I'll use looks like this:

from distutils.core import setup
import py2exe

setup(console=['sudoku.py'], data_files=[('', ['sudoku.clp', 'solve.clp'])])

there are a lot more options available but since this is more of a teaser (or a shameless plug for Python and PyCLIPS depending on how you look at it) I'll let you look into that yourself.

Step 4: Compile the application.
All we need to do to generate the .exe is to run the setup.py script in a command prompt:

C:\Program\...\py2exe-demo>setup.py py2exe
running py2exe
...
*** copy data files ***
copying C:\Python25\lib\site-packages\py2exe\run.exe -> C:\Program\...\py2exe-demo\dist\sudoku.exe

*** binary dependencies ***
Your executable(s) also depend on these dlls which are not included,
you may or may not need to distribute them.

Make sure you have the license if you distribute any of them, and
make sure you don't distribute files belonging to the operating system.

ADVAPI32.dll - C:\WINDOWS\system32\ADVAPI32.dll
USER32.dll - C:\WINDOWS\system32\USER32.dll
SHELL32.dll - C:\WINDOWS\system32\SHELL32.dll
KERNEL32.dll - C:\WINDOWS\system32\KERNEL32.dll
msvcrt.dll - C:\WINDOWS\system32\msvcrt.dll

C:\Program\...\py2exe-demo>cd dist
C:\Program\...\py2exe-demo\dist>sudoku.exe ..\Game03.txt
5 9 7 8 3 4 1 2 6
2 6 8 9 1 5 7 3 4
3 1 4 7 2 6 5 8 9
8 7 3 2 4 1 9 6 5
9 2 5 6 7 3 4 1 8
1 4 6 5 8 9 2 7 3
4 5 2 1 6 8 3 9 7
7 8 9 3 5 2 6 4 1
6 3 1 4 9 7 8 5 2

Seems to work. But listing the contents of the dist directory might make you a bit disappointed:

C:\Program\...\py2exe-demo\dist>dir
...
2006-09-19  09:52            77 824 bz2.pyd
2008-06-04  19:42         1 034 699 library.zip
2006-03-16  16:19           348 160 MSVCR71.dll
2006-09-19  09:52         2 109 440 python25.dll
2008-01-18  21:08            39 997 solve.clp
2008-01-18  21:08             5 036 sudoku.clp
2008-06-04  19:42            18 944 sudoku.exe
2006-09-19  09:52           475 136 unicodedata.pyd
2006-09-19  09:52             4 608 w9xpopen.exe
2008-03-09  04:29         1 009 152 _clips.pyd
...

Neither of the .clp files have been compiled!

If the purpose of generating the .exe is to hide implementation details, such as the CLIPS program, then you're going to have to convert the .clp files into PyCLIPS programs. It's easy enough to do, but it's boring.

You have to go through each .clp file and
1) Either remove all comments or convert them into Python comments (use # instead of ;).
2) Indent all lines in the file with 4 spaces.
3) Insert import clips as the first line.
4) Insert def load(): as the second line.
5) Wrap all definitions with a clips.Build(""" ... """).
6) Rename the file to [filename]_clp.py.

After doing that you can remove the data_files option in setup.py and modify a few lines in sudoku.py. If we change:

clips.Load("sudoku.clp")
clips.Load("solve.clp")

import sudoku_clp, solve_clp
sudoku_clp.load()
solve_clp.load()

and run the compilation again, the problem is "fixed". Since all of the CLIPS constructs are now embedded in Python files they will be sucked into the .exe. The "fixed" code is available here.

The steps outlined above might at least be an alternative for those of us that aren't that well-versed in C/C++. I'm sure that the same, or at least something similar, can be done with other tools and languages - but that's for someone else to write about.

The code I've used as the example ought to be pretty simple to understand, but if you have any questions or if you think I've been too brief at some point, leave a comment or send me an e-mail and we'll sort it out.

Eowyn's first birthday

2008-06-02T21:30:00.003+02:00

Eowyn and cousin Nora + granddad in the background.

Sofia and Eowyn.

Today is Eowyn's first birthday and we've celebrated it (twice) during the weekend. The weather's been great for about a week so we had both birthday parties outside with (almost) all of our relatives visiting. Eo got lots of great presents and seemed to enjoy the attention.

Granddad, grandmom, some aunts, an uncle, a few cousins, me and Eowyn sitting in the middle.

Roots of Lisp

2008-05-28T17:00:00.001+02:00

The first time I read Paul Graham's article The Roots of Lisp was a couple of years ago. I remember thinking that it's cool that Lisp can be defined in itself using only seven functions (quote, atom, eq, cons, car, cdr and cond) but it's even more interesting to think about what kind of boiler-plate code would be required to support such an implementation. I mean, it's not like McCarthy and the others had a high-level language available when they wrote the first Lisp interpreter.

Yesterday I stumbled on the Software Preservation Group's History of Lisp-page. It contains a lot of information about those first steps in Lisp history. One of many interesting things to read about is Pascal Bourguignon's work on getting the first Lisp compiler (written in 1962) running on an IBM 7090 emulator.

Whilst Pascal's project is indeed impressive work and interesting in many ways it would be even more interesting to do something similar using GCC in order to get a minimal Lisp interpreter. And I mean really minimal. For instance, complicated things to parse such as (foo bar baz) won't be supported, a minimal parser would require you to write (foo . (bar . (baz . ()))). But since that's just the first layer in the implementation we could write a new reader using our minimal Lisp. One that would support, among other things, parsing lists as we'd usually write them.

I wonder if the same seven functions will be sufficient to pull that off or if it turns out to require more things. Unfortunately I haven't got the time to find out. I'll just keep reading the available historical material and keep hoping for someone else to step up for this experiment ;-)

Domain Specific Languages and XML

2008-05-23T09:00:00.003+02:00

A couple of days ago Pascal Costanza wrote an interesting reply to Martin Fowler's post ParserFear. Like Pascal, I think Martin misses the point, and I agree that the problem is not that it's difficult to implement a DSL. The problem is that the bang/buck ratio favors other solutions (usually XML). But, I'd also like to point out that even when a DSL would prove useful it's still not enough to go and design your own language.

Creating a DSL from scratch is very likely to be, mostly, a duplication of effort. And it ought to be very difficult to justify the cost of that effort considering that there are so many well-designed, easily embedded, languages already. I'm thinking about languages like Python, Ruby and JavaScript to mention a few.

Don't get me wrong. I am a fan of the DSL approach (I try to stay away from XML whenever I can) but I think that it's a bit much to go to such lengths to create custom syntax instead of looking for a decent match in existing languages.

Even in situations where an XML parser is clearly sufficient, I find it better to expose a subset of an existing programming language (usually Python) to the users instead. That way I can grow the capabilities of the language easily and I can re-use all of the resources available (IDE plug-ins, tools, tutorials and other documentation) when instructing users.

The approach is similar to, or maybe exactly the same as, how Martin describes creating a DSL around a Semantic Model. The difference is that I use reflection to populate the model instead of a custom parser. I've found that this works really well with a language like Python. It's usually a lot less code than maintaining ANTLR grammar files or XML schemas/parsers and I think it usually ends up being a lot more understandable. But I guess it's really a matter of taste. You say tomato, I say tomato and all that.

NotNode woes

2008-05-20T10:41:00.002+02:00

Since the rewrite of the RuleCompiler I've been making good progress at good speed with PyRete. It might appear different to the casual observer but the reason it's taking so long to get even an alpha release out is because I've only got about an hour or two a week to spend.

Anyway, last week I spent my hours trying to add support for the NotNode. And, instead of thinking ahead, I implemented it, more or less, exactly in the same faulty manner as I did last time. Which didn't work, I might add. I knew it! But somehow, I kept hoping that changes I had made somewhere else would automagically clean up things here as well. Stupid! Stupid! Stupid!

So, now I've got a RuleCompiler that works as long as the Not-CE contains no more than one Pattern-CE. So Not(Foo(bar == var)) works fine but Not(Foo(bar == var) and Not(Bar(foo == var))) won't compile. Well. It compiles. It's just that it won't result in a correct, usable structure.

The problem is that my approach tries to tack on some state-flags to bits and pieces in the compilation process. But since the Python AST visitor uses a callback interface it's difficult (not impossible) to store state between calls. The more complex the expression being parsed the closer to insanity I get.

The easier solution, and probably the more correct one as well, is to treat whatever is within the Not-CE as a Rete Network in itself. Once compilation is done I rip out the ProductionNode from it and replace it with a NotNode (where the sub-network feeds from the right) and join it to the main network (feeding from the left).

That requires some small changes in my current implementation, but once I get it to support recursive use it's going to work with both Exists-CE and Forall-CE without me having to add an increasingly complex structure for storing state. But, then again. I knew that already! I even knew that before I started working on it. I just didn't believe it would turn out so bad this time. So, I'll spend the rest of the day kicking myself and then it's back to work. Doing it over, but right this time.

Why I love Python

2008-05-14T09:00:00.000+02:00

Two days ago I attended the first GothPy meeting here in Gothenburg. Jeppesen was kind enough to let us use one of their conference rooms for the meeting. About ten people showed up to listen to Andrew's PyCon 2007 talk about Stackless Python and to work on the BankOCR code kata.

The kata was very interesting. It was my first and I was dead certain we'd end up fighting about IDE's or whether function names should be likeThis or like_this, but everyone was very polite and helpful. Funny thing though. When we planned the meeting, Emily insisted that we should bring a computer that is not-a-Mac, preferably a Windows PC. About two minutes into the meeting there are at least six Macs on the table and I only counted to seven computers in total. But apart from the fact that no one could get along with the keyboard, the PyDev/Eclipse editor and that the unit test results where printed in red regardless of whether they failed or succeded everything went fine using a Windows-machine ;-)

We actually managed to get further than I thought we would during the kata. The last piece of code we wrote was the validation part (User story #2)

... The next step therefore is to validate that the numbers you read are in fact valid account numbers. A valid account number has a valid checksum. This can be calculated as follows:
account number:  3  4  5  8  8  2  8  6  5
position names:  d9 d8 d7 d6 d5 d4 d3 d2 d1

checksum calculation:
(d1+2*d2+3*d3 +..+9*d9) mod 11 = 0
So now you should also write some code that calculates the checksum for a given number, and identifies if it is a valid account number.

We made three different versions of the is_valid method. Jacob, who had the keyboard at the time, implemented it like this:

>>> def is_valid(account_number):
...   total = 0
...   for i in xrange(9):
...     total += (9-i)* account_number[i]
...   return total % 11 == 0

and I suggested this:

>>> def is_valid(account_number):
...   return sum(d* i for d, i in zip(reversed(account_number), range(1,10))) % 11 == 0

but the clear winner in our little refactoring battle was Andrew who wrote this:

>>> def is_valid(account_number):
...   d9,d8,d7,d6,d5,d4,d3,d2,d1 = account_number
...   return (d1+2*d2+3*d3+4*d4+5*d5+6*d6+7*d7+8*d8+9*d9) % 11 == 0

which is brilliant and reminded me of why I love Python. It looks like pseudo-code! Reading Andrew's implementation is basically like reading the specification.

NOTE! I re-wrote these functions from memory so I may have missed some little detail. My apologies if that is the case. Also, some variables have been renamed to protect the innocent.

Sling Blade Runner

2008-05-12T08:35:00.008+02:00

I found the ITA Software Hiring Puzzles almost a year ago and ever since I haven't really been able to stop thinking about one of the puzzles: Sling Blade Runner.

"How long a chain of overlapping movie titles, like Sling Blade Runner, can you find?"

Use the following listing of movie titles: MOVIES.LST. Multi-word overlaps, as in "License to Kill a Mockingbird," are allowed. The same title may not be used more than once in a solution. Heuristic solutions that may not always produce the greatest number of titles will be accepted: seek a reasonable tradeoff of efficiency and optimality.

The file MOVIES.LST contains 6561 movie titles in alphabetical order.

It *sounds* simple enough, but it's actually quite a challenging problem. In fact, if I'm not mistaken, it's one of those problems you really can't find an *optimal* solution to. Just better or worse approximations thereof.

I think I've made something like five or six, more or less serious, attempts at getting a decent solution during the year. But thinking about this problem has made me read several books, web pages and articles on various subjects like graph theory and clustering. I've written code in Lisp, CLIPS and Python to test ideas I've had. All in all; it's been a very rewarding, educational and fun year.

Last week I decided to give it another serious attempt. That resulted in (after two days and 6 hours worth of coding) a small (~200 LOC) Python program that finds a chain that is 225 titles long. I really have no idea if that is good or bad. I know that Eric Burke found a chain that is 245 titles long so I guess I could do better. But if that chain is optimal, or close to optimal, I'm quite pleased anyway.

My program uses a best-first search approach using the size of the successors tree as the heuristic. It's a rather crude approach but works surprisingly well. Since it doesn't backtrack or explore more than one path at a time it doesn't really require that much space. This also means that I can keep using my laptop while the program is running.

The program works as follows:

The first step is to build a dict containing all the successors for a title. I'm actually using the line number (from MOVIES.LST) as the identifier instead of the title itself, but this should give you an idea of what it looks like:

{ ..., 'SLING BLADE': ['BLADE II', 'BLADE RUNNER', 'BLADE TRINITY',], ... }

It takes about half a second to create the dict for this data set. It contains 6561 keys and the sum of the lengths of the values is 15157.

The second step is the search. It is done by selecting the title with the most successors (that isn't already in the list), adding it to the list and repeating until there are no more titles that can be added.

The dict is sorted by the length of the list of successors so we don't have to search using all of the 6561 titles as starting points. Since, at least in theory we'll get shorter and shorter chains the further down we go.

The gist of the search function looks like this:

>>> def best_first_search(xref, lookahead = 5, cutoff = -1):
...   [...]
...     for index in sorted(xref.keys(), key = lambda k: tree_size(xref, k, 0, [k,]), reverse = True):
...       [...]
...       while True:
...         [...]
...         for next in sorted(xref[curr], key = lambda k: tree_size(xref, k, lookahead, chain), reverse = True):
...           if next not in chain:
...             chain.append(next)
...             assigned = True
...             break
...         if not assigned:
...           if len(chain) > len(longest):
...             print len(chain), "(#%s)" % (i), "%02.2fs" % (time.time()-start)
...             longest = chain
...           break
...       [...]
...   return longest

The function that calculates the size of the successors tree (see below) does so by traversing it to a certain depth. The deeper you search, the longer it takes, but there seems to be diminishing returns when using a search-depth greater than six or seven.

>>> def tree_size(xref, curr, depth, chain = None):
...   if chain is None:
...     chain = []
...   result = 0
...   if depth > 0:
...     for next in xref[curr][1:]:
...       if next not in chain:
...         result += tree_size(xref, next, depth- 1, chain+ [next,])
...   else:
...     length = 0
...     for title in xref[curr][1:]:
...       if title not in chain:
...         length += 1
...     result = length
...   return result

Using the above we can get a chain that is 203 titles long. It takes about two and a half minutes and is found as the 17th title searched. A chain that is 200 titles long is found when expanding the third title and takes about 20 seconds to get to. The next best chain is 202 titles long and takes about 1 minute 15 seconds to find at the ninth title expanded. The total runtime for the program using a cutoff at 20 takes about three minutes to complete. Here is the output:

161 (#1) 7.98s
177 (#2) 14.72s
200 (#3) 20.57s
202 (#9) 72.25s
203 (#17) 146.46s

1 WOMEN IN LOVE
2 LOVE WALKED IN
3 IN THIS OUR LIFE
4 LIFE OR SOMETHING LIKE IT
5 IT HAPPENED ONE NIGHT
...
199 SEX AND THE OTHER MAN
200 MAN OF THE YEAR
201 YEAR OF THE DRAGON
202 DRAGON SEED
203 SEED OF CHUCKY
203 titles in chain 182.76s

To get a longer chain we need to do some tweaking. The problem is that by selecting the title with the largest successors tree we might get long chains, but we're missing all of those little detours that make it the "longest" chain. For example, if we have a title A with two successors, B and C, where B has several successors (D, E, F, ...) and C only has B as its successor. Even though A->C->B, clearly, is the better choice my program will *always* choose the direct route A->B.

To compensate for this blind spot, every chain is expanded by trying to find longer paths between each pair of nodes in the chain (see below). Unfortunately, by adding this extra step the program requires more memory and becomes noticeably slower.

>>> def expand(xref, chain, max_depth, longest):
...   [...]
...     for curr, next in zip(chain[:-1], chain[1:]):
...       expansions = None
...       for i in range(2, max_depth+ 1):
...         paths = find(xref, curr, next, i, chain)
...         if paths:
...           expansions = paths
...       if expansions is not None:
...         expansion = sorted(expansions, key = lambda k: len(k), reverse = True)[0]
...         [...]
...         chain[chain.index(next):chain.index(next)] = expansion
...   return chain

The find function looks like this:

>>> def find(xref, curr, end, depth, chain = None):
...   if chain is None:
...     chain = []
...   if depth > 0:
...     result = []
...     for next in xref[curr][1:]:
...       if next not in chain:
...         paths = find(xref, next, end, depth- 1, chain+ [next,])
...         if paths:
...           for path in paths:
...             result.append([next,]+ path)
...     return result
...   elif end in xref[curr][1:]:
...     return [[],]
...   return None

I've tried various values for max_depth and 25 seems to be a good-enough value. I have found several expansions that are longer than that but they don't seem to add to the overall result anyway.

If we change the block of code that checks for and assigns the longest chain in the best_first_search function to:

...         if not assigned:
...           chain = expand(xref, chain, max_depth, len(longest))
...           if len(chain) > len(longest):
...             print len(chain), "(#%s)" % (i), "%02.2fs" % (time.time()-start)
...             longest = chain
...           break

and run the program again we get the first result after about a minute and it is 205 titles long.

The longest chain is 225 titles and it is found at #134 but it takes almost 50 minutes to find. Running the whole search (500 "best" titles) takes about 4 hours. Running it with a cutoff of 150 takes about 55 minutes and produces the following output:

205 (#1) 52.72s
206 (#5) 176.38s
208 (#6) 199.54s
[10]
209 (#12) 338.63s
211 (#13) 360.17s
212 (#18) 471.40s
[20]
213 (#21) 538.34s
[30]
[40]
[50]
[60]
[70]
[80]
215 (#85) 1904.34s
[90]
[100]
[110]
218 (#116) 2592.82s
[120]
[130]
219 (#131) 2858.43s
225 (#134) 2900.19s
[140]
[150]
1 OFF THE BLACK
2 THE BLACK ANGEL
3 ANGEL EYES
4 EYES OF AN ANGEL
5 ANGEL BABY
6 BABY SECRET OF THE LOST LEGEND
7 LEGEND OF THE LOST
8 THE LOST BOYS
9 BOYS ON THE SIDE
10 SIDE OUT
11 OUT COLD
12 COLD FEVER
13 FEVER PITCH
14 PITCH BLACK
15 BLACK HAWK DOWN
16 DOWN WITH LOVE
17 LOVE WALKED IN
18 IN THIS OUR LIFE
19 LIFE OR SOMETHING LIKE IT
20 IT HAPPENED ONE NIGHT
21 ONE NIGHT STAND
22 STAND IN
23 IN THE HEAT OF THE NIGHT
24 THE NIGHT OF THE FOLLOWING DAY
25 DAY OF THE DEAD
26 THE DEAD
27 DEAD OF NIGHT
28 NIGHT OF THE LIVING DEAD
29 DEAD MAN
30 DEAD MAN WALKING
31 WALKING AND TALKING
32 TALKING ABOUT SEX
33 SEX AND THE OTHER MAN
34 MAN OF THE HOUSE
35 HOUSE OF DRACULA
36 DRACULA DEAD AND LOVING IT
37 IT HAD TO BE YOU
38 YOU CAN COUNT ON ME
39 ME MYSELF I
40 I LOVE YOU TO DEATH
41 DEATH WISH
42 WISH UPON A STAR
43 A STAR IS BORN
44 BORN AMERICAN
45 AMERICAN ME
46 ME WITHOUT YOU
47 YOU LIGHT UP MY LIFE
48 MY LIFE
49 LIFE AS A HOUSE
50 HOUSE OF FRANKENSTEIN
51 FRANKENSTEIN AND THE MONSTER FROM HELL
52 FROM HELL
53 HELL UP IN HARLEM
54 HARLEM RIVER DRIVE
55 DRIVE ME CRAZY
56 CRAZY AS HELL
57 HELL NIGHT
58 NIGHT AND THE CITY
59 THE CITY
60 CITY OF ANGELS
61 ANGELS WITH DIRTY FACES
62 FACES OF DEATH
63 DEATH SHIP
64 SHIP OF FOOLS
65 FOOLS RUSH IN
66 IN THE WINTER DARK
67 DARK STAR
68 STAR TREK IV THE VOYAGE HOME
69 HOME ALONE
70 ALONE IN THE DARK
71 THE DARK HALF
72 HALF LIGHT
73 LIGHT OF DAY
74 DAY FOR NIGHT
75 NIGHT FALLS ON MANHATTAN
76 MANHATTAN MURDER MYSTERY
77 MYSTERY ALASKA
78 ALASKA SPIRIT OF THE WILD
79 THE WILD ONE
80 ONE NIGHT WITH THE KING
81 THE KING AND I
82 I WANT TO LIVE
83 LIVE AND LET DIE
84 DIE MOMMIE DIE
85 DIE HARD
86 HARD EIGHT
87 EIGHT AND A HALF WOMEN
88 WOMEN IN LOVE
89 LOVE AND DEATH
90 DEATH WISH 3
91 3 NINJAS KNUCKLE UP
92 UP CLOSE AND PERSONAL
93 PERSONAL BEST
94 BEST OF THE BEST
95 BEST MEN
96 MEN IN BLACK
97 BLACK AND WHITE
98 WHITE HUNTER BLACK HEART
99 HEART CONDITION
100 CONDITION RED
101 RED EYE
102 EYE FOR AN EYE
103 EYE OF GOD
104 GOD TOLD ME TO
105 TO DIE FOR
106 FOR THE BOYS
107 THE BOYS
108 BOYS AND GIRLS
109 GIRLS WILL BE GIRLS
110 GIRLS GIRLS GIRLS
111 GIRLS OF SUMMER
112 SUMMER SCHOOL
113 SCHOOL OF ROCK
114 ROCK STAR
115 STAR TREK THE MOTION PICTURE
116 PICTURE BRIDE
117 BRIDE OF THE WIND
118 THE WIND AND THE LION
119 THE LION KING
120 KING OF THE JUNGLE
121 THE JUNGLE BOOK
122 BOOK OF LOVE
123 LOVE IS THE DEVIL
124 THE DEVIL RIDES OUT
125 OUT OF THE BLUE
126 BLUE CAR
127 CAR 54 WHERE ARE YOU
128 YOU ONLY LIVE ONCE
129 ONCE AROUND
130 AROUND THE BEND
131 BEND OF THE RIVER
132 THE RIVER
133 THE RIVER WILD
134 WILD THINGS
135 THINGS TO COME
136 COME AND GET IT
137 IT TAKES TWO
138 TWO FRIENDS
139 FRIENDS WITH MONEY
140 MONEY FOR NOTHING
141 NOTHING BUT TROUBLE
142 TROUBLE EVERY DAY
143 DAY OF THE WOMAN
144 THE WOMAN IN RED
145 RED RIVER
146 RIVER OF NO RETURN
147 RETURN TO HORROR HIGH
148 HIGH SPIRITS
149 SPIRITS OF THE DEAD
150 DEAD BANG
151 BANG BANG YOURE DEAD
152 DEAD MAN ON CAMPUS
153 CAMPUS MAN
154 MAN TROUBLE
155 TROUBLE IN PARADISE
156 PARADISE ROAD
157 ROAD HOUSE
158 HOUSE PARTY
159 HOUSE PARTY 3
160 3 NINJAS KICK BACK
161 BACK STAGE
162 STAGE FRIGHT
163 FRIGHT NIGHT
164 NIGHT MOTHER
165 MOTHER NIGHT
166 NIGHT ON EARTH
167 EARTH GIRLS ARE EASY
168 EASY COME EASY GO
169 GO NOW
170 NOW YOU SEE HIM NOW YOU DONT
171 DONT GO IN THE HOUSE
172 THE HOUSE OF THE DEAD
173 DEAD END
174 END OF DAYS
175 DAYS OF HEAVEN
176 HEAVEN CAN WAIT
177 WAIT UNTIL DARK
178 DARK CITY
179 CITY BY THE SEA
180 SEA OF LOVE
181 LOVE LIFE
182 LIFE IS BEAUTIFUL
183 BEAUTIFUL PEOPLE
184 PEOPLE I KNOW
185 I KNOW WHAT YOU DID LAST SUMMER
186 SUMMER CATCH
187 CATCH A FIRE
188 FIRE ON THE MOUNTAIN
189 THE MOUNTAIN MEN
190 MEN WITH GUNS
191 GUNS OF THE MAGNIFICENT SEVEN
192 THE MAGNIFICENT SEVEN
193 THE MAGNIFICENT SEVEN RIDE
194 RIDE THE HIGH COUNTRY
195 COUNTRY LIFE
196 LIFE WITH FATHER
197 FATHER OF THE BRIDE
198 BRIDE OF THE MONSTER
199 MONSTER HOUSE
200 HOUSE PARTY 2
201 2 DAYS IN THE VALLEY
202 VALLEY GIRL
203 GIRL IN THE CADILLAC
204 CADILLAC MAN
205 MAN ON FIRE
206 FIRE IN THE SKY
207 SKY HIGH
208 HIGH SCHOOL HIGH
209 HIGH CRIMES
210 CRIMES OF PASSION
211 PASSION IN THE DESERT
212 DESERT BLUE
213 BLUE STEEL
214 STEEL DAWN
215 DAWN OF THE DEAD
216 DEAD HEAT
217 HEAT AND DUST
218 DUST TO GLORY
219 GLORY ROAD
220 ROAD GAMES
221 GAMES PEOPLE PLAY NEW YORK
222 NEW YORK COP
223 COP LAND
224 LAND OF THE DEAD
225 THE DEAD POOL
225 titles in chain 3203.74s

I've got a few other ideas and strategies (~~beam search~~ beam-stack search for instance) I'd like to try to see if I can get an even longer chain, but I should probably re-implement the code in Lisp to make it faster first. 50 minutes is a tad on the long side ;-)

[Update 2008-05-12] I just did some more extensive Googling and my results are not that good in comparison to the 312 titles long chain found by icefox. Back to work.

[Correction 2008-07-02]: When I say beam search I mean beam-stack search.

Implied deftemplates considered harmful

2008-05-07T10:32:00.001+02:00

CLIPS is an extremely flexible and adaptive programming environment. Unfortunately, that's not always for the best.

Implied deftemplates (see chapter 3.4 in CLIPS Basic Programming Guide) can be a nuisance when debugging. It makes a difficult task even more difficult because certain, *trivial*, errors (more specifically, spelling errors) can go undetected. It's a bit similar to weak typing, though usually not as bad.

I've learned (the hard way) to stay clear from ordered facts and implied deftemplates but if you still do use them and your application isn't really behaving as you expect. Try a (list-deftemplates) as your first debugging effort. You may well be surprised.

12.3.6 Evaluating a Construct within a String

2008-05-04T11:30:00.000+02:00

The CLIPS Basic Programming Guide is (more or less) the only reference you'll ever need for your CLIPS programming needs. It is however sometimes a bit brief. Like the section describing how to add constructs at run-time:

12.3.6 Evaluating a Construct within a String

The build function evaluates the string as though it were entered at the command prompt.

Syntax
(build [string-or-symbol-expression])

where the only argument is the construct to be added. The return value is TRUE if the construct was added (or FALSE if an error occurs).

The build function is not available for binary-load only or run-time CLIPS configurations (see the Advanced Programming Guide).

Example
CLIPS> (clear)
CLIPS> (build "(defrule foo (a) => (assert (b)))")
TRUE
CLIPS> (rules)
foo
For a total of 1 rule.
CLIPS>

It could use a few more examples. Or at least one that is slightly more complex. Personally, I've never used build without wrapping it in a deffunction. But that also introduces the complexity of handling several str-cat calls to build up the definition of the construct in a variable.

Almost all such builder-deffunctions that I've made follow the same basic template

|CLIPS> (deffunction build-foo-deftemplate (?n)
|  (bind ?templ (str-cat "(deftemplate foo (slot id)"))
|  (loop-for-count (?i ?n)
|    (bind ?templ (str-cat ?templ
|                          " (slot slot" ?i ")")))
|  (bind ?templ (str-cat ?templ ")"))
|  (build ?templ))
|CLIPS> (build-foo-deftemplate 3)
|TRUE
|CLIPS> (ppdeftemplate foo)
|(deftemplate MAIN::foo
|   (slot id)
|   (slot slot1)
|   (slot slot2)
|   (slot slot3))
|CLIPS>

Granted, this example might not be very useful but at least it shows the steps required to incrementally build up a definition in a variable. It's easy to get lost in all of those extra parens but if you've got a decent editor it can match them up for you even though they're embedded in strings.

KataMinesweeper

2008-04-28T10:32:00.000+02:00

I've been playing around with a few of the katas at codingdojo.org these past few days. I'm new to the concept but I like the idea and since I'm going to attend a kata session led by Emily in a couple of weeks I thought I'd prepare.

Here's my best-so-far attempt at KataMinesweeper:

|def convert(rows, cols, field):
|    """
|    >>> print convert(1,1,['*'])
|    *
|    >>> print convert(2,2,['*.', '..'])
|    *1
|    11
|    >>> print convert(4,4,['*...', '....', '.*..', '....'])
|    *100
|    2210
|    1*10
|    1110
|    >>> print convert(3,5,['**...', '.....', '.*...'])
|    **100
|    33200
|    1*100
|    """
| 
|    _field = dict(zip(range(rows), [dict(zip(range(cols), f)) for f in field]))
| 
|    for r in range(rows):
|        for c in range(cols):
|            if _field[r][c] == '.':
|                count = 0
|                for _r,_c in [(r-1,c-1), (r-1,c), (r-1,c+1), (r,c-1), (r,c+1), (r+1,c-1), (r+1,c), (r+1,c+1)]:
|                    try:
|                        if _field[_r][_c] == '*':
|                            count += 1
|                    except:
|                        pass
|                     
|                _field[r][c] = str(count)
|             
|    return "\n".join(["".join(f.values()) for f in _field.values()])
| 
|def content(filename):
|    f = open(filename)
|    lines = f.readlines()
|    f.close()
| 
|    return lines
| 
|def solve(lines):
|    """
|    >>> solve(['4 4\\n','*...\\n','....\\n','.*..\\n','....\\n',
|    ...        '3 5\\n','**...\\n','.....\\n','.*...\\n',
|    ...        '0 0\\n'])
|    Field #1:
|    *100
|    2210
|    1*10
|    1110
|    [BLANKLINE]
|    Field #2:
|    **100
|    33200
|    1*100
|    [BLANKLINE]
|    """
| 
|    l, n = 0, 1
|    while True:
|        rows, cols = map(int, lines[l].split())
|        if rows == 0 and cols == 0:
|            break
|         
|        print "Field #%s:" % n
|        print convert(rows, cols, [line.strip() for line in lines[l+1:l+rows+1]])
|        print
|     
|        n += 1
|        l += rows+1
|     
|if __name__ == '__main__':
|    import doctest
|    doctest.testmod()
| 
|    import sys
|    solve(content(sys.argv[-1]))

and running it with the suggested test-case in a text-file (minesweeper.txt) gives the following output:

|C:\Playground\Katas>minesweeper.py minesweeper.txt
|Field #1:
|*100
|2210
|1*10
|1110
|
|Field #2:
|**100
|33200
|1*100

It needs more tests. I know ;-)

Another SVN update

2008-04-26T11:39:00.005+02:00

This has been a slow week, the whole family has come down with the flu and I haven't been able to do that much.

I've come a bit further though and now the code in the SVN repo has a working execution environment and conflict resolver. There are still a lot of things to add and work out but it really feels as if the pieces are starting to fall into place.

Debugging in CLIPS

2008-04-21T10:14:00.000+02:00

I spend part of my time at CLIPSESG and I try to help whenever I can. Usually that involves figuring out why a rule is, or isn't, firing and mostly it's a simple-enough error or an "obvious" mistake that causes the problem. The thing is that it's mostly real easy to find them as well. At least if you know where to look.

One (very useful) way of looking at your CLIPS program is by using the built-in facts and matches functions (see chapter 13.4.1 Displaying the Fact-List and chapter 13.6.4 Displaying Matches for a Rule in the CLIPS Basic Programming Guide). There are some things to think about though.

Evaluating (facts) is tricky in the same way select * from Foo is tricky in SQL. You've got to make sure that when you've got enough facts in Working Memory you don't print them all in the shell. Mostly because it takes a while, but also because you can't scroll more than a few hundred lines. So if what you're interested in is printed early on, chances are you won't be able to see it anyway.

The matches function is equally verbose. Unfortunately there's no way to turn that verbosity off. If you've got a lot of facts matching some pattern in a rule they will all be printed to the shell and if you've got a lot of patterns with a lot of matching facts you're not going to be able to inspect all of the output in the shell. Luckily you can use the dribble-on/off functions (see chapter 13.2.1 Generating Trace Files in the BPG) to copy output to a file. That way, you can use your favorite text editor to inspect the output instead.

I should also mention breakpoints and set-break (see chapter 13.6.5 Setting a Breakpoint for a Rule in the BPG). They're great if you need to inspect the application after it has done some processing but before it has finished. You can also use the poor-man's version: (run n) if you're really certain on how many rule firings it takes to build up the problematic state. But I've found that I usually only use that when I'm in an exploratory mood and step through the application using (run 1).

It might take a while to become familiar with debugging in CLIPS but it's well worth the effort.

SVN update

2008-04-16T13:07:00.003+02:00

I haven't updated the PyRete SVN repo for some time now. Mostly because I haven't really had any (working) code I wanted to share. But no more of that. Today I managed to compile:

>>> @prodsys.rule
... def rule1(self, large = Large, medium = Medium, small = Small):
...   if large(value == x, another == y) and \
...      medium(value == y, another == z) and \
...      small(value == z, another == x):
...     pass

into a Rete Network. Seems to work as well ;-)

I'm not saying I'm done or anything. It'll probably take a while to finish all of the details and write test cases for all the relevant variants of rules that can be expressed but I'm hoping that most of the tricky parts have been sorted out. And since the public engine functions (reset, watch etc) already have been implemented once. I figure it's easy to port them to the new code. It'll probably be boring but it should be easy enough.

Swedish Championships of Robotics

2008-04-15T20:47:00.003+02:00

This weekend, the University of Chalmers is hosting the Swedish Championships of Robotics. The whole family is going to go watch and it looks like it's going to be a killer event. I can't wait!

AST to AST translation in Python

2008-04-11T22:26:00.002+02:00

In an attempt to further simplify PyRete's rule compiler I've split it into three parts.

1) Pre-processing (splits a rule into subrules, if necessary),
2) macro-expansion (translates, for example, Exists(CE*) into Not(Not(CE*))) and
3) Rete Network construction (creates Production-, Alpha- and BetaNodes and joins them together).

The complexity of trying to handle all of that in one class just got out of hand. Also, I think this design will make PyRete a lot more flexible and easier to extend with custom constructs (given that they are not violating Python's syntax that is).

Anyway, the idea is that the Rete Network construction (step 3) should only have to deal with constructs that can be translated directly into a node in the Rete Network and that everything else should be handled in either of the two previous steps. This means, among other things, that in step 3 there'll only be Object-Pattern-CEs, Test-CEs and Not-CEs left.

I'll talk about parts of step 2 (the macro-expansion) since I think it's the most interesting part.

Unfortunately there isn't that much written about AST to AST translation in Python. Not very surprising considering that it's not generally the level of abstraction most people decide to interfer with the compilation-chain. Most attempts either cover the whole thing, from front to back, like python4ply and EasyExtend or perform low-level bytecode manipulation as bytecodehacks and psyco. Even the Python docs for the compiler module and its AST visitor class is quite sparse to say the least.

Luckily I've spent more than a year poking around on the AST level of Python code so I'm used to trial and error and having exceptions thrown in my face every now and then. The translation scheme I've implemented is not as smooth as having Common Lisp or Scheme macros but it does the job.

Here's the code for handling the Exists-CE:

>>> class ExistsCE(object):
...   @classmethod
...   def expand(self, node):
...     nodesToVisit = [node]
...     while len(nodesToVisit) > 0:
...       curr = nodesToVisit.pop(0)
...       for child in curr.getChildNodes():
...         nodesToVisit.append(child)
...       if isinstance(curr, CallFunc) and curr.node.name == "Exists":
...         curr.node.name = "Not"
...         curr.args = [CallFunc(Name("Not"), curr.args)]
...     return node

and here's a sample usage (I've highlighted the interesting parts).

>>> ast = compiler.parse("Exists(Spam(eggs == 1, bacon = 2))")
>>> print ast
Module(None, Stmt([Discard(CallFunc(Name('Exists'), [CallFunc(Name('Spam'), [Com
pare(Name('eggs'), [('==', Const(1))]), Keyword('bacon', Const(2))], None, None)
], None, None))]))

and if we run it through the ExistsCE macro expander we get:

>>> print ExistsCE.expand(ast)
Module(None, Stmt([Discard(CallFunc(Name('Not'), [CallFunc(Name('Not'), [CallFun
c(Name('Spam'), [Compare(Name('eggs'), [('==', Const(1))]), Keyword('bacon', Con
st(2))], None, None)], None, None)], None, None))]))

which is exactly the same AST as if we had written two nested Not calls instead:

>>> print compiler.parse("Not(Not(Spam(eggs == 1, bacon = 2)))")
Module(None, Stmt([Discard(CallFunc(Name('Not'), [CallFunc(Name('Not'), [CallFun
c(Name('Spam'), [Compare(Name('eggs'), [('==', Const(1))]), Keyword('bacon', Con
st(2))], None, None)], None, None)], None, None))]))

I wonder if I can abstract away some of that boiler plate, make it more general and usable. I'll have to tinker some more but it shouldn't be impossible.

The Absolute Minimum Every CLIPS Developer Absolutely, Positively Must Know About the Not-CE and Template-Pattern-Constraints (No Excuses!)

2008-04-08T21:40:00.003+02:00

Ok. So I stole the title from Joel's very popular article about Unicode, but it's not just a way to get attention. The point is that there are some things about how CLIPS (and other Rule Engines) handle not that might not be all that obvious to programmers used to languages such as Python or Java.

More specifically, I'm talking about the difference between

|CLIPS> (defrule rule1
|  (spam (eggs ?eggs) (bacon ?bacon))
|  (test (not (and (eq ?eggs 1) (eq ?bacon 2))))
|  =>)

and

|CLIPS> (defrule rule2
|  (not (spam (eggs 1) (bacon 2))
|  =>)

You're not alone if you've ever made the mistake of thinking that wrapping a template-pattern-CE with a not would negate the constraints inside it. That's, however, not what the Not-CE does.

A logical not is the simplest possible operator. It simply returns True if the expression it applies to returns False and vice versa. In CLIPS, it's easy enough to figure out what expression a not applies to, but you might be surprised at how that expression is evaluated?

The Not-CE evaluates to True if there are no facts in Working Memory matching the pattern it applies to. You should think of not as short hand for Not-in-Working-Memory and not as a Not-Equals variant. I know it's not at all that obvious since there are no hints (compare Java's !=) but it should make it's behaviour less of a surprise.

Python as a boat

2008-04-05T13:52:00.003+02:00

There are a lot of funny what-kind-of-X-would-programming-language-Y-be-lists floating around on the internet. And, here's another one from CompSci.ca/blog. I especially like jpc's description of Python (in the comments):

"Python would be a catamaran. Light and functional, with conspicuous spacing."

Another attempt at pattern matching

2008-04-04T21:29:00.001+02:00

In my previous post I'm talking about feature-tests without really explaining what I mean. So here's an attempt to re-phrase, expand on and give some background to my thoughts.

I spent yesterday re-reading parts of Forgy's thesis (using OPS2) and the AI Journal article (using OPS5) describing the Rete Algorithm.

The implementation described in the thesis uses a whole lot of nodes to test for features of the fact-structure as well as the values contained in a fact. This approach of classifying things is known as Structural Typing.

Compiling the MB11 production in OPS2 (see 2.2.1 Productions with one Condition Element in the thesis):

MB11 ( (Want (Monkey Near =P))
       -->
      (Want (Monkey On Floor)) )

produces no less than five nodes in the Rete Network:

1. Is the element a list of two subelements?
2. Is the first subelement Want?
3. Is the second subelement a list of three subelements?
4. Is the first subelement of the second subelement Monkey?
5. Is the second subelement of the second subelement Near?

The article, however, describes a different approach, based on Static Typing, which requires you to declare the structure of a fact before using it. This way, we can remove all feature-tests and replace them with only one test, an expression node (also known as an object type node).

The MB11 production for OPS5 looks like this:

(p mb11
 (goal ^status active ^type walk-to ^object [p])
  -->
 (make goal ^status active ^type on ^object floor))

They're not the same, I know.

But still, from the description in the article this would be compiled into three nodes:

1. Is the element's class goal?
2. Is the value of the status attribute active?
3. Is the value of the type attribute walk-to?

It doesn't take too large a rulebase before the benefits of this approach start to show. But at the same time, it seems that we have also lost the possibility to match nested structures.

In OPS5, according to the OPS5 Reference Manual, there's a possibility to create a vector attribute which can hold several values. Here's part of an OPS5 dialog that shows what happens when you match a vector attribute:

OPS> (vector-attribute bar)
(BAR)
OPS> (literalize foo bar)
NIL
OPS> (p rule
       (foo ^bar [bar])
        -->
       (write " [bar] = " [bar] (crlf)))
*
NIL
OPS> (make foo ^bar 1 2 3)
NIL
OPS> (run)
1. RULE 1 [bar] =  1

I haven't yet been able to match several values with one variable (as $? allows you to in CLIPS). I'm not sure if this is even possible in OPS5. Actually, in chapter 2.6 The Range of Applicability of the Algorithm of Forgy's thesis he describes some of the constraints that we have to work around. In short, they are: 1) facts must only contain constants and 2) it must be possible to determine (at compile-time) which subelement each condition matches. This last constraint applies to Multifield variables and is probably one explanation to why they're so much slower than regular variables.

My question in the previous post was: why aren't nested data structures supported? Don't get me wrong. I'm not out to convince anyone to change anything or question whatever decisions has been made. I don't know if the issue is related to Multifield variables or not and I'm not sure I really care. The situation is as it is and CLIPS works just fine for my needs.

But. I'd really, *really* love to learn more about the design decisions made in different production systems regarding this, and other, areas. If you know of papers, articles, books or magazines that contain information about OPS, CLIPS and/or ART history please let me know.

[Update 2008-04-05]: The article The OPS Languages - An Historical Overview in this issue of PC AI magazine looks interesting enough to order.

LISA, Multislots and thoughts about Pattern matching

2008-04-02T16:02:00.001+02:00

LISA has no multislots. That's just the way it is. You can add a list to a slot, but you have to match it as-is unless you provide a custom test-function.

About a week ago, Pedro Kröger announced on the Lisa Users mailing list that he was converting the Zebra puzzle from CLIPS to LISA. The rule syntax is so similar between the engines that it ought to have been a quite straightforward and simple exercise. But, since the CLIPS solution uses implied deftemplates (which are implemented as multislots) the LISA program wouldn't work.

This, and many other situations like it, has made me wonder about why nested fact structures aren't supported. Matching, on any level in a nested list, is actually described in Forgy's thesis (from 1979) but hasn't, for some reason, been implemented in most rule engines. Probably because it's faster to only allow flat structures.

The Rete implementation described in the thesis constructs an awful lot of nodes but I'm not sure you need all of them. A rule compiler ought to be able to figure out which part of a structure to test without doing too many feature-tests ("is the second subelement a list of 3 subelements" etc).

Utility for working with CSV-files in CLIPS

2008-03-29T08:35:00.001+01:00

A couple of months ago I wrote a CLIPS function that could load and assert data from a CSV-file. It was simple but it worked well for my needs. When I started working on The CLIPS Cookbook a couple of weeks ago, a CSV-utility was one of the first things I thought about. Unfortunately, it turned out to be more difficult than I thought to produce an RFC4180 compliant parser so the recipe has remained a placeholder. But, it won't much longer.

Yesterday, I managed to get an implementation to work such that it can handle both import and export from and to CSV-files. I've still got some polishing to do but here's a short introduction to using it.

Assuming we've got a set of link-facts in Working Memory:

CLIPS> (facts)
f-0     (initial-fact)
f-1     (link (title "CLIPSESG") (url "http://groups.google.com/group/CLIPSESG"))
f-2     (link (title "CLIPS") (url "http://clipsrules.sourceforge.net/"))
For a total of 3 facts.

We can export them to a CSV-file using the function CSV-export:

CLIPS> (load "csv.clp")
:!!!!
TRUE
CLIPS> (CSV-export "links.csv" link)
2

The file links.csv looks like this afterwards:

title,url
"CLIPSESG","http://groups.google.com/group/CLIPSESG"
"CLIPS","http://clipsrules.sourceforge.net/"

And if we instead want to load the link-facts from file we can use CSV-import:

CLIPS> (load "csv.clp")
:!!!!
TRUE
CLIPS> (CSV-import "links.csv" link)
2
CLIPS> (facts)
f-0     (initial-fact)
f-1     (link (title "CLIPSESG") (url "http://groups.google.com/group/CLIPSESG"))
f-2     (link (title "CLIPS") (url "http://clipsrules.sourceforge.net/"))
For a total of 3 facts.

Both functions take the filename and the deftemplate as parameters. You can also specify which slots should be exported/imported but that's really not neccessary. However, the first row of the CSV-file must contain slot names (column headers) if you import facts without specifying slots.

Expert Systems Book

2008-03-25T08:53:00.000+01:00

I live about 50 m from the University of Chalmers and, naturally, I make use of their library.

During my visit last week I accidently found a very interesting 6-volume set of books named Expert Systems: The Technology of Knowledge Management and Decision Making for the 21st Century.

I'm currently reading the first volume and it is very good. It's a bit theoretical, but I can really recommend it to anyone interested in Expert Systems. Here's a short list of selected chapters to whet your appetite:

Volume 1.
Ch. 4 - Reasoning with Imperfect Information.

Volume 2.
Ch. 9 - Model of Reasoning with Conflicting Information Sources in Knowledge Based Systems.

Volume 3.
Ch. 24 - Cellular Automata Architectures for Pattern Recognition.

Volume 4.
Ch. 29 - Automatic Knowledge Discovery in Larger Scale Knowledge-Data Bases.
Ch. 34 - Neural Networks for Economic Forecasting Problems.

Volume 5.
Ch. 37 - Hybrid Expert Systems: An Approach to Combining Neural Computation and Rule-Based Reasoning.
Ch. 40 - Distributed Logic Processors in Process Indentification.

Volume 6.
Ch. 46 - Methodology for Building Case-Based Resaoning Systems in Ill-Structured Optimization Domains.

There are 50 chapters all in all spanning almost 2000 pages so this is probably going to take me a while.

1000 LOC removed

2008-03-21T09:59:00.004+01:00

There's not many things that make me happier than being able to remove existing code. These past few days have been quite good in that respect.

Previously I compiled a Rete Network from a Python AST by passing the rule function's AST to an ASTVisitor which returned a dictionary holding information about which nodes should be created. The dictionary was then passed to a method (construct_rete) which was in charge of creating the Rete Network and figuring out in what way the nodes should be connected.

That way of doing it turned out to be an ugly beast of complexity which managed to resist all of my attempts to make it simpler. I spent more than half a year trying before I binned it completely and yesterday I updated PyRete's SVN repository with the code I've got so far.

The approach I use now is that I pass the rule function's AST to an ASTVisitor which *directly* calls the Rete implementation. This way I don't have to go through all of the trouble of maintaining a dictionary with intermediate details and the result is that I've managed to get rid of about 1000 lines of code and the compilation process is more or less understandable.

"K-I-S-S. Keep it simple, stupid. Great advice. Hurts my feelings every time." -Dwight Schrute

I hate mathematics

2008-03-14T22:27:00.003+01:00

Via Gary King, I found this little weirdness, called the 6174 problem.

Pick any four distinct digits (e.g., 6, 2, 9, 0)
arrange them into the largest possible integer (e.g., 9620)
arrange them into the smallest (e.g., 0269)
subtract the smaller from the larger (e.g., (- 9620 0269) => 9351)
go back to step 2 and repeat

The cool thing is that, regardless of which digits you choose, you will end up with 6174. Here's the sequence for the digits 6, 2, 9, 0:

9620 - 0269 = 9351
9531 - 1359 = 8172
8721 - 1278 = 7443
7443 - 3447 = 3996
9963 - 3699 = 6264
6642 - 2466 = 4176
7641 - 1467 = 6174
7641 - 1467 = 6174  ...

Apparently that's the longest one, I haven't bothered to check myself but I did translate Gary's Lisp code to Python. I took the memoize implementation straight from the Python Decorator Library. The whole thing is about 100 lines (which includes doctests).

ANN: CLIPS Cookbook

2008-03-14T21:21:00.000+01:00

The CLIPS Cookbook is now available at http://clipsrules.wiki.sourceforge.net/.

At this point it only includes 5 recipes but I hope that, with a little help and given time, it will grow into a valuable resource as a complement to the CLIPS documentation.

The Cookbook uses a public wiki which means that anyone can, and is encouraged to, add new or improve existing recipes. I will try to, periodically, add recipes based on what people ask about in CLIPSESG but you don't have to wait for me or anyone else if you think something is missing. Just add it. If you don't feel comfortable writing a recipe yourself, please add a page for it anyway and indicate that you want someone to help you write it.

All standard expectations of good wiki-behaviour applies so please behave.

Yet another post about the RuleCompiler

2008-03-11T23:38:00.003+01:00

There's still a lot of code to be written for the RuleCompiler but I came a bit further today. I've added print statements to the parser so I can trace the creation of the Rete Network.

>>> def rule1(self, large = Large, medium = Medium, small = Small):
...   salience = 10
...   if large(value == x and x > 10, another == y) and \
...      medium(value == y and y > x, another == z) and \
...      small(value == z):
...     pass

>>> parse(rule1)
# p = ProductionNode(rule = rule1)
# p.doc = None
# o1 = ObjectTypeNode(type = Small)
# o2 = ObjectTypeNode(type = Medium)
# o3 = ObjectTypeNode(type = Large)
# p.salience = 10
# x = large.value
# a1 = AlphaNode(large.value > 10)
# y = large.another
# j1 = JoinNode(large.another == medium.value)
# a2 = AlphaNode(large.another > large.value)
# z = medium.another
# j2 = JoinNode(medium.another == small.value)

I'm about 90% done. It took about 8h of programming, spread out during a week. I figure the last 10% will take at least as long. They always seem to do. But this is good. In my previous attempts it took me a lot longer to get this far.

A couple of days ago I thought I could lose the fact bindings (the method parameters) but it occured to me today that they are needed if one or more of the Facts are to be referenced in the RHS. So, the bindings stay.

And, regarding python4ply I've decided to do without it at the moment. The only thing I've found I really miss is the ability to use ? to distinguish a variable name from an attribute name. Without it there's no way a variable can have the same name as an attribute.

Funny thing

2008-03-10T10:49:00.005+01:00

It turns out that Andrew (who, among other things, have written python4ply) lives 200m away from me. I think I can see his apartment from my balcony ;-)

python4ply vs a custom rule compiler

2008-03-09T13:25:00.003+01:00

Andrew Dalke released python4ply 1.0 today. It might be useful as part of the RuleCompiler since I wouldn't have to constrain the rule syntax to Python's.

One of the main reasons for doing the rule compiler the way I am, is so I wouldn't have to re-implement a parser for Python's syntax but now that Andrew's gone and done just that... I don't know. This is from his announcement:

You might use python4ply to experiment with variations in the Python language. The PLY-based lexer and parser are much easier to change than the C implementation Python itself uses or even the ones written in Python which are part of the standard library.

It would be cool to have support for other syntaxes as well... I'll have to think about it.

Progress with the RuleCompiler

2008-03-07T16:20:00.000+01:00

Finally! It's starting to feel like I'm getting somewhere with PyRete's RuleCompiler. Earlier this week I decided to change quite a lot about the allowed syntax in a rule.

I've always kind of thought I'd have to have support for expressing rules in many different ways. For instance, I've tried to support at least three different approaches to expressing:

|CLIPS>(defrule rule
|  (foo (attribute ?attr&:(> ?attr 10)))
|  (bar (attribute ?attr))
|  =>)

This way, which used to be the preferred way, you would write the rule as if you were writing procedural code:

>>> @prodsys.rule
... def rule(engine, foo = Foo, bar = Bar):
...   if foo.attribute == bar.attribute and \
...      foo.attribute > 10:
...     pass

Another way, which always felt a bit weird and unnatural to me, was to use a (logical) variable:

>>> @prodsys.rule
... def rule(engine, foo = Foo, bar = Bar):
...   if foo.attribute == attr and \
...      bar.attribute == attr and \
...      attr > 10:
...     pass

The problem with it, and the reason I don't like it, is that it's not all that clear what is going to happen. There's no way of telling that attr is a logical variable and that makes it look like it's three ordinary comparisons, but it's not. In any other context the code would raise an Exception because the local variable attr is unbound and that's probably how most Python programmers will read it.

I thought that the above would cause a lot of confusion which is why I implemented another way of expressing the same thing which looks a lot more like the pattern-matching syntax of CLIPS:

>>> @prodsys.rule
... def rule(engine, foo = Foo, bar = Bar):
...   if foo(attribute == attr and attr > 10) and \
...      bar(attribute == attr):
...     pass

This is, of course, also slightly problematic but at least there's no interpretation of the code that completely shadows how it's being used in PyRete.

It wasn't until I decided, quite recently, that I'll only support the last type of syntax (pattern matching-style) that I started to get somewhere with the RuleCompiler. It also meant that I could get rid of the object bindings in the parameter list.

The above rule should be written as:

>>> @prodsys.rule
... def rule(engine):
...   if Foo(attribute == attr and attr > 10) and \
...      Bar(attribute == attr):
...     pass

It's only too bad that it takes me so long to figure these things out.

Exercise 16.1 in PAIP

2008-02-21T12:50:00.004+01:00

Suppose you read the headline "Elvis Alive in Kalamazoo" in a tabloid newspaper to which you attribute a certainty factor of .01. If you combine certainties using EMYCIN's combination rule, how many more copies of the newspaper would you need to see before you were .95 certain Elvis is alive?

Hilarious!

Evolvable Rules

2008-02-15T10:45:00.009+01:00

I stumbled on Evolvable Rules and REAT (Rete Evolution of Augmenting Topologies) yesterday whilst searching for interesting stuff to read. I'm not yet sure about what I think of the project but Greg sure got my attention.

The idea behind evolvable rules seem to be using Artificial Neural Network (ANN) techniques to generate a Rete network ~~and some additional stuff like conflict resolution and the code needed for executing the RHS of a rule~~.

There's not that much info yet but Greg shares a few references that explain the technology he intends to use. Apart from Charles Forgy's Rete papers (the thesis and the article) and the Wikipedia description of the Rete algorithm (which we have another Charles to thank for) he also refers to Evolving Neural Networks through Augmenting Topologies by Kenneth O. Stanley and Risto Miikkulainen.

I haven't read the last paper that thoroughly (skimmed it once) and I'm only just learning about ANN technology but it seems to me that this requires a lot of work. And, if I understand correctly, it might not be very good at producing a Rete network at all and since there are "simple" rules that can be used to construct a Rete network based on, for example, an Abstract Syntax Tree I don't really see the point. Apart from being really cool of course ;-)

Anyway, I'm real interested to see how all this works out. I've had similar lines of thought myself after having read An Optimization Algorithm for Production Systems by Toru Ishida last summer. It would be really neat to find a way to automatically optimize (restructure) a Rete network based on the contents of the working memory without having to pass through all Facts and re-evaulate the goal of the optimization continuously.

The problem is that I have no idea of how, or even if, it can be accomplished. But I bet that if someone does it, it's probably going to have something to do with using ~~ANN~~ GA techniques. I'm not holding my breath though.

Another backward chaining example from Jess In Action

2008-02-12T12:02:00.000+01:00

This is the multi-level backward chaining example from Jess In Action. My implementation of backward chaining had some problems with the original example so here is a new version of the shell that does the job.

CLIPS[001/01]> (deffunction fetch-price-from-database (?number)
CLIPS[001/02]:   (if (eq ?number 1)
CLIPS[001/03]:    then (return $1.99))
CLIPS[001/04]:   (return nil))
CLIPS[002/01]> (deffunction fetch-number-from-database (?name)
CLIPS[002/02]:   (if (eq ?name waffles)
CLIPS[002/03]:    then (return 1))
CLIPS[002/04]:   (return 0))
CLIPS[003/01]> (defrule price-check
CLIPS[003/02]:   (do-price-check ?name)
CLIPS[003/03]:   (price ?name ?price)
CLIPS[003/04]:   =>
CLIPS[003/05]:   (printout t "Price of " ?name " is " ?price crlf))
CLIPS[004/01]> (defrule find-price
CLIPS[004/02]:   (need-price ?name ?)
CLIPS[004/03]:   (item-number ?name ?number)
CLIPS[004/04]:   =>
CLIPS[004/05]:   (bind ?price (fetch-price-from-database ?number))
CLIPS[004/06]:   (assert (price ?name ?price)))
CLIPS[005/01]> (defrule find-item-number
CLIPS[005/02]:   (need-item-number ?name ?)
CLIPS[005/03]:   =>
CLIPS[005/04]:   (bind ?number (fetch-number-from-database ?name))
CLIPS[005/05]:   (assert (item-number ?name ?number)))
CLIPS[006/01]> (do-backward-chaining item-number)
; + MAIN::find-price/0
nil
CLIPS[007/01]> (do-backward-chaining price)
; + MAIN::price-check/0
nil
CLIPS[008/01]> (ppdefrule price-check/0)
(defrule MAIN::price-check/0
 (do-price-check ?name)
 =>
 (assert (need-price ?name nil)))
CLIPS[009/01]> (ppdefrule find-price/0)
(defrule MAIN::find-price/0
 (need-price ?name ?)
 =>
 (assert (need-item-number ?name nil)))
CLIPS[010/01]> (reset)
CLIPS[011/01]> (assert (do-price-check waffles))
CLIPS[012/01]> (watch rules)
CLIPS[013/01]> (run)
FIRE    1 price-check/0: f-1
FIRE    2 find-price/0: f-2
FIRE    3 find-item-number: f-3
FIRE    4 find-price: f-2,f-4
FIRE    5 price-check: f-1,f-5
Price of waffles is $1.99
CLIPS[014/01]> (facts)
f-0     (initial-fact)
f-1     (do-price-check waffles)
f-2     (need-price waffles nil)
f-3     (need-item-number waffles nil)
f-4     (item-number waffles 1)
f-5     (price waffles $1.99)
For a total of 6 facts.
CLIPS[015/01]>

Implementing backward chaining in PyCLIPS II.

2008-02-05T16:08:00.000+01:00

In my previous post I described a proof-of-concept implementation for backward chaining in PyCLIPS. One of the drawbacks was that it doesn't work on deftemplates.

Consider the factorial example again:

CLIPS[001/01]> (deftemplate factorial
CLIPS[001/02]:   (slot v)
CLIPS[001/03]:   (slot r))
CLIPS[002/01]> (defrule print-factorial-10
CLIPS[002/02]:   (factorial (v 10) (r ?r1))
CLIPS[002/03]:   =>
CLIPS[002/04]:   (printout t "The factorial of 10 is " ?r1 crlf))
CLIPS[003/01]> (defrule do-factorial
CLIPS[003/02]:   (need-factorial (v ?x) (r nil))
CLIPS[003/03]:   =>
CLIPS[003/04]:   (bind ?r 1)
CLIPS[003/05]:   (bind ?n ?x)
CLIPS[003/06]:   (while (> ?n 1)
CLIPS[003/07]:     (bind ?r (* ?r ?n))
CLIPS[003/08]:     (bind ?n (- ?n 1)))
CLIPS[003/09]:   (assert (factorial (v ?x) (r ?r))))
[PYCLIPS] C09: unable to understand argument
[PRNTUTIL2] Syntax Error:  Check appropriate syntax for defrule.
ERROR:
(defrule MAIN::do-factorial
(need-factorial (
CLIPS[004/01]>

The problem is that the CE that matches need-factorial requires a deftemplate and we haven't provided one. The "solution" is to have the do-backward-chaining function define the neccessary deftemplate dynamically. So all you need to think of is that you must either call do-backward-chaining or define the appropriate need-template before defining any rules that try to match it.

CLIPS[001/01]> (deftemplate factorial
CLIPS[001/02]:   (slot v)
CLIPS[001/03]:   (slot r))
CLIPS[002/01]> (defrule print-factorial-10
CLIPS[002/02]:   (factorial (v 10) (r ?r1))
CLIPS[002/03]:   =>
CLIPS[002/04]:   (printout t "The factorial of 10 is " ?r1 crlf))
CLIPS[003/01]> (do-backward-chaining factorial)
; + MAIN::need-factorial
; + MAIN::print-factorial-10/0
nil
CLIPS[004/01]> (defrule do-factorial
CLIPS[004/02]:   (need-factorial (v ?x) (r nil))
CLIPS[004/03]:   =>
CLIPS[004/04]:   (bind ?r 1)
CLIPS[004/05]:   (bind ?n ?x)
CLIPS[004/06]:   (while (> ?n 1)
CLIPS[004/07]:     (bind ?r (* ?r ?n))
CLIPS[004/08]:     (bind ?n (- ?n 1)))
CLIPS[004/09]:   (assert (factorial (v ?x) (r ?r))))
CLIPS[005/01]> (reset)
CLIPS[006/01]> (run)
The factorial of 10 is 3628800
CLIPS[007/01]>

The code is here, if you're interested. I'm not saying it's done or anything and I should probably have cleaned it up a bit more but I've been battling a cold for two weeks now and there are tons of other interesting things to try out. So this will have to do, at least for now.

Implementing backward chaining in PyCLIPS.

2008-01-27T00:11:00.000+01:00

I have been having an interesting e-mail conversation with Francesco about PyCLIPS this last week. PyCLIPS is mostly geared towards adding CLIPS to Python programs but it can also be used to add Python functionality to CLIPS. I've been urging him to add his Shell utility to the main package. The reason is because I think it would make a brilliant starting point for extensions. Regular expressions, backward chaining, database access and GUI capabilities are all good examples of what could be done.

I've done a little proof-of-concept implementation of backward chaining to show the idea and to provide a basis for discussion of these kinds of things. There are still a lot of things to do if this experiment is ever going to be useful and it might not even be possible to reach decent functionality (but it might be worth exploring further?). However, there are ways around most things when you control the dialog window ;-)

The general idea of the experiment is to implement something similar to how Jess handles backward chaining. Since there's no way to extend the syntax of CLIPS I can't add an explicit-CE and instead we'll have to make do with an explicit function.

> (deffunction MAIN::explicit ($?rules)
>   (progn$ (?rule $?rules)
>      (python-call explicit ?rule)))

I'll explain how it works after we've looked at do-backward-chaining and talked about some of the Python code.

> (deffunction MAIN::do-backward-chaining ($?templates)
>   (progn$ (?template $?templates)
>      (python-call do-backward-chaining ?template)))

I'm using Francesco's shell.py script as a basis for this experiment. I've modified it slightly though. When loaded it defines the above methods and attaches them to their Python counterpart using:

_cm.RegisterPythonFunction(do_backward_chaining, "do-backward-chaining")
_cm.RegisterPythonFunction(explicit, "explicit")

I've also made it such that whenever a user enters "(clear)" in the console the above functions are re-defined. I haven't found a good way of hooking into the clear command yet so if it's executed from a batch, this little hack won't do any good.

OK, let's see how it "works". Here's the factorial example from Jess In Action:

CLIPS[1/1]> (defrule print-factorial-10
CLIPS[1/2]:   (factorial 10 ?r1)
CLIPS[1/3]:   =>
CLIPS[1/4]:   (printout t "The factorial of 10 is " ?r1 crlf))
CLIPS[2/1]> (defrule do-factorial
CLIPS[2/2]:   (need-factorial ?x ?)
CLIPS[2/3]:   =>
CLIPS[2/4]:   (bind ?r 1)
CLIPS[2/5]:   (bind ?n ?x)
CLIPS[2/6]:   (while (> ?n 1)
CLIPS[2/7]:     (bind ?r (* ?r ?n))
CLIPS[2/8]:     (bind ?n (- ?n 1)))
CLIPS[2/9]:   (assert (factorial ?x ?r)))
CLIPS[3/1]> (do-backward-chaining factorial)
; + rule MAIN::print-factorial-10/0
nil
CLIPS[4/1]> (reset)
CLIPS[5/1]> (run)
The factorial of 10 is 3628800
CLIPS[6/1]>

The rules themselves are really not that interesting. What's interesting is that none of them ought to have been activated. And the reason they are is because of the function call to do-backward-chaining. We get a hint at what it has done on the line that says

; + rule MAIN::print-factorial-10/0

What happens is that the do-backward-chaining function in CLIPS calls the do_backward_chaining function in Python which searches through all rules (in all modules) for CEs that match

r"^\s*?\(%s\b(.*?)\)$" % (template)

(Yes. It's a Regular Expression. I know it's a bit hackish to do introspection work based on ppdefrule calls but it's not like there's any other option. At least not any that I can think of. If you know of a better way please let me know!)

If it finds a CE that matches, in our case (factorial 10 ?r1) in print-factorial-10, it generates a new rule based on the one containing the match. It adds a "/0" to the name (making it print-factorial-10/0), copies the LHS but removes the matching CE and constructs an RHS by taking the matching CE with a few modifications and placing it in an assert statement. The modifications it does is adding "need-" to the template name and replacing all variables with nil. We can see the result with

CLIPS[6/1]> (ppdefrule print-factorial-10/0)
(defrule MAIN::print-factorial-10/0
=>
(assert (need-factorial 10 nil)))
CLIPS[7/1]>

So, now it's easy to see why we got a result after (reset) and (run). Here's the dialog again, with facts and rules watched.

CLIPS[7/1]> (watch facts)
CLIPS[8/1]> (watch rules)
CLIPS[9/1]> (reset)
<== f-0     (initial-fact)
<== f-1     (need-factorial 10 nil)
<== f-2     (factorial 10 3628800)
==> f-0     (initial-fact)
CLIPS[10/1]> (run)
FIRE    1 print-factorial-10/0: f-0
==> f-1     (need-factorial 10 nil)
FIRE    2 do-factorial: f-1
==> f-2     (factorial 10 3628800)
FIRE    3 print-factorial-10: f-2
The factorial of 10 is 3628800
CLIPS[11/1]>

This little hack does unfortunately not work with deftemplates unless you also define a need-deftemplate as an exact copy. And, that just doesn't feel right. Also, if you've got a connected constraint in your CE, it will be ignored. I haven't been able to figure out a good way to communicate that type of constraint to the rule matching the need-fact so if you've got one please let me know.

When it comes to explicit, I've tried to keep it as simple as possible. I keep a list of all generated rules and when you execute

CLIPS[11/1]> (explicit print-factorial-10)
; - rule MAIN::print-factorial-10/0

any generated rule for print-factorial-10 is taken away (undefruled).

CLIPS[12/1]> (reset)
<== f-0     (initial-fact)
<== f-1     (need-factorial 10 nil)
<== f-2     (factorial 10 3628800)
==> f-0     (initial-fact)
CLIPS[13/1]> (run)
CLIPS[14/1]>

and that's it really.

That's all it does (for now at least). It's simple and it's not very elegant, but it works. I won't publish the code (yet) because I'm still trying to clean it up. Trying to make it "easier" to build on. I'll share with anyone interested though (send me an e-mail). But I would like to hear if this is a stupid idea in general or if I've done something wrong somewhere. Is there something I havent thought of that might pop up later and turn out to be near impossible to fix?

SudokuDemo.wx.py

2008-01-21T16:37:00.000+01:00

About a week later than I had hoped I've finally managed to finish the Sudoku demo from ClipsJNI. I've tried staying as close to the Java version as possible but there are a few differences. For example, I've added an Open File-button that allows you to load a puzzle from a text file. I've included a few sample puzzles in the zip. The format of the puzzle must be exactly as in the examples: 9 lines of 9 characters (and a newline) each. Characters "1", "2", "3" to "9" are added as-is, all other characters are "added" as blanks (I use "0" in my examples).

I've still got some work to do before I upload this as a pyClips example on SourceForge. I really want to clean up the code and try to make it as easy to understand as possible. I also intend to write a short introduction to using wxPython and pyClips together.

The code is here if you want to have a premature look. If you find any bugs or peculiar behaviour please let me know. Enjoy!

A simple wx.grid.Grid example

2008-01-18T10:47:00.000+01:00

I've had the opportunity to help Dereje with a wxPython question this week. His question was how to add an image to a cell in a wx.Grid. The wxPython demo and docs are great (really) but are not always the easiest to understand and the wx.Grid examples are a bit over-complicated so I've made an implementation that's as simple as can be. Here goes.

>>> import wx
>>> import wx.grid
>>> class MyApp(wx.App):
...     def OnInit(self):
...         frame = wx.Frame(None, -1, title = "wx.Grid - Bitmap example")
...         grid = wx.grid.Grid(frame)
...         grid.CreateGrid(1,1)
...         img = wx.Bitmap("python-logo.png", wx.BITMAP_TYPE_PNG)
...         imageRenderer = MyImageRenderer(img)
...         grid.SetCellRenderer(0,0,imageRenderer)
...         grid.SetColSize(0,img.GetWidth()+2)
...         grid.SetRowSize(0,img.GetHeight()+2)
...         frame.Show(True)
...         return True

>>> class MyImageRenderer(wx.grid.PyGridCellRenderer):
...     def __init__(self, img):
...         wx.grid.PyGridCellRenderer.__init__(self)
...         self.img = img
...     def Draw(self, grid, attr, dc, rect, row, col, isSelected):
...         image = wx.MemoryDC()
...         image.SelectObject(self.img)
...         dc.SetBackgroundMode(wx.SOLID)
...         if isSelected:
...             dc.SetBrush(wx.Brush(wx.BLUE, wx.SOLID))
...             dc.SetPen(wx.Pen(wx.BLUE, 1, wx.SOLID))
...         else:
...             dc.SetBrush(wx.Brush(wx.WHITE, wx.SOLID))
...             dc.SetPen(wx.Pen(wx.WHITE, 1, wx.SOLID))
...         dc.DrawRectangleRect(rect)
...         width, height = self.img.GetWidth(), self.img.GetHeight()
...         if width > rect.width-2:
...             width = rect.width-2
...         if height > rect.height-2:
...             height = rect.height-2
...         dc.Blit(rect.x+1, rect.y+1, width, height, image, 0, 0, wx.COPY, True)

>>> app = MyApp(0)
>>> app.MainLoop()

The above code ought to look something like this:

The class MyImageRenderer is the same as the one from the demo. I modified it slightly so that it loads an image from file rather than from a hex coded string and that you can set the image as a parameter instead of having it defined within the renderer itself.

Kicking a dead horse

2008-01-09T20:49:00.000+01:00

This is my first week of my 8 months of daddy-duty. I've got a bit more free time now, not an obscene amount more, but Eowyn is very easy to take care of and she sleeps quite a few times during the day so I've found myself spending more time thinking about my after-work projects.

So, as I was converting the ClipsJNI demos to wxPython/pyClips (still one to go though) I realised that I might have use for a project I worked on a couple of years ago.

The summer of 2004 I wrote an "application browser" based on wxPython. The easiest way to explain what it does is to think of it as a regular web browser but instead of reading HTML and generating a view it reads something I called wxWML or wxWidgets Markup Language (wxML was taken already) and "generates" a wxPython rich client application.

The project is called wxBrowser and can be found on SourceForge. We used it at work to deploy an application we couldn't get working in the web browsers at that time. Today, there are several options that are much, much better of course. XUL and Eclipse RCF come to mind.

Anyway, I made one last release in the summer of 2005 and I haven't looked at it since. Until today that is.

It turns out that creating a GUI for a Clips application requires you to divide your application into (at least) two distinct parts that are quite tightly coupled. You can try to make the coupling looser by having a more dynamic GUI application that decides what to show on the screen based on Facts in Working Memory (see the Auto Demo for an example of this). But there will still be quite a lot of GUI specific code that won't be all that dynamic. Which, as it turns out, was exactly the problem I wrote the wxBrowser for in the first place.

If I can translate Facts in Clips' Working Memory to wxWML I could use the wxBrowser to provide a GUI for a Clips program. Sure, I'd have to write a whole lot of rules and functions to get it to work but at least I won't have to do it in another language or environment. The wxBrowser itself can be distributed as an .exe which contains pyClips so all you really need is the Clips program to run and you're good to go.

There's of course a down side to all of this which is why I decided to go with the Kicking a dead horse title instead of Blowing new life into old things or something similar. First of all, wxPython code (and the structure of the library) isn't always that easy to understand. This was one of the major stumbling blocks in 2004 and it hasn't gone away. Secondly, there's a reason people use all sorts of tools to generate GUIs and last time I checked there was no tool that could save in Clips' deffacts format. Third, it's an evil bitch-monster of death to debug if something isn't working as expected (which almost ALWAYS is the case when working with GUIs).

Well, luckily I've gotten quite good at kicking dead horses over the years so I'll give this idea a try in the next few weeks. If it doesn't work out, I'll just bring it up again in 2012 or so ;-)

[2008-01-10] Update: Fourth, Client-side scripting. This will actually be less of a problem with Clips as a backend because, well, there wouldn't be any need for client side scripting since the back end is available all the time unlike in an HTTP environment.

New host for pyRete

2008-01-08T19:08:00.000+01:00

I've registered pyRete as a Free Software (GPL) project at Google. The project site is more or less empty at the moment but I intend on moving all of the source code together with examples, instructions and documentation in the next few days.

AutoDemo.wx.py

2008-01-08T16:33:00.000+01:00

I've just finished implementing the ClipsJNI Auto Demo example in wxPython. This time it was easier to do a line by line (more or less) re-write of the Java code, but that's mostly because most of the GUI is controlled from within the Clips file.

Just as with the Wine Demo I had to modify some of the calls to the Clips engine. I added two functions that return Fact indexes instead of Fact addresses, but that's it.

The demo is here. If you've already got Python, wxPython and pyClips installed all you have to do is run python AutoDemo.wx.py at a command line and it should pop right up (same goes for the Wine Demo).

Once I've finished the Sudoku Demo I'll write up some instructions on how to use pyClips and wxPython in general. Where to start, where to get help and such things. Enjoy!

Clips Wine Demo using wxPython

2008-01-05T19:12:00.000+01:00

I finally got enough free time to finish the wxPython Wine Demo I found last week. At first I wanted it to be, more or less, a line by line re-write of the Java version (ClipsJNI) but that turned out to be too difficult in the end.

Instead, I've tried to do as little "over all" damage as possible.

I didn't make the GUI 100% the same because that would have required too much wxPython specific code (and the point is not to show off wxPython anyway). I've also had to make a small change to the Clips code. It turned out that pyClips had trouble converting a MultiField return value containing Fact Addresses, so I added a function that instead returns the Fact Indexes.

Last, but not least, I designed the GUI using a wxPython XRC editor. That way I didn't have to write all that boilerplate GUI code to create, add and configure all of the widgets in the application.

I have kept the code for asserting facts exactly as in the ClipsJNI example even though that's not really the way to do it in Python.

All of the above are things that have been added or more complicated in Python/pyClips but there are other things as well. Things that could have been done easier. For example, there's no point in sorting the Facts in Clips, that can be done automatically in the ListCtrl widget (if you want).

The code is here. At least for now, I'm hoping it can be hosted on SourceForge together with the pyClips project but that's up to Franz so I'll have to wait and see what he says first. If you find any bugs or have any other comments, please let me know.

Enjoy!

WineDemo.wx.py

2007-12-30T19:50:00.000+01:00

Today I found, buried deep in the Playground folder on my hard disk, a half finished wxPython implementation of the WineDemo from Gary's ClipsJNI package. I'd completely forgotten about it but I still think it's worth finishing. Not having a good example in Python/pyClips is actually very annoying. Especially if you're, like me, trying to promote Python as a good way to provide a GUI for Clips programs.

So I started going through the code, trying to finish it earlier today but that made me remember why I stopped in the first place. I'm having a lot of trouble converting these two lines of Java into Python:

String evalStr = "(WINES::get-wine-list)";
MultifieldValue pv = (MultifieldValue) clips.eval(evalStr);

The conversion itself is quite simple but I can't get pyClips to evaluate the function, I keep getting this:

>>> clips.Eval("(WINES::get-wine-list)")

Traceback (most recent call last):
File "", line 1, in 
clips.Eval("(WINES::get-wine-list)")
File "C:\Python25\lib\site-packages\clips\_clips_wrap.py", line 3430, in Eval
return _cl2py(_c.eval(expr))
ClipsError: C10: unable to evaluate expression

~~I guess I should~~ I have reported it as a bug.

Constraint Programming in Clips

2007-12-27T09:35:00.000+01:00

A couple of weeks ago, I found Michel Futtersack and Jean Marc Labat's research on Constraint Programming in Clips from 1997. I've spent part of Christmas going through the source code. It's quite an interesting "read" if you're a Clips user. They've implemented a backtracking search algorithm with forward checking. But the really cool thing is that they've packaged it all as a reusable component (in CCP.clp) to be used as the main driver to find solutions for any Constraint Satisfaction Problem (CSP).

They've also provided some examples, one of them is the classic N-Queens. But I've modified it a bit to make it easier to try out different sizes of the chessboard. Also, their implementation is based around either finding all solutions to a problem or finding solutions one by one until the user says stop. This makes it a bit difficult to time the algorithm and compare it against, for example, Drools' solver module. What I want it to do is to find the first solution and then quit, without any user interaction.

So here's what I changed:

The first question the main driver loop asks is: "Do you want all solutions?" and if you answer "No" the next question is "Do you want another solution?" So I can easily get what I want by short-circuiting the yes-or-no-p function in CCP.clp to always return FALSE (No).

(deffunction MAIN::yes-or-no-p (?question)
(printout t ?question " No" crlf)
(return FALSE))

I've also turned on the customzied printing of solutions (remove or comment out print-solution and remove the comments from to_customized_printing) because it's easier to read the result in that form.

When it comes to the specifics of the N-Queens problem (in n-queens.clp) they've put the definition of the solution space in two different deffacts: queens and chessboard, which unfortunately also binds the n implicitly.

For example, instead of having:

(deffacts PROPAG::queens
(var (name x1)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x2)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x3)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x4)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x5)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x6)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x7)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x8)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x9)  (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x10) (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x11) (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
(var (name x12) (possible-values (create$ 1 2 3 4 5 6 7 8 9 10 11 12)))
)

I wrote a function to generate and assert var facts:

(deffunction PROPAG::generate-var (?i $?v)
(assert (var (name (sym-cat x ?i)) (possible-values $?v))))

there's also a matching rule:

(defrule generate-vars
(generate-vars)
(problem-size ?n)
=>
(loop-for-count (?i ?n)
(bind ?v (create$))
(loop-for-count (?j ?n)
   (bind ?v (insert$ $?v (+ (length$ $?v) 1) ?j)))
(generate-var ?i $?v)))

and the deffacts becomes:

(deffacts PROPAG::queens
(generate-vars))

Ok, maybe it's not the prettiest solution, but it gets the job done and I don't have to manually define 64, 128 or 256 var facts containing 64, 128 or 256 items long multislots. There's also similarly a function, a rule and a deffacts for the chessboard facts.

The problem size (marked with red above) is now instead specified in an implied deftemplate which is injected at the batch file level. So an N-Queens of size 12 can look like this:

CLIPS> (load "CCP.clp")
+%%%$!*****+******
TRUE
CLIPS> (load "n-queens.clp")
+$!%$!!*******
TRUE
CLIPS> (deffacts PROPAG::problem-size
(problem-size 12))
CLIPS> (watch statistics)
CLIPS> (reset)
CLIPS> (run)
Do you want all the solutions ?  No
the problem is solved
Do you want another solution ?  No
No more solution

I found 1 solution(s)



* * * * * * X * * * * *
* * * * * * * * X * * *
* * * * * * * * * * X *
* * * * X * * * * * * *
* X * * * * * * * * * *
* * * X * * * * * * * *
* * * * * * * * * * * X
* * * * * * * * * X * *
* * * * * * * X * * * *
* * * * * X * * * * * *
X * * * * * * * * * * *
* * X * * * * * * * * *


2181 rules fired        Run time is 1.101 seconds.
1980.92643051771 rules per second.
99 mean number of facts (116 maximum).
1 mean number of instances (1 maximum).
5 mean number of activations (23 maximum).
CLIPS>

I really have no idea if CCP is fast or slow but here are some numbers:

 n | rules | seconds
---+-------+-------
04 |    31 | 000.01
06 |   101 | 000.02
08 |   162 | 000.04
10 |   577 | 000.18
12 |  2181 | 001.06
16 |  2584 | 002.97
20 |   613 | 001.05
24 |  2709 | 012.95
28 |   699 | 002.89
32 |  9284 | 130.72

I'm guessing it's the heuristics of the forward checking (or possibly the structure of the problem) that makes the number of rules fired and the run-time to differ so much between different sizes of the chessboard. I was really expecting n = 28 to be "harder" than n = 24 but... apparently not.

If you also want to experiment with N-Queens in CCP, the modified files can be found here (CCP.clp), here (n-queens.clp) and here (n-queens.bat). They won't work with Clips 6.30 (Beta) though because of a problem with Logical CE's but I think Gary's on top of that already. Once a new release is out it will be interesting to see if the new and improved Rete implementation of Clips 6.3 will reduce the run-time and/or possibly the number of rules fired as well.

MultiField variables in pyRete

2007-12-14T11:20:00.000+01:00

I've been thinking about MultiField variables quite a bit these past few weeks. I want to fit them into pyRete. However, they're a bit different from SingleField variables - as this snippet shows:

CLIPS> (deftemplate Person (multislot name))
CLIPS> (assert (Person (name Astrid Ingrid Eowyn Lindberg)))
[fact-1]
CLIPS> (defrule match-names
         (Person (name $?n1 $?n2))
        =>
         (printout t $?n1 " " $?n2 crlf))
CLIPS> (run)
() (Astrid Ingrid Eowyn Lindberg)
(Astrid) (Ingrid Eowyn Lindberg)
(Astrid Ingrid) (Eowyn Lindberg)
(Astrid Ingrid Eowyn) (Lindberg)
(Astrid Ingrid Eowyn Lindberg) ()

As you can see a MultiField variable can, and will, hold all possible combinations of values found in a multislot.

Given the current design of pyRete this means that I'll have to implement functionality to generate all combinations *within* a Node's match method. I'm slightly worried that this might make the processing quite a bit slower (I believe it's slower in Clips as well but I haven't benchmarked it so I can't really say for sure).

The other thing is that in Clips there's no way of nesting multifield structures. You cannot have a multifield of multifields. When it comes to Python, nested tuples/lists/dicts are common and I'd like to end up with an implementation that supports them.

The question is how to best do that?

In pyRete today there's no equivalent to Single or MultiField variables. Variables are bound to fact-instances and not parts of a fact (attributes of an object). You *can* introduce a variable in the RHS that binds to a part of a fact, but that cannot be done using pattern-matching.

>>> def rule(foo = Foo):
...   if foo(something = 100):
...     something_else = foo.something_else
...     # ...

So what we're talking about here is basically the possibility to do this:

>>> def rule(foo = Foo):
...   if foo(something = 100, something_else = something_else):
...     # ...

However, this will of course let you do far more sophisticated things than that. For example, you could "filter" out facts based on attribute values in another fact:

>>> def rule(foo = Foo, bar = Bar):
...   if foo(something = var) and bar(something_else = var):
...     # ...

My thoughts so far are that I'll use __ as Clips use $? and _ as Clips use ?. Named Single and MultiField variables would be _foo and __foo respectively. Variables will default to SingleField so foo and _foo are really the same thing.

Unfortunately those types of variable names already have a meaning in Python. Though I'm not sure I can afford to care about that since there's really no other way to distinguish variable names without breaking syntax rules (which I'm hoping to avoid).

Also, I'd like to introduce a way of specifying a minimum and possibly a maximum number of values a MultiField should take on. That would allow you to, for example, say that all MultiField variables must have at least one value. My Clips example would instead give the following result:

(Astrid) (Ingrid Eowyn Lindberg)
(Astrid Ingrid) (Eowyn Lindberg)
(Astrid Ingrid Eowyn) (Lindberg)

I don't really have a suggestion for syntax for that though, _foo_1toN doesn't really feel right :-)

If you've got any suggestions or thoughts about this I'd love to hear them.

Guy Steele's keynote from OOPSLA 1998

2007-12-12T22:20:00.000+01:00

I found Guy Steele's keynote from OOPSLA 1998 on Google Video a few weeks ago. It's quite funny (both peculiar and ha-ha) and well worth watching.

A week in NYC

2007-11-30T21:47:00.000+01:00

Tomorrow at this time (Swedish time that is) Sofia, Eowyn and I will land at Newark Liberty International Airport. We're having a weeks well earned vacation in New York City. It's a nine hour flight across the Atlantic so the toughest question at this point is what books to pack?

Added some functionality in the Clips regexp library

2007-11-29T20:51:00.000+01:00

Today I spent about three hours on a train between Stockholm and Gothenburg. That was nearly enough to complete the functionality in the small regexp library for Clips I wrote a few weeks ago.

I've added findall, split and sub(stitute) functions which work likeso:

CLIPS> (load "regexp.clp")
:!!!!!!
CLIPS> (findall "a" "Today I spent about three hours on a train between Stockholm and Gothenburg")
("4 4 "a"" "15 15 "a"" "36 36 "a"" "40 40 "a"" "62 62 "a"")
CLIPS> (split "a" "Today I spent about three hours on a train between Stockholm and Gothenburg")
("Tod" "y I spent " "bout three hours on " " tr" "in between Stockholm " "nd Gothenburg")
CLIPS> (sub "a" "A" "Today I spent about three hours on a train between Stockholm and Gothenburg")
"TodAy I spent About three hours on A trAin between Stockholm And Gothenburg"

Ok, my examples might not be the best but you get the idea. Both split and sub also take an optional parameter ?max which allows you to limit the number of splits and substitutions:

CLIPS> (sub "a" "A" "Today I spent about three hours on a train between Stockholm and Gothenburg" 2)
"TodAy I spent About three hours on a train between Stockholm and Gothenburg"

The library consists of two files: regexp.clp and regexp-test.bat (requires unittest.clp).

[2007-11-30] Update: I found a bug in the search function which caused a string not to be properly searched (the search ended too early). Apparently my test cases are not very good...

Yet another starting-over post

2007-11-19T16:52:00.000+01:00

This is the fifth time I've decided to start over (more or less from scratch) in my attempt to produce a Rete rule engine in Python. It' irritating that it's so hard to get the pyRete code into a shape I'm pleased with and I've been feeling kind of low these past few weeks since my last attempt to beat the RuleCompiler into submission failed miserably.

I know that developing a rule engine is no easy task and that others have devoted large portions of their lives doing it so 2 years isn't that much, really. I'd feel a whole lot better though if I was sure that I won't write this post again in a year or so.

Give one. Get one.

2007-11-12T18:51:00.000+01:00

As of today, the G1G1 program of OLPC has started. Unfortunately the program is only intended for USA and Canada but there are ways to get them to Europe (and elsewhere) so I may just have to order one (for Eowyn of course). $400 is only about 2500 SEK so it's definitely worth it even if the shipping will cost loads.

Another Clips and Lisa comparison

2007-10-22T21:59:00.000+02:00

I spent this evening with Emacs, CLisp and Lisa. I wanted to get this piece of Clips code working:

|CLIPS> (deftemplate movie
|  (multislot title))
|CLIPS> (deffacts movies
|  (movie (title "A" "B" "C"))
|  (movie (title "B" "C" "D"))
|  (movie (title "C" "D" "E")))
|CLIPS> (defrule chain
|  ?m1 <- (movie (title $? $?link&:(> (length$ $?link) 0)))
|  ?m2 <- (movie (title $?link $?))
|  (test (neq ?m2 ?m1)) ; Avoid infinite chains because of
|                       ; movie titles like "Liar Liar".
| =>
|  (printout t (fact-slot-value ?m1 title) " " (fact-slot-value ?m2 title) crlf))
|CLIPS> (reset)
|==> Activation 0      chain: f-1,f-2
|==> Activation 0      chain: f-2,f-3
|==> Activation 0      chain: f-1,f-3
|CLIPS> (run)
|("A" "B" "C") ("C" "D" "E")
|("B" "C" "D") ("C" "D" "E")
|("A" "B" "C") ("B" "C" "D")

Note how elegantly $?link matches any number of elements in a multislot.

Unfortunately, there are no multislots in Lisa. But, you're allowed to add a list (or even a list of lists) to a slot. Only thing is that you either have to match it as-is or provide your own predicate function to perform whatever test you need done. Here's what I came up with:

|LISA-USER> (deftemplate movie ()
|             (slot title))
|#[STANDARD-CLASS MOVIE]
|LISA-USER> (deffacts movies ()
|             (movie (title '("A" "B" "C")))
|             (movie (title '("B" "C" "D")))
|             (movie (title '("C" "D" "E"))))
|(#[DEFFACTS
|   MOVIES ; (#[MOVIE ; id -1 #x19FF2789] #[MOVIE ; id -1 #x19FF2ADD]
|    #[MOVIE ; id -1 #x19FF2E31])
|   #x19FF2EDD])
|LISA-USER> (defun overlap? (list-1 list-2)
|             (if (not (equal list-1 list-2))
|                   (dotimes (index (min (length list-1)
|                                        (length list-2)))
|                     (if (equal (subseq list-1 (- (length list-1) index 1) (length list-1))
|                                (subseq list-2 0 (+ index 1)))
|                       (return-from overlap? t))))
|             nil)
|OVERLAP?
|LISA-USER> (defrule chain ()
|             (?m1 (movie (title ?title1)))
|             (?m2 (movie (title ?title2)))
|             (test (overlap? ?title1 ?title2))
|             =>
|             (format t "~A ~A~%" ?title1 ?title2))
|#[RULE CHAIN]
|LISA-USER> (reset)
|T
|LISA-USER> (run)
|(A B C) (B C D)
|(B C D) (C D E)
|(A B C) (C D E)
|3

Not quite as elegant... but it works. I never managed to get the not equal test working in the rule so I had to place it in the overlap? function. Other than that, I think they're about as equivalent as they can get.

A small Regular Expression library for Clips

2007-10-21T19:03:00.000+02:00

Inspired by the first chapter in Beautiful Code I've decided to try and implement a small regular expressions library in Clips. The code that's discussed in the book is taken from another book; The Practice of Programming and the match code, written by Rob Pike, is amazingly enough only about 35 lines of C.

I can say straight away that my code (roughly 200 lines) is *not* very beautiful. But then again, that wasn't the point of the exercise.

Seeing as this is supposed to become a library I've implemented it a bit differently as well. To begin with, I've done two separate functions: match and search. They behave (roughly) as described in the docs for Python's re module: match only matches from the beginning of the string (roughly equivalent to Rob's matchhere function) and search matches anywhere.

I've started working on findall, split and sub (substitute) but it's taking slightly longer to finish them than I've expected. I've also been *thinking* about implementing:
1) character sets; for example \s, \d and \w
2) match groups; so that you could write "(.+) \1" and have it match repeated character sequences
3) and some more quantifiers; +, ? and possibly also {m[,n]}, {m[,n]}?, *?, +? and ??.

but I don't know. The code is complex enough as it is and I think I'd take too long doing it (according to the book, it only took Rob about two hours to finish his implementation and I've already spent a *lot* more time on this than that ;-)

Here's how it works:

CLIPS> (load "regexp.clp")
:!!!
TRUE
CLIPS> (match "do"  "Lorem ipsum dolores sit amet")
nil
CLIPS> (match ".* "  "Lorem ipsum dolores sit amet")
"Lorem "
CLIPS> (search "do" "Lorem ipsum dolores sit amet")
(13 14 "do")

The code is available here and I've also prepared a batch file with unit tests which can serve as an example of how to use the functions. NOTE! You will also have to have unittest.clp in order to run it.

If you find any bugs, please let me know. Enjoy.

Going from Clips to Lisa

2007-10-17T17:06:00.000+02:00

I'm currently experimenting with (and thinking about moving my current after-work projects to) Lisa. It's close enough to Clips to make it very easy to pick up but there are a few things that will take some time to get used to.

CL-USER> (in-package LISA-USER)
#[PACKAGE LISA-USER]
LISA-USER> (deftemplate foo
    (slot name)
    (slot age))
; Evaluation aborted
LISA-USER> (deftemplate foo ()
    (slot name)
    (slot age))
#[STANDARD-CLASS FOO]
LISA-USER> (assert (foo (name "Johan") (age 34)))
#[FOO ; id 1 #x1A015B01]
LISA-USER> (defrule remove-old-people
      ?foo <- (foo (age ?age&:(> ?age 30)))
      =>
      (retract ?foo))
; Evaluation aborted
LISA-USER> (defrule remove-old-people
      (?foo (foo (age ?age (> ?age 30))))
      =>
      (retract ?foo))
; Evaluation aborted
LISA-USER> (defrule remove-old-people ()
      (?foo (foo (age ?age (> ?age 30))))
      =>
      (retract ?foo))
#[RULE REMOVE-OLD-PEOPLE]
LISA-USER> (agenda)
#[ACTIVATION (INITIAL-CONTEXT.RETRACT-PEOPLE-OVER-30 (F-1) ; salience = 0)
#x19FAED25]
#[ACTIVATION (INITIAL-CONTEXT.RETRACT-PEOPLE-OVER-30 (F-1) ; salience = 0)
#x19FAED25]
For a total of 2 activations.
; No value
LISA-USER> (facts)
#[FOO ; id 1 #x19FAEBDD]
For a total of 1 fact.
; No value
LISA-USER> (run)
1
LISA-USER> (facts)
For a total of 0 facts.
; No value
LISA-USER>

Each of the ; Evaluation aborted lines marks where I was sent into the debugger. I'm not sure how I managed to get two activations but I suspect that part of the rule was already created when I got the error of not having specified any keywords. No warning about redefining the rule though!

Anyway, Lisa allows me to use the full power of Common Lisp side by side with a Rete-engine and I must admit I kind of like that idea. Lately, one of the things I've come to miss in Clips is the ability to define rules dynamically. I've tried using eval:

CLIPS> (eval "(defrule blah (whatever) =>)")
[EXPRNPSR3] Missing function declaration for defrule.
FALSE

but without success.

Whenever such a need has appeared I have used Python to dynamically generate the source code which I then load and run in Clips but I'd prefer to keep it all in one place and since I know better than to have delusions about pyRete performance I *think* this might be the way to go.

[2007-10-17] Update: Less than an hour after I posted this I learned that there is indeed a way to generate rules dynamically. The function is called build and is described in chapter 12.3.6 Evaluating a Construct within a String of the Clips Basic Programming Guide. Thanks Gary and Peter for pointing this out.

Cracking Go?

2007-10-13T19:00:00.000+02:00

The October issue of IEEE Spectrum has a very interesting article about Go AI players and whether or not one can be created that will beat the best human players. The article is written by Feng-Hsiung Hsu. He was one of the people in the team behind Deep Blue, the chess-playing program that beat Garry Kasparov in 1997, so I guess he knows what he's talking about.

I was a bit disappointed though, after having read the article, since I got the feeling that the solution was more or less the Deep Blue program running on faster hardware and having been enhanced using null-move pruning and caching results of life-and-death analysis. It all sounds a bit... too simple. Life-and-death analysis is tricky business indeed and it doesn't help at all when he basically says that all the leading Go programmers today are too narrow minded in what they do and that their approach(es) won't ever lead to any decent Go AI players.

Until he provides some more details about this I'm going to have to agree with Luke Biewald that he himself may very well have underestimated the problem. It will however be very interesting to see what they come up with in the next few years in the research efforts that Microsoft (where he works) sponsor.

Drools puzzle #2 winner announced

2007-10-08T21:33:00.000+02:00

Gernot just sent out an e-mail announcing that Scott Reed is the winner of Drools Puzzle #2. I'm looking forward to another puzzle. So hurry up Scott! ;-)

Erlang

2007-09-24T18:43:00.000+02:00

All the cool kids are doing it! Erlang seems to be all the rage at the moment. It's (almost) difficult to find a blog that isn't about trying or learning Erlang. The first time I heard about it I thought it was a joke, then I saw the video and was sort of convinced it was a joke but when I saw Joe's book in the book store last week I thought I'd give it a try.

The promise of Erlang is that it's a breeze to write highly parallel, distributed, fault-tolerant systems. Apparently an Erlang program run on a quad-core computer will run (close to) four times as fast without changes to source code.

I haven't finished the book or anything so I can't really say much about the language yet. It looks interesting but I'm not sure it will live up to the expectations. But it will at least give me a decent excuse to get a dual-core computer ;-)

Drools puzzle #2

2007-09-13T22:51:00.000+02:00

The second Drools puzzle was a lot trickier than the first one. It took a while for me to figure out a solution I was content with. I re-wrote the application three times before settling on this one. It's a rather simple generate-and-test solution but it works and it's not unreasonably slow.

CLIPS> (batch ".../family.bat")
TRUE
CLIPS> (clear)
CLIPS> (unwatch all)
CLIPS> (load "family.clp")
:::%%%********!!
TRUE
CLIPS> (solve)
Who is married to whom and what are their sons called?
1 solution(s).
Snyder is married to Edith and their son is Victor
Locker is married to Doris and their son is Henry
Abel is married to Luisa and their son is Albert

CLIPS>

I hope more people have sent in solutions this time and that the next puzzle will be as good as this one.

Beautiful code

2007-09-12T21:20:00.000+02:00

Today, I stumbled on a Google Tech Talk video where Jon Bentley talks about three implementations of Quicksort. Apparently it was his contribution to the book Beautiful Code (O'Reilly). His chapter is called The Most Beautiful Code I Never Wrote. There are several interesting chapter titles and all author royalties are donated to Amnesty International.

I am *so* ordering this book.

The stable marriage problem.

2007-09-02T22:30:00.001+02:00

Awaiting the next Drools puzzle I decided to write a solver for the stable marriage problem:

Given a set of N men and N women, marry them off in pairs after each man has ranked the women in order of preference from 1 to N, {w1, ..., wN} and each woman has done likewise, {m1, ..., mN}. If the resulting set of marriages contains no pairs of the form {mA,wB}, {mC,wD} such that mA prefers wD to wB and wD prefers mA to mC, the marriage is said to be stable.

It's an old problem and you can read lots more about it here [PDF], here and here, and there's a solver Applet here. I haven't googled for source code and solutions to the problem but there are some descriptions of algorithms and ways to go about it (using a procedural language) in the links above.

I aimed at a small rule set so it might not be super efficient but I don't think it's particularly bad either. On my machine the limit seems to be at around 15, 16 men and women. If you try it with more than that it takes a long, *long* time to finish. I should probably also mention that my solver disagrees sometimes with the solver applet I linked to above. I do believe that the solver applet is wrong though but if you can spot mistakes in my code, please let me know.

Enjoy!

CLIPS> (batch "C:/Program/CLIPS/drools-puzzle/marriage.bat")
TRUE
CLIPS> (clear)
CLIPS> (load "marriage.clp")
%%%***
TRUE
CLIPS> (load "marriage-data-16.clp")
$
TRUE
CLIPS> (reset)
CLIPS> (run)
man-3 (#10) is married to woman-1 (#4)
man-11 (#4) is married to woman-8 (#9)
man-16 (#3) is married to woman-14 (#1)
man-8 (#2) is married to woman-4 (#2)
man-14 (#6) is married to woman-3 (#3)
man-5 (#1) is married to woman-2 (#3)
man-1 (#11) is married to woman-11 (#9)
man-4 (#1) is married to woman-6 (#2)
man-15 (#1) is married to woman-15 (#2)
man-13 (#2) is married to woman-16 (#2)
man-12 (#5) is married to woman-10 (#1)
man-7 (#5) is married to woman-9 (#1)
man-9 (#8) is married to woman-5 (#8)
man-10 (#1) is married to woman-7 (#5)
man-6 (#5) is married to woman-12 (#1)
man-2 (#2) is married to woman-13 (#1)
CLIPS>

Duck typing, again.

2007-08-26T10:24:00.000+02:00

I have previously posted about duck-typing and whether or not it should be possible to write a rule that doesn't check the Fact object's class name but instead check the existance of the attributes that are tested in Alpha and Beta nodes.

A couple of months ago I concluded that it's best to leave that sort of thing out and instead require that the rule's definition include class names for each variable.

However, things are not so simple. Just because pyRete won't allow you to compile a "duck-typed" Rete Network doesn't mean the Fact objects passing through it will play nice as well.

Consider the following rule:

>>> @pyRete.rule
... def foo(a= Foo):
...   if a.n > 10:
...     pass

and this Fact class:

>>> class Foo(pyRete.Fact):
...   def __init__(self, n):
...     self.n = n

Using it as defined won't cause any problems but unfortunately (or luckily, depends a bit on how you view the world ;-) there's no stopping this type of behaviour:

>>> obj = Foo(n = 10)
>>> obj.n
10
>>> del obj.n
>>> obj.n

Traceback (most recent call last):
  File "", line 1, in 
  obj.n
AttributeError: 'Foo' object has no attribute 'n'

That makes it obviuos that the ObjectType node test won't be sufficient for pyRete. Even though the above (using del on an instance's property) is probably rather rare there's no way to *know* if the public interface of the Fact instance has been modified or not.

I think I'm going to have to implement the Rete Network more or less as described in Forgy's 1979 paper where he tests the length and the contents of a Fact object in order to categorize it properly. In the 1982 article it appears as if these tests have vanished and have been replaced by a "type" symbol in the first element of each fact. Which, I believe, is now usually known as an ObjectType node.

Now, the only question is: Should I distribute the tests among the Alpha and Beta nodes or should I extend the ObjectType node with some property existance tests as well?

Drools puzzle #1

2007-08-20T21:17:00.000+02:00

I completely missed the announcement for the Drools puzzles but it looks like lots of fun. Here's my solution to the first puzzle using Clips. You run it by executing the batch file:

CLIPS> (batch "... /ages-of-the-sons.bat")
TRUE
CLIPS> (clear)
CLIPS> (load "ages-of-the-sons.clp")
%%!***
TRUE
CLIPS> (generate-ages)
FALSE
CLIPS> (run)
What are the ages of the three sons of the old man?
2, 2 and 9
10 rules fired
40 mean number of facts (44 maximum).
0 mean number of instances (0 maximum).
4 mean number of activations (8 maximum)

Even more profiling...

2007-08-16T16:29:00.000+02:00

Ok, this will be my last post about (this round of) profiling. Honest!

I have now decided on which implementation to use so I thought I should take some time to describe it.

It *is* a bit of a hack, but it allows me to remove the eval calls in the OO implementation. It's not as fast as the flattened, procedural Rete implementation. But it's quite close and, more importantly, I believe it's easier to implement and add optimizations to it.

Here's the profiling output:

using 4000 facts
plain OO impl. Assert took 6.0490000248 s and produced 79735 facts
hack OO impl. Assert took 3.16399979591 s and produced 79735 facts
inline impl. Assert took 2.68400001526 s and produced 79735 facts

As you can see, the difference is about half a second between the hack and the inline version.

using 10000 facts
plain OO impl. Assert took 15.2119998932 s and produced 199735 facts
hack OO impl. Assert took 7.88100004196 s and produced 199735 facts
inline impl. Assert took 7.49099993706 s and produced 199735 facts

Luckily, that difference remains "constant" for any size of the data set and the difference between the plain OO and the hack remain at about 50%.

Now, to talk about how it's done. In the plain OO version, the Rete Compiler makes an instance of AlphaTestNode like this:

>>> a1 = rete.AlphaTestNode('a.n > 10')

The AlphaTestNode is defined as:

>>> class AlphaTestNode(object):
...     def __init__(self, expr):
...         self.expr = expr
...         self.nexts = []
...     
...         self.right_activate = self.activate
...     
...     def activate(self, tag, token):
...         if eval(self.expr, token):
...             for next in self.nexts:
...                 next.right_activate(tag, token)

whenever activate is called on the a1 instance it will evaluate the expression 'a.n > 10' using the token, and all bindings (variable name and value) found in it, as execution scope. In order to remove the expensive eval call we have to "inline" the expression to be tested. A macro would have been very handy here (the Lisp type) but I don't expect them to show up in Python any time soon so instead we'll have to have a work-around. If we remove the class definition and replace it with a function:

>>> def make_AlphaTestNode(expr, var):
...     class_definition = \
... """class GeneratedAlphaTestNode(object):
...     def __init__(self):
...         self.nexts = []
...         self.right_activate = self.activate
...     
...     def activate(self, tag, token):
...         %s = token['%s']
...         if %s:
...             for next in self.nexts:
...                 next.right_activate(tag, token)""" % (var, var, expr)
...             
...     exec(compiler.compile(class_definition, '__generated__', 'exec'))
...     return GeneratedAlphaTestNode()

we can make an instance of AlphaTestNode equivalent to the one above (a1) using:

>>> a1 = rete.make_AlphaTestNode('a.n > 10', 'a')

The "extra" parameter ('a') is used to generate a statement to bind the variable (a), found in the token, locally before execution. This is necessary because we cannot specify token as the execution context (as we can when using eval or exec).

The parameter class_definition will look like this when it's sent to the compile method:

>>> class GeneratedAlphaTestNode(object):
...     def __init__(self):
...         self.nexts = []
...         self.right_activate = self.activate
...
...     def activate(self, tag, token):
...         a = token['a']
...         if a.n > 10:
...             for next in self.nexts:
...                 next.right_activate(tag, token)

executing the code object that is returned by compile causes the class GeneratedAlphaTestNode to become available in local scope so all that is left to do is to make an instance and return it.

Ugly!? Incomprehensible!? Yes, sir! But it shaves a lot of time off of fact evaluation in the Rete Network so I don't care!

Next up is to implement a second pass in the compilation step to remove "un-necessary" nodes. This is actually the main reason I chose this design over the inlined, flattened, procedural implementation. Optimizing travseral of the Rete Network in an OO implementation means traversing it and moving "next pointers" from one node to another whilst in procedural code I would have to handle it on the level of source code (text) which feels a lot harder (I can't think of an easy way to do it so if you've got suggestions please let me know).

Corrected profiling results

2007-08-13T23:02:00.000+02:00

It's official: I'm a dimwit!

The inline versions of the profiling tests I presented last week are wrong. The correct time for the plain inline version is in fact somewhere between a third to half of the OO implementation.

The inlined version was incorrectly using eval calls to test the conditions. The whole speed-up stems from replacing, for example,

>>> eval('a.n > 10', token)

with

>>> a = token['a']
>>> a.n > 10

The reason that I can lose the eval in the inline version is because it works by translating source code from the rule definition to regular Python code, which is then compiled into a function object which is invoked at run-time.

In the OO-version, the test to be performed is bound to the instance of the node and since the activate method is "pre-defined" we need eval in order to execute whatever test is stored in the instance. Most activate methods besically looks like this:

>>> def activate(self, tag, token):
...   if eval(self.test, token):
...     # store in mem and propagate

There might be a way of doing the same sort of "trick" to get rid of the eval in the OO-implementation as well. I'll have to think about that though.

More profiling

2007-08-09T21:24:00.000+02:00

Turns out I was right about the error in the current pyRete version. I hand made a Rete network by connecting nodes from the refactored Rete implementation and it turned out to be as fast as (and sometimes faster than) the one based on dictionaries/functions.

Whilst the one based on dicts and functions is in some was easier to handle and deal with it also has some serious drawbacks. First and foremost it saves state at *each* node. This can probably be dealt with but then I'd have to write some boiler-plate code to handle when and when not to store tokens and that was the whole point of the implementation, to reduce the boiler-plate code. Secondly, it can be harder to wrap your head around since you'd have to look at both where the function is defined and where it is called in order to find out the exact behaviour of a node. It's not magic or anything but it may be confusing at first.

Given these two drawbacks of the dicts and functions implementation I decided that I wasn't going to use it. At all... unless I could find a way to perform function inlining and that the inlined version was faster than an optimized OO-Rete network.

So, now I've got no less than six implementations of a small Rete network[1]:
1) the current pyRete implementation (which is quite obviously just plain wrong).
2) the experimental dicts and functions implementation
3) the refactored OO-implementation
4) an optimized version of 3[2]
5) an implementation using function inlining based on 2
6) an optimized version of 5[2]

Here are the results (I've run these about ten times and the numbers below are typical) for 2 to 6 using 4000 facts:

2) took 6.58899998665 s => 79735 facts
3) took 5.98900008202 s => 79735 facts
4) took 5.70799994469 s => 79735 facts
5) took 5.63800001144 s => 79735 facts
6) took 5.52800011635 s => 79735 facts

Inlining apparently speeds up the matching but not with much and I'm not sure it's worth the effort. It would be cool though to generate a large blurb of code and see if it can be optimized by some other program like psyco or possibly one of the bytecodehacks or some such thing. I haven't looked for optimizers but I believe I will have to if I am going to get something out of the inlining implementation.

All in all. This week's been good fun looking at different implementations but it's time to get back to work and make sure that the pyRete code in the subversion repository works as expected.

[1] Here is the Rete network I'm using. Memory nodes are not shown.

#                       TYPE
#                       
#   TOP         ALPHA {--+     TYPE
#                            
#    +--} JOIN {--+    ALPHA {--+
#                      
#           +--} JOIN {--+
#                 
#                  +--} BETA
#                        
#                         +--} PROD

[2] I have removed a few "unneccessary" memory nodes. But since I believe that that sentence can easily be misunderstood I'll try to explain a bit more.
I have, for example removed storage of tokens at nodes which are never "read" in other parts of the network. For example the Beta Node places Tokens directly into the Production Node instead of going via a Beta Memory Node. It is "last" in the network and the Beta Memory would have fed the Production Node. Also, the first AlphaMemory has been converted into a LeftInputAdapter and sends Tokens directly to the second Join instead of going thru a DummyJoin with a DummyTopNode.

Some profiling results

2007-08-08T22:08:00.000+02:00

I've made a small test to see how my experimental Rete implementation is performing. I'm using a very simple rule that generates a lot of tokens:

>>> @pyRete.Rule
... def rule(a = Foo, b = Foo):
...   if a.n > 10 and b.n < 20 and a.n > b.n:
...     print a.n, b.n

where Foo is a value object.

I'm comparing against the pyRete version currently in Subversion and the results are not looking good. In fact, they're looking *so* bad, I believe it is because of an error in the pyRete implementation rather than a difference in time for object+ method lookups (which is what I hoped to test).

I'm only timing the assert_fact method calls (and the index loop):

... start = time.time()
... for i in range(size):
...   pyRete.assert_fact(Foo(n=i))
... stop = time.time()

so Rete compilation, parsing and such is not included. Here are the results:

using 50 facts [Foo(0), Foo(1), ..., Foo(49)]
rule: +O+O+A+A+B+P
pyRete implementation took 0.210000038147 s => 735 facts
expRete implementation took 0.0599999427795 s => 735 facts

using 100 facts [Foo(0), Foo(1), ..., Foo(99)]
rule: +O+O+A+A+B+P
pyRete implementation took 0.871000051498 s => 1735 facts
expRete implementation took 0.149999856949 s => 1735 facts

using 200 facts [Foo(0), Foo(1), ..., Foo(199)]
rule: +O+O+A+A+B+P
pyRete implementation took 3.51600003242 s => 3735 facts
expRete implementation took 0.319999933243 s => 3735 facts

using 300 facts [Foo(0), Foo(1), ..., Foo(299)]
rule: +O+O+A+A+B+P
pyRete implementation took 7.84099984169 s => 5735 facts
expRete implementation took 0.481000185013 s => 5735 facts

using 400 facts [Foo(0), Foo(1), ..., Foo(399)]
rule: +O+O+A+A+B+P
pyRete implementation took 14.0199999809 s => 7735 facts
expRete implementation took 0.671000003815 s => 7735 facts

Clearly, something's not right. Going from 300 to 400 fact objects shouldn't take nearly twice as long.

Now, in order to be fair I should also mention that the experimental Rete implementation is hand-made (but it's topology is identical to that pyRete generates) and doesn't include things like callbacks for debugging, compilation, activations and statistics. However, that cannot account for *all* of the extra time, maybe some of it. I don't know.

I will try to make a hand-made, slimmed OO Rete Network tomorrow to see if I can get a fair comparison.

Experimental Rete implementation

2007-07-30T20:37:00.000+02:00

Last week I tried a "new" approach for pyRete's Rete implementation. At the moment I'm using a number of objects linked together such that they make up a Directed Acyclic Graph. Which also happens to be the way most other implementations handle it (I think).

Take for example object type tests. In pyRete they are implemented such that the Rule Compiler instantiates an ObjectTypeNode and initializes it with the type to test against. Later on it connects the instance to the "next" nodes in the Rete Network (usually Alpha Nodes). The ObjectTypeNode basically looks like this:

>>> class ObjectTypeNode(Node):
...   def __init__(self, type):
...     self.type = type
...     self.successors = []
...   def activate(self, tag, timestamp, obj):
...     if obj.__class__.__name__ == self.type:
...       for node in self.successors:
...         node.activate(tag, timestamp, obj)

The above is of course grossly simplified, for starters it doesn't have any error checking, but it's enough to convey the general idea.

There are several other types of nodes as well. They all have a list of successors and at least one activation method (Join Nodes have two). When a fact is asserted, it is propagated through the Rete Network via the activation methods of each node.

There are several problems with my current approach and it's no secret that I've been trying to clean up and simplify both the Rete Implementation, the Rule Parser and the Rule Compiler. However, a simple, efficient implementation using an object-based DAG have so far eluded me. So last week I tried to use functions (instead of objects) together with a hash table to provide, among other things, storage (it replaces the memory node objects).

So far, I've only got some very simple tests working but the code is smaller, cleaner and faster. The ObjectTypeNode above is replaced by:

>>> class Rete(dict):
...   def __init__(self):
...     self["OBJ"] = {}
...   def make_object_type_node(self, var, value):
...     key = (var, '__class__.__name__', value)
...     def activate(tag, o):
...       if getattr(getattr(o, '__class__'), '__name__') == value:
...         token = Token()
...         token[var] = o
...         if tag == '+':
...           self["MEM"][key].append(token)
...         elif tag == '-':
...           self["MEM"][key].remove(token)
...         self.propagate(tag, token, key)
...     self["OBJ"][key] = activate
...     self["MEM"][key] = []
...     self["NEXT"][key] = []
...     return key

What happens here is that the Rule Compiler calls the make_object_type_node instead of instantiating an object. The method calculates a unique key, defines the activate function and registers it in the common hash table. It also registers two empty lists which are used as output memory ("MEM") and as a list of succesor nodes ("NEXT").

The object type test is performed within the activate method and uses a common propagate method, which looks like this:

>>> def propagate(self, tag, obj, key):
...   [self[dictionary][_key](tag, obj) for _key, dictionary in self["NEXT"][key]]

One of the *really* good things with it is that those two lines can be used for all types of nodes. The Rule Compiler only needs to register which dictionary the next node is found in (usually "ALPHA" for Object type tests) and which key it has.

One of the bad things with this approach is that all of the function calls are nested so it might not work too great for large Rete Networks.

The idea was actually to generate one function that would have *all* tests (for one rule) laid out as a procedural function which would update a common (to all rules) storage of some sort. I'm not 100% sure of what it would look like and since Python doesn't have macros I can't really do it either so this will do for now.

Once I get the more complicated things working (Not Nodes) I'll let you know if it's better or worse than my current implementation.

pyRete update

2007-07-13T18:57:00.000+02:00

It's been awhile since I've mentioned what's happening with pyRete. I'm still in the middle of refactoring the Rete implementation and, more importantly, the rule compiler (which is a bloated mess at the moment). I wanted to make most of these changes in one fell swoop, but I soon realized that I'm not even half the programmer required to pull that off. So instead I'm slowly (but steadily) modifying Rete node implementations and the rule compiler. Among other things, the single Not node works as expected now but there's still lots of things to do...

FSFE meeting in Gothenburg

2007-07-05T21:45:00.000+02:00

I attended a local FSFE meetup here in Gothenburg yesterday. There was some discussion about what the Swedish chapter (FSF-SE) should focus on and what activities to arrange.

This was my first IRL contact with FSF people but I have previously considered becoming a fellow because I whole-heartedly support the ideas behind Gnu and FSF. The reason I haven't bothered yet is because it's still quite unclear to me what the FSFE and FSF-SE are supposed to do. I know about all of the high profile things they're doing, such as the fight against software patents in Europe, the fight against DRM and the fight against Microsoft's attempt to get their OO-XML document format approved as an ISO standard... and that's the problem right there. I find it easier and more natural to define FSFE in terms of what they oppose than anything else, and I'd rather spend my time contributing than protesting.

Jonas and Henrik (both are employed by the FSFE) mentioned the SELF project as an example of such an activity and I hope that I sometime soon will find it easier to talk about what the FSFE are supporting and contributing to when explaining the organisation and the philosophy to people who've never heard of them.

At the meeting I suggested local (in and around Gothenburg) projects to support and help schools, libraries and other public institutions with both hard- and software. I believe that the content currently being developed for the OLPC could be real useful in Swedish schools as well and that would really be worth spending time on. I really hope that we can make something useful happen after summer. If you at least promise to try, I'll pay the fee for fellowship. That's a promise :-)