Evolving FizzBuzz programs with Clojush
Draft of 2018.02.12
May include: genetic programming ↗ &c.
The “Fizz Buzz Test” (which because I used to hang out more on the canonical C2 wiki I can’t help but call FizzBuzz) was originally a game for teaching simple arithmetic to elementary school kids, but over the years it’s morphed into a Coding Kata for TDD and other mindful coding practices, and from there (somehow) it’s moved on to appear on the Leader Board for Worst Whiteboard Interview Questions in Tech.
It’s easy to describe: If I give you a number that’s divisible by three, you say (or print) “fizz”; if the number is divisible by 5, you say “buzz”. If both, you say “fizzbuzz”. If neither, say nothing.
It’s a small program. The only value I can see in having somebody write it, would be to watch them surface their thinking process mindfully, or possibly to surface their tacit knowledge of stuff like “how to write automated tests” or “how to commit to GitHub”. But as code goes, it is not in itself useful for anything practical.
Some years ago, I ran a Coding Dojo for Nic McPhee’s computer science club folks at the University of Minnesota at Morris, and we did FizzBuzz in Java (a language I don’t know anything about), and it was fun. Thinking back, we were doing Mob Programming, though it was before that notion seems to have been formalized. As a social thing, it was great.
But this multiparter is going to be about the opposite of “social things”. Programs making programs automatically? Surely that doesn’t involve people.
NARRATOR (V.O.)
It will turn out to involve people.
The other day that very amusing “Fizz Buzz in TensorFlow” essay popped up in my Twitter feed again, some months after it was first doing the rounds. This time, it was Eric Jang, a researcher at Google, who was pointing it out.
We are a long ways away from general AI; ML does poorly on learning tasks like Fizzbuzz. Generalization of FizzBuzz to arbitrary integers would be an excellent benchmark for testing the reasoning capabilities of AI systems, learned or not.
— Eric Jang (@ericjang11) February 9, 2018
I don’t know Eric, but a lot of friends and colleagues follow him on Twitter. But it was the end of a long day, and I did the thing I probably shouldn’t: I popped up in his feed doing my normal Grumpy Old Engineer Schtick:
[muttering] genetic programming handles it remarkably well…
— Striving Always for Insalience (@Vaguery) February 9, 2018
By which of course, I meant, you know… Genetic Programming. The thing I spend most of the time working on, and also the decadesold softwaresynthesis approach to machine learning that does all kinds of things neural networks don’t.^{1}
But I don’t think Eric knew I meant GP, the field. I think maybe he thought I meant “human genetics” somehow:
It does not. many humans fail it...
— Eric Jang (@ericjang11) February 9, 2018
I confess it was really hard not to reply with the canonical o.O
of startled confusion. But being snippy isn’t warranted. After all, I’ve spent most of the last two decades consulting on bluesky engineering projects where there’s no known algorithm at all, not easysounding coding kata stuff like FizzBuzz. So there’s a reasonable question here: Does GP in fact “handle” FizzBuzz “remarkably well”?
One thing I should say before we start: I’ve been using GP since about 1995, and actively working in the field of genetic programming since about 1998. I’m not going to explain a lot of the fiddly details, because one of the things I’ve been doing for twenty fucking years is complaining to people in the field about how many details they like to add.
All you really need to know is this: You may be used to thinking that runnable computer programs need to be semantically and syntactically “right” before you can even run them, and so the idea of “running random code” or “cutting code up and pasting it into random other code” may seem impossible and weird. But the code we use in GP is intentionally “written” in languages that are robust to this kind of abuse. So we often (mainly) write interpreters for these weird robust languages in other “host” languages, so they run on your normal HyooMan computers.
For example, Lee Spector’s Clojush system (which I’ll be using here) is written in Clojure, but it includes an interpreter for the specialpurpose Push language Lee invented about 15 years back. Clojure code is intended for people to read and write (one assumes); Push code is not intended for people to write, and it’s a pain to read. But I’ll try to be clear on the differences.
In this foray, I will be using Clojush to evolve Push programs that “do FizzBuzz”. That makes sense to me, mainly because I know a lot of secrets about Push that I will share with you if and when they come up.
And yes, there are GP systems that will write Java and Python and all kinds of other “humanreadable” code. We’ll do one of those next time.
Am I accidentally lying?
Ironically, I nosed into this embarrassing Twitter conversation just as I was sending out invitations to the sixteenth annual Genetic Programming Theory & Practice workshop. It’s also the point in the calendar where I do a (roughly biennial) review of the FOSS GP software packages out there. And I vaguely recall not long ago friends Lee Spector, Tom Helmuth and Nic McPhee had all mentioned undergraduate students evolving FizzBuzz programs with GP.
So this seems like an interesting opportunity to see whether in fact it’s feasible to download an offtheshelf GP package, build a set of training cases for FizzBuzz, and get the damned thing to evolve a solution.
Frankly, it’s also deeply salient to the work I’ve been trying to do over the last five years on user experience in GP and software synthesis. Looking over the available packages to see how far they’ve improved is just another reminder that the high standards for usability I’ve been yelling about for some time apply to me too… if only I release code.^{2}
This could be a first step of my survey of usability, flexibility and performativeness of FOSS genetic programming software. Just ask it for a quick, oneoff, avocationallevel result; something fancier than a toy demo, but not complicated enough to win the Humie Awards. “Evolve a FizzBuzz program” is a nice, humansized thing to use as a touchstone, it seems, and it’s a good candidate for checking whether a particular GP system is sufficiently flexible and usable, off the shelf.
Also, this will be a good excuse for me to ask again: What is it that we really want these systems to do? Because there’s an interesting analogy here: What is it that we want a candidate for a programming job to “do”?
Spoilers
So far, I’ve downloaded Clojush, and (by force of will and by dint of many swears) managed to build a FizzBuzz problem config file using all kinds of undocumented code and special stuff I have access to on private lab discussion groups. And hey! it runs, and—some of the time—it does in fact evolve FizzBuzz algorithms in the Push language. By running the code several times, of course, I have collected several different FizzBuzz solutions (and made a lot of heat from the laptop), and so we have a variety of stuff to talk about here.
For example, here’s a FizzBuzz program (in Clojushflavored Push) that I quite like, which evolved yesterday:
(exec_stackdepth integer_mod exec_s string_swap in1 integer_mult exec_stackdepth integer_mod "fizz" exec_do*range (string_parse_to_chars string_rest "fizz" string_shove) in1 boolean_xor exec_swap (string_dup "buzz" string_concat exec_stackdepth integer_mod string_empty boolean_dup string_shove boolean_and) false)
I’ll walk through it and explain this little beauty stepbystep later. For now, just believe me that it “does FizzBuzz”, in the sense that if you set an input
(here, in1
) to an integer, and run the program in the Clojush Push interpreter, then when it’s done running the top item on the string
stack will be either an empty string, "fizz"
if the input was divisible by 3, "buzz"
if the input was divisible by 5, or "fizzbuzz"
if it was divisible by 15.
But the important part of the story is what it took for me to “write” that program, despite the paucity of documentation. And maybe the time I’ve spent doing basic science trying to figure out how the fuck it actually works.
Because of course that program (and the several others I’ll show off) doesn’t “do FizzBuzz right”, for an interesting version of “right”. There are tacit and implicit rubrics in the canonical game of “writing code” that these evolved things don’t always surface in a way that would… you know, get GP a job.
You might say this is evolution “being funny”, if you were in a patient mood. Or maybe “writing terrible fucking code” if you were hoping to see something you could adapt and use in production.
See, this is where we come full circle: Maybe GP isn’t trying to get a job writing code for production on your team, Mister Interviewer With a Whiteboard. Maybe GP is a lot more like Joel Grus, and is making a point about what’s being asked of it, and your assumptions and expectations, and maybe even about the mismatch between what you think you want programmers to do, and what you really want them to do in practice….
Maybe it’s working to rule, in other words. And, like its tame and rigid younger cousin Deep Learning, it keeps acting out that way so often that… maybe we should listen?
Oh dear. I see the look on your face. Am I anthropomorphizing too much by saying that? Well, you know… if you thought computers could write code or drive cars like people do, maybe I didn’t start this argument.
So. Let’s evolve some code!
In which I evolve some code
(but not the code I want)
Because I’m very familiar with the project and the people involved, and also because Lee gave a talk touting it at a recent Clojure conference—and definitely also because I’ve based my own work on the Klapaucius interpreter so much on it, after yelling at him (affably, I guess?) about how terrible the User Experience was—I decided to download a fresh copy of Lee Spector’s Clojush package and see what I could do.
Thanks to GitHub, downloading and installing wasn’t too bad. Lee provides instructions. Though I confess I have a lot of previous experience with Leiningen, the requisite package manager for Clojure packages, and setting that up to work seamlessly wasn’t a walk in the park.
Tally “have to install Clojure and Leiningen” first to your list of “does Clojush get a programming job?” tally sheets, please.
Now, let’s look at the repo.
Down inside /Clojush/src/clojush/problems/
is a directory called demos/
, and another one called software/
. I imagine—mainly from experience—that demos/
will contain some examples of how to set up Clojush problems to learn from data I want to provide, and that software/
will contain problem definitions for software synthesis as such. Glancing at the filenames in software/
, I recognize a lot of the software synthesis benchmarks from Tom Helmuth’s thesis, like replace_space_with_newline.clj
and syllables.clj
.
Can I follow directions?
That is to say, can I do what the Clojush docs say and run one of the demo problems? The one Lee spells out in his README.md
looks promising. Here’s the description from the comments inside /Clojush/src/clojush/problems/demos/simple_regression.clj
:
;;;;;;;;;;;; ;; Integer symbolic regression of x^3  2x^2  x (problem 5 from the ;; trivial geography chapter) with minimal integer instructions and an ;; input instruction that uses the default input stack
Sounds pretty straightforward. I don’t have a trivial geography chapter on hand (though I admit I do know what it means, having copyedited that book chapter). Maybe we should suggest he link directly from the code to the paper if he’s going to mention it in the code?
In any case, this problem boils down to: given 10 training cases of the form \((x,y=(x^3  2x^2  x))\), where \(x\) is an integer, give me a program that fits that data.
lein run clojush.problems.demos.simpleregression
Yes! That produces… well an awful lot, actually. The Clojush package has a tendency to dump reams of text to STDOUT
.
$ lein run clojush.problems.demos.simpleregression Command line args: clojush.problems.demos.simpleregression ###################################### Parameters set at command line or in problem file argmap; may or may not be default: atomgenerators = (#object[clojush.problems.demos.simple_regression$fn__6154 0x1573e8a5 clojush.problems.demos.simple_regression$fn__6154@1573e8a5] in1 integer_div integer_mult integer_add integer_sub) epigeneticmarkers = [] errorfunction = #object[clojush.problems.demos.simple_regression$fn__6138 0x69f9b561 clojush.problems.demos.simple_regression$fn__6138@69f9b561] geneticoperatorprobabilities = {:alternation 0.5, :uniformmutation 0.5} parentselection = :tournament ###################################### Registered instructions: #{code_atom genome_uniform_tag_mutation code_car... [and so on]
So there’s a dump here of all the instructions that the defined Clojush interpreter knows. Then we get
Starting PushGP run.
Wait, what? I thought…
Clojush version = 3.9.01SNAPSHOTHash of last Git commit = 904a92397b99100bf983a7d7adbcbc50a119bb4b GitHub link = https://github.com/lspector/Clojush/commit/904a92397b99100bf983a7d7adbcbc50a119bb4b
Ah, OK. More versioning. I can get behind thoroughness.
Then:
agecombiningfunction = :average agemediatedparentselection = false alignmentdeviation = 10 alternationrate = 0.01 atomgenerators = (#object[clojush.problems.demos.simple_regression$fn__6154 0x1573e8a5 clojush.problems.demos.simple_regression$fn__6154@1573e8a5] in1 integer_div integer_mult integer_add integer_sub) autoconstructive = false autoconstructivebooleanrandenrichment = 0 autoconstructivecloneprobability = 0.0 autoconstructivedecay = 0.0 autoconstructivediffmeanschildren = 10 autoconstructivediversificationtest = :gecco2016 autoconstructiveenvironments = false autoconstructivegenomeinstructions = :all autoconstructiveintegerrandenrichment = 0 autoconstructiveparentdecay = 0.0 autoconstructivesichildren = 8 autoconstructivetagtypes = [:integer :boolean :exec :float :char :string :code] closeincrementrate = 0.2 closeparensprobabilities = [0.772 0.206 0.021 0.001] csvcolumns = [:generation :location :totalerror :pushprogramsize] csvlogfilename = log.csv decimationratio = 1 decimationtournamentsize = 2 ednadditionalkeys = [:generation :location] ednkeys = [:uuid :parentuuids :geneticoperators :program :genome :totalerror :errors] ednlogfilename = log.edn epigeneticmarkers = [] epsilonlexicaseepsilon = nil epsilonlexicaseprobability = 1 errorfunction = #object[clojush.problems.demos.simple_regression$fn__6138 0x69f9b561 clojush.problems.demos.simple_regression$fn__6138@69f9b561] errorthreshold = 0 evalpushlimit = 150 evalpushtimelimit = 0 exitonsuccess = true finalreportsimplifications = 1000 geneticoperatorprobabilities = {:alternation 0.5, :uniformmutation 0.5} improvementdiscount = 0.5 individualsfornoveltyarchivepergeneration = 0 jsonlogfilename = log.json jsonlogprogramstrings = false label = nil lexicaseleakage = 0.1 lexicaseslippage = 0 logfitnessesforallcases = false maintainancestors = false maxerror = 1000 maxgenerations = 1001 maxgenomesizeininitialprogram = 50 maxpointevaluations = 1.0E101 maxpoints = 200 metaerrorcategories = [] normalization = :none noveltydistancemetric = :euclidean noveltynumberofneighborsk = 25 parentreversionprobability = 1.0 parentselection = :tournament popwhentagging = true populationsize = 1000 printancestorsofsolution = false printcosmosdata = false printcsvlogs = false printednlogs = false printerrorfrequenciesbycase = false printerrors = true printhistory = false printhomologydata = false printjsonlogs = false printselectioncounts = false printtimings = false problemspecificinitialreport = #object[clojush.pushgp.report$default_problem_specific_initial_report 0x59fea5f5 clojush.pushgp.report$default_problem_specific_initial_report@59fea5f5] problemspecificreport = #object[clojush.pushgp.report$default_problem_specific_report 0x70f4abc1 clojush.pushgp.report$default_problem_specific_report@70f4abc1] randomscreen = false randomseed = 64 49 68 60 18 120 65 82 14 100 112 15 69 70 26 46 randomthresholdlexicaseprobability = 1 recordhost = nil replacechildthatexceedssizelimitwith = :random reportsimplifications = 100 returnsimplifiedonfailure = false reuseerrors = true selfmateavoidancelimit = 0 silentinstructionprobability = 0.2 tagenrichment = 0 tagenrichmenttypes = [:integer :boolean :exec :float :char :string :code] taglimit = 10000 toplevelpopcode = false toplevelpushcode = false totalerrormethod = :sum tournamentsize = 7 trackinstructionmaps = false uniformadditionanddeletionrate = 0.01 uniformadditionrate = 0.01 uniformclosemutationrate = 0.1 uniformcombinationanddeletionrate = 0.01 uniformdeletionrate = 0.01 uniformmutationconstanttweakrate = 0.5 uniformmutationfloatgaussianstandarddeviation = 1.0 uniformmutationintgaussianstandarddeviation = 1 uniformmutationrate = 0.01 uniformmutationstringcharchangerate = 0.1 uniformmutationtaggaussianstandarddeviation = 100 uniformsilencemutationrate = 0.1 usesinglethread = false
Ah. These seem to be the configuration variables. Since the problem definition file doesn’t actually define most of those, I suppose the vast majority of them must be defaults. I guess? Though at least a few of them aren’t actually reporting what the values are, they’re just printing the object ID in memory, like problemspecificreport = #object[clojush.pushgp.report$default_problem_specific_report 0x70f4abc1 clojush.pushgp.report$default_problem_specific_report@70f4abc1]
, which must actually be the memory location of the code in the definition file?
Anyway, that seems to be the pile of background material. Now we start actually evolving:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Generating initial population... Processing generation: 0 Computing errors... Done computing errors. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; * Report at generation 0  Best Program (based on totalerror) Statistics  Best genome: ({:instruction in1} {:instruction in1} {:instruction in1} {:instruction integer_add} {:instruction integer_mult} {:instruction integer_add} {:instruction 8} {:instruction 7} {:instruction integer_div} {:instruction integer_div} {:instruction in1} {:instruction integer_mult} {:instruction integer_add} {:instruction integer_sub} {:instruction in1} {:instruction integer_mult} {:instruction in1} {:instruction 9} {:instruction integer_mult} {:instruction integer_div} {:instruction integer_add} {:instruction integer_mult} {:instruction 0} {:instruction integer_div} {:instruction integer_add} {:instruction integer_add} {:instruction integer_div} {:instruction 2} {:instruction integer_sub} {:instruction in1} {:instruction integer_div} {:instruction integer_add} {:instruction integer_div} {:instruction integer_add} {:instruction integer_sub} {:instruction integer_div} {:instruction in1} {:instruction integer_mult} {:instruction integer_sub} {:instruction integer_mult} {:instruction integer_div} {:instruction 3} {:instruction in1} {:instruction integer_add} {:instruction in1} {:instruction integer_sub} {:instruction 1} {:instruction integer_mult} {:instruction integer_mult}) Best program: (in1 in1 in1 integer_add integer_mult integer_add 8 7 integer_div integer_div in1 integer_mult integer_add integer_sub in1 integer_mult in1 9 integer_mult integer_div integer_add integer_mult 0 integer_div integer_add integer_add integer_div 2 integer_sub in1 integer_div integer_add integer_div integer_add integer_sub integer_div in1 integer_mult integer_sub integer_mult integer_div 3 in1 integer_add in1 integer_sub 1 integer_mult integer_mult) Partial simplification: (in1 in1 in1 integer_add integer_mult integer_add 8 7 integer_div integer_div in1 integer_mult in1 integer_mult in1 9 integer_mult integer_div 0 integer_add 2 integer_sub in1 integer_div integer_add in1 integer_mult integer_sub integer_div 3 in1 integer_add in1 integer_sub integer_mult) Errors: [0N 4N 2N 3N 8N 5N 6N 7N 40N 72N] Total: 147N Mean: 14.7 Genome size: 49 Size: 50 Percent parens: 0.020  Population Statistics  Average total errors in population: 4803.516 Median total errors in population: 1392N Error averages by case: (6.218 14.683 23.831 43.051 101.167 220.47 425.62 752.152 1248.967 1967.357) Error minima by case: (0 0 0 0 0N 0 0 7N 8N 9N) Average genome size in population (length): 25.225 Average program size in population (points): 26.225 Average percent parens in population: 0.076 Minimum age in population: 0.0 Maximum age in population: 0.0 Average age in population: 0.0 Median age in population: 0.0 Minimum grainsize in population: 1.0 Maximum grainsize in population: 1.0 Average grainsize in population: 1.0 Median grainsize in population: 1.0  Population Diversity Statistics  Min copy number of one Plush genome: 1 Median copy number of one Plush genome: 1 Max copy number of one Plush genome: 7 Genome diversity (% unique Plush genomes): 0.976 Min copy number of one Push program: 1 Median copy number of one Push program: 1 Max copy number of one Push program: 7 Syntactic diversity (% unique Push programs): 0.976 Total error diversity: 0.297 Error (vector) diversity: 0.395  Run Statistics  Number of program evaluations used so far: 1000 Number of point (instruction) evaluations so far: 252250  Timings  Current time: 1518468358560 milliseconds ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; * End of report for generation 0 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Lots of stuff here. We have a genome for the “best” program, and the program itself, and some miscellaneousseeming descriptive statistics (like Percent parens: 0.020
). And then we talk about all the nonbest programs, I guess. There are (now I glance at it) 1000 genomes and programs in the population, so there are a lot of things going on behind the scenes. Ten training cases, each evaluated for 1000 programs… we’re running 10000 programs here, just to report these stats.
But this is the first generation, which is to say it’s just random guesses, not evolved programs yet. So then what happens?
Well, that generation report prints a few more times, and then—for my run on my computer, that time—the final (tenth) generation includes a program with errors Errors: [0N 0N 0N 0N 0N 0N 0N 0N 0N 0N]
, which I suppose means it solved the training cases perfectly. Here it is:
Producing offspring... Installing next generation... Processing generation: 10 Computing errors... Done computing errors. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; * Report at generation 10  Best Program (based on totalerror) Statistics  Best genome: ({:instruction in1} {:instruction integer_mult} {:instruction integer_add} {:instruction 9} {:instruction integer_sub} {:instruction in1} {:instruction integer_div} {:instruction 7} {:instruction 3} {:instruction 4} {:instruction integer_div} {:instruction integer_div} {:instruction integer_mult} {:instruction 4} {:instruction integer_div} {:instruction integer_div} {:instruction integer_mult} {:instruction integer_mult} {:instruction integer_add} {:instruction in1} {:instruction integer_add} {:instruction in1} {:instruction in1} {:instruction integer_mult} {:instruction integer_sub} {:instruction integer_sub} {:instruction in1} {:instruction 1} {:instruction in1} {:instruction integer_mult} {:instruction integer_div} {:instruction in1} {:instruction integer_sub} {:instruction integer_mult} {:instruction integer_mult} {:instruction integer_div} {:instruction in1} {:instruction integer_sub} {:instruction integer_mult} {:instruction integer_div} {:instruction integer_mult} {:instruction integer_div} {:instruction in1} {:instruction integer_sub} {:instruction integer_mult} {:instruction integer_div} {:instruction integer_sub} {:instruction integer_mult}) Best program: (in1 integer_mult integer_add 9 integer_sub in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult) Partial simplification: (integer_add 9 integer_sub 4 integer_div 4 integer_div in1 integer_add in1 in1 integer_mult integer_sub in1 in1 integer_div in1 integer_sub integer_mult in1 integer_sub in1 integer_sub integer_mult) Errors: [0N 0N 0N 0N 0N 0N 0N 0N 0N 0N] Total: 0N Mean: 0.0 Genome size: 48 Size: 49 Percent parens: 0.020  Population Statistics  Average total errors in population: 698.629 Median total errors in population: 45N Error averages by case: (2.553 1.897 3.546 7.482 17.435 36.512 68.082 117.567 190.101 253.454) Error minima by case: (0N 0N 0N 0N 0N 0N 0N 0 0N 0N) Average genome size in population (length): 37.68 Average program size in population (points): 38.68 Average percent parens in population: 0.027 Minimum age in population: 0.0 Maximum age in population: 10.0 Average age in population: 9.82 Median age in population: 10.0 Minimum grainsize in population: 1.0 Maximum grainsize in population: 1.0 Average grainsize in population: 1.0 Median grainsize in population: 1.0  Population Diversity Statistics  Min copy number of one Plush genome: 1 Median copy number of one Plush genome: 1 Max copy number of one Plush genome: 263 Genome diversity (% unique Plush genomes): 0.353 Min copy number of one Push program: 1 Median copy number of one Push program: 1 Max copy number of one Push program: 263 Syntactic diversity (% unique Push programs): 0.353 Total error diversity: 0.193 Error (vector) diversity: 0.213  Run Statistics  Number of program evaluations used so far: 11000 Number of point (instruction) evaluations so far: 3804910  Timings  Current time: 1518468376974 milliseconds ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; * End of report for generation 10 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Then, having identified a perfectscoring program over the training data, we do some more reporting:
SUCCESS at generation 10 Successful program: (in1 integer_mult integer_add 9 integer_sub in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult) Errors: [0N 0N 0N 0N 0N 0N 0N 0N 0N 0N] Total error: 0 History: null Size: 49 Autosimplifying with starting size: 49 step: 0 program: (in1 integer_mult integer_add 9 integer_sub in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult) errors: [0N 0N 0N 0N 0N 0N 0N 0N 0N 0N] total: 0 size: 49 step: 500 program: (3 4 integer_div in1 integer_add in1 integer_mult integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult in1 integer_sub in1 integer_sub) errors: (0 0N 0N 0N 0N 0N 0N 0N 0N 0N) total: 0 size: 21 step: 1000 program: (3 4 integer_div in1 integer_add in1 integer_mult integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult in1 integer_sub in1 integer_sub) errors: (0 0N 0N 0N 0N 0N 0N 0N 0N 0N) total: 0 size: 21 ;;****************************** ;; ProblemSpecific Report of Simplified Solution
So to summarize, here’s what was evolved as a “match” to our training data:
( in1 integer_mult integer_add 9 integer_sub in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult)
And that evolved program is subsequently “autosimplified” to a much shorter one… but (foreshadowing) let’s set the simpler one aside for the moment and look at the long convoluted one, OK?
Clearly you can see that it’s \(y=(x^3  2x^2  x)\). Right?
What’s that? You’re not seeing it?
Here, let’s walk through the code step by step.
Walking through the code
Things you need to know:
Push is a stackbased, typed, imperative language. A program is an ordered collection of literals, instructions and code blocks, and the interpreter is initialized by pushing the program onto a special :exec
stack. The interpreter then pops the top item from :exec
, examines what it is, and acts accordingly.
Literals (numbers, here) are pushed immediately onto the corresponding stack of their type.
Instructions are executed immediately, consuming their arguments from the tops of the appropriate stacks if their arguments are present. If arguments are missing—for instance, if integer_add
is being executed but there aren’t two or more items on the integer
stack at that moment—then the instruction disappears and nothing else changes. If integer_add
is executed when there are two or more integer
items, then the top two integer
items are popped immediately, and their sum (in this case) is pushed back onto the integer
stack.
Variables, like in1
here, are simple instructions in Clojush that return their assigned value. They’re immutable and readonly.
Code blocks (there aren’t any here, except the whole program) are parenthesized collections of other items, including potentially more code blocks. When the interpreter executes them, the items are “unwrapped” and pushed back onto the exec
stack in the same order. You don’t need to know that here, for this program, but for others later you will.
So now let’s walk through our \(y=(x^3  2x^2  x)\) program, drawing the Push stacks along the way. We start with the program pushed onto the exec
stack. Say we’ve already assigned a (test) value of 17 to the in1
input, so the result should end up being \(4318=(17^3  2(17^2)  17)\). I’ll represent the top of the stacks at the left here, because it’s easier for me.
;; starting condition exec: [(in1 integer_mult integer_add 9 integer_sub in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult)] integer: [] ;; pop the code block (the whole program) and repush its contents to exec exec: [in1 integer_mult integer_add 9 integer_sub in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [] ;; pop in1; push its assigned value (17) exec: [integer_mult integer_add 9 integer_sub in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17] ;; pop integer_mult; it's missing arguments, so nothing happens exec: [ integer_add 9 integer_sub in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17] ;; pop integer_add; it's missing arguments, so nothing happens exec: [ 9 integer_sub in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17] ;; pop 9; push it exec: [ integer_sub in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [9 17] ;; pop integer_sub; do it (17  9) exec: [ in1 integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [8] ;; pop in1; push its assigned value (17) exec: [ integer_div 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17 8] ;; pop integer_div; do it (8 / 17) exec: [ 7 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [0] ;; pop 7 exec: [ 3 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [7 0] ;; pop 3 exec: [ 4 integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [3 7 0] ;; pop 4 exec: [ integer_div integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [4 3 7 0] ;; pop integer_div; do it exec: [ integer_div integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [0 7 0] ;; pop integer_div; but divisor is 0, so do nothing (in Clojush) exec: [ integer_mult 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [0 7 0] ;; pop integer_mult; do it exec: [ 4 integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [0 0] ;; pop 4; exec: [ integer_div integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [4 0 0] ;; pop integer_div; do it exec: [ integer_div integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [0 0] ;; pop integer_div; but divisor is 0, so do nothing (in Clojush) exec: [ integer_mult integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [0 0] ;; pop integer_mult; do it exec: [ integer_mult integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [0] ;; pop integer_mult; missing argument so do nothing exec: [ integer_add in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [0] ;; pop integer_add; missing argument so do nothing exec: [ in1 integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [0] ;; pop in1; push its assigned value (17) exec: [ integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17 0] ;; pop integer_add; do it exec: [ integer_add in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17] ;; pop integer_add; missing argument so do nothing exec: [ in1 in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17] ;; pop in1; push its assigned value (17) exec: [ in1 integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17 17] ;; pop in1; push its assigned value (17) exec: [ integer_mult integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17 17 17] ;; pop integer_mult; do it exec: [ integer_sub integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [289 17] ;; pop integer_sub; do it (17289) exec: [ integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [272] ;; pop integer_sub; missing argument so do nothing exec: [ in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [272] ;; pop in1; push its assigned value (17) exec: [ 1 in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17 272] ;; pop 1 exec: [ in1 integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [1 17 272] ;; pop in1; push its assigned value (17) exec: [ integer_mult integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17 1 17 272] ;; pop integer_mult; do it exec: [ integer_div in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17 17 272] ;; pop integer_div; do it exec: [ in1 integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [1 272] ;; pop in1; push its assigned value (17) exec: [ integer_sub integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17 1 272] ;; pop integer_sub; do it (117) exec: [ integer_mult integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [16 272] ;; pop integer_mult; do it exec: [ integer_mult integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [4352] ;; pop integer_mult; missing arg exec: [ integer_div in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [4352] ;; pop integer_div; missing arg exec: [ in1 integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [4352] ;; pop in1; push its assigned value (17) exec: [ integer_sub integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17 4352] ;; pop integer_sub; do it (435217) exec: [ integer_mult integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [4335] ;; pop integer_mult; missing arg exec: [ integer_div integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [4335] ;; pop integer_div; missing arg exec: [ integer_mult integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [4335] ;; pop integer_mult; missing arg exec: [ integer_div in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [4335] ;; pop integer_div; missing arg exec: [ in1 integer_sub integer_mult integer_div integer_sub integer_mult] integer: [4335] ;; pop in1; push its assigned value (17) exec: [ integer_sub integer_mult integer_div integer_sub integer_mult] integer: [17 4335] ;; pop integer_sub; do it (433517) exec: [ integer_mult integer_div integer_sub integer_mult] integer: [4318] ;; pop integer_mult; missing arg exec: [ integer_div integer_sub integer_mult] integer: [4318] ;; pop integer_div; missing arg exec: [ integer_sub integer_mult] integer: [4318] ;; pop integer_sub; missing arg exec: [ integer_mult] integer: [4318] ;; pop integer_mult; missing arg exec: [ ] integer: [4318]
And there you have it! The top item on the integer
stack is 4318, which is exactly \(4318=(17^3  2(17^2)  17)\), as expected.
How do you feel?
A few observations and a serious bug (?)
By convention, Push programs in Clojush don’t return a value as such. The interpreter state changes for every step of the program that’s run, and each change may consume or add items to a variety of stacks.
In general, folks evolve programs so that when they’re done running, the “answer” is sitting on top of the appropriate stack. In the case of this demo problem, we’re looking for an integer
, so the “answer” is expected to be at the top of the integer
stack when we’re done.
In the case of FizzBuzz, the input argument will be an integer value, but we’re looking for a string
. Push, as implemented in Clojush, has several types and hundreds of instructions that do useful work on literals on the stacks. So when we get around to writing a problem definition for FizzBuzz, I’ll be comparing the expected string “output” to the top item on the string
stack.
You might have noticed that (1) this evolved program is very convoluted, and (2) I carefully didn’t walk through the automatically simplified version of the program. That’s because the automaticallysimplified program, which is supposed to do the same thing, does not. When I run (3 4 integer_div in1 integer_add in1 integer_mult integer_sub in1 1 in1 integer_mult integer_div in1 integer_sub integer_mult in1 integer_sub in1 integer_sub)
I don’t get the same “answer”. I’m not sure what’s happening there, but the errors against the training set don’t even look like they’re correct. Using the (slightly) more straightforward way of tracing a program inside the Clojush interpreter, I find that the simplified program gives 464
as the answer for an input of 8
, instead of the expected 376
.
This seems to be a bug, since even though the autosimplified program is described as having errors: (0 0N 0N 0N 0N 0N 0N 0N 0N 0N)
, clearly that’s not happening here.
As for the working (whole) program being convoluted… yes, well. It does exactly what we asked it to do. It “learned” an algorithm that mapped the training cases to the desired outputs, and which generalizes quite nicely. It is, in some real sense that should leave you pretty dissatisfied, an implementation of \(f(x) = (x^3  2x^2  x)\) in the Push language.
It also seems to do a lot of other things. We’ll talk more about that later.
For now, agree with me that it worked as promised (except for the troubling autosimplification bug), when I typed the magical incantation.
Later: It turns out that this is not a bug in the autosimplification, but rather a weird collision between my (reasonable) expectations of how an interpreter is set up, and how the demo problem actually sets its interpreters up. Spoiler: the demo config file pushes two copies of the input value to two different stacks!
OK, so the demo worked…
On the premise that looking at a problem definition file in demos/
should actually demonstrate how to do stuff in Clojush, let’s look at that file.
;; simple_regression.clj ;; an example problem for clojush, a Push/PushGP system written in Clojure ;; Lee Spector, lspector@hampshire.edu, 2010 (ns clojush.problems.demos.simpleregression (:use [clojush.pushgp.pushgp] [clojush.pushstate] [clojush.random] [clojush.interpreter] [clojure.math.numerictower])) ;;;;;;;;;;;; ;; Integer symbolic regression of x^3  2x^2  x (problem 5 from the ;; trivial geography chapter) with minimal integer instructions and an ;; input instruction that uses the default input stack (def argmap {:errorfunction (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (let [state (runpush (:program individual) (pushitem input :input (pushitem input :integer (makepushstate)))) topint (topitem :integer state)] (if (number? topint) (abs ( topint ( (* input input input) (* 2 input input) input))) 1000)))))) :atomgenerators (list (fn [] (lrandint 10)) 'in1 'integer_div 'integer_mult 'integer_add 'integer_sub) :epigeneticmarkers [] :parentselection :tournament :geneticoperatorprobabilities {:alternation 0.5 :uniformmutation 0.5} })
It’s a lovely example of concrete poetry. Is there enough information here to understand how to build a Fizz Buzz problem and run it?
Obviously argmap
is superimportant, because it’s the only thing in the file… though it’s not exactly selfexplanatory or selfdocumenting.
The :errorfunction
seems particularly salient, since we all know we’re trying to evolve things that have minimal error over some set of training cases. But let’s set that aside for a moment and look at the rest.
I happen to know that :atomgenerators
is a collection of all the parts that can appear in a Push program in Clojush. That is, it’s saying what we build random programs from, and also what we can mutate items into. To be honest, this demo is stacking the deck a good bit by only including four instructions (integer_div
, integer_mult
, integer_add
and integer_sub
), the input in1
, and constant numbers from 0
through 9
. The whole Clojush dialect of Push is several hundred instructions, and of course all kinds of constants.
But that’s to be expected. We want to demonstrate the process, not try something super hard, right? (:thinking_face:
)
I don’t know what :epigeneticmarkers []
might be, but it sure doesn’t seem to be doing anything here, since it’s set to an empty vector.
I happen to know what :parentselection :tournament
means. Tournament selection is a common algorithm for selecting breeding individuals in evolutionary algorithms and related metaheuristics. What I don’t know is what other values it might take, besides :tournament
. Maybe we’ll look those up later.
And :geneticoperatorprobabilities {:alternation 0.5 :uniformmutation 0.5}
is clearly setting some more configurable parameters for search. I happen to know what alternation
refers to, because I read these folks’ papers every year or so. Do you?
We’re not getting a lot of information I think we need.
Now, let’s return to :errorfunction
. Here, let me indent it to my own demented tastes:
(def argmap {:errorfunction (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (let [state (runpush (:program individual) (pushitem input :input (pushitem input :integer (makepushstate) ))) topint (topitem :integer state)] (if (number? topint) (abs ( topint ( (* input input input) (* 2 input input) input ))) 1000 )))))) ;; ... })
So it looks as if…. [squinting]
OK. So we’re associating a new value with an individual
, under the key :errors
. It’s plural, so it’s going to be an error value for each training case, I suspect.
Then we’re explicitly doing this for the numbers (range 10)
, instead of passing in an argument to a function? Make a note: see if you can extract that function.
For each one of those integers i
, we’re making a state
, which is some awful nested call thing where we’re starting with (makepushstate)
, and then calling #(pushitem i :integer %)
on that, and then calling #(pushitem i :input %)
on that.
There’s something bugging me about that. So we’re starting the program running with one number on the integer
stack? That’s not what I assumed, above… and now I should check to see whether I worked out the values correctly for my evolved programs after all. But after we fix this code to learn how what it actually intends.
Let me try something more like
(def argmap {:errorfunction (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (let [state (runpush (:program individual) (>> (makepushstate) (pushitem input :integer ,) (pushitem input :input ,))) topint (topitem :integer state)] (if (number? topint) (abs ( topint ( (* input input input) (* 2 input input) input ))) 1000 )))))) ;;... })
Oh wait! We’re actually not just setting up the Push interpreter here, we’re running the set up interpreter as well. In a let
block. Wow that wants to be a function, so let me just reach down in there and…
(defn runwithinput "returns a push state in which the input has been put onto the :integer _and_ the :input stacks, and the program has been run" [program input] (runpush program (>> (makepushstate) (pushitem input :integer ,) (pushitem input :input ,) ))) (def argmap {:errorfunction (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (let [program (:program individual) state (runwithinput program input) topint (topitem :integer state)] (if (number? topint) (abs ( topint ( (* input input input) (* 2 input input) input ))) 1000 )))))) ;;... })
Ah, that’s better. Now there’s some breathing room here. Now what’s that wobbly tail hanging down at the bottom?
We’re checking to see if the topint
is a number?
. OK. And if it is, we’re doing some math, which also should probably come out because what the actual fuck is it doing in there?
Here. Give me that….
(defn runwithinput "returns a push state in which the input has been put onto the :integer _and_ the :input stacks, and the program has been run" [program input] (runpush program (>> (makepushstate) (pushitem input :integer ,) (pushitem input :input ,) ))) (defn targetfunction "returns x^3  2x^2  x" [x] ( (* x x x) (* 2 x x) x )) (defn absolutedifference "returns the absolute difference between two numbers" [v1 v2] (abs ( v1 v2))) (def argmap {:errorfunction (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (let [program (:program individual) state (runwithinput program input) topint (topitem :integer state)] (if (number? topint) (absolutedifference topint (targetfunction input)) 1000 )))))) ;;... })
Aha, and topint
is in fact something more like the “calculated answer”, right? And that whole doall
loop is just calculating the absolute difference between the expected value and the answer, or 1000
if there is no answer.
Here, now it makes some sense:
(defn runwithinput [individual input] (runpush (:program individual) (>> (makepushstate) (pushitem input :integer ,) (pushitem input :input ,) ))) (defn targetfunction "returns x^3  2x^2  x" [x] ( (* x x x) (* 2 x x) x )) (defn absolutedifference "returns the absolute difference between two numbers" [v1 v2] (abs ( v1 v2))) (defn absoluteerrorfortrainingcase "given an individual and an x value, runs the program with that x loaded as an input and an integer, and " [individual input] (let [program (:program individual) state (runwithinput program input) topint (topitem :integer state) expected (targetfunction input)] (if (number? topint) (absolutedifference topint expected) 1000 ))) (def argmap {:errorfunction (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (absoluteerrorfortrainingcase individual input) )))) ;;... })
OK. Now it makes some sense!
Caveat lector: I have been manually refactoring this code so I can understand it but there are no tests in the codebase, so I am not actually running the code. That is horrible and I will yell at the authors (again) about how horrible this is to make me do this sort of sinful crap. I feel bad. Do not try this at home; throw away code that isn’t tested, before trying to refactor it.
To run a program here, we first make a new pushstate
(which I guess is an interpreter?) and load the input value onto both the :input
and :integer
stacks. Remind me, again, to go back and recheck my “bug”, above.
To evaluate a run program, we look at the top integer
item after it’s been run. If there’s no item at all, we give it a score of 1000
, and if there is an item, we take the absolute difference between that number and the desired target value.
And the :errorfunction
is therefore a function over a single individual
argument, which produces a collection (using for
) for inputoutput pairs in (range 10)
.
I would have made 10
an argument, but I’m not trying to fix this. I’m just trying to understand the simplest demo.
Backtracking: Is there a bug in autosimplification after all?
So I use the Clojure REPL to trace the programs I evolved earlier, being careful this time to set up a copy of the input value on both the input
and integer
stacks. And when I run it, the simplified program now does indeed produce the correct values.
Interestingly, the unsimplified program produces the same value whether the value is on integer
or not. Which makes me still feel there is a qualitative difference between the two programs. I am still falling to the side of “this is a bug”, but it’s a bug of documentation and intent, not a bug in the reporting itself. I’m sure folks would think I was being fiddly, and that I should perhaps be happy that I evolved a program that didn’t even need both copies of the number. The fact that “simplifying it” produced a program that did need both copies is simply a coincidental juxtaposition of two mistakes on my part.
Hmmm.
Answer: No. The bug is in the documentation.
And of course, now the bug is in my handmade trace of the more complicated program, above. I won’t bother you with the same thing worked out again, since you can actually get a lessdescriptive version by tracing the two programs I provided in the REPL. But be sure to set up the pushstate
correctly, with both values!
Are we there yet?
No.
I’ve just run (and tried to understand) the simplest demo here. Whew.
How did I produce a version of a problem file (like the one above) that would work for my FizzBuzz program?
One thing I see, working through the simple_regression.clj
error function, is that distance is a useful concept here. What is the “distance” between a string I see on the string
stack, and one I want to see produced?
My first instinct here is to use an edit distance. I happen to know that Clojush has a Levenshtein distance utility built in, so I will let it slip that I used that.
So here’s the premise for modifying this problem definition to work with FizzBuzz:
 Use some integer inputs (just like this example)
 Use the top
string
as an “answer” (much like this example)  Search over programs that have more (and more appropriate) Push instructions in them; this will involve the enigmatic
:atomgenerators
, but I don’t want to specify every damned instruction in a list. So I’ll need to find out how to say “all of them”  Instead of using the absolute difference, use the Levenshtein distance
 Figure out how to do those search operator things. Specifically, because I know how these things work already and I know these folks’ research, I will want to use lexicase selection, and the addition and deletion search operators, not just pointmutation and alternation crossover. You probably don’t know what I’m talking about, and to be honest you shouldn’t have to because these are Terms of Art that should be documented in the damned code.
Next time, I’ll speak briefly about how I managed to do those five simplesounding things. Spoiler: Since they are even worsedocumented than what I’ve done so far with Clojush, getting the configuration built was more painful in many ways than today’s story of running the demo sounds. I suspect it’s only because I know an awful lot about GP that I was able to evolve some FizzBuzz programs at all.
My takehome lesson: I wish the Clojush code was more carefully refactored, maybe enough to make it legible for a human being, and also that it was better documented. This is a complicated system, but it doesn’t have to be so damned opaque. I am frustrated and tired, just writing about what I did the other day.
But it all works out, in the end. Sort of.
Next time: Evolved FizzBuzz programs, and what they mean

Like, for example, designing optical devices and stock portfolio management of real money, both things Eric seems to have been musing aloud about lately…. ↩

I am about to release code. Real soon now. ↩