Slashdot Mirror
ICFP 2001 Contest Results
Phil Bewig writes: "Results of the 2001
ICFP
Programming Contest (previously mentioned at SlashDot
here and
here) have been
announced.
First place is to a program in
Haskell,
second place is to a program in
Dylan,
and the judges' prize is to a
program
in Erlang.
The judges also named
third place
(ocaml)
and fourth place (C) entries that were not awarded prizes.
ICFP Programming Contest pages for prior years are available:
2000,
1999, and
1998."
For those who don't want to click on all the links, the task was to produce a program that would optimise a HTML-like markup language called SML/NG. The programs had to remove excess whitespace, redundant and overlapping tags, and perform other simplifications.
It's hard to be religious when certain people are never incinerated by bolts of lightning.
I've always wanted to get time to sit down and play with languages like Haskell, but never seem to get around to it. I think part of my hesitance (i.e. finding other things to do), is that I'm not confident that it's a commercially useful language.
The same goes for Erlang as well, which just seems to be an Ericsson R&D effort. In fact the only application I've seen written in the outside world in Erlang was Eddie and even that was an in-house Ericsson creation.
But then, the increase in languages has always confused me. When I was browsing through a bookstore one day I was amazed to see a book entitled 'REBOL for Dummies' - who, in their right mind, uses REBOL????
Before everyone runs out and says "Haskell is the best programming language", as seemed to happen with things like OCaml in the past, please bear in mind that the ICFP tasks are somewhat biased toward functional languages. It is principally a contest for functional programmers, after all. This year's task, in particular, seems to be particularly suited to the built-in features of many such languages -- more so, perhaps, than things like the ray tracer task in the past.
It's to the credit of the coders that they produce such impressive results so fast, and it'll certainly be interesting reading when the full details are out. But let's not try to read too much into it this time, OK? Haskell is not suddenly a million times better than OCaml was last year, just because OCaml doesn't feature in the top list this time around. Functional programming still may not be the best approach for writing low-level instrument control code or operating systems.
So, before the millions of posts start arriving, I make a small plea: don't treat this as an objective (no pun intended) programming language comparison!
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
More about the Dylan Hackers' entry; they use (and maintain) Gwydion Dylan.
Functional Objects, Inc. sells Functional Developer, their Dylan implementation, for Windows and soon for Linux.
Whilst looking through the winner's personal info, I came across this page which has quite a photo of ... something bloody attached to his arm ... and a god of vampires link.
It's often said that genius and eccentricity often go hand-in-hand, I'm just not sure what's in the photo. Dare I say it's a vampire bat feeding off the 2001 ICFP Contest Winner's arm? Anyone else know?
Someone has got to get an interview with this guy for slashdot!
Treatment, not tyranny. End the drug war and free our American POWs.
See my user info for links.
I believe that some of the URL resolvers in Slashcode are Turing complete, and by typing in the correct URL you can make Slashcode perform arbitrary calculations (albeit in a very inefficient manner). I'd love to see an entry that worked by taking advantage of that!
Even Slashdot wants to hide some things
Just found this interesting analysis by the captain of the highly-placed Dylan Hackers entry. He uses his own sensible-sounding criteria for rating the entries, obviously somewhat different from the real judges', but not so far off in final results. It makes for an interesting alternative perspective.
BTW, after I earlier posted that this shouldn't be taken as a fair comparison between programming languages, this information shows exactly why. The top entry is written in C++, and didn't figure in the "big five" mentioned by the judges of the real contest. In other words, the languages coming out on top change significantly, based on two different, but both reasonable, methods of ranking the entries.
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
"and the judges' prize is to a program in Erlang."
what does that mean?
For example, Dylan's syntax is based on whitespace; so identifiers are permitted to contain most characters except whitespace and punctuation. (The downside, of course, is that you must type spaces around most operators. However, any character can be escaped with \, and you can even reuse reserved words this way.)
This flexibility gives you a lot of freedom. For example, the official convention uses dashes to separate words; methods/functions that return a boolean value ends with ?; globals are surrounded by asterisks; and types are surrounded by angle brackets. So a method may be named is-camera-on?(), a global may named *game-clients*, and a class may be named <socket-server>.
Dylan provides other small, but distinctive, features. For example, it supports per-file metadata: Any source file can start with an RFC 822-like header, which you'd typically use for version, author, copyright, license and documentation data.
Of course, I haven't even started on the language features. Dylan has an interesting, elegant object model. It has explicit support for "slots", analogous to Delphi's class properties: data members whose access is delegated to accessor methods. It has explicit support for singletons and generic programming. It has multiple inheritance. It has garbage collection, type safety, a modern module system, etc. Dylan is usually compiled, but can be interpreted. Its extremely dynamic nature means that method dispatching and "smart linking" can be a complex affair; this is a weak link, and at least for Functional Developer (formerly Harlequin Dylan), program efficiency is dependent on the compiler being able to do "whole program" analysis.
However, I would hesitate to call it a functional programming language. According to the Dylan reference manual, "Dylan is a general-purpose high-level programming language, designed for use both in application and systems programming". It is a structured programming language belonging to the same paradigm as C++ and Java. There are clear signs of having been influenced by functional programming, though.
The name "Dylan" does not come from Bob or Thomas, but from the phrase "dynamic language".
For more information, I recommend the Functional Objects site. They provide a Windows/Linux-based IDE and compiler for Dylan. The "Basic Edition" is free as in beer.
> a strong object-oriented type system which
> ensures that the vast majority of coding errors
> result in a type error (although it can take a
> little while to get used to Haskell's type system);
Yes, Haskell has a strong type system that finds many errors at compile-time. This is IMHO one of THE arguments why YOU(yes you) should use Haskell. It will make your programs better. But the type-system is not object-oriented. It uses type-classes to provide a way for overloading in the type-system. See this paper, for example.
BTW. Did you know that, because of this type system, Haskell programs cannot segfault.?
There are always plenty of people on Slashdot
willing to point out that there is no best language, only the best language for certain use. While there is certainly truth in that, it's usualy used as a poor excuse to excuse using perl or some other monstrosity, and the people saying it would have no idea whether Haskell or Scheme or Eiffel or whatever would be much better than their use of C or perl on the theory "I think this is the best language for this use", when likely it is not at all.
It is completely alien to those people who are used to C/Perl/Java/Basic type languages, it is obsessively recursive (which scares a lot of people).
It also by default uses whitespace to determine nesting, and HUGS (the compiler we use) gives error messages that look like garbage: complaining about unexpected brackets when there are no brackets in the whole program (the brackets are implied by the whitespace).
The combination of an eccentric compiler and the fact that Functional languages are 'alien' makes most of us hate Haskel and most 'Hackers' would rather shoot themselves or use Visual Basic than use Haskel.
BUT if you can cope with recursion (which you should) and are willing to forget a lot about 'normal languages' and learn functional languages, (HUGS is fine too once you get used to it and is free so its unfair to complain), then Haskel can produce beautiful simple concise programs and 5% of the course love it (those that know how to use it - you might even call them software engineers [not hackers]).
-I should be working but I doubt my license is valid.
Reading through some of the example code on the Dylan team's page, much of the style seems similar to Scheme, but without the paren notation. I find the paren notation easier to scan, but then I use Scheme a lot and no Dylan. Can someone who works actively with both Dylan and Scheme make a comparison?
I understand Scheme was a big influence in the design of Dylan.
I look ... and wonder how the judging criteria worked ... since I would have to agree with the guy from the dylan team about who should have won. Based on the results I can see that is...
Admitedly the algorithm of the winning team sounds kinda cool...
*wont possibly consider anti-c++ bias...*
Sigs are for wimps. I am proud to be one.
"That's a lovely function you've got there, Mrs. Cleaver."
-Eddie 'Lambda' Haskell
m00.
This is the program that got the best results (if I can read the score table). Where is it?
Yes, Dylan was very much influenced by Scheme, and a number of very big wheel Lisp-hackers (like Moon) were involved in its design.
You can map Dylan's constructs pretty much one-for-one to Scheme. The big difference between Scheme and Dylan is that Dylan is completely OO in design, and has an object system that is reminiscent of CLOS or Cecil's -- multimethods and generic functions. Perhaps as a result, Dylan also has a vastly larger standard library than Scheme does, though the SRFI process will with luck eventually alleviate this somewhat for Scheme.
Dylan also limits continuations compared to Scheme, so that they have a dynamic lifetime and can be only called once, so that code can be compiled to use a stack efficiently. (You can't code coroutines with Dylan's block() statement, so there's a separate threading standard to cope with this.) Like Scheme, Dylan also has a hygienic macro system, and this is used to implement most of Dylan's control structures, like loops, case, and select statements.
Every year I see this contest and every year the results are impressive. But I still rarely, rarely see any open source programs of significance written in OCaml, Haskell, etc. Okay, there's a really nice webserver written in Erlang ("eddie"). But with all the frothing about how great these languages are, you'd expect to see the next great program written using one.
it actually favored intelligence, and clever algorithms. Maybe such algorithms can be better be expressed in functional languages ?
Maybe clever programmers tend to use more challenging, less commonly used languages. The programmer may be more important than the language.
(Myself, my favorites are, in order, Scheme and Haskell.)
..Who don't know what ICFP is (I didn't) and the site's a bit slashdotted, the google cache is Here.
Editors, would it hurt to expand uncommon acronyms in stories?
Send lawyers, guns, and money!
Being slightly more objective, I agree that for a 0% bug rate, C and C++ are not the solution
This reminds me of how things were in tech support. Everybody thought USRobotics modems were bad. So did I until I heard that USR had a *huge* chunk of the modem market. Then I realized that the only reason we dealt with so many crappy USR modems is simply that there were so *many* USR modems.
Same thing applies here. There is a lot of crappy C and C++ because there is so much of it. Let Haskell, OCaml or any of these functional languages become dominant in the industry, and we will see just how crappy they can be.
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
* Ericssons AXD301 ATM switching system
http://www.ericsson.com/review/1998_01/
* Alteon WebSystems iSD (Integrated Service Director) SSL Accelerator
see review at:
http://www.networkcomputing.com/1212/1212f46.html
Enough?
/RogerL
That's true of the 99 competition, and maybe to a lesser degree this last competition. But they ray-tracer really was not geared towards functional languages at all. The language was totally trivial to parse and easy to evaluate; the real test was to see how much you could code without making mistakes in just the one weekend.
Almost all of the C/C++ entries were disqualified for crashing or being buggy!
At least for last year's task, I believe this was a fair language comparison in terms of developer productivity.
(Of course, I am biased. 9th place, woo hoo!)
9th place baby!!!
SML rulez!!!!!@!!!
BTW. Did you know that, because of this type system, Haskell programs cannot segfault.?
Perl, Python, TCL, Scheme, REBOL, and Lisp can't "segfault" either, but they don't have such a type system. Haskell is a fine language, but much of its advocacy is misguided (as is much Linux advocacy).
> Perl, Python, TCL, Scheme, REBOL, and Lisp can't > "segfault" either
You missed the point. Obviously, C or C++ cannot segfault when run in an interpreter.
The post explains the reasons behind the dislike of Haskell amongst most students and other programmers. You cannot dispute that Haskell and functional languages are wierd to most people, who've been brought up on 'normal' languages (ranging from Assembler to C/Java/Perl/etc). Recursion is your friend, but unfortunately it scares a lot of people (who should neither be called discerning Hackers nor Software engineers). Any quirks with the compiler will only add to the state of FUD when trying to introduce new people to Functional Programing.
Haskell in the right hands is obviously effective but right now it's still alien to most people. This is a pity because Haskell is beautiful and useful, but it is still true.
*It's worth noting that the Haskell programs are always a fraction of the size of the Java, look very pretty and tend to work as required.
-Don't flame the messenger, flame the content.
You missed the point. Obviously, C or C++ cannot segfault when run in an interpreter.
And compiled Lisp and Scheme can't segfault either. What's your point?
You are right in that the type classes provide a form of overloading. However, the argument that Haskell is not object-oriented is a sticky one at best. The most fundamental problem is that OO does not have a universal definition. Even languages such as Progress and Perl claim to be OO, when they are not OO by any reasonable definition.
Haskell provides all the features usually included in definitions of OO, however, it doesn't lump all the functionality together in a single megaconstruct as most traditional OO languages do. Instead, it breaks up the functionality among many relatively simple language constructs. These constructs can be used together so that your code is virtually identical to object-oriented languages. However, you could also use the features together in different ways to come up with something completely different.
The definition for OO that is most commonly accepted as reasonable is that objects are a language feature that provide encapsulation, inheritance, and some kind of polymorphism.
Encapsulation is performed by Haskell's module system. Type classes don't really have that much to do with encapsulation.
Essentially, type classes enhances Haskell's polymorphism, which is a feature claimed by OO programming. Type classes compliment the parametric polymorphism already inherent in haskell's type system with a controlled variant of ad-hoc polymorphism. Essentially, it enhances Haskell's polymorphism, which is a feature claimed by OO programming.
Type classes also provide much more flexible form of interface inheritance through class extensions. For example, multiple inheritance is clean and not at all problematic in Haskell. Furthermore, multiparameter type classes provide functionality that is very difficult to describe in OO jargon. (Roughly, think multiple objects that together instanstiate a class, and if you change just one object, they together instanstiate an entirely different class.)
Type classes provide a limited form of implementation inheritance through the generality of Haskells "instance" construct.
Sometimes OO definitions require a form of dynamic dispatch, where the particular function to actually use is selected at run-time. This can be accomplished by using existential typing, which is a language extension offered by Hugs, GHC, and HBC.
Sometimes OO definitions require that objects must have mutable state. This is can be accomplished, among other things, by the use of monads.
Monads are commonly misunderstood by those that haven't used them. One of the most common misconceptions is that monads are a language feature. Rather they are a specific programming idiom that can be used in any language that provides higher-order functions, such as Lisp or SML. Haskell simply adopted this idiom as a standard way to do a variety of things, including I/O. Haskell eases the use of monads by the addition of the "do-notation". Other than this optional alternative syntax to writing monads, there is nothing special about them in the language itself.
Although Python, Scheme, Lisp, and Erlang do not perform static (compile-time) type checking, they perform dynamic (run-time) type checking that is equally stringent. This is why these languages can be considered almost as reliable as statically typed ones such as Haskell and ML. A program written in such languages do not crash; or they crash at the very first sign of trouble, which is the next best thing.
The same cannot be said about Perl, TCL, and C. They intentionally allow you to confuse strings with numbers with window handles with file descriptors with pointers. This is just asking for confusions and mistakes that are hard to trouble-shoot. A program written in such languages usually goes nuts and corrupts data without crashing; or by the time it crashes, it is no longer possible to identify the problem by looking at core dumps. This happens to many a student: the C program segfaults at malloc, and it is because of a memory corruption in a function that has returned several hundred steps ago. And this is just a 200-line toy program for a school assignment.
My take at the issue is not whether the program crashes or not, but how much damage it has done before it crashes and how quickly I can identify the problem. It is from the perspectives of damage control and diagnosis.
I personally prefer static typing, though I accept dynamic typing as equally useful and possibly easier to work with. But I reject weak typing. If your Perl script doesn't crash, you'd better pray that it isn't pulling your leg.
I have recently put a page up about our entry which came fourth (and now equal third due to the judges being nice...) written in C. Find more about it here
contest.
More than one entry implemented dynamic programming: Rokicki's,
Sawicki's, and our winning entry. (We call dynamic programming "CYK
parsing", but as we explain in section 3.2 of our write-up, they are
the same thing.) Dynamic programming by itself is not enough, because
the algorithm takes time cubic in the input length, and with large
inputs it takes too long. Some "end-game" approximation technique is
therefore necessary. Rokicki didn't finish in time with his coding,
but Sawicki did put together dynamic programming with a simple
end-game technique. His entry placed 15th in your unofficial rankings
and did not officially qualify for the final round.
What made the difference between our entry and Sawicki's entry seems
to be the approximation techniques our entries used. Our technique
simplifies of techniques known to work in the parsing literature. We
couldn't have thought of what we implemented without the help of this
literature.
The bottom line: The programming language may matter (the essence of
dynamic programming is 10 lines of beautiful Haskell), but what is
more important is understanding the problem, relating it to existing
research, and taking advantage of previous work.