Overview

In this assignment, we will implement an interpreter for a subset of ML. We have seen that programs, such as machine language programs for the Hypothetical Machine, can be executed or interpreted by other programs. In the case of the Hypothetical Machine, the interpreter modeled the hardware architecture and implemented the fetch/execute cycle of the processor in order to execute programs.

Executing a high-level language requires parsing source text to some intermediate form, such as an Abstract Syntax Tree (AST). Compilers can then translate the AST to machine code; interpreters can execute the program directly from the AST representation. Our implementation will use the AST directly, implying we will enter programs as an AST. For example, the ML:

3+4;

can be represented as an AST for Language Three by:

val3( Plus(Const 3, Const 4), [] );

with the AST graphical representation of:

               Plus
              /      \
     Const 3     Const 4

Language 3 will be extended to implement additional ML language constructs.

Assignment 

Define Language 4, an extension of Language 3. Below is a somewhat contorted ML program using all of the new constructs:

let val fact = fn n => if n=0 or n=1 then 1 else n * fact(n-1)
in
    fact 5
end

Language 4 extends Language 3 with four new constructs:

1. Sub - Similar to Plus operator.
2. If - Conditional operator, if-then-else.
3. Eq - Eq operator, returns Bool true or Bool false.
4. Or - Or operator, returns Bool true or Bool false.

Suggested Method of Solution

1. Start with Language 3 and Debugging instructions; copy and paste the following ML.

   The symbol T may still be defined from a previous assignment. If so, ML will give an error similar to:

   Can't unify ('a * 'b) list with BOOL (Different type constructors) Found near
   ::( ( var, value), T)

   The fix is to change any T to some other symbol, t will do, as in the following.

   fun lookup (V,(var,value)::t) = if (V=var) then value else lookup(V,t);
    

   PolyML.Compiler.debug := true; open PolyML.Debug; trace true;  datatype AST =     Const of int |     Var of string |     Plus of AST * AST |     Times of AST * AST |     Let of string * AST * AST |     Fn of string * AST |     Apply of AST * AST; fun lookup (V,(var,value)::T) = if (V=var) then value else lookup(V,T); fun val3 (Const(X), _) = Const(X) |    val3 (Var(V), Context) = lookup(V, Context) |    val3 (Plus(Const(X),Const(Y)),_) = Const(X+Y) |    val3 (Plus(X, Y), Context) = val3(Plus(val3(X,Context),val3(Y,Context)), Context) |    val3 (Times(Const(X),Const(Y)),_) = Const(X*Y) |    val3 (Times(X, Y), Context) = val3(Times(val3(X,Context),val3(Y,Context)), Context) |    val3 (Let(V,Exp1,Exp2), Context) = val3(Exp2, (V, val3(Exp1, Context))::Context) |    val3 (Fn(Formal, Body), _) = Fn(Formal, Body) |    val3 (Apply( Fn(Formal, Body), Actual), Context) = val3( Body,(Formal,val3(Actual, Context))::Context) |    val3 (Apply( Var(V), Actual), Context) = val3( Apply( val3(Var(V), Context), Actual), Context);

    

2. Define an additional datatype AST for Bool, Sub, If, and Eq constructs.
   
       Bool of bool | 
       Sub of AST * AST |
       Eq of AST * AST |
       If of AST * AST * AST

    

3. Add Sub which is very similar to Plus. Perform unit level test using:

   val4(Sub(Const 5,Const 1),[]);                     returns 4
   val4(Sub(Var "n",Const 1),[("n",Const 5)]);        returns 4

    

4. Eq is very similar to Plus also but should return a Bool AST rather than a Const. Perform unit level test using:

   val4(Eq(Const 3,Const 4),[]);                                 returns Bool false
   val4(Eq(Bool true, Bool false),[]);                           returns Bool false
   val4(Eq(Var "X",Var "Y"),[("Y",Const 4),("X",Const 4)]);      returns Bool true
    

5. Or is very similar to Eq but requires an additional AST datatype definition. Give unit level test results.
    
6. If can be implemented most directly as two cases.             
   1. Case One where E1 is either Bool true or Bool false, that is: If (Bool b, E2, E3)
      • Reduce E2 when b is true or E3 when b is false using the ML: if b then E1 else E2
   2. Case Two reduces the general form: If(E1, E2, E3) to If (Bool b, E2, E3) as in Case One. Remember that If short-circuits, E2 is evaluated only when E1 reduces to true; E3 is evaluated only when E1 reduces to false.

   Perform unit level test using:

   val4(If(Bool true, Const 3, Const 4),[]);                    return Const 3
   val4(If(Or(Bool true, Bool false), Const 3, Const 4),[]);    return Const 3

7. Perform system level tests using:

   val4(If(Eq(Const 3,Const 4),Const 1,Const 2),[]);    returns 2
   val4(If(Eq(Var "A",Var "B"),Var "A",Var "B"),[("A",Const 4),("B",Const 3)]);
                                                        returns Const 3

8. Final system level test is to compute 5!

   val4(
    Let( "fact",
         Fn( "n",
             If( Or(Eq(Var "n", Const 0),Eq(Var "n", Const 1)),
                 Const 1,
                 Times(Var "n", Apply(Var "fact", Sub(Var "n",Const 1))))), 
         Apply(Var "fact", Const 5)),
    []);
    

9. Give the Language 4 definition (i.e. val4) and test results for finding the Fibonacci value for Const 6. Define new operations if you want but it is not necessary.
    

Turn In

1. Cover sheet with your name, date, and Homework 10.
2. Listing of val4.
3. Screen shot of 3-9 tests above. Include debug trace page showing final result.