%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Objects (20 points)

Given the following Java declarations:

class A {
    int i = 3; 
    int m1 () { return i + m2(); }
    int m2 () { return i + m1(); }
}

class B extends A {
    int i = 30;
    int m1 () { return i + super.m1(); }
    int m2 () { return i + m3(); }
    int m3 () { return i; }
}

class C extends B {
    int i = 300;
    int m1 () { return i + super.m1(); }
    int m3 () { return i; }
}

Answer the following questions:
* Draw a diagram that shows how a realistic JVM would internally
represent an instance of class C.

----------------------------------------------------------------------

An instance of class C looks like:

  { { 3, 30, 300 } , pointer to class C }

----------------------------------------------------------------------

* Draw diagrams that show how a realistic JVM would internally
represent the classes A, B, and C.

----------------------------------------------------------------------

Class A looks like:

  { pointer to superclass Object, 
    pointer to method m1 defined in class A, 
    pointer to method m2 defined in class A 
  }

Class B looks like: 

  { pointer to superclass A, 
    pointer to method m1 defined in class B, 
    pointer to method m2 defined in class B, 
    pointer to method m3 defined in class B
  }

Class C looks like: 
   
  { pointer to superclass B, 
    pointer to method m1 defined in class C, 
    pointer to method m2 defined in class B, 
    pointer to method m3 defined in class C
  }

----------------------------------------------------------------------

* Trace the main steps needed to execute the call
new C().m1(). Be sure to tell me what the result of the call
is!

----------------------------------------------------------------------

Steps: 
* Create instance of class C
  --> Class of current instance is C <--
* Go to first method in class C
  --> Current class is C <--
* Access variable i in current class (get 300)
* Go to super class
  --> Current class is B <--
* Access variable i in current class (get 30)
* Go to super class
  --> Current class is A <--
* Access variable i in current class (get 3)
* Go to second method in class C
  --> Current class is B <--
* Access variable i in current class (get 30)
* Go to third method in class C
  --> Current class is C <--
* Access variable i in current class (get 300)
* Result is 663

----------------------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
More Objects (15 points)

This problem builds on the implementation of the OO interpreter done
in Homework 7. The main features of this implementation are summarized
on the next page. 

We will extend the OO language to be interpreted with
a new construct:

datatype exp = ...
  | Cast of string * exp

The informal semantics is as expected. A Cast(s,e) expression
evaluates e to an object reference, then checks that the class
of the object is a subclass the class s. If the check succeeds,
the evaluation returns the object reference as its result; otherwise
the evaluation raises an exception. 

The main changes needed to support the new construct are the following: 

* add a new clause to the definition of evalexp in the MakeInterpreter
functor,

* add a isSubclass function to the OO_INTERPRETER interface,

* add an implementation of the isSubclass function in the
OO_Interpreter structure.

Describe these changes in as much detail as possible. An ideal
solution would give the entire code, possibly relying on some
non-public functions implemented in the homework, as long a short
description of these functions is given.

----------------------------------------------------------------------

In functor: 

  | evalexp (A.Cast(cn,e)) env = 
        let val objref = evalexp e env
        in case objref of 
            (EV.ObjectRef obj) =>
                let val oclass = OO.getClassName obj
                    val test = OO.isSubclass oclass cn
                in if test then objref
                   else raise ClassCastException(oclass,cn)
                end
          | _ => raise (InternalError "Bug in typechecker")
        end

In interface: 

  val isSubclass : Absyn.className -> Absyn.className -> bool

In oo interpreter:

  fun isSubclass cn1 cn2 = 
      (cn1=cn2) orelse
      (let val (Class{superName=sn1,...}) = lookupClass cn1
       in if sn1="object" then false
          else isSubclass sn1 cn2
       end)

----------------------------------------------------------------------

functor MakeInterpreter (OO_Interpreter : OO_INTERPRETER) : INTERPRETER = 
struct
  (* Implementation of an interpreter parametrized by the OO constructs *)
  fun evalexp exp env = ...
end

structure OO_Interpreter : OO_INTERPRETER = 
struct
  (* Implementation of the OO constructs *)
end

signature INTERPRETER = sig
  val eval : Absyn.prog -> unit
end

signature OO_INTERPRETER = sig
  type object
  type value = object Env_Value.value
  type env = object Env_Value.env

  val elaborateClassDecls : Absyn.class list -> unit
  val getClassName : object -> Absyn.classname
  val find_method_and_apply : 
      (Absyn.exp -> env -> value) -> 
      Absyn.methodname -> Absyn.classname -> object -> value list 
      -> value
  val new_object : Absyn.classname -> object
end

signature ENV_VALUE = sig
  datatype 'a value = 
      Num of int
    | Closure of Absyn.parametername list * Absyn.exp * 'a env
    | List of 'a value list
    | Void
    | ObjectRef of 'a
    | Classname of Absyn.classname
  and 'a env = 
      EmptyEnv
    | ExtendList of ('a env) * (string list) * ('a value ref list)
    | ExtendArray of ('a env) * (string list) * ('a value ref array)

  val lookupL : 'a env -> string -> 'a value ref 
  val lookup : 'a env -> string -> 'a value
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Variable Offsets (20 points)

