microScheme

Author: Dekai Wu
Date: Due in lab by CASS
Download: http://www.cs.ust.hk/~dekai/2012H/assignments/a7.tar.gz
Assignment page: http://www.cs.ust.hk/~dekai/2012H/assignments/a7/html/
Course page: http://www.cs.ust.hk/~dekai/2012H/
In this piece of your programming project, you are assigned to maintain and extend the microScheme language you've built in Assignments 1, 2, 3, and 4, specifically to provide a bigger microScheme Standard Library of generalpurpose library functions for users of your programming language.
Recall that your microScheme interpreter has been Turingequivalent since Assignment 4. We celebrated by beginning to implement the rest of your microScheme programming language, using only microScheme. We had successfully used C++ to bootstrap your implementation of the microScheme programming language, so that the rest can be done in microScheme itself.
Back in Assignment 4, we got you started by giving you implementations of the microScheme Standard Library function factorial
and the binary versions of the >
, <=
, >=
, =
, and abs
operators. You yourself contributed your own implementation of another Standard Library function, foreach
. 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 your existing library.scm
file you will add implementations of a larger set of extremely useful Standard Library functions: listtail
and listref
, reverse
, equal?
, assoc
, partition
, and listsort
.
listtail
and listref
Your listtail
and listref
functions should take two operands, where the first operand must be a list, and the second operand must be an int.
(listtail
<list> <k>)
<list> <k>
(listref)
It is an error if <list> has fewer than <k> elements.
listtail
should return the sublist of <list> obtained by omitting the first <k> elements.
listref
should return the kth element of list. (This is the same as the car
of (listtail
<list> <k>)
.)
For example:
> (listtail '(a b c d e) 2)
(c d e)
> (listref '(a b c d e) 2)
c
Notice that listref
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 toplevel 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 itembyitem 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 elementwise 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)
listpartition
Your listpartition
function should take two operands, where the first operand must be a procedure, and the second operand must be a list:
(listpartition
<proc> <list>)
The <proc> must be a predicate that accepts one argument and return a single value (which is either zero or nonzero, interpreted as a boolean). It should not have any side effects on the <list>.
The listpartition
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:
> (listpartition even? ’(3 1 4 1 5 9 2 6))
((4 2 6) (3 1 1 5 9))
listsort
Your listsort
function should take two operands, where the first operand must be a procedure, and the second operand must be a list:
(listsort
<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 listsort
function performs a sort of <list> in ascending order according to <proc>, without changing <list> in any way. The listsort
procedure returns a list.
You are required to use the Quicksort algorithm in your implementation of listsort
. 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:
> (listsort < ’(3 5 2 1))
(1 2 3 5)
Hint: take advantage of your listpartition
function...
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 foreach
. Make sure your improved version of library.scm
is included in your tarball submission.
Again, please feel free to implement any other generalpurpose 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 miniexercises 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 writeup for each problem, whether or not they are classmates. Other cases will be dealt with as plagiarism. Reread 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++ and Scheme) is what will be graded. Correct functioning of your program is necessary but not sufficient!