[Push] Push version 2 development notes

[Lee Spector]

Push list people et al.,

Chris Perry and I have been working on a specification for an official
"version 2" of the Push programming language and I wanted to run some of
the ideas by people who have had (or may soon have) some connection to the
project to solicit opinions.

Several versions/implementations of Push have now been written, by
different people and for different purposes. There is a lot of variation
among the existing versions, and while that's okay in many respects it
would be nice to have a somewhat definitive standard against which things
can be compared. The specification in the Genetic Programming and Evolvable
Machines article has served as such a standard so far, but as Chris and I
discussed a new implementation that he is writing (in C++, for graphics
work he is doing AND for a new Push interpreter for the BREVE simulation
environment) we decided that it was time for a new, refined standard. The
old standard included several experimental features that no longer seem to
be essential, along with several things that were included mainly because
they were easy to include in the Lisp implementation (and because I
thought, "why not?").

Our current thinking is that we should define a language "core" that
includes mostly just essential stuff, along with a standardized
library-based way of specifying additions (including both additional types
and instructions). We haven't yet worked out the details of how the library
mechanism will work (e.g., how the user will specify the interpreter
configuration) -- we're currently working on defining the core, though
we're trying to do so in a way that will allow for a simple cross-version
library/configuration scheme.

The biggest planned change, which some people have already made in their
own versions, is to drop the TYPE type and the instruction overloading that
this permitted. This seemed like a neat feature when I first wrote Push, as
it was vaguely similar to hierarchical class specification in OOP, but it
was also awkward in several ways. It requires many TYPE literals to be
included in most programs and it more-or-less requires the TYPE stack to be
handled in a unique way (consulted but not popped for almost all
instruction executions -- unless we require even more TYPE literals to be
included in most programs). The TYPE stack also tends to grow without
bound. The benefits of the TYPE type were of two sorts: 1) the inheritance
mechanism made it easy to add new types to the language, and 2) the
overloading could in some cases be used to advantage, for example by
allowing the same chunk of code to work for both integers and floats simply
by changing an initial type literal. However, #1 can be obtained in other
ways (e.g. template-like mechanisms) and it's not clear that #2 was really
very useful in very many situations. So we're planning to drop the TYPE
type. Do any of you think we'll be losing anything that I've overlooked by
doing this?

The types that we currently intend to include in the core are just CODE,
INTEGER, BOOLEAN, and NAME. I expect initial libraries to add FLOAT,
VECTOR, and CHILD (and other code-like expression stacks), as these are
types we'll need right away for our own work. A template-like mechanism
will help to create versions of instructions for many or all types, and
these will end up with names that look like "INTEGER.DUP".

I am including below our current working notes on the details of the core
instructions, etc. They're a little terse, but I hope that they're
sufficient to give you an idea of the direction in which we're headed. If
you have any thoughts on any of this please let us know, but please also
respond to the list so that others can join the discussion. We're hoping to
have a written standard and a new C++-based implementation around the end
of the summer or shortly thereafter.

One other thing that we ought to standardize is the representation of
literals (e.g., whether NAMEs must have particular leading characters, how
a vector literal appears in a program, etc.). We haven't yet written this
up.

BTW, I've put up a web page on our GECCO-2003 push-related work, at
http://hampshire.edu/lspector/gecco2003-collective.html. This includes work
in the BREVE simulation environment using the Push plugin, and the web page
has links to some pretty movies...

Thanks in advance for any input on the specification notes (below).

 -Lee


-----------------------------------------------------------------------------

Push language specification, version 2
Notes
Lee Spector and Chris Perry, July 2003

-------------------------------------
-- core types
CODE
INTEGER
BOOLEAN
NAME

--- core instructions

-- TYPELESS:
NOOP

-- FOR ALL TYPES (named like "INTEGER.DUP"):
DUP
POP
SWAP
=
SET
GET
YANK (same as old PULL, but index is clamped rather than modding)
YANKDUP (same as old PULLDUP, but index is clamped rather than modding)
SHOVE (inverse of YANK)
RAND
STACKDEPTH

-- CONVERSIONS:
NONE! (but various instructions push values of one type based on args of
another)

-- CODE:
--- minimal:
QUOTE
ATOM (pushes T or NIL to boolean stack)
CAR
CDR
CONS
INSTRUCTIONS
DO*
IF
--- additional:
LIST
APPEND
NTH
NTHCDR
MEMBER
POSITION (pushes an integer)
CONTAINS (pushes a boolean)
INSERT (takes an integer index)
EXTRACT (takes an integer index)
LENGTH (pushes an integer)
SIZE (pushes an integer)
DO
---

-- INTEGER:
+
-
*
/
% (that's mod)
>
<

-- BOOLEAN:
AND
OR
NOT

-- NAME:
RANDBOUNDNAME (push on name stack one name that already has a binding)


--- parameters:
random seeds (how many depends on random number generator... let's
              make this a list of numbers and worry about possibly
              standardizing it later)
max-points-in-program
max-points-in-random-expressions
random-int-range
new-ephemeral-random-name-probability (probability, when the ephemeral
              random name constant is chosen during code generation,
              that a NEW name will be generated -- in other cases
              a previously-generated name will be returned)
ephemeral-random-constant-generators (there will be a generator for
              each type, but the config has to say which ones are active)
evalpush-limit (max points executed in a single top-level interpreter
call)
initial-names (names (for variables) to to include in the
               initial instruction set)

------------- callback api


------------- config
parameters
types
instructions
ephemeral constant ranges
[rand ranges (same as above)]
initial stacks contents
initial bindings
--
Lee Spector
Dean, School of Cognitive Science
Associate Professor of Computer Science    lspector at hampshire.edu
Cognitive Science, Hampshire College       http://hampshire.edu/lspector/
Amherst, MA 01002                          413-559-5352, Fax: 413-559-5438