**Author:** Dekai Wu

**Date:** Due 2008.05.16 at 23:00 by CASS

**Download:** http://www.cs.ust.hk/~dekai/151H/assignments/a6.tar.gz

**Assignment page:** http://www.cs.ust.hk/~dekai/151H/assignments/a6/html/

**Course page:** http://www.cs.ust.hk/~dekai/151H/

In this sixth piece of your programming project, you are assigned to maintain and extend the micro-Scheme language you've built in Assignments 1, 2, 3, and 4, specifically to provide a bigger micro-Scheme Standard Library of general-purpose library functions for users of your programming language.

Recall that your micro-Scheme interpreter has been Turing-equivalent since Assignment 4. We celebrated by beginning to implement the rest of your micro-Scheme programming language, using only micro-Scheme. We had successfully used C++ to bootstrap your implementation of the micro-Scheme programming language, so that the rest can be done in micro-Scheme itself.

Back in Assignment 4, we got you started by giving you implementations of the micro-Scheme Standard Library function `factorial`

and the binary versions of the `>`

, `<=`

, `>=`

, `=`

, and `abs`

operators. You yourself contributed your own implementation of another Standard Library function, `for-each`

. Purely for fun, some of you also wrote additional Standard Library functions, such as the general `map`

and `reduce`

functions and the `list`

function (which required you to have implemented the optional bonus support for a variable number of formal parameters for `lambda`

).

Now in Assignment 5, in your existing `library.scm`

file you will add implementations of a larger set of extremely useful Standard Library functions: `list-tail`

and `list-ref`

, `reverse`

, `equal?`

, `assoc`

, `partition`

, and `list-sort`

.

`list-tail`

and `list-ref`

Your `list-tail`

and `list-ref`

functions should take two operands, where the first operand must be a list, and the second operand must be an int.

`(list-tail`

*<list> <k>*`)`

