Twiddly bits

tangible toys to transmit theories

Squeak Smalltalk

The first course I took at Portland State University was called “Object Oriented Programming” with Professor Andrew Black. I hadn’t written any code since I was a kid, but I wanted to learn about Smalltalk and I was fascinated by user interfaces that mimicked the physics of real objects. (The iPhone wasn’t yet even an unconfirmed rumor.) For my final project, I came up with a “throwable” little shuffle-puck widget that bounces off your Squeak (or Pharo or Cuis) environment’s windows. [HockeyPuck.st]


Scratch

I soon discovered Scratch, a blocks-based drag-and-drop programming environment for kids. To try it out, I made a little software poem featuring the cake toppers from my wedding. The gist is that Dino and Bot want to be close... but not too close. If you move one of them, the other follows. (You have to be in ‘presentation mode’.) Try it in your browser on the Scratch site, or download here. [dino+bot.sb]


RoarVM Smalltalk

When Dr Black invited me to collaborate on a summer project with himself, Dr David Ungar (of Self fame!), and a grad student in exotic faraway Belgium named Stephan Marr, my undergraduate research career had begun. The Renaissance project explored trading correctness against performance in “many-core” computers. Our motto was “embracing nondeterminism” and our research vehicle (Stephan’s dissertation piece) was an unsynchronized parallel Smalltalk virtual machine called RoarVM, which runs a souped-up old Squeak image with MVC graphics (since Morphic’s unprotected threading model was too delicate for the VM). My role was to make a demo application, and I thought a particle simulator might be a good match.

Thus was born “collision sort,” my multidimensional, spatially constrained, parallel sorting algorithm; a descendent of the ancient and oft-maligned bubble sort. You can watch an animation of the original demo in action. If you’re brave, [RVM-CollisionSort.zip] has all the bits (as .st fileouts, since we never did back-port Monticello package management into the RVM-compatible image).

More on collision sort below, but my other contribution to the project was the logo. My thinking went like this:

But they didn’t like my mouse; too fat, too grey... sigh. Everyone’s a critic.

And my next attempt looked too much like bees, they said. Andrew discreetly suggested that I copy from the masters. So that’s the origin of the official version, the one that ended up on the ultra-limited-edition T-shirts which we handed out at SPLASH’10. Mild apologies to the Stuart Little movie’s CGI artists and their lawyers... but in retrospect the mighty Disney empire probably still owed its estranged stepchild Squeak an itty-bitty kindness.


Haskell

The next step in my programming language journey was PLT Scheme (now Racket). I’d happily recommend the How To Design Programs curriculum to programming beginners, but I haven’t yet made anything worth sharing in that environment. Haskell introduced me to auto-checked function types, dispatch via pattern-matching, immutable state, and lazy evaluation: a heady mix of features, all bound up in a syntax and culture which encouraged literacy. Programs you could read? What a concept! Dr Christof Teuscher was cool enough to let me use it in his “Advanced Embedded In-Silico and In-Materio Computing” survey course, while all the poor ECE Master’s students were wrestling with MatLab. Teuscher’s an engaging lecturer and a connoisseur of bold ideas, so his course was great fun. Apart from research presentations, the assignments consisted of making highly simplified models of speculative (er, “emerging”) proto-technologies.

Here’s an annotated Haskell (GHC) program for the stochastic self-assembly of my initials from square little ‘particles’ which wander around a 2D grid, and a text file with some sample results. [SelfAssembly.hs] [SelfAssemblyResults.txt]

And here’s my solution to a slightly more open-ended assignment, also involving little square particles in a jiggly-noisy regime. They work together to form a substrate for a cellular automaton of sorts, which in turn acts as a self-repairing NAND gate. You can watch a video demo if you’re not inclined to run the program yourself. [SelfRepair.hs]


NetLogo

Shortly thereafter I wandered into NetLogo. My sojourn there has been prolonged, in no small part because it gives me that blissful old HyperCard feeling. It’s a far less ambitious environment than Squeak: the turtles get around, but they don’t even try to go all the way down. The Java basement’s lately been remodeled with Scala, but there’s no interior access. Still, the floor doesn’t creak under my feet and the ceiling’s high enough for grown-up scientists (so long as they’re not computer scientists). I love NetLogo for its carefully comprehensive tangible metaphor, for its thoroughly documented and plain-spoken primitive vocabulary, and above all for the sociable humility which has gained it a healthy user base: not of techies, but of sociologists, biologists, geographers, teachers, and kids.

Memes in space

One of the paradigmatic NetLogo models is called Wolf Sheep Predation, included in the download package’s Models Library. It de-abstracts the classic Lotka-Volterra differential equations into discrete interactions between spatial agent-sprites: one of the easiest things to do with NetLogo. My own take on it involved an adaptation of what sociologist Derek Gatherer calls “the paradigmatic example in memetics,” the Boyd-Richerson “homebodies vs the hellraisers” recurrence-relation model. I’ve put the accompanying formal writeup over with the rest of the essays. It’s (mostly) just a bit of silly-serious fun. [HnH.nlogo]

Spatial sorting

