Changing the idea of type in Push

The Push programming language—which, as a reminder, is not technically designed for people to program in, but rather to be “evolvable” and “robust” so that GP can “program” in it—has some interesting characteristics. As I’ve been watching programs evolve in Lee Spector’s Push system Clojush over the last few days, I’m reminded of some open questions that have bothered me since I started working on my first Nudge interpreter almost a decade ago.

It’s time for me to be finishing up some loose ends in the Klapaucius interpreter, too. Time for a formal release, I think. I’ve been using it to evolve Push programs myself, on the sly and in the background, at the same time I’ve been working on simplifying and modifying and expanding the interpreter itself. Indeed, many of the amendments and extensions I’ve made to the Push language in Klapaucius have come up in response to things I’ve seen happen as I evolve and execute unusual code.

Just what do I want from this variant of the Push language, that the “standard” implementation in Clojush doesn’t provide?

Well, first, I want it to be maintainable and expandable. I’ve tried to minimize the complexity of the code itself, and provide as many hooks as possible for amending and expanding the language. Not just because Clojush is “other people’s code”, but because I’ve watched as folks I know have struggled to work with an old-fashioned ball-of-mud codebase. So for one thing, I’m trying to refactor diligently, in service of people who’ll need to read the code after it’s written.¹

But beyond that, you might say that my core design principle is the evil twin of the one often invoked for the Python language: There should be as many non-obvious ways to do a thing as possible.

There should be at least one kind of recursion, and a few kinds of iteration, and collections and comprehensions, and higher-order functions should emerge from the soil of program execution dynamics like stop-motion mushrooms. There should be ways to easily combine and access parts of objects all over the place. Ways to tuck data away into organized collections, or associate it with arbitrary and abstract functionality into an object-like structure. There should be all kinds of nooks and crannies of cross-reference and data structures and ad hoc complexity available “for free”.

It should be possible, in other words, to look at any Klapaucius-flavored Push program, know that it “works” and does what you wanted it to do… and then say, “Good, now do it again, in a completely different way.”

And without being mean when you say it. It should be possible for the poor search process, the “programmer”. Not a Sisyphean challenge.

That may sounds “ambitious”, if all you’re used to working with is enterprise software or mobile apps, but it’s not about kitchen-sinking the thing for the sake of human programmers. Remember: this is a language for programs that are meant to be evolved. What I’m doing is about the search landscape for arbitrary algorithmic structures, not about “convenience”. I don’t mean these to be “simple” ways of working—the codebase itself should be simple, but it should be capable of expressing deep and confounding complexities.

This makes the struggle a bit more struggly than you’d expect in a normal software library. Over several years, there are a half-dozen design decisions deep down inside the codebase that have seemed reasonable at the time and in themselves, but which after the fact feel as though they’re holding things back.

But I think now I see a way forward.

Today I’m writing in the spirit of (1) “learning in public” and (2) probably overthinking things. In defense of overthinking: it’s stuff about problems I started noticing five or six years back, so you may have a skewed vision of the narrative arc.

But you’re encouraged to skim. This particular piece is more for me, and for the record, and may appeal in parts to colleagues who work actively with the Push language. It’ll be easier, honestly, to look at the docs I write when I finish doing what I’m about to tell you I think maybe I might do soon….

So anyway.

First, I’ve realized that there’s a problem with the way we’ve all been talking and thinking about “type” in Push. I want to know better what we really mean by the word “type”, because it doesn’t seem to be what’s meant in most glib programmers’ sense of the word.

So I want to spend some time talking out loud and rethinking “type” in Push. In a pragmatic sense, “types” are the “edges” representational chunks of the code… but on the one hand, there’s the code we write intentionally to build an interpreter, and on the other hand, the code the interpreter evolves to solve problems based on examples. And on the third hand, there’s the imagined user, somebody who wants to evolve code for a new domain, and is faced with the challenge of tying their extension of Push into both the codebase and the evolutionary dynamics at the same time.

That may sound like a lot of crap. If so, you’re in a good starting place: it is.

“What’s this? What’s this?”

There is a long-standing problem with “types” in Push. I’m gonna keep using the quotes for a while—until we get used to them—and then I’ll try to fix things so I can stop in good conscience.

“Type” pervades the architecture of every extant Push interpreter. Including mine. It’s the thing we say first, whenever we describe the language to a new audience: It’s a “strongly typed” imperative language… &c &c”.

Well, yes.

