AI Expert Newsletter
AI - The art and science of making computers do interesting
things that are not in their nature.
August 2005
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,
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.
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/.
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.
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 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.
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.
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.
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.
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.
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.
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.
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".
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.
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.
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/.
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.
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.
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.
Past newsletters are available at either www.ddj.com
or www.ainewsletter.com.
As ever, interesting links and ideas for future issues are very
welcome.
Until next month,
Jocelyn <popx@j-paine.org>
For questions about the www.ainewsletter.com
site, contact Dennis
Merritt
Copyright ©2005 Amzi! inc., CMP, and Jocelyn Paine. All Rights
Reserved
|