Slashdot Mirror
Second Annual ICFP Programming Contest
PsionV writes "The second annual ICFP Programming Contest begins September 2nd. For those of you who didn't participate in this last year, this is a contest where competitors enter programs written in any language which then compete tournament style against each other in a processing intensive task to possibly win money, books, bragging rights, and more. "
Performance was central to last year's contest, for writing a game-playing algorithm. Read the writeups of last year's: the winning team had to do a great deal of damn clever stuff to get that first place. They called on a lot of resources that it would be hard to beat them without.
--
Xenu loves you!
Perl won't win because I'd guess performance will almost certainly be important, and while Perl is easily fast enough for a variety of real-world tasks (where networks and disks become the bottleneck above a particular performance anyway) it's not designed to win contests like this, where the winning entry will almost certainly be CPU-bound in some central computing core.
--
Xenu loves you!
...what last year's problem was? Just curious as to what to expect.
Steve
ftp://rtfm.mit.edu/pub/usenet/comp.lang.functional /
Search engines are your friends, please use them.
Need to re-read/A> it?
:-)
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
Perl won't win unless somebody does something very elegant using it, and I'd be surprised if a more elegant solution did not come from a team using something more appropriate. Style counts in this contest. However, as last year proves, if performance and experience of the task are significant factors, functional languages aren't guaranteed a win either.
BTW, why use an "Anonymous Coward" post and then include your URL? I took a quick look, and you've got a very nice web site. Anybody interested in computational mathematics should have a gander.
Don't feel at a disadvantage.. just because some one is in college doesn't necessarily mean they can code better than you.
If you think you are at a disadvantage, well then, you are, if only because you think you are.
Personnally, I'm going to give it my damndest. I don't know what language I'm going to use yet though.
Does anyone remember the programming contest sponsored by some west-coast university that banned Perl? Apparently, using Perl, a student completely thrashed the competition; therefore, Perl is now a no-no.
There is a link on the main page of The Perl Journal.
Yes, there is more to good programming than performance. However, this is a *contest*. It does not reflect practical job skill. It simply challenges you to solve an arbitrary problem. If you wish to avoid that, do not enter. :-)
dragonhawk@iname.microsoft.com
I do not like Microsoft. Remove them from my email address.
If you were this abusive then, I do not doubt in the least that he skipped right over your mail.
dragonhawk@iname.microsoft.com
I do not like Microsoft. Remove them from my email address.
Perl is very dynamic, in terms of runtime data storage, execution, etc. Thus, it does well at things that change frequently or are largely undefined at design time.
It makes text/string manipulation very easy. A good deal of what computers do is string processing of some kind.
It uses C-like syntax, and C is very familar to a lot of people already.
It integrates with the POSIX (UNIX) environment very well. Perl is ideal for "gluing" separate, unrelated tools together.
Perl is extremely portable. If you are looking to implement something that will run on as many platforms as possible, Perl is a good choice.
There are a lot of already-written Perl "modules" which are freely available. It is often easier to piece together several Perl modules then to solve a problem from scratch. In particular, there are a lot of web- and database-related modules.
Perl is faster then most interpreted langauges, and there are a number of optimizations which can make it even faster for specific cases (caching compiled Perl scripts in the Apache web server being the popular one).
:-)
:-)
This is not to say Perl is the perfect language. Far from it. The lack of imposed structure and data types is not always a Good Thing. Like anything else, you need to evaluate the available tools, and choose the best one for the task at hand.
As far as learning it does, I think a lot of that is the way it is taught. A lot of books ("Programming Perl" especially) introduce a lot of the Perl "tricks" right away. These "tricks" are useful in contests, one-liners, and write-only code, but for professional projects, they are to be avoided. Again, the lack of imposed structure is not always a Good Thing.
All IMHO, YMMV, etc.
dragonhawk@iname.microsoft.com
I do not like Microsoft. Remove them from my email address.
Okay, I have to ask, and this isn't a flame, but what do people see in Scheme? Perl was a little obtuse initially, but not a difficult language to learn. Scheme just makes my brain hurt -- the syntax is ++ugly and I just can't seem to wrap my head around it.
I wonder if this year's contest will be on another 4 processor machine. I think something like that makes it a bit unfair to those of us running little budget Linux boxes. I've never programmed for such a beautiful set of hardware and even if I learned something like Cilk (which looks rather nice and simple), I'd have to find somebody w/ a bigassed powerful machine to test any of the code on. I suppose it's time to recruit from PLUG (Philadelphia Linux User's Group).
hmmm, I wonder if a team of 50 would be too big to effectively manage...
When you do head of to school, you'll probably end up taking a class using a book called "Introduction to Algorithms" written by Cormen, Leiserson an Rivest. Just so you understand where I'm going, Leiserson was on the team ("Cilk Pousse") that won the contest last year.
I'd say that you're not the only one with a disadvantage
-NooM
Re: only allow functional languages.
It's probably still better this way since it gives a good idea of where optimizing functional compilers stand against "the competition." Although the Cilk team one, that second place spot held by a team which used OCaml is a pretty strong statement for the progress of recent compilers for functional languages.
If other languages were not allowed, someone could easily say "well, I could have written something far better in C." Considering that an OCaml entry beat out all entries written in "pure C", and was only second to a multithreaded version of the language, the outcome is more relevant.
-NooM
Isn't PERL the Practical Extraction and Report Language? :-)
Yes... it's also the Pathologically Eclectic Rubbish Lister, now you know why SlashDot is written in Perl
My own experience with perl is that it is one of the least restrictive languages I know of. This means that its easy to throw something togethor fast, but I avoid it like the plague simply because my code always looks like it was run over by a lawnmower when I'm through with it. But then what do I know, I'm still in love with scheme ;).
-Jon Schaab
I don't believe that any of last year's entries were straight out pre-written. Even the guys who had code written to play games like chess had to make non-trivial changes to get their programs to play Pousse well enough to be competitive.
:)
For this year's contest, we have again tried our best to come up with a problem that won't give some teams a competitive advantage over others.
Hopefully everyone will be equally challenged
I just hope they can seperate student submissions some how. I feel at a big disadvantage having not gone to college yet and taking Comp Sci classes.
This is a really cool idea.. i didnt know of the competition last year (had i, i would have registered then too :) )
i look forward to getting totally thromped at the hands of some actually competant coders, but eh, whachagonnado
tchort
Am I the only programmer out there who is secretly embarassed by each and every line he writes? -----
The impression that Perl produces worse code than other languages usually comes from the hurdle of being able to visually guage regular expressions and grasp context-sensitivity. I try to code with these two hurdles in mind (both for abuse in contests and for maintainability at work), and things work out quite well. But, I've learned to think in Perl, so even "bad" Perl is more readable to me than "good" C++ (which I program in, but do not yet think in).
My favorite obfuscated contest entry is still my C/LISP combo which printed "Hello, world" with only one copy of the string in the code. It would run under EMACS LISP or compile as C code. Fun stuff, that!
wonder how long a basic program would last? I'm betting that such an entry (I'm halfway considering entering one) would be instantly disqualified just on general principle =)
-Lx?
This is one of the better contests that I have seen. It not only awards for correctness, but creativity.
Indeed... I agree. If only I could program, heck, I'd enter the thing!
All I can say is, "Carry on! Carry on!"
Insert mind here.
taken from the page about last year's competition:
/. will up that number this year.
>Here are some broad statistics for the primary language used by the various teams:
> 24 C dialects: C, C++, Cilk
> 12 ML variants (SML/NJ, Moscow ML, OCaml, >OLabel)
> 3 Scheme
> 3 Haskell
> 3 Perl
> 1 J
> 1 Mercury
> 1 Icon
looks like there was barely enough perl representation to give it a good chance. but doesnt that also say something about it? perl really isnt designed for tasks like this.
im sure ill be using c, but if i get to the last 2 hours and dont have anythign to submit yet, then ill just write a simple little perl script to get the job done.
also, apparently there were only 48 entries last year. maybe getting some exposure here on
with all that being said, what then is the advantage of a functional language? it would appear to me (in my staggering ignorance) that they are primarily usefull in hiding the programmer from some of the gory details of the programming by making it higher level.
/. discussions an excellent place to learn.
while it is obvious that this speeds up development time, does it really improve execution speed over a well written algorithm? it seems to me that maybe one line of haskell code might be able to do what 10 lines of C code can (maybe even in a loop or recursively), but in order to get the job done, isnt the haskell gonna have to do just as much underneath?
also, (and please flame me if im wrong) but dont i remember being told in a programming class that 1.) anything that can be done recursively can be done iteratively, and 2.) that recursion (while often easier to code) is usually not the most efficent solution. ? im still very confused. can anyone help me on why/how functional programs would be faster? (or maybe im misinterpreting the idea of why they were suggested to be used in this contest)
dont think that im trying to put functional programming down, im still learning what it is. i just want to understand more, and i find these
However nice it may be to think of this theoretically, what USE is it? Why would I ever NOT want to use assignment when it is applicable? "Curry"ing looks like it can be done in any language (FOO = "bar"; g(x) { f(x, FOO) }; /why/ would we ever want to do such a thing (besides as an academic thought problem)?
"Functional" programming looks like a subset of object-oriented programming, in which the only objects are functions...what use is that? I can't help but thinking that this is shooting yourself in the foot. If we banished all circular objects from the RL world, it probably would lead to very interesting solutions and phenomenon, but
It's 10 PM. Do you know if you're un-American?
Isn't PERL the Practical Extraction and Report Language?
I'd imagine it's good for exactly what it is used for...text manipulation, database/network interaction, data extraction, etc.
It's 10 PM. Do you know if you're un-American?
Crudely put: functional programming is based on the idea that any computation can be represented as a function, according to the standard definition of a "general recursive function" from algebra.
Mathematically, a function takes an input and maps it to an output -- given the same input, it will always give the same output. There is no hidden state: the black box always works the same way. Things like random number generators (which produce a different result each time called) aren't true functions.
Functional programming takes that idea and uses it to program. Usually, there is no "state" at all, enforced by the lack of assignment. Variable binding usually takes place through "let" constructs (as in "let x=... in (expression)") or through function calls.
Since iteration tends to be though of as inherently stateful, functional programming tends to lack it -- everything is done using recursion.
So if you use C without using assignment or loops, you can write C in a functional style. An example might be:
int strcmp(char *a, char *b)
/* returns 0 if string a is lexigraphically greater
* than b
*/
{
if ((*a == 0) && (*b == 0)) return 0;
else return *a - *b || strcmp(a+1,b+1);
}
Since this is unnatural for C, functional programming languages have been written to support the programming paradigm. Examples include ML, Haskel, and Lisp. Purists can argue about how functional they are, but compared to C, they are.
Functional programming languages tend to be rich in the ability to arbitrarily construct complex types as needed, and treat functions as first-class objects (you can create them on the fly, pass them as arguments, put them in lists, tuples, records, or other structured types).
This freedom to use functions leads to some very different programming techniques. For instance, one common construct is called a "curry" (after the mathematician who described it), which converts a function of N variables into a function of N-1 variables. For instance, if f(x,y) is a function, and g=curry(f,Y), then g(x)=g(x,Y)). One way of thinking of this is that if you think of f as a two-dimensional array, then curry(f,Y) is a one-dimensional slice of the array.
Or, you could do something like this:
(define (addXto x) (curry add x)) ==> addXto
(define g (addXto 5)) ==> g
(g 4) ==> 9
(g 45) ==> 50
These examples of currying are simple, but it can be a powerful technique.
This is one of the better contests that I have seen. It not only awards for correctness, but creativity. If you get into a small team with some creative peolple you could win and not even be the fastest. Also, contests like this help promote CS amoung peolple who normally do not think of themselves as programmers.
---- aut viam inveniam aut faciam
(FOO = "bar"; g(x) { f(x, FOO) };
This does not work at all when you want
a function to return a partially applied
function.
The problem with your "encoding" is that it
is possible to create only a fixed (at compile
time) number of partial applications. Whereas
you may want to partially apply g to an unbound
number of values.
But functionnal languages *can* be encoded in
"non-functionnal" ones. You just have a
hard time handling environments by yourself
when you do so.
Well someone has to answer this, right?
Functional languages have an advantage in correctness: Its my experience that they're easier to prove correct. I don't know if a haskell algorithm is faster than the c++ one, its probably all in the compiler, and most of the ML compilers I've worked with seem quite a bit younger than c compilers, so they probably haven't been tweeked as much, and consequently, they're not necessarily faster. (But if you think speed is everything, than you're missing the point, I guess)...
I think the reason they're in the contest is because its sponsored by a functional programming group (ICFP).
I don't imagine there's much difference in speed in a good tail recursive function versus iterative.
Someone told me (right before I took a class in ML) that if your ML program compiled, and you knew a little of what you were doing, it was going to be right. Forget all the bug testing and memory leaks, not an issue. Well, I failed that class... but anyway, I still like functional programming, and recursion and induction seem pretty cool.
Troll Like a Champion Today
there are a lot of ways to optimize a program...
are they going for speed? size?
if they are going for speed, it is certain that
perl wont win- its interpreted fergodsake...
or for size...
so why do people use perl anyway?
its certainly not an EASY language
to learn...
so all you perl fanatics, whats it good
for?
"some people have too much freedom" - george dubya bush, facist, err republican presidential hopeful and domain name squ
javascript sounds like a great language with which to submit a gag program. Put it in a little webpage and everything.
"There is nothing more intimidating than an idiotic smile worn by a manifest non-idiot." --unknown
"Obfuscated Perl"? Isn't that redundant?
Yeah, I know... it's possible to write good Perl... it's way too easy to write bad Perl, though. You should see the mess I inherited at work...
So you mean nobody, prior to this contest, had implemented a program to play Pousse? I suppose it's an obscure enough game that it would be possible, I just would've expected nearly every game to have a least some sort of program playing it by now...
However, it seems the contest ran quite well, so I'll stop complaining =) Good luck on this year's.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
I have a strange feeling that there will be somebody out there that has some pre-written code for whatever the challenge will be, that will only need slight modification. For example, last year's contest was playing pousse, and I'd be surprised if no pousse implementations had ever been written before. That'd leave the rest of us at a slight disadvantage.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Last year a program had to respond within 30 seconds. If your algorithm is fast enough to respond easily within a time limit then performance is not much of an issue. Performance does matter if you and your program have to make an effort to respond within the time limit.
Hmmm... I don't like the sound of that.
Geeky modern art T-shirts