Introduction

A few months ago, I discovered the Python code repository for the textbook Artificial Intelligence: A Modern Approach by Peter Norvig and Stuart Russell. There's some good stuff there, and this inspired me to find out what else Python had to offer AI. A lot, is the answer, and that's the topic of this month's main feature. If you have no interest in Python, I hope the examples may still be useful as demonstrations of assorted AI techniques and how they can be taught. Next month, I hope to continue this with a look at Python in robotics. Until then,

Iterative Spreadsheets, Recurrent Neural Nets, Cellular Automaton Knitting, and Relativistic Time Dilation

Simon Andersson mailed me about my assertions in our May Spreadsheet Issue that Excel can't implement the iteration needed for a Hopfield neural net, and can only simulate cellular automata by displaying each generation separately.

In fact, he says, if you tell Excel to allow circular references, these can be implemented - as he did one idle Sunday afternoon five years ago when he wrote a spreadsheet for Conway's game of Life. To follow this up, I searched the Web and found a page by David Ellerman about Math on Spreadsheets. Ellerman says:

Since any algorithm of any sophistication requires circular references and iterations, the trick is to use the fixed order of recalculating cells during iteration (usually left to right across columns, top to bottom down rows) and to construct an iteration counter within the spreadsheet. With an iteration counter, the formulas can distinguish between the initial iteration when the variables are first given seeded values and the later iterations when the variables use the results of earlier iterations.

Ellerman demonstrates with several examples, including a basic Life spreadsheet, a Life Glidergun, a simple genetic algorithm (simple or not, it's an impressive spreadsheet), and spreadsheets based on Stuart Kauffman's book At Home in the Universe.

During my search, I found two unusual links. Pati Taylor's Cellular Automaton Design is a small Excel cellular automaton for generating knitting patterns. This CA is one-dimensional; each generation is one row of the spreadsheet, and corresponds to one row of yarn. CA cells are stitches, their colour given by the state of the cell. This is the first time I've seen CAs explained via knitting.

The second is George Jaroszkiewicz's Causal Implication and the Origin of Time Dilation, which derives qualitative equivalents of relativistic time dilation and the Lorentz-Fitzgerald contraction by viewing the Universe as a cellular automaton. It's God as the Eternal Knitter, stitching the Present to the upper surface of the Past and propagating world-lines in coloured stitches, their position determined via the rules of a 3-D cellular automaton.

Since this is hard to depict in your average PDF file, Jaroszkiewicz uses a one-dimensional CA as an example:

I use a spreadsheet such as Excel to discuss the time delays occurring during the running of a cellular automaton (similar to Conways "Game of Life") when initial data is organised in a manner resembling data distributed over a moving frame of reference. The level of mathematics is suitable for undergraduate or high school interest, and helps to develop a knowledge of special relativity.

He starts with an observer or "Theorist" standing outside the space-time represented by the spreadsheet, at rest relative to the frame of reference defined by the space and time axes of the CA it contains. He then considers a second frame of reference moving relative to this, meaning that its space and time axes are tilted across the spreadsheet. The Theorist observes a line of lights (say) moving with this frame; on the spreadsheet, these are represented by a line of cells which runs parallel with the moving frame's space axis. He runs the CA forward from this state (the notion of CA has to be widened to permit this, allowing both past and future to determine a neighbouring cell) and notes the earliest time in his frame at which he can compute the next state of each light. From this, Jaroszkiewicz gets a mapping between the two frames' time flows, and derives time dilation. As Omar Khayam, who was a mathematician as well as a poet, didn't quite say: once the moving finger of the Theorist has written in a cell, it moves on and never rewrites that cell.

Links

www.math.com/students/wonders/life/life.html - What is the Game of Life?, by Paul Callahan. Explains Life, with some really nice applets on which you can draw and run Life patterns.

www.ellerman.org/Davids-Stuff/Maths/Math-on-SS/MathonS.htm - David Ellerman's Math on Spreadsheets. Look also at his Math: Pure and Applied - this includes an algebraic formulation of double-entry bookkeeping - and his home page, including Notes, Memos, and Other Rants from the World Bank.

www.knitting-and.com/knitting/tips/automaton.htm - Cellular Automaton Design, by Pati Taylor.

xxx.soton.ac.uk/abs/gr-qc/0008022 - Causal Implication and the Origin of Time Dilation, by George Jaroszkiewicz, University of Nottingham. His other papers about discrete time are at www.maths.nott.ac.uk/personal/gaj/papers.html, and his home page is www.maths.nott.ac.uk/personal/gaj/.

The Koders Source-code Search Engine

I recently came across a blog entry announcing its author's discovery of Koders, a search engine designed specially to look for open source code. To quote Koders's Getting Started page:

A significant portion of application development involves a process of find, copy, paste, and integrate. This process can be greatly accelerated when you can find existing source code that provides a solution to the task at hand.

Koders makes it easy for software developers to find existing source code that solves many common development problems with our vast index of working source code from a variety of open source projects. In many cases you may find code that solves the exact problem you are working on, and in other cases, you can find an 80% solution - where existing code can be suited to your needs with minor modifications.

This was interesting, so I did some experiments. I tried Koders to see whether it could find the free software I've put on my Web site: specifically, my Java implementation of Fortran formats and my Kawa pattern matcher. (Kawa is Per Bothner's Java implementation of Scheme.) It didn't find either. In fact, Koders may not be set up to find Kawa code at all. Its search form contains a menu of languages to search for, and this doesn't include Kawa. There is an "All languages" option, but it may not cover languages not in the other options.

