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.

The cleanup isn’t necessarily straightforward, because it involves making decisions about what the libraries are designed for — who their audience is, what other purposes they would serve, what terminology to use for them. (And yet I have to make sure not to get distracted with those other purposes when I should be writing documentation. :-p ) For two years I was evaluating all my hypersnippet-related code in terms of whether it helped with extensible quasiquotation, and since I couldn’t get it working until now, my repos are littered with false starts all over the place.

But I think I’m getting that cleanup design sorted out. I’m planning to factor out the most essential hypersnippet-related data structures and utilities (currently part of Punctaffy) into a new library, Lathe Opetopes, which will focus more on modeling the abstract mathematical concept of opetopes, while Punctaffy continues to be about macro systems. I’ll get to the surrounding reasons for this direction toward the end of this post.

Cene for Racket

I mentioned spending two months away from hypersnippets. I spent that time returning to the project that was stalled while I worked on hypersnippets in the first place, Cene. I’ve started to implement a new version of Cene in Racket. It’s not as complete as the JavaScript version of Cene (currently at this repo, whose link may change soon), but for now it’s the version in active development.

Basically, hitting that latest snag with hypersnippets made me reconsider whether I actually needed hypersnippets for Cene at all. It’s a wistful thought I’ve had several times over the past couple of years, but this time I came up with an alternative I liked well enough to do it: Instead of adding hypersnippets, I’m removing s-expressions. More specifically, instead of having an s-expression-based macro system, Cene now has a reader macro system.

This vastly simplifies the source location tracking I was having trouble with when the syntax was s-expression-based. Tracking source locations for error messages was the main reason I felt hypersnippets were necessary for the core language of Cene.

Of course, as I said, I was evaluating hypersnippets by whether they could be used for extensible quasiquotation, but quasiquotation isn’t really core to the Cene language; it can be a library. Tracking source locations was the main thing I felt I needed to figure out to make Cene presentable as a programming language.

With the reader macro approach, I’m glad the Cene core language doesn’t seem to need hypersnippets. Even with stellar documentation, I think hypersnippets would be pretty frustrating for Cene users. (Or maybe I’m projecting. :) )

This time around, implementing Cene in Racket, the implementation gets to benefit from several nearly metacircular things. This time, I don’t have to do quite so much manual continuation-passing thanks to Racket’s first-class continuations, I don’t have to implement my own AVL trees, I don’t have to implement my own bigint arithmetic (which I didn’t get around to doing in JavaScript anyway), and even some of Cene’s more unique subsystems can be implemented in terms of the Cene-style libraries I’ve made for Racket.

When it came time to implement some of Cene’s extensibility-related features, I got a bit lost pondering how they could interact with a module system. I had never gotten around to implementing a module system for the JavaScript version, and this time I had a number of ideas. In order to navigate all these ideas, I spent some time writing design notes. (Here they are.) By the time I was able to write down some action items I could work on, I was happy with the idea of setting it aside for a while and coming back later with these notes to guide me.

Other programming pursuits

Over the past few weeks I’ve done other things:

  • I contributed a simple documentation website generator to the Anarki project. I’ve been helping out with fixing unit tests there too, including upgrading a Racket namespace manipulation library I made 7 years ago (ns.arc) so I could get it running on Racket 7.0.
  • For a discussion with Michael Arntzenius, I wrote some Racket code to demonstrate that with the use of weak tables and finalizers, a Racket data structure could optimize its data representation once all the references to it went through a strict enough contract.
  • For a discussion with Jack Firth about an approach he was taking to implement efficient stream transformation operations, I wrote some Racket code to get a better grip on techniques like those. This is something I’ve seen libraries for but had never used or attempted myself; I’m typically happy to iterate over a stream multiple times.
  • Still thinking about codata thanks to that, I reconsidered Lathe Ordinals. I realized that even though it dealt with “infinite lists” in a certain sense, it still didn’t subsume what streams in the codata sense could do. There seemed to be a perfectly legitimate notion of “ordinal-indexed stream,” where the ordinal bound on the stream’s length (if such a bound even exists) wouldn’t necessarily be possible to determine through a finite amount of computation. Although I don’t have a use for these ordinal-indexed streams, I wrote up an implementation anyway. (Here’s the commit.) I’m pretty sure I haven’t gotten them quite right yet.

Co-opetopes? Ordinal-sized opetopes?

With codata and ordinals on my mind, I gave some thought to how opetope-shaped data would generalize to codata or to ordinal sizes. I have some thoughts forming on this, but I think it’s a topic better covered in another blog post sometime.

This line of thinking clarified how I should proceed with cleaning up my hypersnippet code. If I’m going to be implementing these variations of opetopes and trying to get them algebraically cromulent, I should have a place to do that which is similar in focus to Lathe Ordinals. I should have Lathe Opetopes, a library that’s just focused on data structures that correspond with a mathematical concept of opetopes.

(Ordinal-sized opetopes would naturally go into Lathe Opetopes, not Lathe Ordinals, since opetopes are the more obscure of the two concepts.)

Once I pull this code out of Punctaffy and put it there, what remains in Punctaffy will be focused on macro systems. Just as quasiquotation-shaped macroexpansion can be a Cene library rather than part of the language design, I can treat Punctaffy as the corresponding quasiquotation-shaped macroexpansion library for Racket. Since I put most of my Cene-style libraries for Racket in Lathe, Punctaffy might become “Lathe Punctaffy.”

(Punctaffy should probably not become “Lathe Quasiquotation,” since quasiquotation is only one of the operations it’s good for. And probably not “Lathe Hypersnippets,” since I’m not sure I think of hypersnippets and opetopes as very distinct concepts at this point. But hey, I might just be finding excuses to keep the name “Punctaffy” around. I love that name.)

Wrapping up

For some reason I’ve been bringing a lot of optimism to my programming lately. I suppose it’s truly because I’m back to the state I was in two years ago, where I was hacking away on Cene and making lots of progress, without all the hard problems of hypersnippets getting in the way.

It’s important to me to get Cene working. I have so many other projects I’d like to build if only I had a language stable and extensible enough to build them in. Two years ago, Cene was shaping up to be the most fully polished language I’d ever built, with practical features like building Cene projects from the command line, full JavaScript FFI integration, at least the skeleton of some comprehensive reference documentation, and so on.

But then the idea of hypersnippets seemed like it could solve source location tracking and extensible quasiquotation once and for all if I could get it to work, and just about every time I came back to Cene, I felt like that was what I had to focus on.

Now, hypersnippets are actually doing what I want them to, and if they prove to be broken again, they aren’t that critical to Cene anyway.

So I’m back on the road to making a fully polished programming language and libraries, documenting them, and actually putting them to use. Pretty hopeful about it!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s