Carleton University
School of Computer Science
95.501  Assignment 1 (Fall '2001)

Due: Oct 2, 4:00 p.m.

The objectives of this assignment are to familiarize you with Scheme, to build abstractions with procedures, to use recursion,  to explore patterns of computational processes, and to become familiar with scheme’s and your own data abstractions by structuring procedures that operate on “abstract data.”. You should follow the programming style and guidelines set forth in class. In particular, use meaningful names for variables and procedures, use recursion wherever possible and write concise readable procedures. For each problem, turn in a listing of your procedures, when applicable, and a demonstration showing the problem has been solved. It is up to you to make up a convincing test plan.


1) Suppose that you evaluate the following:

    (define what 44)
    (define (add  a b ) ( + b a))
    (define my-procedure (lambda (x y) (add x what)))
    (my-procedure 2 (+ 3 4))

Using the substitution model and starting at the last line, show the sequence of evaluations performed  using applicative-order evaluation and then normal-order evaluation.

2) Define a procedure that takes three numbers as arguments and returns the sum of the squares of the numbers that are duplicated. For example,

(sum-square-duplicates 1 2 4 ) => 0
(sum-square-duplicates 1 1 4 ) => 2
(sum-square-duplicates 1 1 1 ) => 3
(sum-square-duplicates 1 3 3 ) => 18
(sum-square-duplicates 5 2 2 ) => 8


3) Write a procedure that returns all but the n'th word of a string, assuming the words are separated by spaces. Thus, (word-remove 2 "The big dog ate my lunch") ==> "The big ate my lunch". Is the process your procedure creates iterative or recursive? Create the procedure again so that it creates the other type of process.

DO NOT use built-in ref functions like list-ref or string-ref.


4) A function f is defined by the rule that f(n) = 1 if n < 3, f(n) = n if n is a prime number, and f(n) = f(n-1) + 2f(n-2) + 3f(n-3)  if n >= 3 and not prime. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

5) Define a procedure double that takes a procedure of one argument as an argument and returns a procedure that applies the original procedure twice. For example, if increment is a procedure that adds 1 to its argument, then (double increment) should return a procedure that adds 2. What is returned by the following and why?

(((double (double double)) increment) 4)

 6) Consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation add-1 as the following:

(define zero (lambda (f) (lambda(x) x)))

(define (add-1 n)
    (lambda (f) (lambda(x) (f ((n f ) x )))))

This representation is know as Church numerals after its inventor Alonzo Church the logician who invented Lamda Calculus.

Define one and two directly (not in terms of zero and add-1) (Hint: Use substitution to evaluate (add-1 zero)


7) Here is an alternative procedure representation of pairs.

     (define (special-cons x y)
          (lambda (m) (m x y)))
 

What are the corresponding definitions of car and cdr? Use news names for the procedures so as to not conflict with the existing ones. For this representation, verify that (special-car (special-cons x y)  yields x for any objects x and y and (special-cdr (special-cons x y)) yields y.


8) Write the definition of the Scheme predicate equal? that tests whether two expressions are the same. If neither of the expressions is a pair it uses eqv? to test their equality. Otherwise it recursivley tests the car and cdr of the expressions until it can use eqv? For example,

    (my-equal? '(a (b c (d e ) f)) '(a (b c (d e ) f))) => #t
    (my-equal? '(a (( b d ) c) e) '( a (b d) c e)) => #f
    (my-equal? '( a (( b d ) c ) e ) '( a (( d b ) c) e)) => #f

Do not use Scheme's built-in procedure equal? in your procedure.


9) The procedure +, * and list take arbitrary numbers of arguments. One way to define such a procedure is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter's value will be a list of any remaining arguments. For instance, give the definition:
 

     (define (f x y . z)  ?body> )

     the procedure f can be called with two or more arguments. If we evaluate

     (f 1 2 3 4 5 6)

     then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6).

     Given the definition:

     (define (g . w) ?body>)

     the procedure g can be called with 1 or more arguments. If we evaluate

     (g 1 2 3 4 5 6)

     then in the body of g, w will be the list ( 1 2 3 4 5 6).

     Use this notation to write a procedure unique-count that takes one or more integers and returns a list unqiue (no duplicates) integer in the list. For
     example:

      (unique-count 1 2 3 1 2 1) => ( 3 )
      (unique-count  1 1 1 1 2 2 4 2 3 3 3 1 2 3 6 ) => ( 4 6)

Testing:

Be sure to test your procedures thoroughly and make sure to pick meaningful test cases.  It is up to you to make up a convincing test plan (i.e. convince the TAs that your procedures work properly).   Make sure you test all your procedures.

Submission:

Submit a printout of all of your procedures and along with a copy of the output generated from the testing.   Be sure to include comments where appropriate in your code and make sure that all output is clearly explained.  Testing will be marked!   It is always a good idea to highlight the beginning of the procedure on the printout.  Place your name, student #, course#, and assignment # on the top of each page.   Put all printouts in one unsealed envelope, with this same information clearly marked on the envelope. You should also include a diskette containing the procedures and test output files you generated for the assignment. All of these files should be stored in the directory A:\ASS1 (actually B:\ASS1 when in the labs here).  Finally, hand in your assignment in class. Don't forget that the assignment will be marked for style, testing and your solutions.