Archive for the 'Uncategorized' Category

Function calls and the ENV concept

Tuesday, March 15th, 2011

This message in response to a request from Lee to try to explain what the ENV concept was and how it relates to function isolation in Push.

The concept is really simply and relies upon a single observation: given a push program and its current state (i.e., the states of the stacks), can we construct a program that, when run on an ’empty’ interpreter (an environment, ENV), will reproduce the exact state of the running program. This is possible.

Suppose you execute a program ( CODE.QUOTE (a b) 1 2 + 3 *), and everything before the ‘*’ sign has executed. If we want to describe what is going on we can say something like:

The INT stack contains a 3 followed by a 3

The Code stack contains the program (a b)

The EXEC stack contains the single instruction ‘*’

We could however also say that the ENV is described by the program

(  3 3 CODE.QUOTE (a b) * )

[Updated 19th March, the code above had a plus where it should be multiplication]

Which effectively, when run in a clean environment, will reconstruct the original situation. It’s not that hard to create a program like this from within any given interpreter (and it’s a great way to achieve persistence, serialization, etc.).

I’ve always taken this method of creating a program out of an environment to be the ideal return value of a function call. This has lead me to define a function call in Push3 as follows.

  1. ENV.DO will take the top of the code stack and start running this piece of code in a new interpreter (puts it on the EXEC stack there)
  2. every execution slice that is allocated to this env will go to this new interpreter instead, until…
  3. When the execution stack of the new interpreter is empty, i.e., it is done, create a program of the ENV, and treat that as a return value by either putting it on the CODE stack or directly on the EXEC stack (I usually pick the latter)
  4. done
That’s about it. I’ve worked with this, but never found any big improvements over running without this. Human concepts such as modularity and isolation and ‘good’ coding practices, rarely translate to randomized programming that is exercised here. However, isolation could have some benefit.

Getting tagged stuff to the code stack and running without time limits

Tuesday, January 18th, 2011

A couple of new features in Clojush.

Available as usual from:

20110118: - Added support for tagged_code_<number> instructions. These are like
            tagged_<number> instructions except that retrieved values are pushed
            onto the code stack rather than the exec stack. Without these the
            only way to get tagged values onto the code stack is to wrap
            values with code_quote prior to tagging. An alternative approach
            is to add new tagging instructions that automatically perform
            code_quote wrapping, but for full generality that would require
            new instructions for each type; also quote-tagged values would
            always be destined for the code stack, while the scheme adopted
            here allows any stored value to be retrieved either to exec or to
          - A value of 0 for the evalpush-time-limit parameter of pushgp
            now means that no time limit will be enforced. This is also
            now the default.

Zippers and dirt-sensing, obstacle-avoiding robots in Clojush

Wednesday, January 12th, 2011

A couple of new features in Clojush.

Available as usual from:

20110111: - Added zipper stack and functions (thanks to Kyle Harrington for
            draft code, although this was re-written).
          - Added registered-nonrandom function.
          - Modified odd.clj example to use registered-nonrandom.
          - Added examples/dsoar.clj, a version of the "Dirt-Sensing,
            Obstacle-Avoiding Robot" (DSOAR) problem first described in:
              Spector, L. 1996. Simultaneous Evolution of Programs and their
              Control Structures. In Advances in Genetic Programming 2, edited
              by P. Angeline and K. Kinnear, pp. 137-154. Cambridge, MA: MIT Press.
            This version was written by Brian Martin in 2010-2011.

Alternative node selection methods in Clojush

Wednesday, December 8th, 2010

Clojush now supports alternative node selection methods for mutation and crossover. In addition to the :unbiased method (which was all that was previously available) there is now also :leaf-probability (which allows for Koza-style selection of 90% internal nodes / 10% leaves, or any other percentages) and a novel method, :size-tournament (see below). Brian Martin drafted these changes, which I subsequently tweaked with input also from Kyle Harrington.

Available as usual from:

