# A Very Small Push

Draft of 2017.12.10

May include: genetic programming ↙ Push ↘ &c.

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.^{1}

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

- literal values of some known type
- variable names
- instruction names
- 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:

- clear all the stacks and bindings
- assign argument values to
`:x1`

and`:x2`

bindings - place the program onto the
`:exec`

stack - 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.^{2} 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:

- The top item is popped off of
`:exec`

. - If the item is a variable binding, then the current value of that variable is looked up and pushed back onto
`:exec`

. - If the item is an instruction name, then the instruction is immediately
*executed*(more on this below). - 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.
- 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 theirsumonto`: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.