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 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).
Write data definitions and examples of data for patches and operations.
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.
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 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).
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.
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.
[Credits: 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 Scheme 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
reference to an identifier before its definition: x
function call: expected a defined name or a primitive operation name after an open parenthesis, but found a number
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.