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:
schemewarmup.ss
latestschemes.ss
Your files should begin with
comment lines that give the
name of the file, a program name (that is more descriptive and Englishlike
than the filename), the author's (your) name,
and a brief description (25 lines) of what the program does.
The file schemewarmup.ss should contain your solutions to
Problems 15. The file latestschemes.ss should include the
code that you write for Problem 6, which should consist of
global function definitions for the following:
mylistofvalues
evalor
evaland
let>combination
It should also include the myeval function from the given source
but with the new clauses necessary to incorporate
evalor, evaland,
mylistofvalues, and let>combination into the evaluator.
Finally, it
should include comments showing why evalor and evaland are derived expressions by
showing equivalency relations with the preexisting language (without both
evaland and evalor). The file should NOT contain any of the many other
functions (such as myapply) 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 (euclideandist x1 y1 x2 y2)
that returns the Euclidean distance between points (x1, y1) and
(x2, y2).
 (10 points)
Define a recursive function (incrementnumbers lst)
that takes a list of elements as input and returns a copy of
the list in which any (toplevel) element that is a number
is one greater than its original value. For example:
(incrementnumbers '(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 threenode 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 binarytree) that reverses
the entire tree by exchanging the car and cdr parts of every
dotted pair in binarytree. For example:
(define mytree '((a . b) . (c . d)))
(twist mytree)
; > ((d . c) . (b . a))
 (10 points)
Using apply and max, define a function
(chebyshevdistance v1 v2) that computes the Linfinity
metric between two mathematical vectors. This distance is
defined as the maximum of the absolute values of the
differences between corresponding elements. For example:
(chebyshevdistance '(17 4 88) '(19 7 81)) ; > 7
 (10 points)Define a function (infixeval expr) that will
accept fullyparenthesized arithmetic expressions
having infix ordering and evaluate them properly.
The allowed operators are + and * and they will always
take two arguments. For example:
(infixeval '((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 RighttoLeft),
4.4, and 4.6.

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