CSE 341 - Spring 2002 - Assignment 7

CSE 341 - Spring 2002 - Assignment 7 - Scheme

Due June 3, at the beginning of class. Please submit all of your function definitions in one code file and your testing output in a separate file. Use comments to clearly indicate which problem number each section of code/output matches. In your tests, be sure and exercise the boundary cases as well as the normal ones. For example, try finding the mean of an empty list, and a list of one number, as well as a list of several numbers; or for duplicate, duplicate something 0 times as well as several.

The purpose of this assignment is to have you gain some experience with Scheme, in particular with Scheme's code/data equivalence. The first two questions are intentionally analogous to those on the Miranda warm-up, to give a comparison of the two languages.

Write and test a scheme function mean that finds the mean (average) of a list of numbers. Signal an error if mean is given an empty list as an argument.

Write and test a Scheme function duplicate that takes a number n and some other value x, and returns a list of n x's. For example:
```
(duplicate 3 "squid")  => ("squid" "squid" "squid")
(duplicate 0 #t)       => ()
```
Write and test a set of Scheme functions to do algebraic simplification of arithmetic expressions. You should perform the following simplifications. In the rules below x is an arbitrary expression. These rules are given in infix notation, but your Scheme functions should manipulate expressions using Scheme's expression syntax.
- Addition
  a + b => value of a + b if a and b are numbers
  0 + x => x
  x + 0 => x
- Multiplication
  a * b => value of a * b if a and b are numbers
  0 * x => 0
  x * 0 => 0
  1 * x => x
  x * 1 => x
Test your function on the following inputs, plus others if appropriate. The correct output is also shown here.
```
(simplify '(+ 2 3))  =>  5
(simplify '(+ 0 x))  =>  x
(simplify '(* x 0))  =>  0
(simplify '(* 5 6))  =>  30
(simplify '(* 1 (* x y)))  =>  (* x y)
(simplify '(+ x (* (+ 2 4) (* 3 3))))  =>  (+ x 54)
(simplify '(* 1 (+ (+ x 0) (* x 0))))  => x
```
You can also check that your simplifications are working correctly by giving the variables values and using eval on the original and simplified expressions. For example:
```
(define x 5)
(define y 10)
(eval '(* x (+ y 0)) user-initial-environment)  =>  50
(eval (simplify '(* x (+ y 0))) user-initial-environment)  =>  50
```
(Make sure you understand why this works.)
To help you get started, the Scheme functions that perform the simplifications for + are in the file ~borning/scheme/simplify.scm on the instructional UNIX hosts. You can copy this file to your own directory, try it on some problems just involving + to make sure it's working, and edit as needed.

Your program should be written in a purely functional style, with no side effects. (The starting file mentioned above is in this style.)