But also no. I think the notion of “type” in play here has become too closely tied up with our vision of interpreter dynamics, and with our implicit idea of “the flow of code”. To the point where we write our code to suit the notion of “type”, and not the other way around.

As a result, this folk “type” has become self-reinforcing. Everybody Knows you write a Push interpreter like so, because we describe what Push does in terms of what the existing interpreters have done. This is not merely annoying, but is also visibly bad. It keeps most extant versions of Push from being easily extended.

First, because you can do a lot of simple and amusing stuff with the “types” that Push includes from its origins. You can solve a lot of demo problems, you can sort and fiddle strings, you can do arithmetic and manage to iterate a few things. You can do some homework problems… at least in the sense that you can generate code that produces the correct outputs for all inputs.

But code is not merely to be run. It’s necessary for it to be reusable, and preferable that it be at least minimally readable. By “reusable” I don’t mean in what my Computer Scientist friends call disparagingly the “Software Engineering” sense of the phrase; I mean the fucking evolutionary algorithm should at least be able to take pieces of code from one place and use them again later for something else. And while by “readable” I do in fact mean “by me”, that’s not such a high bar since after all I wrote the fucking language interpreter—and oh by the way this is the fifth I’ve made.

I can’t do either of those, yet. It’s not evolving reusable code, and it’s not readable. Not because it can do so much, but because it can do so little.

Push is remarkably expressive, compared to its cousins and ancestors in the GP world. It’s feasible to add “types” that capture the notion of vectors-of-things, for example. And to build suites of hundreds of instructions in a reasonably abstract way that manipulate and transform the relatively primitive types we know from basic language design into something you might use in, for instance, mathematical programming courses.

But it’s a royal pain to think about matrices, or higher-order functions, or key-value pairs. Not because those things are hard to construct, and certainly not because it’s hard to make the interpreter recognize those things and put them on the right stacks. That stuff is easy.

See, the problems arise because Push is also startlingly robust. It’s designed—very, very carefully as it turns out—to avoid almost all of the pitfalls that you can probably imagine you’d see when, say, running a “program” made up of random Java instructions, all stuck into a shuffled collection. Java and Python and Lisp don’t like it when you permute programs; a lot of those permutations will crash something, somewhere.

Push doesn’t care.

That robustness gives you perks: Push programs don’t stop running just because some instruction’s arguments are missing. They never need to allocate big blobs of memory. Hell, the Klapaucius interpreter doesn’t even need to recognize all the tokens you give it to run, and it doesn’t even care if it’s not Push code.

Push is the honey badger of robust execution.

But of course this remarkable robustness comes at a remarkable cost. Like Spider Man says. It’s a pain to add even a simple new Push “type”. It demands a lot of thought and care. Not, as I said above, because recognizing a new thing is hard, but rather because doing anything with that thing is hard. You will be adding instructions that make your new “type” of thing, and which break it down into components.

You’ll be adding instructions that grab arguments from stacks and places you may not even know exist, and you will also be required to make those instructions as robust as the rest of Push already is.

Do you want to add a :matrix type to a Push interpreter you’ve downloaded? Great! That’s made of what? Numbers? Well there may be a :float and an :integer type in the Push interpreter you’ve downloaded. So be sure to add instructions to get and set individual elements of :matrix items, and to build and deconstruct them. Oh, and realize you’ll have to write those to use arbitrary numerical arguments, because when you invoke your new :matrix-from-integers instruction, it will start by wanting to know how big you want, and if you grab the top two numbers from a stack they might be 9e12 and -77, and then what will you do?

Oh, and you want to multiply :matrix items. OK, you realize won’t get to select the arguments for compatibility, right? The instruction must be, in essence, memoryless, and should work with whatever top two :matrix items it’s given. If the matrices are incompatible for multiplication, what will you do? Will you throw them away? Put them back?

And oh! Sometimes when you want to do some linear algebra stuff, you’ll end up with :complex values in a :matrix. If your deconstructor instruction gets a :matrix item that happens to contain a few :complex values, what will happen? Do you want a :real-matrix and :complex-matrix type? Really? Oh wait, I forgot to ask: I said there was a :float and :integer type in the interpreter you downloaded… do you want :real-float-matrix and :real-integer-matrix and :complex-float-matrix and also :complex-integer-matrix types, too?

And so on.

It gets worse. Realize that running random code can sometimes discover programs that “blow up”. The “types” and instructions present in any Push interpreter you download are carefully selected to minimize the amount of “blowing up” that can happen, but it’s ridiculously easy to introduce an innocuous-seeming pair of things that will indirectly throw it all out of whack.

