AI - The art and science of making computers do interesting things that
are not in their nature.
- Introduction
- Iterative Spreadsheets, Recurrent Neural Nets, Cellular Automaton
Knitting, and Relativistic Time Dilation
- The Koders Source-code Search Engine
- Real Programmers
- Matrix Algorithms using Quadtrees
- Python for AI and Logic Programming
- The 800-pound gorilla versus a steaming
pile of dinosaur dung
- "I never understood why LISP was a good idea until
I started playing with Python"
- Python implementations
- AI in Python
- Prolog in Python - PyLog and Pylogic
- Constraint logic programming in Python
- Production rules and the Rete algorithm in Python
- Links
- The 800-pound gorilla versus a steaming
- Open Automaton
- Common-sense Reasoning and the Anti-squirrel-nut-theft Challenge
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
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
about Math
on Spreadsheets
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
Glidergun
a simple
genetic algorithm
Stuart Kauffman's book
At Home in the Universe.
During my search, I found two unusual links. Pati Taylor's
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
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 therunning 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 Khayyam, 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
this includes an algebraic formulation of
double-entry bookkeeping
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
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
issue; the Python function enumerate_joint_ask
I exhibit in this month's Python for AI and
Logic Programming
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.
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
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
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
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
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
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
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
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
(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
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
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
This is based on a
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-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
This is a method of optimising conflict
resolution
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
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
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
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
Python.
Stackless Python.
www.onlamp.com/pub/a/python/2000/10/04/stackless-intro.html -
Introduction to Stackless Python,
by Cameron Laird.
Jython.
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.
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.
Logilab's free software: programs include:
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
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 program 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.
