One of the things you real­ize after a while is that projects drop into your lap faster than they can be com­pleted. Some sources of inspi­ra­tion are things you encounter all the time: your work (I know a lot about mol­e­c­u­lar design and phar­ma­ceu­ti­cal lead com­pound dis­cov­ery), your hob­bies (I know a lot about image recog­ni­tion and seg­men­ta­tion for OCR of dig­i­tized books), and things you see other folks doing and just want to try (I’ve enjoyed my years doing Sym­bolic Regres­sion because so many other peo­ple have paved the way, while leav­ing other paths less trav­eled and thus more interesting).

I’m find­ing that writ­ing the intro­duc­tory mate­r­ial for the book is dif­fi­cult. In fact I’ll prob­a­bly post­pone releas­ing the intro until more of the core guts are writ­ten. Mainly the intro­duc­tory mate­r­ial has been about that peren­nial ques­tion, “How do I find and pur­sue ideas?” My core argu­ment is that GP is use­ful for accel­er­at­ing the fruit­ful inves­ti­ga­tion of your ideas, but the chal­lenge for many folks is rec­og­niz­ing the heuris­tics I per­son­ally take for granted. Some of this means I’m revis­it­ing Polya’s How To Solve It: A New Aspect of Math­e­mat­i­cal Method, but I find that it’s not philo­soph­i­cally com­pat­i­ble with the agile stance I per­son­ally pre­fer, so I’m actu­ally find­ing Andrew Abbott’s Meth­ods of Dis­cov­ery: Heuris­tics for the Social Sci­ences more use­ful, not least because he sug­gests Aristotle’s four causes and Kant’s schema as inter­est­ing “kicks to the head”. And there’s Michalewicz and Fogel’s excel­lent How to Solve It: Mod­ern Heuris­tics, which goes in a more tech­ni­cal direc­tion (and closer to GP) tan Polya was able to do.

But I look over all that good advice, and I find it trou­bling. So I’m up in the air about it.

I decided more than a month back to change some­thing impor­tant in the book. I still think Learn­ing by Doing is cru­cial and impor­tant. But I can’t see a way to pro­vide accep­tance tests alone (with no pseudocode or worked-out exam­ples) in an enticing-enough way that pro­vokes rea­son­able responses from the read­ers. That is, I got a lot of push­back from poten­tial audi­ence mem­bers who don’t actu­ally know how to write their own code based on accep­tance tests.

Le sigh.

So I’m try­ing what Ron Jef­fries did in his Extreme Pro­gram­ming Adven­tures in C#: describ­ing what I am think­ing, what moti­vates me, what I actu­ally do, and as a result I hope to make the process itself more trans­par­ent, not just the exter­nally vis­i­ble steps. As Ron pointed out a few weeks back when we chat­ted about it, this smacks of arro­gance. Who am I to think other peo­ple care about the mis­takes I’m mak­ing, or want to be mis­led by watch­ing me do stuff I sub­se­quently undo? Just to prove I “learn some­thing” from it?

Them’s the breaks. The alter­na­tive would be the crap one already has: pseudocode pre­sented as if it were the one “right” way to do stuff, and the inclu­sion of idiomatic (or worse, generic) libraries that the reader should re-create them­selves for every project, not bor­row and re-use indis­crim­i­nately just because it hap­pened to be in a book. In other words, bet­ter sorry than unsafe.

So inspi­ra­tion is a thing I’ll set aside and talk about sub­jec­tively, not in terms of heuris­tics which (as Abbott points out in his excel­lent account) can quickly become fos­silized and rit­u­al­ized as though they were “cor­rect” instead of use­ful.

So I picked up a book

I seem to like math­e­mat­i­cal recre­ations. Just the other day I sketched a lit­tle game thing that some­body should pick up and run with. If it sits around long enough, maybe I’ll do it myself, but not until the book is far­ther along.

