Introduction

This document is generated using pandoc from README.md. It's provided as a convenience.

The specification is avaiable here.

Hacking

This project has been developed using stack and all commands casually assumes that you will too.

The project includes a simple make-file that serves more as documentation than anything else. The make-target test will not work because I have not included the test-runner in my submission. This is because I have made small modifications to the test-runner you have provided. In stead I assume that you will be using your own test-runner on this project and I provide a one-liner for doing exactly this. Please see [testing].¹

Building

Lexing and parsing has been implemented using bnfc. The syntax-file can be converted using:

bin/dobnfc.sh

But (much against my good will) the code that is generated by this is version-controlled as well, so stack should be the only thing you need to get up and running. Thus; building is as easy as 1... 2...

stack build

Running

This projects defines two executables jlc and javalette-parser.

javalette-parser is an executable generated by bnfc. jlc is the main executable that implements the compiler. As of now it does not have a lot of sophisticated options. It expects all arguments to be paths to a javalette-file. It will then type-check it and write eiher "OK" to stderr if typechecking succeeds or "ERROR" followed by an error message in the case of failure.

Testing

Tests are performed as described in the spec.

Simply supply the location to the directory in which the binary jlc ends up. With stack this is a (somewhat awkward) one-liner:

Grade `stack path --project-root`/`stack path --dist-dir`/build/jlc

Implementation

Project structure

The most important modules are in the src directory:

Javalette.Syntax Re-exports the AST generated by bnfc.
Javalette.Syntax.* Modules generated by bnfc.
Javalette.Interpreter An interpreter for Javalette.
Javalette.Interpreter.Program A program-description using free monads used by the interpreter.
Javalette.TypeChecking Typechecking.
Javalette.Parser The parser. This is a simple wrapper around the parser generated by bnfc.

And the compiler executable jlc is defined in apps/compiler/Main.hs. This program takes care of input-parsing, calling the correct methods from the library and reporting success/error according to the spec.

The syntax of javalette is described by javalette.cf (used by bnfc to generate a lexer, parser and an ast desription of the language).

Typechecking

The typechecker is implemented using a monad-stack:

type TypeChecker a = StateT Env (Except TypeCheckingError) a

TypeCheckingError is a simple sum-type with different errors that can occur during type-checking.

The environment is defined as follows:

data Env = Env
  { envVars :: [Map Ident Type]
  , envDefs :: Definitions
  }
type Definitions = Map Ident Definition
data Definition = DefWiredIn WiredIn | Def TopDef

That is, variables are stored in a list of maps. This is so that we can distinguish variables declared in different blocks. Each time a block is encountered a new empty environment is appended to this list. Variable lookups works by finding the first matching variable.

The definitions are either one of the built-in definitons (printString, readInt...) or it's a reference to a function definition from the AST.

Note that definitions do not have the same notion of scopes as variables. Also note that no overloading of functions can take place since we map from the identifier, i.e. we don't consider the arguments.

The main exported function from Javalette.TypeChecking is typecheck which does 2 passes over the AST. It first ensures that any return-statement encountered inside function definitions have the same type as the function. Note that this does not ensure that the function actually has a return- statement. This is checked in the second pass (call to staticControlFlowCheck). This check does a conservative check that such a return-statement is encountered.

Note that staticControlFlowCheck will reject some functions that actually would always return a value of the given type. E.g.:

int main() {
  if(entscheidung()) { return 0; }
}

Where entcheidung is some function that always returns true but proving this in general is undecidable (or at least more complex than what my simple implementation handles).

For more details please refer to the haddock documentation or the source.

Ideally you'd run the test-runner directly on the archive generated by stack sdist -- but unfortunately I have not gotten this to work. ↩