A Very Small Push

The other day I realized that several of my colleagues who invented the Push language, or who have written interpreters in other “host” languages, haven’t really done a very thorough job explaining what Push is. There are a few slide decks from tutorials at the big GECCO conference, but they’re hard to parse out of context.

So let me start.

Now, a word of warning to the lector: Push is an old language as these things go, but more importantly it’s an intentionally extensible and experimental one. So the last “firm” basis for comparison between the many Push implementations in the world is probably the Push3 specification from Lee Spector, Chris Perry, Jon Klein, and Maarten Keijzer and jesus christ that’s almost fifteen years old. A lot of changes—some of which might be improvements—have been made since those days in both the Clojush version (which is kinda sorta canon now), and my own Klapaucius implementation, which is intended as a kind of “next generation” Push.¹

I want to start small here, so I will be describing what to do to build the kind of Push interpreter I see many people imagining they want. Because of machine learning’s (disappointing) focus on numerical models, let’s build a simple numerical Push interpreter. But because there needs to be a difference between neural networks and other machine learning methods on the one hand, and genetic programming on the other, let’s also include the :boolean type and logical instructions in our mix. This pushes the sorts of model we can develop out past most mathematical habits, into if/then territory that’s hard to type in \(\LaTeX\). We will also implement an :error type, because reasons.

But also realize that as soon as I start off I will be describing a Push which is different from most of the canon, and that I’ll be including things that are essentially “modern and advanced” compared to Push3 and earlier versions. We’ll use a simple :scalar type to represent all numbers, not two separate Computer Sciencey :integer and :float types. I do this 100% because I have a horse in this race, but I can also justify it because of all the weird broken things we’ll encounter along the way as we explore the consequences of computers’ stupidity when it comes to numbers.

I won’t include code here, if I can avoid it. I’ll expect you to have a strong enough grasp of relatively simple data structures (like arrays and stacks and conditional logic) in whatever language you choose to use for your implementation. But I’ve done this in Ruby, and Javascript, and Swift and Clojure so far, and it’s pretty resilient against language quirks.

What is Push?

Push is a simple programming language which is designed to maximize semantic flexibility and robustness against syntax errors. Speaking more practically, it’s designed so that Push programs can be chopped up and rearranged arbitrarily and still run. You might want to chop up and run rearranged programs if you’re interested in genetic programming. Which definitely what Lee Spector and colleagues had in mind when Push was first designed many years back.

A Push program, or code block, is an ordered collection (“array” or “list”, depending on what your programming inclinations are) of

1. literal values of some known type
2. variable names
3. instruction names
4. code blocks

I’ll try to use parentheses here to show general code blocks, both at the program level and the internal code block level. I’ll use a colon in front of both instruction names and variable names, because it’s handy to have a visual clue and also because a lot of the implementation languages I’ve worked in have a “keyword” type that has a colon for decoration.

Here are some Very Small Push programs we might run across:

(6 :x1 :add)
(:x2 :x1 :divide :x1 :scalar-swap)
(:x1 1964 :multiply :x1 :multiply 9 :x1 :multiply :add 11 :subtract)
( ( ( ( 7 ) 2 ) :add ) )

The interpreter has a collection of stacks. These are pushdown stacks which generally hold items of a particular type, although there are some exceptions and conventions that undermine that a bit. In our Very Small Push interpreter, we’ll have

• :exec stack, which holds any Push code items
• :scalar stack, which will hold numbers
• :boolean stack, which will hold true and false values
• :error stack, which will hold records of bad things that almost happened

The interpreter also has a collection of bindings, which are how we can deal with arguments and input values. In the Very Small Push interpreter, we’ll start with two bindings: :x1 and :x2, which I’ll just use to represent our input values. Before we run a program that we want to think of as a function, we’ll assign input values to these variables. If we wanted to write (or evolve) a function with a lot of different input possibilities—for instance in data mining applications—we’d simply need to set up the appropriate bindings beforehand.

Here, we’ll be running programs that are intended to represent mathematical functions on two input variables, so let’s stick with :x1 and :x2 for now.