I then searched for AI source code I know to exist elsewhere: the Bochum neural-gas applet discussed in our June 2005 issue; the Python function enumerate_joint_ask I exhibit in this month's Python for AI and Logic Programming feature, which is on Norvig and Russell's site; and Scott Bollland's Copycat reimplementation at Queensland, which I wrote about last February. None of these were found.

Going on to a general search for utilities, I searched for "unify" in Prolog. Surprisingly, Koders found nothing - unlike Google, which turned up a number of files, from a copy of Mark Stickel's Prolog Technology Theorem Prover to a course example used at Southampton University. I then thought of a game - look for an algorithm in the most unlikely language possible. Has anybody written a unifier in Visual Basic? No. In Cold Fusion? No. In Perl? Yes ... except it wasn't. All the "Perl" unifiers Koders found were in Prolog. I suspect it guesses programming language from file extensions, and therefore classifies .pl files as Perl even when they're Prolog.

Recently, I needed to invert some matrices in Prolog, so I tried Koders to see how it might have helped. Could it find me matrix inverters in other declarative languages, easily translatable to Prolog? The functional language Haskell is one possibility, but Koders doesn't have a Haskell language option. There is one for Lisp, and here, Koders did find several useful files.

When Koders displayed the files it found, it obscured them with a "nag curtain": an advert which one must click to remove. It would be better to imitate Google, which manages to display both advertising and search results, clearly, separately, and without nagging.

I hope these remarks don't seem like carping. They do reflect what I need from a source-code search engine, not least in finding tasty software to write about in this Newsletter. It would be nice if one could rely on Koders to index all the free courseware and other code available at universities and similar organisations. I should say that users with different needs have been very pleased with Koders: in his blog, Scott Schram tells how amazingly useful it was in his quest for a Java FilenameFilter. And he also mentions one unusual feature: Koders will not only tell you the size of the code it finds, but will also estimate the cost of re-implementing it from scratch.

Links

koders.com/ - Koders.

weblogs.java.net/blog/scottschram/archive/2005/04/koderscom_searc.html - koders.com Searches Open Source Projects, by Scott Schram. Blog entry about searching for a FilenameFilter.

www.socaltech.com/fullstory/0002028.html - Interview with Jorn Teutloff, a co-founder of Koders.

Real Programmers

Real programmers don't comment their code. If it was hard to write, it should be hard to read.

From www.guidenet.net/resources/programmers.html and many other sites.

Matrix Algorithms using Quadtrees

While comparing Koders with Google, I came across a paper by David Wise on Matrix Algorithms using Quadtrees. Perhaps it will interest those implementing efficient functional or logic-based versions of some array algorithms. The excerpt below is from the Introduction. Since the paper mentions APL, I've included some links explaining that too. As spreadsheet and Linux expert Chris Browne once told me, APL's rich variety of array operations may be useful inspiration for programmers processing array-like structures in other languages and trying to decide on suitable primitive operations:

