Push instructions done lazily
Draft of 2024.08.08
May include: genetic programming ↘ Push language ↗ &c.
Lee Spector’s Push language is an excellent and under-utilized focus of research in genetic programming. There are a lot of reasons for this, mainly things Lee knew from the early days: unlike more traditional GP-facing representation schemes, it allows for code with iteration and recursion; it permits—though in practice rarely is allowed to use—runtime variables and code abstraction; it includes the capacity for some simple runtime introspection of interpreter and program states; it can easily (sortof) be extended with domain-specific types. And as I recently argued in my GPTP 2024 video on the subject, it’s much more closely related to traditional Koza-style GP “trees” than anybody has mentioned.
There are some other aspects that have gone relatively unexplored, though. For instance, the structure of the language is easy to imagine in the framework by which it was designed, with two broad classes: one I might want to call the “work-facing” instructions that “do math” and manipulate the values of arguments and produce results (traditional functions, in a way, though they are not); and a second class of “combinator” instructions that “change state” by operating on the runtime interpreter’s data structures, often without directly manipulating the internal state of items, or creating any new “results”. But I think there’s a potentially more useful dichotomy to explore, as the video linked above points out. Instructions that can be performed in a “lazy interpreter” (or as Acides Fonseca prefers, an “abstract interpreter”), and those that cannot.
To that end, I’ve been trying to compile a big Encyclopedia of Push Instructions (so far), and work my way through them all and decide whether they can be lazy/abstract, or whether they must be handled by propagating eager assignments.
For example, in my Klapaucius 2 interpreter, I’ve extended the standard Push 2-input boolean functions from :boolean_and and :boolean_or to include a more general one, which is capable of expressing all possible 2-input truth tables: :bool_2in. This function takes a :scalar argument and two :bool arguments, and depending on the value of the scalar (modulo 16), it applies the corresponding truth table to the two boolean arguments.
This seems like a useful thing, but it introduces some thought-provoking problems for “lazy interpreter” mode.
Consider what happens when I run the Push code (:b1 :b2 :bool_or :b3 :bool_and) in a “lazy mode” (where :b1, :b2 and :b3 are boolean constants):
:exec :bool
(:b1 :b2 :bool_or :b3 :bool_and)
:b1 :b2 :bool_or :b3 :bool_and
:b2 :bool_or :b3 :bool_and :b1
:bool_or :b3 :bool_and :b2 :b1
:b3 :bool_and (:b1 :b2 :bool_or)
:bool_and :b3 (:b1 :b2 :bool_or)
((:b1 :b2 :bool_or) :b3 :bool_and)
I have a clean, postfix “trace” of all function arguments and their outcomes.
Things are a little more complicated (but not broken) for something like :bool_2in (again, :k1 and :k2 as constant scalars):
:exec :bool :scalar
(:b1 :b2 :k1 :k2 :bool_2in :b3 :bool_2in)
:b1 :b2 :k1 :k2 :bool_2in :b3 :bool_2in
:b2 :k1 :k2 :bool_2in :b3 :bool_2in :b1
:k1 :k2 :bool_2in :b3 :bool_2in :b2 :b1
:k2 :bool_2in :b3 :bool_2in :b2 :b1 :k1
:bool_2in :b3 :bool_2in :b2 :b1 :k2 :k1
:b3 :bool_2in (:k2 :b1 :b2 :bool_2in) :k1
:bool_2in :b3 (:k2 :b1 :b2 :bool_2in) :k1
(:k1 :b3 (:k2 :b1 :b2 :bool_2in) :bool_2in)
Now this is not ambiguous. It captures every argument and result correctly, and it’s produced a valid postfix representation of the resulting DAG of this interpreter’s trace.
But on the face of it, it feels precarious. Most of us, even those who’ve written a number of interpreters ourselves, have not handled this sort of “possible ambiguity” before. Because none of us really do anything beyond imperative, eager evaluation; this “lazy” bullshit is weird and new.
So let’s think it all through. One instruction at a time. And decide what is and is not “lazyable”.
Lacking any complete Push language specification, I’ll use the most senior Clojush instruction set here.
Boolean instructions: very lazy
boolean_and:(:b1 :b2 :boolean_and) -> :boolboolean_not:(:b1 :boolean_not) -> :boolboolean_or:(:b1 :b2 :boolean_or) -> :boolboolean_xor:(:b1 :b2 :boolean_xor) -> :boolboolean_invert_first_then_and:(:b1 :b2 :boolean_invert_first_then_and) -> :boolboolean_invert_second_then_and:(:b1 :b2 :boolean_invert_second_then_and) -> :boolboolean_fromfloat:(:f1 :boolean_fromfloat) -> :boolboolean_frominteger:(:k1 :boolean_frominteger) -> :bool
Character instructions: very lazy
:char_isletter:(:c1 :char_isletter) -> :bool:char_isdigit:(:c1 :char_isdigit) -> :bool:char_iswhitespace:(:c1 :char_iswhitespace) -> :bool:char_fromfloat:(:f1 :char_fromfloat) -> :char:char_frominteger:(:k1 :char_frominteger) -> :char:char_allfromstring:(:s1 :char_allfromstring) -> :char[](multiple results):char_uppercase:(:c1 :char_uppercase) -> :char:char_lowercase:(:c1 :char_lowercase) -> :char
Numeric (float and integer) instructions: very lazy
:NUMERIC_gt:(:k1 :k2 :integer_gt) -> :bool:NUMERIC_gte:(:k1 :k2 :integer_gte) -> :bool:NUMERIC_lt:(:k1 :k2 :integer_lt) -> :bool:NUMERIC_lte:(:k1 :k2 :integer_lte) -> :bool:NUMERIC_add:(:k1 :k2 :integer_add) -> :integer:NUMERIC_sub:(:k1 :k2 :integer_sub) -> :integer:NUMERIC_mult:(:k1 :k2 :integer_mult) -> :integer:NUMERIC_div:(:k1 :k2 :integer_div) -> :integer:NUMERIC_mod:(:k1 :k2 :integer_mod) -> :integer:NUMERIC_max:(:k1 :k2 :integer_max) -> :integer:NUMERIC_min:(:k1 :k2 :integer_min) -> :integer:NUMERIC_fromboolean:(:b1 :integer_fromboolean) -> :integer:NUMERIC_fromchar:(:c1 :integer_fromchar) -> :integer:NUMERIC_fromstring:(:s1 :integer_fromstring) -> :integer:NUMERIC_inc:(:k1 :integer_inc) -> :integer:NUMERIC_dec:(:k1 :integer_dec) -> :integer:float_cos:(:f1 :float_cos) -> :float:float_sin:(:f1 :float_sin) -> :float:float_tan:(:f1 :float_tan) -> :float:NUMERIC_negate:(:f1 :float_negate) -> :float:NUMERIC_abs:(:f1 :float_abs) -> :float:NUMERIC_pow:(:f1 :f2 :float_pow) -> :float:float_square:(:f1 :float_square) -> :float:float_sqrt:(:f1 :float_sqrt) -> :float:float_log10:(:f1 :float_log10) -> :float:float_log2:(:f1 :float_log2) -> :float:float_ceiling:(:f1 :float_ceiling) -> :float:float_floor:(:f1 :float_floor) -> :float:float_arccos:(:f1 :float_arccos) -> :float:float_arcsin:(:f1 :float_arcsin) -> :float:float_arctan:(:f1 :float_arctan) -> :float
String instructions (not shown): also lazy
There are a lot of :string instructions in Clojush, and it turns out they’re all lazyable, in the same way the numeric ones above are.
Code instructions: more interesting
Here we start to see some interesting dynamics, which may or may not affect abstraction.
In all cases where the arguments are themselves fully-determined, as you should understand by now, there’s no issue constructing a clean postfix abstract function call. I won’t work through them all—not least because they’re fiddly and complicated when it comes to argument order—but here are the instructions I’m glossing over: :code_append, :code_atom, :code_car, :code_cdr, :code_cons, :code_container, :code_contains, :code_do, :code_do*, :code_extract, :code_fromboolean (and related conversions), :code_if, :code_insert, :code_length, :code_list, :code_map, :code_member, :code_noop, :code_null, :code_position, :code_quote, :code_size, :code_subst, :code_wrap.
Here are some more interesting ones though:
:code_do*count: takes two arguments, a:k1from:integerand:q1from:code. Constructs a continuation form(0 :k1 :code_quote :q1 :code_do*range), which is pushed to:exec. As it happens, this is… fine? Nothing weird happens in this lazy version. The:code_quotetakes its argument from:exec, and we are guaranteed to end up in the:code_do*rangebecause the numerical constant must be strictly positive. So let’s look at that….-
:code_do*range: This slightly more complex iteration instruction takes two integer arguments:k1and:k2, and a:codeargument:q1. If:k1 ≠ :k2, it brings:k1closer by one to:k2, and pushes the following continuation form to:exec, where:k3is an intermediate result that is “move:k1one closer to:k2:(:q1 (:k3 :k2 :code_quote :q1 :code_do*range)). However, if:k1 = :k2we push the continuation form(:q1 (:k1 :k2 :q1)). The practical question, though, is what consequences this might have for an abstract interpreter.Let’s work it through with an example.
:exec :code :int
(:k1 :k2 :code_do*range) :foo
:k1 :k2 :code_do*range :foo
:k2 :code_do*range :foo :k1
:code_do*range :foo :k2 :k1
:code_do*range :foo :k2 :k1
(:foo ((:k1 :integer_inc) :k2 :code_quote :foo :code_do*range))
:foo ((:k1 :integer_inc) :k2 :code_quote :foo :code_do*range)
((:k1 :integer_inc) :k2 :code_quote :foo :code_do*range) ;; :foo is invoked
(:k1 :integer_inc) :k2 :code_quote :foo :code_do*range
:k2 :code_quote :foo :code_do*range (:k1 :integer_inc)
:code_quote :foo :code_do*range :k2 (:k1 :integer_inc)
:code_do*range :foo :k2 (:k1 :integer_inc)
:code_do*range :foo :k2 (:k1 :integer_inc)
(:foo (((:k1 :integer_inc) :integer_inc) :k2 :code_quote :foo :code_do*range))
:foo (((:k1 :integer_inc) :integer_inc) :k2 :code_quote :foo :code_do*range)
(((:k1 :integer_inc) :integer_inc) :k2 :code_quote :foo :code_do*range) ;; :foo is invoked
((:k1 :integer_inc) :integer_inc) :k2 :code_quote :foo :code_do*range
:k2 :code_quote :foo :code_do*range ((:k1 :integer_inc) :integer_inc)
:code_quote :foo :code_do*range :k2 ((:k1 :integer_inc) :integer_inc)
:code_do*range :foo :k2 ((:k1 :integer_inc) :integer_inc)
(:foo (((:k1 :integer_inc) :integer_inc) :k2 :foo))
:foo (((:k1 :integer_inc) :integer_inc) :k2 :foo)
(((:k1 :integer_inc) :integer_inc) :k2 :foo) ;; :foo is invoked
((:k1 :integer_inc) :integer_inc) :k2 :foo
5 :foo ((:k1 :integer_inc) :integer_inc)
:foo :k2 ((:k1 :integer_inc) :integer_inc)
:k2 ((:k1 :integer_inc) :integer_inc) ;; :foo is invoked?
While there seems to be some question about how many times :foo (the popped code argument) is executed, I can see no place where the careful tracking of increments (or decrements) of the counters will fail. There’s no need to invoke the conditional “if :k1 is less than :k2 then…” sort of code in the trace, since that happens offstage, within the logic, and is deterministic. Aside from side-effects caused by the repeated execution of :foo (whatever that is), the only slightly-weird thing is the accumulation of increments/decrements of the counters. Which is linear in terms of number of steps executed, to be frank.
:code_do*times: literally works by invokingcode_do*range, so nothing weird here
indexed instructions
:code_nth: This is the first instruction I’m examining where there’s a numeric argument that affects the outcome. The integer argument (in Clojush’s version) is used to index an element of the topmost :code item, and essentially replace the item with that sub-item.
On the one hand, an abstract interpreter could very easily just note all the parts as usual, and propagate something like (:k1 :code_quote (:q1 :q2) :code_nth) through the entire DAG. That is, it could carry the abstract :k1 and :q1/:q2 forward, and just not bother locking either one down. That certainly preserves the flexibility of the conditional execution this sort of instruction captures.
The trick here though is that I’ve intentionally added a piece of code, the :code_quote, to make this executable when it’s revisited. That code is not part of the actual execution trace; it exists only so that when this new code is executed, the results are (hopefully) the same.
But that sort of intervention is worrying, because there very much are places we’ll get to below, like :X_stackdepth instructions, where adding a new piece of weird code will throw off the recorded behavior.
On the other hand, a bit of notation might avoid this problem, without obfuscating too much, but at the cost of executability. Perhaps something like (:q1 :q2)[:k1], where we’re using an idiomatic array-indexing notation from other languages just for this task, might also work? Is there any reason to preserve the causal relationship that :code_nth brings to the table? Any existing counter-logic could be captured inside the indexing brackets, for instance in (:q1 :q2)[(:k1 :integer_inc)]. Is that good enough?
To be continued…