From: Alexander Bykov
Subject: compare two lisp programs for being the same
Date:
Message-ID: <2p2f9l$8h1@pollux.usc.edu>
Hi, I need the program that would compare two lisp programs for being
identical. I do have csh script that uses diff utility. It will strip
off the comments, ignore white spaces and then compare two programs.
The output is the number in the range [0..1]. If the number is > 0.5 I
get suspicious and compare the programs by hand. However my script is
useless against a very simple trick: if one program differs from the
other only by the names of variables then my script would not
recognize the fact that the programs are identical. So I am looking
for lexical analyzer that takes it into account.
I would appreciate your help in finding such a program: let me know by
e-mail if you have the code that does the job or if you know where I
can find one.
--- Alex Bykov ······@pollux.usc.edu
From: Henry G. Baker
Subject: Re: compare two lisp programs for being the same
Date:
Message-ID: <hbakerCoKGt5.46A@netcom.com>
In article <··········@pollux.usc.edu> ······@pollux.usc.edu (Alexander Bykov) writes:
>Hi, I need the program that would compare two lisp programs for being identical.
(I assume that) You're supposed to be _teaching_ this course, and you
can't compare homework for identity?
Seriously, many compiler first passes rename everything as they run.
If you're the tiniest bit careful, you can arrange so that
alpha-renamed programs map to the same program. Unfortunately,
rearranging the ordering of functions will screw this up.
A similar scheme is that of 'De Bruijn' (sp??) notation, which works for
a lexically scoped language. Each variable reference is replaced by a
relative index into the lexical environment -- essentially what every
Algol compiler does already.
I believe that Scheme allows for one of its 'equality' predicates to
do something more interesting on functions than simply compare pointers.
There may even be Scheme implementations that do things like the above
for their equality predicate.
From: Simon E Spero
Subject: Re: compare two lisp programs for being the same
Date:
Message-ID: <2p6aeg$fmj@bigblue.oit.unc.edu>
Well, solving the full problem is a little tricky, as I've already
eaten breakfast, and I never do impossible things after that. :)
Depending on how devious your students are, you could do a quick hack to
just READ in each expression in the file, and then compare the structures
Just walk down each form, making recursive calls for each cons, and
checking for identical types for everything else.
Here's a quick hack to do that; it's pretty easy to defeat; if the order
of defuns is changed, then the matcher will be defeated. You could make
it smarter by sorting the forms by length, and testing each form in
the second file against all forms of the same length in the first file.
Simon
(defun type-eq (x y)
"do x and y have the same type?"
(eql (class-of x) (class-of y)))
(defun check-form (x y)
"check two forms for structural equality"
(if (and (consp x) (consp y))
(and (check-form (car x) (car y))
(check-form (cdr x) (cdr y)))
(type-eq x y)))
(defun check-files (filename-1 filename-2)
"compare two files for structural equality"
(let ((forms1
(with-open-file (file1 filename-1 :direction :input)
(do* ((forms nil)
(form (read file1 nil nil) (read file1 nil nil)))
((null form) forms)
(setq forms (cons form forms)))))
(forms2
(with-open-file (file2 filename-2 :direction :input)
(do* ((forms nil)
(form (read file2 nil nil) (read file2 nil nil)))
((null form) forms)
(setq forms (cons form forms))))))
(format t "~d% matches~%"
(loop for i in forms1 and
j in forms2
count t into total
count (check-form i j) into match
finally (return (* 100 (/ match total)))))))