I have alluded several times in class to the fact that variable names
are replaced by offsets during compilation.

Consider the following simple source language and the test expression:

structure Absyn = 
struct 
    datatype exp = 
        Var of string
      | Num of int
      | Plus of exp list
      | Lambda of string list * exp 
      | App of exp * exp list

val test = 
  App(Lambda(["a","b","c"],
        App(Lambda(["a","b"],
              Plus([Var "c", 
                    Plus([Var "a", Var "b"])])),
            [Var "b", Var "c"])),
      [Num 1, Num 2, Num 3]);
end

The evaluation of expressions in the source language usually requires
an environment which associates every variable with its value. For
example, at the point where we are ready to perform the additions in
the test expression above, the environment looks like:

FRAME 1:   (a b c) --> (1 2 3)
FRAME 2:     (a b) --> (2 3)

Because of the static scope rules, the shape (but not the actual
contents) of that environment can be completely determined without
evaluating the expression. Indeed, examination of the test expression
should reveal that the shape of the environment at the point where we
are ready to perform the additions is:

FRAME 1:   (a b c) --> (? ? ?)
FRAME 2:     (a b) --> (? ?)

The first frame corresponds to the first Lambda and the second
frame corresponds to the second Lambda. Given this information,
we can pre-compute the following (zero-based) offsets for the
arguments to the additions:

* The value of the first argument to Plus (the value of
Var "c") can be found by traversing the environment as
follows. Starting from the most recent frame, skip one frame, and get
the value at index 2 in the next frame. We can summarize this
information as the pair (1,2).
* The values of the arguments to the inner Plus are found
at offsets (0,0), and (0,1) in the environment respectively.

Given this idea, we can compile the source language to a language in
which all variable names have been replaced by offsets. In addition,
Lambda expressions only need the number of arguments but not
their names. The syntax of such a target language is:

structure Target = 
struct
    datatype exp = 
        Var of int * int
      | Num of int
      | Plus of exp list
      | Lambda of int * exp 
      | App of exp * exp list
end

The evaluation of expressions in the target language can proceed using
the offsets instead of the names. Here is a complete interpreter for
the target language:

structure Eval =
struct
  structure T = Target

  exception Error

  datatype value = 
      Prim of int
    | Closure of int * T.exp * env
  withtype env = (value list) list

  fun extend env vs = vs :: env
  fun lookup env d p = List.nth(List.nth(env,d),p)

  fun eval (T.Var (d,p)) env = lookup env d p
    | eval (T.Num i) env = Prim i
    | eval (T.Plus es) env = 
      let val [Prim v1, Prim v2] = map (fn e => eval e env) es
      in Prim (v1+v2)
      end
    | eval (T.Lambda(n,e)) env = Closure(n,e,env)
    | eval (T.App(e,es)) env = 
      let val (Closure(n,body,cenv)) = eval e env
          val args = map (fn e => eval e env) es
      in if (length args = n) 
         then eval body (extend cenv args)
         else raise Error
      end
end

Write the function translate that converts from source
expressions to target expressions. The result of converting the
test expression above is:

  T.App(T.Lambda(3,
          T.App(T.Lambda(2,
                  T.Plus[T.Var (1,2),
                         T.Plus [T.Var (0,0), T.Var (0,1)]]),
                [T.Var (0,1), T.Var (0,2)])),
        [T.Num 1, T.Num 2, T.Num 3]) 

----------------------------------------------------------------------

    exception Unbound_Variable of string

    fun extend env xs = xs :: env

    fun lookup env x = 
        let fun loop [] d p = raise (Unbound_Variable x)
              | loop ([] :: env) d p = loop env (d+1) 0
              | loop ((y::ys) :: env) d p = if x=y then (d,p) 
                                            else loop (ys::env) d (p+1)
        in loop env 0 0
        end 
    
    fun translate (A.Var s) env = T.Var (lookup env s)
      | translate (A.Num i) env = T.Num i
      | translate (A.Plus es) env = 
        T.Plus (map (fn e => translate e env) es)
      | translate (A.If(e1,e2,e3)) env = 
        T.If(translate e1 env, translate e2 env, translate e3 env)
      | translate (A.Lambda(ss,e)) env = 
        T.Lambda(length ss, translate e (extend env ss))
      | translate (A.App(e,es)) env = 
        T.App(translate e env, map (fn e => translate e env) es)

----------------------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Call-by-need (15 points)

Call-by-need is the default parameter-passing mechanism in languages
like Haskell. We will only consider the following small subset:

structure Absyn = 
struct 
    datatype exp = 
        Var of string
      | Num of int
      | Plus of exp list
      | If of exp * exp * exp 
      | Lambda of string list * exp 
      | App of exp * exp list
end

