Slang: Review of 2012

Already the first quarter of 2013 is behind us, but I wanted to take a look whether I accomplished the goals I set for Slang development in 2012. I’m not going to reiterate the goals here, but almost none of them were completed.

I wanted to bring the language into a usable form, but so far there is still a lot of work to do. I wanted to make the compiler open source, but I’m still not sure at which point I would like to do that. I think I will postpone that quite a bit, because I don’t have the time to run an open source project at the moment (and parts of the compiler are still full of horrible hacks). Actually, lack of development time was one of the things that prevented me from fulfilling the goals. I worked on Slang mostly during vacations and when I found a drive to start work during other times I would continue for a couple of weeks and then take a break for a few months.

I am suspecting that development will continue at a similar pace. I have made some progress, though, sporadically during 2012 and more continuously during the last few weeks.

New Parser

I think I spent most of my Slang development time last year on the new parser, using the mixfix parser combinators I blogged about (sorry, I kind of forgot to post the third part of that). I have improved the parser framework a lot since then, but it does have a downside of being quite slow for large programs, even with Packrat parsers. So I have some further work to do here, like maybe replacing the whole parser again, but I will probably leave that to some unknown future date.

Custom Operator Precedence Rules

The new mixfix parser theoretically enabled a modular grammar: the default grammar can be relatively small, but programs could define their own prefix, postfix, infix and closed operators and their precedence rules. And recently, I made that actually work. You still can’t quite define a grammar per Slang source file, but you can add operator graph (.ops) files to the list of compiled files and together with the standard rules, they will define the grammar for that compiler run. Some examples.

New Compiler Infrastructure

I just finished the initial work on this, a step towards separate compilation: instead of including library code into the source file being compiled, now the new Slang compiler driver can compile multiple source files at the same time, but still requires that the library sources are available. The end result is linked together with the LLVM IR linker.

Slang IDE

I started work on an Eclipse-based Slang IDE. Currently it includes syntax highlighting, error reporting, a few quick fixes, and quick-assist for rewriting expressions to use different aliases of methods. E.g. if you write x.times(y) you can then click Ctrl+1 and select “Use alias: *”. Then the expression will be rewritten to x * y. This is much more useful if you have Unicode operators that can’t be easily typed. Another example: you write array(1), Ctrl+1 suggests “Use alias: subscript” and selecting it turns the expression into array₁

The IDE also shows warnings and errors with squiggly lines, and I added a few more useful warnings to the compiler and improved the messages.


This is still in progress, but for some programs, Slang compiler can now emit DWARF debug info, and the programs can be debugged using the GNU Debugger. I was quite pleased to get that working, and together with the IDE, and new compiler driver, it has made Slang much more usable for myself.

Next Steps

This time, I don’t want to give any deadlines, but the next steps are to make the tooling more usable, improve error messages, add some of the language features I didn’t get to add in 2012, etc. I think I might even release a build in the form of the Slang IDE with the compiler embedded, even if it will not be open source.

I have various language features in mind that I want to explore, such as proper generic types, some form of dependent types, Strings, IO, better interoperability with C, JVM back-end. Strings and IO are pretty much given, and generics as well. Not sure how soon I’ll get to the other things.

I think I will pretty much be doing pain-driven development: what is currently giving me most pain will get fixed first. I think actually generics might be the thing, because adding collection methods for only a specific type of arrays is no fun.

Lines of Fire: Thinking about modular board game design

Long time no blag. Last time I wrote about a board game I’m working on. I actually let the project lay dormant for a few months, because I wasn’t completely happy with the design and was hoping to come up with new ideas after a pause. Which I did, but I’ll talk about those on some later date.

The idea for Lines of Fire started with Bomberman and the first prototype wasn’t much more than the multiplayer Bomberman formula turned into a turn based, physical game. Later I started adding a completely different theme, which might actually end up working quite well. I also experimented with other additions that had nothing to do with Bomberman. And I think I’m going to continue on that route, because maybe Bomberman isn’t such a well-designed game after all, or at least doesn’t directly translate into a well-designed turn-based game (or at the very least, my translation was poor). I think this might let down the players who already played it and liked its similarity to Bomberman, but if I manage to turn it into a better game than it was, then that’s fine. The core of the game will still retain some (or even a lot of) resemblance to the first prototype, though.