“Blowing up” is bad. When you’re running arbitrary code, you can quickly fill up your working memory, or start a looping process that will take infinite time to do trivial things. All you need to do is miss a place where you add some new code to concatenate a couple of “simple collections”—how could that be a problem?—and then also in a different place maybe you introduce a sort of list comprehension that loops over all the items in one of your fancy new collections.

Now how could those two perfectly reasonable and innocuous things be problematic? Loads of “normal” languages have collections and comprehensions.

Combinatorics can be a mean motherfucker. How about when you stumble across one of your list comprehensions, which applies concatenation to itself? Every Push interpreter has been rigorously tested and pruned of that kind of “blow up” crap, before you got there. And so when you add your domain-specific stuff, you will also need the same ridiculous degree of rigor. As Dr. Malcolm says, “[Evolution], uh, finds a way.”

That may not sound like it’s about “type”, but it is.

Push “type”, as it is

Here’s how we have used “type” in Push, to date.

First, “type” is about how program items are recognized and routed by the interpreter.

A Push program is an ordered collection of items. The items can be (1) code blocks, (2) instructions, (3) variable names (or “references”), and (4) “literal items” of various distinct types.

The program is itself a code block.

When a new Push interpreter begins running a program, the first thing it does is push the whole code block of the program onto a “special” stack called :exec.² That is, the entire program—the whole collection—is pushed onto that stack, as one item on the stack.

But the stack itself doesn’t “have a type”. We don’t say the “type” of :exec is “code block” or “push item”.

Because of the way we’ve defined the Push interpreter dynamics, we tend (if anything) to say :exec is “special” compared to other stack. Who knows? it may not have a type. Or maybe its type is… some kind of “root” type. Maybe :code?

Maybe we’ll come back to :code in a while.

Then, once the program is on the :exec stack as a single item, and possibly after some other setup has been done (such as associating initial values with variable names), the interpreter will begin executing the program. It does that by popping the top item, from the :exec stack, and doing something to it.

What the interpreter does depends on what the “type” of the item happens to be.

If the top item from :exec is a code block—like the program is, at the start—then the interpreter will put all its contents back onto the :exec stack, in the same order. So if the program is (1 2 false), then the first steps of the interpreter running that program will look something like this, where I’m placing the “top” of the stack at the left for convenience on the page:

;; step -1
;; before running, all stacks are empty
:exec []

;; step 0
;; program setup
:exec [(1 2 false)]

;; step 1
;; pop code block, "unwrap" it
:exec [1 2 false]

In each step of execution, the interpreter pops one item from :exec, inspects it, and “does the right thing” based on its type.

For a code block, “the right thing” is “put the stuff inside onto :exec, in this order”. For a literal item (like a number or a boolean value), “the right thing” will be to push the item onto some type-specific stack.

Let’s finish that program, and you’ll see.

All Push implementations define a core set of recognized literal “types”. These are what you might call the junk “obvious to one skilled in the art”: numbers like “integer” and “floating-point value”, and “boolean” and “string”. You know, primitive types like you’re used to from the 1970s.

As a rule, Push is designed to handle those in the simplest possible way. For each recognized literal type like that, the interpreter will have a type-specific stack to which it will push that item, when it’s popped off of the :exec stack.

So let’s return to our friend (1 2 false). I’ll back up a bit, and add some missing stack names to help clarify what happens.

;; step -1
;; before running, all stacks are empty
:exec    []
:integer []
:boolean []

;; step 0
;; program setup
:exec    [(1 2 false)]
:integer []
:boolean []

;; step 1
;; pop code block, "unwrap" it
:exec    [1 2 false]
:integer []
:boolean []

;; step 2
;; pop 1, push to :integer
:exec    [2 false]
:integer [1]
:boolean []

;; step 3
;; pop 2, push to :integer
:exec    [false]
:integer [2 1]
:boolean []

;; step 4
;; pop false, push to :boolean
:exec    []
:integer [2 1]
:boolean [false]

;; done, because :exec is empty

Note that somewhere back before we arrived, somebody has “told” this Push interpreter that things that look like integers should be sent to :integer, and things that look like boolean values should go to :boolean. This is about as fancy as the basic Push literal types get. When you see it, and you recognize it, it goes onto the previously-assigned type-specific stack.

This is ridiculously boring and useless, of course. In itself.

However, there are two other broad “kinds of thing” that can occur in Push programs. Strangely, we don’t generally speak of them as “typed” in the same sense as literal items or even code blocks, which is one of the reasons I’ve salted this whole paragraph with scare quotes.

