Qi++: Qi but with Real Macros

[countvajhula]

Just kidding, it isn't really called Qi++ . It's the same old Qi, but it now does have real macros!

What does that mean? Well, some time ago this paper about making DSLs "macro extensible" was doing the rounds in the community. Unfortunately it was way over my head and so, covetous of the kind of macro-extensibility it talked about, I implemented a simple hack to achieve it in Qi in cunning fashion. This meant that the language could indeed be extended by using macros, but the approach taken being superficial meant that user-defined macros could in a sense only be second class citizens of the Qi language.

Shortly after I posted about the initial macro-extensibility approach, Michael Ballantyne (who wrote that paper! Along with Alexis King and Matthias Felleisen) reached out and offered to help implement a proper solution in Qi. By his generous sharing of expertise (and the support and encouragement of his advisor, Matthias), I'm pleased to report that Qi is now properly macro extensible, in a way that essentially puts it on even footing with Racket as a basis for writing language extensions and even new DSLs. As anyone who uses macros would appreciate, this is a major improvement in the language and opens up a lot of new possibilities. Some of these possibilities are foreshadowed in some exercises in the docs, including:

• adding monads (a new feature) to Qi
• adding pattern matching (a new DSL)
• and adding a custom compiler (for faster performance)

And I am sure that you will think of a lot more

Other things in this release:

• More docs. A quick wc -w estimate suggests Qi now has over 50 pages of docs! (at 300 words per page). There are some ideas guiding the organization of the docs that I hope make them easy to navigate and efficient. If you have any problems finding information please let me know.
• The "probe" debugger (for debugging flows) got an upgrade. Now there's no need to define flows using a debugging-specific macro in order to be able to debug them using probe -- it can debug existing flows as written.
• A convenient way to embed DSLs like Deta and Sawzall into Qi

Btw, as this release leverages features only present in Racket 8.3+, older (i.e. <= 8.2) versions of Racket will go into maintenance mode and only receive bug fixes going forward.

Finally, I also want to give a special shout out to D. Ben Knoble, whose early input led to many improvements in Qi 1.0.

Alright enjoy!

-Sid

[dstorrs]

Could you give us a quick summary of what Qi is and what it can do?

[scolobb]

@countvajhula recently announced Qi here: Qi tutorial and Jay's challenge

A brief summary taken from Qi: An Embeddable Flow-Oriented Language :

An embeddable, general-purpose language to allow convenient framing of programming logic in terms of functional flows.

I find that this section nicely presents some more details if you are interested.

Note that I am not a Qi user, but that I find the concept very interesting

[countvajhula]

This section of the docs provides an overview, but here are a few different ways I'd describe it:

• It's a language that's data-oriented instead of control-oriented
• It's a language where your program is a function that is made up of functions, i.e. functions are the building blocks and there is nothing smaller nor anything bigger (even literal values like 1 are treated as functions generating them)
• It's a bit like programming with analog circuits, where the "circuit components" are functions
• It's a language for working with values directly instead of collections of values

What can it do?

It's a general-purpose language but it is most appropriate for cases where you are working with data of any kind, and would prefer to do things in a functional way. This section provides some examples of where you might use it.

How to use it?

The language is not a #lang, but rather, it is an "embeddable" DSL. This means that you can use it in Racket or any other host language via a normal macro, and mixing Racket and Qi in the same source file is easy.

[Laurent.O]

@countvajhula In hindsight, what main points would you explain to yourself to understand the concepts in the macro-extensible DSLs paper?

[countvajhula]

That is a great question. I'm not sure I'll have a good answer since I wouldn't really call myself an expert here, but I'll do my best.

There are two main kinds of DSLs: embedded, and hosted. These are distinguished primarily by their "interface macros". Interface macros are just the set of macros which you use to implement a DSL (thus forming the "interface" between two languages). For instance, with Sawzall, the interface macros are aggregate, slice, where, among many others. With Racket's language for specifying contracts (racket/contract), the interface macros are and/c, or/c, -> and more. With Qi, the interface macro (singular) is flow.

