Scheme Programming Weeks 1 and 2

Individual Work

Group work to get acquainted with Scheme is OK, and asking and answering general questions about how things work is OK. But aside from 1.1, all these exercises are individual. That is: no joint efforts, no code-sharing.

Turn in your code, README, annotated output transcripts, and PDF writeup to Blackboard. For these first exercies the writeup is de-emphasized or not necessary (notice the weights).

You can download Dr. Racket easily for most platforms. You should also find an executable Racket drracket on the UR UG network somewhere under /usr/staff/drracket/, possibly at /usr/staff/drracket/plt/bin/drracket. Let us know if there are any problems or surprises.

I use the swindle version of the language, the top choice of the several options there (sounds most advanced). R5RS or "pretty big" might be OK too, but see below. Some versions of the language don't allow elementary things you might expect, like giving an error on (cons 'a 'b) since the answer isn't a proper list, it's a pair.

Week 1. Code+Readme 100%, Writeup 0%

1.1 Use course ``textbook'' refs and read tutorials, reference, the suggested book The Scheme Programming Language by Dybvig, whatever works. The DrScheme help desk has a very useful pointer to the ``Dr. Scheme Programming Environment'' and an on-line MIT text that looks useful. You have to choose a language to get started (Language tab in the Racket interaction window). You need to klik Run (upper right) after changing languages.

Get acquainted with the DrScheme tools. Do the normal get-acquainted thing with examples, debugging, etc. A very few elementary observations by a naive user are in Schematology .

Look through the list of built-in functions. Do other examples and exercises that appeal to you (or you may want to jump ahead and start work on later exercises in this set). Anyway stay busy, create and answer your own questions, work in groups to understand general issues, and your classmates, the TA, or whoever you can find who knows this stuff are legal resources for general questions.

1.2. Scheme provides the procedures min and max. Each takes two numeric arguments, returning the minimum or maximum, or the first argument if they are equal. Define them in Scheme.

1.3. Define the predicate list?, which returns true if its argument is a (proper or improper) list and false otherwise. [Hint: since arg. need not be a proper list, you only need to determine whether it is a pair or ()].

1.4 Now define proper-list? which tests if the argument is a list terminated by (). Try to avoid using if (or cond). Use and and or instead.

1.5. Define make-list , which takes a nonnegative integer n and an object and returns a new list, n long, each element of which is the object. [Hint: the base test should be (= n 0), andthe recursion step should involve (- n 1).] Generally () is the base case for recursion on lists, and one ``cdrs down'' them, whereas 0 is natural base case for recursion on nonnegative numbers, and subtracting 1 is the natural way to get them closer to 0.

1.6. In indirect recursion, procedures can use each other. Define odd? and even?, each in terms of the other [Hint: what should each return when its argument is zero?].

Week 2. Code+Readme 100%, Writeup 0%

2.1. Let's represent a trinary tree: each tree node is either null or has a contents and three child nodes. Not only that, each node is just a list of four items: contents and three children. If the node is a leaf, it has a value but has three null lists instead of children.

A node with contents of 3 and two children might look like '(3 a () b), where a and b are other nodes (4-element lists). You can use a string for contents and not an integer if you want.

Any tree is thus just a nested list, and for your work I'd just suggest you construct a few of them by hand that span the usual end-cases and normal cases (null tree, full tree, skinny tree with few children per node, etc.).

Both the required functions are probably easiest to write as recursive depth-first tree-traversals like those in 172, only for trinary, not the usual 172 binary trees.

Define a function to copy such a tree so that no node in the copy is eq? to a node in the original. That is, no fair just pointing to your original tree or parts of it... you need to make a new tree-representation list.

Define a function that takes an object and such a tree and returns true if the object is eqv? to the data field of one of the nodes.

2.2. Define an iterative (i.e. using do) and a recursive version of a function that takes an object x and a vector v and returns a list of all the objects that immediately precede x in v.

 (precedes 'a \#(a b r a c a d a d r a))
(r c d r)


Dvybig on page 52 (recall his book is on line.... Scheme Prog. Lang Ed. 3) shows one way to program a queue, using set-car!, set-cdr!. Due to ideological purity, Racket no longer supports these particular commands, which are completely non-functional in spirit. "Mutable lists" are now supported at least in swindle by mcons, mcar, mcdr, set-mcar!, set-mcdr!. You can't "mutate" the 'normal' lists you get in Scheme since they are now considered "immutable".

Anyway, please implement a priority queue with similar instructions to those for the queue, and demonstrate it works.

2.4 This function will be useful in weeks 3-4 if you take the 8-Puzzle option. Extend remv so it takes two lists and a match function. Its value is the first list with all elements that match (according to the match function) anything on the second list removed, like

(define rem-all
   (lambda (dirtylist badlist match)
)  )

(define dirtyletters '(x a  z x b z x x c x y))
(define dirtynumbers (list 1 0 0 7 0 0 6 7 2 3 8 9 9 0))
(define badletters '(x y z))
(define badnumbers '(7 9 8))

>(rem-all dirtynumbers badnumbers eqv?)
(1 0 0 0 0 6 2 3 0)
>(rem-all dirtynumbers badnumbers =)
(1 0 0 0 0 6 2 3 0)
>(rem-all dirtyletters badletters eqv?)
(a b c)
>(rem-all dirtyletters badletters =)
*BUG* VecFilter.scm::1103: =: expects type  
as 2nd argument, given: x; other arguments were: x
This page is maintained by Deer Boy

Last update: 7/6/11