>> Hello. Welcome back, everyone. We have Simon Carryer, who's going to talk to us about syntax
trees. I love syntax trees. I really do. Simon Carryer is a data analyst in New Zealand. He works
on other peoples' dumb ideas. This is his wording. And his on dumb ideas on the weekend. Welcome,
Simon. So great to have you. So great to have you. SIMON CARRYER: Hi, thank you very much. This talk
will provide almost no education content around ASTs. Please do not take this as
informative at all. This is purely stupid ideas in this talk. So, some context,
I have kind of a brain problem, which is that if I have a dumb idea, I have to make it real.
I can't think about anything else until it's done and that has led to
several terrible things being created. I made a website, which forces people to choose which
kind of milk they'd rather drink between two different mammals and then creates a ranking
of those so people like lama milk, but not rat milk, for example.
I made a thing, which took my own, horrible drawings and turned them into Bob Ross paintings.
So that's the kind of thing that I like doing. But, this idea, that I'm going to talk to you
about now, is probably the stupidest idea I've ever had. For you to understand why that idea
was so stupid, you'd probably need a little bit of context. In particular, what is an AST? Well, it's
an Abstract Syntax Tree. I learned about those, in this talk, called Fantastic ASTs and Where to Find
Them. You should check out that talk, which is far more educational than this one is going to be.
Imagine you've got a little bit of Python code, like this, super simple, adding
a couple of variables together. If you pass that to Python's AST library and call it
"pass method init string," it'll return a binary option and on the left hand, it's taking "A" and
a thing called "B" and it's adding them together. Why is that a good thing to do? Why would you want
to do that and what can you do with these things? Well, for a lot of smart reasons, but the key
thing to understand about it is that it is making a tree representation of your code.
Right. It's turning into each of the objects that are being acted on by the code,
into a sort of node and then representing their relationship to each other like a tree.
And that lets you traverse that tree and kind of understand what the code does without
having to execute the code itself. And you can chain those things together to make
really big, complex bits of code. So, here we're taking A and B, adding them together, comparing it
and passing that into a "if" to boolean. If A+B is greater than 10, XY might be what this tree does.
Why is that good? So, it tells you what your code does without having to execute it. And people use
it for all kinds of smart stuff. Automatic testing, transpiling. Any time, in your IDE,
when you're, like, writing code and it underlines it in red and says, "oh, you made a mistake here,"
it's probably using a AST for that. That's not what I'm using it for in this talk.
I guess the main thing that you should take from this is that it represents the
what your code does in a kind of tree like format.
The other thing that you need to understand, for context in this talk, is genetic programming.
So, that's also really complicated. I'm not going to go into it in too much detail. I learned most
of what I know about genetic programming from this library, JP Learn, from Trevor Stevens.
You should check out that library if you're not already familiar with it. It's very clever.
Basically, the idea of genetic programming is you've got a problem you want to solve. You write
something that can measure how well a particular solution has solved that problem and you generate
random solutions to the problem and then randomly re combine those solutions of multiple
generations, keeping the fittest solutions in each generation and eventually come up with a
fittest possible solution that solves your problem.
And I guess the the key thing, to take from this, is that the way one of the things that genetic
programming does is it represents those solutions as a kind of tree structure. Right. So, it using
these it usually uses mathematical operations and then it takes two solutions
and mangles them together by taking a bit of each of them and recombining them to a new solution.
So that gives you the genesis of my stupid idea. Given that you can represent code
as a as a tree from an Abstract Syntax Tree, and given that you can and genetic programming,
they've shown you can make new solutions by mangling together these tree structures. Can you
write new code, in Python, by mangling the ASTs together and get something that produces some
kind of output? Can you make a function that is the combination of two other functions that does
something a bit like the both of them? I wanted to play around with that idea.
And to do that, I wanted to I needed to have something that could write functions,
where I could see the output of them and see if the output of these two different functions
of the new function was similar to these two source functions and so I guess taking an idea for
Mendelian genetics, which started with flowers, I thought it would be cool to write functions
that draw flowers so the first thing I did was write kind of a harness,
or code that would help me write functions that would draw flowers.
What I wanted to do was have really simple flowers that could be generated
by minimal functions. Because I knew I would be writing really terrible code,
I needed it to handle bad outputs and have something kind of legible.
So, 90s kids will understand, if you did any kind of computer programming in school in the 90s, you
probably played around with Logo. There's a little turtle and you tell him to move around and turn
and whatever he does, he leaves a little trail behind him and you can make drawings
out of it. Well, Python contains Logo. There's a library the core library of
in Python, called "turtle," is Logo. It is a nice, simple drawing library. So that was the
basis of my drawing library that I wrote. What I did was it starts with a state,
an x and a y position and a iteration number, which will become important later. And then I
could pass to that some really simple functions. So, here's a function I wrote for drawing a daisy.
It takes just an iteration number and it produces an output based on that iteration number.
So, that function returns some outputs which are interpreted as instructions to my
drawing library. Or it could produce one set of instructions or multiple sets of instructions.
I passed that to a couple of regulator functions that would make sure that those instructions
produced by the function were actually able to be interpreted as drawing instructions
and then make a turtle. And I tell that turtle to draw, based on the instructions. So, for example,
the instructions might say, "turn let and go forward." And it would do that and draw a
little bit of a flower and then it would return a new state and increase the iteration one step
and then get passed to that that state would get passed to the function again. So I made this real,
simple, little framework for drawing flowers and that meant I could write a handful of really,
simple functions that would draw different flowers, like this. So, I made a little daisy
and a cyclamen and a fox glove and a tree. And each of those are generated
by a function that's only, you know, a handful of lines long.
And then I wanted to mangle those together. So, I wanted to achieve was, could I get
two of those functions, the daisy function and the tree function,
mangle their ASTs together and produce a new function that drew a flower that looked
a bit like a tree and a bit like a daisy? So, I needed to take a function, using
Inspect, I could get the source string of that function and then pass that and I'd get an AST,
so I did that to two functions and then kind of jumble them together and make a combined AST.
And there's a cool thing that's I think they only introduced it in Python 3.9,
which means you can unpass an AST as well, which means it will show you the code
that it shows you code that would generate an AST that matches the AST you've unpassed.
And that was enormously helpful in doing this. Anyway, so, when I was mangling them together,
I used a few ideas from genetic programming. The main one being cross pollination.
What that looks like is this, you start with a source you start with an AST. And then you
select a donor AST. So, in this, we've got the AST we looked at before and another AST.
You select a donor, from the donor, you select a subtree and a target location
in the in the original AST, and then you kind of graft on that bit of the AST
to the, um, to the subject. And that gives you a new function.
There are a couple of other things that I tried, as well, mutation, which is just
changing one node, like incrementing a number up or down and a greater than to a less than
and pruning, which is snipping bits off the tree.
So, from from that new, combined AST, you can compile it back into compiled code
and then execute that, which creates a function back in your namespace. So then you've got
a new function, which is whatever that AST tells it to do.
And that kind of works. If you take the tree function and the daisy function
and then mangle them together, you kind of get something that sometimes looks like a combination
of the two of them. This was enormously exciting to me when I first achieved this, but it was also
terrible because I hadn't really expected this to work and the fact that it did work meant
that I was encouraged, in my stupid idea, and then had to take it further.
And the first thing that I did to take it further was multiple generations.
Could I take these mangled ASTs, these functions that were the product of a mangled AST
and then mangle them together even more and get something even worse?
So, to do that, I had to kind of do this round trip, an AST that was compiled into a function,
choosing the functions that I wanted to recombine, get the ASTs for them,
mutate those to and then combine them again and do this whole round trip. And that was a bunch
of [Indiscernible] around. You can go and look at my code to see how I did that. It was gross.
But it worked. I got even more hideous functions. Things that
produced sort of [Indiscernible] sigils that looked less and less like flowers.
That was also very encouraging to me. So, then I got to thinking, if I can do that,
maybe I can go, like, full genetic programming on it. Maybe I can actually
evolve code. Make something that evolves a Python function to solve a problem.
So, to do that, I needed to start with a function stub. All right. A random function. So, I wrote
a thing that would randomly piece together a little bit of an AST that could get
turned into a function, so this is the example of that approach, using that unpause function
from 3.9 to see the code your AST would generate. So, this is this function doesn't do very much,
but it produces an output that is capable of being interpreted by my drawing library.
So, you take one of those random function stubs, get the instructions that it generates
and then measure the fitness of that function. I'm going to get into that,
more later, because that's kind of the trickiest part, right. Writing something that can tell you,
does the output of this function look like a flower? That's very hard to do.
So, this is where I took most inspiration from genetic programming and spent the most time
talking to Trevor, with him trying to get me to understand this. What I did was used tournament
selection. So, the idea with that is that you have dozens or hundreds of these random functions.
And randomly select a handful of them and then measure the fitness of that random
selection and then take the best of those to be the donor for your next generation.
And then, iterate that several times so that your your next generation is a combination of random
selection and selecting the best. And the reason we do that is to maintain genetic diversity.
If you just get the best functions from each generation, they tend to all be very, very similar
solutions to the problem. By introducing a random element, you get this genetic diversity,
which is [Indiscernible] over time, tends to give you a little bit. Those selected functions
become the donors for this random combination of functions and they make new functions,
which are hopefully a slightly better solution to the problem than the ones you started with.
So, what does that look like? Well, a lot of it depends on the fitness function. This was my first
kind of naive fitness function that I wrote. Basically the idea is, what does a flower look
like? Well, it's got a thin stem and then it's big at the top. So what I want to say, the first
few iterations should have one output in them. It should be just one line
and then after the first four generations or the first four lines,
it should get big, right? So little stem at the bottom and then big at the top.
This is what it output. So, I wrote a thing that would
get the best output the best function from each generation over 10 or 12 generations
and although this is sometimes generating functions that produce flowers, a lot of the time,
it's generating stuff that doesn't it's generating functions that don't draw anything at all.
This is an example of one of the functions it generates and it's illustrating one of the key
pitfalls in machine learning, which is that it has done literally exactly what I asked for.
So, it's doing it's doing something once for every every time, in a range. But
because it starts at zero, the first thing it does is nothing at all and that stops
it from stops the function from working, which means that the flower dies before it's even born.
So, I had to fix that with my next fitness function,
which adds a penalty if the flower is ever a size of zero.
And that's a little bit more successful, right? It's not evolving things that
kind of start to look a little tree like,
like this. Here's an example of the kind of function that it generates. So, still very,
very simple things that get but it does that thing where it starts small and gets bigger.
I did a lot more fiddling around. Here's another thing where it's trying to make it only of a
certain length and get a little more daisy like and kind of this is the first time where I started
to feel like I was actually starting to get something that looked like a flower. See that last
one there? Hang on, there, I'll zoom in. It's got a stem and then a flower on top. Right. It's kind
of it's kind of a flower. Anyway, maybe it was the mania I had gotten into trying to solve this
problem, but I was very, very excited when I saw this picture. And it encouraged me to work harder
that's the function that drew that. So, you can see that it is generating very, very complex code
and code that doesn't a lot of this code never actually gets invoked so it's sort of
demonstrating another common pit fall in genetic programming, which is called bloat. It just
writes mangles things together and seeing what the output is. So, we've got kind of a miss here.
So, it was many, many iterations later of fiddling with that fitness function and seeing the results
and [Indiscernible] around when it kind of started kind of producing things that looked a little bit
like a flower. Not a lot like a flower. It's got a stem at the bottom, which is all one color and
it's thin and it gets big at the top and it sort of explodes out. I think this was maybe my best
flower of many, many attempts and there were a lot more that looked much uglier than that.
Less you be concerned about this taking over our jobs and making us less redundant, do not fear.
This is some of the code that generated that flower, so it's making
absolutely hideous code that none of us should feel worried about. Even my
code looks slightly better than this, when I write it myself.
So some conclusions. Don't do this. It's a terrible idea. Why is it a terrible idea? I guess,
because of that the thing with the fitness functions. Right. What I realized was that
in order to get this to work, I needed to be able to write a function that could exactly
measure whether I had solved the problem. And for any problem with any degree of
complexity, solving that problem
measuring whether I had solved the problem was exactly the same as solving the problem in the
first place. If you can tell whether or not you've solved the problem, if you can describe
the problem so exactly that you can measure it in code, then you've already solved the problem.
So, it turns out this is an actually pointless thing to do for writing code. So, don't do it.
I learned a lot from doing it. I learned a lot about ASTs and what they're good for, which is not
this. I learned a lot about genetic programming. Also, not a good application in this case.
But, very instructive. If you want to learn from my mistakes, you can go and check out my code,
which is here. And, you can read about several of my other stupid ideas, mostly on Medium,
which you can check out there. I'll also try to get those links somewhere where
you can click on them and you don't have to copy them down from my slides.
Um, thank you very much. I've finished a little bit ahead of time so I'll try to
take some questions, if I can. >> Thank you so much, Simon,
for that just delightful journey you've taken us on, on growing syntax trees. I
was laughing laughing a lot, admiring your beautiful blooms that you tended so carefully.
Okay. And, yeah, the chat has been going off this whole time,
with a lot of excellent commentary and puns.
SIMON CARRYER: Oh, I'm glad. I'm glad. >> We have a couple of questions.
We have a few minutes, so add more questions while I'm asking Simon these questions.
Why do all the flowers turn to the left? SIMON CARRYER: Oh, that's a really good
question. Which I don't know the answer to. It's probably a
an accident of how I wrote the code that generates the functions being biased towards no,
it'll be my drawing library, which the turn is either a positive or a negative number and
it's more likely to be a positive number than a negative number because of the way the it's just
an accident of how the code is written. >> That makes sense. That makes sense.
Our next question, actually, I'm going to reorder these questions slightly. Do you think
this would be applicable to data analysis? SIMON CARRYER: I hope not, that's my job.
[Laughter]. >> Good answer.
SIMON CARRYER: Genetic programming, in general, is more applicable in cases where you can easily,
sort of mathematically measure whether you've got a good solution so it tends to be good for
fitting to a curve or, you know, writing a function that can describe some real world
data accessibility. So, yeah, that sort of realm is more likely to be a good idea. Whether doing
that on Abstract Syntax Trees is ever a good idea, I don't know. I don't know. I would be
delighted to find a practical use for this. >> What were your favorite resources for
learning Abstract Syntax Tree stuff? SIMON CARRYER: Um, my favorite way
to do it was to annoy Trevor on Slack, at work, while he was trying to do his job in lockdown.
>> So the rest of us will have to find our own "Trevor" then?
SIMON CARRYER: His documentation of his library is good. Check out the docs on G P Learn.
>> It's always great to hear a recommendation for docs.
Our last question I'd like to end on this, I did not write this question.
What awful, terrible idea are you currently working on?
SIMON CARRYER: So, yeah. You know how when you write code, you, like,
write one function and then another function and then you write something that puts both those
functions together and then you have to why do we have to do that ourselves? It knows what to do.
That's a path finding problem, right? >> That makes perfect non, in brackets,
sense to me. Thanks, Simon, we all needed a good laugh, you provided.
SIMON CARRYER: Cool. Thanks very much. >> So, everybody, we are on a break now.
It is lunchtime. And, just a heads up for anybody who's thinking about submitting a
lightning talk to deliver tomorrow, lightning talk submission close during the lunch break. It's
one of the best parts of a conference. Now's your chance to participate.
Okay. Thanks, again, Simon and we will see you all back after lunch, at 2:00pm conference time,
that's in an hour and a half. Have a nice break. [Lunch break until 2:00 p.m. conference time].