▼CS 107 Projects (Spring 2026)
►Project 3:   Type Checking, Functions, and Heap Allocation
On this page:
1 Introduction
2 Project Structure
2.1 src/  main/  scala/  project3/  Util.scala
2.2 gen/  bootstrap.c
2.3 src/  main/  scala/  project3/  Main.scala
2.4 src/  main/  scala/  project3/  Language.scala
2.5 src/  main/  scala/  project3/  Parser.scala
2.6 src/  main/  scala/  project3/  Semantic  Analyzer.scala
2.7 src/  main/  scala/  project3/  Interpreter.scala
2.8 src/  main/  scala/  project3/  Compiler.scala
2.9 src/  test/  scala/  project3/  *Test.scala
2.10 Extra Credits
2.10.1 Char
2.10.2 Functions as Values
3 Submission
3.1 Grading
Feb 5, 2026
    contents    up  next → 

Project 3: Type Checking, Functions, and Heap Allocation🔗

Quick links
• Course Home
• Piazza
• Canvas
• Scala 3 Book
• X86 Cheat Sheet

Due: Feb 15, 2026 at 11:59pm

1 Introduction🔗

In this project, we will enrich the language we defined in the first two projects.

At the end of the project, we will be able to parse full programs, including functions and arrays. Our parser will generate an intermediate representation in the form of an Abstract Syntax Tree (AST), and our Semantic Analyzer will be able to verify the typing rules.

With functions now in our language, we can add a little bit of I/O. When writing code in our programming language, the programmer will have access to two primitives:

  • getchar of type () => Int. See doc.

  • putchar of type Int => Unit. See doc; we do not return the character.

Using these functions may lead to some issues when the code is launched from sbt. In order to test, launch the out binary generated in the folder gen.

To get started, first download the skeleton file proj3.zip (updated with grammar) and unzip it:

unzip proj3.zip
cd proj3

2 Project Structure🔗

A description of the different files is provided below. The files you need to complete are Parser.scala, SemanticAnalyzer.scala, Interpreter.scala, and Compiler.scala. Following the path of the first project, we are going to implement the parser step by step. Follow the comments in the code and find the TODOs. The parts are independent and can be develop separately. In order to implement the new features more easily, we have changed some of the previous class/function definition we had. You can search for the string CHANGE into the source code to see these modifications.

2.1 src/main/scala/project3/Util.scala🔗

This file defines multiple classes that are used to generate the code and run it on your machine. Nothing needs to be modified, but it is recommended to read it and have an idea of what is happening behind the scene.

2.2 gen/bootstrap.c🔗

As we are generating x86-64 assembly code which is OS independent, we will be using GCC/Clang to do the heavy lifting for us. The bootstrap file is a generic C file that is calling a function entry_point and is printing the result to stdout. Our compiler will generate the file gen/gen.s and will be assembled and linked by gcc:

gcc bootstrap.c gen.s -o out

2.3 src/main/scala/project3/Main.scala🔗

The main function is defined in this file. The data flow in this file can be viewed as:

Read from file / Read from command line -> Parser -> Semantic analyzer -> Interpreter or compiler

You will be implementing many different parsers in order to test them through the main function.

The AST generated will be then provided to the semantic analyzer. If there is no error, then the code (represented as AST) is going to be interpreted or compiled. The skeleton provides you with one interpreter. You will have to write one interpreter and one compiler.

As our language becomes more complex, it will become more useful to read the input code from a source file. You may find some sample programs in the examples/ folder. Here some examples to run the code:

$ sbt
sbt:Project3> run
Usage: run PROG [OPTION]
   or: run FILE [OPTION]
OPTION: intStack
sbt:Project3> run examples/valid_arithm.scala           –> interpret with the provided interpreter, and x86 compiler
sbt:Project3> run examples/valid_arithm.scala intStack  –> stack interpreter (your code), and x86 compiler

It is still possible to run code from the command line, as in project 1. For example:

$ sbt
sbt:Project3> run "val x = 5; x"
sbt:Project3> run "val x = 5; x" intStack

2.4 src/main/scala/project3/Language.scala🔗

This class contains the definition of our intermediate language.

2.5 src/main/scala/project3/Parser.scala🔗

