Obsidian

What the heck is generative programming anyway?

The idea behind generative programming is that rather than writing a program in one language and having it either interpreted and executed directly or compiled to a binary and then executed, we write a program in a host programming language that outputs a source file in a target language. This might seem strange at first; what's the point, you might ask? The advantages are twofold.

First, we can eliminate repetitive parts of our program by abstracting their generation in the host language. Suppose we have a sparse matrix that's fixed at compile-time and we want to multiply it by another matrix that's provided at runtime. One efficient way to do this is to unroll the loops for rows of the fixed matrix that are more sparse; however, doing that by hand would be tedious and would need to be redone if the compile-time matrix changed. Instead, if we build this program programmatically, we can avoid the manual labor and fine-tune performance much more efficiently. Now, you might say this can be accomplished with macros just as effectively, and you would be right, for the most part. If you're constrained to using C or C++ or CUDA, say because of library dependencies, you don't have macros to work with (decent ones anyway). Generative programming gives metaprogramming capabilities to languages that don't support it natively.

The second advantage is that because we have access to the full semantic model of our program at compile-time, we can verify the correctness of our program in the same language as we're writing it. We can even do so as we build our program up from expressions. Suppose we're writing a websocket library and we want to ensure that websockets are initialized exactly once before they're opened. This could be accomplished using dependent types in a language like Idris, but first of all Idris is much too cumbersome to use for practical tasks at the moment, and second, if as before we have library dependency constraints, we aren't at liberty to choose a target language at all. Generative programming gives an alternative to dependent types that's more flexible and intuitive.

Why a new programming language?

Of course, there are excellent generative programming libraries available for other language. One notable example is Scala's LMS library, which is an extremely powerful generative programming library that can target a number of languages including CUDA and C. However, generative programming in Scala is less than streamlined. The sample snipped from the LMS webpage is this:

class Vector[T:Numeric:Manifest](val data: Rep[Array[T]]) {
  def foreach(f: Rep[T] => Rep[Unit]): Rep[Unit] =
    for (i <- 0 until data.length) f(data(i))
  def sumIf(f: Rep[T] => Rep[Boolean]) = { 
    var n = zero[T]; foreach(x => if (f(x)) n += x); n }
}

Not exactly the cleanest code in the world. Obsidian solves this with metaprogramming. In Obsidian, a generative programming library might let the same code might be written as:

class vector(data)
    def foreach(f)
        for j in 0..data.length
            f(data(j))
    def sumif(f)
        n = 0
        ...

What it does

Obsidian lets users define new keywords, essentially multiline macros with minimal boilerplate syntax, which means we can have a separate keyword for Obsidian functions and for functions that represent a chunk of code in the target language. Keywords also receive a raw lexeme stream, which means that they have the liberty to use their own syntax entirely; if a generative programming library designer wished, they could even come close to closely imitating the syntax of the target language!

Challenges I ran into

I spent about two hours this morning finding a bug in the parser generator library I used, TatSu, that prevented the # symbol from being consumed by the lexer. I'll probably have to submit a pull request so that users of Obsidian don't have to manually fix TatSu before they can run the interpreter.

What's next for Obsidian

So far, I've only made the interpreter for the language. The next step will be to write the first generative programming library and demonstrate the power of keyword definition and dynamic syntax.

Built With

• python
• tatsu