Fexpress: Compilation-friendly fexprs

This week, I implemented something I’ve had at the edge of my mind for a long time. It’s an fexpr language, but with a rudimentary type hinting system that lets it produce compiled code. If you want to dive right into the details of the system, the documentation is written for that, and the code might even be explorable on its own.

For background, an fexpr is an abstraction like a function or a macro, but its computation can depend on a mix of run-time information and syntax information.

Advertisement

Progress: Quasiquotation; Cene; co-opetopes?

About two months ago, in my ongoing project to make a quasiquote operation that allows users to define their own variants of unquote as macros, I hit a snag. I took some time away from the problem for a couple of months, but lately I’ve come back to pick up where I left off, and the extensible quasiquote now has a complete implementation. (Here’s the relevant Git commit.) It doesn’t do anything out of the box that other quasiquote implementations don’t do, but it uses hypersnippets to do it, and as planned, it allows users to define their own alternatives to unquote.

To get past the snag I hit, I thought I would need to implement several “selective” operations on hypertees. It turns out I only needed one: hypertee-zip-selective. This operation makes it possible to zip two hypertees while selectively skipping some of the holes of each one. This makes it easy to store data in some hypertee holes while still treating others as actual holes, which is useful for representing hypersnippet-shaped data besides hypertees themselves.

So, now I have a working implementation of a quasiquotation operator with user-definable unquote. I should really write a better post at some point describing how this technique works. In order to get to something that’s simple and stable enough to write useful guide materials for, I’m planning to focus next on cleaning up some of the mess I’ve made trying to implement it over the past couple of years.

Status update: A new library, Lathe Ordinals

I pulled out my ordinal code from Lathe Morphisms into its own library, Lathe Ordinals. It’s like a lot of ordinal number libraries out there already. This Maple documentation is a pretty thorough, if terse, description of the kind of thing I’m implementing for Racket.

Arriving at opetopes for higher quasiquotation

This is another journal entry of my progress toward an extensible quasiquotation syntax. It wanders a bit, but I think it has a happy ending. :)

My last post was about “higher quasiquotation.” Since then, I’ve taken to calling that subject hypersnippets, since the characteristic feature is that it’s a repeated iteration of the concept of “the snippet of code between this boundary and this boundary.” Degree-N hypersnippets are made up of all the code in between a degree-(N-1) hypersnippet shape and zero or more nonoverlapping degree-(N-1) hypersnippet shapes appearing inside it. A degree-1 hypersnippet is like a text selection, and degree-0 hypersnippet is a text stream. Quotation is a certain kind of DSL where the syntax is hypersnippet-shaped, but there are potentially other uses for these shapes.

(Spoilers: Yesterday I finally convinced myself hypersnippet shapes were precisely the opetopes, and hypersnippet-shaped data is data that’s composable using the operations of an opetopic ω-category. So hypersnippets in my original sense are an ω-category generated by some free 1-cells corresponding to characters that can appear in a text stream. (Update 6-3-2018: Michael Arntzenius points out that these generators on their own would just generate strings. I was also sloppy about specifying the generator cells’ sources and targets here. Looks like I need one generator of each opetopic shape to be the holes, with each one’s sources and target being lower-dimensional holes; as well as one generator corresponding to each text character, each of which is a 2-cell with no sources, targeting the unique 1-cell hole.) Nevertheless, I’m still going to refer to these as “hypersnippets” in this post, and I think it’s valuable to refer to them by their intended usage domain in case they morph into a slightly different concept, even if the concept now seems to have stabilized into something that corresponds with opetopes.)

Pursuing higher quasiquotation

Lately I’ve been trying to iron out the details of a generalization of quasiquotation which I call “higher quasiquotation.” The basic idea is that just as a quasiquotation is a region in one parenthesis-delimited region (marked by quasiquote) and a set of other parenthesis-delimited regions (marked by unquote​), we can go on to talk about regions between quasiquoted regions, regions between those regions, and so on.

If you think of values with holes as being functions, then the notion that this is a “higher-order” quasiquotation is clear: Each quasiquotation determines a value of type (c SExpr -> SExpr), the next higher degree of quasiquotation determines a value of type (c (c SExpr -> SExpr) -> (c SExpr -> SExpr)),  and so on, where c is some collection like c a = Map String a. But these functions aren’t the whole story; the quasiquotations should be able to be pulled apart like other data structures, not just filled in to create s-expressions.

I haven’t managed to write a full macroexpander for higher quasiquotation yet. I’ve written this post to share my status as it is.

Design and due diligence of the Cene language

Cene is a language I’ve built over the last couple of years. I’ve talked about Staccato and Tenerezza here, and that code has turned into Cene.

What sets Cene apart: Extensibility support

