# Expr trees and genetic programming

**URL:** <https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488>\
**Category:** General Usage\
**Tags:** question\
**Created:** [October 4, 2019, 3:21pm UTC](https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488 "2019-10-04T15:21:21Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Gus\_Hart](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gus_hart/32/6987_2.png) [@Gus\_Hart](https://discourse.julialang.org/u/Gus_Hart)\
**Post date:** [October 4, 2019, 3:21pm UTC](https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488/1 "2019-10-04T15:21:21Z")

</div>

I’ve been experimenting with metaprogramming in Julia. I’d like to make a simple program to experiment around with a toy model for genetic programming. I’d like to be able to “splice” `Expr` trees but the fact that they are nested makes things a little bit more complicated. I was hoping I could just treat them like a simple tree (where the number of nodes and leaves would be easy to query). But I can’t seem to avoid just traversing the whole tree to know how many nodes and leaves it has.

Could anyone offer some helpful hints or insights? Or point me to examples that would be relevant?

Many thanks,  
-Gus

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [October 4, 2019, 3:27pm UTC](https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488/2 "2019-10-04T15:27:43Z")

</div>

Hi, I happen to have created a package to meet a similar need of mine called [SyntaxTree.jl](https://github.com/chakravala/SyntaxTree.jl) for counting.

```nohighlight
julia> using SyntaxTree

julia> SyntaxTree.callcount(:(x^2+y^2))
3

```

It also has function to recursively compute other statistics, such as the average exponent and the average of the non-exponential numerical coefficients in an algebraic expression tree.

```nohighlight
@noinline function callcount(expr)
    c = 0
    if typeof(expr) == Expr
        expr.head == :call && (c += 1)
        c += sum(callcount.(expr.args))
    end
    return c
end

```

There are a bunch of different functions in the package, and more could be added, since there are various ways to count and measure different attributes of the syntax tree.

The purpose of the `SyntaxTree` package is to collect these type of methods in one place.

---

<div class="post-metadata">

**Author:** ![Gus\_Hart](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gus_hart/32/6987_2.png) [@Gus\_Hart](https://discourse.julialang.org/u/Gus_Hart)\
**Post date:** [October 4, 2019, 3:38pm UTC](https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488/3 "2019-10-04T15:38:37Z")

</div>

That’s great. Thanks or the quick response. Does your package provide a way to splice `Expr` trees? Say grab all of the subtree below a certain node and replace it with a different subtree?

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [October 4, 2019, 3:41pm UTC](https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488/4 "2019-10-04T15:41:05Z")

</div>

For expression tree rewriting I made a package called [Reduce.jl](https://github.com/chakravala/Reduce.jl) which does symbolic algebra. There are also various other term rewriting packages out there.

What exactly are you trying to splice? Is it an algebraic expression?

---

<div class="post-metadata">

**Author:** ![Gus\_Hart](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gus_hart/32/6987_2.png) [@Gus\_Hart](https://discourse.julialang.org/u/Gus_Hart)\
**Post date:** [October 4, 2019, 3:47pm UTC](https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488/5 "2019-10-04T15:47:05Z")

</div>

Yes, I’d like to make arbitrary algebraic expressions and then cut and splice them together.  
 ![image](https://global.discourse-cdn.com/julialang/original/3X/9/9/99cee16ecb2cd93b7c2edc38991f5db3c6f312e4.png)

---

<div class="post-metadata">

**Author:** ![dfdx](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dfdx/32/120_2.png) [@dfdx](https://discourse.julialang.org/u/dfdx)\
**Post date:** [October 4, 2019, 4:05pm UTC](https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488/6 "2019-10-04T16:05:21Z")

</div>

Espresso.jl contains [a number of functions](https://github.com/dfdx/Espresso.jl/blob/master/src/rewrite.jl) for finding, matching and substituting subexpressions. Here’s one way to implement what you’ve described (if I got it right):

```julia
using Espresso

ex1 = :((2 + 3) - x)
# ==> :((2 + 3) - x)

ex2 = :(y + 7)
# ==> :(y + 7)

plus_ex = findex(:(_a + _b), ex1)[1]
# ==> :(2 + 3)

# option 1: substitute :y in ex2 with plus_ex
subs(ex2, Dict(:y => plus_ex))
# ==> :((2 + 3) + 7)

# option 2: rewrite all subexpressions according 
# to pattern (which is still simply :y)
rewrite_all(ex2, :y, plus_ex)
# ==> :((2 + 3) + 7)

```

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [October 4, 2019, 4:46pm UTC](https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488/7 "2019-10-04T16:46:24Z")

</div>

@dfdx Just so you know, I do a lot of googling for things like “julia pattern matching” and Espresso.jl never showed up. I had heard of it in the distant past, but completely forgot it had term rewriting and pattern matching utilities. I think you should probably put some tags on it and also write a blurb about what it’s for in the readme to aid discoverability. This seems like a really useful package for my purposes!

---

<div class="post-metadata">

**Author:** ![dfdx](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dfdx/32/120_2.png) [@dfdx](https://discourse.julialang.org/u/dfdx)\
**Post date:** [October 4, 2019, 10:58pm UTC](https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488/8 "2019-10-04T22:58:03Z")

</div>

That’s a great suggestion, thanks! I’ve added tags and more meaningful README.

---

<div class="post-metadata">

**Author:** ![xgdgsc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xgdgsc/32/608_2.png) [@xgdgsc](https://discourse.julialang.org/u/xgdgsc)\
**Post date:** [October 5, 2019, 2:54am UTC](https://discourse.julialang.org/t/expr-trees-and-genetic-programming/29488/9 "2019-10-05T02:54:33Z")

</div>

I’ ve used [https://github.com/sisl/ExprRules.jl](https://github.com/sisl/ExprRules.jl) and [https://github.com/sisl/ExprOptimization.jl](https://github.com/sisl/ExprOptimization.jl) to do genetic optimizations. They may contain what you need.