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)
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!
1.5.3