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 PROGRAM1)) with (get PROGRAM2)) We will break down this command into sections. Note the piece that says (get 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 is based on the scheme BNF. So when we do (choose 1 of (get 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 ) 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 PROGRAM1)) gets clobbered by what gets returned by the expression following the with keyword, which in example 2 is (get 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 PROGRAM1)) with (get 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 PROGRAM1)) with (get 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 PROGRAM1)) with (get 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 PROGRAM1)) with (get 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 )) 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 pool. (generate 1 ) 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 : --> " * " 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 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 ) foo) (add .4 (generate 1 ) 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 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 PROGRAM1)) (define bar '()) (add .1 (generate 1 ) bar) (add .2 (choose 1 of (get PROGRAM1)) bar) (add .3 clo bar) (replace! (choose 1 of (get 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 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 ************************************************** - how well did we achieve original goals 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 ) foo) (choose 1 of (50 (begin (crossover! (PROGRAM1) (PROGRAM2)) (crossover! (PROGRAM1) (PROGRAM2)) (crossover! (PROGRAM1) (PROGRAM2)))) (150 (begin (replace (choose 1 of (get PROGRAM1)) with (get 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 is extended to include one additional rule: --> | | | | | | | | | When nonterminals occur more than once in the same rule, they are assumed to map to potentially different code (ie, won't necessarily be the same number when it appears repeatedly in the same rule). --> --> --> /* here the outer "<" and ">" are literals */ --> <> --> --> --> --> | pool | function --> | (add [] ) | (add [] function ) | (add [] pool ) | (combine +) | (crossover! ( [:]) ( [:])) | (generate [to depth ]) | (choose of ) | (choose of ([] )*) | (node [internal leaf ] ) | (node [ ]+ ) | (load bnf ) | (populate from ) | (get ) | (replace! with ) | (replace! using ) | (replace! with ) semantics: -------------------- Any nonterminal in the scheme BNF (see scheme BNF). -------------------- Refers to a tilt datatype (essentially, it's a scheme pointer) -------------------- Refers to a tilt closure which can be run. This must return a valid scheme (*note* scheme, not tilt) -------------------- Refers to a tilt datatype which contains , pairs. '() is considered to be an empty pool. is the probability that a given 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. is either a scheme , another pool, or a tilt function. Every data structure keeps track of where values of type 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 ) 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! ( [:]) ( [:])) 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 permanently. -------------------- (generate [to depth ]) uses other nonterminal's pools and the BNF to randomly generate values for the pool (all of type function, since they have no s, as in add). In the case of recursive rules, it will max out a depth 10, or if to depth is specified. This will copy s from other pools if possible. It returns the generated pool, or if is 1, the generated (a scheme ). Upon error, it returns nil. -------------------- (choose of ) will pick values from the , with either equal probability, or the probability specified by the elements of the . Probabilities in the pool are automatically normalized to values between 0 and 1 by choose. choose returns a of the chosen s, with no probabilities assigned, or a 's if is 1. If the has no node, the itself is returned. If a chosen is a function the result of calling is used as a (of type ). If a is a pool , the result of calling (choose 1 of ) is used. It returns nil if there is an error. (choose of ([] )*) will run of the s, chosen randomly or according to the specified s as described above. -------------------- (node [internal leaf ] ) (node [ ]+ ) returns a (pointer into) the expression chosen either randomly, or with probability according to whether it's internal, a leaf, or matches the given set of as specified. It returns an error if there is an error. -------------------- (populate from ) 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 ) returns a of all the occurrences of in . Each time get is called, it automatically add anything new if finds to the pool associated with (see load bnf) -------------------- (replace! with ) (replace! with ) The pointer is changed to point at the result of a copy of the value associated with (choose 1 ) or . This returns nil on error, #t otherwise. (replace! using ) Replace will choose a (and associated ) from the pool, and then it will look up the nonterminals in the rule for (e.g. and for ). If the pointed at by has any such nonterminals, they will be used in order, until they are used up, to replace the corresponding terminals in the chosen . The result will be copied into the pointed at by . e.g. (replace! (or #t 1 2) using ) The pool contains (and (foo) bar) <- randomly chosen (or (baz) quux) since we have (and *) as our rule, and #t is a , we get (and #t 1). -------------------- (add [] ) adds and it's associated to with probability if specified. (add [] function ) (add [] pool ) adds the appropriate function or pool to with probability if specified. (add [] ) calls (add function (lambda () ) ) with probability if specified. -------------------- (combine +) basically appends two 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. stands for the empty string. The following extensions to BNF are used to make the description more concise: * means zero or more occurrences of ; and + means at least one . 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 , but not necessarily by anything else. **/ --> | | | | | ( | ) | #( | ' | ` | , | ,@ | . --> | ( | ) | " | ; --> --> ; --> | --> * --> * | --> | --> a | b | c | ... | z --> ! | $ | % | & | * | / | : | < | = | > | ? | ^ | _ | ~ --> | | --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 --> + | - | . | @ --> + | - | ... --> | else | => | define --> quote | lambda | if | set! | begin | cond | and | or | case | let | let* | letrec | do --> #t | #f --> #\ | #\ --> space | newline --> " * " --> | \" | \\ --> --> | @ | + i | - i | + i | - i | + i | - i | + i | - i --> --> | / | --> | . + #* | + . * #* | + #+ . #* --> + #* --> | --> | + --> e | s | f | d | l --> | + | - --> | #i | #e --> | #d /** is what the read procedure (section see section Input) successfully parses. Note that any string that parses as an will also parse as a . **/ --> | --> | | | | --> --> | --> (*) | (+ . ) | --> --> ' | ` | , | ,@ --> #(*) --> | | | | | | | | --> | --> | | | --> ' | (quote ) --> ( *) --> --> --> (lambda ) --> (*) | | (+ . ) --> * --> * --> --> (if ) --> --> --> | --> (set! ) --> | | | | | --> (cond +) | (cond * (else )) --> (case +) | (case * (else )) --> | --> (and *) --> (or *) --> (let (*) ) | (let (*) ) | (let* (*) ) | (letrec (*) ) --> (begin ) --> (do (*) ( ) *) --> ( ) | () | ( => ) --> --> ((*) ) --> ( ) --> ( ) | ( ) --> --> --> | /** Programs and definitions **/ --> * --> | | (begin +) --> (define ) | (define ( ) ) | (begin *) --> * | * . 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.