Tests for programmers Part IV: comparing routines | Hacker News Reader

Tests for programmers Part IV: comparing routines

solipsys.co.uk

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.)

Yes, it is. But C's other nuts and bolts are so low level that they introduce lots of variability.

In e.g. Haskell everyone would just do

  condense_by_removing :: Char -> String -> String
  condense_by_removing c = filter (/=c)

Because there's much less going on here--the loop being more or less implicit only--there's less room for variations.

Mind you, Haskell programs also show lots of variability if the tasks gets only slightly more complicated.

The Haskell snippet doesn't remove the character in place though, does it? I imagine solutions would be more varied then.

No. "In place" has virtually no meaning in Haskell.

I find this very interesting -- a popular idiom in one language can't even be represented in another.

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.

The Haskell compiler is free to use in-place mutations, when it can prove that nobody can access the old object any longer.

The language Clean supports this notion explicitly in its type system (and uses it for IO, instead of, say, Monads like Haskell).

You can do replace stuff in-place (and other low-level stuff) in the IO Monad.

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.

You should probably start with Brenda S Baker's work at Bell Labs: http://www.cs.ucdavis.edu/~devanbu/teaching/289/Schedule_fil... references the final result.

Baker's alumni web page: http://cm.bell-labs.com/cm/cs/who/bsb/index.html

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.

http://www.micans.org/mcl/ http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algori...

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.)

That's fair enough. Are you still coming to the London meetup on Thursday?

I was going to ask if it's still on. Yes, I'm intending to. I need to remember/find out where and when.

I'm so busy at the moment that important things are starting to slide and get lost.

Is it open for other hackers, too?

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.

They're advertised as local posts here on HN. Here's the link: http://news.ycombinator.com/item?id=1434964

Sorry for the delay, hope I've given you enough time to sort out travel arrangements.

Well, I wouldn't have made it anyway, but I'll keep my eyes open for the next one. Maybe I'll be able to go then :)

Yes, I believe it's open to anyone. See the previous post: http://news.ycombinator.com/item?id=1434964

Thanks!

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.

http://en.wikipedia.org/wiki/Integer_overflow

Nope - not integer overflow.

(OK, yes, for exceedingly large inputs there are issues about sizes of integers, etc., but that's not the bug. It's much, much simpler.)

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?)

See http://www.joachimschipper.nl/posts/20100622/answer.txt. (Hidden behind a hyperlink to not spoil the riddle.)

I think I disagree with you. The input you mention is correctly handled by the routine you mention, and is tested correctly.

Certainly there is a bug other than the one you think you've found, and I don't think the circumstances you mention demonstrate a bug at all.

I would certainly be interested in seeing a more detailed analysis.

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.

But that's not the point, as you say.

And the real bug is still there.

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.

Will you give out the answer at some point?

Yes - in the next part of the analysis.

Interesting analysis so far.

Are we going to see some performance data?

While pure performance should not be the overriding consideration, it would still be interesting to see how everyone's routine stacked up.

I would hazard a guess that some dissimilar looking routines will have very similar performance.

Of course, in reality, all I am looking for is the confirmation that my code did not suck too badly...

What's your routine ID and I'll give you my opinion - I will discuss performance later.

While I was trying to figure out why my submission ended up where it did...

I realized my code has a bug.

It's too late for a resubmission, isn't it? :(

I think all solutions are used, anyway. And the submissions are anonymous for exactly this reason.

Reply on news.ycombinator.com