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."
But the uniformity of the syntax of lisp (actually VERY traditional, going back to 1958...) is one of its major advantages.
:-)
Dylan, a bit like Python, is a "gateway" language. People start using it, and slowly come to realise what makes lisp great. Then they make the leap to Lisp. Handy
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...
Funnily enough, I came away with the impression that C++ had an advantage this year, since the removal of the requirement that the judges run the program themselves meant, in theory, that a brute-force approach combined with a supercomputer could have beaten the most delicately honed algorithm imaginable. That the winner was not an example of this surprised me.
Ah well. Those of us with functional inclinations can console ourselves with the knowledge that at least the winning program didn't use COBOL...
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!
There are two advantages with the Lisp syntax: it is easy to write parsers for, and is easy to write powerful macros that make the syntax extensible.
Now we don't have 1958 anymore, and writing parsers for high-level languages is no black art anymore. A proper syntax makes code easier to read and to maintain, and laziness on the side of the compiler writer cannot be held up as an argument to make usage of the language harder to the user.
And Dylan introduces a macro system that works much like the Lisp macros used to, only with an Algol-like syntax. Basically, the macros work on the parse tree instead of the string representation, and thus can be used to extend the syntax of the language, If you want, you can think about it as adding productions to the grammar.
Dylan definitely is a dialect of Lisp, with another syntax. And it has been cleaned up in a lot of places, too (OO from the ground up, for instance).
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.
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...
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