CS451 F2002         Assignment 5          ML

Problem five is forty points, the rest are ten points each.

Put answers to "essay questions" in comments, so we can simply load
your source code.  Please try to use good ML style.  Hint: liberal use
of pattern matching will make your life easier.

Due (in the usual fashion) by 3pm Mon Dec 9.

1

    This Scheme function is impossible to write in ML.  Why?  Do a
    direct translation, and explain what the resulting compiler error
    means.

    (define ignore-n-curried
      (lambda (lis)
	(if (null? lis)
	    (lambda (x) x)
	    (lambda (x)
	       (ignore-n-curried (cdr lis))))))

2

    Define
      repeat: int -> ('a -> 'a) -> 'a -> 'a
    which works like this, eg
      repeat 4 (fn x => "foo"::x) ["aye", "bee", "sea"]
    evaluates to
      ["foo", "foo", "foo", "foo", "aye", "bee", "sea"]

3

    Use repeat to define myPow: real -> int -> real, which raises a
    real to the given (non-negative) power, eg
      myPow 2.0 8
    evaluates to
      256.0
    and butHead: int -> 'a list -> 'a list, which chops some elements
    off the front of a list, eg
      butHead 3 ["a","b","c","d","e","f","g","h"]
    evaluates to
      ["d","e","f","g","h"]

4

    Give equivalent recursive definitions of the same functions:
    myPowR, butHeadR


5

    SYMBOLIC DIFFERENTIATION

    This problem involves defining a new datatype to hold "simple
    arithmetic expressions involving X", and some functions to
    manipulate them.

    You will use

	datatype expr = Prod of expr * expr
			| Sum of expr * expr
			| Negative of expr
			| Expt of expr * int
			| Exp of expr
			| Ln of expr
			| Const of real
			| X

    Note that powers must be integers.  (Although the system does have
    the ability to do fancier stuff using a trick, eg you could get
    the square root of x^2+1 using
    Exp(Prod(Const 0.5, Ln(Sum(Expt(X, 2), Const 1.0)))) )

5a

    Define exprToStringP: expr -> string, which converts an expr to a
    printable representation in POSTFIX notation, with tokens
    separated by spaces, multiplication represented by "*", addition
    by "+", unary negation by "-", raising to a power by "^", log by
    "ln", the X expr by "x", and reals in the usual ML fashion.  Eg

	exprToStringP(Exp(Prod(Const 0.5, Ln(Sum(Expt(X, 2), Const 1.0)))))
	= "0.5 x 2 ^ 1.0 + ln * exp"

5b

    Define stringPToExpr, which takes a string in postfix notation
    with spaces as shown above, and converts it to an expr.  It should
    raise an exception if the postfix expression has a problem, eg
    for bad strings like "x x" or "1 2 + +" or "1 + 2" or "x1 2 +".

5c

    Define exprEval: expr -> real -> real, which evaluates an expr
    using the semantics you'd expect, with the given value plugged in
    for X.  Eg

	exprEval (Negative (Exp X)) 2.0 = ~7.38905609893065

5d

    Define exprDiff: expr -> expr, which takes the "symbolic
    derivative" of an expr using the usual rules of differentiation.
    (Extra credit if you have smarts in it to return something
    reasonably simplified, instead of with arithmetic on constants and
    such inside it.)

5e

    Define exprFun: expr -> (real -> real), which takes an expr and
    returns a function from reals to reals corresponding to the
    expression.  So eg
	exprFun (Prod (Const 2.0, Prod(X, X)))
    is effectively the same as
	fn r => 2.0*r*r

6

    Define sIntegrate: (real -> real) -> real -> real -> int -> real,
    which takes a numeric function, a range, and a grid count, and
    returns the area under the curve, approximated by evaluating the
    function at evenly spaced points along the range, with the number
    of points as given, and using Simpson's rule.

    Eg
      fun nearCube x:real = sIntegrate (fn t=>3.0*t*t) 0.0 x 200
    defines nearCube x to be "nearly" the cube of x, ie up to
    approximation error from the numeric integration.

7

    Use sIntegrate to numerically approximate pi by integrating
    2*sqrt(1-x*x) from -1 to 1.  How does the accuracy change as you
    modify the number of grid points?  Make a plot (handed in as a
    separate file (.ps or .pdf or a bitmap), given as an extra file
    argument to handin, OR on paper in my physical CS mail box.)  What
    would be the best (ie most accurate) number of grid points?