A few more evolved FizzBuzz Push programs
Draft of 2018.02.20
May include: genetic programming ↘ &c.
I’ve said in earlier episodes that I’ve been successfully evolving algorithms that “do” FizzBuzz, using Lee Spector’s Clojush. I wanted to record and walk through a few more of the programs that arose, just to explore the “design patterns” that Clojush tends to uncover in the Push language it implements.
I’m hoping to use one of the other off-the-shelf genetic programming projects out there (possibly PonyGE2, which uses Grammatical Evolution) to do the same thing. We’ll see how that works another time, but I am curious to see what the Python code it “discovers” will be like, in comparison to Push code.
How I’m doing this
I’m starting from the instructions posted at the Clojush repository’s wiki, but of course things could be made a lot easier.
So here’s what I’ve set up in my REPL, which is honestly weird because why wouldn’t this already be a thing included in the Clojush distribution?
(use 'clojush.pushstate) (use 'clojush.interpreter) (use 'clojush.args) (defn trace-push [program args-vector steps] (let [start-state (reduce (fn [p i] (push-item i :input p)) (make-push-state) args-vector)] (reset-globals {:evalpush-limit steps}) (run-push program start-state true) ))
This function trace-push does all the work of setting up a new Push interpreter thing, pushes all the items in the collection args-vector onto the :input stack (in that order), and runs the program with the specified :evalpush-limit. This way, I can type a single line to trace a given program with a particular input, and it will poop out all this state information for me to edit later:
clojush.core=> (trace-push '(2 3 integer_mult 4 5 integer_sub) [17] 100)
State after 0 steps:
:exec = ((2 3 integer_mult 4 5 integer_sub))
:code = nil
:integer = nil
:float = nil
:boolean = nil
:char = nil
:string = nil
:zip = nil
:vector_integer = nil
:vector_float = nil
:vector_boolean = nil
:vector_string = nil
:input = (17)
:output = nil
:auxiliary = nil
:tag = nil
:return = nil
:environment = nil
:genome = nil
State after 1 steps (last step: (...)):
:exec = (2 3 integer_mult 4 5 integer_sub)
:code = nil
:integer = nil
:float = nil
:boolean = nil
:char = nil
:string = nil
:zip = nil
:vector_integer = nil
:vector_float = nil
:vector_boolean = nil
:vector_string = nil
:input = (17)
:output = nil
:auxiliary = nil
:tag = nil
:return = nil
:environment = nil
:genome = nil
State after 2 steps (last step: 2):
:exec = (3 integer_mult 4 5 integer_sub)
:code = nil
:integer = (2)
:float = nil
:boolean = nil
:char = nil
:string = nil
:zip = nil
:vector_integer = nil
:vector_float = nil
:vector_boolean = nil
:vector_string = nil
:input = (17)
:output = nil
:auxiliary = nil
:tag = nil
:return = nil
:environment = nil
:genome = nil
State after 3 steps (last step: 3):
:exec = (integer_mult 4 5 integer_sub)
:code = nil
:integer = (3 2)
:float = nil
:boolean = nil
:char = nil
:string = nil
:zip = nil
:vector_integer = nil
:vector_float = nil
:vector_boolean = nil
:vector_string = nil
:input = (17)
:output = nil
:auxiliary = nil
:tag = nil
:return = nil
:environment = nil
:genome = nil
State after 4 steps (last step: integer_mult):
:exec = (4 5 integer_sub)
:code = nil
:integer = (6)
:float = nil
:boolean = nil
:char = nil
:string = nil
:zip = nil
:vector_integer = nil
:vector_float = nil
:vector_boolean = nil
:vector_string = nil
:input = (17)
:output = nil
:auxiliary = nil
:tag = nil
:return = nil
:environment = nil
:genome = nil
State after 5 steps (last step: 4):
:exec = (5 integer_sub)
:code = nil
:integer = (4 6)
:float = nil
:boolean = nil
:char = nil
:string = nil
:zip = nil
:vector_integer = nil
:vector_float = nil
:vector_boolean = nil
:vector_string = nil
:input = (17)
:output = nil
:auxiliary = nil
:tag = nil
:return = nil
:environment = nil
:genome = nil
State after 6 steps (last step: 5):
:exec = (integer_sub)
:code = nil
:integer = (5 4 6)
:float = nil
:boolean = nil
:char = nil
:string = nil
:zip = nil
:vector_integer = nil
:vector_float = nil
:vector_boolean = nil
:vector_string = nil
:input = (17)
:output = nil
:auxiliary = nil
:tag = nil
:return = nil
:environment = nil
:genome = nil
State after 7 steps (last step: integer_sub):
:exec = ()
:code = nil
:integer = (-1 6)
:float = nil
:boolean = nil
:char = nil
:string = nil
:zip = nil
:vector_integer = nil
:vector_float = nil
:vector_boolean = nil
:vector_string = nil
:input = (17)
:output = nil
:auxiliary = nil
:tag = nil
:return = nil
:environment = nil
:genome = nil
#clojush.pushstate.PushState{:exec (), :code nil, :integer (-1 6), :float nil, :boolean nil, :char nil, :string nil, :zip nil, :vector_integer nil, :vector_float nil, :vector_boolean nil, :vector_string nil, :input (17), :output nil, :auxiliary nil, :tag nil, :return nil, :environment nil, :genome nil, :termination :normal}
clojush.core=>
As I mentioned in earlier Push traces, I’m editing out the superfluous information by hand, and also adding annotations in each step to help explain what’s going on. So don’t worry, I hope it won’t be this messy or opaque for the real programs.
Revisiting “The Finger Counter”
This is actually a program I’ve already discussed, which I started to call “the Finger Counter” when I started to take a look into its dynamics. I’m not certain I really know how it works, at this writing, just that it seems to have a remarkably high computational complexity. So I want to go back and walk through it for all four input conditions: argument is divisible by 15, divisible by 3, divisible by 5 and not divisible by 3 or 5.
;; "fingers"
(in1
exec_do*while
(exec_do*count
(exec_do*count
(in1
"buzz"
exec_yankdup)
integer_div
exec_when
"fizz"
string_take
integer_yankdup
boolean_frominteger
string_take
string_dup
integer_stackdepth
exec_yankdup
exec_y
integer_sub
string_take
exec_do*times
(integer_lte
exec_while
("fizz"
"buzz"
string_concat
exec_flush)))))
Let me start this time with an input of 14:
And you know what? I have no damned idea how this works. I mean, I see it looping and stuff, but I can’t follow this example at all.
Let me try with an argument that is divisible by 3 (so how about 3 itself?):
It’s a real head-scratcher. But then, finally, I see where there’s a divergence in the two runs, at the 16th step. There is a call to 'exec_yankdup, and that is using a value that changes depending on the input argument (the value is actually, at this point, \((i-1)\) for some argument \(i\)).
The 'x_yankdup combinator instruction, in Push languages, pops an :integer argument. It looks at the :x stack (for some :x, so :exec_yankdup looks at :exec), and it makes a duplicate of the item in that stack it finds at the indicated position (in zero-based notation, because Clojure). If the integer is 0 or less, it will return the top item; up to the length of the stack, it will pick that indexed item; for larger numbers, it will pick the last item.
So this is where we see our branching logic in “Fingers”. For an input of 15, we push a copy of the item on the :exec stack indexed by 14, which is the code block '(integer_lte exec_while ("fizz" "buzz" string_concat exec_flush)). For an input of 3, we push a copy of the item found in the 2nd position, which is a 'string_take instruction. These two new different-sized :exec items change the length of the :exec stack in each case, so from here on the dynamics diverge in time somewhat as well.
What happens further along, it seems, is that with input 14, at step 21 we end up with :string = ("fizz" "buzz"), and the very next instruction is that string_take we didn’t duplicate earlier, producing the stack :string = ("" "buzz"), which persists through the remainder of the trace.
On the other hand, with input 3, the duplicated string_take instruction has erased the one string on the stack, but it has also consumed our one :integer. So now we enter a series of instructions that need :integer arguments, but lack them and therefore fail. Finally, in the 19th step, we obtain the stack :string = ("fizz" ""). Later, in the 24th step, we actually duplicate the top "fizz", but for no apparent reason.
To be honest, it’s not clear how this could work for an argument that is a multiple of 3. That is, we duplicated a particular item onto the :exec stack with input 3, and that depended on the input. If I try 6 what happens?
That’s odd. I haven’t finished annotating this one, because it appears to the same things along the way as the case with input 3. So what’s different, and how does that…?
Here’s what’s happens with an input of 33:
Notice that this one doesn’t enter the infinite loop until step 43, and when it does, its :string stack is :string = ("fizz" "fizz" "" "buzz" "buzz"). That’s quite a bit different from the earlier 3-divisible cases, where we entered the infinite loop at step 26, with a stack :string = ("fizz" "fizz" ""), in both cases.
This is so confusing.
I try a few different 3-divisible inputs, and look to see (1) when the infinite loop starts, and (2) what the :string stack looks like.
input first exec_y string stack
----- ------------ ------------
3 27 ["fizz" "fizz" ""]
6 27 ["fizz" "fizz" ""]
9 28 * ["fizz" "fizz" "buzz"]
12 27 ["fizz" "fizz" ""]
18 35 ["fizz" "fizz" "" "buzz"]
21 35 ["fizz" "fizz" "" "buzz"]
24 36 * ["fizz" "fizz" "buzz" "buzz"]
27 35 ["fizz" "fizz" "" "buzz"]
33 43 ["fizz" "fizz" "" "buzz" "buzz"]
36 43 ["fizz" "fizz" "" "buzz" "buzz"]
39 44 * ["fizz" "fizz" "buzz" "buzz" "buzz"]
42 43 ["fizz" "fizz" "" "buzz" "buzz"]
48 51 ["fizz" "fizz" "" "buzz" "buzz" "buzz"]
51 51 ["fizz" "fizz" "" "buzz" "buzz" "buzz"]
54 52 * ["fizz" "fizz" "buzz" "buzz" "buzz" "buzz"]
57 51 ["fizz" "fizz" "" "buzz" "buzz" "buzz"]
63 59 ["fizz" "fizz" "" "buzz" "buzz" "buzz" "buzz"]
69 60 * ["fizz" "fizz" "buzz" "buzz" "buzz" "buzz" "buzz"]
111 83 ["fizz" "fizz" "" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz"]
222 139 ["fizz" "fizz" "" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz"]
333 203 ["fizz" "fizz" "" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz"]
336 203 ["fizz" "fizz" "" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz"]
339 225 * ["fizz" "fizz" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz" "buzz"]
342 203 ["fizz" "fizz" "" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz" "buzz" "buzz" "buzz" "buzz"
"buzz" "buzz" "buzz"]
My head hurts.
OK, so it seems as if there are actually two different branches handling “divisible by 3 not 5”. In one, which applies when the argument is \(i \in \{3,6,12,18,21,27,33,36,42,\dots\}\), there ends up being an empty string between the two copies of "fizz", and a monotonically-increasing series of "buzz". In the other, which applies when the argument is \(i \in \{9,24,39,54,69,\dots\}\), the stacks don’t contain an empty string.
Those numbers don’t seem familiar. But looking up [9,24,39,54,69] in the OEIS produces, “Numbers that are the sum of 9 nonzero 4th powers.”
What the actual fuck?
You’ll notice that at the end of the table above, I considered inputs of 333, 336, 339 and 342. That’s because I’d looked at 333 (one of those numbers you type into a program when you want “a bunch not a lot”), and once I saw the OEIS series I tested to see if the next element larger than 333 would share that not-deleted-central-“buzz” feature. And yes, it does, and the adjacent divisible-by-3 values do not.
Seriously: what?
I will have to come back to to this another day. More infrastructure is called for, if I’m to actually understand what’s happening here. For example, as I watch the traces scroll by on the terminal window, I notice that the :exec stack grows and then shrinks again. Obviously something is happening that makes copies of something (possibly the way the Push loops unroll?), and then as those get executed we consume items until we’re down to the 'exec_y milestone I’ve arbitrarily picked.
But… what?
Just what is it that you’re doing, Fingers?