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 multi-parter 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 decades-old software-synthesis 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 blue-sky engineering projects where there’s no known algorithm at all, not easy-sounding 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 Hyoo-Man 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 special-purpose 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 “human-readable” 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 off-the-shelf 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, one-off, avocational-level result; something fancier than a toy demo, but not complicated enough to win the Humie Awards. “Evolve a FizzBuzz program” is a nice, human-sized 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 Clojush-flavored 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 step-by-step 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 copy-edited 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.simple-regression
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.simple-regression
Command line args: clojush.problems.demos.simple-regression
######################################
Parameters set at command line or in problem file argmap; may or may not be default:
atom-generators = (#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)
epigenetic-markers = []
error-function = #object[clojush.problems.demos.simple_regression$fn__6138 0x69f9b561 clojush.problems.demos.simple_regression$fn__6138@69f9b561]
genetic-operator-probabilities = {:alternation 0.5, :uniform-mutation 0.5}
parent-selection = :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.0-1-SNAPSHOTHash of last Git commit = 904a92397b99100bf983a7d7adbcbc50a119bb4b GitHub link = https://github.com/lspector/Clojush/commit/904a92397b99100bf983a7d7adbcbc50a119bb4b
Ah, OK. More versioning. I can get behind thoroughness.
Then:
age-combining-function = :average
age-mediated-parent-selection = false
alignment-deviation = 10
alternation-rate = 0.01
atom-generators = (#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
autoconstructive-boolean-rand-enrichment = 0
autoconstructive-clone-probability = 0.0
autoconstructive-decay = 0.0
autoconstructive-diffmeans-children = 10
autoconstructive-diversification-test = :gecco2016
autoconstructive-environments = false
autoconstructive-genome-instructions = :all
autoconstructive-integer-rand-enrichment = 0
autoconstructive-parent-decay = 0.0
autoconstructive-si-children = 8
autoconstructive-tag-types = [:integer :boolean :exec :float :char :string :code]
close-increment-rate = 0.2
close-parens-probabilities = [0.772 0.206 0.021 0.001]
csv-columns = [:generation :location :total-error :push-program-size]
csv-log-filename = log.csv
decimation-ratio = 1
decimation-tournament-size = 2
edn-additional-keys = [:generation :location]
edn-keys = [:uuid :parent-uuids :genetic-operators :program :genome :total-error :errors]
edn-log-filename = log.edn
epigenetic-markers = []
epsilon-lexicase-epsilon = nil
epsilon-lexicase-probability = 1
error-function = #object[clojush.problems.demos.simple_regression$fn__6138 0x69f9b561 clojush.problems.demos.simple_regression$fn__6138@69f9b561]
error-threshold = 0
evalpush-limit = 150
evalpush-time-limit = 0
exit-on-success = true
final-report-simplifications = 1000
genetic-operator-probabilities = {:alternation 0.5, :uniform-mutation 0.5}
improvement-discount = 0.5
individuals-for-novelty-archive-per-generation = 0
json-log-filename = log.json
json-log-program-strings = false
label = nil
lexicase-leakage = 0.1
lexicase-slippage = 0
log-fitnesses-for-all-cases = false
maintain-ancestors = false
max-error = 1000
max-generations = 1001
max-genome-size-in-initial-program = 50
max-point-evaluations = 1.0E101
max-points = 200
meta-error-categories = []
normalization = :none
novelty-distance-metric = :euclidean
novelty-number-of-neighbors-k = 25
parent-reversion-probability = 1.0
parent-selection = :tournament
pop-when-tagging = true
population-size = 1000
print-ancestors-of-solution = false
print-cosmos-data = false
print-csv-logs = false
print-edn-logs = false
print-error-frequencies-by-case = false
print-errors = true
print-history = false
print-homology-data = false
print-json-logs = false
print-selection-counts = false
print-timings = false
problem-specific-initial-report = #object[clojush.pushgp.report$default_problem_specific_initial_report 0x59fea5f5 clojush.pushgp.report$default_problem_specific_initial_report@59fea5f5]
problem-specific-report = #object[clojush.pushgp.report$default_problem_specific_report 0x70f4abc1 clojush.pushgp.report$default_problem_specific_report@70f4abc1]
random-screen = false
random-seed = -64 -49 68 -60 18 120 65 82 14 100 112 -15 69 70 -26 -46
random-threshold-lexicase-probability = 1
record-host = nil
replace-child-that-exceeds-size-limit-with = :random
report-simplifications = 100
return-simplified-on-failure = false
reuse-errors = true
self-mate-avoidance-limit = 0
silent-instruction-probability = 0.2
tag-enrichment = 0
tag-enrichment-types = [:integer :boolean :exec :float :char :string :code]
tag-limit = 10000
top-level-pop-code = false
top-level-push-code = false
total-error-method = :sum
tournament-size = 7
track-instruction-maps = false
uniform-addition-and-deletion-rate = 0.01
uniform-addition-rate = 0.01
uniform-close-mutation-rate = 0.1
uniform-combination-and-deletion-rate = 0.01
uniform-deletion-rate = 0.01
uniform-mutation-constant-tweak-rate = 0.5
uniform-mutation-float-gaussian-standard-deviation = 1.0
uniform-mutation-int-gaussian-standard-deviation = 1
uniform-mutation-rate = 0.01
uniform-mutation-string-char-change-rate = 0.1
uniform-mutation-tag-gaussian-standard-deviation = 100
uniform-silence-mutation-rate = 0.1
use-single-thread = 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 problem-specific-report = #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 total-error) 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 grain-size in population: 1.0
Maximum grain-size in population: 1.0
Average grain-size in population: 1.0
Median grain-size 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 miscellaneous-seeming descriptive statistics (like Percent parens: 0.020). And then we talk about all the non-best 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 total-error) 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 grain-size in population: 1.0
Maximum grain-size in population: 1.0
Average grain-size in population: 1.0
Median grain-size 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 perfect-scoring 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 Auto-simplifying 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 ;;****************************** ;; Problem-Specific 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 “auto-simplified” 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 stack-based, 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 read-only.
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 re-push 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 (17-289) 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 (1-17) 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 (4352-17) 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 (4335-17) 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 automatically-simplified 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 auto-simplified 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 auto-simplification bug), when I typed the magical incantation.
Later: It turns out that this is not a bug in the auto-simplification, 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.simple-regression (:use [clojush.pushgp.pushgp] [clojush.pushstate] [clojush.random] [clojush.interpreter] [clojure.math.numeric-tower])) ;;;;;;;;;;;; ;; 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 {:error-function (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (let [state (run-push (:program individual) (push-item input :input (push-item input :integer (make-push-state)))) top-int (top-item :integer state)] (if (number? top-int) (abs (- top-int (- (* input input input) (* 2 input input) input))) 1000)))))) :atom-generators (list (fn [] (lrand-int 10)) 'in1 'integer_div 'integer_mult 'integer_add 'integer_sub) :epigenetic-markers [] :parent-selection :tournament :genetic-operator-probabilities {:alternation 0.5 :uniform-mutation 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 super-important, because it’s the only thing in the file… though it’s not exactly self-explanatory or self-documenting.
The :error-function 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 :atom-generators 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 :epigenetic-markers [] 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 :parent-selection :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 :genetic-operator-probabilities {:alternation 0.5 :uniform-mutation 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 :error-function. Here, let me indent it to my own demented tastes:
(def argmap {:error-function (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (let [state (run-push (:program individual) (push-item input :input (push-item input :integer (make-push-state) ))) top-int (top-item :integer state)] (if (number? top-int) (abs (- top-int (- (* 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 (make-push-state), and then calling #(push-item i :integer %) on that, and then calling #(push-item 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 {:error-function (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (let [state (run-push (:program individual) (->> (make-push-state) (push-item input :integer ,) (push-item input :input ,))) top-int (top-item :integer state)] (if (number? top-int) (abs (- top-int (- (* 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 run-with-input "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] (run-push program (->> (make-push-state) (push-item input :integer ,) (push-item input :input ,) ))) (def argmap {:error-function (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (let [program (:program individual) state (run-with-input program input) top-int (top-item :integer state)] (if (number? top-int) (abs (- top-int (- (* 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 top-int 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 run-with-input "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] (run-push program (->> (make-push-state) (push-item input :integer ,) (push-item input :input ,) ))) (defn target-function "returns x^3 - 2x^2 - x" [x] (- (* x x x) (* 2 x x) x )) (defn absolute-difference "returns the absolute difference between two numbers" [v1 v2] (abs (- v1 v2))) (def argmap {:error-function (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (let [program (:program individual) state (run-with-input program input) top-int (top-item :integer state)] (if (number? top-int) (absolute-difference top-int (target-function input)) 1000 )))))) ;;... })
Aha, and top-int 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 run-with-input [individual input] (run-push (:program individual) (->> (make-push-state) (push-item input :integer ,) (push-item input :input ,) ))) (defn target-function "returns x^3 - 2x^2 - x" [x] (- (* x x x) (* 2 x x) x )) (defn absolute-difference "returns the absolute difference between two numbers" [v1 v2] (abs (- v1 v2))) (defn absolute-error-for-training-case "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 (run-with-input program input) top-int (top-item :integer state) expected (target-function input)] (if (number? top-int) (absolute-difference top-int expected) 1000 ))) (def argmap {:error-function (fn [individual] (assoc individual :errors (doall (for [input (range 10)] (absolute-error-for-training-case 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 push-state (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 re-check 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 :error-function is therefore a function over a single individual argument, which produces a collection (using for) for input-output 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 auto-simplification 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 hand-made 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 less-descriptive version by tracing the two programs I provided in the REPL. But be sure to set up the push-state 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
stringas an “answer” (much like this example) - Search over programs that have more (and more appropriate) Push instructions in them; this will involve the enigmatic
:atom-generators, 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 point-mutation 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 simple-sounding things. Spoiler: Since they are even worse-documented 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 take-home 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. ↩