Expr trees and genetic programming

General Usage
1

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

2

Hi, I happen to have created a package to meet a similar need of mine called SyntaxTree.jl for counting.

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.

@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.

1 Like
3

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?

4

For expression tree rewriting I made a package called 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?

5

Yes, I’d like to make arbitrary algebraic expressions and then cut and splice them together.
image

6

Espresso.jl contains a number of functions for finding, matching and substituting subexpressions. Here’s one way to implement what you’ve described (if I got it right):

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)
5 Likes
7

@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!

3 Likes
8

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

3 Likes
9

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

3 Likes