Remember to follow the Expectations on Homework when preparing your solutions, including the academic honesty policy.
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).
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.)
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.
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.
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).
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.)
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?
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.]
(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.
(/ (- (* 9 3) (double a)) 2) where double is
defined as (define (double n) (* n 2))
(or (< 5 2) (and (= 15 (- 18 3)) (> 8 4)))
(and (+ 5 -1) false)
(apply-patch 'remove "this is a test string") [use your own
apply-patch program from this assignment]
cond: expected a clause with a question and answer, but found a clause with only one part
x: this variable is not defined
function call: expected a function after an open parenthesis, but found a number
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.
Blah.
Blah.
|#