Iverson built many novel attributes into APL; almost all of them appeared in other languages since then. Interactive dialog, novel in the era of batch processing, is now necessary to personal - and personalized - computers. Overloading of operators not only is one of the pillars of Object Oriented Programming, but also has been extensively analyzed in the development of polymorphic type checkers, as in ML or Haskell, for instance. A significant contribution from APL is its rich vocabulary for array operations, which has become the heritage of this meeting.

From the pure-functional programming camp I come to assail some constraining prejudices that are part of that heritage: APL's aggregate/matrix operations that, regrettably, focus on row/column decomposition. If one asserts, since the underlying model for memory in a modern computer is an array, that row- or vector-processing is closest to "natural" computation, I want to undo that prejudice, as well. My model of memory is a heap of relatively small nodes, linked into trees, dags, and graphs.

Lucid expression of parallelism requires a comfortable vocabulary and style formapping functions. Mapping or "spreading" of application across data structure is the best applicative analog of parallelism, and is particularly important in a functional language because the mapped function is necessarily independent in all its applications. (Collateral argument evaluation is the simplest and most common case of such mapping.) When mapping occurs early in the divide-and-conquer decomposition of a problem, each application represents a desirably large granule of computation that can be further mapped. APL maps across arrays, which is insufficient; Haskell maps (or (cringe) zipWith3s) only across lists; this is also too weak. The most important target for mapping is homogeneous tuples of relatively small size, so to control the growth of parallelism and the scheduling problem. Much is done here with fourples.

My task is to propose and to justify a new approach to an old algorithm, Gaussian elimination|an essential result from matrix algebra. While the performance of this algorithm won't beat a Cray so far, it has ample opportunities formultiprocessing, for distributed processing, for algebraic transformation, and even for partial evaluation; that is, it exhibits lots of structured opportunities for massive parallelism, just as we expect from a functional program. The challenge is to express array algorithms like this in your favorite array language. Since the principal data structure is a quaternary tree and no row or column operations are used, vector operations may be useless. Block decomposition and block arithmetic are important; sometimes blocks carry other decorations, aside from their constituent elements.

Links

www.cs.indiana.edu/pub/techreports/TR357.pdf - Matrix Algorithms using Quadtrees, by David Wise, Indiana.

www.acm.org/sigs/sigapl/links.htm - The ACM Special Interest Group resource pages for APL and J. Links include John Howland's Great Ideas in Computer Science course, with copious course examples in both Scheme and the J dialect of APL.

www.cs.trinity.edu/Other_Attractions/j.html/ - About J.

www.vector.org.uk/archive/v213/ - Current issue of Vector, Journal of the British APL Association. Includes a feature on industrial functional programming by Stephen Taylor in which he asks "does FP remain an academic fad, a cunning trick - look, Ma, no variables? What can we take and use from FP, and how might it help us in everyday programming?" Not many articles conclude as he does that "refactoring was a snack".

www.ics.uci.edu/~eppstein/gina/quadtree.html - Quadtrees and Hierarchical Space Decomposition, by David Eppstein, Irvine. Introduction to quadtrees and their applications.

Python for AI and Logic Programming

The 800-pound gorilla versus a steaming pile of dinosaur dung

Let's start right away with an example of Python, from the introduction to Python at www.python.org/. Here's a function which inverts a mapping stored in the lookup table - or dictionary, as Python calls it - table:

def invert(table):

    index = {}                # empty dictionary

    for key in table.keys():

        value = table[key]

        if not index.has_key(value):

            index[value] = [] # empty list

        index[value].append(key)

    return index

As one might guess from the syntax, Python has lists and dictionaries built in, providing building blocks for a variety of standard algorithms. It's also easy to read. This is partly because of the way Python handles indentation. The language does not use begin...end or {...} brackets. Instead, the compiler infers nesting from indentation. This lack of brackets reduces visual clutter, and forces programmers to make their indentation reflect code structure, thus aiding legibility.

