Exercise 11    Name    ____________________   Points __/33

Document last modified: 
 

datatype AST =
    Const of int |
    Plus of AST * AST |
    Times of AST * AST;

1. fun val1 (Const(n)) = Const(n)
2. |    val1 (Plus(Const(v1),Const(v2))) = Const(v1+v2)
3. |    val1 (Plus(E1,E2))=val1(Plus(val1(E1),val1(E2)))
4. |    val1 (Times(Const(v1),Const(v2))) = Const(v1*v2)
5. |    val1 (Times(E1,E2))=val1(Times(val1(E1),val1(E2)));

Language 1

1. (3) Give the following in Language 1:
   1. 6 + 5
   2. 6 + 5 * 3
       
2. (4) Trace the following executions:
   1. val1(Const 3);
   2. val1(Times(Const 3,Const 4);
   3. val1(Times(Const 2,Plus(Const 3,Const 4));

datatype AST =
    Const of int |
    Var of string |
    Plus of AST * AST |
    Times of AST * AST |
    Let of string * AST * AST;

1. fun lookup (V,(var,value)::T) = if (V=var) then value else lookup(V,T);
2. fun val2 (Const(X), _) = Const(X)
3. |    val2 (Var(V), Context) = lookup(V,Context)
4. |    val2 (Plus(Const(X),Const(Y)),_) = Const(X+Y)
5. |    val2 (Plus(X, Y), Context) = val2(Plus(val2(X,Context),val2(Y,Context)), Context)
6. |    val2 (Times(Const(X),Const(Y)),_) = Const(X*Y)
7. |    val2 (Times(X, Y), Context) = val2(Times(val2(X,Context),val2(Y,Context)), Context)
8. |    val2 (Let(V,Exp1,Exp2), Context) = val2(Exp2, (V, val2(Exp1, Context))::Context);

Language 2

3. (1) Give the ML syntax for:
           val2(Let("X", Const 2, Times(Var "X“,Const 3)), []);
    
4. (1) Give the Language Two syntax for:
           let val X = 3 in X*5 end
    
5. (1) Give the Language Two syntax for:
           let val X = 3 in X*5+X end
    
6. (1) Which line(s) reduces variables?
    
7. (1) Which line(s) reduces Plus?
    
8. (1) Which line(s) reduces Let?
    
9. (1) Where exactly is a variable name bound to a value?
    
10. (2) Trace lines executed by:
            val2(Var “Y", [(“Y",Const 6)]);
     
11. (4) What is V, Exp1, Exp2, Context for:
            val2(Let(“Y",Const 3,Var “Y"),[(“Y",Const 6)]);
     
12. (2) What is the environment during execution of line 8 for:
            val2(Let(“Y",Const 3,Var “Y"),[(“Y",Const 6)]);
     
13. (2) Trace lines executed by:
            val2(Let(“Y",Const 3,Var “Y"),[(“Y",Const 6)]);

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;

1. fun lookup (V,(var,value)::T) = if (V=var) then value else lookup(V,T);
2. fun val3 (Const X, _) = Const(X)
3. |    val3 (Var V, Context) = lookup(V, Context)
4. |    val3 (Plus(Const X,Const Y),_) = Const(X+Y)
5. |    val3 (Plus(X, Y), Context) = val3(Plus(val3(X,Context),val3(Y,Context)), Context)
6. |    val3 (Times(Const X,Const Y),_) = Const(X*Y)
7. |    val3 (Times(X, Y), Context) = val3(Times(val3(X,Context),val3(Y,Context)), Context)
8. |    val3 (Let(V,Exp1,Exp2), Context) = val3(Exp2, (V, val3(Exp1, Context))::Context)
9. |    val3 (Fn(Formal, Body), _) = Fn(Formal, Body)
10. |    val3 (Apply( Fn(Formal, Body), Actual), Context) = val3( Body,(Formal,val3(Actual, Context))::Context)
11. |    val3 (Apply( Var(V), Actual), Context) = val3( Apply( val3(Var(V), Context), Actual), Context);

Language 3

14. (2) What is the result of:
    
        val3(Fn(“z”, Plus(Var “z”, Const 2)), []);

     

15. (4) What are the values of Formal, Body, Actual, Context?

        val3( Apply( Fn(“x”, Plus(Var “x”, Const 4)), Const 2), []);
     

16. (3) What are the first 3 line(s) in the reduction of:

          val3( Apply( Fn(“x”, Plus(Var “x”, Const 4)), Const 2), []);