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

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)),[]);
            Fn("z", Plus(Var "z", Const 2))

     

15. (4) What are the values of Formal, Body, Actual, Context?    Formal="x", Body=Plus(Var “x”, Const 4),
                                                                                                         Actual=Const 2, 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:        Lines 10, 2, 5

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