Welcome to the November 2004 Newsletter. I like Prolog, and have used it as my language of choice for various applications, including expert systems, analysing financial data, and teaching AI at Oxford University. My most recent project is an algebraic manipulation system for safe spreadsheet construction, to try and reduce some of the billions of pounds lost to spreadsheet errors every year. Having declared a bias to Prolog and logic-based AI, I must add that this is not the only way to go. I've worked, and in some cases fought, with a variety of other languages, and with AI topics ranging from machine learning and artificial life to interactive fiction and drug design. As Dennis said in his welcome to the Premier Issue of the Newsletter, AI encompasses a wide variety of fascinating software and hardware. There's tons of interesting stuff out there, and I hope I'll keep you informed and entertained. If there's anything you'd like to see, do please send me your suggestions.

A Computational Ring Around My Brain - The science fiction of Charles Stross

I could not resist beginning an AI Newsletter with this quote:

Despite all our propaganda attempts to convince you otherwise, AI is alarmingly easy to produce; the human brain isn't unique, it isn't well-tuned, and you don't need eighty billion neurons joined in an asynchronous network to generate consciousness. And although it looks like a good idea to a naive observer, in practice it's absolutely deadly.

Anyone who has wasted a day in fruitless search for a typo or absent-mindedly loaded their morning biscuit into the floppy drive knows the human brain is not well-tuned. And we all hope AI is easy to produce. But deadly? I thought I'd begin this issue with some fiction, to stimulate the sense of wonder and restore the vigour on those days when we feel that never mind solving strong AI, it'll be a miracle if we can even get append to work correctly. The quote is from the short story Antibodies by science fiction writer Charles Stross, in which AI is so feared that the protagonists take some very extreme measures to avert its development:

"Damn it, Bob, I really had high hopes for this world-line. They seemed to be doing so well for a revelatory Christian-Islamic line, despite the post-Enlightenment mind-set. Especially Microsoft - "

"Was that one of ours?". She nodded.

"Then it was a master-stroke. Getting everybody used to exchanging macro-infested documents without any kind of security policy. Operating systems that crash whenever a microsecond timer overflows. And all those viruses!"

The story begins when a computer programmer is notified that all NP-complete problems lie in P, the travelling salesman problem can be solved in O(n2), and thus computer security is forever compromised. Via a sleeper trip to Edinburgh - in this timeline, neither the capital of the Viking Empire, an active volcano, nor a cloud of feral nanobots - and interrogation by police officers playing cheesy psychedelic videos in an attempt to perform a buffer-overflow attack on their limbic systems, the protagonists realise their attempts to cripple computing technology have failed. Even now, artificial intelligence programs are exploiting the NP-complete-is-P discovery to optimise themselves. And these AIs are not nice AIs. They want to take over the Internet and then all the humans, before they eat the entire Universe, converting it into a kind of ubiquitous computational dust in their exponential lust for processing power. Will they succeed? Read the story, and enjoy the amusing little asides, to find out.

Unless you imagine yourself as the nascent AI, Antibodies is not an optimistic story. The Atrocity Archive, which originally appeared in Spectrum SF and is now published in book form, is. It's also an excellent, and funny, combination of secret service novella and computer geekery with the Cthulhu mythos of H P Lovecraft. The main character, when not busy maintaining his department's Beowulf clusters, frankenstein servers and tarot permutators, perusing Knuth's blacklisted 4th volume to the Art of Computer Programming, or attending departmental training courses -

"We're going to try a lesser summoning, a type three invocation using these coordinates I've sketched out on the blackboard. This should raise a primary manifestation of nameless horror, but it'll be a fairly tractable nameless horror as long as we observe sensible precautions. There will be unpleasant visual distortions and some protosapient wittering, but it's no more intelligent than a News of the World reporter - not really smart enough to be dangerous. Manesh, if you could switch on the ABSOLUTELY NO ENTRY sign..."

