Function Set

The simple GP programs in the previous examples use only 'simple' function set.  That is the function set contains only branching {if-and, if-or, if-not} or mathematical function { +, - , * , / , sin, cos, exp . . . }.  This lecture will introduce more advanced function set that involve control flow of program and data structure.

A simple GP contains only branching and sequencing function for control flow.  In an ordinary programming language there are other methods to perform control flow : iteration and recursion.  And to cope with a large program, the 'reuse' of code is important.  User defined function allows code to be reused.  Therefore function call is the main mechanism in any programming language.

User defined function

A subroutine can be evolved concurrently with the main program.  This structure is called 'automatic defined function' (ADF) by Koza.  There are many concerns in using this structure.  First, the number of subroutine, the maximum number of subroutine must be specified in advance before starting the evolutionary process.  Second, the number of the argument in a subroutine.  Finally, how parents with different number of subroutine and different number of argument be recombined (crossover) ?

In the following explanation, we will use ( function arg arg ... ) to denote  tree structures.

A program with subroutine has the top level structure
( main sub1 sub2 . . . subn )

The main program has terminal symbols { sub1, sub2, . . . } to call subroutines.  There is a  restriction to avoid infinite loop, that is, the subroutine can not call subroutines.  If subroutines can freely call subroutines, the problem of recursion, mutual recursion and infinite loop can occur.  The crossover operation will be permitted only the similar type of structure, i.e, main with main, sub1 with sub1 etc.   Subroutines with the same name but with different number of arguments will be considered as different type, for example, sub1 with 2 arguments (sub1/2) is not the same as sub1 with 3 arguments (sub1/3).  There are many possibilities of mixing programs with different number of subroutines. For example, see the reference (Jassadapakorn, C. and Chongstitvatana, P., 1998)

Reference
Jassadapakorn, C. and Chongstitvatana, P., "Reduction of Computational Effort in Genetic Programming by Subroutines", Proc. of National Computer Science and Engineering Conference, NCSEC98, Bangkok, Thailand, 1998.  (pdf) (html)

Iteration and Recursion

While loop and For loop can be implemented.
(while condition body)
the operational meaning of while loop is as follow :
while  condition > 0  do body

(for initialize terminate increment body)
the meaning is as follow :
initialize
while terminate < 1 do
  body
  increment

These two structures can be generalized into one as while loop is just a special case of for loop :
(loop initialize condition update body)
with the following meaning :
initialize
while condition >  0 do
  body
  update
return the result from body
One need to be aware that For loop usually works with index variables (array).  Therefore the index in the initialize, terminate, increment and body must be arranged to be corresponded to each other.  Recursion can be implemented in a similar fashion.
(recur arg0 condition update body)
with the following meaning :
if condition ( arg0 ) > 1 then do
  body ( arg0 )
  update ( arg0 )

Data Structure

Any scalar value can be stored and retrieved by defining a variable.

(setMx  value)   store value to the variable number x
Mx                            retrieve value from the variable number x

where x is the number 0.. n

A vector can also be defined.

(setVx index value)  store value to the array Vx[index]
(getVx index)              retrieve value from the array Vx[index]

Some simple data structure can also be used such as stack which the operations : push and pop.  Some operation can also be defined to operate iteratively on the vector such as sum_array, (sum_array v0) where v0 is a vector of length n.  This is easier than using the iteration structure.  Evolving data structure is an interesting topic, see the work of Langdon.  His work shows how to evolve List, Queue, Stack from primitive operations.

Reference
Langdon, Genetic algorithm + data structure = automatic program, ? , 1999.