CptS 355 - Assignment 2

Assignment 2 - Scheme
CptS 355 - Programming Language Design
Washington State University


Home
Calendar
Syllabus
Resources
People
Project turn-in

Overview

Weight: This assignment will count approximately 9% of your final grade.
Due Date: Monday, Feb 20, 2004, 11:59:59 PM

Fun with Lists

This assignment provides experience in Scheme programming. You can download Scheme from http://www.gnu.org/software/mit-scheme. Scheme can be installed on most operating systems (eg,. Linux, Unix, Windows). The Windows installation package is 21MB. The software is also installed in the Sloan 353 labs.

Turning in your work

All code should be developed in the file called assign2.scm. The problem solution will consist of a sequence of function definitions. When you are done and certain that everything is working correctly, turn in the file using the turn-in page. Upload a file named assign2.scm. You may turn in your assignment as many times as you like. Everything you turn in is saved - but I will look at only the last turn-in before the deadline. Code you write to test your functions should be placed in a separate file. When you turn in assign2.scm it should contain only the required function definitions.

Grading

The assignment will be marked for good programming style (indentation and appropriate comments), as well as clean compilation and correct execution.

General rules

Unless directed otherwise, you must implement your functions using recursive definitions built up from the basic built-in functions such as CONS, CAR, CDR. (i.e., when I ask you to implement append you may not use the built-in append function, nor use the built-in sort functions for the sorting assignment, etc.). You may use the built-in function equal? to test equality of lists.

The only thing that you may define in this assignment is functions. You may not use set!. You may use let, let*, or letrec.

append - 10%

Write a function to append two lists

>  (append '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)
>  (append () '(4 5))
(4 5)
>  (append '(a b) ())
(a b)
>  (append '(1 (2 3)) '(4 5))
(1 (2 3) 4 5)

intersection0 - 5%

This function should return the intersection of two lists

>  (intersection0 '(1) '(1))    
(1)
>  (intersection0 '(1 2) '(1))  
(1)
>  (intersection0 '(2 1 2) '((1) 2)) 
(2 2) or (2)

If an element appears in one input list or the other more than once it is ok if it appears in the output multiple times (but it need not)

intersection1 - 10%

This function should return the intersection of two lists

>  (intersection1 '(1) '(1))    
(1)
>  (intersection1 '(1 2) '(1))  
(1)
>  (intersection1 '(2 1 2) '((1) 2)) 
(2)

In this version each value should appear in the output list only once.

zip - 10%

This function of two lists pairs up corresponding elements of the two lists. If one list is longer than the other, extra elements of the longer list are ignored.

>  (zip '(1 2 3) '(a b c))    
((1 a) (2 b) (3 c))
>  (zip '(1 2) '(a))  
((1 a))

in? - 10%

This function should return true if the first argument is a member of the second argument or any of its sublists.

> (in? 1 ())
#f
> (in? 1 '(1))
#t
> (in? '(1) '(1))
#f
> (in? '(1) '((1)))
#t
> (in? 1 '((1 2) 3))
#t

You may use the built-in equal? function as part of your implementation of in?.

flatten - 10%

This function should return a list consisting of all the primitive elements (numbers, atoms, etc.) of a list and its sublists.

> (flatten ())
()
> (flatten '(1))
(1)
> (flatten '((1 2) 3)
(1 2 3)

filter - 15%

This function takes as its first argument one-argument function, called a predicate, which returns #t or #f, and as its second argument a list. It returns a list of all elements in the second argument that satisfy that predicate. The elements must appear in the result in the same order that they appear in the original list.

> (filter (lambda (x) (= x 1)) '(1 2))
(1) 
> (filter (lambda (x) (< x 3)) '(1 2))
(1 2)

For this problem (only) your implementation is required to be tail recursive, so you will need to define an auxiliary function that takes a parameter in which the result is accumulated. filter will simply call the auxiliary function with () as the initial result. The auxiliary function will be tail recursive. You may use the built-in reverse function in implementing filter.

We will discuss tail recursion, auxiliary functions, and accumulating parameters in class.

quicksort - 20%

This function takes as its first argument a two-argument function called a comparator and as its second argument a list. For any pair the comparator returns #t or #f. quicksort returns a list consisting of the members of its second argument, ordered so that the comparator returns true on adjacent members.

> (quicksort (lambda (x y) (<= x y)) '(1))
(1)
> (quicksort (lambda (x y) (<= x y)) '(3 2 1 2))
(1 2 2 3)
> (quicksort (lambda (x y) (>= x y)) '(3 2 1 2))
(3 2 2 1)

Recall the quicksort algorithm: partition the input into 2 pieces by picking a value and comparing all the remaining elements of the input to that value; put the elements for which the comparator returns #t in one partition, those where it returns #f in the other. Recursively quicksort the two partitions obtaining two sorted lists. Append the two lists with the initial element between them to get the final answer. Do not use any of the built-in sort functions. You will need to define an auxiliary partition function.

reduce - 10%

This problem appears in Scheme and the Art of Programming by George Springer and Daniel Friedman. Define a function, reduce, that has two parameters, proc and aList. The parameter proc is a function. The parameter aList is a list. reduce "reduces" the list aList replacing pairs of values chosen from the list with the value produced by applying proc until there is only one value left in the list. reduce returns this value. Here is how the successive stages in the reduction might look when proc is + and aList is (3 7 -2 5).

    (3 7 -2 5) --> (10 -2 5) --> (8 5) --> 13

Here are some example calls to reduce.

> (reduce + (list 1 3 5 7 9)) 
25
> (reduce max (list 2 3 -5 7 -9)) 
7

Hints on working with Scheme

The following are a few tips to help you get started on working with Scheme on the Windows machines in the Sloan 353 lab.

Finding scheme in Windows

Click Start, point to All Programs, point to MIT Scheme, and then click 'Scheme'.

Invoking scheme on a file

In order to load files in scheme you have to use the procedure 'load'.
The procedure load has the following syntax
(load filename)
Here filename can be a string specifying a single file or a list of strings specifying multiple files.
For example in order to load a file named "example.scm" (.scm is the extension for scheme source files) you would type (load "example.scm") at the prompt.
If the file is not located in the current working directory you should specify the full path-name for the file. For example in windows for loading a file present in the users directory in the C drive you would type (load "c:\\users\\example.scm") at the prompt.

What to do when an error occurs in Scheme

Control Key Combinations (Interrupt Keys)
Scheme also has some control key combinations (interrupt keys) which will do the various restarts with a lot less retyping for you. These are C-g (Ctrl-g -> press and hold down control key and press the key 'g' on the keyboard), C-b, C-x and C-u. The C-g key will halt any running scheme evaluation and will return you to the top-level REPL (short for typing (restart 1) at the error prompt). You can also press the control key combination C-c (C-c displays all the interrupt choices) which prompts for another character (either C-g, C-x, C-b, C-u) and performs the corresponding action. Short definitions for some of the interrupt keys are listed below.
- C-g (or C-c C-g)
- C-x (or C-c C-x)
- C-u (or C-c C-u)