manages to avert a Nazi invasion which, if not prevented, would rage a wind of desolation and pain through the heart of Europe before plunging the Earth into an eternal fimbulwinter. He also, and this is the really important bit, saves himself from the clutches of his departmental administrator. (I once had an administrator like that, and it wasn't nice. Stross has clearly suffered too. It is clear that he has also lived amongst computer geeks.)
And finally, another chunk of optimism. All the stories mentioned are fun in the way they play with computing and AI, but this is the most relevant to us. As Stross says at www.accelerando.org/, his Accelerando novellas (due out in book form in July 2005) explore the human consequences of the technological revolution, by following three generations of a family through the technological singularity. The quote below is from one novella in the series, Halo, which first appeared in Asimov's Science Fiction and was nominated for the Hugo award:

Welcome to the third decade. The thinking mass of the solar system now exceeds one MIP per gram; it's still pretty dumb, but it's not dumb all over. The human population is near maximum overshoot, pushing nine billion, but its growth rate is tipping towards negative numbers, and bits of what used to be the first world are now facing a middle-aged average. Human cogitation provides about 1028 MIPS of the solar system's brainpower. The real thinking is mostly done by the halo of a thousand trillion processors that surround the meat machines with a haze of computation - individually a tenth as powerful as a human brain, collectively, they're ten thousand times more powerful, and their numbers are doubling every twenty million seconds. They're up to 1033 MIPS and rising, although there's a long way to go before the solar system is fully awake.

Now that's what I want to see. Leave the AI's to do the real thinking, and let the organic bits do what they do best - wibble on about food, sex and football.

Links

www.antipope.org/charlie/ - Stross's main site, including information on his fiction and where to buy it. He has a few short stories on-line. There are also links to his computer journalism - articles from Computer Shopper, writings on Linux and Perl - and his weblog.

www.accelerando.org/ - Another Stross site, devoted to Accelerando. Headed by a US Commission on National Security quote about the accelerating pace of technological change, it explains the motivation behind the stories, and ends with links to nanotechnology, mind-to-computer uploading, and other hi-tech topics.

www.eternalwarriors.com/REVstross1.html - Review of Antibodies and other stories in Toast.

www.nesfa.org/reviews/Olson/AtrocityArchives.html - Review of The Atrocity Archives.

www.asimovs.com/Hugos/Halo.shtml - Online text of Halo, at Asimov's SF.

http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP - What does the discovery that starts Antibodies, all NP-complete problems lie in P, mean? Here, from Wikipedia, is an explanation of P, NP, and why they are so important; and hence, of why some tasks have no efficient algorithm.

Robots Amongst the Roaches - Insect telepresence and the Toy Robots Initiative

In a recent weblog entry, Stross writes that he's treating himself to a new PDA for his birthday. It will have twice the memory of his old server, be 50% faster, and be upgradeable to 10Gb of flash memory. And this little sardine-tin sized thingy holds as much power as a budget server did in 2000, or a fast mid-range Sun box in 1994, or a supercomputer that would have left Seymour Cray drooling a decade earlier. As Stross says, "Yesterday's supercomputer is truly today's toy".

With this in mind, I thought I'd see what's new in robot toys. They've long seemed an ideal setting to develop robotics: competitive, fun, and not too demanding. You might have specced your company's robot cat to recognise its owners' faces from 2 meters after only 3 exposures, but you won't be sued if it fails to, and anyway, some hobbyist will eventually work out how, then publish their code on a toy-hacker's site. Nor is the average toy big enough to run amok and eat the baby, so safety need not be a big concern. However, my first search landed me not at home, but amongst a herd of Madagascan hissing cockroaches at the Carnegie Museum of Natural History.

Within its many exhibits, the museum has live exhibitions of exotic insects. These are as fascinating as any product of evolution, but many visitors fail to appreciate them, as frequent "Ew Gross" comments in the museum visitors' book testify. Providing staff to guide visitors around the exhibitions can help, but this is expensive. Anyway, even with a guide, you can't get close enough to the insects to see the complexity of their anatomy and behaviour.

To solve this, the Toy Robots Initiative at Carnegie Mellon University has worked with the museum to develop a tele-embodiment robot that visitors can drive amongst the insects, in effect shrinking down to insect size and meeting them eyeball to compound eye. Tele-embodiment is the use of robotics to involve a human in a new environment in a way that makes them feel they're actually there. Because of the size difference betwen insect and human, the TRI call this project, "tele-embodiment in scale".

It's interesting that in this project, less was more. The TRI site's Insect Telepresence paper describes as well as the robot's construction, the "Contextual Inquiry and Design" used to determine how the robot should interact with its users (and, in this case, also with the insects). This, eliciting the human-computer interaction requirements, is an essential first stage in design. One requirement that came out of this analysis is that the robot must not be able to harm the insects - some visitors would inevitably try to drive over and squash them, were this possible. Consequently, the designers opted not for a standalone mobile robot but for a camera running on tracks above the insects, capable of being moved around the enclosure and rotated. Certainly, were the robot fully mobile, it would seem difficult to program it to ignore user commands to damage the insects.

Three short videos from the robot can be downloaded from the links below. In the paper - written probably 1999 - the authors state that, after user-testing a prototype in the CMU Mobot Programming Lab, a version was installed as a permanent exhibit near the museum's entrace. It's a nice idea, worth considering for similar exhibits elsewhere. One amusing point to emerge from the user testing was that about 1/5 of the users liked just driving the robot round and round without paying much attention to the insects. As the designers say:

Our theory for this action is that the users are engaged by the motion. The color monitor is extremely large, and so continuous motion is visually stunning to the point that motion sickness is possible. Those behaving this way seem to spend little time actually looking at the bugs, and more time driving like a video game.

Links

www-2.cs.cmu.edu/~illah/EDUTOY/ - Toy Robots Initiative home page. This links to the Insect Telepresence Project, as well as the TRI's other work.

www-2.cs.cmu.edu/~illah/PAPERS/insect.pdf - the Insect Telepresence paper, as PDF.

www-2.cs.cmu.edu/~illah/EDUTOY/movies/bug_back.mov, www-2.cs.cmu.edu/~illah/EDUTOY/movies/bug_ram.mov, and www-2.cs.cmu.edu/~illah/EDUTOY/movies/bug_pear.mov - Three short videos of cockroaches taken by the insect telepresence robot, as Quick Time.

Aesthetic Evolution and Genetic Graphs - The virtual beauties of Karl Sims

Artificial evolution is itself evolving to a point where its products can be as fascinating as those of biological evolution. If the Insect Telepresence project can immerse us in the natural, Karl Sims's work can, with its emphasis on art as well as technology, involve us in the beauty of the artificial.

I came across Sims ten years ago, at an artificial life conference in Brighton. His presentation showed videos of a simulated beachside world - complete with a physics engine which implemented both gravity and friction - in which he had placed an initial population of several hundred simple blocklike creatures with randomly-generated bodies and nervous systems. Each creature was tested for its ability to perform a pre-specified task. Those that were most successful survived, and their genes were copied, combined, and mutated to make offspring for a new population. The new creatures were once again tested, and so evolution continued.

One of the tasks set for the creatures was to move as far as possible in a certain direction. Members of the first generation might only twitch feebly or stand like sticks, but as simulated generations were born and died, some impressive results emerged. I remember a helical snake which had evolved to gain purchase on the ground by friction, whilst moving forward by spiralling along its axis.

In another task, the creatures had to evolve to gain and keep possession of a large virtual cube at the water's edge. One creature evolved huge flippers for this purpose, one of which it wrapped around the cube to protect it, whilst bashing competitors to pieces with the other. There are some pictures of these creatures at Sims's Evolved Virtual Creatures page. No videos unfortunately - it seems the volume of downloads overwhelmed the server.

Genetic graphs for virtual creatures

How do these creatures work? Sodarace is a joint venture between the Soda arts company and Queen Mary College, which enables users to build virtual creatures from simulated springs, muscles and other body parts and then race them against competitors in the Sodarace application. There's lots of documentation, and it's well worth exploring. I mention it here in order to cite an interview with Sims:

Ed: Your Evolved Virtual Creatures are highly successful not only at excelling in their virtual domains, but also as beautiful creations inspiring many to contemplate and explore artificial evolution. Do you have three golden rules for our users that are going to be writing computer programs to generate and optimise racing Sodaconstructor models?

Karl: The main secret I think is designing a good genetic language. You want to be able to describe all possible creatures with some language that you can then use as your virtual DNA. You want it high level enough so you could "design" with it - you should be able to make some successful creatures by hand. You also want random and mutated codes to have a reasonable chance of being viable. I think the language should be able to somehow re-use "ideas" by instancing parts of the creature such as a "leg". Reusable growth rules such as in L-systems or directed graphs can allow this. But at the same time you want it to be flexible enough to describe any possible creature, not just a subset that you've designed into the language. Finally of course you need to mutate and combine the genetic codes from different individuals so you get a good balance of viable offspring and significant changes. I guess that is more than 3 rules, but there you go.
So what are genetic graphs? Most genetic algorithms represent genes as linear strings, mimicking chromosomes. However, Sims's creatures have - as his paper on Evolving 3D Morphology and Behavior by Competition describes - graphs or networks for genes. The idea is that the graphs describe the creatures' shape (the number and connectivity of their body parts) and at the same time, their neurology. Each body part has its own neural control circuitry, and the graph node that determines the part's shape also determines the circuitry. This leads to modularity. If a mutation causes a body part to be duplicated, say, then the control circuitry will be duplicated along with it, increasing the chance that the mutatated individual continues to function in its environment. Details, and diagrams of graphs and the creatures derived from them, can be seen in the paper.

Genetic graphs for drug design and wireless-access-point placement

There are one or two other papers on genetic graphs available on the Web. In common with other representations of genes, genetic graphs can be "direct" or "indirect". Direct genetic graphs not only act as genes, but also as the creature (the "phenotype") derived from it. In contrast, indirect genetic graphs have to be transformed into the phenotype by a "developmental" process - something analogous to embryonic development. Sims's genetic graphs are indirect - the creatures are not themselves graphs, but assemblages of blocks.

Another indirect genetic graph system is Jianjun Hu's EvoGraph, developed at Michigan State University. The site demonstrates its use for optimum placement of wireless access points, and has some downloadable C++ libraries. Direct genetic graphs have been used for molecular design. Here, the object being evolved - the molecule - is the gene. The links below include a paper on this work, and also a simplified account written for drugs designers.

Panspermia, aesthetic evolution and Sims's computer art

As Sims explains in his Sodarace interview, the motivation for the evolved virtual creatures came from his computer art. In Panspermia - named for the theory that life is distributed throughout the universe in the form of germs or spores - Sims created a short and rather lovely animation in which spores land on a barren planet, germinate, and slowly unfurl into graceful and elaborate fernlike plants, which then seed and, cannon-like, blast their own spores back into outer space to continue the cycle. Sims needed a practical way to create these artificial plants, began experimenting with artificial evolution, and then went on to evolve creatures not for their shapes but for their behaviour.

After the virtual creatures work, Sims turned back to art, so-called aesthetic evolution. Here, it's the human rather than the computer that provides the selection pressure. We start with a population of randomly generated art works - images, music, or whatever - and at each generation, the user selects those most desired to pass on for further evolution. The Galápagos page shows this at work in an interactive media installation exhibited at the ICC in Tokyo between 1997 to 2000. As Tom Ray, the inventor of the Tierra artificial life system, writes in an essay on evolution as artist,

Evolution is a creative process, which acting independently, has produced living forms of great beauty and complexity. Today, artists and engineers are beginning to work together with evolution. In the future, it may be possible for artists to work in collaboration with evolution to produce works of art whose beauty and complexity approach that of organic life.

Yes, evolution did create life

Many, many people do not believe anything as complex as a living creature can arise by evolution. The first example I turned up on the Web was an "intelligent design" site - "Intelligent Design, (I.D.) shows the incredible complexity of the world's creatures and it provides compelling evidence that they have been created rather than randomly evolved". Sims's virtual evolved creatures, which modern PCs are surely powerful enough to run, demonstrate that evolution is sufficient, and would make a wonderful educational tool. I commend them to any game designer looking for a new product.

Let's end with another quote, from an interview Sims gave Wired:

Did transferring evolution into a computer diminish Sims's appreciation for the wonders of biological life? Sims says that the projects have actually increased his respect for living things: "Exposing more details about life and how it might have occurred makes it even more amazing. You can't help but appreciate the extreme unlikeliness that any given organism or species ever evolved at all."

Links

www.genarts.com/karl/ - Karl Sims's home page at Genarts. This links to other pages on his work, with copious pictures, including the Evolved Virtual Creatures photos, Panspermia and Galápagos.

http://sodarace.net/index.jsp - Sodarace home page. The interview is at http://sodarace.net/sims/index.jsp.

www.genarts.com/karl/papers/alife94.pdf - Evolving 3D Morphology and Behavior by Competition, as PDF.

www.egr.msu.edu/~hujianju/evograph/ - Jianjun Hu's EvoGraph genetic graph system.

www.nas.nasa.gov/~globus/papers/Nanotechnology98/paper.html - Automatic molecular design using evolutionary techniques.

http://pubs.acs.org/subscribe/journals/mdd/v03/i09/html/felton.html - Survival of the Fittest in Drug Design. This article is on the Modern Drug Discovery site, and gives an easy-to-read summary of the above paper, from the point of view of a drug designer.

www.wired.com/wired/archive/6.10/sims_pr.html - Do-It-Yourself Darwin - Karl Sims invites you to play God among the machines. This is the text of the Wired interview. As it says, "In Sims's virtual biosphere, boredom equals death. It's survival of the aesthetically fittest".

www.his.atr.jp/~ray/pubs/art/ - A paper by Tom Ray, the inventor of the Tierra artificial life system, on evolution as artist. Tom's Tierra home page is at http://www.his.atr.jp/~ray/tierra/index.html.

www.byfaith.co.uk/pauldesign.htm#f - One example from many of a site whose author does not believe evolution created life.

Prolog Code Corner - A preprocessor for functional Prolog

Although Prolog makes some programs remarkably concise, it's less than ideal when we want to write expressions containing nested function calls. The programmer has to unwrap these into sequences of goals, giving code which is verbose and hard to read. In this Prolog Code Corner, I show how to overcome this by writing a preprocessor for a functional dialect of Prolog. Note that here, "functional" has its usual computer science meaning of "programmed in terms of function calls" rather than "working". All my programs work.

The problem

Let us suppose that Prolog's designers had never thought of is for doing arithmetic, but instead had provided predicates such as plus, mult and div, each of which carries out an arithmetic operation on its first two arguments and returns the result in the third. Then instead of being able to write

X is A*B + A*C + A*D.

we would have to code the expression as calls to plus and mult. This would force us to manually unwind the expression and invent new variables to hold intermediate results:

mult( A, B, V1 ),
mult( A, C, V2 ),
mult( A, D, V3 ),
plus( V1, V2, V4 ),
plus( V4, V3, X ).

Fortunately, we do have is, and so we are spared this inconvenience when doing arithmetic. It still faces us, however, whenever we want to write expressions for manipulating sets, vectors, complex numbers; indeed, any time we just want to nest function calls. In effect, Prolog forces us to become our own compilers. Even an ancient language like Fortran does better.

The solution

My answer to this problem was to write a preprocessor. This did two main things. It allowed expressions to occur as the arguments to goals, and generated code that evaluated them and replaced them by their results. They were signalled by the operator eval: thus I can say, for example, in my Prolog source files or to the top-level interpreter:

write( eval(1+2) )

or

write( eval( length( [1,2,3] ) ) )

and have it mean the same as

write( 3 )

This has marvellous benefits for the brevity of my code.

The preprocessor also understands functional definitions. These are indicated by the connective <-, analogous to :-. Using this, I can write code such as

factorial( 0 ) <- 1.
factorial( N ) <- N * factorial( N-1 ).

In the rest of this feature, I explain how I did this. Some of the techniques can be used to extend Prolog in other ways, which may be useful if you want to implement your own favourite notation for a problem.

Translating function calls

The idea is to translate each expression into a pair consisting of a goal and a "result". The result will be the original expression if it needs no evaluation, otherwise a variable which the goal will bind to the result of evaluation. For example:

We can do this very simply. If the expression is a number, we return it as the result. The goal doesn't need to do anything, so we make it true. Otherwise, we assume the expression is a function call. We split this into the function, F, and its arguments. We translate the arguments into a goal AG which evaluates them, together with variable to hold the result of evaluation. We then conjoin to AG another goal FG, formed by calling F on a list of the evaluated arguments with a result variable appended.

Some examples may help. To translate plus(1,2), no code is required to evaluate the arguments, so the goal AG becomes true. The goal FG is the function F - plus - called on the evaluated arguments with a result variable appended. In this case, the evaluated arguments are the same as the originals, so FG becomes plus(1,2,R), where R is the result variable.

For the more complicated expression plus( mult(1,2), 3 ), the goal AG would become - via a recursive call - mult(1,2,R1). The evaluated arguments would becone [ R1, 3 ], where the first one is replaced by the variable holding the result of evaluating it. The goal FG becomes plus( R1, 3 ). And finally, the goal for evaluating the entire goal becomes AG conjoined with FG, or

mult( 1, 2, R1 ), plus( R1, 3, R )  

Here is the translation code. The predicate trans_expr translates the expression in its first argument into a result in its second and a goal in its third. It calls trans_arglist to translate function arguments:

trans_expr( Expr, Expr, true ) :-
        number( Expr ), !.


trans_expr( Expr, Expr, true ) :-
        var( Expr ), !.


trans_expr( Expr, ResultVar, Goal ) :-
    Expr =.. [ F | Args ],
    trans_arglist( Args, ArgResults, ArgGoals ),
    append( ArgResults, [ResultVar], ArgsAndResultVar ),
    ExprGoal =.. [ F | ArgsAndResultVar ],
    Goal = ( ArgGoals , ExprGoal ).


trans_arglist( [ Arg1 | Args ], [ Result1 | Results ], Goal ) :-
    trans_arglist( Args, Results, Goals ),
    trans_expr( Arg1, Result1, Goal1 ),
    Goal = ( Goal1 , Goals ).


trans_arglist( [], [], true ).

Note that we have added a clause which checks for expressions that are variables. These are unlikely to occur as the argument to eval, but will turn up once we start translating definitions, which are likely to contain variables (possibly from their head) in the tail expression, in the way that the second clause for factorial above did:
factorial( N ) <- N * factorial( N-1 ).

Conjoining goals

If you try this code, you will find the generated goals contain a lot of unnecessary trues. We can remove these by writing a special goal-conjoining predicate:

conjoin( true, G, G ) :- !.
conjoin( G, true, G ) :- !.
conjoin( G1, G2, (G1,G2) ).

This is a good utility to have whenever we write programs that code-generate Prolog.

Using goal_expansion

The Prolog I normally use, SWI, contains a number of "preprocessor hooks": predicates that you can define to add your own preprocessing code. These are not in the ISO Prolog standard, but several other implementations, such as SICStus, also provide them. If your Prolog doesn't, you will have to find another way to hook your preprocessor into it. The easiest is to write your own version of consult.

I use the goal_expansion hook to add the eval macro mentioned earlier. As it reads a file, SWI-Prolog hands each goal G appearing in the body of a clause to goal_expansion, passing it as the first argument. If the call succeeds, G gets replaced by goal_expansion's second argument, assumed to be its translation.

First, we write a predicate to translate goals whose arguments may include an eval:

trans_goal( G, GTranslated ) :-
    G =.. [ F | Args ],
    trans_goal_args( Args, ArgResults, ArgGoals ),
    FGoal =.. [ F | ArgResults ], 
    GTranslated = ( ArgGoals , FGoal ).


trans_goal_args( [], [], true ) :- !.


trans_goal_args( [Arg1|Args], [Result1|Results], Goal ) :-
    trans_goal_arg( Arg1, Result1, Goal1 ),
    trans_goal_args( Args, Results, Goals ),
    Goal = ( Goal1 , Goals ).


trans_goal_arg( Arg, Result, Goal ) :- 
    nonvar( Arg ), Arg =.. [ eval , E ], !,
    trans_expr( E, Result, Goal ).


trans_goal_arg( Arg, Arg, true ).

This predicate, trans_goal runs over the arguments of a goal G. If any argument is a term eval(E), trans_goal calls trans_expr on the expression E. It collects the goals for evaluating the arguments and prepends them to G. Thus, the goal
write( eval( plus(1,2) ) )

gets transformed into

plus( 1, 2, R ), write( R ).

Notice that the first clause to trans_goal_arg needs to test whether it is dealing with an eval(E). We take care not to write the eval(E) explicitly, instead calling =.. to test for it. Were we not to do this, then if we already had the preprocessor installed (which we might if repeatedly editing, cnsulting, and testing it), it would try expanding this particular eval(E), with amusing, but probably unhelpful, effects.

Having written the translator, we install it. This involves adding a clause for goal_expansion which calls trans_goal. We also make this clause test whether the goal actually needs translating - whether it does contain an eval - and fail if not. This is good practice, because some Prologs might call goal_expansion over and over again on the same goal if we make it return the original without any change. Here is the code:

needs_translating( G ) :-
    nonvar( G ),
        G =.. [ _ | Args ],
        member( Arg, Args ), nonvar( Arg ), functor( Arg, eval, 1 ), !.  


:- multifile user:goal_expansion/2.


:- dynamic user:goal_expansion/2.


user:goal_expansion( G, GTranslated ) :-
    needs_translating( G ), !,
        trans_goal( G, GTranslated ).

As with trans_goal, we take care to avoid an explicit eval(E) in the code.

Note that there could be could be several different clauses for goal_expansion in force at the same time if you or someone else have installed other preprocessors. Care will be needed to ensure these work correctly together, especially if a single goal contains constructs from different preprocessors, or gets translated by one preprocessor into a construct handled by another.

Translating function definitions

Translating function definitions is now straightforward. To translate

double(N) <- plus(N,N).

we translate plus(N,N), giving the goal plus(N,N,R). We use this as the tail of the new predicate. We then insert R as the final argument of double(N):

double( N, R ) :- plus( N, N, R ).

Here is the code:

:- op( 1200, xfx, user:(<-) ).


trans_def( (Head <- Expr) , (PrologHead:-Tail) ) :-
    !,
    trans_expr( Expr, ResultVar, Tail ),
    trans_head( Head, ResultVar, PrologHead ).


trans_head( Head, ResultVar, PrologHead ) :-
    Head =.. [ F | Args ],
    append( Args, [ResultVar], ArgsAndResultVar ),
    PrologHead =.. [ F | ArgsAndResultVar ].

Using term_expansion

Finally, we install trans_def using the term_expansion preprocessor hook. This resembles goal_expansion, but translates complete terms in the source file. For us, it is simpler to use: we can test whether a definition needs translating just by whether it contains a <- connective; we don't need to decompose definitions in the same way we did with goals; and we don't need to worry about avoiding explicit calls to <- in the translator. Here is the code:

:- multifile user:term_expansion/2.


:- dynamic user:term_expansion/2.


user:term_expansion( Def, DefTranslated ) :-
    trans_def( Def, DefTranslated ).

Extensions and semantic questions

The translator above is pretty basic, and would need extending to be useful. For example, the atom [] (empty list) probably wants to be treated as a constant that stands for itself in the same way as the numbers; non-empty lists almost certainly should be evaluated element by element.

Other constructs that could be added include an expression-disjunction operator. If we call this ;, then E1;E2 would evaluate E1, return its result if it succeeds, and otherwise return that of E2. Ciao Prolog has such a thing. Along different lines, it's probably worth translating +, * and other arithmetic operators into calls to is. My preprocessor does this, enabling me to use them in the definition of factorial shown above.

We need to take care with the semantics. One question is how to distinguish between atom constants and functions of no arguments. For example, how should we invoke read/1 as a function? We can't write read(), because it's not valid syntax. If the translator takes the atom read to denote a call to the predicate, how should we write the atom constant read? On the other hand, if read denotes the atom, then we need a special notation for the function call. In my work, I eventually decided that an atom on its own should be a call, and that to make it a literal, we precede by (backquote), declared as a prefix operator. In fact, I use ` to quote any term, not just atoms.

Another semantic question concerns eval. Should the translator recognise it if it occurs at any level inside a goal, or only at the top level? That is, should the goal

write( pair( eval( plus(1,2) ), 3 ) )

stay as it is, or evaluate to write( pair( 3, 3 ) )? Tempting as it can be just to hack, hack, and hack again, such questions must be considered. And of course, if you are using any preprocessor for serious development, it is essential to avoid changes that break source code already written for it!

The GRIPS functional-Prolog preprocessor

My own preprocessor is named GRIPS; a version for SWI-Prolog can be found at www.j-paine.org/grips.html. It has a number of enhancements beyond the basic code given here, including conditionals, options for specifying evaluation modes for special functions, and a where operator for embedding subsidiary definitions.

Applications

I use functional notation as frequently in my Prolog projects as I do DCGs, indeed probably much more. Firstly, it just is convenient when writing complicated expressions. It also saves thinking up names for result variables, and hence helps mitigate the psychological condition known as "naming fatigue" - a steadily increasing inability, as the day wears on, to invent meaningful identifiers. (This is not meant to be facetious. I once read a book on programming which asserted that many programmers suffer from naming fatigue.)

Functional notation is also useful because it makes data flow explicit. When reading a goal such as

bar( C, D, A ), foo( A, B ), fred( B, D )

one has to examine the predicate definitions and accompanying comments or mode declarations before being sure of the data flow. The same call in functional notation makes the flow immediately clear:

fred( foo( bar(C,D) ), D )

For this reason, I have experimented with functional notation in teaching Prolog, to make it easier for novices to read Prolog code.

I am also using GRIPS as the basis of a computer-algebra-style interface for manipulating spreadsheets. This works in the same way as Mathematica, Maple, and other algebra programs, except that the objects handed on from function to function are spreadsheets and parts of spreadsheets rather than numbers and algebraic expressions. Functional notation is useful for both: typically in an interaction, the user puts one or more things in, carries out a transformation, and gets one thing out which is then either stored for future use or displayed.

Finally, I have experimented with the idea that dynamic Web pages can be regarded as functions generating HTML, and should be written this way, so that all variables referenced on the pages are explicitly passed as function arguments. This aids readability, and also makes it simple to include parts of a page inside one another, since the includes just become function calls. This is something that Java Server Pages and other popular Web-page generators do very inelegantly.

Links

www.j-paine.org/grips.html - Source and documentation for the GRIPS preprocessor.

http://babel.ls.fi.upm.es/html/ciao1.9/ciao_html/ciao_100.html - Functional notation in Ciao Prolog, an open-source next-generation Prolog developed at the Computational Logic laboratory at the Universidad Polit&eeacute;cnica de Madrid. See http://clip.dia.fi.upm.es/Software/Ciao/ for the Ciao home page.

www.j-paine.org/csp.html - The Watchmaker And The Spreadsheet Factory, a demonstration of spreadsheet manipulation in Prolog. Some of the examples demonstrate the use of functional notation.

www.j-paine.org/wsm.html - Dynamic Web pages in Kawa. This implements the idea of Web pages as functions, using the Kawa dialect of Scheme. A Prolog version is still under development.

Until next month.