CSE 341 -- Assignment 1

January 9, 2002
Due in class January 16, 2002

Purpose: To become familiar with the Scheme programming environment; to experiment with elementary Scheme data types and operations; to practice writing your own Scheme functions (including recursive functions).

Experiment with the Scheme system a bit. Try the built-in functions that we have discussed in class and in the notes. You don't have to hand in anything for this question. See the Scheme help page for more info.
Draw a box-and-arrow diagram showing the result of evaluating the following Scheme expressions. (It's OK to check your answer by trying this on the computer, but you don't need to.)
1. (cons 3 (cons 30 ()))
2. (list 10 5 1)
3. (cons (cons 'x ()) (cons 'x ()))
4. (cons (+ 1 1) (cons (list 4 5) (list 5 6)))
Describe in your own words the difference between strongly and weakly typed and also statically typed and dynamically typed. Give an example of a Scheme function definition that has a type error in its body. When would the error be detected? (Try it.) When would the error be detected for an analogous function in C or Java? (Pick whichever language you know.)
Write and test a Scheme function trichotomy that takes two numbers and returns a symbol denoting the relationship between them (>, <, or =). Examples:
```
(trichotomy 3 6.0)     => <
(trichotomy 4.0 3.9)   => >
(trichotomy 1 1)       => =
```
Write and test a Scheme function midpoint that takes two lists that represent points as arguments and returns the list representing the midpoint. Your function should work on general n-ary points (eg. lists of length 4 represent 4-dimensional points). Example:
```
(midpoint '(0.0 0.0) '(10.0 8.0))         => (5.0 4.0)     ;; 2D points
(midpoint '(0.0 2.0 4.0) '(2.0 4.0 6.0))  => (1.0 3.0 5.0) ;; 3D points
(midpoint '(-1.0) '(3.0))                 => (1.0)         ;; 1D points
```

Write and test a Scheme function deep-reverse that "deeply" reverses a list. In other words, it reverses every element of the list (if that element is a list). For example:

;; reverse only reverses the "top" layer of the list:

(reverse '(1 (2 3) (4 5)))       => ((4 5) (2 3) 1)

;; deep reverse recursively reverses the whole list

(deep-reverse '(1 (2 3) (4 5)))  => ((5 4) (3 2) 1)
(deep-reverse '(1 (2 (3 4))))    => (((4 3) 2) 1)

;; here is how we would write reverse 
;; (called myreverse so we don't redefine reverse and make Scheme mad...)

(define (reverse-helper x result)
  (cond ((null? x) result)
	(#t (reverse-helper (cdr x) (cons (car x) result)))))

(defun myreverse (x)
  (reverse-helper x ()))

Hint: Make sure you understand how the above definition of myreverse works. When you understand this, think about making the COND expression a little more complicated. In particular, deep-reverse will have to do different things depending on whether the first element of the list it is reversing is an atom or a list (use the predicate list? to check for "listedness").

Suppose your Scheme implementation only has EQ? (not EQUAL?). Write and test a function my-equal? which relies only on EQ? to decide if two objects "look the same." (Your function needs not worry about numbers, pretend that the Scheme system only has symbols and lists.) To help you write your function, recall how EQUAL? works (as a first approximation):
1. Two atoms are EQUAL? iff they are EQ? (remember that the empty list is considered an atom).
2. Two lists are EQUAL? iff all of their elements are EQUAL?.
Write and test a Scheme function biggers which takes a pivot element and a list of numbers and returns the list consisting only of those numbers which are greater than the pivot. Write a Scheme function called smallers which takes a pivot element and a list of numbers and returns the list consisting only of those numbers which are less than or equal to the pivot. Both should return the empty list if the argument is empty. Both must be written recursively. Examples:
```
(biggers  10 '(3 245 6 14 245 56 4 10 7))   => (245 14 245 56)
(smallers 10 '(3 245 6 14 245 56 4 10 7))   => (3 6 4 10 7)
(biggers 10 ())                             => ()
```

Here is the pseudo-code for quicksort. Use biggers and smallers (above) to implement Quicksort in Scheme.

function quicksort (N : numlist) returns a numlist
  if N is empty
     return the empty list
  else
     pivot  <- the first element of N
     rest   <- all elements of N but the pivot
     big    <- biggers(pivot,rest)
     small  <- smallers(pivot,rest)
     result <- concatenation of quicksort(small), pivot, and quicksort(big)
     return result
  end if
end quicksort

Write two short questions you have about Scheme or any other topic in the class we've covered. We ask this to (1) get you to think a little deeply about the course/language and (2) help us learn what we're not getting across in lecture and section.

Deliverables: Please turn in the following:

Your written answers.
Hardcopy of your Scheme functions.

A script of you testing out your functions on the following sample data. (Hint: you should be able to cut and paste these calls from your browser, to avoid typing them in again.)

    (midpoint '(1 2) '(3 4))
    (trichotomy 3 3.14)
    (trichotomy 3 3.0)
    (trichotomy 10 2)
    (deep-reverse '(1 2 3 (4 5 6 (7 8 9))))
    (deep-reverse '((1 2) (3 4) 5 (6 7)))
    (deep-reverse '(1 2 3 4 ()))
    (my-equal? '(a b) ())
    (my-equal? '(a b c) '(a b c))
    (my-equal? '(a b c (d e f) g) '(a b c (d e f) g))
    (my-equal? '(a b c (d e f) g) '(a b c (d e e) g))
    (my-equal? 'a 'a)
    (quicksort '(10 9 8 7 6 5 4 3 2 1))
    (quicksort '(234 34 334 45 3 13 5 65 77 666))
    (quicksort '(235 54 45 23 1 2 3 4 5))

(If you use DrScheme, you can just do a "Print Interactions" to print out your interactions window...)

Hardcopies/scripts of any other cool things you did during this assignment.