At the moment I have several new ideas that I think are really cool, and I wrote them down as a preliminary additional rules document. I stress “additional”, because I want to keep the game modular. It’s mostly because I have done so much experiments with variants that I’ve later reverted that I just don’t have a vision for a single set of rules that would be the one true embodiment of the game idea. Maybe the lack of such vision means that I shouldn’t be designing this game in the first place, or should just do my best with one variant, but at the moment I’m hoping I can in fact come up with some set of modules that players can combine to play the game the way they want to play it. This idea crystallized for me today, after listening to a recent 3MA episode about modding, modularity and house rules in board games.

Modularity and moddability make me think about software. I think we understand software modules pretty well, and why not try to actually create the game rule/component modules as software modules. Modelling a game as software should give it another desirable property: as long as I’m modelling the game systems well enough as type-safe code, I should be able to find problems in the rules that I won’t find if they are just paragraphs of text in a document. I should also be able to find corner cases, and verify properties about the software (although I’m not going quite as far as to use something like Coq for this, I’m probably sticking with Scala) which implicitly verifies the game rules as long as they are directly based on that software. It should also help me test changes to the rules by myself without having to do a lot of work and setup with physical game pieces.

As a result of such thinking, I have in mind a small project to start turning the current game rules into a set of software modules. I should have a tool that lets me play the game digitally, with just a crude visual representation and ability to control multiple players in turns. The game components and rules should be modular, so that for each play I can turn some modules on and off, or modify their parameters. When I have implemented the game in its current state, I can find problems with the rules and hopefully simplify them by refactoring or modifying the program.

What I want to achieve in the end is that the modules being represented in software actually enable me to find the best places for the module boundaries, and a way to get to a really small core module that can be learned and played quickly, with other modules that can be layered on top of that to make the game more interesting. I’m also hoping that I will then find a good way to lay out the modular rules in a linear rulebook so that the modules are easy to combine and the book itself easy to use for reference.

Mayhaps I will document this process somewhat on this blog, or on BGDF.

Lines of Fire — Evolution of a Prototype

During my vacation this summer, I somehow ended up designing a board game. The idea came to me strangely — I had seen a board game in a dream, but all I could remember when waking up was an image of what the board looked like. I thought it looked a bit like Bomberman, and that’s when I had the idea — why not take the gameplay from Bomberman and put it into a board game.

Creating the first prototype took only a few hours, and I thought I had a somewhat fun game. I called it Bombarena.

A lot of testing followed, first by myself and then with others. I’ve put tens of hours into it since then and made tens of smaller and larger improvements. Version 0.2 got only a couple of play tests, but I took some suggestions from the players and it was soon replaced with version 0.3, which added cards to spice up the game.

Version 0.4 is in progress and for now I’m mostly focused on simplifying, clarifying, balancing and polishing. I gave the game a new name “Lines of Fire”, rewrote the rules (PDF), which should be pretty solid for the main game variant now. I imagine that the basic rules will not change too much any more — what remains is mostly balancing; further play testing will tell if I’m right. I also created new tokens and improved the look of the board (making set-up related elements stand out less).

The next version will probably focus on balancing the ability cards and I hope to make it available for wider play testing soon, in a Print & Play form. I’m finding that open source/free software (such as Inkscape, Scribus, Foxit Reader) has all kinds of issues with printing, though, so making good printable documents available is a bit of a challenge.

Syntax Matters in Slang

This post was inspired by Ola Bini’s notes on syntax. I agree with most of Ola’s thoughts. I’m not convinced that repetition aids reading or improves syntax, and think that optimising syntax for writing is mostly irrelevant. I might agree less about the familiarity of syntax. I would love it if people, including me, were more open to trying languages with unfamiliar syntax, but the familiarity is important to many on some level.

Some of these thoughts form the basis for Slang’s syntax. I’m not quite ready to define The Zen of Slang, but I can give a shot to stating some of the underlying principles behind its syntax:

  • Reading code is an order of magnitude more important than writing code
  • You should still be able to type a lot of code quickly in any text editor
  • Concise is good, repetition is bad
  • There can be multiple ways to write the same thing, but one way should be canonical
  • Familiarity is good, in this case with:
    • Scala
    • to a lesser extent, other curly brace languages
    • mathematical notation

How these goals actually effect the syntax deserves more explanation

