EECS 321: Programming Languages — Homework 1

1 Set up DrRacket & Create Handin Account

Be sure you have Racket version 7.0 installed. You can download it from https://download.racket-lang.org/ Racket is also installed on the T-lab machines in: /home/software/racket/bin/drracket

Open DrRacket, set the language to "The Racket Language" (via the Language | Choose Language menu item), put the following program into the upper window (replacing whatever is there), and click "Run":

#lang plai

(expt 2 100)

You should see the prompt in the interactions window (a > character) and the number 1267650600228229401496703205376.

The first line tells Racket that we’ll be using the plai language, which is what we’ll use throughout the quarter. You can find the documentation for the plai language here. The second line just does some computation to make sure everything is working.

Install the handin server plugin by using DrRacket’s File | Install Package... menu item. In the dialog box, paste this url into the box: http://www.eecs.northwestern.edu/~stamourv/teaching/321-F18/cs321-fall-2018-handin.zip

Then press Install. Wait for the Close button to become enabled (and then click it). Restart DrRacket.

After restarting DrRacket, select the Manage EECS 321 PL Handin Account... menu item from DrRacket’s File menu. Change to the New User panel, and pick a username and password. (Use your real name and real NetID, so that we can connect your homework submissions with you. DON’T reuse an existing password. Good password hygiene is important.)

You will have to install the handin plugin for each different filesystem for which you want to have a Handin button. However, after creating a handin account once from any machine, you can use DrRacket’s Handin button on any other machine.

There is a quick reference for Racket available from the course webpage. You may wish to have a look if you’re not familiar with the language.

2 Honor Code

Every homework assignment you hand in must begin with the following definition (taken from the Provost’s website; see that for a more detailed explanation of these points):

(define eight-principles

(list

"Know your rights."

"Acknowledge your sources."

"Protect your work."

"Avoid suspicion."

"Do your own work."

"Never falsify a record or permit another person to do so."

"Never fabricate data, citations, or experimental results."

"Always tell the truth when discussing your work with your instructor."))

If the definition is not present, you receive no credit for the assignment.

3 Trees

The following Tree datatype describes a variant of binary trees. Such trees may have two kinds of internal nodes, one with one color (a string), and one with two colors. Nodes with two colors are considered to be of both their colors; i.e., a node that has both the colors "red" and "blue" counts both as a "red" node and as a "blue" node. The leaves of these trees carry an integer value (positive or negative).

(define-type Tree

[one-color-node (color string?)

(left-child Tree?)

(right-child Tree?)]

[two-color-node (color1 string?)

(color2 string?)

(left-child Tree?)

(right-child Tree?)]

[leaf (value integer?)])

4 Search

Implement a contains? function that takes a Tree as its first argument and a color (string) as its second. contains? should return #t if the given tree contains a node of the given color, and return #f otherwise.

Every problem must come with an appropriate set of test cases. At a minimum the test cases must cover every branch in each function you write. Here’s two to get you started:

(test (contains? (one-color-node "blue" (leaf 1) (leaf 4))

"blue")

#t)

(test (contains? (one-color-node "blue" (leaf 1) (leaf 4))

"red")

#f)

5 Counting Colors

Implement a count-colors function, which takes a Tree as argument and returns the number of distinct colors that appear in the tree.

Hint: you may want to take a look at the remove-duplicates or member functions.

6 Monochromatic Trees

Monochromatic trees are trees that contain (at most) a single color. Trees that consist of a single leaf are trivially monochromatic.

Implement a monochromatic? function, which takes a Tree as argument and returns #t if the tree is monochromatic, and returns #f otherwise.

7 Color-Based Summing

Implement a colored-sum function which takes a Tree and a color, and returns the sum of the values at all the leaves which have a node of the given color anywhere above (i.e., closer to the root) them in the tree.

8 Color-Guarded Increment

Implement a increment-if-not-color function, which takes a Tree, an integer, and a color as arguments, and returns a new Tree. The new tree has the same shape as the original tree, except that the values at each leaf is incremented by the given integer unless that leaf has a node of the given color above it in the tree.

9 Color-Based Merging

Implement a merge-color function, which takes a Tree and a color as arguments and produces a new Tree where all the nodes of the given color are replaced with a single leaf, whose value is the sum of the leaf values of the entire subtree.

10 Handin

Click the handin button in DrRacket to hand in your submission before the deadline. Make sure you wait until you see the "Handin Successful". message before closing. Late homework will not be accepted.