The evaluation of the language proceeds in a familiar way: we have a
notion of environments, a notion of value, and an interpreter that
maps abstract syntax expressions and environments to values. The
fundamental change is that arguments to functions are not
evaluated at the time when the function is called. Instead enough
information is saved in the environment (essentially a closure but
traditionally called a thunk). Then when the value of a
variable is needed (hence the call-by-need), this
information is used to calculate a value for the variable. So far, we
have described call-by-name. What distinguishes call-by-need from
call-by-name is that, once computed, the value of the variable is used
to update the environment so that later accesses to the variable need
not recompute it.

Here are the beginnings of a call-by-need interpreter that you should
complete: 

structure Eval =
struct
  structure A = Absyn

  exception Error

  datatype value = 
      Prim of int
    | Closure of string list * A.exp * env
  and entry = 
      Evaluated of value
    | Thunk of A.exp * env
  withtype env = (string * entry ref) list

  fun extend env xs rs = ListPair.zip(xs,rs) @ env

  fun lookup [] x = raise Error
    | lookup ((y,r)::env) x = if x=y then r else lookup env x

----------------------------------------------------------------------

  fun force r = 
      case !r of 
          Evaluated v => v
        | Thunk (e,env) => let val v = eval e env
                           in r := Evaluated v; v
                           end

  and eval (A.Var s) env = force (lookup env s)
    | eval (A.Num i) env = Prim i 
    | eval (A.Plus es) env = 
      let val [Prim v1, Prim v2] = map (fn e => eval e env) es
      in Prim (v1+v2)
      end
    | eval (A.If(e1,e2,e3)) env = 
      let val (Prim v1) = eval e1 env
      in if (v1 = 0) then eval e2 env else eval e3 env
      end
    | eval (A.Lambda(xs,e)) env = Closure(xs,e,env)
    | eval (A.App(e,es)) env = 
      let val (Closure(xs,body,cenv)) = eval e env
          val newenv = extend cenv xs (map (fn e => ref (Thunk(e,env))) es)
      in eval body newenv
      end

----------------------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Callcc and Control Operators (15 points)

Write an interpreter for the following language:

datatype exp = 
    Var of string
  | Lambda of string * exp 
  | App of exp * exp 
  | Callcc of string * exp
  | Throw of exp * exp

The informal semantics is the following. The functional subset has the
same semantics as ML (call-by-value with static scope). The evaluation
of a Callcc(s,e) expression captures the current continuation,
binds it to the variable s, and then evaluates the expression
e. The evaluation of Throw(e1,e2) evaluates e1 to
a continuation (say k), then evaluates e2 to a value (say
v). Instead of returning v to the current continuation, it ignores
the current continuation and uses k instead. 

You may either use ML's callcc and throw or write your
interpreter in CPS.

----------------------------------------------------------------------

datatype value = 
    Closure of string list * A.exp * env
  | Continuation of value K.cont 
withtype env = (string * value) list

exception Error
fun extend env xs rs = ListPair.zip(xs,rs) @ env
fun lookup [] x = raise Error
  | lookup ((y,r)::env) x = if x=y then r else lookup env x

fun eval (A.Var s) env = lookup env s
  | eval (A.Lambda(xs,e)) env = Closure(xs,e,env)
  | eval (A.App(e,es)) env = 
    let val (Closure(xs,body,cenv)) = eval e env
        val vs = map (fn e => eval e env) es
    in eval body (extend cenv xs vs)
    end
  | eval (A.Callcc(s,e)) env = 
    K.callcc (fn k => eval e (extend env [s] [Continuation k]))
  | eval (A.Throw(e1,e2)) env = 
    let val (Continuation k) = eval e1 env
        val v = eval e2 env
    in K.throw k v
    end

----------------------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Types (10 points)

For each of the following ML expressions, either give its type, or
explain the type error:

------------------ 

let fun f x = x+1
in f 3
end

--> int
------------------ 

let fun f x = (x+1) div x
    fun g (h,y) = h( f (y+y) )
in g(f,3)
end

--> int
------------------ 

fun help_ack f = fn n => if n=0 
                         then f 1
                         else f ((help_ack f) (n-1))

fun ack n = if n=0 
            then (fn y => y + 1)
            else help_ack (help_ack (n-1))

-->
  operator domain: int -> int
  operand:         int
  in expression:
    help_ack (n - 1)
------------------ 

let exception Error
    fun f x = if x then 3 else raise Error
in (f false) + 4 + (f true) + 5 + (f false)
end

--> int
------------------

datatype intlist = Empty | Cons of int * intlist

let fun f c = c
in f Cons
end

--> int * intlist -> intlist

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Inlining Using beta-reductions (10 points)

A beta-reduction formalizes the process of symbolically executing a
procedure call. For example if f has the declaration: 

fun f x y = x (y , y+1)

then a call to f in another part of the program can be
inlined during compilation. For example, a compiler can rewrite
the call f(g,4) to g(4,5) by doing a beta-reduction
and then performing the addition of the two constants. 

List at least three reasons that would prevent an optimizing compiler
from aggressively performing beta-reductions to try to eliminate
all function calls.

----------------------------------------------------------------------

Reasons: 

* Non-termination

* Side-effects

* Program size

* Separate compilation

----------------------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
