Introduction

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.

New Release of Logic Programming Associates WinProlog

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, https://www.lpa.co.uk. If you would like a WinProlog 4.6 evaluation CD or details of the accompanying promotional offer, please contact LPA.

AI in Gawk and Forth

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.

Links

www.forth.org/ - Forth Interest Group site, linking to tutorials, applications of Forth, and an FAQ.

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.

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.

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.

Perl Style Regular Expressions in Prolog

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.

Links

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

https://en.wikipedia.org/wiki/Regular_expression - Wikipedia entry for regular expressions.

The Future of Logic Programming; or, How XML Saved Prolog

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 https://dtai-static.cs.kuleuven.be/projects/ALP/newsletter/feb04/nav/van_emden/van_emden.html.

The Encyclopedia that Wrote Itself - an Introduction to Evolutionary Art

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

Mark Shaney and the Markov chains

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.


## Links

Evopedia. The three entries I mentioned were Cake Recipe; Low Carb Recipe; and Bush Joke.

www.intelligentsolutionsinc.com/- *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.

https://en.wikipedia.org/wiki/Mark_V_Shaney - Wikipedia entry for *Mark Shaney*, the Markov-generated Usenet user. Links include Shaney in Python.

https://en.wikipedia.org/wiki/Markov_chain - Wikipedia entry for *Markov chain*.

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