So far so good?

The Interpreter cycle

We initialize the Very Small Push interpreter this way:

1. clear all the stacks and bindings
2. assign argument values to :x1 and :x2 bindings
3. place the program onto the :exec stack
4. establish any routing rules for literals

In Very Small Push, we’ll implement two simple routing rules for literals: Any number will go to :scalar, any true or false value will go to :boolean. We’ll talk about :error below.

So let’s do that in a little cartoon, with a simple Push program, say (6 :x1 :add). I’ll draw the state of the Push interpreter as a series of “snapshots”, starting from the initialized state with the stacks and bindings cleared, an assignment of :x1 (say it’s 33) and :x2 of -2.3.

:x1      [33]
:x2      [-2.3]
:exec    [(6 :x1 :add)]
:scalar  []
:boolean []
:error   []

I’m drawing the bindings and the stacks with square brackets, so I can indicate where they’re empty. In our Very Small Push though, realize that the bindings aren’t stacks.² Notice also that I’ve put the whole program (6 :x1 :add) onto the :exec stack as a single code block. So there’s one thing on :exec and nothing on :scalar or :boolean or :error.

Now that the interpreter is set up, we can start the interpreter cycling until we run out of stuff to do.

The core Push interpreter cycle is this:

1. The top item is popped off of :exec.
2. If the item is a variable binding, then the current value of that variable is looked up and pushed back onto :exec.
3. If the item is an instruction name, then the instruction is immediately executed (more on this below).
4. If the item is a literal item (a number or boolean value, in our case here) then it is pushed onto the appropriate stack associated with its type.
5. If the item is a code block, then it is “unwrapped” and all the pieces inside are pushed onto the :exec stack in the same order.

So let me walk through what happens with (6 :x1 :add). Here’s our initial state again:

:x1      [33]
:x2      [-2.3]
:exec    [(6 :x1 :add)]
:scalar  []
:boolean []
:error   []

We pop the top item off of :exec. Let me indicate what’s being processed by adding a place-holder for it in my diagram, and also label the “tick” of the interpreter cycle:

step       1
processing (6 :x1 :add)
:x1        [33]
:x2        [-2.3]
:exec      []
:scalar    []
:boolean   []
:error     []

In step 1, we’re considering the code block (6 :x1 :add). It’s not an instruction or literal or bound variable, so we trigger the rule for code blocks and unwrap it and push it back onto :exec as three items:

step       1
processing N/A
:x1        [33]
:x2        [-2.3]
:exec      [6 :x1 :add]
:scalar    []
:boolean   []
:error     []

And that’s it for the first step of execution. Notice that if the items inside the block had included other blocks, we would not have unwrapped those.

Why in Push do we “unwrap” code blocks like that? It seems to have no effect on the outcome of any of the instructions, since you’re doing the same thing as just ignoring the parentheses. Ah, yes, this is true for our limited instruction set in Very Small Push. But in full-fledged Push there is also a :code type, and there are number of useful and interesting instructions that can effect “the next item on :exec” to implement loops and recursion and all kinds of computer sciencey stuff. So go through the motions now, to make a full Push implementation easier later.

In any case, we’ve finished the first interpreter step. Let’s carry on by popping the top :exec item, which is now 6:

step       2
processing 6
:x1        [33]
:x2        [-2.3]
:exec      [:x1 :add]
:scalar    []
:boolean   []
:error     []

The number is going to be sent to :scalar, because our routers recognize it as such.

step       2
processing N/A
:x1        [33]
:x2        [-2.3]
:exec      [:x1 :add]
:scalar    [6]
:boolean   []
:error     []

Let’s carry on. The next item is :x1.

step       3
processing :x1
:x1        [33]
:x2        [-2.3]
:exec      [:add]
:scalar    [6]
:boolean   []
:error     []

Now this is a known variable name, so we push its current value onto :exec:

step       3
processing N/A
:x1        [33]
:x2        [-2.3]
:exec      [33 :add]
:scalar    [6]
:boolean   []
:error     []

