Problem Set 5h

This is the honors version of Problem Set 5; if you’re looking for the normal version, click here!


home work!

Programming Language BSL

Purpose This problem set (primarily) concerns the design of functions on self-referential data definitions.

You should’ve received an email from your lab’s head TA on/around Oct. 3rd assigning you a new partner. This problem set should be done with your new partner. If you were not assigned a new partner or you discover that your partner is no longer in the honors class, let your lab’s head TA know right away so we can assign you another partner.

You must follow the design recipe. The graders will look for data definitions, contracts, purpose statements, examples/tests, and properly organized function definitions. For the latter, you must design templates. You do not need to include the templates with your homework, however. If you do, comment them out.

Your graders have been instructed to grade off for gruesomely laid-out code; proceed accordingly.

Finger Exercises HtDP/2e: 166, 167, 168, 169, 171, 172, 173, 174, 175, 176; in preparation for the first exam, consider solving any of the extended exercises in chapter 13. (As usual, "finger exercises" will not be graded; they are just for you to practice on.)


Problem 1 : Processing Mail

You are designing software for the post office to help process physical mail. There are two kinds of physical mail: letters and boxes. A letter has an address (which we’ll represent simply, as a string) and a weight (measured in ounces). A box has height, width and length dimensions (measured in inches) and a weight (measured in ounces).

There are some rules for mail:
  • A letter must weigh less than 3.5 ounces.

  • The sum of a box’s height, width, and length must be 62 inches or less, its total volume must be 7938 cubic inches or less, and its weight must be 50 pounds (800 ounces) or less.

  • A letter costs fifty cents to mail, while a box is fifteen cents an ounce.

Here are the tasks before you:
  1. Design a data definition, Item, to represent one item of mail.

  2. Design a function, item-ok?, to determine if a piece of mail satisfies the rules.

  3. Design a data definition, LOI, for a list of items.

  4. Design a function, bad-items, that takes a collection of mail (represented as an LOI), and returns all the items that don’t satisfy the rules.

  5. Design a function, total-postage, that produces the total postage for a collection of mail.


Problem 2 : Graphical Editor, Revisited

Re-develop your graphical editor from the last assignment using a slightly different data representation.

A 1String is a string, s, whose length is exactly one, i.e. (= (string-length s) 1). Note: 1String is not a valid BSL identifier, but it works fine as a name for your data representation.

; An Lo1String (i.e., list of 1Strings) is one of:
; - empty
; - (cons 1String Lo1String)

Revise the Editor data defintion from the first part of the last assignment to only use 1Strings and Lo1Strings:

(define-struct editor (pre post))
; An Editor is a (make-editor Lo1String Lo1String)


Problem 3 : Pocket Calculator

In this part of the assignment you will develop the basic pieces of a small pocket calculator for arithmetic expressions.

An arithmetic expression can either be a number, a variable, a unary operation applied to one argument, or a binary operation applied to two arguments. So for example, 3 + 4 is an arithmetic expression – the binary operation + is applied to the arithmetic expressions 3 and 4. Arithmetic expressions nest of course, and we use parentheses to indicate the nesting, so for example, (1 / 2) * (x + (3 + 4)) is an arithmetic expression. The basic operations are (unary) -, which flips the sign of its argument, and (binary) -, +, *, /, which perform subtraction, addition, multiplication, and division, respectively.

  1. Develop a data definition for arithmetic expressions without variables.

  2. An expression that contains no variables can be evaluated. For example, 3 + 4 evaluates to 7. Develop a program eval-arith that evaluates a given arithmetic expression (without variables).

  3. Develop a data definition for arithmetic expressions that may contain variables. Hint: what can you reuse?

  4. Develop a program plug-in that consumes an arithmetic expression (that may contain variables), a variable, and a number, and produces a similar arithmetic expression where all occurrences of the given variable are replaced with the given number. So for example, plugging 5 in for x in (the representation of) 2 * (x * x) should produce the expression (that represents) 2 * (5 * 5).