In the pile of inter­li­brary loans that I picked up the other day was a trea­sure trove in one vol­ume: Geo­met­ric Fold­ing Algo­rithms: Link­ages, Origami, Poly­he­dra. Now the math­e­mat­ics of origami and stuff is all mod­ern and weird and “advanced” to my gen­er­a­tion; most of the actual math­e­mat­i­cal results came after I grad­u­ated from Uni­ver­sity, and appeared in fancy eso­teric math­e­mat­ics jour­nals even then. But there’s a con­stant cho­rus in New Sci­en­tist and Sci­ence News and stuff about new results, and there’s this other thing I used to do when I was a struc­tural biol­o­gist that involves fold­ing and abstrac­tions of phys­i­cal real­ity sur­pris­ingly sim­i­lar to those in origami. Which is the Holy Grail of a multi-trillion dol­lar indus­try at the moment, by the way.

I’m try­ing to put my fin­ger on what it is about some books— Mar­tin Gardner’s or Cliff Pickover’s or Ivan Moscovitch’s, for exam­ple — that makes them so inspir­ing. Is it the den­sity of open ques­tions? A tone that makes you won­der before dis­clos­ing any­thing? Some­thing inher­ent in this semi-abstracted recre­ational game stuff that makes it clear how to write a sim­ple com­puter pro­gram but unclear how to solve a prob­lem? Some­thing about puz­zles? I have no idea.

At any rate, this one has that same stuff on it. It’s fun.

I picked it up from the stack this morn­ing, opened to a ran­dom page, and started read­ing about one-dimensional origami. Now this is a book that’s fram­ing new work in mod­el­ing phys­i­cal sys­tems like folded paper (and pro­teins) by set­ting up the math­e­mat­i­cal con­structs and abstrac­tions in a tra­di­tional way. But there’s a heuris­tic I find myself adding to the other handy “kicks to the head”, espe­cially use­ful for GP work: What would it take to build a soft­ware sys­tem that “did” this?

So let’s think about one-dimensional origami for a second.

Does it fold?

Before they even get very far in the for­mal math­e­mat­ics of paper-folding, Demaine and O’Rourke talk a bit about rep­re­sent­ing one-dimensional folded struc­tures. You know, the tra­di­tional nec­es­sary and suf­fi­cient con­di­tions for deter­min­ing whether a thing is what you call it or not. Those core con­cepts, the stuff hang­ing off the “triv­ial” parts of tra­di­tional sci­ence and engi­neer­ing that you often elide because you’re just defin­ing your terms, that’s where there’s often low-hanging fruit for GP projects.

I rec­om­mend a browse through the excel­lent book, or just peek at Erik Demaine’s lec­ture notes on the sub­ject. We’re talk­ing about what starts out as a line seg­ment, which we crease at cer­tain (arbi­trary) points, and then press flat so that it pro­duces a sort of accor­dioned stack of squig­gles. Think of a cross-section through a piece of folded paper.

Let’s use paper, for a minute, and just assume for now we are fold­ing it only in the ver­ti­cal direc­tion. Just to get a slightly more vis­ceral sense of it.

Plop a (big) sheet of paper down on the table in front of your mind’s eye for me, OK?

We can make “moun­tain” or “val­ley” folds. Think of a “val­ley” fold as tak­ing either the left or right edge of the paper and fold­ing it upwards and across towards the oppo­site; think of “moun­tain” folds as tuck­ing the right or left edge down under­neath the stack. You can make these moun­tain or val­ley folds any­where between the edges of the paper, and as long as the creases are par­al­lel with the left and right sides you’re mim­ic­k­ing one-dimensional fold­ing. Just peek at the end of the sheet to lose the extra dimension.

There’s a tricky bit of math­e­mat­ics hid­den inside this simple-seeming phys­i­cal model, though: how do we cap­ture the phys­i­cal con­straint that keeps paper from pass­ing through itself?

Demaine and O’Rourke’s con­tri­bu­tions are emi­nent and inter­est­ing and well-considered. There are cunningly-crafted con­straints that cap­ture the phys­i­cal­ity of paper’s inabil­ity to cross itself, and iden­tify fea­si­ble flat fold­ings (and implic­itly fold­ings that aren’t “flat” at all), while main­tain­ing the integrity of the paper itself. In other words, you carry on that direc­tion, and you have a for­mal rep­re­sen­ta­tion that lets you do some fas­ci­nat­ing math­e­mat­ics and modeling.

