The tilt programming language

by Jim Davies, Jennifer Mankoff

and Terry Shikano

TABLE OF CONTENTS

Introduction

- what a genetic algorithm is

- what genetic programming is

- crossover and mutation

- how crossover and mutation are normally done

- how tilt can improve on this

- design goals

- language requirements

Comparisons to Other Languages

User's Manual

- the BNF

- the crossover! command

- the replace! command

- the choose command; using probabilities

- random generation of code

- defining pools

Conclusions

Reference Manual

Default Scheme BNF

References

INTRODUCTION

What a genetic algorithm is.

A genetic algorithm is a process that adapts a reproducing population

according to some notion of fitness. Evolution of any sort requires the

following:

* a population of entities that reproduce

* diversity of traits

* an environment that selects certain members of the

population to reproduce over others because of difference in traits.

What genetic programming is.

Genetic programming is the use of genetic algorithms to create

programs with a certain function. This example demonstrates the approach:

A user wants to make a program that can sort a list quickly. He

randomly generates 500 programs, and tests them all according to how

well they sort (based on accuracy and speed). He tests each one of

them 10 times and gives the average score to that program. Each

program receives a score. The programs are ranked according to score,

and the bottom 250 are deleted. This is selection. The remaining 250

are copied, resulting in a population of 500 once again. This is

reproduction. The new 250 are not copied perfectly, but are changed

slightly. Some have pieces from more than one of the originals. Some

are changed slightly in random ways. Then, the entire operation is

done to the new population. This pattern repeats. Over the course of

the process, the average sorting quality has slowly increaces.

In the above example, the 500 programs are the population. Different

sized populations can be used, but 500 is sufficient for many simple

problems (Koza 1993). A generation is the time between any two

selections. In the example, the top scoring half are selected, but

one could select the top two, only those that reach achieve a certain

score, or even an amount of reproduction in proportion to the fitness.

What deterimes the quality of how well the program sorts is called the

fitness function. When a program is copied, the copy is called the

child and the copied is called the parent. Crossover is when a child

has parts from more than one parent. Crossover is analogous to sexual

reproduction in nature. Mutation is when a program is changed slightly

in a random way. The algorithm can run for a specified amount of time

or it can terminate when the average fitness reaches a certain point.

Crossover and mutation.

In general, most adaptation comes as a result of crossover. Mutation

plays a smaller role, but can be important for removing the population

from local maxima (Back 1996). The tilt programming language focuses on

the mutation and crossover aspect of genetic programming: it provides

the programmer an easy way to describe how mutations and crossovers

can happen.

How crossover and mutation are normally done.

Each Lisp S expression is a tree.

(list (+ 1 2) (- (+ 2 3) 1))  

                list
                /  \
               +    -
              /\    | \
             1  2   +   1
                    /\
                   2  3

and each node gets assigned a number

1 2 3 4 5 6 7 8 9

(list (+ 1 2) (- (+ 2 3) 1))

One of the nodes is selected to be the cutoff point.

Say 5.

Then we have program2:

1 2 3 4 5

(first (rest (cons 1 2)))

and we get a cutoff point there, like 4. Now we clip the first at 5

and replace program 2 with it at 4:

(first (rest (cons (- (+ 2 3) 1) 2)))

This is basically how crossover is done with programs.

By default tilt specifies that there is a 90% chance that interior

nodes will be chosen, and a 10% chance that leaves will be chosen, as

swapping leaves is more like normal mutation, which is has not been

found to be helpful.

How tilt can improve on this.

Tilt's replace command can act as a kind of halfway between crossover

and mutation: it retrieves tree segments of a certain type and can

determine what type gets put in. In this way the programmer can

choose how drastically she wants the programs to be changed.

Tilt also allows multiple crossover and mutation kinds, and can assign

probabilities to them. So the tilt code can specify that mutations

occur rarely and that crossover happens more often.

Design goals.

The original design goals were uniformity, redundancy, orthogonality,

and locality/linearity. The original tilt concept was broader in

scope; as the project evolved its purpose became more specific and

