Channels ▼


Nimrod: A New Systems Programming Language

The obvious thing to do with a formula is to evaluate it. The following proc does just that. It requires a mapping varToVal from the variable name to its value:

from math import pow

proc evaluate(n: Formula; varToVal: proc (name: string): float): float =
  case n.kind
  of fkVar: varToVal(
  of fkLit: n.value
  of fkAdd: evaluate(n.left, varToVal) + evaluate(n.right, varToVal)
  of fkMul: evaluate(n.left, varToVal) * evaluate(n.right, varToVal)
  of fkExp: pow(evaluate(n.left, varToVal), evaluate(n.right, varToVal))

Now, to check whether a formula is a polynomial (to see if we can easily differentiate it, for instance), we can use the following code:

proc isPolyTerm(n: Formula): bool =
  n.kind == fkMul and n.left.kind == fkLit and (let e = n.right;
    e.kind == fkExp and e.left.kind == fkVar and e.right.kind == fkLit)

proc isPolynomial(n: Formula): bool =
  isPolyTerm(n) or
    (n.kind == fkAdd and isPolynomial(n.left) and isPolynomial(n.right))

isPolyTerm is quite ugly. Pattern matching would be much nicer. While Nimrod does not support elaborate pattern matching beyond case out-of-the-box, it's quite easy to implement it thanks to the sophisticated macro system: For pattern matching, we define a macro =~ that constructs the and expression at compile time. Then the code can look like this:

proc isPolyTerm(n: Formula): bool = n =~ fkMul(fkLit, fkExp(fkVar, fkLit))

But this is still not as nice as it could be: The point of Nimrod's macros is that they enable DSLs that make use of Nimrod's lovely infix syntax. In fact, that's a conscious design decision: Macros do not affect Nimrod's syntax — they can only affect the semantics. This helps readability.

So here is what we really want to support:

proc isPolyTerm(n: Formula): bool = n =~ c * x^c

Where c matches any literal , x matches any variable, and the operators their corresponding formula kinds:

proc pat2kind(pattern: string): FormulaKind =
  case pattern
  of "^": fkExp
  of "*": fkMul
  of "+": fkAdd
  of "x": fkVar
  of "c": fkLit
  else:   fkVar # no error reporting for reasons of simplicity

Note that for reasons of simplicity, we don't implement any kind of variable binding, so 1 * x^2 matches c * x^c as c is not bound to the literal 1 in any way. This form of variable binding is called unification. Without unification, the pattern matching support is still quite primitive. However, unification requires a notion of equality, and since many useful but different equality relations exist, pattern matching is not baked into the language.

So here's the implementation of the =~ macro in all its glory:

  import macros

  proc matchAgainst(n, pattern: PNimrodNode): PNimrodNode {.compileTime.} =
    template `@`(current, field: expr): expr =
     newDotExpr(current, newIdentNode(astToStr(field)))

   template `[email protected]`(n, pattern: expr): expr =
     newCall("==", [email protected], newIdentNode($pat2kind($pattern.ident)))

   case pattern.kind
   of CallNodes:
     result = newCall("and",
       n [email protected] pattern[0],
       matchAgainst([email protected], pattern[1]))
     if pattern.len == 3:
       result = newCall("and", result.copy,
         matchAgainst([email protected], pattern[2]))
   of nnkIdent:
     result = n [email protected] pattern
   of nnkPar:
     result = matchAgainst(n, pattern[0])
     error "invalid pattern"

  macro `=~` (n: Formula; pattern: expr): bool =
   result = matchAgainst(n, pattern)

In Nimrod, a template is a declarative form of a macro, while a macro is imperative. It constructs the AST with the help of an API that can be found in the macros module, so that's what line 1 imports. The final macro definition is in line 25 and it follows a fairly common approach: It delegates all of its work to a helper proc called matchAgainst, which constructs the resulting AST recursively. PNimrodNode is the type the Nimrod AST consists of. The Nimrod AST is structured quite similar to how we implemented Formula, except that every node can have a variable number of children. n[i] is the ith child.

The various function application syntaxes (prefix, infix, command) all map to the same AST structure kind(callee, arg1, arg2, ...), where kind describes the particular syntax. In matchAgainst, we treat every call syntax the same with the help of macros.CallNodes. We allow for a(b) and a(b, c) (line 15) call syntaxes and construct the AST representing an and expression with the help of two @ and [email protected] templates.

[email protected] constructs the AST that corresponds to n.field and a [email protected] b constructs a.kind == pat2kind(b). Line 18 deals with the case when the pattern only consists of a single identifier (nnkIdent), and line 20 supports () (nnkPar) so that grouping in a pattern is allowed.

As this example shows, metaprogramming is a good way to transform two lines of long ugly code to a short beautiful one-liner at the cost of 30 lines of ugly code dealing with AST transformations. However, the DSL we created here pays off as soon as there are more patterns to match against. It's also reasonably easy to abstract the =~ pattern-match operator so that it operates on more than just the Formula data type. In fact, a library solution that also supports unification is in development.


Nimrod is open source software that runs on Windows, Linux, Mac OS, and BSD. In addition to generating C and JavaScript, it can generate C++ or Objective-C. The compiler can optionally enforce all kinds of error checking (bounds checking, overflow, etc.) and it can perform extensive optimizations.

It has an extensive standard library and many ported libraries. In addition, it has wrappers for most of the premier C libraries (including OLE, X, Glib/GTK, SQLite, etc.) and C-based languages (Lua and Tcl). If you're searching for a systems programming language that provides higher-level constructs and extensive metaprogramming, but boils down to C, Nimrod might well be what you're looking for.

Andreas Rumpf is the creator of Nimrod.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.