We pop another item. Oh look, it’s 33:

step       4
processing 33
:x1        [33]
:x2        [-2.3]
:exec      [:add]
:scalar    [6]
:boolean   []
:error     []

We know what to do

step       4
processing N/A
:x1        [33]
:x2        [-2.3]
:exec      [:add]
:scalar    [33 6]
:boolean   []
:error     []

By convention I am putting the top of the stacks at the left. This is entirely up to you, and in fact it contradicts what a lot of stack implementations in programming languages usually do (preferring the right end), but I like it because it makes reading the :exec stack easier for humans. (2 3 :minus) will eventually produce \((2-3)\), not \((3-2)\).

Now we come to our first instruction in this program, :add.

step       5
processing :add
:x1        [33]
:x2        [-2.3]
:exec      []
:scalar    [33 6]
:boolean   []
:error     []

All the useful work of Push is done by its instructions. Indeed, it quickly becomes impossible to understand how programs unfold without looking at the finicky details of instructions and their arguments.

Let me just say what I think :add should do, being careful to specify it exactly: If there are two or more items on :scalar, pop the top two items, and push their sum onto :exec.

So let’s do that, because our program is about finished, and then I’ll go into some details and caveats. There are in fact two or more items on :scalar, so we pop 33 and 6, add them, and push the result onto :exec.

step       5
processing N/A
:x1        [33]
:x2        [-2.3]
:exec      [39]
:scalar    []
:boolean   []
:error     []

There’s one thing on :exec, so we’ll pop it and do the thing:

step       6
processing 39
:x1        [33]
:x2        [-2.3]
:exec      []
:scalar    []
:boolean   []
:error     []

step       6
processing N/A
:x1        [33]
:x2        [-2.3]
:exec      []
:scalar    [39]
:boolean   []
:error     []

And with that, we’re done executing our simple Push program.

Some notes

The first thing you will probably be thinking is: Couldn’t we have skipped that bit with the :exec stack and just pushed 39 onto :scalar right away? And the answer is yes, except that once again there may end up being some consequences down the road in a full-featured Push language implementation. For now, let me do this odd-seeming extra work, because it will always be the case—as long as I’m consistent—that things work out correctly when this happens.

The second thing you might be thinking is: So we end up with something on :scalar? Isn’t there an “answer” or something? And here you’re right again! There is no universal convention in Push for “return this value”, and the reasons are tied up in the philosophy of computation and modeling. So the most common approach to evaluating a program is to state what the type of the “result” should be, and look at the top item on the stack when the program is “done”.

The trick with “done”, and the reason for the scare quotes, is again a thing about full-fledged Push that doesn’t signify in our Very Small Push. That is, as I mentioned above, there are code-manipulating iteration and recursion instructions that fiddle in all kinds of arbitrary ways with the running program while it’s running. So “done” is in quotes because of the Halting Problem. It’s entirely possible for a Push program to never reach a state with an empty :exec stack, although we did here. In our Very Small Push, there’s no risk of a runaway program, but we might as well use the convention of looking at the top item on :scalar (or :boolean if you want to consider a predicate function).

But if you’re really paying close attention (or if you read my previous piece on it), you might be wondering what should happen when we encounter an instruction like :add and do not have enough items on the :scalar stack to execute it.

Missing arguments

Let me show. I’ll shuffle the parts of our program (6 :x1 :add) a little bit, and execute (6 :add x1) instead this time.

step       1
processing (6 :add :x1)
:x1        [33]
:x2        [-2.3]
:exec      []
:scalar    []
:boolean   []
:error     []

step       1
processing
:x1        [33]
:x2        [-2.3]
:exec      [6 :add :x1]
:scalar    []
:boolean   []
:error     []

step       2
processing 6
:x1        [33]
:x2        [-2.3]
:exec      [:add :x1]
:scalar    []
:boolean   []
:error     []

step       2
processing
:x1        [33]
:x2        [-2.3]
:exec      [:add :x1]
:scalar    [6]
:boolean   []
:error     []

