Assignment 6 for CSE 341 (Winter 2012)

Assignment 6: Schemin' Scheme.

CSE 341: Programming Languages
The University of Washington, Seattle, Winter 2012

Purposes: The purposes of this assignment are (a) to gain experience with the Scheme language and (b) to use Scheme to explore issues in programming language interpretation.

Due: Thursday, February 23 at 11:00 PM via Catalyst CollectIt. (changed from Feb. 21). The target date, however, is Feb. 21.

Individual Work.
Do this assignment individually. DO NOT COLLABORATE on this assignment. This is not a partnership or teamwork assignment.

What to Turn In: You should turn in the following files:

scheme-warmup.ss
latest-schemes.ss

Your files should begin with comment lines that give the name of the file, a program name (that is more descriptive and English-like than the filename), the author's (your) name, and a brief description (2-5 lines) of what the program does.

The file scheme-warmup.ss should contain your solutions to Problems 1-5. The file latest-schemes.ss should include the code that you write for Problem 6, which should consist of global function definitions for the following:

my-list-of-values
eval-or
eval-and
let->combination

It should also include the my-eval function from the given source but with the new clauses necessary to incorporate eval-or, eval-and, my-list-of-values, and let->combination into the evaluator. Finally, it should include comments showing why eval-or and eval-and are derived expressions by showing equivalency relations with the pre-existing language (without both eval-and and eval-or). The file should NOT contain any of the many other functions (such as my-apply) defined in mceval.ss.

Read chapters 1 and 2 of Sketchy Scheme. Also, read chapter 4 of Structure and Interpretation of Computer Programs.

(10 points) Define a function (euclidean-dist x1 y1 x2 y2) that returns the Euclidean distance between points (x1, y1) and (x2, y2).
(10 points) Define a recursive function (increment-numbers lst) that takes a list of elements as input and returns a copy of the list in which any (top-level) element that is a number is one greater than its original value. For example:
```
(increment-numbers '(one day we saw 2 bears and 3 horses))
 ; --> (one day we saw 3 bears and 4 horses)
```
(10 points) A binary tree whose internal nodes are unlabeled can be represented in Lisp (including Scheme) as a structure composed of dotted pairs. For example, a three-node binary tree whose left leaf has label a and whose right subtree has label b can be created with the form (cons 'a 'b), which has the result external form (a . b). A larger example is ((a . b) . (c . d)). Define a function (twist binary-tree) that reverses the entire tree by exchanging the car and cdr parts of every dotted pair in binary-tree. For example:
```
(define mytree '((a . b) . (c . d)))
(twist mytree)
 ; --> ((d . c) . (b . a))
```
(10 points) Using apply and max, define a function (chebyshev-distance v1 v2) that computes the L-infinity metric between two mathematical vectors. This distance is defined as the maximum of the absolute values of the differences between corresponding elements. For example:
```
(chebyshev-distance '(17 4 88) '(19 7 81)) ; --> 7
```
(10 points)Define a function (infix-eval expr) that will accept fully-parenthesized arithmetic expressions having infix ordering and evaluate them properly. The allowed operators are + and * and they will always take two arguments. For example:
```
(infix-eval '((1 + 2) * ((3 + 4) * (5 + 6)))) ; --> 231
```
(50 points) Starting from this CSE 341 variation of the metacircular evaluator given in Chapter 4 of Structure and Interpretation of Computer Programs, create a new version that incorporates the features described in Exercises 4.1 (but make the order of evaluation Right-to-Left), 4.4, and 4.6.

Last updated 17 February at 10:00 PM (changed due date); previously updated Feb. 13, Feb. 8.