defined. At first tilt was meant to be a language with which one would

write programs that could generate output with a certain syntax,

defined at multiple levels. The target problem was fiction

generation. The idea was that a tilt program could know the basic

elements of a story at a high level-- the word "tilt" referred to the

main conflict in a story.

Other applications of tilt that were planned were the generation of

test cases for software and mutation for genetic programming. We

found the fiction writing aspect too ambitious, and ended up focusing

on the mutation and crossover of scheme programs for genetic

algorithms as an interesting problem of appropriate scope.

LANGUAGE REQUIREMENTS

Tilt programs modify scheme code, so it is very handy to be able to

use the scheme commands in the tilt program. This allows tilt

programmers to do complex, sophisticated genetic programming.

Every expression in tilt should return some value. This is tilt's

functional aspect. If it does not return a value or a list of values,

it returns #t on success and nil or an error on error. This is

important because when the program has to terminate, it needs to spit

out a valid program. By requiring each expression, tilt can keep

track of what the latest successful change was.

Tilt should be of use to those doing genetic programming, and allow

all of the common functions normally used in genetic programming. The

exception is the fitness evaluation.

Tilt allows someone without probability training to make use of

randomness in the tilt program. A programmer may want to specify the

probability distribution of items in a pool, if not specified or

specified in a novice-like manner, tilt normlizes the distribution and

generate more easily-managable distribution..

COMPARISONS TO OTHER LANGUAGES

