Invention in Rust

Sunday, July 23, 2023

Tagged: forth, rust, postim, the moon, image filters, programming, bach, paul lutus, douglas hofstadter

When I was a kid, I played around with the language FORTH on my Apple 2. GraFORTH, I'm pretty sure. I didn't get very far into it -- I don't remember creating anything complicated. But I did figure out how to make beeps and boops at various pitches. (Chapter 9!)

As it happened, another floppy in my (mostly pirated) collection was Electric Duet. This program accomplished the feat of playing two-voice music through the Apple's one-bit sound channel. Two notes at once on the same speaker! Inconceivable wizardry. If you fire up that link, you'll find a "jukebox" of pre-programmed tunes -- mostly Bach inventions -- and an editor that lets you play with the system yourself. If I recall correctly, I typed up Bach's Crab Canon. (Of course I was a Hofstadter fan.)

I was also a fan of other "weird" Bach renditions, notably Wendy Carlos (electronic) and the Swingle Singers (a cappella jazz). The best idea I ever had -- and I may mean that literally -- was to program in a Swingle-style rendition of a Bach fugue in GraFORTH, and then go around telling people that I had invented swinging Bach in FORTH.

(...You have to say it out loud.)

(No, I never got around to doing it.)

By not exactly a coincidence, both GraFORTH and Electric Duet were created by Paul Lutus, a genius of the early Apple era who really deserves to be better-sung. No pun intended. I am delighted that he's still around and running a web site. Lutus also created Apple Writer 2, the text editor that got me through high school with my fingerbones intact. (I have never been able to hand-write long essays without my hand cramping up.)

If I had gotten more deeply into FORTH, I might have realized it was peculiarly suited to those early 8-bit machines. FORTH is powerful, flexible, speedy to execute, and dead-simple to parse.

But I didn't re-encounter FORTH-like languages until college, when I began messing with hand-written PostScript. PostScript was a stack-based language like FORTH, and for similar reasons: it had to be fast, flexible, and run as embedded software on a printer. And you could write it yourself! I must have first encountered the idea as a file called (Yes, there's my name in the credits, but I just fixed a few rendering bugs.)

A stylized running Wizard.

For a few years, almost every visual design project I got into was PostScript underneath.

A maze drawn on a Rubik's cube. Play money in denominations of 1 and 5.

PS remained my art language of choice until 2006-ish, when I ran into SVG. SVG is not stack-based; it's not a programming language at all, but a declarative data language like HTML. That was somewhat limiting, but I decided that a visual editor was just easier to work with. And hey, if I needed to generate SVG procedurally, I could always write a Python script.

The idea of code-making-art stayed in the back of my head, though. For one thing, I'm good at code. Any personal art project is a project that, in some sense, nobody else could have done -- but if it involves code, then I know not a lot of people could do it!

So when I started looking around for a Rust project, I decided to whip up some image transforms.

(This is a post about learning Rust. Did I forget to mention that? Sorry.)

I installed the Rust compiler, opened up the manual, compiled the ritual invocation to Mother Gaia, and then got started with some image code.

