I think there are some implications for copyright-on-code from all this analysis, it is surprising given the simplicity of the problem that there are so many unique ways to solve it.
This contradicts the statement that 'given an adequate spec two competent programmers will solve a problem in the same way except for stylistic differences'.
I've seen that tossed around quite a few times and if it doesn't hold water for such a simple problem it certainly won't be left standing if we start analyzing larger pieces of code.
On the whole I think this research is one of the most interesting things on HN as of late.
Yes, probably. But it also seems to depend on the level of your language. I.e. if your language's built-ins are close to the problem, the solutions will probably be much shorter and thus have a higher chance of being similar.
Actually, C's string handling is very well-suited to this problem. (Which doesn't mean it is perfect - in fact, it's highly inconvenient for many tasks. Just not this one.)
One of the biggest reservations I initially had about abstraction, when learning programming, was that I didn't consider performance a detail. As such, I didn't litter my code with objects or pure functions even when they made conceptual sense, unless I was convinced the overhead was small and the abstraction helpful.
I've found that languages like Java make assumptions about your memory, and languages like Prolog make assumptions about your data. I'm under the impression that in Haskell in-place modification is an interpreter optimization, whereas C is increasingly employed when resources are constrained and abstraction layers are deemed too costly. Consequently, C is maligned for resulting in faulty implementations behind every corner, yet it remains one of the most used languages.
Wouldn't it be better to build a parse tree and then cluster based on the difference between the trees? I think this is called "tree distance", or sometimes "tree edit distance." There seems to be a reasonable amount of research on the subject.
Much harder to do with the tools I have immediately to hand, and much harder to visualise the main results without special tools. The "fingerprint string" gives 90% of the effect with very little effort on my part.
However, I will investigate further the "tree edit distance" to see if I can bootstrap something quickly, just out of interest. Thanks for the reminder.
It's unfortunate that Baker's "dup" and "pdiff" haven't gotten the open source treatment, or at least if they have, they're not widespread. SCO could have saved themselves a lot of lawyer's fees by running "dup" over SysV and Linux sources to see what's similar.
Pretty neat stuff. The method used for decimating representations is pretty awesome. Seeing the aligned routines makes me think that quite a few of the bioinformatics algorithms could be useful for such an analysis.
The two that spring to mind would are the MCL clustering algorithm that could be applied quite easily to the similarity matrix. As a more academic endeavor, it'd also be interesting to see what kinds of differences in similarity you'd get by applying Needleman-Wunsch.
Thanks for the explanation on your process for creating the clusters and the analysis. It cleared up a few questions I had.
What's interesting is the large clusters where either a for or while loop were used. I'm curious whether if given a (limited) choice any hiring manager would have a preference between the two implementations?
TLDR: How much does/would coding style influence the hiring process?
That's something I'll be going into in the next stage - feature identification. Some routines used for, some used while, some used do, and some used switch.
Yes, switch. Addmittedly not as the looping structure, but for the internal decision process of the loop.
Some of these choices are indicative that the programmer isn't a native idiomatic C programmer, but some might be genuine choices for one reason or another. That's when style choice exposes internal concepts.
More later. (On current work load - much later. It's taking about 2 weeks per article here, so it won't be quick. Sorry.)
And where are these things advertised? I'd love to attend, but need a little bit more notice since I'd have to arrange a flight from Dublin and somewhere to stay for a night or two.
That's pretty logical, given that the problem is inherently a 'loop' problem and that there are 'templates' in use for solving this sort of problem either way.
I don't think 'style' should be the deciding factor in something like this unless the difference in style translates in to 'readable' versus 'unreadable', old-school coders would do it in one style, people that came to C later will probably do it slightly different.
The main criteria are:
- does it work ?
- is it reasonably efficient ? (as in within a factor
of two or so from the optimum solution)
- is it reasonably readable ?
If all of those are good then you could consider the programmer to have passed this test. Such a test by itself is not enough to disqualify someone for hiring or not hiring based on the style alone, assuming the above three conditions are met.
It's just one little element in the total, one of the many 'and' gates you have to get through as a candidate when applying for a position.
> I don't think 'style' should be the deciding factor in something like this unless the difference in style translates in to 'readable' versus 'unreadable'
Not a deciding factor, but there's a lot of subtle info in a whole code sample.
When asking someone for some OO code, I sometimes see OK-but-a-bit-naive code, which includes variable names like "theObject".
That suggests to me that the most important characteristic of this entity in the coder's head is that it is an object - i.e. that they're not very familiar with OO code.
Basically, information like the choice of variables names provides a window on the mental model the coder has of the problem. And that's useful.
If I read the first question correctly it asks if choosing a 'for' over a 'while' would be a reason to pick one programmer over another and I don't think that should be the case, it's a stylistic thing but one that is probably not very important.
I agree with you on the naming issue, but the funny thing is that that sort of information is exactly what was removed in order to make the analysis possible.
"myObject" is one of my pet peeves. I've seen and its relatives "myString" and "myNumber" in far too many published programming texts. In fact, its one of the many reasons I don't like vb.net, it actually has its own my name space!
heh, I just had to think of some of my adventures in metaprogramming in python. Eventually, I ended up with variable names like "decoraterSelf", "mySelf" and "decoratedSelf", when I had stateful class decorators. One of the few instances where I was glad to see a myFrobble-Variable in code :)
Just wondering, what's the solution to the riddle at the end? The test function sets up the input, calls the routine, and then compares its output to the desired output. There doesn't seem to be a place for error there.
You're right, that answer isn't correct. I still think that particular input should be tested, though (you say it is - did you leave out that part of your testing program? It should be possible to construct a program that fails on such inputs.)
I don't think I've found a real "bug" yet. You include, but don't use, stdlib.h; you exit with status 0, even on error; but these are nitpicks, not what you mean. I'll think a bit more.
I tested that case when you mentioned it. All routines submitted pass it correctly, so I haven't worried about it too much. To do so would be to stray too far from the original intention. I think it's hard to write a natural looking routine that fails that test.
I return 0 in all cases because my test succeeds, even if the routine it's testing fails. It's up to my shell to decide what to do about that error. As it stands it reports the error, but it has succeeded in doing so, so it hasn't failed.
Well, I'm stumped. I can think of some other "cosmetic" issues and some things you fail to test (e.g. that the function is in-place, runs in O(strlen(z_terminated)) and does not access memory beyond z_terminated[strlen(z_terminated)]), but that's it. Besides, as you mention, such issues can usually be found just by looking at the function.
Unless I'm sorely mistaken, there's no integer overflow in the program as published. (You could cause an overflow in test() by calling it with a very long output argument, but it's much simpler to cause a buffer overflow, so why bother?)
This contradicts the statement that 'given an adequate spec two competent programmers will solve a problem in the same way except for stylistic differences'.
I've seen that tossed around quite a few times and if it doesn't hold water for such a simple problem it certainly won't be left standing if we start analyzing larger pieces of code.
On the whole I think this research is one of the most interesting things on HN as of late.