Compiler Feature

• Assign: Tuesday, 18 May
• Due: Standard due date Friday, 28 May
• Submit: git add, git commit, and git push your completed code.

Contents

• Revised End-of-Term Plan
  • Timeline
  • Format

Revised End-of-Term Plan

According to the revised end-of-term plan, Roost compiler implementation work will be abridged to your current Front End checkpoint. After completing that and the Tiny Compiler Back End mini-project, you will complete one small extension with your current team, a new team, or on you own. Consult with me as you are deciding what option to pursue.

Timeline

For all work, consider May 28 the standard deadline. If really necessary, work can be accepted until 4 PM Tuesday June 1 ET, but I cannot guarantee to be available for assistance during this extended window.

Format

There are three general options:

• Extend tinyc: Add a small feature to the Tiny language or compiler and document it thoroughly in the README. Feel free to use the tiny-cup version for this. Suggestions:

  • Implement an additional optimization pass following normal optimizations and before code generation that minimizes the amount of stack storage space required by rewriting the TAC code to reuse TAC cells as much as possible.

  • Implement a WebAssembly code generator.

  • Implement an additional data type and associated statements/expressions, such as tuples and indexing:

    x = ( input, 3, input ) ;
    y = 1;
    print ( ( x [ 2 ] ) + ( x [ y ] ) ) ;
    

  • Implement support for an implicit stack with push/pop:

    x = input;
    push ( x + 7 ) ;
    print ( pop + 3 );
    

  • Implement basic loops (terminates when x is 0):

    x = input ;
    while x {
      print x ;
      x = x - 1 ;
    }
    

  • Some other small feature you have wished for.

• Extend roostc: Add a small feature to your Roost compiler front end and document it thoroughly in the README. Suggestions:
  • Improved syntax error reporting using explicit error directives in the grammar.
  • Nestable comments: /* This /* comment does not end here: */ it ends here: */

  • Error reports that include helpful visualization:

    [4:17] Name Error: No variable 'lnegth' is in scope.
           let nums = [0; lnegth];
                          ^^^^^^
    

  • Scope/type error reporting that keeps going past the first error to report all errors that it can find before rejecting an ill-formed program.

  • Scope errors that suggest similar (potential typo) names when a variable name is not found in scope.

    [45:23] Name Error: No variable 'foo' is in scope. Did you mean 'food: i64', defined at [42:13]?

  • A for comprehension over arrays, implemented as syntactic sugar that is desugared (translated) at the AST level. Code like this:

    for (elem in getArray()) {
      println(elem.name);
      let sid = elem.studentID;
      total = total + string_length(elem.name) + sid;
    }

    would be translated at AST construction time during parsing or immediately after parsing and AST construction, before scope checking and name resolution, to [an abstract form equivalent to]:

    {
      let $synthetic_array_var = getArray();
      let mut $synthetic_index_var = 0;
      while ($synthetic_index_var < $synthetic_array_var.length) {
        let elem = $synthetic_array_var[$synthetic_index_var];
        $synthetic_index_var = $synthetic_index_var + 1;
        println(elem.name);
        let sid = elem.studentID;
        total = total + string_length(elem.name) + sid;
      }
    }

    Thus later stages of the compiler need not know about this extra syntactic form. The use of $ in the generated variable names ensures that (internally, inside the AST) the generated variable names never accidentally capture other existing variables.

  • Some other feature you have wished for.

  • This small feature could be whatever Front End checkpoint is next after what you are working on now, although the “small feature” does not need to be as large as an entire Front End checkpoint.

• Explore compiler research: Read a research paper on a compiler-related topic and produce a short video presentation teaching its big ideas for a CS 301 Spring 2021-level audience. Some suggestions:

  • Type system applications:
    • Language-Based Information-Flow Security.
      Andrei Sabelfeld, Andrew C. Myers. IEEE Journal on Selected Areas in Communications, 2003.
      http://www.cs.cornell.edu/andru/papers/jsac/sm-jsac03.pdf
    • EnerJ: Approximate Data Types for Safe and General Low-Power Computing.
      Adrian Sampson, et al.. PLDI 2011.
      https://doi.org/10.1145/1993498.1993518
      (Off campus: https://www.cs.cornell.edu/~asampson/media/papers/enerj-pldi2011.pdf)
      • EnerJ, The Language of Good-Enough Computing. (General-audience article.)
        Adrian Sampson, Luis Ceze, Dan Grossman. IEEE Spectrum.
        https://spectrum.ieee.org/computing/software/enerj-the-language-of-goodenough-computing

  • Static analysis:

    • KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. Cristian Cadar, Daniel Dunbar, Dawson Engler. OSDI 2008.
    • All You Ever Wanted to Know about Dynamic Taint Analysis and Forward Symbolic Execution (but Might Have Been Afraid to Ask). Edward J. Schwartz, Thanassis Avgerinos, David Brumley. Oakland 2010.
    • Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. Patrick and Radhia Cousot. POPL 1977.
    • Dataflow Analysis for Concurrent Programs Using Datarace Detection. Ravi Chugh, et al. PLDI 2008.
    • Escape Analysis for Java: Theory and Practice. Bruno Blanchet. TOPLAS vol. 25 issue 6, November 2003.
    • Lecture Notes: Pointer Analysis. Jonathan Aldrich.

  • Dynamic analysis:

    • Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation. Nicholas Nethercote, Julian Seward. PLDI 2007.
    • Tracking Bad Apples: Reporting the Origin of Null and Undefined Value Errors. Michael Bond, et al. OOPSLA 2007.
    • FastTrack: Efficient and Precise Dynamic Race Detection. Cormac Flanagan, Stephen N. Freund. PLDI 2009.
    • Coz: Finding Code that Counts with Causal Profiling. Charlie Curtsinger, Emery D. Berger. SOSP 2015.
    • TaintDroid: An Information-Flow Tracking System for Realtime Privacy Monitoring on Smartphones. William Enck, et al. TOCS vol. 32, issue 2, June 2014.
    • Efficient Path Profiling. Thomas Ball, James Larus. MICRO 1996.
    • Dynamically Discovering Likely Program Invariants to Support Program Evolution. Michael Ernst, et al. ICSE 1999.