Time to say bye bye!

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

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...

"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

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

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

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

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?

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

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

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

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

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

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

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

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

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

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

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.

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

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

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.