Week 1

Week 1 – WASM, TypeScript, and a Mini Compiler

Table of Contents

Readings & Due Dates

Read:

TODOs:

  • Quiz 1 - Due 11:59pm Friday, April 1, 2022
  • Assignment 1 - Due 11:59pm Monday, April 4, 2022

Lecture Materials

Tuesday Class Notes

Thursday Handout

Assignment 1

In this programming assignment, you will start from a compiler that we (mostly) provide based on one from class. You will add binary arithmetic operators and a few built-in Python functions.

Starter code is here:

https://github.com/ucsd-cse231-s22/pa1

In the office hours sessions for week 1 (see calendar on homepage), we will run tutorials for doing much of the needed work for this assignment. Seriously, go and you’ll see how much we’ve tutorialized this assignment for you! These sessions will also be recorded.

  • Yousef’s Tutorial: https://ucsd.zoom.us/rec/share/GqPlU0k-8gc_S9QoNHFMFUDcIZFAq1OiqCLkuHElzLi93qSwmgoPEWSTk-TswK42.EOLj5YGOo7jYyBb4 Passcode: $HmB0iY%

Problem Specification

The grammar of the language your compiler will support is:

program := <stmt> ...
stmt := <name> = <expr>
      | <expr>
expr := <number>
      | <name>
      | <expr> <op> <expr>         (you!)
      | <builtin1>(<expr>)
      | <builtin2>(<expr>, <expr>) (you!)
op   := + | - | *                  (you!)
builtin1 := print | abs            (you! [abs])
builtin2 := max | min | pow        (you!)
number := 32-bit integer literals

You can see this (mostly) reflected in the ast.ts, with parser.ts converting from a parse tree representation to the AST representation. Then code generation for several of them is implemented for you in compiler.ts. You will need to add the cases corresponding to binary operators and the new builtins, which are labeled with (you!) in the grammar above.

Your task will be to make it so input programs using the binary operators, and the builtin functions listed above, have the following behavior:

  • +, -, and * should use the corresponding WASM operators i32.add, i32.sub, and i32.mul on the two operands after evaluating them
  • abs should produce the absolute value of its argument
  • max/min/pow should take two arguments and produce the larger of the numbers, the smaller of the numbers, and the first number raised to the other’s power, respectively

Your implementation is up to you, but a likely approach is:

  • Add expressions for binary operators and builtin2 to ast.ts
  • Add parsing support for these expressions in parser.ts
  • Add code generation for these expressions in compiler.ts
  • Add TypeScript functions to implement the new builtins as necessary (use print as a guide)
  • Test this as you go by adding tests in the tests/ directory
  • Watch your program work in the browser by opening build/index.html in a browser of your choice.

We recommend implementing these features one at a time (don’t try to do multiple new kinds of expressions at once), so that you can test more incrementally.

Testing

We use the Mocha test framework along with Chai assertion library to simplify testing the compiler. We provide some starter testing code in tests/parser.test.ts and tests/runner.test.ts. We included comments in these files to get you started testing the compiler and we added to-dos where we expect additional tests. We encourage you to test other parts of the compiler individually if you find yourself stuck, like compile.

A few specific cases have specific errors we will test for:

  1. If the program doesn’t parse correctly, make sure the error has ParseError as a substring of the thrown message
  2. If the program uses a name that isn’t defined, make sure the error has ReferenceError as a substring of the thrown message

To throw specific errors, throw new Error(" message here ...") suffices (this uses the built-in Error class in JavaScript/TypeScript). If you want to make specialized exception classes, go for it! We will make refinements like this in future assignments.

Building and Running

To get started, make sure you have NodeJS installed https://nodejs.org/en/download/, and check out this repository. In the repository, run

npm install

This will download and install the necessary WASM and Typescript dependencies.

You can build index.html by running:

npm run build-web

And then open the created file in build/index.html in a browser to get the textbox and run button for your code.

You can run test suits using the following command, and it will print a summary of passing and failing tests:

npm test

Writeup

In a file called README.txt, answer the following questions:

  1. Give three examples of Python programs that use binary operators and/or builtins from this PA, but have different behavior than your compiler. For each, write:
    • a sentence about why that is
    • a sentence about what you might do to extend the compiler to support it
  2. What resources did you find most helpful in completing the assignment?
  3. Who (if anyone) in the class did you work with on the assignment? (See collaboration below)

Collaboration

You can discuss your approach and code with anyone in the class, make study groups to work together, have public discussions on the course message board, and so on. Make sure to give credit to collaborators in your README (see below) and make an individual submission. This assignment is predominantly for your learning and practice. Other assignments in the course will be completed on your own and/or with additional assessment and have more restrictive collaboration policies.

Submission

You can submit your code to the pa1 assignment on Gradescope.

Grading

Most of your grade on this assignment comes simply from the autograded component – we want to make sure you have everything built successfully. A note that future assignments will not necessarily follow this scheme.

  • 90% Autograder Tests
  • 10% Written Responses

Another note about stakes while discussing credit – this class’s material is necessarily cumulative. That means that the next assignment will build on this one, not just conceptually but concretely in terms of code. As a result:

  • It’s important that you understand this one!
  • There will be another opportunity to demonstrate that you understood this one on the next assignment! So if you’re worried that you’ve done poorly on the assignment, don’t assume your grade is forever ruined, there will be opportunities to regain credit for this. Focus on learning.

Useful References