Python, which has strings, regular expression matching, classes, and all the other features found in today's imperative programming languages, can be used as a "scripting language", for the same kind of jobs as Perl. In Why Python?, Eric Raymond tells how, when O'Reilly sent him Mark Lutz's book Programming Python, he dived into it to find out what Python had that Perl, the "800-pound gorilla" of scripting languages, did not. On encountering Python's indentation-based bracketing, he reacted at first as though he had stepped in a steaming pile of dinosaur dung. In comparison with Perl, Python seemed to have nothing special to offer. However, as he found himself working on a sequence of large and complicated Perl programs:

Writing these programs left me progressively less satisfied with Perl. Larger project size seemed to magnify some of Perl's annoyances into serious, continuing problems. The syntax that had seemed merely eccentric at a hundred lines began to seem like a nigh-impenetrable hedge of thorns at a thousand. "More than one way to do it" lent flavor and expressiveness at a small scale, but made it significantly harder to maintain consistent style across a wider code base. And many of the features that were later patched into Perl to address the complexity-control needs of bigger programs (objects, lexical scoping, "use strict", etc.) had a fragile, jerry-rigged feel about them.

These problems combined to make large volumes of Perl code seem difficult to read and grasp as a whole after only a few days' absence. Also, I found I was spending more and more time wrestling with artifacts of the language rather than my application problems. And, most damning of all, the resulting code was ugly--this matters. Ugly programs are like ugly suspension bridges: they're much more liable to collapse than pretty ones, because the way humans (especially engineer-humans) perceive beauty is intimately related to our ability to process and understand complexity. A language that makes it hard to write elegant code makes it hard to write good code.

"I never understood why LISP was a good idea until I started playing with Python"

Peter Norvig gives an interesting account of Python in Python for Lisp Programmers. He states that Python can be seen as a dialect of Lisp with infix syntax. It supports all Lisp's essential features except macros; but you can make up for this lack by using eval, operator overloading, and regular expression parsing. This makes it easy to create "little languages" for constructing complicated data structures, something I'll mention again later.

This and other features lead Norvig to conclude that Python is an excellent language for teaching - although it has little compile-time error-checking, and is slow. In general,

Python has the philosophy of making sensible compromises that make the easy things very easy, and don't preclude too many hard things. In my opinion it does a very good job. The easy things are easy, the harder things are progressively harder, and you tend not to notice the inconsistencies. Lisp has the philosophy of making fewer compromises: of providing a very powerful and totally consistent core. This can make Lisp harder to learn because you operate at a higher level of abstraction right from the start and because you need to understand what you're doing, rather than just relying on what feels or looks nice. But it also means that in Lisp it is easier to add levels of abstraction and complexity; Lisp makes the very hard things not too hard.

Python implementations

The main implementation is that at www.python.org/, where you can also find tutorials and reference documentation. There's also Stackless Python, based on the idea that Python should support coroutines, which are easier to program with than threads. And there are IronPython for the .NET and Mono platforms, and Jython, written in Java and compilable to JVM code. While, as Norvig says, Python doesn't satisfy the prerequisite of being spelled J-A-V-A, Jython is close. I would add that it is also a convenient way to run pieces of Java code interactively, useful when testing and debugging Java.

AI in Python

In Python Applications in Artificial Intelligence Research, Daniel Taylor gives an assortment of links to AI software in Python. Some of it, such as the Therapist reimplementation of Eliza, won't interest the serious AI-er; however, such programs can be very good for teaching, and would fit well with Python's legibility. For AI students with no programming experience, being invited to extend a computer conversation program via small additions to its lexicon and pattern-matching rules is not a bad introduction to such things as text editors, operating-system commands, and the need for compilation. More seriously, Taylor mentions the Python interface to ThoughtTreasure's ontology and lexical knowledge base.

A bigger resource, and the main one I want to mention in this section, is Norvig and Russell's textbook Artificial Intelligence: A Modern Approach. Although the book isn't available online, most of the code is, in both Lisp and Python. (There is also a Java version.)

The authors say that neither version is complete, though the Lisp is more so. However, there's still a lot there, including agents and their environments, search, games, probability models and Markov processes, machine learning, chart parsers, and statistical language processing. The contents also mentions planning, but in fact, as the Lisp page explains, you won't find any code for this. Norvig and Russell recommend using the University of Washington UCPOP planner.

To demonstrate the coding style, here's an excerpt from the code for probability models, used in Chapters 13 to 15:

