Lesson 2: Representing Programs
- discussion thread
- representing programs
- getting started with Bril
- tasks due August 31
Gist
- How do you represent a program? The classic options:
- Concrete syntax.
- Abstract syntax (AST).
- Instructions.
- We like the instruction representation for its regularity. To do anything useful with it, however, we need to extract higher-level representations.
- Control flow graph (CFG).
- Basic blocks.
- Terminators (
jmp
andbr
, here). - Derive the algorithm for forming basic blocks.
- Successors & predecessors.
- Derive the algorithm for forming a CFG of basic blocks.
- Bril, the Big Red Intermediate Language, is a language invented just for 6120.
- Philosophy.
- The canonical representation is JSON. There is a text format, but that’s just a detail. (Remember, this class is not about parsing. If you ever find yourself doing something fancy with the text format, stop—that’s not your job.)
- This way, you can use any language you want to work with Bril (and for 6120 work).
- A consequence is that you can (and should!) start “from scratch” with Bril. Do not attempt to use my garbage Python stuff; write your own!
- Getting started with working with Bril.
- The documentation.
- The git repository.
- The video’s installation instructions are stale: it refers to using
yarn
to install stuff. It’s now somewhat easier:- Install Deno.
brew install deno
on macOS, for example. - Type
deno install brili.ts
. - As Deno instructs, add
$HOME/.deno/bin
to your$PATH
. That’s it!
- Install Deno.
- Lots of examples in the
tests
andbenchmarks
directories.- An extremely simple example:
add.json
in the canonical representation, or the equivalent text for your human convenience.
- An extremely simple example:
- How to load up and process a Bril program, using Python as an example, but remember that you can use any language you like.
- Getting started with generating the CFG.
- Try it yourself!
- Afterward, if you’re curious, check out a completed implementation (with some added fanciness) in the examples directory (see
form_blocks.py
,cfg.py
, andcfg_dot.py
).
- Philosophy.
- Turnt is a tool you might like for testing compiler tools.
- Turnt does snapshot testing, also known as golden or expect testing. It’s different from other kinds of testing you might have done in the past, like unit testing, in that you don’t have to write a spec: you just run the program and “lock in” its output as the expected output.
- It might feel weird, but I personally think snapshot testing represents a wonderful effort/reward trade-off for compilers. Check out a gentler introduction in a blog post about snapshot testing for compilers.
Tasks
Your goal is to get familiar with Bril.
- Write a new benchmark.
- You can write it by hand, use the TypeScript compiler, or generate it some other way.
- Try running it with brili.
- Open a pull request to add your new benchmark.
- Add your code to the the
benchmarks
directory. - Use
turnt --save yours.bril
to create the test outputs for your new benchmark. (See the Turnt README for details.) - If your
@main
function takes arguments, you can specify ones to use in testing with anARGS:
comment, like this. - Mention it in the docs.
- Add your code to the the
- Write a program to analyze or transform Bril programs in some small way.
- Pick your favorite programming language—there is no “starter code,” so you can start from scratch.
- Load up a JSON file. You can start with this tiny one!
- Read the docs.
- Do something unambitious with it: count the number of add instructions, or add a
print
instruction before every jump, or whatever. Pick something small and contrived!
- Use Turnt to test your new tool. Think carefully about what makes a good test for your tool, no matter how trivial.
- Along the way, you may run into problems! Ask questions on Zulip, and open issues and pull requests to describe or fix problems. For example, some benchmarks you might imagine probably can’t be written easily because Bril is too simple. Mention this on Zulip, and consider pitching in to help add features.
- As with all implementation tasks:
- Summarize your work in the discussion thread associated with this lesson (see the link above). Check out the relevant section in the syllabus to know more about what this post should consist of.
- Submit the URL for your source code on CMS.