Languages that have more than one interface macro are called "embedded," and languages that have just one are called "hosted."

Embedded languages are the most seamless since the DSL appears to be part of the host language. E.g. once you do (require sawzall), you can use the entire DSL just like any other Racket forms.

The tradeoff is that embedded DSLs must:

1. share their binding space with the host language, and so cannot have forms named and and if, for example.
2. always rely on the host language expansion and compilation process since such languages are wired directly as extensions of the host language (we'll see why this matters soon)

Hosted languages add an extra level of indirection -- e.g. once you (require qi) you can use the entire language in your code, but only by wrapping the expressions in (flow ...). This adds a seam, but it gains the two advantages mentioned above.

First with naming, for instance Qi has an and form which composes predicates by conjoining them (e.g. (and positive? integer?)). Likewise, Racket's pattern matching language (another hosted DSL) also has and and or forms.

Second -- and now we're getting to the heart of what the paper talks about -- with expansion, a hosted language gains more control here because the entire language is specified as subforms in a single macro (flow, in the case of Qi) whose responsibility is to generate Racket code from whatever the user has written. How we do it is up to us. Naively, we can fulfill expansion by the interface macro (e.g. flow) just recursively invoking itself until Racket code is generated. In this case, it is just a simple extension of the Racket expander and isn't doing anything fancy. This is how Qi 1.0 worked.

The paper proposes that, instead, the interface macro should do its job in two phases: (1) expansion to a core language, (2) compilation of that core language. This allows the language to be faster and smaller, while also supporting extension by users via macros.

In retrospect, we can see that in Qi 1.0, these two phases were conflated and there was no separation between them.

In order to achieve this goal, the paper proposes changing the implementation of the language itself from a "flat" layout (where all of the syntax is specified in a single macro) to a two-level layout, where there is a small core language on the lower level, and any number of macros on the higher level which simply expand into the core forms. The "expansion" part of the process is now all about expanding the macros (upper level) into the core syntax (lower level) of the language. Then, the compilation phase kicks off and compiles the core language into Racket. This is exactly the architecture of Racket itself: expansion of macros to a core language (fully expanded Racket), followed by compilation to a lower level language (Racket bytecode). Having this architecture allows us to implement optimizations at the level of abstraction of the DSL, where it is possible that there are optimizations that could be done which could no longer be reliably done at the level of Racket expressions since some information may be lost at that stage -- just as the Racket compiler does some optimizations even though lower level languages in the stack (e.g. C) will be compiled too. This allows your DSL to potentially recoup the performance losses it might incur from its idioms that may deviate from the host language idioms.

Incidentally when I wrote Qi I didn't set out to write a particular kind of DSL. It's only upon reading the paper that I, like Monsieur Jourdain, can say that I have been speaking a hosted DSL all along And as it happened, that was exactly the kind of DSL that the paper is applicable to. Finally, hosted DSLs can also be embedded into the host language, to get the best of both worlds.

References for further reading:

Macroexpand anywhere with local-apply-transformer! -- a blog post by Alexis King covering how to expand subforms on demand within the context of macro expansion.

Qi compiler -- describes the planned Qi compiler which will complete the second phase described in the paper.

[Laurent.O]

Thank you very much, it's very informative!

[Jimi]

This seems like a really excellent language. I'm new to programming, I have read your docs and discussions, but I'm curious are the concepts in qi the same as what is called tacit programming, or point free programming, or function level programming? ((which I think are all roughly the same thing as far as I can tell having done a quick Wikipedia...) or is that way off?

[countvajhula]

Hi Jimi, welcome! You know, it never occurred to me that someone new to programming would consider using Qi as a first language (or among the first). I hope you have fun with it!

Coincidentally, I just looked up "tacit programming" earlier today in an unrelated context and learned that it's a synonym for point-free programming. Now, point-free is a somewhat polarizing subject. On the one hand, it allows you to express your code in the most economical way when you are writing it, with no extra words. On the other hand, "extra words" sometimes are extra clues when you are reading the code. I've heard it said that point-free code is fun to write but hard to maintain, and there is some truth to this.

Qi is essentially point-free, meaning that you can write code purely by assembling functions and can avoid naming the arguments altogether -- in essence, describing what you are trying to do and how to do it, but not what is being acted upon. But, it also allows you to use identifiers in many common cases. In fact, the docs recommend that you do use names in cases where being point-free would lead to "incidental" and unnecessary complexity. So to answer your question, yes, Qi is point-free, but it favors clarity over adhering to one style of programming. I think in practice there is a balance of identifiers and point-freeness in clear code, and Qi gives you the flexibility to find that balance.

[Jimi]

Thank you for the reply!
Briefly about myself, I am an almost complete novice to programming. However I research a fair amount on a topic before committing. programming being so vast, lots of places to start, and so little time to waste.. My job doesn't demand programming, except R is encouraged for statistics if participating in research, so that is my real start, a dsl for stats.
after a lot of research, for a self guided programming education, putting aside low level languages and web programming, I thought to start with racket, and if there's time, an apl type language, which I may never get around to...
Apl, which apart from the algorithm symbols and arrays, from what I've read is also a point free language, to varying extents depending on the implementation. Reading around Apl is, I think, maybe how I came to be aware of this paradigm.
In my opinion Qi is another exciting and excellent reason to use racket, along with so many of it's other facets and I'm grateful for your work on it. Also incidentally and off topic, I saw your talk on the emacs package rigpa (I think that was the name) which I confess I havnt tried yet, but it was also very excellent and the concept very impressive.

[countvajhula]

Briefly about myself, I am an almost complete novice to programming. However I research a fair amount on a topic before committing. programming being so vast, lots of places to start, and so little time to waste.. My job doesn't demand programming, except R is encouraged for statistics if participating in research, so that is my real start, a dsl for stats.
after a lot of research, for a self guided programming education, putting aside low level languages and web programming, I thought to start with racket, and if there's time, an apl type language, which I may never get around to...

That sounds like a very disciplined approach you've taken. Learning can take time but it will eventually click, just like learning human languages (which is much harder than learning programming languages!). R is a great start. Good luck!

Apl, which apart from the algorithm symbols and arrays, from what I've read is also a point free language, to varying extents depending on the implementation. Reading around Apl is, I think, maybe how I came to be aware of this paradigm.

Funnily enough, the "unrelated context" in which I read about "tacit programming" yesterday was in learning about APL :). Many people have brought up similarities between Qi and APL, and so I made a first attempt at comparing these languages. I hope to learn more about APL myself.

In my opinion Qi is another exciting and excellent reason to use racket, along with so many of it's other facets and I'm grateful for your work on it. Also incidentally and off topic, I saw your talk on the emacs package rigpa (I think that was the name) which I confess I havnt tried yet, but it was also very excellent and the concept very impressive.

Thank you so much for the kind words. I haven't had a lot of time to work on Rigpa lately but I intend to return to it at some point.

[Jimi]

That's really cool! I must tell you, I fortuitously came across this podcast, via a YouTube video..
The Array Cast: Episodes — The Array Cast
, apologies if know about it already.
The tacit programming episode, the hsu episode and the bqn episode are all I've listened to but I've found they are all amazingly pertinent, and above my head quite often but I do get the gist, without the detail unfortunately,
you will probably get far more out of it than me I hope.

[countvajhula]

These look great, thanks for passing them along! You may also be interested in these slides that user Sarna posted on Discord about APL, which also seem great. (but also, to the point raised in the other thread about transitioning to the practice stage of coding, at some point you gotta stop reading and just dive in!)

[Jimi]

Yes you're completely right, thank you for the help!