October 06, 2005
AI Expert Newsletter - October 2005
Jocelyn Paine
Logic Programming Associates's new Prolog (announcement).
AI in Forth and Gawk.
Maarten van Emden on the future of logic programming.
Regular expressions in Prolog.
An introduction to evolutionary art.
Dr. Dobb's AI Expert Newsletter
By Jocelyn Paine
AI Expert Newsletter
AI - The art and science of making computers do interesting things that
are not in their nature.
Logic Programming Associates's new Prolog (announcement).
AI in Forth and Gawk.
Maarten van Emden on the future of logic programming.
Regular expressions in Prolog.
An introduction to evolutionary art.
October 2005
Welcome to the October 2005 issue. My main topic this month is
an introduction to evolutionary art - genetic algorithms and
other evolutionary programming techniques for generating text,
visual art, and music. I'll continue next month - if you can recommend
any particularly splendid examples, please contact me at my usual
address, popx@j-paine.org.
Logic Programming Associates have released
version 4.6 of WinProlog, with lots of
improvements and enhancements.
You can download a 28-day Free Trial of WinProlog plus Flex plus VisiRule plus Chimera Agents from
their Web site,
www.lpa.co.uk/.
If you would like a WinProlog 4.6 evaluation CD or details of the
accompanying promotional offer, please contact LPA.
Dennis Jensen mailed me with links to
AI in
Gawk and
Forth.
Forth was developed,
to cut a
long story short,
by Charles Moore in the 1960s for distributed small computers -
"fourth generation" systems, or "forth generation"
if you restrict names to the five characters allowed
by Moore's operating system. It's
an interactive language with postfix syntax and
explicit manipulation of the call stack: you
add
2 and 2 by typing
2 2 + ., and if you want to
duplicate the item on top of the stack,
you use the command DUP.
It's no coincidence that
Forth looks like
the PostScript page-description language,
and if you've ever seen large quantities of PostScript spewing
from a mis-programmed printer, anything resembling it
may not appear to be an ideal language for
software engineering. There is,
however, an assortment of Forth-based robotics projects, and
you can find out more at
UltraTechnology's
robotics with Forth page.
Lest I sound flippant,
it's only because I think software engineering
is already risky enough without crippling one's ergonomics
by coding in anything so unintelligible as Forth in bulk. That said,
Dennis also pointed me at an interesting attempt to use
visual cues of a kind not
usually found in programming languages.
Distinctions important to Forth programmers, which
ordinary Forth makes via punctuation, colorForth makes by
colour. New
identifiers are red, green identifiers are
compiled, yellow identifiers are executed.
Charles Moore uses colorForth on his
Forth microprocessor chips,
and explains that his rationale is to
get away from elephantine
operating systems and user-interfaces:
Current software is shameful. Giant operating systems linger
from the 1970's. Applications are team-produced with built-in
obsolescence. User interfaces feature puzzle-solving.
With the huge RAM of modern computers, an operating system
is no longer necessary, if it ever was. colorForth includes
multi-tasking, and drivers for essential devices. But that is
hardly an operating system in the style of Windows or Linux.
Megabytes of software may be required for
historical compatibility, but sometimes we need a fresh start.
ColorForth provides the necessary capability with kilobytes of code.
At boot, it copies disk into RAM. Then compiles the macros that
emulate the stack machine that Forth expects. As applications are requested, they are compiled.
Meanwhile,
Ronald Loui at
Washington University in St. Louis writes
about teaching AI in
Gawk, the GNU implementation of
the
Awk text-processing
language. I didn't find any of his courseware, but
he argues that: students can master Gawk in a single lab
session; AI is increasingly interested in processing
Web pages, for which Gawk is well-suited; and features such as its regular expressions
and associative arrays make it quick and easy to prototype in.
Moreover, at
a deeper level:
Inference is merely the expansion of notation. No matter whether
the logic that underlies an AI program is fuzzy, probabilistic, deontic,
defeasible, or deductive, the logic merely defines how strings can be
transformed into other strings. A language that provides the best
support for string processing in the end provides the best support for
logic, for the exploration of various logics, and for most forms of
symbolic processing that AI might choose to call "reasoning" instead of
"logic." The implication is that PROLOG, which saves the AI programmer
from having to write a unifier, saves perhaps two dozen lines of GAWK
code at the expense of strongly biassing the logic and representational
expressiveness of any approach.
www.forth.org/ -
Forth Interest Group site, linking to tutorials,
applications of Forth, and an FAQ.
cliki.tunes.org/Forth -
The entry on Forth in the TUNES CLiki, with lots of links
to tutorials, extensions, applications, and so on.
www.geocities.com/jim_bowery/psgenesis.html -
The Genesis of Postscript (1981),
by Jim Bowery, telling of PostScript's relation to Forth.
www.ultratechnology.com/robolist.htm -
UltraTechnology's robotics with Forth page, including
links to Forth for Lego Mindstorms.
www.ultratechnology.com/forth.htm -
Thoughtful Programming and Forth, by Jeff Fox, UltraTechnology.
www.ultratechnology.com/essence.htm -
Essential Forth, also by Jeff Fox.
www.colorforth.com/cf.html -
colorForth.
www.latrobe.edu.au/philosophy/phimvt/joy/forth-joy.html -
Synopsis of Joy, a kind of cleaned-up Forth
based on combinators and higher-order functions.
www.gnu.org/software/gawk/gawk.html -
The GNU Gawk page, with links to a manual.
www.vectorsite.net/tsawk.html -
An Awk Tutorial, by Greg Goebel.
www.wra1th.plus.com/awk/awkfri.txt -
Why GAWK for AI?, by Ronald Loui,
Washington University in St. Louis.
By coincidence, considering the
previous feature on Gawk, I found a Prolog implementation
of regular expressions. It's by
Robert Cameron and makes a nice example of
symbolic computing in Prolog and a clear
specification
of regular expression semantics. There are
two stages: the first uses Definite
Clause Grammars to parse regular expressions
into trees, and the second matches strings
against the trees. This example combines both stages:
| ?- tokenize(" +|([0-9]+|\\+|-)", "12 + 4 - 29", L).
L = [12,+,4,-,29] ? ;
L = [12,+,4,-,2,9] ? ;
L = [1,2,+,4,-,29] ? ;
L = [1,2,+,4,-,2,9] ? ;
no
Here, the regular expression first finds the
longest match; backtracking then undoes this
and looks for alternative matches.
www.cs.sfu.ca/people/Faculty/cameron/Teaching/384/99-3/regexp-plg.html -
Perl Style Regular Expressions in Prolog, by
Robert Cameron, Simon Fraser University.
www.let.rug.nl/~vannoord/prolog-rx/PrologAndRegex.html -
Prolog and Regular Expressions, by Gertjan van Noord.
Ten or so links to regular expression software for various
Prolog systems. Amongst them is a
link to van Noord's
Elex scanner generator, which
generates lexical analysers in various languages, including Prolog. The page also
links to his
Finite-State Automata Utilities,
of interest because transforming regular expressions
into finite-state automata is a standard implementation technique - see
James Power's Notes on Formal Language Theory and
Parsing at
www.cs.may.ie/~jpower/Courses/parsing/node8.html.
Van Noord's utilities include some powerful software for displaying
automata as graphs, and an extension which allows arcs in the automata
to be labelled with predicates.
en.wikipedia.org/wiki/Regular_expression -
Wikipedia entry for regular expressions.
One of the great contributions of the Nineties was the
"real world" discovering the advantages of the compilation/execution
model of WAM based Prolog in the form of the Java Virtual Machine.
Perhaps in some quarters it was still somewhat suspect, SUN being a
notoriously innovative company. The last doubts disappeared when
this model was adopted for C#...
From
A Possible Future History of Logic Programming
by
Maarten van Emden,
University of Victoria.
The article is at
www.cs.kuleuven.ac.be/~dtai/projects/ALP/newsletter/ feb04/nav/van_emden/van_emden.html.
Evopedia
is an online encyclopedia
with a difference. It evolved.
Evopedia's home page explains how. In evolutionary programming,
you need a problem, a way to generate random solutions,
a way to evaluate solutions (a fitness function), and a way to mutate solutions.
For Evopedia, the problem is the need for an informative Web page about
some topic. To start, Evopedia creates some Web pages at random
from other pages,
using
Markov text-generation.
It copies them to www.evopedia.com
under their topic headings, and waits for several weeks while
gathering stats on their usage. The worst pages (presumably
the least read) are discarded;
the best are kept and mutated to make new pages. These get
copied to the site in their turn, and so the cycle repeats,
converging eventually (so Evopedia hopes) to sense.
To mutate pages, Evopedia swaps sections within them,
replaces sections with new sections, or adds or removes sections.
Its home page is weak on detail, but as common
in evolutionary programming,
it appears to model these mutations on
the behaviour of DNA. Those unfamiliar with
genetic algorithms will find copious information
on the Web; a good intro with clear diagrams is
the Evolutionary Computing chapter of Shahab Mohaghegh's
Virtual Intelligence
and its Applications in Petroleum Engineering.
Does Evopedia work? Here's the
entry for
Cake Recipe:
Cook the yeast over water and swirl into egg cloves
salt. Place in remaining milk the same size as possible.
Pour into the yeast and cornstarch stir in new brunswick
new york north carolina north dakota nova scotia ohio
oklahoma ontario oregon pennsylvania prince edward isl.
Spoon into prepared. Tablespoons triple sec and covered with a
spice nutmeg butter vanilla. Soak the centre and. This cake
recipe swap! Refrigerate then cut into the mixture beating
over the top of the cake parties games. Spoon the touch
shell borders. Add the baking sheet of an oval ring with a
well-greased. Fold in the long cylinder
in public domain that is frosted with confectioners' sugar.
This page clearly "knows" something about its topic; and
is different
from, say,
Low Carb Recipe,
which has its own specific concerns
about the Atkins diet, the unappetising nature
of health-food recipes, and the dangers of teenage obesity:
Looking for years of refined carbohydrates and chill at
left? Cooking section has been a high-carbohydrate meal
that lasted this? Well i send via email option. Low carb
recipes and i'll send out! However a low-carb cooking
altogether by dr. It has provided us on some minor
withdrawal symptoms and salt pepper cayenne and eggs.
Although the register button above navigation bar to be a
by-product are safe way of calories count for anyone who are
available at supermarkets and saturated fats and lightly coat
with mildly hot chillies and in their recommendations as
whole-grain breads and energy it includes kitchen! People
like many low carb recipes but we will be more convenient
central place in this vicious cycle. Teenage sons ranging from around.
In two primary reasons to waste her promise.
We have made an electric mixer until softened.
Subscribe to eat well. It been teaching for
themselves not intended to add lobster shells
and brought up to suffer from me away from.
Can be quite delicious satisfying. ...
Teenage sons ranging from the mondo Atkins
diet and the low-carb diet is also real food
pyramid recommendations as soon as often as main
energy levels of carb recipes.
Turning to an entirely different subject,
Bush Joke
tells us that
Democracy is factually innacurrate [sic]
and explains
Their way to get this point of the debate right in voter land.
I said that Evopedia claims to use Markov chains to generate its
initial population of Web pages from other pages,
but doesn't explain further. However,
Markov text-generation is well-known and
frequently used in creating parodies, such as
Mark Shaney,
the fake Usenet user written by
Bruce Ellis
and
Rob Pike.
My links give other examples; one
comes from
Fun with Markov Chains,
in which Andrew Plotkin exhibits
his
The Revelation of St. Alice, generated
from the Alice books and the Books of Genesis and Revelation:
For England expects--I forbear to proceed:
'Tis a maxim tremendous, but trite:
And you'd best be unpacking the things which were written
in this way when she bare him.
And his tail drew the back of it in Dutch--
I said it as she lifted it off, and brought them near unto him.
~~~~~~~
I shall continue with evolutionary art next month.
In the meantime, let me point at what
must be the star of evolutionary image generators,
Kandid.
This is
an open-source Java program which you run over the the Web
via the Java
WEB Start interface. Be warned - it's slow, but
definitely worth persevering.
With a variety of image-generating functions
to evolve, the ability to save
evolved images, and a genome editor you
can use during a run, Kandid
is a splendid introduction
to genetic algorithms.
www.evopedia.com -
Evopedia. The three entries I mentioned were
Cake Recipe,
www.evopedia.com/cake-recipe/GOMAHQLHFV.html;
Low Carb Recipe
www.evopedia.com/low-carb-recipe/MPYMLRCFDP.html;
and Bush Joke,
www.evopedia.com/bush-joke/AJMITMARAD.html.
www.intelligentsolutionsinc.com/part2.htm -
the Evolutionary Computing chapter of
Virtual Intelligence
and its Applications in Petroleum Engineering by Shahab Mohaghegh.
Mark Shaney and the Markov Chains
www.eblong.com/zarf/markov/ -
Fun With Markov Chains, by Andrew Plotkin.
Explains why his signature is
"And Aholibamah bare Jeush, and Jaalam, and Korah: these were the borogoves", and
links to the Markov-generated
The Revelation of St. Alice,
www.eblong.com/zarf/markov/revelation_of_alice.txt.
www.cs.bell-labs.com/cm/cs/pearls/sec153.html -
Generating Text
(Section 15.3 of
Programming Pearls), by Jon Bentley. Good explanation of letter-level
and word-level Markov text, plus pseudocode for generating
order-k approximations.
en.wikipedia.org/wiki/Mark_V_Shaney -
Wikipedia entry for
Mark Shaney, the
Markov-generated Usenet user. Links include
Shaney in Python.
en.wikipedia.org/wiki/Markov_chain -
Wikipedia entry for Markov chain.
www.m-i-b.com.ar/mib/letter_pairs/eng/ -
Letter-pairs analysis application, by
Martin Ignacio Bereciartua. Shows elegant output from
a program for reading a text and calculating in real time the
number of times each pair of letters appears.
This kind of display would also be useful for
transition matrices in Markov generation.
kandid.sourceforge.net/index.html -
Kandid. An excellent program on which to end.
