hawkw/decaf

like Java, but less so

decaf

Decaf is an alleged programming language. It's kinda like Java but a lot less so.

Decaf was implemented by Hawk Weisman (@hawkw) and Max Clive (@ArcticLight) for Professor Janyl Jumadinova's CMPSC420 at Allegheny College. We apologize in advance.

This Scala implementation of the Decaf compiler (dcc) is based on the C++/Flex/Bison reference implementation provided by Professor Jumadinova.

Decaf is open as in “source,” not as in “container.”

Rave Reviews

... [I]mmense sadness that the first thought that ran through my mind after typing "^this" was "*** this used in incorrect context", demonstrating that clearly I have spent FAR too much time on this project.

~ Max Clive

I've seen other languages with support for recursive descent parsing, for instance, but for the shear, nightmare glory of an LALR parser, nothing more than superficially more elegant (sic) than Flex/Bison.

~ Andrew Thall, Ph.D

You're making a compiler named after coffee? That's so dorky.

~ Cara Brosius

No errors and 468 warnings detected.

~ IntelliJ IDEA

Using Decaf

Programming in Decaf

Decaf is a simple object-oriented language with a C-like syntax that produces Java bytecode. Essentially, it is a watered-down version of Java (hence the name).

If you'd like to actually write programs in Decaf, the file decaf.pdf contains a brief specification of the Decaf language, written by Julie Zelenski and updated by Janyl Jumadinova. Our implementation deviates from the specification in a few ways, documented in the next section.

Additionally, the src/test/resources contains a number of sample Decaf programs which are used by our test suite for various phases of the compiler. These could be very useful to get an understanding of Decaf's syntax. Of particular interest are the samples used by the parser test suite, which contain whole working Decaf programs.

The Decaf compiler's code generation component is currently a work in progress, and a number of language features described in the specification are not yet implemented. Currently, object-oriented features such as class and interface definitions are not yet implemented.

Differences from Decaf Specification

• Since the Decaf specification states that "Decaf does not support encapsulation", we chose to make all names globally visible, rather than making all fields private and all methods public, as we determined that the latter option sounds dangerously close to encapsulation. Since our implementation of dcc generates Java bytecode, implementing support for Java-style encapsulation in Decaf would be very easy, and may be implemented at a later date.
• Although the Decaf spec does not support type lifting, we chose to implement type lifting from int to double. This is because Decaf has no casting mechanism, and therefore, there is no way to ever perform operations on mixed numeric types.
• We've added additional syntactical sugar for a couple of statements not documented in the original spec:
  • A switch/case statement, which functions almost identically to Java's switch statement
  • Unary increment and decrement operators (i++ and i--) which add or subract one from a numeric variable. These function identically to the similar operators in C and Java.
• Some error messages generated by the semantic analysis stage are slightly different from those specified in the Decaf spec and samples. We wanted to make error messages as helpful as possible, and changed some messages when we thought that the wording in the spec was difficult to understand.

Additionally, there are some internal implementation differences from the reference implementation, mostly in the parser and semantic analysis components. These differences don't impact programmers using Decaf, but if you're interested to read about them, they're in the Decaf ScalaDoc API documentation.

Using the Decaf compiler

You can build the Decaf compiler, dcc, using our Gradle build script. Simply type the command ./gradlew dccJar. This will build Decaf, run our ScalaTest test suite, and then generate the runnable dcc jar file. The jar file is output to build/libs/dcc.jar relative to the root of the repository, and can be run with java -jar dcc.jar path/to/source/code/file.decaf. The Decaf compiler currently takes one argument, a Decaf source code file to compile. If you pass more or less arguments, at this point, the compiler will do nothing and issue a warning.

Decaf's default backend generates Java bytecode using the Jasmin assembly language. Invoking the Decaf compiler (dcc) on a Decaf source code file will produce Jasmin assembly files with the file extension .j. In order to produce executable .class files, the Jasmin assembler must be invoked on those .j files. You can download an executable Jasmin jarfile here.

