Wednesday, December 22, 2010

Python as an Alternative to Lisp or Java, Peter Norvig revisited

Because I'm a fan of Peter Norvig, and because I've recently been going through some of his articles about Lisp, I ran into an old entry of his from 1999 about Lisp and Java. In it, he links off to a study where a sample problem was provided in order to compare the efficiency of C++/Java programmers. Feel free to read his post Lisp as an Alternative to Java. How did Peter do 11 years ago?

I did not participate in the study, but after I saw it, I wrote my version in Lisp. It took me about 2 hours (compared to a range of 2 to 8.5 hours for the other Lisp programmers in the study, 3 to 25 for C/C++ and 4 to 63 for Java) and I ended up with 45 non-comment non-blank lines (compared with a range of 51 to 182 for Lisp, and 107 to 614 for the other languages). (That means that some Java programmer was spending 13 lines and 84 minutes to provide the functionality of each line of my Lisp program.)

While relaxing a bit while testing was going on for our code push today, I followed the same instructions, only in Python. I hadn't read his lisp code before (and reading it afterwards, there is a lot of Common-Lisp-isms that I don't really understand), nor had I read the specific problem before (though I solved a similar problem in the spring of 1999 during a local programming competition in undergrad in C++).

My first correct solution was done in an hour with 53 non-comment lines, but I could trim it to 37 lines if I was okay collapsing all lines that could be collapsed.

Looking around a bit while counting lines, I realized that if I added a utility function, I could remove some confusing stuff, while at the same time reducing line count. Spending another 10 minutes got me to 47 lines without comments or spaces, and 44 if I collapsed all lines that could be collapsed while limiting it to 78 columns wide.

My solution is available at this github gist. I didn't write this or this blog post to be "look at how good Python is", because obviously one's ability to program solutions to problems/puzzles/etc., is fundamentally related to your experience and ability to think in a given language. And, on the most part, I've been living and breathing Python for the past 10+ years, with the last 6 years programming 4-5 days a week in Python both professionally and personally. That said, I do think that similar conclusions can be drawn from this bit of the experiment as Peter made, primarily that Python is very effective, very expressive, and can cut out a lot of the bullshit that most Java programmers deal with on a regular basis.

UPDATE:
A commenter pointed out that I had a bug that was exposed running over the large input files and comparing with the large output file. I fell into the same ambiguity as was pointed out in the paper as the "hint" on page 12.

If you want to see more posts like this, you can buy my book, Redis in Action from Manning Publications today!