I’m talking here about variable references and instructions. There’s a lot going on in these two cases, so let me walk through them both carefully.

Now a “variable reference” is an ill-defined concept in Push. There’s been very little standardization over time, and the notion is left out of some implementations entirely. In Push3, which is perhaps the last “well-documented” Push language specification, variable references were called :name items, and they were intended as a way of passing in arguments, and also for permitting code reuse.

The idea is that a special subset of tokens, perhaps keywords like the ones I’ve been using for types and instructions, can be assigned values. When the interpreter encounters one of these special references, it looks up the associated value and pushes that to the :exec stack.

So for example, if it happened that the name :foo had been assigned a value of 99, then whenever :foo has been popped by the interpreter from the :exec stack when running the Push program, a 99 will appear “in its place” in the next step.

Let me step past the problem of how things get bound to :name items for the moment. Instead, let’s walk through a variant of our friendly Push program, but this time I’ll also define an item :foo to have the value 99, and run a program (1 :foo false).

;; step -1
;; before running, all stacks are empty
:exec    []
:integer []
:boolean []

;; step 0
;; program setup, and also bind `:foo` -> `99`
:exec    [(1 :foo false)]
:integer []
:boolean []
:foo     99

;; step 1
;; pop code block, "unwrap" it
:exec    [1 :foo false]
:integer []
:boolean []
:foo     99

;; step 2
;; pop 1, push to :integer
:exec    [:foo false]
:integer [1]
:boolean []
:foo     99

;; step 3
;; pop :foo, push 99 to :exec
:exec    [99 false]
:integer [1]
:boolean []
:foo     99

;; step 4
;; pop 99, push to :integer
:exec    [false]
:integer [99 1]
:boolean []
:foo     99

;; step 5
;; pop false, push to :boolean
:exec    []
:integer [99 1]
:boolean [false]
:foo     99

;; done

Notice that :foo—at least in this Push3 idiom—isn’t quite like the :exec and :integer stacks. It’s got a single value associated with it, not an ordered collection.

In my Klapaucius interpreter, I’ve made a half-way reconciliation of this difference between variables and stacks. First, I’ve started calling this thing we use to hold items a :binding, and I call the thing that refers to it a :ref. But more importantly, a K-Push binding holds a stack of items, not just one value.

So in K-Push, when the interpreter encounters a :ref like :foo, it peeks at the top item on the stack associated with :foo, and pushes a copy of that item to :exec. There are justifications for this approach, because it seems to make K-Push more evolvable and robust, but for now… In K-Push, an analogous program would run something like this:

;; step -1
;; before running, all stacks are empty
:exec    []
:scalar  []
:boolean []

;; step 0
;; program setup, bind `:foo` -> `99`
:exec    [(1 :foo false)]
:scalar  []
:boolean []
:foo     [99]

;; step 1
;; pop code block, "unwrap" it
:exec    [1 :foo false]
:scalar  []
:boolean []
:foo     [99]

;; step 2
;; pop 1, push to :scalar
:exec    [:foo false]
:scalar  [1]
:boolean []
:foo     [99]

;; step 3
;; pop :foo, push 99 (top of :foo) to :exec
:exec    [99 false]
:scalar  [1]
:boolean []
:foo     [99]

;; step 4
;; pop 99, push to :scalar
:exec    [false]
:scalar  [99 1]
:boolean []
:foo     [99]

;; step 5
;; pop false, push to :boolean
:exec    []
:scalar  [99 1]
:boolean [false]
:foo     [99]

;; done

A few things to notice in this K-Push version. First, is no :integer stack, but rather a :scalar stack. It’s a design difference that’s not really salient here, in which I combined the “types” :float and :integer into a single scalar numeric “type”.

The point I want to emphasize is that :foo—the binding and the stack—doesn’t have a “type” in the same sense as :scalar seems to. That was actually true of :name items in Push3, as well: it was assumed that any Push item (a code block, an instruction, a literal value or even another :name) could be associated with a variable binding.

So somehow we seem to have ended up with “untyped” variables, but “typed” stacks. That’s got a smell to it.

Finally, notice that this is still super boring. Seriously, this program does nothing, except look stuff up and sort it all into various piles.

Yay, I guess?

The problem of instructions

Of course that would be silly. There is one more sort of Push item that can appear in a program: an instruction. When the item popped from the :exec stack happens to be an instruction, then the interpreter… well, a lot can happen.

Push instructions are the rug under which all of us involved in developing Push seem to have swept all the real complexity of computation.

