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.
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)
(while condition body)These two structures can be generalized into one as while loop is just a special case of for loop :
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
(loop initialize condition update 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.
with the following meaning :
initialize
while condition > 0 do
body
update
return the result from body
(recur arg0 condition update body)
with the following meaning :
if condition ( arg0 ) > 1 then do
body ( arg0 )
update ( arg0 )
(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.