step       3
processing :add
:x1        [33]
:x2        [-2.3]
:exec      [:x1]
:scalar    [6]
:boolean   []
:error     []

Aha. Here we are, processing :add, but there are not two or more items on :scalar. What happens?

Well, in the simplest case (which is to be honest 90% or more of Push interpreters in the world), we treat :add as if it were a NOOP. That is, we do nothing at all. We throw it away. We move on.

But I would like to suggest that maybe it would be useful for more complex programs if we made a note of it, instead. So let me amend my definition of :add from above just a bit, so it reads

If there are two or more items on :scalar, pop the top two items, and push their sum onto :exec; otherwise, push an error message to :error.

So instead of doing nothing at all, let’s make a note on :error. And carry on.

step       3
processing
:x1        [33]
:x2        [-2.3]
:exec      [:x1]
:scalar    [6]
:boolean   []
:error     ["step 3: :add missing args"]

step       4
processing :x1
:x1        [33]
:x2        [-2.3]
:exec      []
:scalar    [6]
:boolean   []
:error     ["step 3: :add missing args"]

step       4
processing
:x1        [33]
:x2        [-2.3]
:exec      [33]
:scalar    [6]
:boolean   []
:error     ["step 3: :add missing args"]

step       5
processing 33
:x1        [33]
:x2        [-2.3]
:exec      []
:scalar    [6]
:boolean   []
:error     ["step 3: :add missing args"]

step       5
processing
:x1        [33]
:x2        [-2.3]
:exec      []
:scalar    [33 6]
:boolean   []
:error     ["step 3: :add missing args"]

Now we’re “done”, because there’s nothing on :exec.

Notice what happened. Instead of breaking because of a syntax error, our :add instruction failed but we kept plowing ahead anyway. I made up a simple “error message” and pushed it to my :error stack, but that is just for my personal benefit.

Actually, it’s not just for my personal benefit, though the reason is again tied up in the more “advanced” world in which Push originally arose. Consider that we’re running Push programs in order to evaluate them, because we’re evolving them trying to find some that have more useful behavior, or more accurate matches to some target data or specification. For instance, we might have a population of a thousand different programs, each of which is executed with :x1 set to 33 because we want to find models where the “result” is 39.

Keeping track of :error values gives us a way of comparing two otherwise indistinguishable programs that return identical answers, but which might use different algorithms to do so. It gives us clues about what chunks of Push code we can delete as well, since of course any instruction that lacks arguments won’t change the non-:error parts of the interpreter.

But even more interesting is what we can do with runtime errors.

Runtime errors

Let me walk through the second example program I listed above, (:x2 :x1 :divide :x1 :scalar-swap), with the assignments :x1->33 and :x2->0.0:

step       1
processing (:x2 :x1 :divide :x1 :scalar-swap)
:x1        [33]
:x2        [0.0]
:exec      []
:scalar    []
:boolean   []
:error     []

step       1
processing
:x1        [33]
:x2        [0.0]
:exec      [:x2 :x1 :divide :x1 :scalar-swap]
:scalar    []
:boolean   []
:error     []

step       2
processing :x2
:x1        [33]
:x2        [0.0]
:exec      [:x1 :divide :x1 :scalar-swap]
:scalar    []
:boolean   []
:error     []

step       2
processing  
:x1        [33]
:x2        [0.0]
:exec      [0.0 :x1 :divide :x1 :scalar-swap]
:scalar    []
:boolean   []
:error     []

step       3
processing 0.0
:x1        [33]
:x2        [0.0]
:exec      [:x1 :divide :x1 :scalar-swap]
:scalar    []
:boolean   []
:error     []

step       3
processing
:x1        [33]
:x2        [0.0]
:exec      [:x1 :divide :x1 :scalar-swap]
:scalar    [0.0]
:boolean   []
:error     []

step       4
processing :x1
:x1        [33]
:x2        [0.0]
:exec      [:divide :x1 :scalar-swap]
:scalar    [0.0]
:boolean   []
:error     []

step       4
processing
:x1        [33]
:x2        [0.0]
:exec      [:divide :x1 :scalar-swap]
:scalar    [33 0.0]
:boolean   []
:error     []

