Slashdot Mirror
ICFP 2003 Programming Contest Results
An anonymous reader writes "The previously reported ICFP Contest has been over for quite some time. The results were announced on August 26, 2003 at the conference in Uppsala, Sweden, yet the contest organizers have yet to publish results. Despite the forgetfulness of the organizers, it is known that this year C++ did well, taking first and second, but not judge's prize. Interestingly, a one-man team consisting of an undergraduate student took first place, followed by a team of highly ranked 'red' TopCoders, with the maintainers of Gwydion Dylan taking judge's prize."
I wonder how many job offers 1st place winner and UT undergrad Andrew Hudson is going to receive... or for you conspiracy folks out there, how many shadowy organizations he'll be "invited" to join.
Who do you get to be an expert to tell you something's not obvious? The least insightful person you can find? -J Roberts
Its nice to see my two favorite languages take the top spots :) Its also pretty nifty that the Gwydion Dylan team got another prize. They got second place a couple of years ago too. Anyway, more people need to check out Dylan. Its a pretty nifty language. It was made by Apple in the early 1990's, by a committe containing a lot of important Lisp people. As a result, its kind of an object-oriented Lisp with a more traditional syntax. Its a very powerful language, but also very fast. It was designed to achieve 90% the performance of C. In practice, the current Gwydion compiler (designed by the same group at CMU that did CMUCL) achieves 50-90% given similar code.
A deep unwavering belief is a sure sign you're missing something...
Congratulations! I've usually steered clear of checking out programming "challenges" because they usually seem to be focused on producing the most unreadable or obscure code to confuse the judges.
While you can learn things from obfuscated code, I think these practical challenges are a lot better for the programming community as a whole.
Finding optimal paths around race tracks and obstacles presents a number of challenges which when solved in multiple totally different ways, helps give us new theories and data which we can use to develop new algorithms and theories for use in the real world.
Can anyone recommend any other programming challenges which focus on developing new algorithms which may be useful in other disciplines?
The only example I can think of is the many "robot" fighting challenges, where you write a program for a robot, and it has to destroy the other robots within the battlefield using its own "wits" and no human input. You might remember PC-ROBOTS from the early 90's if you're a real geek ^v^
Web Hosting Reviews
That's great, but he used SCO code. And he coded all this while listening to illegal MP3's. SCO and the RIAA are filing a joint suit against his grandmother.
That's not entirely fair. There are lots of places where functional programming is the way to go. You'd be surprised at how much stuff you "real programmers" come up with that the FP world did better, more cleanly, and years ago. XML and XSLT come to mind, as well as some of the weirdness they've begotten.
Its really a matter of what kind of programming you are doing. FP is all about making algorithms primary and data secondary. There are some applications where this fits. Take, for example, parsers. In writing a parser, you've only got to deal with a few tokens at a time. Try writing a Scheme parser in imperative vs functional style and tell me which one is shorter and cleaner. However, in some applications, data is the only important thing. Take, for example, an OS kernel. In a kernel, most work boils down to finding highly efficient data structures to track certain state, and writing highly efficient algorithms that mutate that state. Functional programming isn't a good fit for this --- its is often very difficult to express algorithms in a pure-functional manner that have the same asymptotic complexity as their imperitive counterparts.
A deep unwavering belief is a sure sign you're missing something...
I guess it should come as no surprise that the winners should be programming in the decidedly non-functional (no pun intended, really) language C++. There are far more C++ programmers out there than Dylan, Haskell, and ML combined, probably by a couple orders of magnitude.
The prizes were awarded based on answer quality, not performance, which takes away one of C++'s natural advantages over functional languages. Still, I'd like to see a breakdown of entry languages.
from: http://developers.slashdot.org/comments.pl?sid=688 44&cid=6294481
[qoute]
ICFP stands for International Conference on Functional Programming. Neither the /. story nor the contest website make this clear
[/quote]
This contest concerned virtual racing tracks. The winner was the one who submitted the trace which would pilot the car as fast as possible around the track. (See the problem description for more information.)
Thus the judges never ran the program on their computers, and in theory could have judged the contest without even looking at source code. To me this seems a bit unfair because the winner could just be the one with the fastest computer, not the best code. I noticed that the first prize team used 16 dual Xeons.
So did anyone here compete? In practice are the results greatly influenced by how much hardware the contestants had access to?
when you dont even understand the problem.
I read the dylan entry description and didnt even understand the problem. *smacks head*
Bush and Blair ate my sig!
Take a look at the topcoder.com site. It's a periodic competition with short round matches that take a little over an hour to complete 3 challenges. These challenges are similiar to ACM competitions, but quite a bit easier b/c of the time limitations. The rankings are given in points kind of like chess, and the highest ranked coders are color-coded red. Below that is yellow and so on. Thus the best coders are 'Red coders'.
Values taken from the ICFP 2002 webpage and munged with an awk script... not 100% accurate, but close enough.
language entries
java 28
c 24
c++ 22
caml 19
python 15
perl 11
scheme 7
haskell 6
lisp 5
dylan 2
erlang 2
mercury 2
pltbot 2
ruby 2
ada 1
bot! 1
dogs 1
extensions 1
forth 1
icon 1
kylix 1
lspm 1
mhotas 1
pandemonium 1
pps 1
prolog 1
sk 1
smalltalk 1
sml 1
v202 1
Some languages are bogus because of the format of the author's entry, or they used multiple languages.
I've been participating in TC's programming contests for more than a year. There are weekly contests, each of which take only about 90 minutes of your time. There are no prizes given out for the regular contests any more, but I really enjoy being able to get a nice mental workout, and compare myself to some really elite programmers. Most of the top-ranked coders have done extremely well in other prestigious international math and programming contests. And even if you aren't at the level of the top ranked guys (mostly - I think the highest ranked woman is around 50th or so, it would be nice to see more female participation), it can still be fun to work on improving your rating and other statistics such as submission accuracy. The rating system is modelled after the FIDE system for rating chess players.
There are many other reasons to participate. You can also learn a lot by looking at the submissions by the top ranked coders. If you're looking for a job and do reasonably well, there's a good chance one of the many sponsor companies will be interested in hiring you. And perhaps most of all, TC has two big tournaments each year - the open, and the college invitational. These tournaments usually have a total prize purse of $100,000 or more, and pay out $50,000 or more to the winner.
Finally, to answer your question; the TC ratings brackets are split up into different colours. 'Red' is the highest bracket, and includes anyone with a rating higher than 2199. This corresponds to roughly the top 2% of all rated members.
Your comparision is not quite correct.
... who knows? Scheme is that easy to parse, that the questin makes no real sense to me. It only looks more beautyfull if you find scheme beautyfull ... wich I don't :-)
FP is all about making algorithms primary and data secondary.
In FP, functions *ARE* data. The main way to distinguish programming languages, or programming paradigms, is by looking at the question: what are the so called "first class citicens?" (fcc)
In "procedureal" languages the fcc's are *NOT* "procedures", its only called procedural because the main "structuring" feature at that time was the procedure.
Functional languages are best set in relation to oo languages (or oo-like languages like Java and hybrids like C++). The most heavyly used fcc's in oo languages are objects. Thats what you create and what you pass around. E.G.: you create an object and pass it via a call to an algorithm.
In functional languages, the things you create are: functions, not objects, not structs. the things you pass around are functions, you *apply* a funcion on some data.
In both cases you still have data, and still you have algorithms.
What makes fuctional languages "inefficient" in some respects is the fact that they in general do not manipulate "state" of some data, but consider data to be read-only and yield an result instead. Suppose the whole kernal memory is the state of a system, a functional "kernal" would compute a complete new kernal state as a value object.
OTOH: functional languages are inherently multi threaded, as they only read access unchangeable data.
Regarding your - hypotetical - question wether a scheme parser written in scheme would be easyer than a standard C/Pascal parser
BTW: its is often very difficult to express algorithms in a pure-functional manner that have the same asymptotic complexity as their imperitive counterparts
This makes no sense to me, either. The asymptotic complexity of a problem has no relation to the programming paradigm you use -- only to your skills in that paradigm.
angel'o'sphere
Cost free eBook I read (by iBook/Kobo/Amazon/ObookO/Gutenberg etc.): "The Green Odyssey" by Philip Jose Farmer.
A more interesting question might be how many offers have gone to someone who's consistently done well two or three times but never won. By my count, there is at least one such person, looking at the most recent contests.
This year's contest was an interesting problem, and no doubt the winning entry was well done, but there's also an element of brute force involved; look at the hardware Andrew had available. You could make a reasonable argument that this year's winner wasn't decided purely on programming skill, and an even more reasonable argument that doing well in one such contest doesn't say nearly as much as doing well in multiple consecutive ones with different problems to solve.
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
Somethign nobody has mentioned yet (at least with a high rating) is that this is the contest for the International Conference on Functional Programming, and not only that, from the rules page:
First prize: $1000, free conference registration for two student team members, and the satisfaction of hearing the judges proclaim your programming language "the programming tool of choice for discriminating hackers."
Second place language gets: "the consolation of hearing us proclaim your programming language "a fine programming tool for many applications." "
So, I want to make sure this is clear: At the International Conference on Functional Programming, the judges had to get up a proclaim that "C++ is the programming tool of choice for discriminating hackers."
I would've loved to be there. Anybody who was at ICFP care to comment?
In FP, functions *ARE* data.
... who knows?
>>>>>>
"State" probably would be a better word to use here. A procedural language is all about state. You call a procedure, and it modifies some state. If you want to reason about the program, you have to reason about all the state. In a functional program (rather than an imperative program written in a functional language) function application is primary, and state only exists in function parameters and return values. This minimizes the amount of state one has to think about at any one time.
In both cases you still have data, and still you have algorithms.
>>>>>>>
You do, but the relative importance of each is different. The whole idea of OO is that you have objects --- which are containers of state. You have some methods that imperitively modify that state. The central paradigm is the manipulation of state. In function programming, state is secondary to functions. You call a function that evaluates something, and state is only relavent to the functions that receive them as parameters, and return them as results.
What makes fuctional languages "inefficient" in some respects is the fact that they in general do not manipulate "state" of some data, but consider data to be read-only and yield an result instead.
>>>>
Precisely.
Suppose the whole kernal memory is the state of a system, a functional "kernal" would compute a complete new kernal state as a value object.
>>>>>>>>>
Yep. Now the key thing here is that this makes sense in lots of cases. Take this ICFP contest. The idea is to compute the most optimal path through a track. The only thing that matters is the result. FP makes sense here. In comparison, a kernel is all about state. There is no result to compute, and functions are only useful in that they allow manipulation of state. FP makes much less sense in this area.
Regarding your - hypotetical - question wether a scheme parser written in scheme would be easyer than a standard C/Pascal parser
>>>>>>
I think you misunderstand me. Both languages are writing a parser for Scheme. I choose Scheme because its a traditional introduction to writing parsers. Compare writing a parser for Scheme in an imperitive style (in any language) vs writing it in a functional style (for any language). The functional approach is much more clear.
The asymptotic complexity of a problem has no relation to the programming paradigm you use -- only to your skills in that paradigm.
>>>>>>>>>>>
Actually, they do. If you're writing in a purely functional language (Haskell/ Clean) you can't use side-effects. As a result, straightforward implementations of many traditional algorithms become more complex. For example, getting purely functional graph algorithms that are as efficient as traditional imperitive algorithms is an important focus of research in functional programming circles. Now, if you're writing a program where state is just a necessary evil, you can get away with using complex methods (monads, language features like uniqueness types) to deal with that state. If your program is *all* about state (like in a kernel) its probably better to write it in an imperitive style.
A deep unwavering belief is a sure sign you're missing something...
Read this message from a recent thread about the subject on news group comp.lang.functional.
Yes, it is. It allows you to both program close to the hardware and on an abstract level. The focus is on efficiency.
But sometimes you want other goals first. In case of concurrent and fault tolerant programming I would rather use Erlang. For GUIs you can hack it together quicker if you rely on Java and its excellent development tools.
It is rather amusing to see the functional programming zealots beaten in their own competiition.
I don't mind. What I mind is that organizer did not officially publish the results. I sent several emails. No reaction. :(
Perhaps the problem posers got tared and feathered after the conference for posing a problem that was more suited to imperative programming. :-)
Now maybe the FP "movement" will go back to relative obscurity where it belongs, and let the real programmers do their jobs.
I hope you mean the F1rst P0st crowd, otherwise I have to consider you being an ignorant idiot.
Regards,
Marc
I was on the team that won the judge's prize, and whilst you can read our report at the link above, I have to say that for us, the key was the human, not the hardware or the program.
;)
The tracks we did well one were the ones that we were able to hand-drive accurately; the ones we did badly on were the ones where there were simply too many hard turns to make that feasible.
Despite having a whole university lab full of computers we could have hijacked to run our program on, we only used a single computer for the actual optimizing.
Also note that although our automatic optimizer was written in Dylan, the visualizer/racing game program was C++.
If I were going to be controversial I would say that it all just goes to show that humans are better than computers and imperative languages are better than functional ones