As we discussed in class, we are introducing types in our language. In addition to Int, we will also have the types Boolean and Unit. You will need to modify the Scanner class in order to tokenize the constants of type Boolean correctly. There is a single Unit constant: (). Because this construct can be used for other reasons (e.g. a function without parameters), the () will still be parsed into two delimiters: ’(’ and ’)’. The function parseAtom will be handling the Unit literal.

The rest of the file is the definition of each parser we are building, starting from a base parser that is an implementation of the parser we implemented in project 2. What you have to do for this project is highlighted with TODOs in the code. We encourage you to read the comments and code carefully before proceeding.

2.6 src/main/scala/project3/SemanticAnalyzer.scala🔗

While the parser is in charge of verifying that the input string follows the defined syntax, the semantic analyzer verifies that the program described is meaningful and follows the rules. The skeleton code already contains the semantic checks we implemented in project 2.

However as we have seen in class, we are upgrading our semantic analyzer into a type checker. Your job is to complete the typeInfer function using the rules we have seen in class.

2.7 src/main/scala/project3/Interpreter.scala🔗

As we have seen in class, now that our programming language accepts more than just mathematical expressions, we need to define the required behavior of our language. An interpreter can be used to define this meaning.

We provide you with an interpreter that is fully functional. Your job is to complete the Stack-based interpreter.

2.8 src/main/scala/project3/Compiler.scala🔗

The x86-64 compiler handling all features up to loops is already implemented for you. You need to complete the compiler with the new features.

2.9 src/test/scala/project3/*Test.scala🔗

These files contain some unit tests for the first parsers. In order to get full credits, you must write your own tests for the others. Every task should have at least 2 tests otherwise points will be deducted. There are some functions given to you in order to make the implementation easier.

2.10 Extra Credits🔗

2.10.1 Char🔗

The programmer can use two functions to interact with the console: getchar and putchar. However, we do not have characters, so in order to print hello world, the programmer would have to write the code:

putchar(72); putchar(101); putchar(108); putchar(108); putchar(111); ...

This is not really convenient; we would rather do:

putchar(toInt(’H’)); putchar(toInt(’e’)); putchar(toInt(’l’)); putchar(toInt(’l’))...

(much better isn’t it?)

We are therefore going to add a new type in the language: Char. All letters, numbers, punctuation signs and spaces should be handled, e.g. you don’t have to handle the escaping characters ’\n’, ’\r’... In the program, a programmer will be able to use the single quote notation to enter a character e.g. ’H’. You will also provide two primitives operations:

toInt: Char => Int
toChar: Int => Char

You can use the example of the Array look up transformation into primitive. In the skeleton this is done in the semantic analyzer in the App case. The x86 implementation: toInt will be a no-op and toChar:

mov loc, %rax
movzbq %al, loc
2.10.2 Functions as Values🔗

In the Compiler.scala file, there are some places marked as Extra Credit. These are the places where we need to generate code for functions used as arguments, stored into variables, or returned from a function. While you are required to parse this kind of code correctly and be able to type check it, you are not required to generate the corresponding x86 code. Implementing such generation correctly will be counted as extra credit.

3 Submission🔗

You should turn in the proj3 directory. Please run an sbt clean before packaging and submitting.

To submit your project, create a ZIP file named proj3.zip of the proj3 directory and upload it to the corresponding assignment on Canvas.

Verify your submission by downloading the ZIP file you uploaded on Canvas and extracting its content. The uncompressed content should be the proj3 folder containing the code. Your submission ZIP file should have the exact same structure as the skeleton ZIP file.

Your submitted code must compile, i.e. running sbt compile gives no errors. If your code does not compile, your submission will not be graded and you will receive 0 points for the whole project.

Late Submission Policy: Projects are due at 11:59pm on the due date. Succeeding projects build upon previous ones and will reveal solutions of preceding projects, so late submissions will not be accepted. Submitted after the deadline will receive 0 points.

3.1 Grading🔗

Your project will be tested against a set of unit tests. The weights of each task will be distributed as follow:

Task

 

Weight

Scanner: Boolean

 

2.5%

BaseParser: Types

 

2.5%

Syntactic Sugar

 

5%

FunctionParser

 

15%

ArrayParser

 

10%

Semantic Analyzer

 

30%

StackInterpreter

 

10%

X86Compiler

 

25%

Extra credit will be worth 1% of the final grade.

    contents    up  next →