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.

Continue reading

Advertisements
Status

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.

Continue reading

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.)

Continue reading

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.

Continue reading

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.

Continue reading

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.