pub struct Pix<T> {
    pub r: T,
    pub g: T,
    pub b: T,
pub struct Img<T> {
    pub width: usize,
    pub height: usize,
    pub pixels: Vec<Pix<T>>,

(That's a Rust generic data structure. T can be any data type. I found it handy to load images with byte pixel data, but convert to float pixels for the math part.)

(Yes, there's packages for this stuff. Shush, it's a learning project.)

Not too long after that, I had basic PPM reading/writing and a cheap box blur. Not too long after that, I had implemented my first idea: a hole in the Moon!

A Lunar surface photo. The same Lunar surface with a geometric hole punched in it, like a sinkhole. Moon image from the Lunar Reconnaissance Orbiter.

This isn't a 3D model. It's just an image distortion combined with a bit of dark-light shading. Pure trickery. Looks nice though, right?

I also messed around with seamless image tiling.

A Lunar surface photo repeated four times. The same photo repeated, but with the seams smoothed out.. Left: Four copies of a Lunar photo. Right: The same image processed to remove visible seams.

Here's a trick that I don't think I've seen before:

Nine Lunar photos. The same image, but with the seams smoothed out.. Left: Nine Lunar photos (actually six with some repeats). Right: The same image processed to remove visible seams.

Usually you want a single tile that can be repeated seamlessly. But here I've got a quilt of tiles which are blended seamlessly. There's some repetition -- you can see craters cloned here and there -- but it's a random mix of six basic tiles, rather than one over and over. Much less painfully rhythmic. If I bumped it up to a dozen basic tiles, it would do for a background.

(By the way, this isn't smart modern AI image smoothing! It's a simple image offset-and-blend straight out of the 1990s. I reverse-engineered the GnuIMP Tile Seamless filter.)

That was fun. Where does the FORTH come in?

After a few days of writing Rust functions to manipulate pixels, I decided it would be more fun if I could specify those manipulating with scripts. And hey, learning project, right? Parsing scripts is a Rust skill I could certainly reuse.

Steve Donovan's Gentle Introduction mentioned the Nom parser, so I dug into that.

Nom gets way deeper into Rust generics than my simple pixel-masher. So that was good. After a couple of days of bitter struggle in the 'a trenches, I had the input split up into a sequence of FORTH tokens. Plus a few special cases like floats, size tuples (64x64), and hex colors ($7F0).

Given a stream of tokens, the interpreter itself was as easy as promised. Within a couple of hours I had a script that read an image, applied an operator, and wrote it back out again.

Let's jump straight to my showpiece, the hole-in-the-moon script:

>>rad  >>img

img size split 0.5 * >>halfheight 0.5 * >>halfwidth

img {
  halfheight - >>ypc
  halfwidth - >>xpc

  xpc ypc hypot >>dist
  xpc dist / >>xvec
  ypc dist / >>yvec
    xpc halfwidth +  ypc halfheight +
  } {
    rad dist - 2.0 * rad / >>dist
    xvec yvec + dist * >>mshade
    rad  dist asin rad *  - >>dist
      dist dist
    } {
      0.5 mshade *
      xvec dist * halfwidth +  yvec dist * halfheight +
    } dist isnan ifelse
  } dist rad >= ifelse
} {
  swap shade
} projectmap

When reading this, remember that FORTH is stack-based (postfix, or "reverse Polish notation" if you're of a certain age). xpc dist / means "push xpc onto the stack; then push dist; then pop those two values, divide, and push the result". My only real addition is the >>foo notation, which means "pop a value and store it in the variable foo". (I fudged the postfix a little.)

I also went for extremely polymorphic operators. 5 2 * evaluates to 10. But then 32x64 2 * evaluates to the size 64x128, and $112233 2 * evaluates to the hex color $224466. And of course you can multiply an entire image by a constant, element-wise. Or by a color, RGB-wise. Or by another image, pixel-wise -- if they're the same size. You can add or subtract images. All arithmetic operators work the same way.

(These operations are always pixel-by-pixel or value-by-value. So img img + is matrix addition, but img img * is not matrix multiplication. I could put that in but I haven't had a reason.)

Given this, our "seamless" operation becomes very simple:

img halfshift
img size diamond  4 sigmoid

We begin with an image on the stack. Store it as the variable img for future reference.

Then we push three images onto the stack:

  • The original image
  • That image shifted by half. (halfshift is a built-in operator.)
  • A diamond-shaped mask of the same size. diamond is a built-in that generates this; 4 sigmoid applies an ease-in-ease-out curve which looks better.

A diamond gradient mask.   A diamond gradient mask with a narrower gradient. Left: A diamond mask gradient with a simple linear gradient. Right: The same with a sigmoid ease-in-ease-out gradient.

Finally, IMG1 IMG2 IMGMASK interpolate combines IMG1 and IMG2 based on the IMGMASK value -- pixel by pixel, of course. That's our result! (I told you it was brutally simple.)

The last important trick is functional operators. Let me drastically simplify the "holify" script above:

>>rad  >>img

img size split 0.5 * >>halfheight 0.5 * >>halfwidth

img {FUNC1} {FUNC2} projectmap

We store the two arguments as rad (the size of the hole) and img (the image to operate on). We also compute halfwidth and halfheight, which will be handy temporary values.

All of the work is the line img {FUNC1} {FUNC2} projectmap. (Curly braces mark a function -- I stole that from PostScript.) What is this magic?

The projectmap operator means: "Given an image img, create a new image of the same size. For each pixel (x,y), let (x',y')=FUNC1(x,y). Look up the color c from img at (x',y'). Then let c'=FUNC2(c). Use color c' for the new image."

In other words, we project the coordinate to a new location, then map that pixel color to a new color. Repeat this operation across the whole image and we have a new image. Then it's just a matter of finding the right math for FUNC1 (stretch away from the center) and FUNC2 (lighten or darken around the edges) and whoosh -- holified.

(The extra curly braces inside FUNC1 are just nested conditionals. An "if" statement in FORTH looks like {FUNC1} {FUNC2} condition ifelse.)

(Yes, there's separate project and map operators if you want to start simple. But, like I said, this is my showpiece. Gotta get fancy. Also it lets me avoid some repeated arithmetic; I compute the shade value in FUNC1 and pass it to FUNC2 on the stack. That's why FUNC2 is so short.)

For a finale, here's a combination of holes, seamless tiling, and a Hubble starfield:

A distorted Lunar surface with many holes punched through it. A starfield of galaxies is visible through the holes.

So what do I think of Rust?

It's usable. I could get work done if Rust were a job requirement.

(This is of course why I looked at it. Lotta systems jobs out there which have gone with Rust.)

It's fast all right. For my original box-blur function, Rust (in release mode) came within 20% of my hand-optimized C. It also found all my optimizations (lifting expressions out of loops) and applied them without me having to think about it. That's good mojo.

Like anyone starting out with Rust, I spent most of my time fighting the compile-time error checker. The compiler is good at telling you when to throw in & or mut or .to_string() or .clone(). Mechanical stuff.

It's less good at telling you how to resolve trait or lifetime conflicts. These are cases where what you want doesn't make sense -- or doesn't make sense to the compiler -- and you have to rethink the plan.

Rust's promise is that it will hold you to good coding practices by catching violations at compile time. This is often successful. "Know who owns an allocated object." "Don't let one function free an object while another function is using it." Rust's move/borrow rules are good at that. But sometimes the enforcement isn't as smart as me.

Example: My interpreter has a stack of executing functions. A function is a shared reference to an array of tokens. (Rc<Vec<ScriptToken>>. In C++, this would be a std::shared_ptr.) I want to iterate through the stack, popping functions when they're finished. Sorry; Rust throws a hissy-cow because the iterator can outlive any given function. Not allowed to return a reference to an array element that might go away.

Okay, that's fair. I'll just make my own iterator object that has shared refs to all its arrays! Then the iterator itself will keep the arrays alive. Simple, right? And it works. Rust can express that with 'a notation: the token references returned by will live as long as the iterator itself.

Only now my object doesn't conform to the standard Iterator interface. I eventually figure out that the problem is inherent. My object has a fact about lifetimes that the standard Iterator does not; therefore it is not an Iterator. (This turns out to be the "lending iterator" pattern; much discussion exists; the upshot is "That's Rust-land, Jake.")

Fine. I can work around it with slightly messier iteration loop. ( only works with a standard Iterator.) But this is not Rust holding me to a good pattern; I've got a good pattern that Rust doesn't like.

Another example: the "holify" script above. Remember how it passes two functions to the projectmap operator? I tried to implement this by writing a project_map(func1, func2) function in Rust. No problem!

But then I couldn't call it, because func1 and func2 are closures which use the same mutable stack. (Remember, I'm passing a value from func1 to func2 on the stack.) Can't have two mutable references to the same object.

I know what I'm doing is safe, because I never call func1 and func2 at the same time. They alternate. But there's no way to express that to the compiler, so it disallows the whole idea.

Again, I found a way around it. (And I thought of a second way while writing this post.) But again, this is time spent working around the compiler.

Yet more: I tried reading up on Rust GUI toolkits. GUIs are naturally big tangles of live, event-driven objects -- controls, windows, views. Rust is not good with that. Cue more ongoing discussion.

("Just use React-style trees of immutable objects!" Yeah no, that gets into a separate issue: time spent getting your code all nice and functional. I'm gonna skip that here because I'm not sure how much Rust really cares about that stuff. The Nom module is very functor-y but that may be a local prejudice. See this Mastodon thread if you want to see my original complaint.)

So Rust is usable. But I don't particularly like it. But I like getting a little functor-y, and Rust supports that. But I also like using exceptions and class inheritance now and then, and Rust doesn't support those.

I dunno. I guess if I had to write a big complicated close-to-the-metal application, I'd consider Rust. C is too bare-bones; C++ is too bloated. Rust is okay. That's my big anticlimactic conclusion.

FORTH is fun though! I'd never write anything big in it, but it's great for this mess-around-with-an-image scripting. I may do some more lunar transforms.

My image-scripting project is called Postim, by the way. You're welcome to mess with it, but I'm not planning to write any documentation. It exists purely to scratch my own itches.