def enumerate_joint_ask(X, e, P):

    """Return a probability distribution over the values of the variable X,

    given the {var:val} observations e, in the JointProbDist P. 

    Works for Boolean variables only. [Fig. 13.4]"""

    Q = ProbDist(X) ## A probability distribution for X, initially empty

    Y = [v for v in P.variables if v != X and v not in e]

    for xi in P.values(X):

        Q[xi] = enumerate_joint(Y, extend(e, X, xi), P)

    return Q.normalize()



def enumerate_joint(vars, values, P):

    "As in Fig 13.4, except x and e are already incorporated in values."

    if not vars: 

        return P[values] 

    Y = vars[0]; rest = vars[1:]

    return sum([enumerate_joint(rest, extend(values, Y, y), P) 

                for y in P.values(Y)])

The functions are well commented and the code is easy to read.
The excerpt below, which defines the class of Bayesian nets and creates an instance, shows how legible the constructors for these complicated structures can be:

class BayesNet:

    def __init__(self, nodes=[]):

        update(self, nodes=[], vars=[])

        for node in nodes:

            self.add(node)



    def add(self, node):

        self.nodes.append(node)

        self.vars.append(node.variable)



    def observe(self, var, val):

        self.evidence[var] = val



class BayesNode:

    def __init__(self, variable, parents, cpt):

        if isinstance(parents, str): parents = parents.split()

        update(self, variable=variable, parents=parents, cpt=cpt)



node = BayesNode





T, F = True, False



burglary = BayesNet([

    node('Burglary', '', .001), 

    node('Earthquake', '', .002),

    node('Alarm', 'Burglary Earthquake', {

                    (T, T):.95,

                    (T, F):.94,

                    (F, T):.29,

                    (F, F):.001}),

    node('JohnCalls', 'Alarm', {T:.90, F:.05}),

    node('MaryCalls', 'Alarm', {T:.70, F:.01})

    ])

Bayes nets are one place where we want concise constructors; another is in parsing, for grammars and lexica. Look at the chart parser of Chapter 22, and you will see that its data too is easy to read.

Prolog in Python - PyLog and Pylogic

Now for some logic programming. PyLog is Christophe Delord's Python logic library and Prolog engine. Here's one of his examples:

from pylog import *



class f(Term): pass

class g(Term): pass



print "Simple unification"

X = Var('X')

Y = Var('Y')

a = f(X,g(Y,2))

b = f(g(1,2),X)

print "\tBefore unification"

print "\t\ta =", a

print "\t\tb =", b

u = mgu(a,b)

print "\t\tmgu(a,b) =", u

u.unify()

print "\tAfter unification"

print "\t\ta =", a

print "\t\tb =", b

which displays

Simple unification

    Before unification

        a = f(X,g(Y,2))

        b = f(g(1,2),X)

        mgu(a,b) = 1/Y g(Y,2)/X

    After unification

        a = f(g(1,2),g(1,2))

        b = f(g(1,2),g(1,2))

This demonstrates how to call PyLog from Python. It assumes you're familiar with logical variables and unification. For those who aren't, unification is a kind of pattern matching, which tries to lay trees - such as those representing the expressions f(X,g(Y,2)) and f(g(1,2),X) above - side by side and match up structurally similar subexpressions. Trees can contain logical variables, such as X and Y: these represent "holes" into which matching subtrees can be slotted.

Logical variables and unification are an integral part of the Prolog language, and PyLog contains a Prolog compiler. This can read its input from a Python string:

from pylog import *



exec(compile(r"""



likes('sam',Food) :-

        indian(Food),

        mild(Food).

likes('sam',Food) :-

        chinese(Food).

likes('sam','chips').



indian('curry').

indian('tandoori').

indian('kurma').



mild('tandoori').

mild('kurma').



chinese('chop_suey').



"""))



WHO, WHAT = Var('WHO'), Var('WHAT')

queries =	[

                likes('sam','chop_suey'),

                likes('sam','chips'),

                likes('sam','curry'),

                likes(WHO,WHAT),

            ]



for query in queries:

    print "?", query

    n=0

    for _ in query():

        print "\tyes:", query

        n += 1

    if n==0:

        print "\tno"

which displays

? likes(sam,chop_suey)

    yes: likes(sam,chop_suey)

? likes(sam,chips)

    yes: likes(sam,chips)