Cene’s design revolves around the primary idea that future generations will have better ideas for programming languages than we do, so most of what sets it apart is its support for custom languages, which mainly has to do with the design of its macroexpander.

Cene’s macroexpansion phase incrementally writes definitions (of macros, functions, etc.) to monotonic state resources using deterministic concurrency. These state resources are expressive enough that user-defined macros can use them to achieve combinations of open-world and closed-world extensibility, which is what I consider to be Cene’s primary feature.

Season finale, season premiere

This is a more personal entry than usual. This year, several important things have happened in my life already.

The storytelling worlds of Mega Man and Red Ash

So the Kickstarter for Red Ash is live! I have mixed feelings about it, and to explain, I’m going to have to explain my take on Mighty No. 9 and the Mega Man franchise first.

If you don’t know any of those things, well, they’re all projects that were (for the most part) led by Keiji Inafune, and they’re all about robots. I started being a Mega Man fan at a young age, and it’s funny how seriously I’ve come to take it.

With the 2011 cancellation of Mega Man Legends 3 and some further cancellations that followed, the Mega Man franchise entered a dry spell that’s still ongoing. Keiji Inafune left Capcom, started up Comcept, and eventually unveiled the Mighty No. 9 Kickstarter to great success in 2013. To most people, Mighty No. 9 is a “spiritual successor” of the Mega Man franchise. Likewise, to most people, Red Ash is now a revival of Mega Man Legends 3 in particular.

If I want some simple nostalgic enjoyment like Yooka-Laylee, I’ll buy it off the (virtual) shelf; I don’t need to back it. I back a project when I want it to exist when it otherwise couldn’t, or if I consider it to have positive cultural impact.

Mighty No. 9: Telling stories about responsibility

The Mighty No. 9 Kickstarter was meaningful to me because it was a new launching point for Keiji Inafune to build story worlds.

A writing prompt generator and a strategic story game

For a few weeks recently, I had a mission in mind. I have several original stories and characters I want to write about, but I rarely write. When I do, I like to come up with great big plots and settings, but I don’t often drill down to the fine details like character dialog and scene-by-scene dramatic twists. Yet I like to program, and I like to reply to things with witty puns and captions: What if I made a program that set up a scene that I could joke about? Maybe I could write dialog as a side effect!

In pursuit of this, I made a little procedural generator for writing prompts. The code is here, and you can see it in action here.

You’ll find procedural story generators all over the place online, and this is one of the simplest possible: It just takes some sentence templates, plugs in a few character names, and plugs in a quality (or two) of those characters. For instance, here’s a sentence generated for my “Mikkamon” continuity, along with the sentence template that creates it:

Everyone suddenly copycats Mick in shaking a sign, but Marty doesn’t follow along.

Everyone suddenly copycats [character A] in [having a certain quality of A], but [character B] doesn’t follow along.

This writing prompt might not be meaningful to you because you don’t know Mikkamon, but I can explain. Mick is the main character, and his enthusiasm for the upcoming battle-toy Mikkamon leads him to work as a sign-shaker for the grand opening event. Marty is one of his best friends, but she constantly has to supervise his harebrained mischief to keep him from hurting himself.

Despite the simplicity of the generator, this writing prompt opens up layers of characterization for me to think about: Why would everyone start shaking signs? Maybe because Mick uses a sign-shaking stunt to win a Mikkamon battle and it catches on. Why wouldn’t Marty follow along? Maybe because she associates Mick with dangerous behavior, and she finds it worrisome that others would treat him like a role model. If I were to show you instead of telling you, this could turn into a pretty interesting story, I think.

This generator has gone through some iterations as I’ve added various story continuities like Mikkamon, added various sentence templates, and tweaked the pseudorandom distribution… but I didn’t get quite the same kind of writing motivation I expected. That is, I actually called the generator “Monday Comics” with the idea of eventually writing stories on Sunday nights, but I haven’t actually made a habit of that yet.

My parents taught me that if I’m indecisive, I can flip a coin. If I like or don’t like the result, that tells me something about what I wanted in the first place.

This writing prompt generator is a coin, and when I flip it, I discover several stories I find fun and several stories I don’t. But most of all, I realized I’d like to write the stories that introduce my characters and their relationships so that people like you will know what the heck these random interludes mean for the characters involved. I also discovered I was more excited and productive writing for the generator than writing from it, so I might want to build a few more generators like this one to help flesh out my ideas.

Canonball, a strategic story game

On that note, I came up with a second generator a couple of weeks ago. On my commute, in one hour, I wrote down the rules of Canonball, a customizable tabletop game. To be fair, some form of the rules was lurking in my mind for months. (Warning: At the time of writing this blog post, Canonball has gone through only three turns of playtesting, which isn’t even a whole game.)

