Assignment 1 (Introduction to SML)

Due Date: April 3, 2000 before class

Here is a grammar for the abstract syntax of some simple arithmetic expressions, specified as a collection of ML datatypes:

(* binary operations *)
datatype BOp = Plus | Minus | Multiply | Divide 

(* unary operations: 
  Inverse is the function that divides 1 by its argument, Inverse 2.0 = 0.5
  Ln is the natural logarithm on your calculator
*)
datatype UOp = Inverse | Square | SquareRoot | Sin | Cos | Tan | Ln 

(* expressions: 
  Pi is the constant 3.1415926...
*)
datatype Expression =
    Pi
  | Number of real
  | Binary of Expression * BOp * Expression
  | Unary of UOp * Expression

• Write representations in ML for the following expressions:
  • 6400
  • 2 * pi * 6400
  • pi * 6400 ^ 2

• Write an ML function interpret which takes an Expression and evaluates it to a real number. For example:

  - interpret(Binary(Number(3.0), Plus, Number(4.0)));
  val it = 7.0 : real
  

  To access the mathematical functions in ML, use Math.sin, Math.cos , etc.

• We are now going to extend the datatype declaration of Expression by adding the following two lines:

    | Define of string * Expression * Expression
    | Variable of string
  

  The intention is that a Define gives a name to a subexpression that can be reused later. For example,

  Define ("x", Number 3.0, Binary(Variable "x", Plus, Variable "x"))
  

  should evaluate to 6 . Extend your interpreter to handle the additional two cases.