When the Push interpreter encounters an instruction, the (interpreter, not Push) code associated with that instruction is executed immediately. So for instance, when an instruction is encountered that “means” something like “cast an integer into a string”, the interpreter will try to pop an :integer item from the top of that stack, and will push the resulting :string item onto that stack.

For a long time, we’ve spoken of what happens whenever the interpreter encounters an instruction as being “like” calling a function. The instruction “has arguments”, and it probably “produces results”. Insofar as those things are usually valid Push items themselves (code blocks, variable names, instructions or literals), then you may be tempted to think of Push instructions as having “type signatures”.

Turns out that would be risky. Let me emphasize one crucial aspect that may not be obvious from here: The interpreter isn’t passing arguments to an instruction as if it were a function, nor is it receiving the results of executing its code. Rather, the instruction’s code is itself taking what arguments it needs, and then putting its results in various places. Instructions are less like functions, in practice, than they are imperative state-changing subroutines.

It turns out that will be super important. Keep it in mind as we move ahead.

Let’s walk through a few basic Push3 and Clojush instructions.

A very simple one is 'boolean_and, to use its Clojush name.

When the interpreter encounters this token, a remarkable amount of stuff happens:

1. It checks, and if there aren’t two or more items on the :boolean stack, then execution ceases, leaving the :boolean stack unchanged.
2. If there are two or more items on the :boolean stack, then
   1. the instruction code pops those items (call them p and q)
   2. it calculates (and p q)
   3. the instruction code pushes the result onto the :boolean stack.

You may not think that’s a lot of work. Also, you might be thinking how obvious it is that the “type” of this instruction is :boolean. Or if you’re a functional programmer sort of person maybe you’re fancy and thinking maybe it’s "[:boolean,:boolean]->:boolean"; that is, that it “consumes” two :boolean items and makes one new one. Or maybe if you’re comfy with conditional type systems, you’re thinking of something involving question marks and nil return values and….

And now maybe you’re frowning just a little, yes?

You should definitely frown a little when I remind you: The instruction is not receiving these two :boolean things, or returning a :boolean thing. It is taking those two :boolean things, and then putting the new :boolean thing.

Let’s do another basic one. How about 'integer_divide? Here’s how it’s implemented in Clojush:

1. If there aren’t two or more items on the :integer stack, it does nothing (leaving that stack unchanged).
2. If there are two or more items on the :integer stack, it:
   1. pops those items (call them b and a for the top and second items, respectively);
   2. unless b is zero, it produces an (internal) result of (/ a b); otherwise it produces no result;
   3. pushes this result onto the :integer stack.

Well, clearly that’s a lot like :boolean_and, in that it…well, often consumes two :integer items, and… often produces a new :integer.

But this time, I guess, it can consume arguments and not produce a result. Hmm….

Or how about one of the numerous and distinctive combinators Push code depends upon? How about :boolean_yank? It’s one of my favorites, and it’s always “fun” [sic] to implement. Here’s the Clojush implementation, more or less:³

1. If there are no items on the :integer stack, it does nothing (leaving all stacks unchanged).
2. If there is at least one item on the :integer stack, then:
   1. it pops the top item from :integer;
   2. it counts the items on the :boolean stack;
   3. it transforms the number it’s grabbed into an index over the :boolean stack, typically by truncating it to fall in the range [0,stack depth);
   4. it peeks at the item indexed at that position on the :boolean stack, and it removes it from the stack, and pushes it back onto the top of the stack; if the :boolean stack is empty, it remains empty.

So here, we will always consume an :integer. Then we’re going to move the nth item of the :boolean stack from its current position up to the top. But the :integer, since it’s arbitrary, might be negative or gigantic compared to the number of items in our :boolean stack, so before it can be considered an “index” we have to bring down to scale. Also, the :boolean stack might be empty! But even if it’s not empty, we don’t know before we get here how many :boolean items we need to “consume”, and so we’re just going to talk about this as if the code were able to do brain surgery directly on the entire stack.

Now try your fancy type signature stuff on this one, Miss Functional Programmer. The instruction consumes one :integer and “some” :boolean items. Or perhaps we should say it consume all the :boolean items, because I can’t know ahead of runtime how many we’ll need to move around.

But… what’s the type signature of a “function” that takes as an argument “all the :boolean items”? It doesn’t feel as if instructions are very good at being functions of their “little arguments”, does it? If they’re functions at all, then they feel much more like they take one argument—an entire interpreter—and transform that in place.

