# Evolutionary Programming

**URL:** <https://discourse.julialang.org/t/evolutionary-programming/42822>\
**Category:** New to Julia\
**Tags:** first-steps\
**Created:** [July 10, 2020, 5:03am UTC](https://discourse.julialang.org/t/evolutionary-programming/42822 "2020-07-10T05:03:58Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![colinclout12](https://avatars.discourse-cdn.com/v4/letter/c/dfb087/32.png) [@colinclout12](https://discourse.julialang.org/u/colinclout12)\
**Post date:** [July 10, 2020, 5:03am UTC](https://discourse.julialang.org/t/evolutionary-programming/42822/1 "2020-07-10T05:03:58Z")

</div>

I’m trying to work through Dan Simon’s _Evolutionary Optimization Algorithms: Biologically-Inspired and Population-Based Approaches to Computer Intelligence_, and would like, to figure out how to turn his sample Genetic Programming lisp code into Julia code. (His code is [here](https://academic.csuohio.edu/simond/EvolutionaryOptimization/), though I can’t find the id to link directly to chapter 7.)

The [manual](https://docs.julialang.org/en/v1/manual/metaprogramming/) says that it’s possible to write “true Lisp-style macros operating at the level of abstract syntax trees”. But I’m having trouble finding any information on how to do so, and I keep getting errors. I may be able to reinvent the wheel after lots of trial and error, but I’d be very interested in resources.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [July 10, 2020, 8:52am UTC](https://discourse.julialang.org/t/evolutionary-programming/42822/2 "2020-07-10T08:52:19Z")

</div>

The chapter you link is one of the best starting points. If you have specific questions, just ask them on this forum, which you should also search for “macro” to find a lot of discussions about macros.

That said, metaprogramming is not needed in Julia as frequently as in CL. See eg

> [@How to warn new users away from metaprogramming](https://discourse.julialang.org/t/how-to-warn-new-users-away-from-metaprogramming/35022):
>
> [Metaprogramming](https://docs.julialang.org/en/v1/manual/metaprogramming/) is a great feature of Julia, allowing advanced users to introduce syntactic extensions with macros, and work around code optimization problems using generated functions. However, it is somewhat of an advanced technique with particular pitfalls, and in practice it is needed much less frequently than some new users of Julia realize, possibly because the basic building blocks of Julia are so powerful. From some discussions on this forum, it appears metaprogramming is considered as …

In particular, try higher order functions first.

---

<div class="post-metadata">

**Author:** ![colinclout12](https://avatars.discourse-cdn.com/v4/letter/c/dfb087/32.png) [@colinclout12](https://discourse.julialang.org/u/colinclout12)\
**Post date:** [July 10, 2020, 4:20pm UTC](https://discourse.julialang.org/t/evolutionary-programming/42822/3 "2020-07-10T16:20:34Z")

</div>

Thanks for the response.

Metaprogramming is important here, because the point of Genetic Programming is to run the following program:

```julia
Randomly generate n parent programs, parents, that attempt to perform some task.
While ! termination condition.
   for prog in parents
      Measure f_{prog}.
   end
Randomly select n/2 duples parents, pairs. #More fit programs more likely to be selected.
children = {code}[] #Empty vector (or tuple or...) of code.
for pair in pairs
   select nodes in syntax tree of pair[1] par[2]
   child1 child2 = parents with subtrees swapped at those nodes
   push!(children,child1)
   push!(children,child2)
end
parents = children
end

```

(This is my attempt at producing the pseudocode.)

The goal is to evolve optimal code for some task. Because this algorithm operates on the abstract syntax tree, metaprogramming is necessary here. (Though perhaps I should take the warning to heart and say this is too advanced me.)

In Lisp, it looks like algorithm is executed by operating on the strings, and I’ve played around with that in Julia, but it doesn’t work well, and the link makes sounds like its a bad practice. I’ve also tried playing around with building expressions with :(). But when I try to randomize the operation (from a list of, say, arithmetic operations) and the leaves, I run into problems related to how Julia parses literals, that I don’t understand well. I could ask about them, but I also suspect (though I don’t know) that this also isn’t best practice.

I _think_ best practice would be to operate on the syntax tree itself with commands like:

```julia
code = :(+(2,3))
operators = [:+, :-, :*]
code.args[1] = rand(operators)
eval(code)

```

which randomly adds, subtracts, or multiplies 2 and 3. But I run into troubles doing much more.

For instance, if I wanted say, to iteratively create a vector, I could use:

```julia
v = Vector{Float64}()
for condition
   arg = foo
   push!(v,arg)
end

```

But I don’t know how to do something similar with code.

Similarly, with a DataFrame df, I can iterate through the columns with:

```julia
for name in Symbol.(names(df))

```

(Or something similar, I may have that a little off. That’s code’s similar to what Adrian Salceanu put in [Julia Programming Projects](https://www.packtpub.com/big-data-and-business-intelligence/julia-programming-projects), but I may have missed some nuances here.)

But I don’t know how to do anything like that here.

There still may not be a specific question there. What I’d like is examples of best practices for operating on, iterating through, and getting information about abstract syntax trees.

---

<div class="post-metadata">

**Author:** ![datnamer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datnamer/32/3471_2.png) [@datnamer](https://discourse.julialang.org/u/datnamer)\
**Post date:** [July 10, 2020, 4:44pm UTC](https://discourse.julialang.org/t/evolutionary-programming/42822/4 "2020-07-10T16:44:51Z")

</div>

Check out [Why use MLStyle.jl? — MLStyle.jl Documentation](https://thautwarm.github.io/MLStyle.jl/latest/why.html#intuition-of-ast-manipulations) and

macrotools.jl

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [July 10, 2020, 6:15pm UTC](https://discourse.julialang.org/t/evolutionary-programming/42822/5 "2020-07-10T18:15:26Z")

</div>

> [@colinclout12](#):
>
> I _think_ best practice would be to operate on the syntax tree itself with commands like:
> 
> ```julia
> code = :(+(2,3))
> operators = [:+, :-, :*]
> code.args[1] = rand(operators)
> eval(code)
> 
> ```
> 
> which randomly adds, subtracts, or multiplies 2 and 3. But I run into troubles doing much more.

I think that metaprogramming and ASTs are are distraction here. Cf

```julia
execute(f, args) = f(args...)
args = (2, 3)
f = rand((+, -, /))
execute(f, args)

```

Just operate on functions and values, and use a functional style. Depending on the space your genetic algorithm operates on, you could use a tree-like stucture or similar. Also, coding this to be type stable requires some tricks, but those can wait until the code stabilizes (and performance will never be worse than `eval` anyway).

FWIW, the same techniques apply in most Lisps, very little is Julia specific here. A modern Lisp approach could just use closures instead of AST construction, benefiting from modern Lisp compiler optimizations.

I am very surprised that some texts recommend AST manipulation. That is similar to using namespaces as a hash table: acceptable for texts from the 1980s, but not something a contemporary Lisp programmer would do.

---

<div class="post-metadata">

**Author:** ![colinclout12](https://avatars.discourse-cdn.com/v4/letter/c/dfb087/32.png) [@colinclout12](https://discourse.julialang.org/u/colinclout12)\
**Post date:** [July 10, 2020, 9:28pm UTC](https://discourse.julialang.org/t/evolutionary-programming/42822/6 "2020-07-10T21:28:39Z")

</div>

Thanks! That’s helpful.

FWIW, [this](http://courses.csail.mit.edu/18.337/2015/projects/MorganFrank/projectReport.pdf) (I think it’s a grad school course project at MIT) implemented GP in Julia by operating on the AST’s. And, [this](https://youtu.be/HWMJdO4klIE?t=536) talk from ClojureConj 2015 gives the same explanation for GP in Lisp as Simon does (and also around 13:30 he explicitly works on subtrees).

I think AST is important for re-combinations and mutations, not for the generation of the initial programs. That is, for programs to evolve, they need to produce children that are like the parents, but with “lines of code” (or something comparable) swapped. (Also, the functions not only need to be generated and evaluated, they need to be stored somewhere so they can be used to produce child functions. The ‘‘execute’’ function above returns a number, not a program, so the program the snippet produces can’t be used to produce a child program.) So, for instance, we’d like to be able to do something like the following example (from Simon), using Matlab code to the two parent programs, Program 1 and Program 2:

```julia
#Program 1
if x<1
    z = [1,2,3,4,5];
else
   for i = 1:5
      z(i) = i/x;
   end
end

```

and

```julia
#Program 2
for i = 1:10
   if x > 5
      z(i) = x^i;
   else
      z(i) = x/i;
   end
end

```

```julia
#Child program
for i = 1:10
   if x > 5
else
   for i = 1:5
      z(i) = i/x;
   end
end

```

Where lines 1 and 2 of the child program come from parent 2, and the rest of the lines come from parent 1. Obviously, this cannot work as the child program is garbled nonsense.

But, he says, because s-expressions in lisp correspond to nodes in the AST, we _can_ perform that sort of operation in lisp. For instance (his example), given parent 1 and parent 2 as follows:

```julia
#parent 1
(+ (* x y) abs z)

```

```julia
#parent 2
(- (* (+ x z) x) (+ z (/ y x)))

```

we can swap the s-expression (\*x y) from parent 1 with the s-expression (+ z (/ y x)) from parent 2 to get two children:

```julia
#child 1
(+ (+ z (/ y x)) abs z) # parent 1, but (+ z (/ y x)) where (* x y) had been.

```

```julia
#child 2
(- (* (+ x z) x) (* x y)) #parent 2, but with (* x y) where (+ z (/ y x)) had been.

```

This swap can (he says) be performed in lisp by finding an opening parenthesis and a matching closing parenthesis in each parent program, and swapping everything between them in the two programs. As I said, the Conjure Conj talk I linked above gives a similar example.

So though your the functional example is very helpful (especially since one of my goals in looking into this is understanding Julia better), I don’t think it can get me all the way there.

Anyway, I wanted to look into this so I could understand how Julia works better, and even if I don’t find answers to all the questions, I understand Julia a lot better.

---

<div class="post-metadata">

**Author:** ![colinclout12](https://avatars.discourse-cdn.com/v4/letter/c/dfb087/32.png) [@colinclout12](https://discourse.julialang.org/u/colinclout12)\
**Post date:** [July 10, 2020, 10:13pm UTC](https://discourse.julialang.org/t/evolutionary-programming/42822/7 "2020-07-10T22:13:32Z")

</div>

Anyway, I think I confused things by putting eval() in my program above. I really am interested in generating a code that can be stored and operated on (by mixing it with other code), not in a convoluted method for generating a function with a random operator—though that’s not what I made it sound like last night.

I think eval() was left over from my sandboxing with code in julia, and my attempts to make sure I understood what was happening. That is, I was using it as a check so I could make sure I get the code I thought I got, and wasn’t just misreading the generated code (which, when I do things wrong can look right, but not be).

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [July 11, 2020, 3:55am UTC](https://discourse.julialang.org/t/evolutionary-programming/42822/8 "2020-07-11T03:55:18Z")

</div>

You can try this tutorial:

[![](https://global.discourse-cdn.com/julialang/original/3X/0/c/0c5d4206e7cb0edfebc8811c184de003bc218dbc.jpeg "JuliaCon 2016 | Intermediate Level Julia (Workshop) | David Sanders") ](https://www.youtube.com/watch?v=rAxzR7lMGDM)

and notebooks here:

> **[GitHub - dpsanders/intermediate\_julia](https://github.com/dpsanders/intermediate_julia)**
>
> Contribute to dpsanders/intermediate\_julia development by creating an account on GitHub.

Some of the syntax is a bit old, but I think most of the metaprogramming stuff should still be OK.  
And the ideas of course are all the same.

A more up-to-date version of the notebooks is here:

> **[GitHub - dpsanders/intermediate\_julia\_2019](https://github.com/dpsanders/intermediate_julia_2019)**
>
> Contribute to dpsanders/intermediate\_julia\_2019 development by creating an account on GitHub.

Hope that helps!

---

<div class="post-metadata">

**Author:** ![colinclout12](https://avatars.discourse-cdn.com/v4/letter/c/dfb087/32.png) [@colinclout12](https://discourse.julialang.org/u/colinclout12)\
**Post date:** [July 11, 2020, 11:40pm UTC](https://discourse.julialang.org/t/evolutionary-programming/42822/9 "2020-07-11T23:40:30Z")

</div>

This is exactly what I was looking for. Thank you!

---

<div class="post-metadata">

**Author:** ![lwabeke](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lwabeke/32/4005_2.png) [@lwabeke](https://discourse.julialang.org/u/lwabeke)\
**Post date:** [July 13, 2020, 12:50pm UTC](https://discourse.julialang.org/t/evolutionary-programming/42822/10 "2020-07-13T12:50:25Z")

</div>

> [@colinclout12](#):
>
> Obviously, this cannot work as the child program is garbled nonsense.

I suspect that is the main concern: Just randomly mucking around with the full blown power of syntax trees are very likely to generate “garbage” that doesn’t run, for example getting into infinite loops, etc. Nevermind the learning curve to understand how to use the syntax.

When I played with Evolutionary Programming almost 20 years ago it was in the context of evolving a formula. It was simply done in C, by defining a tree: Leave nodes are literals or variables, branch nodes are binary operators, for example \*, +, -, , with links to a left node and a right node. Unary operators like sqrt, exp, etc. are also easy as non-splitting branch nodes. You can easily perform cross-over by taking a node and the sub-tree below it and swapping it with a node in a different parent.  
Extending it to the ternary operator ?: (which is actually just an alias for if syntax) should also not be too difficult.

Adding for loop should again be possible, but you probably then also need to think about storing variables etc.

While it might sound like it quickly converges to the full AST, I would still argue it is better to add it manually to force thinking through what you want to allow and what not. For example:

- May the program loop and go into an infinite loop?
- May it allocate new variables? If so how much, what happens if it allocates too much and crashes your whole Julia session, etc.