(list-ref*<list> <k>*`)`

It is an error if <*list*> has fewer than <*k*> elements.

`list-tail`

should return the sublist of <*list*> obtained by omitting the first <*k*> elements.

`list-ref`

should return the kth element of list. (This is the same as the `car`

of `(list-tail`

*<list> <k>*`)`

.)

For example:

`> (list-tail '(a b c d e) 2)`

(c d e)

> (list-ref '(a b c d e) 2)

c

Notice that `list-ref`

basically gives us an indexing operator (like `operator[]`

in C++).

`reverse`

Your `reverse`

function should take one operand, where the operand must be a list. It should return a newly allocated list consisting of the elements of list in reverse order. Note that only the top-level list is to be reversed; as seen in the example below, any nested lists should remain unchanged.

`(reverse`

*<list>*`)`

For example, from the Scheme R5RS specification:

`> (reverse '(a b c))`

(c b a)

> (reverse '(a (b c) d (e (f))))

((e (f)) d (b c) a)

`equal?`

Recall that the `equal?`

predicate checks for equality by *value* and not by reference, and so must do a recursive item-by-item comparison whenever two lists are being compared. Your `equal?`

function should take two operands, where the operands may be of any type. It should return `1`

if both operands have equal element-wise values, and `0`

otherwise.

`(equal?`

*<obj1> <obj2>*`)`

For example:

`> (equal? 'a 'a)`

1

> (equal? '(a) '(a))

1

> (equal? '(a (b) c) '(a (b) c))

1

> (equal? '(a ((b c) d) e) '(a ((b c) d) e))

1

> (equal? 2 2)

1

> (equal? '(5 a b) (cons 5 '(a b)))

1

> (equal? (lambda (x) x) (lambda (y) y))

*unspecified*

You can also consult Scheme R5RS for details of `equal?`

.

`assoc`

The idea of an *alist* (for ``association list'') is fundamental to Scheme/LISP, and is the simplest possible implementation of a dictionary ADT built out of simple cons lists (c.f. `map`

in C++ STL). An alist must be a list of cons pairs, for instance:

`> (define e '((a 1) (b 2) (c 3)))`

The Standard Library procedure `assoc`

has the following form:

`(assoc`

*<obj> <alist>*`)`

It finds the first pair in <*alist*> whose car field is <*obj*>, and returns that pair. If no pair in <*alist*> has <*obj*> as its `car`

, then `0`

(not the empty list) is returned.

Note that `assoc`

is required to use `equal?`

to compare <*obj*> with the items in <*alist*>.

For example:

`> (assoc 'a e)`

(a 1)

> (assoc 'b e)

(b 2)

> (assoc 'd e)

0

`> (assoc (list 'a) '(((a)) ((b)) ((c))))`

((a))

> (assoc 5 '((2 3) (5 7) (11 13)))

(5 7)

`list-partition`

Your `list-partition`

function should take two operands, where the first operand must be a procedure, and the second operand must be a list:

`(list-partition`

*<proc> <list>*`)`

The <*proc*> must be a predicate that accepts one argument and return a single value (which is either zero or non-zero, interpreted as a boolean). It should not have any side effects on the <*list*>.

The `list-partition`

function applies <*proc*> to each element of <*list*>, and returns a list containing two values: the first one a list of the elements of list for which <*proc*> returned a true value (i.e., not `0`

), and the second a list of the elements of list for which <*proc*> returned `0`

. The elements of the two result lists must be in the same order as they appear in the input list.

For example, assuming you've implemented an `even?`

predicate:

`> (partition even? ’(3 1 4 1 5 9 2 6))`

((4 2 6) (3 1 1 5 9))

`list-sort`

Your `list-sort`

function should take two operands, where the first operand must be a procedure, and the second operand must be a list:

`(list-sort`

*<proc> <list>*`)`

The <*proc*> must be a function that accepts any two elements of <*list*>, and should not have any side effects on the <*list*>. It should return a true value (i.e., not `0`

) when its first argument is strictly less than its second, and `0`

otherwise.

The `list-sort`

function performs a sort of <*list*> in ascending order according to <*proc*>, without changing <*list*> in any way. The `list-sort`

procedure returns a list.

You are required to use the Quicksort algorithm in your implementation of `list-sort`

. Therefore the sorting algorithm performs an expected O(*n* lg *n*) calls to <*proc*> where *n* is the length of list. Your implementation must guarantee that all arguments passed to <*proc*> are elements of the list being sorted, but the pairing of arguments and the sequencing of calls to <*proc*> are not specified and is up to you.

For example:

`> (list-sort < ’(3 5 2 1))`

(1 2 3 5)

Hint: take advantage of your `list-partition`

function...

A bonus will be awarded for the first three assignments submitted that are 100% correct. :-)

You must follow the design approach outlined in this document. Do *not* just implement the required functionality using a different design.

Remember to add **all** your Scheme library functions to the `library.scm`

file where you should already have the libary functions `>`

, `<=`

, `>=`

, `=`

, `abs`

, `factorial`

and `for-each`

. Make sure your improved version of `library.scm`

is included in your tarball submission.

Again, please feel free to implement any other general-purpose library functions you would like, just for fun. Some suggestions, in case you did not do them yet in Assignment 4: the general `map`

and `reduce`

functions and the `list`

function. Remember that these require you to have implemented the optional bonus support for a variable number of formal parameters for `lambda`

.

For this exercise we are providing you with no new files. Please build on top of your tarball from the previous assignment(s). Unless you are improving or debugging your previous implementation, the only difference from your Assignment 4 tarball will be that your `library.scm`

has been expanded.

Remember we are still focusing on proper use of encapsulation. So you still should *not* edit the files `c_cons.h`

, `c_cons.cpp`

, `cons.hpp`

, or `eval.hpp`

. Again, the programming assignments are mini-exercises in how multiple programmers are supposed to interact and communicate in the real world; these files are *owned* and *maintained* by the other author(s).

Depending on your approach, you may or may not need to change the `Makefile`

. Whether you changed it or not, always make sure you include whatever `Makefile`

is needed to build your program, when you submit assignment. Otherwise, the graders cannot build your program.

You must write the final version of the program on your own. Sophisticated plagiarism detection systems are in operation, and they are pretty good at catching copying! If you worked in study groups, you must also acknowledge your collaborators in the write-up for each problem, whether or not they are classmates. Other cases will be dealt with as plagiarism. Re-read the policy on the course home page, and note the University's tougher policy this year regarding cheating.

**Your programming style (how clearly and how well you speak C++, yacc/bison, lex/flex, and Scheme) is what will be graded. Correct functioning of your program is necessary but not sufficient!**

Generated on Wed May 7 09:26:26 2008 for a1 by 1.5.3