Homework Four
User-Defined Data Types

Comp210

Due: 98.Sep.30 (Wed.) in class

As usual, follow the design recipe as appropriate.
  1. (3pts) Write a function next-floor to control an elevator. next-floor takes three arguments: the direction the car was just going (either 'up or 'down), the current floor number (an integer), and a list of requested floor numbers already sorted in ascending order. next-floor returns the next floor for the elevator to visit. If the list of requested floors is empty, next-floor should simply return the current floor.

    You can test your function (and helper functions) traditionally. If you like, we also provide you with a visual elevator simulator. In DrScheme, ``Set Library to...'' teach/elevator-lib.ss. To start the elevator, simply evaluate 

          (run next-floor)
    after defining your function next-floor.

    The simulator displays a picture of the elevator. Clicking on call buttons adds floors to the request list. (The up and down buttons behave identically.) The simulator works by calling your function next-floor repeatedly, to decide the next floor to be visited.
    Hint: You can check out the simulator immediately by writing a very simple next-floor function. For example, have next-floor always return the first floor on the request list, or use this rather obstinate elevator controller: 

          (define next-floor
        (lambda (direction current-floor floor-requests)
          3))
    This allows you to get started and see what the simulator looks like.

    Be sure that your elevator controller is fair: Every requested floor should eventually be visited, regardless of the other requests in the list. (This idea of fairness refers to making successive calls to next-floor, with an evolving request list.)
    Hint: Split the list of requested floors into two parts, those floors above the current floor and those below. Use data definition and program templates to derive appropriate helper functions for processing these two pieces.

  2. (4pts) Arithmetic expressions are one of the fundamental components of most programming languages. We can define arithmetic expressions, ArithExp, recursively as follows:
    An ArithExp is
    • (make-real number)
    • (make-plus ArithExp ArithExp)
    • (make-times ArithExp ArithExp)
    where the ArithExps for make-plus and make-times are the arithmetic expression on each side of a plus sign or multiplication sign.
    1. Use define-struct to build constructors, selectors, and predicates for arithmetic expressions. List the names that Scheme assigns to these constructors, selectors, and predicates.
    2. Write a function calc that takes as input an arithmetic expression and returns its value as a number. As always, include your data definition, program template, completed program, and test data.
    3. Write a Scheme function make-sum that takes as input a proper (i.e., non-empty) list of numbers and returns as output an arithmetic expression denoting their sum. Your function should use the constructors defined in the first part of this problem. Include your data definition, sample data, program template, test input/outputs, and completed program.

      Note: The sum should stay unevaluated¹. If your input list contains seven numbers, the resulting arithmetic expression should consist of six uses of the constructor for plus applied to seven uses of the constructor for real; it should not be just a single use of the constructor for real.

  3. (3pts) Recall the data definition for family trees (from Friday's lecture). Write the function count-unknowns. Write a few small test cases yourself; here is a medium-sized test case.

    To answer (by thinking, not w/ a program): For a family tree whose size². is five, how many 'unknowns does it contain? (Is is possible for other trees of size five to contain more or less?) How many 'unknowns in a family tree of size seven? Of size n?

¹ Why on earth would we want to avoid evaluating an expression? Because we might eventually want to allow placeholders as another type of ArithExp. This would let us start to make sense of (lambda (m n) (+ m 7 n)). Clearly the body of the lambda is one of these generalized ArithExprs, and we can't yet evaluate the expression (until somebody would apply the lambda to some actual down-to-earth numbers).

No, we won't actually make this extension to ArithExps, although in the first two weeks of Comp311 you write a program to interpret (most) Scheme expressions -- the heart of DrScheme! Using data definitions derived from the Law of Scheme, this is quite managable...(and if you avoid using data definitions and templates, it can be a mess!). (back)

² Remember, the size of a family tree is the number the family trees involved (including itself). Recall the function size in class. (back)

Back to Assignments
Back to Comp 210 Home