CS 1102 (A12) Homework 1: Warming Up in Racket

Due: August 30 (Thursday) at 11:59pm via turnin.

Assignment Goals

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

The Assignment

Use the How to Design Programs / Beginning Student language for this 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 Racket's string operators by searching for string in DrRacket's Help Desk.

A patch consists of a position (starting at zero) 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, examples of data and templates for patch, operation, insert and delete. (Hint: An operation is a mixed type which is either an insert or a delete.)

  2. Write a function apply-op that consumes an operation, 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 the two patches cannot be applied to the same string because they conflict. Because of the way that patches will be applied (see step 5), there are only three types of conflict you need to consider:

    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 the shape of your functions follow the shape of their input data (i.e., you have explicitly used the design templates).

  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. (Hint: Apply patches from the end of the string forward, applying deletions before insertions.)

  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. [Acknowledgement: This example is a subset of the one in Neil Fraser's explanation of the patch utility.]

Evaluating Racket 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 Racket 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 Racket Programs

For each of the following DrRacket 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. x: this variable is not defined

  3. function call: expected a function after an open parenthesis, but found a number

What to Turn In

Grade your own homework according to General Grading Guidelines before you hand it in!

Turn in a single file hwk1.rkt containing all code and documentation for this assignment (there is something to turn in for every part). Either homework partner can turn in the assignment, but make sure that both students' names are in a comment at the top of the file.

The answers to questions 8 through 14 can be included in the .rkt file using the Racket block comment characters, as in:

     All the text between these characters will be ignored by DrRacket
     when this file is run.

Back to the Assignments page