CS 1102 (A08) Homework 1: Warming Up in Scheme

Due: Setpember 5 (Friday) at 11:59pm via turnin (assignment name hwk1). This is a 24 hour extension over the original due date.

Assignment Goals

Remember to follow the Expectations on Homework when preparing your solutions, including the academic honesty policy.


The Assignment

Programming Exercises: Managing file diffs

Many modern software applications--such as word processors and version control systems--manage multiple versions of files and documents. Rather than store the entire file on each revision, these systems store patches or diffs from which they can reconstruct the current version of the document as needed. In this assignment, you'll implement a basic notion of document patches. Represent documents as strings. You can get documentation on Scheme's string operators by searching for string in DrScheme's Help Desk.

A patch consists of a position (into a document or string) and an operation to perform at that position. The insert operation specifies the string to insert (at the position). The delete operation specifies how many characters should be deleted (starting from the position).

  1. Write data definitions and examples of data for patches and operations.

  2. Write a function apply-op that consumes an operation (one of your structs), a string, and a position (number) and produces a string. The produced string should be the result of applying the given operation to the given string at the given position.

  3. Write a function apply-patch that consumes a patch and a string and produces the string resulting from applying the patch to the string. You may assume that the string is long enough for the operation given in the patch.

  4. Applications often allow multiple users to edit the same document at the same time. These applications then have to merge the respective edits into a single new document. If the users edited different parts of the document, merging consists of applying all the patches. When the edited parts overlap, additional techniques are required to produce a merged document. Write a function overlap? that consumes two patches and produces a boolean indicating whether both patches could be applied to a single string without conflicting with one another.

    Use helper functions to make your code clean and readable. When grading this problem, we will pay particular attention to whether you created helper functions for repeated computations and whether your code follows the shape of the function's inputs (ie, the design template).

  5. Write a function merge that consumes a string and two patches and produces either a string reflecting both patches (if the patches do not overlap) or false if the patches do overlap. Your function should produce the same answer regardless of the order of the two input patches.

  6. In the previous question, we returned false in the event of an overlap. Another option might have been to just return the original (unmerged) string. What are the advantages of returning false instead of the original string in the event of overlap?

  7. Consider the following quotation from Hamlet and an alternative in more modern English:

    *** Original ***
    Hamlet: Do you see yonder cloud that's almost in shape of a camel?
    Polonius: By the mass, and 'tis like a camel, indeed.
    [...]
    Hamlet: Or like a whale?
    Polonius: Very like a whale.
    
    *** Alternative ***
    Hamlet: Do you see the cloud over there that's almost the shape of a camel?
    Polonius: By golly, it is like a camel, indeed.
    [...]
    Hamlet: Or like a whale?
    Polonius: It's totally like a whale.
    
    Define constants for the patches needed to convert the first quotation to the second. Treat each of the two quotations as a single string (you do not need to capture the newlines). Then write a function modernize that consumes a string and applies all of those patches to the string. Test your function on the original Hamlet excerpt. [Credits: This example is a subset of the one in Neil Fraser's explanation of the patch utility.]

Evaluating Scheme Programs

Evaluate each of the following expressions by hand (use the rules covered in class, which match those of Beginner level). Show every step. In each expression, indicate the subexpression that is evaluated to obtain the next expression. For example:
        (sqrt (+ (* 3 3) (* 4 4)))
                 ^^^^^^^
      = (sqrt (+ 9 (* 4 4)))
                   ^^^^^^^
      = (sqrt (+ 9 16))
              ^^^^^^^^
      = (sqrt 25)
        ^^^^^^^^^
      = 5
If an expression would result in an error, show all of the steps up to the error, then indicate the error message you'd get (error messages don't need to be verbatim, as long as they convey the right kind of error). You can use the Stepper to check your answers, but do the problem manually first to make sure you understand how Scheme works.

  1. (/ (- (* 9 3) (double a)) 2) where double is defined as (define (double n) (* n 2))

  2. (or (< 5 2) (and (= 15 (- 18 3)) (> 8 4)))

  3. (and (+ 5 -1) false)

  4. (apply-patch 'remove "this is a test string") [use your own apply-patch program from this assignment]

Debugging Scheme Programs

For each of the following DrScheme error messages (from Beginner language level), describe what code that produces this error message would look like and provide a small illustrative example of code that would yield this error. Your description should not simply restate the error message!
  1. cond: expected a clause with a question and answer, but found a clause with only one part

  2. reference to an identifier before its definition: x

  3. function call: expected a defined name or a primitive operation name after an open parenthesis, but found a number


What to Turn In

Turn in a single file hwk1.ss or hwk1.scm containing all code and documentation for this assignment (there is something to turn in for every part). Make sure that both students' names are in a comment at the top of the file.


Back to the Assignments page