TXL (ftp://ftp.qucis.queensu.ca/pub/txl/) is another tree

transformation lanuage which performs source to source transformations

using a set of transformation rules. A TXL program defines its own

context free grammar according to which the input can be broken into

parts, and rules are constrained to preserve grammatical structure.

The basic unit in the grammar is the define statement. Each define

statement gives all of the alternative forms for one nonterminal type

corresponding roughly to the set of productions for a signal

nonterminal in a BNF grammar.

e.g.

define expression

[number]

| [expression] + [number]

| [expresison] - [number]

end define

Once a TXL program has parsed the input, it transformins the input

into a parse tree for the desired output using functions and rules. A

function has at least a pattern and a replacement:

e.g.

function name

replace [type]

pattern

by

replacement

end function

where type is the nonterminal type of parse tree to be transformed,

and pattern is a pattern which the functions's argument tree must

match in order for the function to transform it. It only transforms

the match it has found first.

For example, the following function changes 5 to 6

function fiveToSix

replace [number]

5

by 6

end function

Rules are similar to functions except that the former searches the

scope tree for matches to its pattern and replaces every such match.

e.g.

rule everyFiveToSix

replace [number]

5

by 6

end rule

fiveToSix transforms the input values [1 5 7 9 2 5 4] into [1 6 7 9 2 5 4]

while everyFiveToSix generates [1 6 7 9 2 6 4].

Both TXL and NewYacc can modify input program in a systematic manner,

whereas tilt modifies input program in more random fashion. Thus

neither TXL nor NewYacc are ideal for genetic programming, where

random diversity is key. Tilt was created to provide an easy way to do

this.

USER’S MANUAL

Tilt is used to specify how crossover and mutation occurs in

evolutionary programming in scheme. To use a tilt program, a higher

level program (the meta-program that's running the genetic algorithm)

calls the tilt program and passes it a file. The meta-program decides

which members of the population to send to this file, and there can be

any number of them. The names given to the functions therein need to

correspond to the names used in the tilt program. For the rest of

this paper, PROGRAM1 and PROGRAM2 will refer to two hypothetical

functions in the input file for a tilt program. The tilt program can

refer to any functions defined in this input file. When the tilt

program is run, it actually changes the functions in the input file

(not a copy of them). The meta-program can then reintroduce them into

the population.

The BNF.

Tilt can parse scheme code and make replacements and changes

of many kinds. In order to do this parsing, a version of the BNF for

scheme is included in the tilt interpreter. If the programmer wants to

use a different BNF, the file can be specified with the load bnf

command. If it is used, it should usually be the first command in the

tilt program.

(load bnf filename)

The crossover! command.

Now let's look at a simple program.

;; example code 1

(crossover! (PROGRAM1)

(PROGRAM2))

In this program, there is a random crossover from PROGRAM1 to

PROGRAM2. Some tree section in PROGRAM1 clobbers a tree in

PROGRAM2. The crossover occurs as described in the

introduction. crossover! has an exclamation mark after it to remind

the programmer that the command actually is destructive to a file.

The replace! command.

Note that this is all that is required for the tilt program, and this

much is sufficient for genetic programming to take place. Now let's

look at the replace! command. Here's another short program:

;; example code 2

(replace! (choose 1 of (get <procedure-call> PROGRAM1))

with

(get <procedure-call> PROGRAM2))

We will break down this command into sections. Note the piece that

says

(get <procedure-call> PROGRAM1)

This returns a pool of all instances of procedure calls in PROGRAM1.

A pool is a set of elements, each of which has a probability

associated with it. Tilt knows what a <procedure-call> is based on

the scheme BNF. So when we do

(choose 1 of (get <procedure-call> PROGRAM1))

it randomly returns one thing from the pool. Specifically, it returns

a node of that one thing chosen. A node is a data structure that

stores where a pool element came from. Essentially, it's a pointer. If

more than one thing is chosen, as in

(choose 10 of <pool>)

then choose returns a pool.

So far, nothing in example 2 has changed anything in the target file

containing PROGRAM1 and PROGRAM2. The replace! command is where the

file changing happens. The node returned by

(choose 1 of (get <procedure-call> PROGRAM1))

gets clobbered by what gets returned by the expression following the

with keyword, which in example 2 is

(get <procedure-call> PROGRAM2))

which is a pool. replace! randomly chooses one element of the pool.

So what example 2 does is it takes a procedure call from PROGRAM1

and replaces it with a procedure call from PROGRAM2.

The choose command; using probabilities.

Let's say that you wanted to replace! half the time and crossover the

other half of the time. You can use the choose command to choose a

procedure as well. See example 3.

;; example code 3

(choose 1 of

( (begin

(crossover! (PROGRAM1) (PROGRAM2))

(crossover! (PROGRAM1) (PROGRAM2))

(crossover! (PROGRAM1) (PROGRAM2))))

( (replace! (choose 1 of (get <procedure-call> PROGRAM1))

with

(get <procedure-call> PROGRAM2)))

)

The begin command is not specific to tilt, but a scheme command that

tilt inherits. It runs in sequence the expressions that follow. So

in this case there are three seperate crossovers occuring, one after

the other. They are descructive, so there is a chance that the first

crossover will be undone by the second! The seperate crossover! and

replace! commands should be familiar. The `choose 1 of' command will

randomly take one of the following expressions, either

( (begin

(crossover! (PROGRAM1) (PROGRAM2))

(crossover! (PROGRAM1) (PROGRAM2))

(crossover! (PROGRAM1) (PROGRAM2))))

or

( (replace! (choose 1 of (get <procedure-call> PROGRAM1))

with

(get <procedure-call> PROGRAM2)))

Choose assumes that the probability of all expressions are equal

unless otherwise specified. But it may be that the programmer wants

crossover to happen much more often than the replace. In this case

the programmer is free to assign probabilities to the choices. For

example:

;; example code 4

(choose 1 of ( .6 (crossover! (PROGRAM1) (PROGRAM2)) )

( .4 (replace! (choose 1 of (get <procedure-call> PROGRAM1))

with

(get <procedure-call> PROGRAM2)) ))

The probabilities (.6 and .4) are optional, but if they are there

choose will do the first 60% of the time and the replace 40% of the

time.

The programmer does not need to make sure that the numbers add

up to one, however. Any numbers can be put into the probability

slots, and tilt calculates the appropriate chances. This is how it

works: If none of the choices have associated probabilities, then all

have an equal chance of being chosen. If one or more have

probabilities, then those choices without probabilities are given the

average probability of the choices that do have assigned

probabilities. When all the choices have numbers, the list of numbers

is normalized to one, making each number a true probability.

Example code 5 is like the last example 4, but now the probabilities

attatched add up to 200. The two weights are normalized by tilt to

.25 and .75 respectively.

;; example code 5

(choose 1 of

( 50 ((crossover! (PROGRAM1) (PROGRAM2))

( 150 ((replace! (choose 1 of (get <procedure-call> PROGRAM1))

with

(get <procedure-call> PROGRAM2))))

)

Random generation of code.

Let's imagine that you want to replace a derived expression in

PROGRAM1 with a random derived expression. Tilt can do

this because it has the BNF. The command generate is used to do this:

(generate 1 <derived expression>))

What tilt does is it makes pools for all of the nonterminals in the

scheme BNF, based on all of the examples of the nonterminals appearing

in PROGRAM1, PROGRAM2, etc. So when you ask tilt to generate 1

derived experssion, it will return an expression from the pool. The

pool is not affected by this. If you try to generate 10 things from a

pool containing only one element, then you will get 1 element from the

pool, and the remaining 9 will be randomly generated from the

BNF. Note that this is the crucial difference between generate and

choose: choose does not guarantee unique returns. If you ask choose to

get 10 elements from a 1 element pool, it will return the same element

10 times. If there is nothing in the pool at all, choose returns nil.

One call to generate will return unique elements. If generate uses up

everything in the pool then tilt uses the BNF to actually randomly

generate an example of that nonterminal. Let's say that tilt gets the

following command, when there are no digits in the <digit> pool.

(generate 1 <digit>)

This command would go to the scheme BNF, look up digit, and randomly take a member of the set described. Some nonterminal definitions

specify a undetermined length, such as <string>:

<string> --> " <string element>* "

In this case the string could potentially be infinitely long. To avoid

this problem, generate assumes a depth of 10. This means that any

repeat operator (*, +, etc.) can be used a maximum of 10 times by

default. This can be overridden with

(generate 1 <string> to depth 500)

Defining pools.

In addition to the pools automatically created by tilt based on the

nonterminals, the programmer can specify further pools using the

define command. Things are added to the pool with the add command.

;; example code 6

(define foo '())

(add .4 (generate 1 <derived expression>) foo)

(add .4 (generate 1 <cond clause>) foo)

The first line in example code 6 creates a new pool called foo that is

empty. The second line adds something to foo. What it adds is a

derived expression from the derived expression pool. It is added with

an associated .4 probability. The third line adds a cond clause to

foo. Now, when the foo pool is called it will return that derived

expression (the same one every time) or the cond clause (the same

one every time.) New things can be added to foo, with or without

probabilities.

If a probability is not specified, then all the probabilities in the

pool are recalculated as in the choose command described above. Let's

extend example code 6.

(replace! (choose 1 of (get <derived expression> PROGRAM1))

with foo)

This replace command notes a derived expression in PROGRAM1 and

replaces it with something from foo. Tilt knows to take something

from foo when it follows a with command. More code:

(define clo (get <derived expression> PROGRAM1))

(define bar '())

(add .1 (generate 1 <derived expression>) bar)

(add .2 (choose 1 of (get <derived expression> PROGRAM1)) bar)

(add .3 clo bar)

(replace! (choose 1 of (get <cond clause> PROGRAM2))

with

bar)

clo is a pool of derived expressions from PROGRAM1. Note that it is a

pool, not an individual element, because we used the get command

rather than the generate command. When you ask for a bar, there is a

weight .1 that you will get some derived expression from the pool.

There is a .2 weight that you will get a derived expression

specifically from PROGRAM1 (of course, all of PROGRAM1's derived

expressions are already in the pool). The weight is .3 that it will

return some <derived expression> from the clo pool. When you ask for

something from a pool x and it refers you to another pool y, tilt asks

it for one element of that.

CONCLUSIONS

1. Uniformity

To promote ease of learning and reading the syntax

should be consistent.

Tilt inherits the uniform syntax of scheme: The first atom in every

expression is a function, for example. Some of the commands in tilt

are rather complicated, and in those cases we attempted to make them

as uniform as possible.

Probability weights can be assigned to elements in pools, and can be

assigned to different expressions in a choose command. In both

instances the probability preceeds the element, but in the choose

expression, expression probabilities are enclosed in parentheses.

(add .1 (generate 1 <derived expression>) foo)

(choose 1 of

(50 (begin

(crossover! (PROGRAM1) (PROGRAM2))

(crossover! (PROGRAM1) (PROGRAM2))

(crossover! (PROGRAM1) (PROGRAM2))))

(150 (begin (replace (choose 1 of (get <procedure-call> PROGRAM1))

with

(get <procedure-call> PROGRAM2))))

)

2. Redundancy

To promote ease of reading and learning, there

will be multiple ways to do the same thing.

Redundancy is most helpful in languages with many functions-- it can

be difficult to remember how to do something, so having many ways to

do it makes programming easier. Tilt turned out to be a small

language, thus reducing the need for our original goal of

redundancy.

One example of redundancy is in the way that the probabilities are

specified. The numbers do not have to add up to 1; since the numbers

are normalized only the relative size of the numbers makes a difference.

3. Orthogonality

To the extent possible we will try to make

commands work together.

Certain commands are overloaded to facilitate orthogonality. The

choose command can be used to pick a procedure or to pick a member out

of a pool. The replace with command can take a pool or a node.

4. locality/linearity

It should be easy to read and tell what kinds

of things the program made will generate.

Although the nature of crossover and mutation is random generation,

there is a level at which the tilt code reader can see what will

happen in the program. The nonterminals are used directly from the

BNF of scheme, and extensions made by the programmer can be named

meaningfully, so that the code reader can see what kinds of things

replace others.

REFERENCE MANUAL

Tilt is a procedural language with a functional-language flavor. It

runs on top of a functional language, scheme. Thus, it requires the

scheme run-time environment. It can be run either as an interactive

process or as an executable. The control regime of tilt is a von

Neuman, fetch-execute style.

The second method is useful when a programmer needs to deal with the

entire genetic programming process. That is, a top-level program runs

tilt to modify the input programs and another fitness function to

evluate the tilt output for the next iteration. For example, a C

program with multiple threads can run several tilt programs at a time

to handle one cycle of evolution and other threads evaluating tilt

output. The C program returns 1) when the fitness function finds the

optimal program or 2) when the maximum number of life-cycles is

reached.

Tilt tries to keep the input program in a valid state. Thus, when a

run-time error occurs, it outputs the state of the last successful

change (commit point) and aborts the execution returning an error.

Formal syntax and semantics.

The lexical issues are the same as that of scheme, and are answered in

the R5RS scheme documentation.

Tilt is very similar to Scheme, and we have extended a subset of the

Scheme BNF (included in this document) in our defenition of Tilt. In the

following grammar, nonterminals in lowercase refer to nonterminals

from the Scheme BNF. Nonterminals in uppercase are specific to tilt.

keywords: add combine crossover! generate choose of node node internal leaf load bnf populate from get replace! with replace! using pool function   A valid tilt program is described by an extension to the schme BNF. Specifically, the nonterminal <expression> is extended to include one additional rule:   <expression> --> <variable> | <literal> | <procedure call> | <lambda expression> | <conditional> | <assignment> | <derived expression> | <macro use> | <macro block> | <EXPRESSION>   When nonterminals occur more than once in the same rule, they are assumed to map to potentially different code (ie, <N> won't necessarily be the same number when it appears repeatedly in the same rule).   <NODE> --> <token> <CLOSURE> --> <token> <POOL> --> <token>   /* here the outer "<" and ">" are literals */ <NONTERMINAL> --> <<token>>   <N> --> <ureal> <M> --> <ureal> <PROBABILITY> --> <ureal> <VALUE> --> <datum> | pool <NAME> | function <CLOSURE> <EXPRESSION> --> <POOL> | (add [<PROBABILITY>] <NODE> <POOL>) | (add [<PROBABILITY>] function <CLOSURE> <POOL>) | (add [<PROBABILITY>] pool <POOL> <POOL>) | (combine <POOL>+) | (crossover! (<datum> [:<NODE>]) (<datum> [:<NODE>])) | (generate <N> <NONTERMINAL> [to depth <M>]) | (choose <N> of <POOL>) | (choose <N> of ([<PROBABILITY>] <expression>)*) | (node [internal <N> leaf <M>] <expression>) | (node [<NONTERMINAL> <N>]+ <expression>) | (load bnf <string>) | (populate from <datum>) | (get <NONTERMINAL> <expression>) | (replace! <NODE> with <POOL>) | (replace! <NODE> using <NONTERMINAL>) | (replace! <NODE> with <NODE>) ONT>

  semantics:   -------------------- <NONTERMINAL> Any nonterminal in the scheme BNF (see scheme BNF). -------------------- <NODE> Refers to a tilt datatype (essentially, it's a scheme pointer) -------------------- <CLOSURE> Refers to a tilt closure which can be run. This must return a valid scheme <datum> (*note* scheme, not tilt)   -------------------- <POOL> Refers to a tilt datatype which contains <PROBABILITY>, <VALUE> pairs. '() is considered to be an empty pool.   <PROBABILITY> is the probability that a given <VALUE> will be chosen from a pool (eg by the choose keyword). If only some of the values have assigned probabilities, the un-assigned values will be given a probability equal to the average of the assigned probabilities. Then all probabilities are normalized to one.   <VALUE> is either a scheme <datum>, another pool, or a tilt function.   Every <POOL> data structure keeps track of where values of type <datum> came from (ie, what points at them), if they are part of some other structure. For example, if a tilt program put the value (or 3 #f) in a pool, and that value came from a list of the form (if (or 3 #f) 3 5), then tilt would need to store (cdr (if (or 3 #f) 3 5)) somewhere.   -------------------- Unless specified, the functions describe below return #t on success, otherwise an error.   (load bnf <string>)   <string> should be a file name   This loads in a BNF from a file. At that time, an empty pool is created for each non-terminal in the BNF (these are populated by calls to get). A default BNF is provided at the beginning of a tile program. This can be changed using load bnf, although it should be changed to be subset of scheme (e.g. new rules should describe valid scheme programs). load bnf returns an error if there is a parsing error, and #t otherwise.   -------------------- (crossover! (<datum> [:<NODE>]) (<datum> [:<NODE>]))   will pick the two nodes randomly if not specified (with a 90% chance of picking internal nodes, 10% leaves). It will then do the standard genetic algorithm crossover described in the introduction. crossover! returns nil if there is an error, #t otherwise. It changes both <datum> permanently.   -------------------- (generate <N> <NONTERMINAL> [to depth <M>])   uses other nonterminal's pools and the BNF to randomly generate <N> values for the <NONTERMINAL> pool (all of type function, since they have no <NODE>s, as in add). In the case of recursive rules, it will max out a depth 10, or <M> if to depth <M> is specified. This will copy <VALUE>s from other pools if possible. It returns the generated pool, or if <N> is 1, the generated <VALUE> (a scheme <datum>). Upon error, it returns nil.   -------------------- (choose <N> of <POOL>)   will pick <N> values from the <POOL>, with either equal probability, or the probability specified by the elements of the <POOL>. Probabilities in the pool are automatically normalized to values between 0 and 1 by choose. choose returns a <POOL> of the chosen <VALUE>s, with no probabilities assigned, or a <VALUE>'s <NODE> if <N> is 1. If the <VALUE> has no node, the <VALUE> itself is returned. If a chosen <VALUE> is a function <CLOSURE> the result of calling <CLOSURE> is used as a <VALUE> (of type <datum>). If a <VALUE> is a pool <NAME>, the result of calling (choose 1 of <NAME>) is used. It returns nil if there is an error.   (choose <N> of ([<PROBABILITY>] <expression>)*) will run <N> of the <expression>s, chosen randomly or according to the specified <PROBABILITY>s as described above.   -------------------- (node [internal <N> leaf <M>] <expression>) (node [<NONTERMINAL> <N>]+ <expression>)   returns a <NODE> (pointer into) the expression chosen either randomly, or with probability according to whether it's internal, a leaf, or matches the given set of <NONTERMINALS> as specified. It returns an error if there is an error.   -------------------- (populate from <datum>)   <datum> is some scheme program (not a tilt program) which will be parsed, and the pools of all non-terminals matched during parsing will be populated with the associated code. It returns a list of all the populated pools on success, otherwise nil.   -------------------- (get <NONTERMINAL> <expression>)   returns a <POOL> of all the occurrences of <NONTERMINAL> in <expression>. Each time get is called, it automatically add anything new if finds to the pool associated with <NONTERMINAL> (see load bnf)   -------------------- (replace! <NODE> with <POOL>) (replace! <NODE> with <NODE>)   The <NODE> pointer is changed to point at the result of a copy of the value associated with (choose 1 <POOL>) or <NODE>. This returns nil on error, #t otherwise.   (replace! <NODE> using <NONTERMINAL>)   Replace will choose a <VALUE> (and associated <NODE>) from the <NONTERMINAL> pool, and then it will look up the nonterminals in the rule for <NONTERMINAL> (e.g. <formals> and <body> for <lambda expression>). If the <expression> pointed at by <NODE> has any such nonterminals, they will be used in order, until they are used up, to replace the corresponding terminals in the chosen <VALUE>. The result will be copied into the <expression> pointed at by <NODE>.   e.g.   (replace! (or #t 1 2) using <derived expression>)   The <derived expression> pool contains (and (foo) bar) <- randomly chosen (or (baz) quux) since we have (and <test>*) as our rule, and #t is a <test>, we get (and #t 1).   -------------------- (add [<PROBABILITY>] <NODE> <POOL>) adds <NODE> and it's associated <VALUE> to <POOL> with probability <PROBABILITY> if specified.   (add [<PROBABILITY>] function <CLOSURE> <POOL>) (add [<PROBABILITY>] pool <POOL> <POOL>) adds the appropriate function or pool to <POOL> with probability <PROBABILITY> if specified.   (add [<PROBABILITY>] <datum> <POOL>) calls (add function (lambda () <datum>) <POOL>) with probability <PROBABILITY> if specified.   -------------------- (combine <POOL>+) basically appends two <POOL>s together and returns the result.     SCHEME BNF       /** This BNF is provided by default to the tilt programmer.   All spaces in the grammar are for legibility. Case is insignificant; for example, `#x1A' and `#X1a' are equivalent. <empty> stands for the empty string.   The following extensions to BNF are used to make the description more concise: <thing>* means zero or more occurrences of <thing>; and <thing>+ means at least one <thing>.   <Intertoken space> may occur on either side of any token, but not within a token.   Tokens which require implicit termination (identifiers, numbers, characters, and dot) may be terminated by any <delimiter>, but not necessarily by anything else. **/   <token> --> <identifier> | <boolean> | <number> | <character> | <string> | ( | ) | #( | ' | ` | , | ,@ | . <delimiter> --> <whitespace> | ( | ) | " | ; <whitespace> --> <space or newline> <comment> --> ; <all subsequent characters up to a line break> <atmosphere> --> <whitespace> | <comment> <intertoken space> --> <atmosphere>*   <identifier> --> <initial> <subsequent>* | <peculiar identifier> <initial> --> <letter> | <special initial> <letter> --> a | b | c | ... | z   <special initial> --> ! | $ | % | & | * | / | : | < | = | > | ? | ^ | _ | ~ <subsequent> --> <initial> | <digit> | <special subsequent> <digit> --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <special subsequent> --> + | - | . | @ <peculiar identifier> --> + | - | ... <syntactic keyword> --> <expression keyword> | else | => | define <expression keyword> --> quote | lambda | if | set! | begin | cond | and | or | case | let | let* | letrec | do   <boolean> --> #t | #f <character> --> #\ <any character> | #\ <character name> <character name> --> space | newline   <string> --> " <string element>* " <string element> --> <any character other than " or \> | \" | \\   <number> --> <prefix> <complex> <complex> --> <real> | <real> @ <real> | <real> + <ureal> i | <real> - <ureal> i | <real> + i | <real> - i | + <ureal> i | - <ureal> i | + i | - i <real> --> <sign> <ureal> <ureal> --> <uinteger> | <uinteger> / <uinteger> | <decimal> <decimal> --> <uinteger> <suffix> | . <digit>+ #* <suffix> | <digit>+ . <digit>* #* <suffix> | <digit>+ #+ . #* <suffix> <uinteger> --> <digit>+ #* <prefix> --> <radix> <exactness> | <exactness> <radix>   <suffix> --> <empty> | <exponent marker> <sign> <digit>+ <exponent marker> --> e | s | f | d | l <sign> --> <empty> | + | - <exactness> --> <empty> | #i | #e <radix> --> <empty> | #d   /** <datum> is what the read procedure (section see section Input) successfully parses. Note that any string that parses as an <expression> will also parse as a <datum>. **/   <datum> --> <simple datum> | <compound datum> <simple datum> --> <boolean> | <number> | <character> | <string> | <symbol> <symbol> --> <identifier> <compound datum> --> <list> | <vector> <list> --> (<datum>*) | (<datum>+ . <datum>) | <abbreviation> <abbreviation> --> <abbrev prefix> <datum> <abbrev prefix> --> ' | ` | , | ,@ <vector> --> #(<datum>*)   <expression> --> <variable> | <literal> | <procedure call> | <lambda expression> | <conditional> | <assignment> | <derived expression> | <macro use> | <macro block>   <literal> --> <quotation> | <self-evaluating> <self-evaluating> --> <boolean> | <number> | <character> | <string> <quotation> --> '<datum> | (quote <datum>) <procedure call> --> (<operator> <operand>*) <operator> --> <expression> <operand> --> <expression>   <lambda expression> --> (lambda <formals> <body>) <formals> --> (<variable>*) | <variable> | (<variable>+ . <variable>) <body> --> <definition>* <sequence> <sequence> --> <command>* <expression> <command> --> <expression>   <conditional> --> (if <test> <consequent> <alternate>) <test> --> <expression> <consequent> --> <expression> <alternate> --> <expression> | <empty>   <assignment> --> (set! <variable> <expression>)   <derived expression> --> <cond> | <case> | <boolfunc> | <let> | <begin> | <loop> <cond> --> (cond <cond clause>+) | (cond <cond clause>* (else <sequence>)) <case> --> (case <expression> <case clause>+) | (case <expression> <case clause>* (else <sequence>)) <boolfunc> --> <and> | <or> <and> --> (and <test>*) <or> --> (or <test>*) <let> --> (let (<binding spec>*) <body>) | (let <variable> (<binding spec>*) <body>) | (let* (<binding spec>*) <body>) | (letrec (<binding spec>*) <body>) <begin> --> (begin <sequence>) <loop> --> (do (<iteration spec>*) (<test> <do result>) <command>*)   <cond clause> --> (<test> <sequence>) | (<test>) | (<test> => <recipient>) <recipient> --> <expression> <case clause> --> ((<datum>*) <sequence>) <binding spec> --> (<variable> <expression>) <iteration spec> --> (<variable> <init> <step>) | (<variable> <init>) <init> --> <expression> <step> --> <expression> <do result> --> <sequence> | <empty>   /** Programs and definitions **/   <program> --> <command or definition>* <command or definition> --> <command> | <definition> | (begin <command or definition>+) <definition> --> (define <variable> <expression>) | (define (<variable> <def formals>) <body>) | (begin <definition>*) <def formals> --> <variable>* | <variable>* . <variable>        

REFERENCES

Back, T. (1996). Evolutionary Algorithms in Theory and Practice. New

York, Oxford University Press.

Koza, J. R. (1993). Genetic Programming. Cambridge, MA. MIT

Press/Bradford Books.

Purtilo, J. J. & Callahan, J. R. (1989). Parse-tree annotations.

Communications of the ACM. 32(12) 1467-77.