They’re starting to feel much more like instance methods of the interpreter object, aren’t they?

Those are three simple Push instructions. They’re easy to describe, especially of you’re not too careful about it. You can glibly say to somebody, “do boolean and on the top two items of that stack”, or “divide the top two :integer items (in reverse order), but only return a result if you get a number”, or “take the top :integer, and use it to move an item in the :boolean stack”.

But you’d be eliding a few things.

One of the great insights that has made Push so interesting and useful is its core notion of implicitly wrapping every instruction in a try block. For every instruction, if any arguments are missing, then no arguments are consumed, and no result is produced. That appears as the “if there are at least N items on the X stack, then” clause in each of the instructions I’ve described so far.

But notice that we talk about “an item from a stack” as a kind of thing, but that sometimes an instruction can affect “a stack full of items”. And that we pepper our definitions with conditional execution, some of which we cannot handle before runtime (as when dividing by zero).

Let me share one more basic Push instruction.

This version is from Push3, and has an analogous version in Klapaucius; for various historical reasons it doesn’t exist in Clojush. It’s called 'NAME.QUOTE in Push3, and :push-quoterefs in Klapaucius.

And it’s even easier to describe than the ones above:

1. Set the interpreter’s quote-refs? flag to true.

That’s it! It isn’t even a “toggle the flag” sort of thing. The global interpreter flag is set to true every time this instruction is encountered.

But wait, you should say. What does the interpreter’s quote-refs? flag do?

Ah. So, do you remember when we executed the program (1 :foo false) above, and we got to the :name (or :ref) :foo in the program? I said that the interpreter responds to this sort of variable name item by looking up its bound value and pushing that onto the :exec stack?

That’s only true if the :quote-refs? flag is false.

Whenever that flag is set to true instead, then the interpreter doesn’t look up the values associated with a :ref. Instead, it will push the variable name directly to a stack called :name (in Push3) or :ref (in Klapaucius). As long as the flag remains set to true, then variables will never be “looked up” at all. Instead, every reference will be piled up on another “special” stack.

What’s the type signature for this instruction? That is, if you want to think of instructions as “functions” with a “type signature”. After all, it affects the global state of the interpreter itself. It has no arguments from stacks, and it returns no argument to a stack.

Much more like an instance method.

The Push type cluster headache

Here’s a web of related problems:

• The Push interpreter is said to send items to stacks based on those items’ “type”… except when it doesn’t. There are actually several places in even basic Push interpreters where (for example) a code block is sent to :code instead of being unwrapped to :exec, or a :ref is sent directly to the :ref stack instead of being looked up. There’s state and contingency all over the place.
• There are several “special” stacks (:exec, :code, :print, :output and others) which don’t ever get literal items routed to them by the interpreter. Rather, special-purpose instructions push things to directly to these stacks in the course of execution. Is the “type” of :print a… “print thing”?
• There’s something deeply worrying about my K-Push “bindings”. They’re stacks, but they can “contain” any Push item at all. As opposed to the standard “type stacks”, which are also stacks, but which by convention only contain one “type” of thing. If a “type stack” like :boolean contained the wrong kind of thing (like a :string), then probably some instruction would cause a runtime error down the road. And we don’t want any runtime errors. Ever. But when a binding contains random push items, we don’t need to worry. Somehow.
• The act of pushing a thing to a stack rarely if ever involves “checking” its type. It’s a matter of imperative action by the interpreter routing, or by the stuff happening inside instructions’ internal definitions. As a result, there’s just an increasingly-rickety mesh of “consistent usage” among all the instructions and stacks and types.
• Similarly, the act of pushing a thing to a stack needs (because of “blowing up” in the ways I mentioned above) to sometimes check how big that new thing is. And that’s hard to centralize, because even if you decide to limit the amount of memory used to store stack items, a stack full of :mp4 items and a stack full of :boolean items will probably want to have different size limits.

• The “type signature of an instruction” is painfully difficult to capture. Indeed, Push instructions have ended up being much more like Forth commands:

  Forth does not enforce consistency of data type usage; it is the programmer’s responsibility to use appropriate operators to fetch and store values or perform other operations on data.

  This is even worse when we start to consider the “type signature of a code block”, which one wants to be able to speak about (because of higher-order and abstract functions), but which can quickly become a headache.

