Your employer Litigious Data Analysts Inc. (LDA) is suing
Software Verification Modules Inc. (SVM), claiming that SVM
stole large bodies of LDA's code and incorporated it into their
data mining product, while tring to hide the fact that the code was stolen
by renaming identifiers and by
replacing `lambda` with `λ` and vice versa,
and also making other minor changes.
As part of the legal discovery process, LDA has
obtained copies of SVM's data miner
and wants to compare it to LDA's to find evidence of unauthorized
copying. About 5% of both data miners are written in Scheme. Your
team has been assigned the job of comparing the Scheme parts.

Your boss suggested that you prototype a
procedure `expr-compare` that compares two Scheme
expressions `x` and `y`, and produces a difference
summary of where the two expressions are the same and where they
differ. Your boss wants the difference summary to be easily checkable,
in case there is a bug in `expr-compare` itself. So you
decide to have the difference summary also be a Scheme expression
which, if executed in an environment where the Scheme
variable `%` is true, has the same behavior
as `x`, and otherwise has the same behavior
as `y`. You prefer to have a shorter summary expression,
so you decide that the summary should use `λ` in places where one
input expression used a `lambda` expression and the other
used a `λ` expression (however, the summary should
use `lambda` in places where both input expressions
used `lambda`).
You also want the summary expression to use the same
identifiers as the two input expressions where they agree, and that if
`x` declares the bound variable `X`
in the same place where `y` declares the bound variable `Y`,
the summary expression should declare a bound
variable `X``!``Y` and use it consistently
thereafter wherever the input expressions use `X`
and `Y` respectively. (A bound variable is one
that is declared in an expression by a binding construct such
as `lambda`.)

To keep things simple your prototype need not handle arbitrary
Scheme expressions; it can be limited to the Scheme subset that
consists
of constant
literals,
variable
references, procedure
calls, the special
form `(quote datum)`,
the special form

First, write a Scheme procedure `(expr-compare
``x y``)` that implements the specification
described above. Your implementation must be free of side effects; for
example you cannot use the `set!` special form. Returned
values should share storage with arguments when possible; they should
not copy their arguments.

The output expression should use
`if` expressions and identifiers containing `!`
to represent differences whenever the two
input expressions disagree, attempting to minimize the size of the
subexpressions under the generated `if`s. As a special
case, it should use `%` to represent a subexpression that
is `#t` in LDA's version and `#f` in SVM's
version, and should use `(not %)` to represent the
reverse situation. Here are some examples and what they
should evaluate to.

(expr-compare 12 12) ⇒ 12 (expr-compare 12 20) ⇒ (if % 12 20) (expr-compare #t #t) ⇒ #t (expr-compare #f #f) ⇒ #f (expr-compare #t #f) ⇒ % (expr-compare #f #t) ⇒ (not %) (expr-compare 'a '(cons a b)) ⇒ (if % a (cons a b)) (expr-compare '(cons a b) '(cons a b)) ⇒ (cons a b) (expr-compare '(cons a b) '(cons a c)) ⇒ (cons a (if % b c)) (expr-compare '(cons (cons a b) (cons b c)) '(cons (cons a c) (cons a c))) ⇒ (cons (cons a (if % b c)) (cons (if % b a) c)) (expr-compare '(cons a b) '(list a b)) ⇒ ((if % cons list) a b) (expr-compare '(list) '(list a)) ⇒ (if % (list) (list a)) (expr-compare ''(a b) ''(a c)) ⇒ (if % '(a b) '(a c)) (expr-compare '(quote (a b)) '(quote (a c))) ⇒ (if % '(a b) '(a c)) (expr-compare '(quoth (a b)) '(quoth (a c))) ⇒ (quoth (a (if % b c))) (expr-compare '(if x y z) '(if x z z)) ⇒ (if x (if % y z) z) (expr-compare '(if x y z) '(g x y z)) ⇒ (if % (if x y z) (g x y z)) (expr-compare '((lambda (a) (f a)) 1) '((lambda (a) (g a)) 2)) ⇒ ((lambda (a) ((if % f g) a)) (if % 1 2)) (expr-compare '((lambda (a) (f a)) 1) '((λ (a) (g a)) 2)) ⇒ ((λ (a) ((if % f g) a)) (if % 1 2)) (expr-compare '((lambda (a) a) c) '((lambda (b) b) d)) ⇒ ((lambda (a!b) a!b) (if % c d)) (expr-compare ''((λ (a) a) c) ''((lambda (b) b) d)) ⇒ (if % '((λ (a) a) c) '((lambda (b) b) d)) (expr-compare '(+ #f ((λ (a b) (f a b)) 1 2)) '(+ #t ((lambda (a c) (f a c)) 1 2))) ⇒ (+ (not %) ((λ (a b!c) (f a b!c)) 1 2)) (expr-compare '((λ (a b) (f a b)) 1 2) '((λ (a b) (f b a)) 1 2)) ⇒ ((λ (a b) (f (if % a b) (if % b a))) 1 2) (expr-compare '((λ (a b) (f a b)) 1 2) '((λ (a c) (f c a)) 1 2)) ⇒ ((λ (a b!c) (f (if % a b!c) (if % b!c a))) 1 2) (expr-compare '((lambda (a) (eq? a ((λ (a b) ((λ (a b) (a b)) b a)) a (lambda (a) a)))) (lambda (b a) (b a))) '((λ (a) (eqv? a ((lambda (b a) ((lambda (a b) (a b)) b a)) a (λ (b) a)))) (lambda (a b) (a b)))) ⇒ ((λ (a) ((if % eq? eqv?) a ((λ (a!b b!a) ((λ (a b) (a b)) (if % b!a a!b) (if % a!b b!a))) a (λ (a!b) (if % a!b a))))) (lambda (b!a a!b) (b!a a!b)))

(When testing your code, please note that Racket read–eval–print
loop quotes its results
unless they are self-quoting, so that, for example,
although `12` prints as itself, `(if % 12 20)`
prints as `'(if % 12 20)`.)

Second, write a Scheme procedure `(test-expr-compare
``x y``)` that tests your implementation
of `expr-compare` by
using `eval`
to evaluate the expression
`x`, and to evaluate the expression returned by `(expr-compare
``x y``)` in the same context
except with `%` bound to `#t`,
and which checks that the two expressions yield the same value.
Similarly, it should check that `y`
evaluates to the same value that the output of `expr-compare`
evaluates to with `%` bound to `#f`.
The `test-expr-compare` function should return a true value
if both tests succeed, and `#f` otherwise.

Third, define two Scheme variables `test-expr-x` and `test-expr-y`
that contain data that can be interpreted as Scheme expressions that test
`expr-compare` well. Your definitions should look like this:

(define test-expr-x '(+ 3 ((lambda (a b) (list a b)) 1 2))) (define test-expr-y '(+ 2 ((lambda (a c) (list a c)) 1 2)))

except that your definitions should attempt to exercise all the specification in order to provide a single test case for this complete assignment.

Submit a file `expr-compare.ss` containing the
definitions of
`expr-compare`, `test-expr-compare`, `test-expr-x`,
and `test-expr-y` along with any other auxiliary definitions
needed. Make sure that your definitions work
with `racket`,
the Scheme implementation installed on SEASnet.

© 2015–2016, 2019 Paul Eggert. See copying rules.

$Id: hw5.html,v 1.59 2019/02/24 17:52:08 eggert Exp eggert $