Let me step in and define our two new instructions for you.

For :divide, if there are two or more items on the :scalar stack, pop the top one and call it B and the second one and call it A. If B is not zero, then calculate A/B and push that quotient onto :exec. If B is zero, or arguments are missing, push an appropriate :error message, consuming the arguments.

Notice that this (like :subtract I mentioned before) is sortof backwards-feeling. But when I wrote (A B :divide) in the program (or in the :exec stack), I mean to indicate \((A\div B)\) not \((B\div A)\). Because of the way we shifted stuff from :exec onto :scalar, things get reversed. So now we unreverse them.

It’s another matter of convention. Honestly, as long as you’re consistent, it’s totally up to you.

For :scalar-swap, if there are two or more items on :scalar, pop the top one (call it A) and the second one (call it B). Push the code block (A B) onto the :exec stack. If there aren’t two or more items, push an :error message.

Got that? Good!

step       5
processing :divide
:x1        [33]
:x2        [0.0]
:exec      [:x1 :scalar-swap]
:scalar    [33 0.0]
:boolean   []
:error     []

step       5
processing
:x1        [33]
:x2        [0.0]
:exec      [0.0 :x1 :scalar-swap]
:scalar    []
:boolean   []
:error     []

step       6
processing 0.0
:x1        [33]
:x2        []
:exec      [:x1 :scalar-swap]
:scalar    []
:boolean   []
:error     []

step       6
processing
:x1        [33]
:x2        []
:exec      [:x1 :scalar-swap]
:scalar    [0.0]
:boolean   []
:error     []

step       7
processing :x1
:x1        [33]
:x2        []
:exec      [:scalar-swap]
:scalar    [0.0]
:boolean   []
:error     []

step       7
processing
:x1        [33]
:x2        []
:exec      [33 :scalar-swap]
:scalar    [0.0]
:boolean   []
:error     []

step       8
processing 33
:x1        [33]
:x2        []
:exec      [:scalar-swap]
:scalar    [0.0]
:boolean   []
:error     []

step       8
processing
:x1        [33]
:x2        []
:exec      [:scalar-swap]
:scalar    [33 0.0]
:boolean   []
:error     []

step       9
processing :scalar-swap
:x1        [33]
:x2        []
:exec      []
:scalar    [33 0.0]
:boolean   []
:error     []

step       9
processing
:x1        [33]
:x2        []
:exec      [(33 0.0)]
:scalar    []
:boolean   []
:error     []

step       10
processing (33 0.0)
:x1        [33]
:x2        []
:exec      []
:scalar    []
:boolean   []
:error     []

step       10
processing
:x1        [33]
:x2        []
:exec      [33 0.0]
:scalar    []
:boolean   []
:error     []

step       11
processing 33
:x1        [33]
:x2        []
:exec      [0.0]
:scalar    []
:boolean   []
:error     []

step       11
processing
:x1        [33]
:x2        []
:exec      [0.0]
:scalar    [33]
:boolean   []
:error     []

step       12
processing 0.0
:x1        [33]
:x2        []
:exec      []
:scalar    [33]
:boolean   []
:error     []

step       12
processing
:x1        [33]
:x2        []
:exec      []
:scalar    [0.0 33]
:boolean   []
:error     []

["done"]

OK? I didn’t bother interrupting to ask if you were surprised by the :divide not generating an error, because I trust you saw that coming (and know what we’ll do next). And I didn’t interrupt to mention how :scalar-swap pushed a code block, because I wanted you to watch one way in which the “flipping” can be implemented.

Again, while we don’t need to push the results of every calculation to the :exec stack, it might save you some anguish when you implement some super-fiddly Push instructions that manipulate code blocks. Besides, computers are made to do this sort of shuffling stuff.