? likes(sam,curry)

    no

? likes(WHO,WHAT)

    yes: likes(sam,tandoori)

    yes: likes(sam,kurma)

    yes: likes(sam,chop_suey)

    yes: likes(sam,chips)

As the end of this example shows, once you've compiled PyLog Prolog, you can submit queries.
The PyLog page doesn't explain how PyLog works, other than that the Prolog engine uses the generators introduced with Python 2.2. It also says that backtracking over a cut works wrongly, in that it doesn't undo unifications done before the cut, something hard to fix with the current structure of PyLog. Delord invites collaborators to help improve PyLog: anyone doing so will find his code to be nicely written and easy to read.

Another almost-Prolog is Francisco Coelho's Pythologic. This is based on a logic-programming system by Shai Berger, extended with logical resolution. I don't think Pythologic can do as much as PyLog, but it's interesting in that it tries to provide Prolog syntax in Python itself, rather than hiding it inside Python strings. Shai Berger explains at the end of his posting that this involves some ingenious metaprogramming, "wildly unpythonic, in its abusive overhaul of the function semantics".

Constraint logic programming in Python

The French company Logilab, as their home page explains, number Python and logic programming amongst their specialities. They maintain a repository of free software, which contains their Constraint constraint-satisfaction package.

They have the following example. You're organising an international Python event, and need to schedule 10 different conferences within it. The event lasts for 2 days, you have 3 conference rooms available, and the length of conferences means you can hold at most two per day in any given room. Conferences 3, 4, 5 and 6 must take place in room C (it's the only one with Internet access). Conferences 1, 5 and 10 must take place on day 1, because their speakers are only available then. Similarly, conferences 2, 3 4 and 9 can only take place on day 2. Finally, some delegates want to attend specific conferences, so these can't take place at the same time. Specifically, one group of delegates wants to attend conferences 1, 2, 3 and 10, so these must not happen at the same time; nor must conferences 2, 6, 8 and 9; conferences 3, 5, 6 and 7; or conferences 1, 3, 7 and 8.

To specify this problem to a constraint solver, we start by creating 10 variables, one for each conference. Don't confuse these with Python variables, though you'll probably have both in the program; they're more like the logical variables mentioned earlier. We want the solver to find a time and a room for each of these variables, satisfying the constraints. In other words, the solver must find a value for each variable, where the value is a pair consisting of a time and a room.

We start by importing the solver and then creating the variables, which the solver represents as names:

from logilab.constraint import *



variables = ('c01','c02','c03','c04','c05','c06','c07','c08','c09','c10')

We then create a list of possible values, that is, of all possible time-room combinations. We can do so very concisely using Python's "list comprehension" syntax:

values = [(room,slot) 

            for room in ('room A','room B','room C') 

            for slot in ('day 1 AM','day 1 PM','day 2 AM','day 2 PM')]

Any constraint solver needs to know what possible values each variable can take. We tell it this by associating each variable with a domain, or class of possible values. For this solver, we do this by creating a mapping from variable name to domain. The mapping is stored in a Python dictionary, here called domains. Domains are represented as instances of class fd.FiniteDomain, and created by invoking the class's instance constructor with the list of values created above:

domains = {}

for v in variables:

    domains[v]=fd.FiniteDomain(values)

Now we tell the solver the constraints. These are instances of a class created by calling the function fd.make_expression, passing it a list of the variables the constraint affects, and an expression that evaluates to true if the constraint is satisfied. The first constraint is the one that some conferences can only take place in Room C:

constraints = []

for conf in ('c03','c04','c05','c06'):

  constraints.append(fd.make_expression((conf,),

                                        "%s[0] == 'room C'"%conf))

Similarly, some speakers can only attend on day 1 or day 2:

for conf in ('c01','c05','c10'):

    constraints.append(fd.make_expression((conf,),

                                            "%s[1].startswith('day 1')"%conf))

for conf in ('c02','c03','c04','c09'):

    constraints.append(fd.make_expression((conf,),

                                            "%s[1].startswith('day 2')"%conf))

Some conferences must not happen at the same time as other conferences:

groups = (('c01','c02','c03','c10'),

            ('c02','c06','c08','c09'),

            ('c03','c05','c06','c07'),

            ('c01','c03','c07','c08'))

