Adding Garbage Collection to the Runtime

QUIZ: Tuples on the Heap

Using the above “library” we can write code like:

def tup4(x1, x2, x3, x4):
  (x1, (x2, (x3, (x4, false))))

def get(e, i):
  if (i == 0):
    head(e)
  else:
    get(tail(e), i-1)

let quad = tup4(1, 2, 3, 4) in
  get(quad, 0) + get(quad, 1) + get(quad, 2) + get(quad, 3)

What will be the result of compiling the above?

1. Compile error
2. Segmentation fault
3. Other run-time error
4. 4
5. 10

QUIZ

Using the above “library” we can write code like:

let quad = tup4(1, 2, 3) in
  get(quad, 0) + get(quad, 1) + get(quad, 2) + get(quad, 3)

What will be the result of compiling the above?

1. Compile error
2. Segmentation fault
3. Other run-time error
4. 4
5. 10

Example 1: Garbage at End

let x = (1, 2)
  , y = let tmp = (10, 20)
        in tmp[0] + tmp[1]
in
  (x[0] + y, x[1] + y)

Click to see video

Example 2: Garbage in Middle

let y = let tmp = (10, 20)
        in tmp[0] + tmp[1]
  , x = (1, 2)

in
  (x[0] + y, x[1] + y)

Click to see video

Example 3: Garbage in Middle (with stack)

def foo(p, q):
  let tmp = (10, 20)
  in tmp[0] + tmp[1]

let y  = foo(10, 20)
  , x  = (y, y + 1)
  , z  = foo(100, 200)
in
  x[0] + z

Click to see video

Example 4: Transitive Reachability

def range(i, j):
  if (i < j):
    (i, range(i+1, j))
  else:
    false

def sum(l):
  if l == false:
    0
  else:
    l[0] + sum(l[1])

let t1 =
         let l1 = range(0, 3)
         in sum(l1)
  , l  = range(t1, t1 + 3)
in
  (1000, l)

Click to see video

Postlude

What will you learn ?

Core principles of compiler construction

• Syntax Trees
• Type Checking (oops!)
• Intermediate forms
• Optimization
• Closures
• Calling conventions (Stacks)
• Memory management (Heap)
• Garbage collection

Several new languages

• Haskell to write the compiler
• C to write the “run-time”
• X86 compilation target

How to write a large program

• How to use types for design
• How to add new features / refactor
• How to test & validate

This is just the beginning …

This is a tiny fraction of what we know about compilers

Optimizations

• Many many more optimizations
• See this https://www.lihaoyi.com/post/HowanOptimizingCompilerWorks.html

Type checking and Static analysis

• Fast user-interfaces for error reporting
• Anders Hejlsberg on Modern Compiler Construction
• Checker framework

Instrumenting code for debugging

• https://rr-project.org/

Just-in-time (JIT) Compilation

• V8, Spidermonkey,…
• Torque

Formal semantics and Correctness

• (Compcert, CakeML, …)

… and many new things are still to be invented!

Optimization

How to generate the fastest possible code

• Image processing with Halide
• Finding the best sequence of instructions Superoptimization
• Optimizing Tensor Computations

Verification

How to get the machine to check your code

• Contracts with Dafny
• Refinement types LiquidHaskell
• Theorem provers Coq, Isabelle, Lean

Synthesis

How to get the machine to write your code

• Using examples Flashfill
• Using fancy types Synquid
• Using live programming Snippy

Compilers touches pretty much all of CS …

Theory

• Regular expressions, Parsing, Optimizations, Graph algorithms

HCI

• Interacting with the PL/Compiler
• Type annotations
• Error messages and reporting

HW/Architecture

• duh.

Machine Learning

• “Tensorflow”
• Optimizing ML computations
• Differentiable programming
• PL for ML Spark
• HW and compilers for ML OctoML

Security

• Compiler bugs == Security vulnerabilities
• Buffer overflows, Heap spraying, JIT based attacks …
• “Return-oriented Programming”