Lesson 2: Representing Programs

• discussion thread
• representing programs
• getting started with Bril
• tasks due January 30

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 and br, 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.
    • Part of the Bril philosophy is that it is language-neutral. As a consequence, the tools you get in the Bril repository are written in a hodgepodge of different languages.
      • The video’s installation instructions are stale: it refers to using yarn to install stuff. It’s now somewhat easier:
        1. Install Deno. brew install deno on macOS, for example.
        2. Type deno install -g brili.ts.
        3. As Deno instructs, add $HOME/.deno/bin to your $PATH. That’s it!
      • Also, there is another (maybe easier) way to install the Python text-format tools, using uv. Try uv tool install . in the bril-txt directory.
    • Lots of examples in the tests and benchmarks directories.
      • An extremely simple example: add.json in the canonical representation, or the equivalent text for your human convenience.
    • Interacting with Bril programs using Unix pipelines. For example, to run programs you write in the text format, use bril2json < stuff.bril | brili.
    • 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.
      • Notably, call instructions are (usually) not considered terminators.
      • 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, and cfg_dot.py).
• 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 an ARGS: comment, like this.
    • Mention it in the docs.
• Write a program to analyze or transform Bril programs in some other small way that you invent.
  • 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.
• Implement the algorithms to form basic blocks and build a control flow graph.
• 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.