for g in groups:

    for conf1 in g:

        for conf2 in g:

            if conf2 > conf1:

                constraints.append(fd.make_expression((conf1,conf2),

                                                        '%s[1] != %s[1]'%\

                                                        (conf1,conf2)))

And no two conferences can happen in the same room at the same time:

for conf1 in variables:

    for conf2 in variables:

        if conf2 > conf1:

            constraints.append(fd.make_expression((conf1,conf2),

                                                    '%s != %s'%(conf1,conf2)))

We're now ready to solve the problem. This entails creating a Repository to hold the variables, domains and constraints, and a Solver object to solve the problem:

r = Repository(variables,domains,constraints)

solutions = Solver().solve(r)

print solutions

There are constraint-logic languages that will express such problems more concisely, with more error-checking, and as pure logic. However, as an embedding of constraint logic in an imperative programming language, the above is not too painful.

Production rules and the Rete algorithm in Python

As my final logic-programming example, I want to mention the Rete algorithm. This is a method of optimising conflict resolution in forward-chaining rule-based systems: that is, of deciding rapidly, when you have perhaps many hundreds of rules that can match your data, which is the most appropriate.

In a Python-logic posting, Nicolas Chauvat announces the Pychinko Rete-based RDF friendly rule engine. This emulates CWM, the Closed World Machine forward-chaining inference engine for semantic Web data. Pychinko's authors explain that CWM is slow; CWM is very slow; CWM is uberslow! With Pychinko, they aim to provide a cleaner, faster, implementation, based on the Rete algorithm.

Should one always go first for Python when choosing a programming language? Of course not. Many factors influence your choice. But as Yoda says in A morality tale of Perl versus Python as he replies to Luke Skywalker's question "But how will I know why Python is better than Perl?":

You will know. When your code you try to read six months from now.

Links

General Python stuff

www.python.org/ - Python.

www.stackless.com/ - Stackless Python.

www.onlamp.com/pub/a/python/2000/10/04/stackless-intro.html - Introduction to Stackless Python, by Cameron Laird.

www.jython.org/ - Jython.

www.ironpython.com/ - IronPython.

wiki.python.org/moin/LanguageComparisons - Language Comparisons. Links to comparisons of Python with other languages. Includes a link to Lutz Prechelt's An Empirical Comparison of C, C++, Java, Perl, Python, Rexx, and Tcl for a Search/String-Processing Program.

www.norvig.com/python-lisp.html - Python for Lisp Programmers, by Peter Norvig.

www.linuxjournal.com/article/3882 - Why Python?, by Eric Raymond.

www.artima.com/intv/python.html - The Making of Python. A conversation with Python's creator Guido van Rossum, by Bill Venners.

www.netfunny.com/rhf/jokes/99/Nov/perl.html - A morality tale of Perl versus Python. A scene from The Empire Strikes Back, reinterpreted to serve a valuable moral lesson for Perl and Python programmers.

linuxgazette.net/100/pramode.html - Python Generator Tricks, by Pramode C.E. Demonstrates a few simple programs which use generators to do things such as filtering out prime numbers, representing an infinite series expansion, and applying the Euler "accelerator" to make a series converge more repidly.

www.ps.uni-sb.de/~duchier/python/continuations.html - Continuations Made Simple and Illustrated, by Denys Duchier. Posted in response to discussion on comp.lang.python, this explains continuations, how to implement them in Python, and their use in implementing generators and Prolog-style search.

AI in Python

programmer-art.org/dan/python-ai.html - Python Applications in Artificial Intelligence Research, by Daniel Taylor.

aima.cs.berkeley.edu/ - Artificial Intelligence: A Modern Approach.

Logic programming in Python

lists.logilab.org/mailman/listinfo/python-logic - Python-logic, a mailing list on logic and constraint-propagation for Python, run by Logilab.

www.logilab.org/ - Logilab's free software: programs include: PyReverse for reverse-engineering Python; PyLint for checking Python code; the Constraint constraint-satisfaction system; HMM for hidden Markov models; and Narval, a language, interpreter, GUI and development environment for writing intelligent personal assistants.