Reading > Writing

We read code more than we write it, and reading is more important. I hope this is accepted by everyone nowadays and I’m not going into why. But how to optimise for readability is another question, and probably highly subjective. In Slang, I am experimenting with syntax that I think is readable, but that might not be always easy to write.

Slang makes very few restrictions on what Unicode characters are allowed in identifiers — I believe that well-known mathematical operators in code that deals with maths are more readable than English words. The ability to write close to mathematical notation in many cases is enhanced by limited mix-fix operator support, but this is really less about syntax and more about libraries. Slang’s standard libraries will prefer well-known mathematical operator symbols instead of word-based method names.

A thing I really love about Scala’s syntax is the ability to define one-line methods without using curly braces.

def +(v: Vector2) = Vector2(x + v.x, y + v.y)

I’d find it incredibly distracting for readability if there were curly braces around this or if the method body was on a separate line due to code conventions. For me, such one-liners and even multi-line single-expression methods are important.

def sum(xs: [Int]) =
  loop(i := 0, acc := 0) while i < #xs do
    (i + 1, acc + xsᵢ)
  yield acc

Many methods that are based on loops can conveniently be implemented as a single loop expression because Slang doesn’t have mutable local variables (at least not yet) that would be defined in a code block, but instead prefers “anonymous recursion” for computing varying values. while is syntax sugar for making that construct more concise. There is just one loop construct, where other languages would have for loops, tail recursion, while loops, or do while loops. It’s likely that I’ll add a ‘for each’ construct, though.

There are other things to consider when thinking about code readability, but that could be a whole post or series of posts on its own.

Writing cannot suck!

Typing Unicode symbols is not easy. The solution I use regularly is to have often-used symbols in a text file, and copy them from there when needed, or to search in a Character Map application (there’s a good one in Ubuntu). This slows down writing, which often doesn’t matter if you spend more time thinking than writing anyway.

But sometimes you still want to type fast, and for that, Slang’s library will have ASCII aliases for every non-ASCII identifier. You can write ASCII names instead of Unicode symbols and replace them later when a code snippet is complete and tested. In the future, an IDE should know what the canonical forms are and do the replacement automatically.

This means there will effectively be two ways of writing many programs. Some language designers would consider multiple ways of doing things bad, but in Slang I allow it with no regrets — this comes from the desire to achieve a balance between the goals “Reading > Writing” and “Writing cannot suck!”.

Repetition is bad and multiple ways of writing things

Ok, I mentioned that non-ASCII symbols always have ASCII aliases (in fact it is mostly vice versa). Consider the following:

class Boolean {
  def xor(that: Boolean) = // intrinsic operation
  def ⊻(that: Boolean) = xor(that)

  // Methods ending with … are prefix operators
  def not…() = true ⊻ this
  def ¬…() = true ⊻ this

In the above code, we create aliases by either duplicating definitions (not, ¬) or defining similar methods where the aliases call the “canonical” method (xor, ). There is repetition in both cases and potential performance issues in the latter case if methods are not in-lined. It is how most widely used languages allow aliasing, because they are not too concerned with providing multiple ways of doing things. But Slang is concerned with that, because it helps deal with the above-mentioned tension between reading and writing. So Slang makes aliases explicit:

class Boolean {
  def xor(that: Boolean) = // intrinsic operation
  def not…() = true ⊻ this

