Project 1: Make Something Cool for Bril

• Proposal due: September 11, 2019
• Report due: September 25, 2019

Overview

Your mission in this project is to make something cool that extends the Bril ecosystem. Bril is the shared programming language we'll use for some work in this class. (Building tools around a common language will let us learn from and build on each other's work.) The idea is to make something that extends Bril to make it more realistic, that makes your life easier when using Bril, or just accomplishes something snazzy using Bril programs. Together, we'll build up an ecosystem to support increasingly cool projects. Your secondary goal in this project is to get experience using Bril and its tools so you'll be ready to implement more sophisticated transformations and optimizations for it in the next project.

Because this is a warm-up project, I encourage you to think small when proposing an idea. Pick something self-contained that you can get done in a couple of weeks—but something that you will still consider cool when you're finished.

Like every 6120 project, however, you will need to do some sort of empirical measurement for this project. Make your evaluation small in scale but rigorous: you might try out your cool thing on a collection of programs and manually check that it does the right thing on most of them, for example, if there's nothing quantitative to collect.

Ideas

Here are some ideas for projects that fit in the scope of this project.

Extending the Language

Bril is a pretty simple language right now. You could extend it to do something new, either as a core feature or an optional extension:

• Add mutable array types, including operations to create, read from, and write to array values.
• Similarly, add (mutable or immutable) record types.
• Add manually-managed pointer types, including operations to allocate, free, read, and write memory cells.
• Functions. You can define functions in Bril right now, but there's no instruction to call them.
• Untyped code. Bril is a typed IR; you could extend it some creative way to support untyped languages as well—either in harmony with typed code or in a separate, untyped version.
• Indirect jumps. Add a type that represents a function pointer and a way to invoke these values. The goal should be to support implementation of higher-order languages.

If you extend the language, you'll want to be sure you at least add to the reference interpreter, the documentation, and the textual representation tools (if necessary).

And here’s a different kind of extension project: you could generalize the notion of Bril extensions. Build a mechanism for specifying and using language extensions so that tools can, for example, easily reject programs that use unsupported extensions or handle new instructions that they don’t know about.

Extending the TypeScript Frontend

I have written a small compiler frontend, ts2bril, that compiles a small subset of TypeScript to Bril. This makes it a little easier to write Bril programs that do something interesting. There are lots of ways you could extend this compiler to make its TypeScript subset more complete:

• Add support for more TypeScript arithmetic operations, like += and *= or ++ and --.
• Add support for interesting control flow constructs like break and continue or do and while.
• Add support for defining and calling top-level functions.

If you pick this path, you'll want to take a careful look at my fledgling frontend to see exactly what I have and have not implemented yet.

A different kind of project you could propose could involve creating a benchmark suite based on the TypeScript frontend. You could assemble small programs from a well-known source, port them to the small TypeScript subset we support, and document their characteristics for other projects on expressiveness or performance to use.

Other Frontends

You could build a new frontend for generating Bril code. I can imagine two flavors of this project:

• Use an existing language and hijack a current parser and AST to emit Bril code. (This is how the current TypeScript frontend works.) For example, it's pretty easy to get a Python AST from a function and write a recursive function that walks it.
• Make your own language “from scratch,” starting by writing a parser (either by hand or with a parser generator) and generating Bril. ChocoPy might be a good choice—it has an exhaustive specification you can follow.

Backends

I don't think it would be too hard to build a backend that translates Bril programs into Java bytecode, WebAssembly, or LLVM IR. Or as silly as it seems, you could even translate Bril into another user-facing language, such as JavaScript or C.

Tools on the Side

Here are some ideas for tools that read or write Bril programs:

• Write a fast interpreter. The reference interpreter is written in TypeScript, but you could make a better one by writing it in a proper systems language like Go, Rust, or Swift. If more than one team writes an interpreter, we could have a good time comparing their performance.
• Design a binary format for Bril programs. Such a format would have a bijective correspondence to the JSON form but would be more compact. It could also facilitate fast interpreters, which could execute the binary form directly without parsing.
• Write a tracing interpreter to help debug Bril programs. Be creative about how you represent the program state and let programmers navigate an execution. In the limit, the tool could act as a gdb-like debugger.
• Static type checking. Bril is a statically typed language, but we don't check the types yet. You could write a checker that finds type errors and uses of undefined variables.
• Editor support for the textual representation. Write a syntax highlighter or other language support for your favorite IDE or text editor. Consider using the Language Server Protocol standard.
• An interactive interpreter that runs in the browser, like one of the many “playgrounds” for other languages.
• A tool for testing optimizations. It would work by taking a command that reads and writes Bril, runs it on a collection of input programs, and uses the interpreter to check that both behave the same way (on fixed or randomly generated inputs). For bonus points, it could also report differences in efficiency metrics like the dynamic instruction count.

Doing the Project

Before you even propose an idea, I recommend you familiarize yourself with the current Bril infrastructure. Write some programs, read some programs, and execute some programs in the interpreter.

Propose an idea that you think will yield a cool result. This means it should probably be as ambitious as you can muster within the given (short) time frame. To submit your proposal, see the general 6120 project instructions. Be sure to include your plan for measuring your success.

I implemented Bril in a "monorepo," meaning that lots of interrelated but separate projects live together in the same version control repository. This is nice because it lets us be sure that all the tools agree on a consistent version of the language. Therefore, unless you have a good reason to, please plan on contributing your work back to the "official" Bril GitHub repository. When you're done with your implementation, you can open a pull request.

You will probably want to write some tests for whatever you implement. The Bril infrastructure uses Turnt, a low-effort testing tool developed in the Capra lab. We invite you to use Turnt for your code also, if you're into it.

When you write your report, please again see the general advice about 6120 projects. Remember that your audience for the report is your peers in 6120 and the rest of the world—not your instructor. Write your report to be accessible to interested experts.