christophe.delord.free.fr/en/pylog/pylogsrc.html - PyLog -- A first order logic library in Python, by Christophe Delord. He has two other Python projects: the Toy Parser Generator (used as PyLog's Prolog parser), and the PopF spam filter.

www.ntt.dis.titech.ac.jp/ICAIL2005/Paper02.pdf - An Integration of a Legal Knowledge Based System and a Content Management System for a Legal Education Support System, by Seiichiro Sakurai and Hajime Yoshino, Meiji Gakuin University Graduate Law School. Short paper about a method for teaching law via examples of correct and incorrect legal inference from legal knowledge bases. The paper does not explain well what this inference does or how it would be used, but is interesting from a Python point of view because it proposes PyLog Prolog for the inference engine, embedded in a Zope-based Web content-management system.

aspn.activestate.com/ASPN/Cookbook/Python/Recipe/360698 - Extending python with prolog syntax and resolution, by Francisco Coelho. This recipe is based on Shai Berger's aspn.activestate.com/ASPN/Cookbook/Python/Recipe/303057, Pythologic -- Prolog syntax in Python.

lists.logilab.org/pipermail/python-logic/2005-May/000109.html - Rete in Python. Posting by Nicolas Chauvat pointing to Pychinko: Rete-based RDF friendly rule engine at www.mindswap.org/~katz/pychinko/.

www.cis.temple.edu/~ingargio/cis587/readings/rete.html - CIS587: The RETE Algorithm, by Giorgio Ingargiola, Temple University. See also the Wikipedia article at en.wikipedia.org/wiki/Rete_algorithm.

www.w3.org/2000/10/swap/doc/cwm - Cwm home page. See also infomesh.net/2001/cwm/.

Open Automaton

An open-source mobile domestic robot? That's the aim of the Open Automaton project which I came across while preparing next month's feature on Python and robotics. I may have more to say about Open Automaton then - in the meantime, here's how they describe themselves on their home page:

Moore's Law has allowed modern mass-produced PC hardware to catch up with the demanding requirements of advanced vision processing and artificial intelligence. Based on current state-of-the-art PC mainboard technology, it is viable to build an intelligent mobile robot with stereo vision, for the price of a good PC.

This project aims to fill the gap between the powerful mobile robot platforms typically used by researchers, and the small rug-roving robots with limited processing power that are popular with hobbyists. ... When it was first conceived, its scope was to include devising a standard framework of hardware and software interfaces that define the contracts between interconnected hardware and software components. However, there are now at least two very serious efforts underway towards this particular goal (the RETF and the OROCOS project), as well as some well implemented modular open source code for mobile robots that arguably constitutes "de-facto" standards. So rather than re-invent the wheel, the Open Automaton Project now focuses on implementation rather than defining standards. Its goals are:

• Design a coherent set of modular components (hardware and software) that conform to standards (where possible), and implement the functionality of an intelligent mobile robot. Use pre-built components that are readily available where possible (and when such pre-built components are affordable).

• Minimize cost. It should be possible to build a robot for around the price of a PC (target: US$1,500 to $2,000). Consumer grade hardware components are to be used in preference to professional grade products.

• Focus on stereo vision as the primary spatial sensor to produce useful space occupancy data. Central to the success of this project is the implementation of a functioning low-cost real-time vision system. The prevalence of FireWire-enabled WebCams and mainboards makes this goal reachable from the standpoint of cost; the difficult part here is the software.

Links

oap.sourceforge.net/index.php - Open Automaton home page.

www.openautomaton.org/community - Open Automaton Community site.

linuxdevices.com/articles/AT8960820667.html - Meet OAP - an open robot reference design project. Feature about Open Automaton and its founder Dafydd Walters.

Common-sense Reasoning and the Anti-squirrel-nut-theft Challenge

Yesterday, I happened to be half listening to Gardeners' Question Time on Radio 4. For those living outside the UK, this is a programme in which members of a studio audience parade their horticultural woes before a panel of experts, seeking advice on such problems as slugs, thrips, and lopsided monkey-puzzles. One lady explained how she circumvents squirrels thieving nuts from her trees: she stands wide pots of soft earth under the trees, then every few days simply digs out and washes the nuts she finds buried in them. Squirrels, apparently, tend to bury nuts near the tree from which they take them. When an AI program can generate such an elegant piece of reasoning, I shall be impressed.

Until next month.