Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ydiff: Structural Comparison of Programs

yinwang0.wordpress.com

Post reply on HN
Print view View original

21–30 of 35 posts

Re: Ydiff: Structural Comparison of Programs

#21

Post by shurcooL »

pshc wrote: post #18
shurcooL wrote: post #12

Earlier quoted context omitted.

> 3) I get your whole in-the-future-we-store-ASTs argument, but that's certainly not the case today. Today we store text, and I don't see that changing. Could there also be a diff, perhaps even another mode that, counter to just dealing with structure, deals with formatting? ie, find the ranges that contribute nothing to the AST and then diff those textually. Agree. I think it's likely code will be stored as text, bu…

I've actually been trying to make 3) happen with a long-standing project of mine, because serializing AST to text discards information. In a (proper) AST, human-readable names are never used as pointer values. When you bind something (reference a variable), you just point at that variable's node, rather than mentioning it by string. This removes a huge class of artificial problems brought on by plaintext source code…

I don't see why a variable can't have a "name" property, even if it's not used as pointer value. I don't see why ASTs should have less information than source code. IMO they're equivalent, and just different forms of representation.

ASTs are easier to manipulate with code, source code is easier to manipulate with text editors. We don't really have good tools for manipulating ASTs yet.

Re: Ydiff: Structural Comparison of Programs

#22

Post by jacques_chester »

RBerenguel wrote: post #2

Neat, love new approaches to old problems. At first sight I thought it would be an awesome implementation of an idea I had (and probably tons of other people before and after :) a few years ago to find cheating among C programming assignments: convert programs to PostScript "drawings": ifs, fors and certain other functions gave rise to different "movements" of the cursor, eventually drawing paths for different expres…

I've seen cheating-detection programs that use tree diff scores to compare code from different students.

The theory goes that students who share solutions will probably change the variable names, do some reformatting etc, which would fool a text diff. But the actual structure of the AST will be the same or similar.

So if you find close matches, you inspect them more closely.

Some quick Googling reveals that plagiarism detection using tree comparisons is a common idea.

Re: Ydiff: Structural Comparison of Programs

#24

Post by jared314 »

frozenport wrote: post #15

Wonderful, although I would rather have the AST integrated with GIT and not as some other kind of version control.

As long as you can convert the AST into a git Tree Object[0] you should be good to go.

[0] http://git-scm.com/book/en/Git-Internals-Git-Objects#Tree-Ob...

Re: Ydiff: Structural Comparison of Programs

#25

Post by pshc »

shurcooL wrote: post #21
pshc wrote: post #18

Earlier quoted context omitted.

I've actually been trying to make 3) happen with a long-standing project of mine, because serializing AST to text discards information. In a (proper) AST, human-readable names are never used as pointer values. When you bind something (reference a variable), you just point at that variable's node, rather than mentioning it by string. This removes a huge class of artificial problems brought on by plaintext source code…

I don't see why a variable can't have a "name" property, even if it's not used as pointer value. I don't see why ASTs should have less information than source code. IMO they're equivalent, and just different forms of representation. ASTs are easier to manipulate with code, source code is easier to manipulate with text editors. We don't really have good tools for manipulating ASTs yet.

The same amount of information exists, but is normalized. The variable _definition_ absolutely will have a "name" annotation, but copying that name to each binding site is brittle. To render a binding, just dereference the pointer to the original definition and use its name.

I'm working on it.

Re: Ydiff: Structural Comparison of Programs

#27

Post by RBerenguel »

jacques_chester wrote: post #22
RBerenguel wrote: post #2

Neat, love new approaches to old problems. At first sight I thought it would be an awesome implementation of an idea I had (and probably tons of other people before and after :) a few years ago to find cheating among C programming assignments: convert programs to PostScript "drawings": ifs, fors and certain other functions gave rise to different "movements" of the cursor, eventually drawing paths for different expres…

I've seen cheating-detection programs that use tree diff scores to compare code from different students. The theory goes that students who share solutions will probably change the variable names, do some reformatting etc, which would fool a text diff. But the actual structure of the AST will be the same or similar. So if you find close matches, you inspect them more closely. Some quick Googling reveals that plagiaris…

Yup, when I thought "this looks neat!" I didn't think it was very novel, the idea is very clear once you are actually looking at cheated code (IIRC my brother in law told me a few years ago - later an I wrote my code, which was written before meeting him - he had used a similar method years earlier in another university). But I didn't bother much with looking for existing solutions: this was just soo fun! I love reinventing wheels for fun/learning :)

Re: Ydiff: Structural Comparison of Programs

#29

Post by aninhumer »

pshc wrote: post #18
shurcooL wrote: post #12

Earlier quoted context omitted.

> 3) I get your whole in-the-future-we-store-ASTs argument, but that's certainly not the case today. Today we store text, and I don't see that changing. Could there also be a diff, perhaps even another mode that, counter to just dealing with structure, deals with formatting? ie, find the ranges that contribute nothing to the AST and then diff those textually. Agree. I think it's likely code will be stored as text, bu…

I've actually been trying to make 3) happen with a long-standing project of mine, because serializing AST to text discards information. In a (proper) AST, human-readable names are never used as pointer values. When you bind something (reference a variable), you just point at that variable's node, rather than mentioning it by string. This removes a huge class of artificial problems brought on by plaintext source code…

While there are certainly advantages to storing code in an AST format, I don't think any of these are significant enough to overcome the hugely important advantage of legacy support. Maybe in the long term it will make sense to replace text based code with a new AST format, but for now a slightly crufty but ultimately isomorphic text format seems entirely sufficient.
Post reply on HN