19 comments:

  1. Groovy also cuts out a lot of the bullshit that most Java programmers deal on a daily basis. Performance-wise it's improving, but in terms of expressiveness and ability, it's top notch.

    ReplyDelete
  2. @anatoly The "syntactical sugar" of Groovy cuts out the BS but 90% of devs mis-use Groovy and just write shorter Java code (static typing and all) instead of fundamentally altering the programming paradigm (like Lisp or Python would do) which leads to *real* productivity improvements.

    ReplyDelete
  3. @Anonymous There are lots (and *lots* and **lots**) of Python coders who write Java-in-Python. (Trac, for instance, looks a whole lot like Java code machine-translated into Python. And the AppEngine sample code... all that needs be said is that 'subclass-and-override' is a anti-pattern virus.)

    Real productivity in Python (as in any language) comes from writing code that matches the idiom of the language, which sadly most people never learn to value. The cult of 'it should be maintainable by any other programmer' leads to everything being written in a crappy pidgin of Algol.

    ReplyDelete
  4. I've come across your post via HN, and thought it'd be fun to do the exercise in Lua: https://gist.github.com/752460 - though I think I missed on some requirement since the order is different for me than in the sample output.

    ReplyDelete
  5. Andrew: The output order is allowed to be arbitrary -- your program looks correct to me (on the long sample input/output) after sorting.

    Josiah: I think your program might have a bug! Try running on the full test-case input (http://www.flownet.com/ron/papers/lisp-java/input.txt)...

    Here's mine: https://gist.github.com/752506

    ReplyDelete
  6. @Mike Cotton:
    I agree with you entirely. A language is more than a set of libraries. It has it's own style and behavior, and one's code should match it accordingly.

    Some months back, I tried to jump into the Python bandwagon, but failed miserably. I too come from a Java background, and was using some random tutorials to try to get things done, but like you say, I was just using Python as if it were Java. And it felt....terrible. If I just wanted to keep coding in Java, I could stick to Java! Could you (or the poster) point me to some appropriate resource to jump into python?

    ReplyDelete
  7. @Omar It all depends on how you learn and what you are willing to put up with. When I was learning, I went through the Python tutorial and it was just enough for me to get started down the "learning Python" path.

    I've been pushing people towards "Think Python: How to Think Like a Computer Scientist", which is available on Amazon, or as a freely downloadable PDF, or via html online. If you are patient and follow along, it may get you into the swing of doing things the Python way. I've heard that some people dig the "Dive Into Python" book, but it really didn't do it for me when I read it.

    There's also the "Learning Python" videos that Google put out along with some extra documentation: http://code.google.com/edu/languages/google-python-class/index.html

    ReplyDelete
  8. @Omar
    This seems like exactly what you are looking for.

    ReplyDelete
  9. @Omar
    Look up "Dive into Python 3". It's available for free online.

    ReplyDelete
  10. I haven't read this yet, but FYI - Norvig also posted an article called

    "Python for Lisp Programmers"

    at

    http://norvig.com/python-lisp.html

    ReplyDelete
  11. What I love about Python aside from its expressiveness is its multi-paradigm nature. In my projects, I use functional style programming for data processing, object oriented style programming for structure, organization and state management and procedural style programming for simple utility functions.

    Python is also, perhaps, the only language I know that gets namespaces right.

    ReplyDelete
  12. dilap: I do notice that my output differs from the full output, I didn't see the full-length input and output when I was writing the program in the first pass, so didn't test it against that input. I do remember reading mention of an ambiguity in the paper, and in re-reading that section of the paper, I suspect I fell into the "trap" caused by the problem definition ambiguity.

    I'll fix my source and update the gist tomorrow. Thank you for the pointer :)

    ReplyDelete
  13. dilap: I finished packing for my trip and found the 5 minutes to look at the code. I've updated the gist, and will be updating the post in a moment. Thank you again :)

    ReplyDelete
  14. This is too much, from reddit I've slowly got the details to this "research" paper, it's completely uncredible in every way.

    1) The base problem. It's a problem practically made for a scripting language. Most excelled programmers would pick a scripting language over oo, simply because they are the better languages to use for such a problem. So already we have a serious problem, how to get good programmers to code the problem in oo?

    2) Oh, we don't have to worry about that. The oo vs scripting languages had DIFFERENT sources. ALL oo programers were selcted from STUDENTS. Some good, most doubtfully completely inexperienced, all in a controlled setting. A proper study.

    Scripting languages? From a worldwide pool of volunteers. How many students do you think volunteered for this task? Inevitably, the sample set for the scripting languages is probably some of the top programmers in the world.

    Best programmers vs students? Isn't that an easy call.

    3) Collection differences. There was no strict watching of the scripting languages time controls. In other words, they could outright lie about how much time it took. I doubt they'd need to since they were all probably gurus, but still. For that matter, anybody who couldn't complete the task in a few hours probably quit. Did they also count research and design time? I myself like to look at a problem, mull it over for a week, then code it quickly all planed out. Scripting programmers got that luxury, the oo students didn't. They were watched for everything.

    4) Delimiters. For pete's sake, the study counted closing brackets and other delimiters! If that isn't language bias I don't know what is. If you count how delimiters work in one language, you must count how they work in ALL languages. By simply counting the indentations in your code, you now have 36 additional lines of code. I expect similar results for every batch of scripting code.

    ...

    Nothing from the paper is credible at all. And I think it is incredibly sad at how many people I've seen try to draw some fanatical conclusion from it.

    ReplyDelete
  15. (this is going to be a 2-part comment)
    I don't think that anyone has claimed that there weren't issues with the study. In fact, the paper itself points out that Java may not have had a fair shake, given how new it was as a language.

    I'm not sure the problem was made for a scripting language. I think that if one were to try solve it using Bash (also a scripting language), I would imagine that a programmer would have some difficulty. Really, the problem might have been biased towards those languages where certain functional constructs, which is generally the case with languages where multiple programming paradigms are avaialable. I would concede the point that the problem does not lend itself to an OO solution, though in doing so I would point out that in looking at some of the Python solutions I've looked at (I didn't look at the Lua version yet), they lend themselves to a procedural style with a bit of functional glue (mine included).

    Some people may have mulled over that particular problem for a week as you suggest. However, this particular problem was not significantly different in difficulty than an easy/mid-level programming competition problem, so it is possible to outright solve it without having looked at it before in an hour or two. Heck, those who took it upon themselves to work at it very likely have done programming competitions before. But I'll concede the point that it is possible that some people took more time to research than those using Java were given, and that they may have misreported their times.

    Like you say, it's also possible that "some of the top programmers in the world" were using scripting languages, but sadly, not enough data was presented to make a proper judgement about it (a graph of time/lines vs. years experience in the language/years experience). I'll concede the point here as well that years total experience may have been vastly different.

    ReplyDelete
  16. Regarding delimiters; I tried to address this in the other reply, but it would seem that you found fault with it. Certainly the counting of delimiters would have increased the total length of the program. But if one looks at LOC/hour, there doesn't seem to be a significant jump for Java, C, or C++ (all of which have the same delimiter requirements) over the other languages. But even if we ignore LOC as a measurement and just look at times; the quickest to develop Java, C, and C++ programs all took longer to write than the scripting langauge versions. However, since we conceded that the scripting langauges may have cheated in their timings (by not counting research time, or not properly counting their actual work time), and we conceded that the scripting programmers may have been much better (and thus faster), then all of the measurements may be f-ed, and many of the conclusions may be unfounded in reality.


    I find it interesting that you consider the drawing of conclusions from the paper in basically any way as being "fanatical". Fanatical implies a deep-seated emotional tie to the conclusions being drawn, and a willful disgregard for facts and/or data. At worst, any conclusions drawn from the paper are merely conclusions drawn upon poor data and/or methodology for those things where data was being drawn from different pools. Hell, I've conceded every one of your points here as being possible, despite having disagreed on the most part with you over on Reddit (and having received a flame for doing so in a way that wasn't acceptable to you), yet I would probably be the person you directed your "fanatical" claim against. Be careful there, ad-hominem attacks damn near ruin your argument.

    Finally, I'm going to go ahead and disagree with your statement that "Nothing from the paper is credible at all." I agree that it is flawed. I agree that they could have gone to greater lengths to get information about the experience and expertise of those submitting solutions. And they certainly could have worked harder to normalize and prevent people from cheating in one way or another over the timings. But while you may not be able to compare scripting vs. non-scripting languages in this study, there are definitely data points for comparing how well people rate themselves and how well they did against each other in their language, and that both Tcl and C seemed to have been much more effective than was expected.

    ReplyDelete
  17. Actually, I didn't target you as being "fanatical". Nor did I flame you. If you read carefully, you'd be sure to find that all aggresion was targetted strictly towards the paper itself while you were mainly just an audience for it. At one point, I aggressively questioned if you read a previous post, but that was about as far as it got towards anything being directed to you.

    On that, fanatical conclusions are different from people being fanatical. I made that distinction, and no ad-hominem attacks exist in my posts towards anybody... other than the paper itself. And I am free to fully curse the paper up and down the street, ideas don't deserve protection.

    Fanatical conclusions would be any that try to state that it takes half as much code and half the time to do things in a scripting language over an oo language, such as the conclusion the paper posed.

    ReplyDelete
  18. Which the delimiters, should counting lines correctly do something else to other values (or not), so be it. This is just to the line total counts, which seem to be a highlight that many, many people look at (I don't blame anybody, I like short concise code myself of course). Counting the indentations in the scripting langauges nearly doubles the code, it's a very huge difference that suddenly shortens the gap by quite a big deal (since we're dealing with small values, "doubling" doesn't hold so much weight as people inherently assume).

    From the paper the only conclusive information is from the oo group itself, which was taken from another study (I therefore do not count it as credible information the paper created). Statistically and scientifically, nothing else was controlled properly in even the slightest. Sure, as you say, it may be interesting things to see, but none of it can be held with any real comparative validity.

    And don't get the wrong idea, I did enjoy this whole ordeal a great deal... otherwise, I wouldn't have ever replied after my first post.

    ReplyDelete
  19. Here is an implementation in scala:
    https://github.com/tolks/scala-test-drive/blob/master/Matcher.scala .

    ReplyDelete