/decaf

An implementation of the Decaf language

Primary LanguageHaskellOtherNOASSERTION

Decaf

CI Coverage Haddock

An implementation of the Decaf language.

Status

Currently scan/parse/cfg phases are implemented and should work for most cases. -t scan generates the token stream. -t parse outputs the abstract syntex tree(AST) in text format. -t cfg generates a dot plot of the control flow graph(CFG), which could be furthur processed by the graphviz tool to give a graphical view of the CFG.

This implementation relies on Alex for lexing and Happy for parsing. The definition of lexmes are in src/Lexer/Lex.x. The grammar is in src/Parser/Grammar.y.

The parser and semantic might not be exactly conformant to the decaf spec. Rather it should be a superset. All valid decaf programs should be compiled to code with the expected behavior. In addition the implementation should also be able to compile some other intuitively reasonable programs which might be invalid in the spec.

Curently the LLVM IR backend is mostly working. (Note There are still lots of bugs though). The compiler should be able to compile some simple code snippets. For example a "hellow world":

import printf;

void main() {
  printf("Hello world!\n");
}

Save the above code into a hello_world.dcf, then compile it with

stack run -- decafc -t llvm hello_world.dcf > hello_world.ll

Then the generated LLVM IR can be further compiled and linked into an executable

llc -filetype=obj hello_world.ll -o hello_world.o
clang hello_world.o -o hello_world

Some working examples

Sum from 1 to 50:

import printf;

void main() {
  int res;
  int i;
  res = 0;
  for (i = 1; i <= 50; i+=1) {
    res = res + i;
  }
  printf("sum(1..50) = %d\n", res);
}

Produces:

sum(1..50) = 1275

Fibonacci series:

import printf;

void main() {
  int i;
  int fib1;
  int fib2;
  int temp;
  i = 0;
  fib1 = 1;
  fib2 = 1;
  temp = 0;
  printf("fibonacci:");
  printf(" %d", fib1);
  printf(" %d", fib2);
  for (i = 3; i <= 10; i++) {
    temp = fib1 + fib2;
    fib1 = fib2;
    fib2 = temp;
    printf(" %d", temp);
  }
  printf("\n");
}

Produces:

fibonacci: 1 1 2 3 5 8 13 21 34 55

Some random comments

Programming in Haskell is an interesting experience. The design of this language is dramatically different from most others. Unfortunately the tooling and the ecosystems are quite lacking. The Haskell language server is OK, however debugging tools are practically non-exist. You can debug simple scripts with an interactive session or Debug.Trace to print some information. But as the complexity of your program goes up, tools like GDB are really important to save some headaches. Also it seems many of the Haskell packages are either short of maintainers or having quality issues. The LLVM binding has been stagnant since a few years ago. It is hard to imagine this could happen for a language which was claimed to be good for compiler development. The GraphViz package which I used at some point had bugs when handling escape sequences, because of which I have to write my own graph drawing functions.

It is a pity to watch such a great language gradually fall into its current status. Initially the plan was to implement the compiler all the way through. But the shortcomings of this language is becoming more than annoying. After the LLVM IR backend this whole stuff is working like a compiler at least. So it is probably a good time to consider looking for another language which might be better for the task and restart there.