For those who don't have Lisp handy, here's some sample output:
JOE WAS NEAR THE CAVE.
JOE KNEW THAT JOE WAS NEAR THE CAVE.
IRVING WAS NEAR THE OAK-TREE.
IRVING KNEW THAT IRVING WAS NEAR THE OAK-TREE.
JOE KNEW THAT IRVING WAS NEAR THE OAK-TREE.
THE WATER WAS NEAR THE RIVER.
JOE KNEW THAT THE WATER WAS NEAR THE RIVER.
THE HONEY WAS NEAR THE ELM-TREE.
IRVING KNEW THAT THE HONEY WAS NEAR THE ELM-TREE.
THE WORM WAS NEAR THE GROUND.
JOE KNEW THAT THE WORM WAS NEAR THE GROUND.
IRVING KNEW THAT JOE WAS NEAR THE CAVE.
THE FISH WAS NEAR THE RIVER.
IRVING KNEW THAT THE FISH WAS NEAR THE RIVER.
One day,
JOE WAS THIRSTY .
JOE WANTED NOT TO BE THIRSTY .
JOE WANTED TO BE NEAR THE WATER.
JOE WENT TO THE RIVER.
JOE WAS NEAR THE RIVER.
JOE DRANK THE WATER.
JOE WAS NOT THIRSTY .
The end.
The original Talespin was Jim Meehan's PhD thesis, if I remember correctly. Jim advised my team for a week one time, many decades ago, and he sort of became a role model to me showing that one could make a good living in AI. He works at Google now, or at least did when I was there.
This miniature program was in a Shank and Riesback book, which I still have.
The (con ...) subtree has to be freshly allocated because ,con is inserted into it. The (val ...) subtree has to be new because (cp ...) has to be new because (part ...) has to be new because ,actor is inserted into it. And so the (mloc ...) tree has to be new because (con ...) and (cp ...) are new.
The only static structure in this backquote are the symbols themselves.
Yes: ANSI "CL 2.4.6 Backquote" does say that constructed copies might share structure with the template. However sharing can only take place where it is rationally possible. If I say that you're permitted to levitate, that doesn't mean you can.
If an evaluation of a backquote produces (1 2 3) and another evaluation of the same backquote produces (1 4 5), and no destructive splicing operators are used, these outputs cannot share list structure with each other or the template. This is because none of their corresponding structural parts are similar under any equality function.
How about if the substitutions are the same? Can we have (eq (mloc x y) (mloc x y))? I'm afraid not; for that to work for any x y pair, the function would have to be memoized. I don't know of any Lisp that automatically memoizes functions. (That would be a bad idea to do for any functions for which the programmer didn't explicitly request memoization.)
It could be done in situations when x and y are constants, like (mloc 'a 1), through a combination of aggressive inlining and backquote optimization. For that to work, backquote would have to be expanded after function inlining (a very curious architecture, indeed) so that the effects of propagation of the constants from the call sites into the function body would be visible to the backquote expander. Many CL implementations of backquote expand it at read time. Those which do it later have a backquote macro, which gets fully processed before any compilation takes place where inlining code transformations may happen.
I don't think that such liberties are implied by 2.4.6. The obvious intent is that pieces of the template structure, in particular tails of lists at any level, can be used like constants. The outputs of multiple evaluations of `(,arg a b c) can obviously share the (a b c) part. They cannot share the ,arg part, unless arg has the shape of a constant visible to backquote like for instance 'whatever. That is to say, `(,'X a b c) can be transformed by backquote into (QUOTE (X A B C)): backquote can recognize the ,(QUOTE X) and treat it as if it were X.
If the goal were to have a mutable list data structure, then switching to a backquote representation is a source code optimization which might or might not be possible, based on what the list structure should be. The user then needs to find out if it is possible or not. That may cost additional time and may introduce errors.
What's the current state of the art in this kind of software and what is it called, anyway? I assume it should be natural language synthesis or story generation?
Story generation, or occasionally automated storytelling, is the keyword for systems that aim to write complete stories, with a narrative structure. There is also a field of natural language generation (NLG) that more broadly looks at generating text (for various purposes); it's a much bigger field.
