In the Summer of 1958, John McCarthy (recipient of the Turing Award in 1971) made a major contribution to the field of programming languages. With the objective of writing a program that performed symbolic differentiation of algebraic expressions in a effective way, he noticed that some features that would have helped him to accomplish this task were absent in the programming languages of that time. This led him to the invention of LISP (published in Communications of the ACM in 1960) and other ideas, such as list processing (the name Lisp derives from "List Processing"), recursion and garbage collection, which are essential to modern programming languages, including Java. Nowadays, symbolic differentiation of algebraic expressions is a task that can be conveniently accomplished on modern mathematical packages, such as Mathematica and Maple.
In this assignment, you will be given the opportunity to write your own language for symbolic differentiation using SML. Through this practice you will exercise important features of this functional language, such as recursion, pattern matching, datatypes, list processing, etc., not to mention the ability to design your own mini-language.
As in the previous assignment, all of your programs must compile. Programs that do not compile will receive an automatic zero. Make sure that the functions you are asked to write have the correct names and the number and type of arguments specified in the assignment. Finally, please pay attention to style and follow the style guidelines posted on the course web site. Think carefully before writing the code, and try to come up with simpler, elegant solutions.
The objective of this assignment is to build a language that provides the derivative of algebraic expressions. Symbolic expressions consist of numbers, variables, and mathematical functions (plus, minus, times, sin, cos, etc). To get you started, we have provided the datatype that defines the abstract syntax for such expressions:
[ Download file: expressions.sml ] Instructions: Change to the directory where you saved the "expressions.sml" file. In the SML environment type:
use "expressions.sml"; open Expressions;
to start using the datatype.
(* abstract syntax tree *) datatype expr = Const of real | Var of string | Plus of expr * expr | Minus of expr * expr | Times of expr * expr | Div of expr * expr | Sin of expr | Cos of expr | Ln of expr | Pow of expr*int | Exp of expr
Expression Ln(e) represents the natural
logarithm of e, Pow(e, n) represents the n-th power of e
(where n is an integer, possibly negative), and Exp(e) is the
exponential function. The other expressions have the usual meaning implied by
their names. Mathematical expressions can be constructed using the
constructors in the above datatype definition. For example, the expression
"x^2 + sin(e^y)" can be
represented as:
Plus(Pow(Var "x", 2), Sin(Exp(Var "y")))
Essentially, this represents a tree where nodes are the datatype constructors
(Plus, Sin, etc), and the children of each node are the arguments of that
constructor. Such a tree is called an abstract syntax tree (or AST for short). For
your convenience, we have provided a function "toString" that prints
expression in a more readable form, using infix notation:
toString(Plus(Pow(Var "x", 2), Sin(Exp(Var "y")))) = "x^2 + sin (exp (y))"
Note. An important consideration when designing a
new language is the specification of operator precedence. For example, the
meaning of expression 3+2*9 depends on which operator evaluates first: the
result 21 if the multiplication evaluates first, and 45 otherwise. Such
ambiguities usually occur when writing expression using infix operators; in such
cases, parentheses can be used for
disambiguation. However, expr datatype expressions use prefix
notation and are unambiguous. For instance, representing 3+2*9 as Plus(Const
3.0, Times(Const 2.0, Const 9.0)) indicates that the multiplication
evaluates first, and the sum evaluates next.
First, we want to be able to evaluate expression for
specific values of the variables. For
example, the expression "x^2 + 3.0*y +1.0" can be evaluated once we
know the
values of x and y. Suppose x=5.0 and y=2.0. Then the result of the
evaluation is 5.0^2 + 3.0*2.0 + 1.0 = 32.0.
The values of variables can be described, in general, using a map data structure that binds variables to their values. This mapping is also called an environment. For the sake of simplicity, we will use an association list to represent the variable environment. An association is a pair of a variable name and its value:
type association = string * real
An
example of an association list that provides values for variables x and y is:
[("x", 5.0), ("y", 2.0)]
lookup that looks up the value of a
variable in an association list. The function must raise a Fail exception if
the variable is not defined in the association listfun lookup(x: string, a: association list): real
eval that takes an expression "e" and an association
list "a", representing values of variables, and evaluates
"e" to a real number. The signature of this function is:fun eval (e:expr, a: association list): real
Next, we want to develop a
function that takes an expression
"e1" and a variable "v" as its arguments and returns an expression
"e2" representing the partial derivative of the expression with
respect to "v". This process is referred to as symbolic differentiation. The prototype of this function is given
bellow:
fun derivative(e: expr, v: string): expr
When implementing this function, recall the chain rule from your freshman Calculus course:
(f(g(x)))' = f'(g(x)) * g'(x)
Also recall the derivatives for the other functions in our language:
The derivative of each constant is 0. The derivative of variable y with respect to variable x is 1 if x = y and 0 otherwise.(f(x) + g(x))' = f'(x) + g'(x)
(f(x) - g(x))' = f'(x) - g'(x)
(f(x) * g(x))' = f'(x) * g(x) + g'(x) * f(x)
(f(x) / g(x))' = (f(x) * g(x)^(-1))'
(sin(x))' = cos(x)
(cos(x))' = -sin(x)
(x^n)' = n * (x^(n-1))
(ln(x))' = 1/x
(exp(x))' = exp(x)
Your task is to implement the derivative function. The result of
your function must be correct, but need not be expressed in the simplest form.
The result of this function will be "cleaned up" in the simplification
process discussed next.
Take advantage of this in order to keep the code in this part as short as possible.
Consider the application of the derivative function with
respect to variable "x" to the expression "x^2+y" and the corresponding output:
derivative(Plus(Pow(Var "x", 2), Var "y"), "x") =
Plus(Times(Const 2.0, Pow(Var "x", 1)), Const 0.0)
The output is equivalent to "2*x^1 + 0". However, the
expression can be simplified to "2*x". This is due to the following
simplification rules:
Thus, in this part of the assignment, you
are required to provide a function to simplify expressions in such cases.
We have presented just two cases in which an expression could
be simplified. Your job is to find and implement other cases where the
simplification function could reduce an expression. You should come up with at
least four more simplification rules. Implement a function simplify:
expr -> expr that performs these simplification rules. Write all the
simplification rules that you have implemented in a comment before the function.
Try the simplification function on the output of derivative, for different input
expressions, and check if the result is in the form that you expect.
Imagine that your were in a IT fair demonstrating your new
product to customers, and, during your presentation, you tell your prospective
customers that in order to write the expression "x*y+2.0" using your product
they should write:
Plus(Times(Var "x", Var "y"), Const 2.0)
Likely, they would leave your presentation before you
finish typing! Thus, you want to provide them with the ability to write
expressions in a more concise form. Since infix notation is ambiguous (as
discussed above), you will use a prefix (Polish) notation instead. For
instance, the above expression would be represented as: "+ * x y
2.0".
fun tokenize(s:string): string list
For instance, tokenize("+ * x y 2.0")
= ["+", "*", "x", "y",
"2.0"]
Write a function that parses expressions , i.e.,
transforms a list of tokens into the expr construct that represents the
expression's AST. If the list of tokens does not correspond to a valid
expression, you must raise a Fail exception.
fun parse(s: string list): expr
For example:
parse ["+", "*",
"x", "y", "2.0"] = Plus(Times(Var
"x", Var "y"), Const 2.0)
parse ["+", "*",
"x", "-", "2.0"] raises Fail
Hint: the parsing process can be performed by constructing the AST in a bottom-up fashion, using a stack data structure to maintain the currently constructed expressions.
Turn in the code for Parts 1-4 in the file expressions.sml.
Consider the following function:
fun foo (n: int) : int = if n > 100 then n - 10 else foo(foo(n + 11))
Use the substitution model discussed in class to show how the expression
foo(99) evaluates to its final value. Make sure you show each
step in the evaluation.
To do: turn in you solution in a file written.txt.