CSE 428: Home Assignment 5

Spring 2001, CSE 428: Assignment 5

Distributed: March 22.
Due: April 3 in class. Note: because of MT2, we need to publish the solution for this assignment on April 3. Hence, no solutions can be turned in after this date (namely, late assignments will not be accepted this time).
Total maximum score: 100 points.

The purpose of this assignment is to provide some experience with writing simple SML programs. In particular, recursion and pattern matching with supplied datatypes will be tested.

Note: Some of these exercises produce a nested object. To make sure that the printer for SML shows you all of it, you can raise the print depth of the compiler by typing the following at SML's prompt.

Compiler.Control.Print.printDepth := 100;

After this, the compiler's printer will print structures up to depth 100.

[Points 40] Mobiles are simple structures often hanging from ceilings involving internal beams with strings attached to weights or other beams. We will model a mobile with the following data type.
```
   datatype mobile = node of mobile * mobile | leaf of int;
```
Some examples of mobiles are the following:
```
   val m1 = node (node(leaf 2, leaf 2), node(leaf 2, leaf 2));

   val m2 = node(node(leaf 2, node(leaf 1, leaf 1)), node(leaf 2,leaf 2));

   val m3 = node(node(node(leaf 2, leaf 2), node(leaf 2, node(leaf 1, leaf 1))),
                 node(leaf 4, leaf 4));

   val m4 = node(node(node(leaf 2, leaf 2), node(leaf 1, node(leaf 1, leaf 1))),
                 node(leaf 4, leaf 4));
```
The weight of a mobile is the sum of the all the weights (integers) at the leaves of the mobile. A mobile is balanced if it is either a leaf or if it is a node then the weight of the left and right subtrees must be the same and these subtrees must be balanced.
Write a function
```
 
   balance_weight : mobile -> bool * int
```
that takes a mobile and returns a pair. The first component of the pair is true if the mobile is balanced and otherwise it is false. The second component is the weight of the mobile. For instance, we should have the following evaluations:
```
   - balance_weight m1;

   val it = (true,8) : bool * int

   - balance_weight m2;

   val it = (true,8) : bool * int

   - balance_weight m3;

   val it = (true,16) : bool * int

   - balance_weight m4;

   val it = (false,15) : bool * int
```
Please write the solution without defining any auxiliary function and in such a way that each node of the mobile is visited only once (i.e. recursion over the mobile is done only once). Solutions which do not satisfy this requirement will get, at most, 30 points (for this exercise).

[Points 40] Consider the following datatype which we shall use to represent simple algebric expressions.

datatype exp = 
     Var of string  | Num of real  | Opr of string * exp * exp;

Some examples of simple expressions of this type would be

   val e1 = Var"x";

   val e2 = Num(3.2);

   val e3 = Opr("+", Var"x",Num 3.2);

   val e4 = Opr("+", Opr("*", Num 3.0,
                         Opr("^", Var "x", Num 2.0)),
                     Opr("*", Num 2.0, Var "x"));

Write a function deriv of type (exp * string) -> exp, where the first argument is the expression to be differentiated and the second argument is the name of the variable for which the derivative is to be done. In computing the derivate, only use the following derivative rules (assuming here that we are taking the derivative with respect to the variable x).

   Dz = 0  if z is a number or a variable different from x
   Dx = 1
   D(u+v) = Du + Dv
   D(u-v) = Du - Dv
   D(u*v) = v*Du + u*Dv
   D(u/v) = (v*Du - u*Dv) / (v^2)
   D(u^n) = n*(u^(n-1)*Du)  where n is a number

For this exercise you can define auxiliary functions if you want.

