klapaucius

A clean, tested, maintainable Push interpreter written in Clojure.

This project is maintained by Vaguery

The Klapaucius Push interpreter

This is the core documentation site for the Klapaucius interpreter, written in Clojure.

The Push language

Push is a stack-based language invented by Lee Spector, Maarten Keijzer and their colleagues. It’s a very peculiar language, with a lot of features that will seem unfamiliar and even off-putting to modern programmers, because it’s not intended to be used by human programmers.

Rather, Push (and the many variations that have cropped up through the years) is intended as a representation framework for automatically generated code, especially (but not exclusively) that the sort produced by genetic programming.

Nonetheless, Push is a simple, extensible programming paradigm. It’s easily extended for domain-specific problems, and beyond a few deep quirks that make it more robust under the sort of syntax-destroying transformations that happen in the course of automated code generation, it tends to be much more readable than many counterparts you’ll see in tree-based, Cartesian, grammatical and other genetic programming paradigms.

The Klapaucius Push dialect

In building this particular Push interpreter for my own genetic programming work, I’ve designed it to be more readily extended than most. As a result, there are features of both the underlying Clojure codebase and the way the library has been and is intended to be extended that will affect the user experience. I’ll go into much more detail in the individual documentation below, but the core features that set Klapaucius apart from other Push interpreter implementations are:

  1. The PushDSL for writing instructions: Push is fundamentally a collection of imperative instructions, executed serially, which affect the global state of a large collection of type-based stacks. In Klapaucius, these instructions are written in a specially-designed domain-specific language, using a small vocabulary of about two dozen Clojure functions. These DSL functions, or “steps”, make the composition of new instructions easier and also more formal, but they have the added benefit of permitting the Interpreter itself to collapse arbitrary collections of Push instructions and literals into higher-order functions. As a result, evolved Push code build in Klapaucius has the ability to discover abstracted and reusable code more easily than its peers.
  2. Robust indexing: One of the fundamental programming tasks that has traditionally been very difficult for genetic programming to work with is the use of collections and iteration. In the Klapaucius Push dialect, there are lots of collections: arbitrary :code blocks, :vector ordered collections of various types, unordered :set collections, ordered :strings composed of characters, the indexed key-value :tagspace collection type, :binding stacks, and the central stacks on which code is manipulated during execution. Code that wants to read or manipulate individual components of these collections is often dependent on fiddly integer-based ordinal indexing, and can become a weak spot for automated code generation. Here, we can use arbitrary scalar values to index the contents of collections. Not just positive integers but any floating-point, rational, and even negative or infinite values can be used to reference individual items in finite-sized collections, using a consistent approximate modulo indexing approach that all collections share.
  3. Flexible data structure composition and templating: TBD
  4. Introspection: TBD
  5. Size limits: TBD
  6. Surfaced error-handling: There’s a long tradition in genetic programming to use “runtime safe” variants of otherwise “risky” operations, like “protected division” that will produce a “safe” 0 result when some random code being executed attempts to divide by zero. Here, I’ve taken a more instructive approach with these low-level risky functions. Instead of emitting a “fake” result and barreling on, Klapaucius programs that attempt to divide by zero or take the arcsin(88) will produce an :error result instead of the “expected” numeric result. As :error messages accumulate in the read-only :error stack, evolved code has the opportunity to interrogate that stack, and potentially to “learn” from earlier missteps.
  7. The Halting Problem: TBD

Interpreter behavior

Stacks and instructions

Basic Push syntax

Types and modules

Numeric

Other basics

Collections

Programming

Non-type stacks

Interpreter states

Arguments and return values

Special instructions

Errors

Program termination

Extending the language

Type, module or both?

Designing new instructions

The Push DSL

Stress-testing your libraries