Currently, the Jasmin assembly output by the Jasmin backend is printed by the compiler to stdout. You can pipe this output into a file and then invoke Jasmin on it (java -jar dcc.jar aprogram.decaf > aprogram.j && jasmin aprogram.j or similar). This is for debugging purposes. Eventually, this output will be written to the current working directory instead, with each class in the program being output to its' own class file (once object-oriented programming is implemented).

Running Tests

Running our test suites is very easy - all you have to do is navigate to this repository's root directory and type ./gradlew test.

This will trigger the Gradle wrapper to download the correct version of Gradle (if it is not already present), install all of Decaf's dependencies (currently the Scala parser-combinators library and ScalaTest), build Decaf, and then run our test cases. Note that the Gradle wrapper will install Gradle and all dependencies locally, so you don't need root access to the machine you wish to test Decaf on. If you have a local copy of Gradle installed, you can feel free to use that to run our test task, as well, but the Gradle wrapper will ensure the correct version of Gradle is used.

Generating Documentation

If you're interested in reading the ScalaDoc documentation we've written (and you might be, as it documents some of the decisions we've made regarding our interpretation of the Decaf spec), you can generate this documentation using the ./gradlew scaladoc command. The documentation will be output to the build/docs/scaladoc directory, and you can read it by opening the index.html file in that directory.

decaf's Issues

Add array literals (Max's idea for Fun Thing)

Add the increment/decrement operators (++ and --)

Apparently we do have to do this (see the handout).

Implement codegen for function calls

• function1.decaf
• function2.decaf
• function3.decaf
• function4.decaf
• function5.decaf
• function6.decaf

Add detection for invalid function parameters

From Dr. Jumadinova's handout:

*** Function ‘Winky’ expects 4 arguments but 3 given
*** Incompatible argument 2 : string given, string[] expected
*** Incompatible argument 3 : double given, int/bool/string expected

Used to report mismatches between actual and formal parameters in a function call. The last one is a special case message used for incorrect argument types to the Print builtin function.

Support class declarations

I need to re-implement the classDecl production that was commented out when we switched over to PackratParsers.

Implement code generation for operators samples

• op1.decaf
• op2.decaf
• op3.decaf
• op4.decaf
• op5.decaf
• op6.decaf
• op7.decaf
• op8.decaf
• op9.decaf
• op10.decaf
• op11.decaf

Add detection for undeclared named types

From Dr. Jumadinova's handout:

*** No declaration for class ‘Cow’ found

This message is used to report undeclared identifiers. The only undeclared identifiers you have to catch for the checkpoint are use of undeclared named types in declarations, i.e. a named type used in a variable/function declaration, a class named in an extends clause, or an interface from a implements clause. This error message is also used for undeclared variables and functions, but checking for those is a task that is handled after the checkpoint.

Class inheritance cycles incorrectly/improperly detected

verifyClassChain is doing much the wrongs;
for example

class A {}
class B extends A {}
class C extends B {}

reports an illegal cyclic dependency involving B in class C.

Add detection for undeclared identifiers

From Dr. Jumadinova's handout:

*** No declaration for function ‘Binky’ found

Used to report undeclared identifiers (classes, interfaces, functions, variables).

Error Handling Architecture

We need to determine how the Decaf compiler will handle errors. We need to determine how we will differentiate between fatal errors (that halt compilation) and warnings (that allow compilation to continue).

We also need to determine if dcc will continue semantic analysis after generating a fatal error, so that we can catch other errors in the program as well. It would be nice to report all of the errors in the program, rather than just the first one encountered; however, this may make some things more difficult, since, for example, type checking depends on scoping, and if we aren't able to scope the program correctly, it might confuse the type checker.

I think Scala's heap-based error management construct (Try[A]) and possibly also Futures and Promises might be useful here.

Add detection for array subtypes & creation issues

From Dr. Jumadinova's handout

*** [ ] can only be applied to arrays
*** Array subscript must be an integer
*** Size for NewArray must be an integer

Used to report incorrectly formed array subscript expressions or improper use of the NewArray.

Lab 3 Spec

We need a Huge Failing Test Fixture for everything required for the final submission of Lab 3. I've included the sample code & output from Dr. Jumadinova in src/test/resources/lab3-samples/samples.

As I mentioned in #24, since most of the requirements at this point are related to error handling, we could consider testing by expecting exceptions rather than through toString testing like in the other labs. Of course, this depends on #23.

Array has no such field "length"

*** Error line 10.
   for (a = 0; a < arr.length(); a = a + 1)
                   ^
*** string[] has no such field 'length'

We need to either add fake nodes for array.length() to the scope tree much as we do for this, or special-case it when we check calls.

Add a Good CLI

My current command-line interface (Compiler.scala) works, but is pretty basic. If we want to add compiler features other than parsing & compiling one Decaf source code file, such as linking, strictness, choosing the name of the output file, or a REPL, we're gonna need a better command-line argument parser.

@ArcticLight and I are both really big fans of Docopt, the Pythonic Command-Line Parser, so I figure we'll use the Scala port of Docopt.

AST is on fire

Sometimes, AST nodes are created that don't have parents, which screws up the compiler for obvious reasons (see the line on which it's caught).

This happens in code generation for while1.decaf, for1.decaf, for2.decaf, and for3.decaf. All of these programs would compile otherwise.

Fix this

As of 6a5ab4d, the this keyword doesn't work.

Support interface declarations

I need to re-implement the interfaceDecl production that was commented out when we switched over to PackratParsers.

Add detection for invalid use of `.`

From Dr. Jumadinova's handout:

*** Cow has no such field ‘trunk’
*** Cow field ‘spots’ only accessible within class scope

Used to report problems with the dot operator. Field means either variable or method. The first message reports to an attempt to apply dot to a non-class type or access a non-existent field from a class. The last is used when the field exists but is not accessible in this context.

Implement code generation for while-loop samples

• while1.decaf
• while2.decaf
• while3.decaf
• while4.decaf

Prettyprint errors

We need to implement a prettyprinter for our errors that prints things with the program line, location, and carrots underlining the specific offending lines.

The Scala standard lib does this for its error reporting when you throw errors during a parse, so presumably there exists code that does the correct printing. Therefore, we should look for this code and see if we can make it work in our typechecker.

Implement IO code gen

• Printing:
  • basic Print with one argument
  • Print with multiple arguments
• Reading:
  • ReadInteger()
  • ReadLine()

Samples:

• io1.decaf
• io2.decaf
• io3.decaf

Class inheritence never checked

Classes never check the existence or the correctness of their inherited superclass.

For this issue, classes must check that their inherited superclass exists.

Add detection for invalid operands

From Dr. Jumadinova's handout:

*** Incompatible operands: double * string
*** Incompatible operand: ! int[]

Used to report expressions with operands of inappropriate type. Assignment, arithmetic, relational, equality, and logical operators all use the same messages. The first is for binary operators, the second for unary.

Make everything more functional/idiomatic

Fix positions being subtly wrong

Not all classes get a 'this'

As of a19617d, it appears that scopes of classes are exploding rather a lot.

See sample run of the current Semantic main method:

Global:  
  A ==> Class: A
  B ==> Class: B
\\
  Class Declaration of B:    
    this ==> Variable of A
//

Add detection for invalid use of `this` keyword

From Dr. Jumadinova's handout:

*** ‘this’ is only valid within class scope

Used to report use of this outside class scope.

Make a runnable `dcc` jar

It would be cool if you could actually run the Decaf compiler (dcc) on arbitrary input from the command line, the way you can for Professor Jumadinova's C reference implementation. The Gradle build script could be modified to make a jarfile pretty easily.

We don't need this for the lab, but it would be cool.

Caret underline whole statements in error reporting

It would be nice if we could do this and fully match JJ's expected output.

Lab 3 Checkpoint Spec

We need a Huge Failing Test Fixture for everything required for the checkpoint. I've included the sample code & output from Dr. Jumadinova in src/test/resources/lab3-samples/samples-checkpoint.

Since most of the requirements at this point are related to error handling, we could consider testing by expecting exceptions rather than through toString testing like in the other labs. Of course, this depends on #23.

Array code generation

Needed:

• Code generation for NewArray
• Code generation for single dimensional array access
• Code generation for multidimensional array access
• Code generation (and fake method annotations) for array.length()

Samples;

• array1.decaf
• array2.decaf This one fails due to a parse error, I'm skipping it.
• array3.decaf
• array4.decaf

Add detection for unimplemented interfaces

From Dr. Jumadinova's handout:

*** Class ‘Cow’ does not implement entire interface ’Printable’

Used for a class that claims to implement an interface but fails to implement one or more of the required methods.

Fix order of operations for arithmetic operators

It makes this:

 12         AssignExpr:
 12            FieldAccess:
 12               Identifier: d
 12            Operator: =
 12            ArithmeticExpr:
 12               IntConstant: 2
 12               Operator: +
 12               ArithmeticExpr:
 12                  IntConstant: 3
 12                  Operator: *
 12                  ArithmeticExpr:
 12                     IntConstant: 4
 12                     Operator: -
 12                     ArithmeticExpr:
 12                        IntConstant: 6
 12                        Operator: /
 12                        IntConstant: 2

when it should make this:

 12         AssignExpr:
 12            FieldAccess:
 12               Identifier: d
 12            Operator: =
 12            ArithmeticExpr:
 12               ArithmeticExpr:
 12                  IntConstant: 2
 12                  Operator: +
 12                  ArithmeticExpr:
 12                     IntConstant: 3
 12                     Operator: *
 12                     IntConstant: 4
 12               Operator: -
 12               ArithmeticExpr:
 12                  IntConstant: 6
 12                  Operator: /
 12                  IntConstant: 2

Print statement should be type checked as though it were a call

Currently, when checkTypes() hits a print statement, it makes a MatchError. I'd rather not special-case these, is there a way to make it count as a regular function call here? Maybe through adding a fake node at global scope the same way we add "this" to class scopes?

Class overrides go unchecked

Classes need to verify that the type of their superclass overrides is the same. This involves (with the currently correctly happening ScopeTree) checking that each entry it can find within its LOCAL SCOPE (I.e. using contains()) either A: Does not exist in the parent scope, or B: is in the parent scope or higher (via chainContains() _on the parent scope_) AND is of precisely the same type (must be the exact same class, exact method signature, or exact datatype).

Note: Decaf supports neither overloading nor any real type of class-inheritence-based shadowing, so it is sufficient to match exactness of inherited values and not worry about anything else inheritence-related.

Add detection for conflicting declarations

From Dr. Jumadinova's handout:

*** Declaration of ‘a’ here conflicts with declaration on line 5 
** Method ’b’ must match inherited type signature

These are used to report a new declaration that conflicts with an existing one. The first message is the generic message, used in most contexts (e.g. class redefinition, two parameters of the same name, and so on). The second is a specialized message identifying an attempt to overload a subclass’s method.

Add the switch statement

Apparently we actually do have to do this (see the handout).

Implement codegen for for-loop statements

• for1.decaf
• for2.decaf
• for3.decaf
• for4.decaf
• for5.decaf
• for6.decaf

Add detection for improper statements

From Dr. Jumadinova's handout:

*** Test expression must have boolean type
*** break is only allowed inside a loop
*** Incompatible return : int given, void expected 

Used to report improper statements.