I’ve spent about the last six weeks writ­ing a “sim­ple” lan­guage for genetic pro­gram­ming projects. As with the Nudge lan­guage I wrote (with Brian Kerr, Bill Mer­rill, Bob Kuehne, James Sweeney, Trek Glowacki and Jesse Sielaff) a few years back, I’m going through the effort to sur­face the sub­jec­tive expe­ri­ence of design and project man­age­ment in genetic pro­gram­ming projects.

Quite a bit more on that in a bit. At any rate, an inter­est­ing thing just hap­pened, on that sub­jec­tive expe­ri­ence front.

First, a brief bit of back­ground (because the book isn’t avail­able yet, even in draft):

When GP was first pop­u­lar­ized by John Koza and his col­leagues back about 20 years ago, there was a huge—nay, over­whelm­ing—founder bias in the way problem-​​solving was approached. The “lan­guage” cho­sen in those early days was emi­nently prac­ti­cal for the hard­ware and soft­ware devel­op­ment con­straints in play. Let alone the cul­tural con­text of being Very Abstruse Com­puter Sci­ence from the 1990s.

In other words, every­thing was pretty much Scheme. At least very very Lisp-​​like.

The cul­tural influ­ence of these early design deci­sions can’t be overem­pha­sized. I mean, look up GP any­where, in books or soft­ware projects, and you’ll see trees. Over twenty years, peo­ple have “exper­i­mented with” lin­ear rep­re­sen­ta­tions, and stack-​​based ones, and gram­mat­i­cal evo­lu­tion in more tra­di­tional lan­guages, and some really funky rep­re­sen­ta­tions like the data-​​flow sys­tems of Carte­sian GP.

But you can’t see the for­est for the trees. Indeed, unless things have seri­ously changed over the last couple-​​three years I stopped pay­ing atten­tion, the major con­fer­ences all prob­a­bly still spend most ses­sions talk­ing about vari­a­tions on tree-​​handling algo­rithms.

Now trees have a few inter­est­ing traits, which I’ve been reminded of through my recent expe­ri­ences build­ing the Duck lan­guage (which is not tree-​​based, much, sort of).

First of all, trees tend to have one base node, or root—at least the way human beings tend to define them by anal­ogy. If you look at the dia­gram so promi­nently shown at Wikipedia’s “genetic pro­gram­ming” exam­ple, you see a tree with some arith­metic func­tion at its root.

And this makes sense, of course, when you’re a classically-​​trained Com­puter Sci­en­tist. Because every­body knows you describe syn­tac­ti­cally cor­rect pro­grams using some kind of a gram­mar, and the eas­i­est way to approach it is to say a pro­gram is a kind of [expres­sion | lit­eral], and that an expres­sion is, for exam­ple, some­thing like [[lit­eral | expres­sion] oper­a­tor [literal|expression]], and that a lit­eral is maybe [int|bool|float|string] and an oper­a­tor is maybe [+|*|–|÷] and so on and so on.

From the mighty acorn doth the tiny oak tree grow, or some­thing like that.

But there’s a very par­tic­u­lar three-​​way ten­sion in all genetic pro­gram­ming work:

• You want to design a rep­re­sen­ta­tion language/​process, suit­able for the rep­re­sen­ta­tion of answers to your prob­lem. It needs to be suf­fi­ciently expres­sive to cap­ture both the “core con­cepts” of domain mod­el­ing and the “obvi­ous toolkit” nor­mal humans can use to at least under­stand a prospec­tive solu­tion. In other words, your rep­re­sen­ta­tion lan­guage has to be able to accept inputs that are appro­pri­ate for your project, act on them algo­rith­mi­cally in ways that are appro­pri­ate for your project’s cul­tural con­text, and pro­duce out­puts that can be assessed in terms of that context.

  Because the con­cept is so often ignored in com­puter sci­ence, here are some explicit exam­ples (not all rec­om­mended): “We model stock prices as inte­gers (in cents), and keep track of the price over the last five days.” “The lawn­mower is mod­eled as an agent on a lawn that is a grid, that can move one step for­ward, turn, or reverse one square.” “The [answers] spec­ify the arrange­ment of cir­cuit com­po­nents, which in turn are con­nected by [heuris­tics] before the result­ing model is sent to the sim­u­la­tor for evaluation.”

• You want to design a sec­ond language/​process, suit­able for describ­ing the effec­tive dynamic search for bet­ter answers to your prob­lem. In other words, you can only use “crossover” when answers writ­ten in your rep­re­sen­ta­tion lan­guage can be chopped up and glued back together; you can only do “hill-​​climbing” when you have some sense of what a “close” or “far” change in your code is; you can “repair con­straint vio­la­tors” only if you have the resources, and so on. I’ll argue that there’s a lan­guage of search, and it’s tied to the lan­guage of rep­re­sen­ta­tion in many ways.

  This is the thing almost every word ever writ­ten about GP is about, so I feel unmo­ti­vated to pro­vide fur­ther examples.