There’s another thing you might notice, if you know about genetic programming from other approaches: I’m not playing around with “protected division”, am I? See, in Ye Olden Times, because GP was done with a relatively limited representation language, people started using a special “protected division” which handled every attempt to divide by zero by returning a value. Usually the value returned was 0.0 or 1.0, sometimes it was something else. But really what this was for, in that context, was type consistency. Something downstream “expected” a number, and it would stumble if it didn’t get one, or (if it was based on IEEE standards for floating-point arithmetic) maybe the NaN value would propagate and you’d get some sort of nonsense.

Here, we don’t care. Make a note of it, move along. You can do the same with the square root of a negative number (if you don’t implement a :complex type), or the \(ln(-44)\) or \(tan(\pi/2)\).

Now let me break this program by changing the value of :x1 so it’s also zero, rather than rearranging the instructions.

step       1
processing (:x2 :x1 :divide :x1 :scalar-swap)
:x1        [0.0]
:x2        [0.0]
:exec      []
:scalar    []
:boolean   []
:error     []

... skipping ...

step       5
processing :divide
:x1        [0.0]
:x2        [0.0]
:exec      [:x1 :scalar-swap]
:scalar    [0.0 0.0]
:boolean   []
:error     []

step       5
processing
:x1        [0.0]
:x2        [0.0]
:exec      [:x1 :scalar-swap]
:scalar    []
:boolean   []
:error     ["step 5: divide by zero"]

step       6
processing :x1
:x1        [0.0]
:x2        [0.0]
:exec      [:scalar-swap]
:scalar    []
:boolean   []
:error     ["step 5: divide by zero"]

step       6
processing
:x1        [0.0]
:x2        [0.0]
:exec      [:scalar-swap]
:scalar    [0.0]
:boolean   []
:error     ["step 5: divide by zero"]

step       7
processing :scalar-swap
:x1        [0.0]
:x2        [0.0]
:exec      []
:scalar    [0.0]
:boolean   []
:error     ["step 5: divide by zero"]

step       7
processing
:x1        [0.0]
:x2        [0.0]
:exec      []
:scalar    [0]
:boolean   []
:error     ["step 7: :scalar-swap missing args" "step 5: divide by zero"]

Ah, see, now we have two items on :error. But notice that this program, broken-seeming as it may be with its runtime divide-by-zero error, and its missing-arguments error for :scalar-swap, still “returns” a value. That is, it still has something sitting on the top of the :scalar stack at the end.

That’s interesting and useful, in its way. It may not be what you’d prefer if you were writing Push programs—because “throwing an exception” is a pretty handy way for an interpreter to get your immediate attention so you can intervene as a human overseer—but if you’re evolving them it represents an abrupt nonlinearity of response surface. Avoiding that nonlinear response is one of the useful benefits of all this “robustness” I mentioned above. If (almost) every program “does something”, and you’re trying to capture “good parts” of programs and recombine them in better ones down the line, then Push’s innovative design lets you avoid having a sharp do-or-die threshold for semantic and syntactic rigor getting in the way of the prospect of moving forward.

Imagine what it would be like to take Java code, or Python, or Clojure, and randomly shuffle the tokens in a program. You would be stopped dead by your IDE or your compiler well before you had a chance to discover whether you’d gotten “partial credit” on the task at hand. And “partial credit” is the point.

Fundamentally uncooperative programs

The point of all this is weird robustness in Push is to provide the capacity to run arbitrary code. But there’s still room for “bad behavior” in the language. First (again, in complete Push implementations) there are inevitably some finite-length Push programs that will never run out of things on their :exec stacks, and which therefore don’t “terminate” in the way I’ve implied means “done”. But there are also Push programs that do terminate, in this sense, but which don’t “return” what you asked.

For example, consider the program (:add :scalar-swap :multiply). What does it “do”?

I won’t work it out by hand for you, because I trust you can do that for yourself programmatically by now. There will be three items on :error, and nothing on :scalar at all. Doesn’t matter what we set :x1 and :x2 to be.

If we say that the “return value” for a function is the “top item on the :scalar stack”, then what can we say about the return value of this “function”?

Good question.