But what would it take to build a soft­ware sys­tem that “did” this?

By “this” I mean the work of estab­lish­ing nec­es­sary and suf­fi­cient con­di­tions for real­is­tic folded lines. The implicit and tacit stuff a human being takes for granted when they have some notion of “cross­ing” or even “fold­ing” in their heads already.

Does this make sense?

So let’s ask a GP sys­tem to look at a stack of line seg­ments of var­i­ous lengths and “merely” say whether there is any way a sin­gle line seg­ment could have been folded that way, with­out cross­ing itself. Heck, there are prob­a­bly long-range sit­u­a­tions in which a partially-folded crum­ple would inter­fere with itself; let’s ignore those.

So here’s a quick sketch to help out:

The top two squig­gles are actual folded line segments.

The first is def­i­nitely fea­si­ble, in the sense that you can imag­ine crunch­ing up a pipe cleaner or fold­ing the edges-only paper I men­tioned above and mak­ing the cross sec­tion look like that.

The sec­ond it infea­si­ble, because the mid­dle leaf is too big for the space it’s in, and pro­trudes through the crease.

But I think we need to go far­ther for this to be rea­son­ably inter­est­ing. Think about how you would rep­re­sent these objects or sit­u­a­tions in your GP sys­tem. What is a “folded stack”? Do you start from a line seg­ment and intro­duce moun­tain and val­ley folds at cer­tain posi­tions in some order? Or do you start from the folded stack and rep­re­sent it as a series of orders in cer­tain posi­tions, like those I’ve shown below?

I’ve sketched five lit­tle sit­u­a­tions down there in the bot­tom, indi­cat­ing with the dot­ted green lines where the nom­i­nal “crease” points are. Which of those five might be fea­si­ble? Which of them are fea­si­ble but rep­re­sent a line seg­ment that’s not the same size as the orig­i­nal shown in the top two? Which if them is infea­si­ble even when you allow the raw mate­r­ial to be any size at all?

See how this works? Those are all rea­son­ably inter­est­ing ques­tions. I can totally see a set of a few hun­dred (or thou­sand) exam­ples and coun­terex­am­ples for each cat­e­gory. Some exam­ples (I assume) from every com­bi­na­tion of feasible/infeasible, same/different, congruent/incongruent, single/multiple pieces. It’s an inter­est­ing algo­rith­mic exer­cise to fill in that chart with dia­gram­matic exam­ples. Train­ing and test data are yours for the tak­ing then.

But what this sort of project wants from us, as GP folks, is a bit of onto­log­i­cal work.

I’m the one who does this for a liv­ing, so let me pre­empt your ver­sions now:

• a Diagram is a list of Stretches
• each Stretch has a numeric length attribute, and a list Segments attribute
• each Segments list con­tains inte­gers rep­re­sent­ing the seg­ments present, in top-to-bottom order, num­bered from 1 at the top and increas­ing downwards

So for the five exam­ples I’ve shown, each would have three Stretches. Say their lengths are 4, 11, and 5 respec­tively. And the Stretches would con­tain these Segments lists, respectively:

1. [1],[1,2,3],[2]
2. [1],[1,2,3],[3]
3. [1,2],[1,2],[1,3]
4. [1,3],[1,2,3],[3]
5. [1,2],[2,3],[2]

Notice that the only dif­fer­ence between the fea­si­ble and infea­si­ble exam­ples (the first two) is the third Segment. What sort of “think­ing work” does your GP-developed algo­rithm need to do in order to dif­fer­en­ti­ate use­fully between these?

Notice that the first and third are both fea­si­ble, but that the third doesn’t add up to the same amount of mate­r­ial. Again, what does your GP-developed algo­rithm need to “know” to be able to iden­tify which dia­grams might and which might not be the same line? On the other hand, if we think of the Segment lengths as pro­por­tions rather than explicit mea­sure­ments, we’re sud­denly allow­ing the third dia­gram as well; in some sense it’s con­gru­ent to the first, but not identical.

And so on.

What sort of manip­u­la­tions of these input struc­tures might a general-purpose clas­si­fi­ca­tion algo­rithm do? What, in other words, is the Answer Lan­guage like?