A primary design goal of this game is to generate fun and dramatic storytelling as a side effect of strategic gameplay, while being open-ended enough that players can design custom add-ons for the kinds of stories they would like to see.

I’ve made numerous attempts at exactly this premise for at least ten years, all under the name “Crossovers and Cameos,” but I’ve gotten bogged down at the prospect of designing hundreds of TCG/LCG cards. Canonball represents a different approach: Each player’s deck has only a handful of cards, currently four, so the game is playable even if I only bother to write up a dozen or so card designs. Not only does that let me approach this as a casual project, but it means players will have a low-effort path to card authorship too!

I want this game to facilitate many of the most popular kinds of stories, so I’ve taken heed of predominant storytelling fomulas that transcend genre:

• In the hero’s journey, a hero ventures to obtain some treasured item and takes it back home.
• In slow-moving serials, characters exchange secrets, and this knowledge can dramatically change their perceptions and goals. If a character discovers a secret that the audience has known for a while, that’s called an internal reveal… or at least that’s what it’s called on TV Tropes!

I’m always excited to see stories break out of the usual structures, but these formulas thrive for practical reasons: Hero’s journeys are schematic advice (or at least encouragement) for adapting to and taming unexpected circumstances. An internal reveal is a pivotal event in the story, so it can reinforce viewership.

When players design new character cards, their experience with these popular story formulas may influence them whether they realize it or not. Even though a game of Canonball doesn’t involve great advice or episodic viewership, it goes with the grain by imitating the superficial appearances of those formulas:

• Each player has a treasured item called their ball. The objective of Canonball is to steal the opponent’s ball and bring it back home, over and over.
• Each player has a power-up card called their evidence. Word spreads fast, but not too fast; if a character has evidence, another character may spend their turn copying it.

Once I’ve playtested Canonball some more, I look forward to encoding several of my characters as Canonball cards. It’ll be a way to help me think about my characters in more depth, and maybe some other people could have fun with these cards even if they don’t know my characters like I do.

Canonball is still in a very early stage, and the rules are mostly notes to myself, but it is playable! If I end up letting it stagnate for a while, don’t let that stop you from trying it out and sharing some card designs. :)

Tenerezza Underway

Over the past couple of weeks, I’ve ironed out most of the design for both the Tenerezza core language and a convenient Lisp-like macro layer.

Tenerezza

Tenerezza is distinguished from mainstream languages in a few ways:

Tenerezza is an untyped language where all values are distinguished by sealer/unsealer tags. Even function closures are unencapsulated to someone who has the right unsealing permission.

Tenerezza’s first-class values are always sets. In fact, you can only unseal an element at the time you loop over its container because you can’t manipulate a single element directly. This builds on some existing work around doing computation on sets.

Tenerezza supports general recursion, but only by way of a computation monad (namely, returning a stack of functions to call). Otherwise if a Tenerezza computation’s set inputs are a constant size, it takes constant time. This is meant to make it easy to visualize, step through, patch, and persist the dynamic shapes of a Tenerezza computation.

Actually, Tenerezza’s first-class values aren’t merely sets. Every first-class value in Tenerezza carries an input set, but it also receives an output set. Overall, it represents a communication channel.

This actually means Tenerezza programs may have causality paradoxes as inputs loop around to become outputs and back, but these infinite loops should be about as easy to debug as the infinite loops today’s programmers are used to.

The macro layer

Although the Tenerezza language does some desugaring so programs can be written in a convenient format, the Tenerezza language is going to be pretty verbose to use directly. Possibly the biggest issue is that a Tenerezza program needs to have names denoting every one of its cheap steps, and these special-purpose, implementation-dependent names clutter the code.

I’ve designed a macro layer. Macros can locally convert custom surface syntaxes into the standard Tenerezza sugar, and Tenerezza can then do nonlocal desugaring transformations to decompose the program into cheap steps.

I’ve put together the macro layer in an extensible way, using some late binding techniques I learned making Penknife. Unlike in Penknife, this time I’m not reliant on global method tables; I’m now using an idiom where the method is a data structure, and an object is a function that takes a method as an argument. This is a pretty simple idiom, and I might revise it in various quirky OO ways to support things like super and meta-object protocols, but I’m happy that these quirks will not pollute the global definition semantics.

Taking it from here

This is shaping up to be a small design that covers most of the bases of what I’d want for general-purpose programming. Once some further details of the design are fleshed out, such as macro hygiene and code signing, I may start implementing this and using it.

It’ll probably be slow at first since the implementation will be passing around sets, but thanks to Tenerezza programs’ decomposition into cheap steps, it should be pretty easy to profile a program and figure out which specific subprograms could benefit from optimization.