Chapter 12 Outlook

12.1 A Taste Of MiniScala

A MiniScala function to compute x to the power of y:

def pow(x: Int,  y: Int) =
  if (y == 0) 1                // pow(x, 0) == 1
  else if (even(y)) {
    val t = pow(x, y /2)       // pow(x, 2z) = pow(pow(x, z), 2)
    t * t
  } else {
    x * pow(x, y - 1)          // pow(x, z + 1) = x * pow(x, z)
  }

Say ``Hello’’:

val arr = new Array[Int](5);
arr(0) = 'H'; arr(1) = 'e'; arr(2) = 'l'; arr(3) = 'l'; arr(4) = 'o';

var i = 0;
while (i < 5) {
  putchar(arr(i));
  i = i + 1
}

Our implementation of MiniScala is already quite powerful.

• We can do essentially everything we can do in C
• Missing features (structs, strings): can be implemented as arrays

Are we done yet?

• Higher level features: nested first-class functions, objects
• Code quality: optimizations

12.2 More Functions

12.2.1 Nested Functions

Lambda lifting: first-order nested function gets additional arguments.

Function passed first-class as argument: partially apply to free variables

NOTE: currying is not natively supported with stack-based 2nd-class values

Second-class vs first-class: stack-allocated vs heap-allocated closure

ALTERNATIVE: linked frames, display, …

12.2.2 Closures

See arrays

12.3 Intermediate Representations

The term intermediate representation (IR) or intermediate language designates the data-structure(s) used by the compiler to represent the program being compiled.

Choosing a good IR is crucial, as many analyses and transformations (e.g. optimizations) are substantially easier to perform on some IRs than on others.

Most non-trivial compilers actually use several IRs during the compilation process, and they tend to become more low-level as the code approaches its final form.

12.4 Optimization

Dataflow etc.