One approach, popular among people who evolve functions based on the error values calculated between the observed and expected return values, is to assign a “penalty answer”. This is equivalent to saying something like “if you don’t answer at all, I’ll assume your answer is infinity (or negative infinity, depending on what’s wanted)”. If the folks involved are calculating error as the difference between observed (returned) and expected values, then this simply says the error for those programs that return no answer at all is as bad as possible.

Another, substantially subtler approach might be to define the function you’re looking for as returning an option type, but this may well be kicking the can down the road. How do you compare one program that returns a bad value, and another that returns none at all?

Perhaps those :error items could be a clue? I’ll leave that up to you.

Very Small Push instructions

So let me say I’m more or less done here, and give you a dictionary of Very Small Push instructions to implement, which will probably suffice to model many interesting numerical and logical stuff. I won’t go into how you should consider finding “good” programs for fitting data yet, because that’s a whole different barrel of monkeys. Think of this as a sufficiently-interesting and -informative subset of Push to get you started, without being so limited that you can’t imagine it being “useful”.

• :add: pop two :scalar, push the sum
• :subtract: pop two :scalar, “B” and “A”; push the difference \((A-B)\)
• :divide: pop two :scalar, “B” and “A”; push the quotient \((A \div B)\), or an error if \(B=0\)
• :multiply: pop two :scalar, push the product
• :log10: pop one :scalar, push the logarithm (base 10), or an :error if the value is undefined
• :sine: pop one :scalar, push the sine (treating the argument as radian value)
• :negative: pop one :scalar, push the result of multiplying by \(-1\)
• :greater-than?: pop two :scalar, “B” and “A”; push true if \((A>B)\), false otherwise
• :less-than?: pop two :scalar, “B” and “A”; push true if \((A<B)\), false otherwise
• :equal?: pop two :scalar, “B” and “A”; push true if \((A=B)\), false otherwise
• :min: pop two :scalar, “B” and “A”; the smaller value (taking negative numbers into account)
• :max: pop two :scalar, “B” and “A”; the larger value (taking negative numbers into account)
• :zero?: pop one :scalar, push true if it’s 0.0, false otherwise
• :sign: pop one :scalar, push \(-1\) if it’s negative, \(1\) if it’s greater than zero, and \(0\) if it’s zero
• :positive?: pop one :scalar, push true if it’s greater than zero, false otherwise
• :negative?: pop one :scalar, push true if it’s strictly negative, false otherwise
• :and: pop two :boolean values, and push the logical value \(A\land B\)
• :or: pop two :boolean values, and push the logical value \(A\lor B\)
• :not: pop one :boolean value A, and push the logical value \(\lnot{A}\)

Those you might have expected. Let me suggest you implement a few of the instructions that make Push interesting though. These are examples; you can probably infer some of the other interesting things that might happen.

• :boolean-flip: reverse all the items on the entire :boolean stack
• :boolean-pop: throw away the top item on the :boolean stack
• :scalar-pop: throw away the top item on the :scalar stack
• :scalar-swap: pop B and A from :scalar, and push (B A) onto :exec
• :scalar-dup: pop A from :boolean, and push (A A) onto :exec
• :exec-if: pop a boolean; if it is false, throw away the top item from :exec (if any)
• :scalar-count: push the number of items on the :scalar stack

That’s enough to get you into some interesting situations. You should be able to produce Push code that implements things like:

• Set the constants \(c_y\), \(c_m\) and \(c_d\) to the year, month and day of your birthday. Calculate \(y=c_y + c_m x - c_d x^2\).
• Return the absolute value of \(x\) (not using a :scalar-abs function as such, obviously)
• Build and execute a random program of 100 items, using whatever instructions, literals and variable names you’ve implemented. If you set the variable inputs to new values, does the “return” value (on top of the :scalar stack) change?
• In rough terms, how likely is it for a random program of 100 items to return a constant value? One of the input variables (unchanged)? A constant added to an input variable? Any higher-order polynomial of an input variable besides a constant \(c\), \((x+c)\) or \((c\times x)\)?

Probably next time we should talk about some of the other standard Push types, especially the :code type, and how that can produce much more complex algorithmic behavior.