Note: When defining this function, it is okay to get aWarning: match nonexhaustiveerror message here since not all expressions will be given a derivative by these rules. For example, there is no rule for taking the derivative of x ^ x. The result of the derivative does not need to be in "simplified" form. That is, the expression Opr("+", Num 1.0, Num 1.0) can be left (although it's "simplified form" would be Num 2.0). For example, you should compute something like the following:

   - deriv (e4,"x");

   val it =
     Opr
       ("+",
        Opr
          ("+",Opr ("*",Opr ("^",Var "x",Num 2.0),Num 0.0),
           Opr
             ("*",Num 3.0,
              Opr ("*",Num 2.0,Opr ("*",Opr ("^",Var "x",Num 1.0),Num 1.0)))),
        Opr ("+",Opr ("*",Var "x",Num 0.0),Opr ("*",Num 2.0,Num 1.0))) : exp

Some more examples:

val a1 = Opr("+",
             Opr("*",
                 Num 3.0,
                 Opr("^", Var "x", Num 2.0)
             ),
             Opr("*",
                 Num 2.0,
                 Var "x"
             )
         );

- deriv(a1,"y");

val it =
  Opr
    ("+",
     Opr
       ("+",Opr ("*",Opr ("^",Var "x",Num 2.0),Num 0.0),
        Opr
          ("*",Num 3.0,
           Opr ("*",Num 2.0,Opr ("*",Opr ("^",Var "x",Num 1.0),Num
0.0)))),
     Opr ("+",Opr ("*",Var "x",Num 0.0),Opr ("*",Num 2.0,Num 0.0))) :
exp

****************************************************

val a2 = Opr("+",
             Opr("*",
                 Var "y",
                 Opr("^", Var "x", Num 2.0)
             ),
             Opr("*",
                 Var "x",
                 Var "z"
             )
         );

- deriv(a2,"y");

val it =
  Opr
    ("+",
     Opr
       ("+",Opr ("*",Opr ("^",Var "x",Num 2.0),Num 1.0),
        Opr
          ("*",Var "y",
           Opr ("*",Num 2.0,Opr ("*",Opr ("^",Var "x",Num 1.0),Num
0.0)))),
     Opr ("+",Opr ("*",Var "z",Num 0.0),Opr ("*",Var "x",Num 0.0))) :
exp

****************************************************

val a3 = Opr("-",
             Opr("/",
                 Opr("^", Var "y", Num 3.0),
                 Num 2.0
             ),
             Opr("/",
                 Var "y",
                 Var "x"
             )
         );             

- deriv(a3,"x");

val it =
  Opr
    ("-",
     Opr
       ("/",
        Opr
          ("-",
           Opr
             ("*",Num 2.0,
              Opr ("*",Num 3.0,Opr ("*",Opr ("^",Var "y",Num 2.0),Num
0.0))),
           Opr ("*",Opr ("^",Var "y",Num 3.0),Num 0.0)),
        Opr ("^",Num 2.0,Num 2.0)),
     Opr
       ("/",Opr ("-",Opr ("*",Var "x",Num 0.0),Opr ("*",Var "y",Num
1.0)),
        Opr ("^",Var "x",Num 2.0))) : exp

[Points 20] Consider representing just 13 cards of one suit of a deck of playing cards with the following datatype:
```
   datatype card = ace | numbered of int | jack | queen | king;
```
Write a function
```
   smaller : card * card -> bool
```
such that smaller(C,D) is true if and only if C is a card that is either the same as D or comes before D (in the usual ordering). Here, aces are the smallest cards, the numbered cards are ordered by their number value. After the numbered cards, jack is the next largest and is followed by the queen. King is the largest card. For example, of the following six expressions
```
   smaller(king,king);
   smaller(ace, ace);
   smaller(numbered 6, numbered 9);
   smaller(queen,numbered 5);
   smaller(jack,numbered 5);
   smaller(king, ace);
```
the first three evaluate to true and the remaining three evaluate to false.
For this exercise you can define auxiliary functions if you want.

Please click here

for some additional notes about this assignment. Please read them carefully.

How to write and test your solution

Download this solution frame and fill it in with your definitions. Save it with name XXXX.sml, where XXXX are the last 4 digits of your student id.

The code of the examples above are here. You can download them, then save it with name definitions.sml. Now you can enter sml with the Unix command

   /home/users2/sml/bin/sml

Now that you are in sml, you can load your code and the definitions, and set the print depth, with the commands

   - use "XXXX.sml";
   - use "definitions.sml";
   - Compiler.Control.Print.printDepth := 100;

Now you are ready to test your program. You can try the expressions above. For instance, if you type

   - balance_weight m1;

you should get the answer

   val it = (true,8) : bool * int

Please note the following:.

Please make sure that your program can be compiled and executed under the Unix sml. Solutions which cannot be compiled or executed will receive, at most, 40 points.
Please don't change the code of the data types !!!. Solutions which work only for your own definition of the data types will receive, at most, 40 points.
Its your responsibility to write a sound, reliable program, so please test your code thoroughly before you submit it.
The TA will test your program with some additional test cases. A program which works only for the examples in this page will receive, at most, 70 points. (60 if the solution of the first exercise uses auxiliary functions). Otherwise it will receive a score between 70 and 100 (or 60 and 90 if the solution of the first exercise uses auxiliary functions) depending on how many of the additional tests it passes.

Format of the solution

Please give an hard copy of the source code to the instructor by the due date. Furthermore, you should also email your code to cg428@cse.psu.edu by the due date, so to allow us to check that it runs correctly. Please write the code in a single file and send it as an attachment (not by "cut-and-paste") and use the name XXXX.sml, where XXXX are the last 4 digits of your student id, as the filename (example: if the last digits of your id are 1001, then the file should have name 1001.sml). Please write in the subject of the email your name and your student id.