Index of /courseware/cse3322/2005/A2

 Name                    Last modified       Size  Description

 Parent Directory        11-Oct-2006 10:29      -  

CSE3322, 2005, SML Assignment 2, due 6pm Friday 26 August

The online copy is the reference document. Check it regularly -- Thursday, 22-Jun-2006 18:55:48 EST.

The (concrete-) syntax of expressions (see cse2303, cse2304) is

<exp> ::= <exp> <plusOrM> <term> | <term> | - <term>   -- i.e. a list of <term> separated by +/-

<term> ::= <term> * <factor> | <factor>   -- i.e. a list of <factor> separated by *

<factor> ::= <factor> ** <intConstant> | <factor> ** - <intConstant> | <operand>   -- ** is exponentiation

<operand> ::= <intConstant> | <identifier> | ( <exp> )

<plusOrM> ::= + | -

<intConstant> ::= non-negative int constants, e.g. 0, 3, or 42, etc.

<identifier> ::= the usual alpha-numeric identifier strings

Note that '**' binds more tightly (has higher precedence) than '*' which binds more tightly than '+' and '-'.  Also note that, although '/' is not included above, 'a/b' is equivalent to 'a*b**-1'.

 

The rules of differentiation are:

dn/dx = 0

dy/dx = 1, if x=y, and =0 if x<>y,

d(a**n)/dx = n*a**(n-1)*da/dx, and a special case, when a=x, is...

d(x**n)/dx = n*x**(n-1)     (even if n<0),

in fact the '**' rule can be derived from the '*' rule,

d(a+b)/dx = da/dx + db/dx,

d(a-b)/dx = da/dx - db/dx,

d(a*b)/dx = a*db/dx + b*da/dx,

d(-a)/dx = - da/dx

for arbitrary constant 'n', identifiers 'x' and 'y', expressions 'a' and 'b'.

E.g..

d (x**2+y*x+3) / dx = 2*x**1 + y*1 + 0*x + 0 which can be simplified to

= 2*x+y

If f is a function of x then df/dx gives the slope, the rate of change, of f as a function of x.

Assignment 2

1. Define a suitable SML data type, exp, to hold (parse-trees, abstract-syntax of) expressions. Also write a function show : exp->string.
2. Write a differentiator, diff : exp->identifier->exp.
3. Write a simplifier, simplify : exp->exp, for the results of differentiation. Given a polynomial expressed as an exp, it should at least be able to simplify the polynomial's derivative. (Simplifying arbitrary expressions (v. polynomials) is hard, in fact it is not even well defined, so it does not have to be able to do that.)

Include three to six examples in your submitted file which clearly demonstrate the full range of behaviour of your functions when we run sml and  'use "a2.sml";'.

• Clayton students use submit (?/cs/cc/bin/submit?) to submit your solution from 22 Aug. on, up to the deadline. Assessment is 'a2', file name is 'a2.sml'. (A late assessment 'a2late' will open on the next day for one week after a1. If you submit on-time we will mark that, not any late submission. Read the [home page] for late penalties etc..)
• NB. You do not have to write a parser : string->exp, unless you want to.

Marking

exp and diff count for approximately half of the marks and simplify for the remainder. We are looking for how well you have used the functional programming paradigm, as well as how well your solution performs. (It is often, but not always, the case in FP that "small is good".)

Misc.

In [.../Prolog.toy/Examples/Diff/] are some notes on differentiation in Prolog -- the logic programming paradigm.

Also see [.../cse3322/2005/Code/].