• There are “types” in here that aren’t accessible, except from deep inside the instructions that use them. For instance, all the combinator instructions work exactly the same way on every stack they are applied to, but there’s no notion in Push of “accepting a stack as an argument, and producing a stack”. Similarly, there are a number of crucial instructions that read or affect global interpreter state. This may seem like niggling over slight sloppiness, but again the notions of partial application and higher-order functions are unreachable as long we let these things do whatever they want with whatever chunks of their host interpreter they want.
• I haven’t even told you about the ways :binding and :ref items get made in Klapaucius, or how :name items get made in Push3. This involves a kind of global key-value store “up in the interpreter” somewhere, and changes made there affect the future behavior of the interpreter the next time a given keyword is processed. Some instructions read and write this core chunk of interpreter state. Again, they’re much more like instance methods not functions.
• It may seem more productive to just say “all instructions accept the whole interpreter as an argument, and return an updated interpreter”, but this elides all the work “type” does in the way we frame Push programs. It doesn’t help, in other words.
• It may seem more productive to just say “an interpreter is an instance, and instructions are instance methods that change its state”… but that throws away the sense that these instructions are consistently “about” manipulating certain “types” of stuff on stacks. It’s like saying that all biological molecules are made of atoms; it doesn’t help describe their function.
• It’s onerous for a developer to add a new “type” that interacts in any reasonable way with the other types. Sure, you can add a stack and a recognizer to the core interpreter, and suddenly have a :color stack and a :color router to send literals to that stack. But your instructions will want to build :color out of some numerical values, or maybe some :string items, or maybe break them down into parts, and maybe talk about vectors and arrays and collections of :color items (like pixels), and at every interface between your new :color and some other “type” you need to build a mesh of enough interoperability.

This last one has an especially wry anecdote associated with it. Tom Helmuth added a variety of :vector_of_x types to the Clojush interpreter to do some of his thesis work. But for a long time he neglected to add any instructions that created :vector items from their component parts. So these instructions only ever appeared in programs where you had given it some literal values, maybe as a :vector valued argument.

There’s more that I’ve missed. For more than a year I’ve been accumulating GitHub issues that seem to return to these problems with type definitions in Push. I haven’t even touched on the ways our assumptions about “type” affects the evolvability and flexibility of Push programs and the dynamics of search itself.

If only I could make it a bit more consistent, and simplify some of these rough corners, I have a sense things would be easier.

Making it all a bit easier

I’m out on a limb, because I’m going to write down my thoughts here before I implement them. Not as a justification of what probably sounds like a “big plan”, but as a roadmap for myself. Maybe just as something I can point back to, and we can laugh about, when the whole thing drives me off the cliff.

So let me talk about the updated type system in Klapaucius, which I have not yet written.

I am Not a Computer Sciencer™, so I may be describing something trivial. It may not be well-considered or well-framed. Or it might turn out to be theoretically intractable.

Don’t care! because I’m trying to solve a problem of my own user experience. Well, for now I am the user; in the future it will hopefully be some of you poor souls. And my experience is “it’s still not robust enough against mistakes made by people adding types and instructions and evolution fucking around with it all”.

But see: I think I know a way to fix it.

“Push onto stack” should be “optimistic send”

Most of the weird stuff that Push does—as opposed to, for example, Forth—is aimed at ensuring the arguments you collect won’t cause a runtime error by being the wrong type inside the code executed when an instruction is processed. Sorting things into stacks feels boring as dirt, until the day you happen to reach blindly into the box marked “numbers” and pull out a string literal.

Remember: nobody wrote the Push program we’re running. But somebody—possibly somebody naive, or not especially careful, or maybe even some other code—wrote the instructions in the program you’re running, which are being executed by the poor over-worked Push interpreter.

Some instructions pop their arguments from named stacks, and then push their results to (possibly different) named stacks. Some other instructions consume whole stacks as their arguments, and replace those stacks with new versions. Some other instructions affect the interpreter state directly, as in setting a flag value or doing some introspection.

But here’s one thing I think we can do to reduce the risk of finding the wrong type of thing on a stack where it’s expected:

Old: Whenever an item is popped from a stack or binding (inside an instruction definition), its type is not checked. When an item is pushed to a stack or binding, its type is not checked, but its size is checked by a centralized size-checker.

New: Whenever an item is popped from a stack or binding, its type is not checked. When an item is sent to a stack or binding, that stack knows (1) how to recognize things it will accept, (2) one or more “parent” addresses to which it will send things it doesn’t accept, (3) its current size, (4) the size it would be if it added the item sent, and (5) what to do if a thing would make it too big.

Notice, though, that a stack and a binding still won’t “have a type” in this scheme. Rather they will “have a type recognizer” or “filter”, and also an association with one or more other stacks or bindings where they will send things they don’t immediately recognize.