• You want to design a third language/​process, suit­able for the unfold­ing goals of your project. This is the lan­guage you, per­son­ally, use to describe what it is you’re doing, and why. It’s how you adapt and plan and mod­ify the project. This is not merely the lan­guage in which the project is spec­i­fied, but the words and con­cepts that describe how you play your role in the project as a process.

  Because the con­cept is so often ignored in com­puter sci­ence, here are some explicit exam­ples (not all rec­om­mended): “I find that the muta­tion rate is too high to let the search con­verge to a suf­fi­ciently good answer.” “I removed trigono­met­ric func­tions from the rep­re­sen­ta­tion because they were wast­ing time.” “The answers quickly grew too large, so we added selec­tion pres­sure to reduce them in size.” “We showed the best answer to the cus­tomer, and they laughed at the nine dig­its of pre­ci­sion on the num­bers.” “I tried that, and it didn’t work.”

To my knowl­edge, GP folks assume the first one is pretty much a given (trees!). Not to be rude, but they often also act as though the third one was some sort of given: after all, research is a mat­ter of Pure Rea­son and Inspi­ra­tion and Fund­ing and Stu­dent Interns, not “process”!

So they focus—as so many nerds are wont to do—on the sec­ond one. Algo­rithms for search: How More to Make Go Fast Now.

Every solu­tion con­strains fur­ther problem-​​solving

I imag­ine only a few of us in the field have exper­i­mented with alter­na­tive rep­re­sen­ta­tion lan­guages. I bet most of those have quickly run into a prob­lem that stan­dard trees can cause.

The last three times I’ve found myself design­ing a lan­guage for rep­re­sen­ta­tion from scratch, I’ve run into one in par­tic­u­lar which I haven’t heard expressed any­where. Took me three rounds to notice, though.

Here are some. (Note that I’m talk­ing about S-​​expressions, like you see in almost every GP book, grown recur­sively accord­ing to a sim­ple grammar.):

• Every tree returns a value. Because of course why would you want to write a pro­gram try­ing to fit a curve through some points that didn’t give you a num­ber as a result?
• Ran­domly grow­ing trees sam­ples the set of “pos­si­ble” trees in a rep­re­sen­ta­tive way. Because, you know, you’re sam­pling them ran­domly, so they must all be in there some­where. Right? [PDF]
• Strongly typed pro­gram­ming is your friend, since you don’t want the result of some badly-​​chosen sub­tree to bol­lux up a cal­cu­la­tion upstream with a run­time error, get­ting you back to “return a value”.
• And the one that brings me here today:

  Recur­sion and iter­a­tion with trees makes me feel icky and strange.

So I guess I’ve writ­ten about eight lan­guages that were specif­i­cally intended for gen­eral and spe­cific genetic pro­gram­ming projects over the last decade or so. Some were tree-​​based, some were lin­ear, some (like Nudge and Duck) stack-​​based, some have been “inter­est­ing” in ways that put Carte­sian GP to shame—remind me to show you Tan­gle in a few months.

In almost every case (except maybe Tan­gle), my over­ar­ch­ing sub­jec­tive expe­ri­ence has run about like this:

1. Oh look, a ratio­nal­iza­tion for writ­ing a qual­i­ta­tively dif­fer­ent new lan­guage for GP!
2. It should be non-​​brittle! Sure, this is mak­ing it harder to read, but eas­ier to use in search! Crossover!
3. It should do arith­metic, and have con­di­tion­als oper­a­tion of some sort, and maybe manip­u­late com­plex struc­tures like trees or arrays or stuff, because you know peo­ple don’t describe their goals in terms of scalar num­bers.
4. Hey look: I threw all the sim­ple stuff in, and I’m run­ning mil­lions of ran­dom programs!
5. Hmmm. [puts hand on beard] Hang on….
6. Almost every ran­dom script I run fin­ishes in Order(N) steps. And thus: they suck at solv­ing inter­est­ing problems.

See, just like every­body else (and more, maybe), I learned a valu­able—and dan­ger­ous—habit back 20 years ago when I started fit­ting data with S-​​expression arithmetic.

Arith­metic is con­trac­tive—or what­ever the right tech­ni­cal term I can’t be both­ered to look up is. Look at addi­tion: two num­bers enter, one num­ber leaves. Sub­trac­tion, mul­ti­pli­ca­tion, divi­sion. Fancy graduate-​​level math like big-​​sigma sum­ma­tion over a set? Con­trac­tion. Hell, it’s not just arith­metic: think about [almost] every Excel spread­sheet func­tion, where no mat­ter how abstruse, the result is never big­ger than the arguments.

Trees are a way of draw­ing con­trac­tions like this. The hun­dreds of mil­lions of spread­sheet users are a valid stress test of the notion: work is mostly about shuf­fling tree struc­tures around. (Well, OK, Directed Acyclic Graphs, but guess what? Odds are, they’re con­trac­tive too!) Hell, cal­cu­lus and alge­bra are about reduc­ing expres­sions too: throw them in the mix. Data­base searches and set the­ory? I’m gonna guess “yup”. Sta­tis­tics? Hell, by def­i­n­i­tion of the term.

