Sep 28, 2011


The journey to macroland keeps amazing me!

Take splices. At first they seemed just a clever response to AST composability issue. Then I figured out that splices can be used to drastically simplify pattern matching. But even that didn't exhaust the bag of tricks provided by splices!

A few days after the pattern matching revelation, I learned how schemers use ellipses to write declarative syntax transformers. Say, we want to code up the following syntactic transformation: (let ([var val] ...) body) = ((lambda (var ...) body) val ...). Clear and concise, but imagine how ugly this will become when we'll try to transform this informal notation into executable code.

This problem has been addressed by Eugene Kohlbecker, a researcher from Scheme community. He extended the macro system to literally understand those ellipses:
(define-syntax my-let
  (syntax-rules ()
    [(my-let ([var val] ...) body)
      ((lambda (var ...) body) val ...)]))
Amazing, huh? But that still doesn't cover all the fancy uses of splices. For an icing on the cake, take a look at string interpolation example from Nemerle:
public static Render(this exprs : list[PExpr]) : String
  $<#..$(exprs; ", "; Render)#>

Sep 27, 2011

Talk at Scala meeting

Today I gave a talk about macros at Scala meeting. The slides start with a basic example of a compiler macro, proceed with more advanced stuff from macrology and conclude with project ideas:

Sep 20, 2011

Epiphany about quasiquotes

Quasiquotes do not have to conform to the syntax rules of the host language. In fact, they can be written in arbitrary style, as long as this style somehow exposes antiquotation facilities.

With such quasiquotes one can, say, concisely implement type-safe regexes or easily express peephole optimizations. Read more on that in "Why It’s Nice to be Quoted: Quasiquoting for Haskell".

Sep 18, 2011

Macros in a typed language with syntax: state of the art

Today I've read two fundamental papers on Nemerle macros: "Syntax-Extending and Type-Reflecting Macros in an Object-Oriented Language" (referred to as "the thesis") and "Язык Немерле, часть 5" (referred to as "the article", sorry, folks, it's in Russian). Also I had a fruitful conversation with VladD2, the principal developer of Nemerle (kudos, Vlad, for your desire to help and very detailed explanations). Some preliminary findings:

1) Quasiquotation is very elegant. It only takes three intuitive language constructs (quotation, antiquotation, splicing, see the section 8.3 of the thesis for the summary and the section "Квази-цитирование" of the article for the details) to significantly simplify parsing and generation of abstract syntax trees. I was especially impressed by the usage of antiquotes and splices together with pattern-matching. Personally for me, the beauty of quasiquotations is especially striking after the troubles with composability of LINQ expression trees.

2) However, there's a painfully familiar problem with LINQ that still persists. How do we lift (i.e. transform to an AST) code from the outer world? Staging adepts take it easy - they lift all functions and values that have staged types (explicitly in tagful style or implicitly in tagless style, see the previous link to find out what this means) and ignore everything else. This comes at a price of syntactic overhead of extra typing (pun intended) + potential performance degradation due to possibly tagful AST representation (take a look here for more details), though the interop with the outer world is kinda ok. With macros we have to bite the bullet - in most cases one needs explicit antiquotations, and this imposes overhead at every callsite that references external code that one wants to lift. There's also a non-obvious dilemma of whether we allow macros to see values from their definition scopes (see the section 2.3.3 of the thesis).

3) Also it's completely unclear how to implement orthogonal codegeneration via macros in a statically typed OO-language. Firstly, macros most likely need to be moved to a separate unit of compilation. Secondly, when writing a macro we have a choice: to bear with untyped ASTs and have a possibility to generate new types, or to enjoy typed ASTs at the cost of locked typespace (don't even think about what happens if we add type inference to the mix). Thirdly, object-orientedness pours even more fuel to the fire since we get a completely heterogeneous concept of classes that do not compose with functions + there's inheritance. This all brings us to a classic nightmare familiar from stateful programming, when operations are randomly prohibited or allowed depending on the phase of the Moon. After all, it's not surprising that F# designers did not implement code generating macros and only went for read-only quasiquotations.

4) Regarding error messages and debugging for the code generated during macro expansion - it's not as bad as it seems. Along with generating executable code we can also generate surrogate source code for macro expansions (we do have an AST after all) which can be used to produce sane debug info. Of course, the original line numbers will be corrupted (yep, we can restore them with lenses, but stepping in the debugger will still be crazy) and there's a glitch with stack traces, but that's at least something, huh? Staging guys have much harder time here (e.g. see the slide #15 of the LMS presentation).

5) Moreover, it's desirable for macros in a language with syntax to have some control over the parser (e.g. see the section 6 of the thesis and also the "Genuine, Full-power, Hygienic Macro System for a Language with Syntax" tech report). This enables the programmer to implement such useful thingies as custom modifiers for declarations (think, "async method" or "method ... precondition ...") or even completely new syntactic constructs. Frankly speaking, this is useful, but not mandatory: the prior can be implemented with annotations that trigger macros for their annotees, while the latter is kinda already in Scala (e.g. see the canonic implementation of the "while" loop).

All in all, at the moment the concept of macros in mainstream programming languages looks to me like a weird mix of butterflies, unicorns, spiders and worms. Template Haskell, here I come.