In Klapaucius there are both :scalar and :complex numeric types. Suppose I have -3 in the :scalar stack, and I execute a :scalar-sqrt instruction.

As written now, that instruction will return either a :scalar (if the argument is non-negative) or a :complex (if the argument is negative). The logic of the instruction now is “put the square root onto :scalar if the argument is non-negative, otherwise put this other thing onto :complex”.

By making this change in routing behavior, that instruction can be simplified to read more like “calculate the result (either a :scalar or :complex) and send it to :scalar”. The :scalar stack itself is (we will have to know) a subtype of :complex, and so any :complex values we send there will end up bumped to :complex.

When a number arrives at :scalar, we will now always check (1) if it’s recognized by the :scalar recognizer, and then (2) whether it will fit. If it’s not recognized, then it will be sent to the parents of :scalar, which are (probably) :complex. Right?

What if some poor novice writes a new instruction that tries to send a :string item to the :scalar stack? Well, it’ll bounce to :complex, but it’s not a number, so that will bounce it to the generic ancestor stack: :code.

Needless to say, the graph of “parent types” needs to avoid loops. But in general we can say that the ultimate ancestor of all “stack types” (that is, all items that might end up in a program, or be produced as a result of an instruction) will be :code. Even “unknown items” can safely end up as :code.

Everything is :code, and :code is everything.

Variables can be typed

It becomes feasible to have “typed variables”, not just untyped ones.

Old: Bindings will all accept arbitrary Push items as their assigned values.

New: Because a binding is a stack with a recognizer predicate and a parent, then every new :binding has the potential can be created with a specific type filter. This permits a particular binding to more easily end up containing “a collection of integers” or “square matrices”, for example.

The parent of any :binding is :exec, rather than :code as it is for the standard stacks. That means that items sent to a :binding that are incompatible with its filter will be bounced to :exec, and then re-routed to a type-correct location by the interpreter router.

Several distinct forms of “routing”

There are some quirks and oddities that have cropped up through the years of building Klapaucius. Each type has an associated :target-stack. But because of the weirdly diffuse responsibility for “being a type” that’s developed, many core Push concepts are not types, but are rather “modules”.

For example, :exec has been built as one of these modules, because there’s no reason for the interpreter to ever “recognize an :exec item”, but there are nonetheless many instructions associated with manipulating :exec items. So the :exec module is “like” a type, but it has no :recognizer used by the interpreter to “send” things to the :exec stack.

In another weird case, there is the problem of handling :code items. In Clojush and earlier interpreters, push items only ever appear on the :code stack when an instruction has put them there. In K-Push, there is an explicit QuotedCode type, which acts like the quote wrapper in Lisp languages: as a wrapper around code that makes it manipulable as such, rather than permitting execution. When a QuotedCode item appears on the :exec stack—whether it arrived in the original program, or was placed there by an instruction—it’s recognized by the interpreter (since it’s a distinct “type”), and the type router for these :quoted items stores a defined “preprocessor” which unquotes them, and then that code is pushed to the :code stack.

This doesn’t subvert the Push idiom of permitting instructions to push anything to :code they want. Rather it permits certain instructions to manipulate code by reference, via the :exec stack.

Old: When the core :exec interpreter cycle recognizes a thing, it uses the router structure associated with its PushType definition. The :router predicate is used for identification, and if it fires the interpreter first applies the defined :preprocessor transformation (if any is defined), and then pushes the result—actively—onto the specified :target-stack. The :router structure of each defined type contains this information. But when an item is created as the result of an instruction, it is pushed directly onto a specified stack or into a binding that’s explicitly specified by the instruction code, without applying any preprocessor or considering the :target-stack specified.

New: The core :exec interpreter cycle will still have to maintain a collection of serially-applied :recognizer and :route pairs. And these may still apply the :preprocessor function, which seems as if it will be useful for several things. However, instead of actively pushing an item onto its :target-stack, they will be “sent” to the receiving stack for processing. Each stack (and binding) will also apply its :recognizer predicate to items it receives from either the core router or an instruction—though not as a collection in series, like the core router, but as a single predicate function—and will not apply a preprocessor. If the :recognizer fails to recognize a received item, it will be forwarded to a specified “parent” address.

More

There’s more. I’ll write about this “more”, shortly. It will involve real “type signatures” of instructions and ad hoc functions. It’ll permit higher-order functions like mapping. It may even simplify defining structural types a lot.

It feels like a good idea. More shortly, possibly in the form of working code and documentation.