But you know what? Pow­er­ful as they are for the expres­sion of com­plex mod­els, purely con­trac­tive schemes suck for writ­ing use­ful pro­grams.

Recur­sion and iter­a­tion with trees makes me feel icky and strange.

It’s easy to write a com­puter lan­guage for peo­ple to use that includes recur­sion and/​or iter­a­tion. It’s harder to write a rep­re­sen­ta­tion lan­guage for genetic pro­gram­ming, because the very notion of “ran­dom pro­grams” (let alone mix­ing up chunks of those) brings up the Halt­ing Prob­lem, and the Not Answer­ing Prob­lem, and (my favorite) the What the Fuck is this Here Doing? Problem.

[If you’ve never seen a WTFITHD? Prob­lem: I recently evolved some Duck pro­grams to score Bowl­ing Games. I’ll talk about the expe­ri­ence in detail else­where, but I want to men­tion that it took me most of two days to fig­ure out how some of the answers “solv­ing” the task. Turns out they were run­ning ran­dom chunks of code and accu­mu­lat­ing a bunch of stuff, and then count­ing how many things they had left over after­wards, because they wanted a way of “stor­ing” the num­ber 103. I still have no idea know what spe­cial value 103 has towards scor­ing bowl­ing games, but I also haven’t yet found a way to ask the inven­tors directly….]

It’s harder to write a rep­re­sen­ta­tion that does recur­sion and iter­a­tion because when you chop things up and mix them at ran­dom, you’re forced to cope with the inevitable per­ma­nent loops, and iter­a­tions fill mem­ory expo­nen­tially, and the ghost of Alan Tur­ing just stands there point­ing and smirk­ing wryly. You’re forced to cope with “answers” that don’t say any­thing at all, or which “return” 812 num­bers. All kinds of weird stuff.

Math, as it hap­pens, isn’t hard. Shop­ping is much more com­pli­cated. [Or rather, I real­ize later: Shop­ping doesn’t let you squish all the hard parts into a set of handy algo­rith­mic received wis­dom, like math­e­mat­ics and genetic pro­gram­ming (to date) does. To shop use­fully, I’ll wager one must be far more fully immersed in that third, reflec­tive lan­guage that talks about why.]

After all this ram­bling I merely want to sur­face a triv­ial point, because it’s what writ­ing the third lan­guage and scratch­ing my beard the third time sur­faced in me: I think that in order to jug­gle the ben­e­fits you get in terms of rep­re­sen­ta­tion with iter­a­tion and recur­sion, and the hor­rors of cop­ing with the neg­a­tive search con­se­quences of non-​​contractive processes, you’re forced to step into the third realm and actu­ally think about how to run a project.

Nerds don’t like to think—let alone talk—about how they solve prob­lems. We don’t like to sur­face our processes. And we hate ques­tion­ing the util­ity of our plan­ning deci­sions: just look at any aca­d­e­mic soft­ware if you’re unsure.

So we spend a lot of time look­ing at prob­lems we can solve with trees, or other con­trac­tive rep­re­sen­ta­tions (like even weird ones like Carte­sian GP can be). Look­ing under the lamp post for the keys we lost.

Not because writ­ing recur­sion and iter­a­tion are hard.

Because they force you to think. And thinking—this is the Dirty Lit­tle Secret of Genetic Programming—isn’t “auto­mated”. Hav­ing to think and talk about how any­body solves a prob­lem use­fully is at odds with all the hype and self-​​delusion about what Genetic Pro­gram­ming is sup­posed to be about.

Though I think there is hope. Strangely enough, us nerds also seem to love sys­tems like these. Those, like genetic pro­gram­ming more gen­er­ally, are forc­ing peo­ple to frame things in that third lan­guage as well.

My Duck lan­guage, as of this writ­ing, has all sorts of amaz­ing stuff it can do. Map and reduce, fancy con­cate­na­tive things, higher-​​order functions.

But it’s so awfully, awfully con­trac­tive at the moment.

The inter­est­ing thing, tak­ing a half-​​dozen years and three go-​​rounds of hav­ing the same sub­jec­tive experience?

I only need to change one minor inci­den­tal behav­ior—minus­cule to the point of triv­i­al­ity in com­par­i­son to all the rest of the last six weeks’ work—to change it from a bor­ing old do-​​nothing to a flex­i­ble, expres­sive lan­guage that can… well, do shop­ping in addi­tion to math.

And I find that inter­est­ing. Not the detail of what it is I’m gonna do. Just that it’s one dinky lit­tle (cen­tral, trans­for­ma­tive) thing that jumps Duck from bor­ing old con­sis­tent con­trac­tive order, to the lively edge of chaos.

And that this all is a story in the third lan­guage.