Christof Teuscher brought the spatial computing community to my attention, and my interest was piqued. After I started working in his research lab, I set about adapting my earlier Renaissance project experiments on sorting data in noisy, defective, highly parallel environments to NetLogo. At Teuscher’s suggestion, I also started thinking about sorting in networks. As it turned out, some of that stuff was eventually worth a research conference workshop paper publication or two, as well as the requisite posters for the undergraduate research program’s poster sessions. (The rest of it I figure is worth an essay page.) Here are video clips of the mesh-embedding insertion sort and the simultaneous two-axis collision sort. And here’s the code:

[mesh-sort.nlogo] [1d-collision-sort.nlogo] [2d-collision-sort.nlogo]

Networks

My best NetLogo work so far has been under the supervision of Melanie Mitchell, after I joined her Complexity Explorer development team at PSU. Knowing that it might be thoroughly puzzled over by anybody on the internet trying to understand something about “complex systems” has been great motivation to write simple, concise, readable code with considerate user interfaces, rather than just hacking stuff up. I was responsible for two broad categories of model, and network science was one of them. Here’s a version of the writeup document for the network model series: my painstaking attempts at accessible explanations and exercises for the following three models. Please note that the official versions of all Complexity Explorer materials are (or eventually will be) available on that website, not here.

[LittleGraphs.nlogo] [ScaleFreeNetworks.nlogo] [SmallWorldNetworks.nlogo]

Cellular automata

I’ve been fascinated with cellular automata since about age 12; reading Wolfram’s ginormous tome merely fed the fire. Given a chance to present one of von Neumann’s under-appreciated brain children to a general audience, and having grasped some of the most basic concepts of algebraic topology, I’m pleased to be able to give a somewhat more general definition of a CA than you might find elsewhere. It’s in the introductory section of my cellular automata model series writeup for Complexity Explorer, which also includes explanations and exercises for these:

[ElementaryCAs.nlogo] [2D-EnumeratedCAs.nlogo] [AdditiveThresholdingCAs.nlogo]

I never quite finished the writeup documents for these others, but I’m quite happy with them too — especially my authentic, unbounded implementation of Conway’s Life, which certainly ain’t your Models Library’s Game of Life! I think they’re sufficiently explained internally.

[GameOfLife.nlogo] [Wireworld.nlogo] [Evoloop.nlogo]

At first I wasn’t sure whether to put the Kauffman random boolean network model with the rest of the network material, but I think it’s more about discrete dynamics than network structure, and anyway it’s a CA under my generalized definition. It’s also thoroughly documented in the writeup PDF. [RandomBooleanNetworks.nlogo]

In the Spring term of 2012, I joined a small handful of PSU’s computer science grad students to watch some video lectures (and read lecture notes) from Frank Pfenning at CMU. As a final project I made a couple of models demonstrating how CAs can be seen as formal proofs in a constructive logic. This perspective led me to a method for coordinating parallel processors to achieve correct computation of CA evolution, without Valiant’s BSP-style global synchronization “super-steps.” Even better, by using a linear logic, I can do the same trick in working space directly proportional to derivation depth. It’s pretty technical, but mostly documented in the models. If you can figure out what I’m saying but think I’ve missed something, I’d appreciate your feedback!

[CA-sync.nlogo] [CA-sync-linear.nlogo]

The Mandelbrot set

Although I wasn’t responsible for Complexity Explorer’s fractal geometry models, who can resist the Mandelbrot set? Except the way it’s usually colored, with a discrete cyclic palette, is both meaningless and kind of garish. Come on people, read your Tufte! I made a zoomable, optimized Mandelbrot set model that isn’t eye candy, but rather wholesome all-natural eye fruit. You can see a video or two of it in action. I went on to invent another way to see what the Mandelbrot set really means, by interactive visualization of the complex sequences which color its points. They’re some of my favorites.

[MandelbrotSet.nlogo] [MandelbrotSequences.zip]

Dynamics

I’m not a big fan of three-dimensional info-graphics, because... well, reasons. But some things are just naturally 3D, and the Lorenz butterfly is one of them. It’s so ridiculously simple to do in NetLogo that I have no idea why it wasn’t yet in the Models Library. A little later, a colleague asked for some help in explaining the concept of a “phase portrait,” so I threw together this bouncing-ball model.

[LorenzAttractor.nlogo3d] [BouncePhase.nlogo]

Rubik’s cube

For some reason, I missed the cube craze back in the eighties. Too busy with the Legos, I suppose. Sure, the mechanism’s quite clever, but what’s it good for? Twenty-five years later, after some encouragement from a friend with a better appreciation for pure puzzles, and about halfway through the upper-division college math curriculum, I finally got it: it’s a pretty good exercise for an intro group theory course!

Utilities

These models don’t illustrate any mathematical ideas, just some NetLogo versions of graphics programming concepts from the nineties: pixel-function graphics (as used in my Mandelbrot set model), a smooth color wheel, and drag-and-drop containment nesting (an appreciative nod in the general direction of Morphic). I hope that they’re useful to other NetLogo users out there somewhere.

[smooth-color-zoom.nlogo] [containment.nlogo]