20101208: - Added alternative methods for node selection, used in mutation
            and crossover (drafted by Brian Martin, with suggestions
            from Kyle Harrington). This introduced three new globals:
            global-node-selection-method, global-node-selection-leaf-probability,
            and global-node-selection-tournament-size, each of which holds
            an atom, and three new parameters to pushgp: node-selection-method,
            node-selection-leaf-probability, and node-selection-tournament-size.
            The node-selection-method can be :unbiased (in which case nodes
            are selected using the uniform distribution that was previously
            used -- this is the default), :leaf-probability (in which case
            the value of the node-selection-leaf-probability argument,
            which defaults to 0.1, specifies the probability that leaves,
            as opposed to internal nodes, will be selected -- this is the
            method used by Koza and others in tree-based GP), or
            :size-tournament (in which case the value of the
            node-selection-tournament-size argument, which defaults to 2,
            determines the tournament size for node tournaments, with the
            largest subtree in the tournament set being selected).

Clojush minor fixes, intertwined spirals

Sunday, December 5th, 2010

Clojush minor enhancements/fixes, intertwined spirals.

Available as usual from:

20101204: - Added pushgp-map, which allows pushgp calls on maps of arguments,
            and a demonstration of its use in argmap_regression.clj.
          - Added :gen-class and -main definition (thanks Kyle Harrington).
          - Fixed eval-push termination to return :abnormal for exceeding
            time-limit (thanks Kyle Harrington).
20101205: - Added modified version of Kyle's version of the intertwined
            spirals problem.
          - Minor changes to this README.

Visual demos of Psh in Processing

Thursday, November 18th, 2010

Tom Helmuth has produced two nice demos of Psh being used in the the Processing programming environment:

  • PshApplet: A symbolic regression demonstration
  • PushBrush: An arts-oriented, visual demonstration

Clojush lawnmower, tweaked ant

Sunday, November 7th, 2010

I’ve added an example problem to Clojush for Koza’s lawnmower problem (from his GP II book, 1994). Koza used this problem to demonstrate the utility of ADFs, and it should be a good benchmark for modularity mechanisms more generally. From my first quick tests it looks like tags help quite a bit here. Of course it’s possible that other Push mechanisms will as well. From a Clojush hacking perspective this example might also be helpful insofar as it shows how to add a new type/stack without messing with the code in clojush.clj — I did this because Koza’s formulation of the lawnmower problem is based on 2-element integer vectors. Also in this update I’ve tweaked the parameters on the ant examples, after noticing that bloat is a real problem for these and that the simplification operator helps.

Available as usual from:

20101106: - Tweaked parameters in ant examples; among other things,
            increased simplification since bloat was an issue. Also
            added some evolved solutions in comments.
20101107: - Added Koza's lawnmower problem example; this demonstrates how
            to add a new type/stack on a problem-specific basis, without
            altering clojush.clj.

First evolved tag use

Thursday, November 4th, 2010

The following solution to the tg8 regression example is the first thing I’ve evolved (and then hand simplified) that makes use of stackless tagging. It uses a single tag, associated with the code “(in integer_mult)” — this is a subroutine that multiplies whatever is on top of the integer stack by the input.

(tag_exec_837 (in integer_mult)
  6 (integer_mult tagged_778) (in -10)
  (integer_mult integer_add in integer_sub -2 in in
    integer_sub 10 integer_add tagged_20 in tagged_237
    integer_sub integer_sub integer_sub -3 integer_add
    in integer_div tagged_767 tagged_601 tagged_20 6
    tagged_237 integer_sub in integer_add tagged_20 in
    integer_add in integer_add in integer_add in
    integer_mult 1 integer_add 4 integer_add))

Stackless tagging (+ fixes/enhancements) in Clojush

Thursday, November 4th, 2010

Several changes have been made to Clojush, the most significant of which is the implementation of stackless tagging (motivated here and here, with the implemented details described below).