  alias ⊻ = xor
  alias ¬… = not…

The repetition is gone — to define an alias, we only define its name and the name of the aliasee. Right now only simple identifiers may be aliased, but I might allow more complex cases later.

If you don’t like the aliases Slang provides for the standard types, you could define your own:

extending Boolean {
  alias `no way!` = not… // I hope nobody will actually do this :)

Now you can write: if collection.isEmpty.`no way!` then ...

As you can see, even spaces are allowed in identifiers, as long as the identifier is surrounded by back-ticks (same as in Scala). We can’t use the `no way!` alias as a prefix operator, though, because Slang currently allows only certain operator symbols to be prefix instead of infix. I might add user-defined precedence/fixity rules later, but not totally sure about that.

Now, I hear alarm bells sounding in some readers’ heads already. How come I’m willing to give potential Slang programmers so many tools to shoot themselves in the foot? Because I want to believe that most programmers are not stupid and the usefulness of this in the hands of smart people outweighs the negative sides.

Similarly to term aliases, there are type aliases:

type SDL_Rect = (x: Short, y: Short, w: Short, h: Short)

Familiar is good

I don’t have a whole lot to say about this, as things are not yet set in stone. I really like most of Scala’s syntax and I want to stick to something similar for the most part. Significant whitespace would be an interesting experiment, but I’m not sure if it’s a clear improvement over curly braces, which are familiar to the vast majority of programmers. Mathematical notation is complex, and varies between different fields of mathematics, blackboard and paper, and so on. But there is a part of it that is commonly understood and I would like to make some subset of that usable in Slang, although slight differences in syntax might be necessary.

Some examples:

∃! xs , x -> x == 3 // there exists only one x in xs where x == 3
2 ∈ xs // 2 is an element of xs
5 + ∏ xs // 5 + the product of xs
∛(27) + |-3| // cube root of 27 + absolute value of -3

// definition of for all on an array of integers
extending [Int] {
  def ∀…,…(ƒ: (Int) → Boolean) =
    loop(i ≔ 0, z ≔ true) while z ∧ i < #this do
      (i + 1, z ∧ ƒ(thisᵢ))
    yield z

You may have noticed

  • quantifiers (for all, exists etc.). For this purpose I allowed comma to be used in a few special identifiers: ∀…,… ∃…,… ∄…,… ∃!…,…
  • subscripts can be used to index into arrays and other indexed collections
  • Unicode aliases like ∧, ≔ and →
  • ∏… as a prefix operator
  • |…| as a closed operator

These all actually translate to method calls such as

xs.∃!…,…((x: Int) -> x == 3)


Syntax is quite important in Slang. I’m not designing it syntax-first, but syntax weighs into most considerations. I think the syntax as a whole will be somewhat familiar to many, being similar to Scala and a couple of other recent JVM languages.

The language is optimised for reading, mostly by allowing concise method definitions, a large range of Unicode characters in identifiers, but also by having some support for mix-fix operators. Aliases to Unicode symbols allow fast writing as well, and the alias definitions are made explicit in code. Lots of aliases allow one to write the same program in multiple ways, but in the future, there might be IDE support for “normalising” the syntax.

There are some new things here as well, or at least things that the vast majority of languages don’t have. One is the translation of subscript and superscript characters to their normal equivalents. Another is the loop construct, which is basically anonymous recursion similar to some functional language constructs. It turned out more flexible than I thought, and I’d like to write another post about that, soon.

Mixfix Operators & Parser Combinators, Bonus Part 2a

This is a short bonus post in the Mixfix Operator series. Part 1 was an introduction to mixfix operators and in part 2 we looked at them more closely in the context of a grammar for a boolean algebra and arithmetic language. The implementation of a parser for the language is coming next, but before that I thought it would be interesting to see what the grammar would look like if we removed the mixfix abstraction and mechanically converted the precedence graph to BNF notation.

It turns out this is not that hard if we turn each operator group (graph node) into a separate production and leave out the irrelevant productions for the types of operators we don’t have in those groups. This is especially easy in our case since we only have the same types of operators in each group. I’ll use shorthand names here for brevity.

expr ::= or | and | not | eq | cmp
       | add | mul | exp | neg | tightest

or   ::= (or | or↑) "|" or↑
or↑  ::= and | not | eq | cmp | tightest

and  ::= (and | and↑) "&" and↑
and↑ ::= not | eq | cmp | tightest

not  ::= "!" (not | not↑)
not↑ ::= eq | cmp | tightest

eq   ::= (eq | eq↑) ("=" | "≠") eq↑
eq↑  ::= cmp | add | mul | exp | neg | tightest

cmp  ::= (cmp | cmp↑) ("<" | ">") cmp↑
cmp↑ ::= add | mul | exp | neg | tightest

add  ::= (add | add↑) ("+" | "-") add↑
add↑ ::= mul | exp | neg | tightest

mul  ::= (mul | mul↑) ("*" | "/" | "mod") mul↑
mul↑ ::= exp | neg | tightest

exp  ::= (exp | exp↑) "^" exp↑
exp↑ ::= neg | tightest

neg  ::= "-" (neg | neg↑)
neg↑ ::= tightest

tightest := ("(" expr ")") | value

To be honest, encoding the whole graph as BNF is a lot simpler than I initially thought, and so is translating this into a combinator parser. It makes me think whether the mixfix grammar abstraction could be overkill. Of course, this is so easy only because we have relatively few different operators: only left-associative infix, prefix and closed. If we had more operators, with more holes in them, and different types of operators in one group (which is probably not usual, though), perhaps we wouldn’t find the conversion to be that simple any more.

Plainly this simplified scheme won’t help much with user-defined operators and precedence, so I think the mixfix parser abstraction is still useful. However, in cases where there are only a few operators/operator groups, maybe the straightforward translation of this BNF form into parser combinators is preferable. If there’s room left in the next post, I’ll include an alternative implementation based on this scheme.

Mixfix Operators & Parser Combinators, Part 2

In the previous post I introduced the notion of mixfix operators. In this post we will look at them more closely, in the context of an actual grammar. In the next part we will implement the parser for this grammar, look at performance issues and try to fix them with packrat parsers.

We will implement a simple language that consists of boolean algebra and integer arithmetic expressions. The grammar for the language looks like the following (we’re only considering tokens here and assume that a lexical parser has already identified literals, identifiers and delimiters in the text)

statement   ::= expression | declaration
declaration ::= variable ":=" expression
expression  ::= ??? | value
value       ::= literal | variable
literal     ::= booleanLiteral | integerLiteral
variable    ::= identifier

What should the expression productions look like, though? In examples of parsers and grammars we can commonly find an arithmetic expression language described with concepts of ‘factor’ and ‘term’ to create a precedence relation between addition and multiplication:

expression ::= (term "+")* term
term       ::= (factor "*")* factor
factor     ::= constant | variable
               | "(" expression ")"

This seems simple, but when we add more precedence rules, it can get quite complex, especially if we are writing a parser for a general purpose programming language instead of a simple expression language, and we also do semantic actions (create AST nodes) in the parser. This also makes the set of operators rather fixed: you might have to change several grammar productions to add a new operator with a new precedence level. I didn’t even try building Slang’s precedence rules into the grammar in this fashion.

Mixfix parsers still make the precedence part of the grammar, but there is a layer of abstraction there: we describe operators and their precedence rules as a directed graph, where (groups of) operators are the nodes and precedences are the edges. Then we instantiate the grammar with that particular precedence graph.

Before getting to the precedence rules in the language we are about to create, lets look at the operators it will have. In the list below, _ means a hole in the expression that can contain any other expression that “binds tighter” than the operator in question. In the case where the hole is closed on both left and right, it can contain any expression at all. Only a pair of parentheses forms a closed operator in this language.

( _ ) – parentheses
_ + _ – addition
_ - _ – subtraction
  - _ – negation
_ * _ – multiplication
_ / _ – division
_ ^ _ – exponent
_ mod _ – modulo/remainder
_ = _ – equality test
_ ≠ _ – inequality test
_ < _ – less than
_ > _ – greater than
_ & _ – conjunction
_ | _ – disjunction
  ! _ – logical not

This doesn’t include many common operators in real programming languages, but it is enough to demonstrate some interesting aspects of mixfix operators and using a DAG to describe their precedence relations. I used mod instead of % to show that operators don’t have to be symbols.

Before defining the precedence rules, lets look at some sample expressions and how we want them to be interpreted, mostly sticking with existing well known precedence rules, such as those in C, Java or Scala, but occasionally deviating from them:

a + b * c      = a + (b * c)
a < b & b < c  = (a < b) & (b < c)
-5 ^ 6         = (-5) ^ 6
a & !b | c     = (a & (!b)) | c
5 < 2 ≠ 6 > 3  = (5 < 2) ≠ (6 > 3)
1 < x & !x > 5 = (1 < x) & !(x > 5)

I think that’s enough examples for now. Lets try to describe the rules behind these somewhat intuitive expectations as a precedence graph. First, we’ll put the operators into groups where all operators in one group bind just as tightly as the others in the same group. For example 1 + 2 - 3 will be (1 + 2) - 3 and 1 - 2 + 3 will be (1 - 2) + 3

parentheses   : ()
negation      : - (prefix)
exponent      : ^
multiplication: *, /, mod
addition      : +, -
comparison    : <, >
equality      : =, ≠
not           : ! (prefix)
and           : &
or            : |

Negation (prefix -) is in it’s own group so that we can do: -2 + 1. If it was in the same group with infix - and +, then it couldn’t appear next to them without parentheses because prefix operators are treated as right-associative, but most infix operators, such as - and + are left-associative. And we can’t mix left-associative and right-associative operators of the same precedence level! Why? Take the expression

1 + 2 - 3

If + and - are left-associatve, it means (1 + 2) - 3.

If - is right-associative instead, then both (1 + 2) - 3 and 1 + (2 - 3) would be right!

We could read the list of operator groups above as an order of precedence, where the first group (parentheses) binds tightest and the last group (or) binds least tight. This would be mostly compatible with many programming languages and we would have a good enough set of precedence rules right there.

However, as mentioned earlier, Danielsson’s mixfix grammar scheme describes precedence relations as a directed graph. Each of the groups above is a node in the graph, and a directed edge from one node to another a -> b means: b binds tighter than a. So lets describe these relations as a graph instead — it will be in reverse order compared to the above list where we started from the most tightly binding:

or             -> and, not, equality, comparison, parentheses
and            -> not, equality, comparison, parentheses
not            -> equality, comparison, parentheses

equality       -> comparison, addition, multiplication, exponent, negation, parentheses
comparison     -> addition, multiplication, exponent, negation, parentheses

addition       -> multiplication, exponent, negation, parentheses
multiplication -> exponent, negation, parentheses
exponent       -> negation, parentheses
negation       -> parentheses

Notice that from each group we draw the edge not into a single group, but into all of the groups that bind tighter. This is because of the non-transitivity of precedence in this scheme: each pair of operator groups that is to have a precedence relation must have an edge between them in the graph. The advantage of this is that we don’t need to describe the precedence between operators that aren’t related at all. This is one of the motivations for using a directed graph to represent operator precedence.

I hope that from the names of the operators it was clear that some of them will apply only to booleans and some only to integers. For example, the & operator isn’t defined as bitwise &, only as logical conjunction. Thus, assuming that our language is strongly typed, some of the operators can’t appear in the holes of some other operators in a correct program.

A parser doesn’t do type checking of course, but with this mixfix grammar scheme, it does implicitly do precedence correctness checking. For example 4 + 5 & 6 + 4 is not precedence correct, as we didn’t define a precedence relation between addition and and. And due to the parser’s precedence checking, this expression will not even parse.

If we had used a total precedence order instead, we would have + binding tighter than &. The expression would be interpreted as (4 + 5) & (6 + 4) but would probably yield a type error as & works on booleans, but + works on integers. We could write (4 + 5) & (6 + 4) ourselves and that would also parse, because we made the precedence explicit. Well, actually parentheses follow the same rules: remember that in our graph, () bind tighter than everything.

The fact that the parser only produces precedence correct expressions can be both a blessing and a curse.

On one hand, this allows us to view some unrelated groups of operators almost as sublanguages. In our case, boolean algebra and integer arithmetic. This might be good for implementing internal DSLs in the presence of extremely flexible user-defined mixfix operators. We could allow users to extend our precedence graph or even replace it completely with their own. If a DSL has boolean logic in it, but no arithmetic, it might have precedence relations to logical operators, but not to arithmetic operators. This would preclude arithmetic operators from appearing in the DSL without being surrounded by parentheses. Or the DSL could even disallow parentheses. Implementing this much flexibility in a host language is complicated, though. For example, the parser would have to know about any custom mixfix grammars defined in imported modules.

On the other hand, this puts some correctness checks at the wrong level. Arguably, a parser should only validate the syntax of a program and nothing else. If a simple mistake such as using a wrong operator (equal to calling a non-existing method in some languages) would prevent the whole program from being parsed, it would also prevent the compiler from doing other interesting and useful things, or reporting better error messages.

So maybe this grammar scheme isn’t ideal for a general purpose programming language. I am sticking with it in Slang for now, because the scheme is relatively simple and works for me at least as long as I’m the only user of Slang :) And perhaps there are workarounds that would allow a precedence-incorrect expression to be accepted by the parser still. But I don’t have immediate plans to allow a wide variety of user-defined mixfix operators or operator precedence.

Anyway, for our simple language, I think this scheme works well enough as long as we don’t care whether it is the parser or the type checker that reports the errors in incorrect programs. There aren’t any useful direct precedence relations between boolean algebra operators and arithmetic operators here. Only by having equality, comparison or parentheses between them, can we put them in the same expression.

Lets look at one of the consequences of our rules more closely. Many languages, including Java and C, would put most prefix (unary) operators such as ! and - at the same level of precedence, binding tighter than all infix (binary) operators. In Java, !6 == 5 is a type error because the operator ! is bound to 6, not to 6 == 5, and ! isn’t defined on integers. In our language, it isn’t necessary to have ! at the same level as -, though. Since there is no (precedence) relation between logical and arithmetic operators, !6 + 5 will not parse. But ! does have a relation to comparison and equality tests (they bind tighter), so you can write !6 = 5 and it will mean !(6 = 5).

The precedence rules that have = binding tighter than boolean operators is based on the assumption that booleans are rarely compared to each other, but multiple comparisons of other types of values are often used in disjunctions, conjunctions and complements.

To get back to the question in the beginning of the post, what would the expression production in the grammar look like instead of expression ::= ??? | value? The short answer is that we replace ??? with the mixfix grammar scheme instantiated with our particular precedence graph. The long answer would probably take an entire blog post by itself. You can read more about this scheme in the Agda paper, or look at the source code of my mixfix library. The scheme looks somewhat like the parser combinators in the following pseudo-code (~ means sequential composition):

value = variable | literal
expression = mixfixGrammar(precedenceGraph) | value

mixfixGrammar(graph) = {
  // graph - the precedence graph
  // g - an operator group, node in the graph
  // op - an operator in a group

  ⋁(parsers) = // returns the result of the first parser in the list to succeed

  opsLeft(g)   = // all left-associative infix operators in g
  opsRight(g)  = // all right-associative infix operators in g
  opsNon(g)    = // all non-associative infix operators in g
  opsClosed(g) = // all closed operators in g
  opsPre(g)    = // all prefix operators in g
  opsPost(g)   = // all postfix operators in g

  operator(op) =
    if (op.internalArity == 0)
    if (op.internalArity == 1)
      op.namePart1 ~ expression ~ op.namePart2
      // expression is an recursive reference back to the "outer" production
      // these are the internal "holes" that can take any expression

  group(g)  = closed(g) | non(g) | left(g) | right(g)    // any ops in this group

  closed(g) = ⋁{ opsClosed(g) map operator }             // closed ops

  non(g)    = ↑(g) ~ ⋁{ opsNon(g) map operator } ~ ↑(g)  // non-associative ops

  left(g)   = (left(g) | ↑(g))                           // left-associative ops
              ~ ( ⋁{ opsPost(g) map operator }
                | ⋁{ opsLeft(g) map operator } ~ ↑(g) )

  right(g)  = ( ⋁{ opsPre(g) map operator }              // right-associative ops
              | ↑(g) ~ ⋁{ opsRight(g) map operator } )
              ~ (right(g) | ↑(g))

  ↑(g) = ⋁{ graph.groupsTighterThan(g) map group } // every group that binds tighter than g
         | value                                   // or the tightest "group" of values

  return ⋁{ graph.nodes map group }

If you don’t understand this right now, no big deal — it’s late enough that I couldn’t come up with a better representation of the actual code that would fit in this post. And if you are not familiar with parser combinators I would recommend reading Daniel Spiewak’s post on the subject, at least before continuing to the next part of this series.

If you notice, the value and expression productions are referenced inside the mixfixGrammar. This is no good if the mixfix library is to be a separate module, so I actually implemented that by introducing a pseudo operator group that has a custom parser. This pseudo-group is then added to the precedence graph along with edges from every other group into that “really tight” group.

This concludes part 2. In the next part we will forget this pseudo-code and use Scala’s parser combinators and my mixfix library to implement an actual parser for the language, and maybe an AST and an interpreter as well.

Thanks to Miles Sabin and Daniel Spiewak for reviewing drafts for this series of posts.

Mixfix Operators & Parser Combinators, Part 1

Until recently, Slang’s parser really sucked. It was a quick hack implemented with Scala’s parser combinator library. Nothing really wrong about that in particular, but there was a gaping hole in the grammar: no operator precedence. So to get an expression like a + b * c to mean a + (b * c) I had to add the parentheses myself. In fact, there were even more problems — some things that should have been left-associative were right-associative. This resulted in very hairy test code, with lots of parentheses everywhere.

Although I think parsers are cool, I am actually not very good at writing one for a complex grammar. I feel that I just know too little about the theory behind them or how to put it to practical use. I’ve used parser combinators before and think they are probably the easiest way for newbies like me to implement parsers, so that’s what I used. The use of symbolic names in the library might be scary the first time, but actually I think parsing is one of the few contexts where use of lots of symbols and extremeley concise code is desirable. It allows one to put a lot of code on a few lines, and when you are looking at or writing a parser, you want to see many productions of the grammar at the same time to understand what is going on. At least I do.

For Slang, I implemented something minimal that could parse the language. I had no idea how to solve operator precedence well with parser combinators, and I didn’t want to spend a lot of time studying parsers, because the next compiler phases seemed more interesting at first. But getting the parser right is important for actually using the language because it’s the first thing that processes the code and reports errors. A parser that only kind of works can be very annoying.

Thankfully Miles Sabin suggested that I should look into mixfix operator parsers, and I did. I don’t know exactly where the word mixfix comes from, so I’m assuming it means mixed fixity — operators can be prefix, infix, postfix or closed. Here are some samples:

  • prefix : -a
  • infix : a + b
  • postfix: n!
  • closed : (a)

Of course, most languages have operators with all of these fixities. The term mixfix actually refers to something more flexible than that — a mixfix operator can be seen as a sequence of alternating name parts and “holes in the expression”. A hole is where the operator’s arguments go.

_ + _ has two holes and one name part + (and is infix)
if _ then _ else _ has three name parts if, then, else and three holes (and is prefix)

In the mixfix viewpoint, many syntactic constructs might be seen as operators that can have precedence in relation to others, and this concept of many name parts can make it easier to let users define their own operators in a more flexible way than just a single prefix or infix word (as is allowed by Scala). I think this would be a really nice way of creating internal DSL-s. In Slang, like in Scala, most operators are really methods. Slang doesn’t allow user-defined fixity or precedence for methods yet (or even multiple argument lists), but I may add this feature one day.

There are existing languages that support mixfix operators, such as Agda, Maude and BitC. To my knowledge, all these languages assign numeric precedence values to operators, and no language currently uses the exact scheme we will look at, although it was proposed for Agda.

Mixfix operators can be implemented in many ways, but one of the first things I found was the paper Parsing Mixfix Operators by Anders Danielsson and Ulf Norell that was a great help to me. I was able to implement the grammar scheme described in that paper on top of Scala’s parser combinators and patch that into Slang’s existing parser with minimal changes to existing productions. The characteristics of the grammar scheme described in Danielsson’s paper seemed like a good enough fit for what I wanted for Slang:

  • operator name parts and holes alternate — there can’t be two subsequent name parts or two subsequent holes

if _ then _ else _ is ok, if _ _ else _ is not

  • operator precedence is described as a directed acyclic graph (DAG), not as a total or partial ordering. You only have to describe the precedence relations where they make sense (more about this in the next post)

a directed edge '+' -> '*' means “* binds tighter than -

  • operator precedence is not transitive

'=' -> '+' and '&' -> '=' does not mean “+ binds tighter than &

  • prefix operators are treated as right-associative

!!a = !(!(a))

  • postfix operators are treated as left-associative

n!! = ((n)!)!

  • left-associative and right-associative operators of the same precedence can’t appear next to each other

assuming +: is a right-associative +, a + b +: c would not be allowed

  • parses are precedence correct
  • implementation using left-recursion is possible, for example when using Scala’s Packrat parsers

There weren’t any restrictions I couldn’t live with (in fact, we could relax some of the above requirements and the scheme would still work for some grammars), so I decided to implement this grammar scheme for Slang, pretty much as described in the paper. Although I didn’t really grok all of the Agda code samples, the principles were easily understandable. I implemented it as a separate library (available on GitHub) that builds on top of the existing Scala parser combinator library. It might even be somewhat usable in it’s current state, but needs improvement.

In the next post we’ll look at how to define a grammar for an arithmetic and boolean algebra language using mixfix operators. In the third part, we will actually implement the parser for the grammar, look at performance issues and whether we can solve them with packrat parsers.

Thanks to Miles Sabin and Daniel Spiewak for reviewing drafts for this series of posts.