20101102: - Switched to new clojure.core/frequencies from depricated
            seq-utils/frequencies (h/t Kyle Harrington), and similarly
            for flatten.
          - Added :include-randoms keyword argument for registered-for-type.
            Defaults to true, but if specified as false then instructions
            ending with "_rand" will be excluded.
          - Raised invalid output penalty in tg8 (it was lower than reasonable
            errors for that problem).
20101103: - Converted evalpush-limit and evalpush-time-limit into vars
            (global-evalupush-limit and global-evalpush-time-limit) bound
            to atoms that are reset by calls to pushgp (keyword arguments
            :evalpush-limit and :evalpush-time-limit).
          - Changed pushgp parameters in the tg8.clj example.
20101104: - Implemented stackless tagging (see
            2010/10/28/stackless-tagging/). Tag instructions take one of
            the following forms:
                create tage/value association, with the value taken from the
                stack of the given type and the number serving as the tag
                remove the association for the closest-matching tag
                push the value associated with the closest-matching tag onto
                the exec stack (or no-op if no associations).
            Here "closest-matching" means the tag with lowest number that
            is greater than or equal to the number of the tag being matched,
            or the lowest-numbered tag if none meet this criterion. Tag
            instructions are not implemented in the same way as other
            instructions; they are detected and handled specially by the
            interpreter (see execute-instruction). Tag instructions
            can be included in pushgp runs by using the new ephemeral
            random constant functions tag-instruction-erc,
            untag-instruction-erc, and tagged-instruction-erc, each of
            which takes a limit (for the numerical part) as an
          - Added examples using tags: tagged_ant, tagged_regression, and

Stackless tagging

Thursday, October 28th, 2010

Following up the recent post and comments on Lexicographic names, along with some off-blog discussion, I think I’m ready to implement something called “stackless tagging.”

First the tagging part: This is really just what we’ve been discussing as lexicographic names, but (as we discussed) the name “name” isn’t quite right, and we might want this new thing to co-exist with Push3 names some day. So we were casting about for other names/metaphors, ranging from the vacuous (“index”) to the wacky (something based on The Price is Right), and I subsequently scoured a thesaurus and even Charles Sanders Peirce’s 19th century classification of signifiers…. leading to a couple of candidates I didn’t love (I think the leader was “lexeme” — blah)…. before I realized what should have been obvious to me: “tags”. This comes from Holland via Riolo and company in their model of the evolution of altruism, on which Jon Klein and I later did some work (ALife paper, GPTP06 chapter)

The key idea is that a tag is like a name except that you don’t have to match it exactly. In the Riolo-style models tags were floating point numbers and similarity was numeric difference (which was thresholded), and we may implement something similar (probably more like integers, using differences but not thresholding), but Holland’s notion was more general (see his book Hidden Order). In any event, at a conceptual level all that we care about is that there’s a way to address things with inexact references (via similarity), and the tag concept covers this nicely. (BTW in my quick look back at Hidden Order I don’t see explicit mention of non-identical similarity, but I think it’s implicit.)

The stackless part is Tom’s suggestion that, for parsimony, we just build the tags directly into tagging and tag-lookup instruction names. So for example we may have things like integer.tag-4123 which pops the top integer and tags it with 4123, along with things like at-tag-3745 which pushes whatever is tagged with 3745 (OR, if nothing is tagged with 3745, whatever has the closet tag) onto the exec stack.

We could have typed at-tag instructions and separate tag stores by type, but for now, for simplicity if nothing else, I plan to have only one store and have at-tag-<num> instuctions push whatever has the closest tag onto the exec stack, from where it may end up on another stack via execution. I will have type-based tagging instructions, since otherwise it would be hard to tag different types of things, but not type-based tag lookup/reference instructions.

This kind of stackless mechanism would be a awkward with Push3 names, at least if you have a potentially large or unbounded set of possible names, because in that situation you really want a name stack so that you can correlate definitions with references, etc. But with similarity-based (e.g. lexicographic) lookup this seems much more reasonable. And since it does provide a highly parsimonious way to do this “nameish” thing, and is also simple to implement (although I think that I will treat these new “instructions” in a non-standard way in clojush…), I think it’s a good thing to try first.