Slashdot Mirror
ICFP 2001 Task
David Mentré writes: "The ICFP 2001 programming contest TASK is now available. The objective is to write an optimizer (aka compressor) for an HTML-like language. It must work for arbitrarily big inputs and in a limited wall-clock time. Can you guess what will be the winning language? ;)" We already announced the contest, but now that the task is available, it might be fun to look at. So what will the contestants come up with? Anyone think perl might be the language of choice? :)
Just to point out, there's a good functional XML parser/processor available for Scheme - as everyone here knows, XML is just a verbose way of writing certain Lisp S-Expressions. This software will allow you to load any XML in as a lump of Scheme, and it can then be treated like any other Scheme data structure you've been taught how to process in CS 101. See www.lh.com/~oleg/ftp/Scheme/xml.html
for example: <WEIGHT unit="pound">
<NET certified="certified"> 67 </NET>
<GROSS> 95 </GROSS>
</WEIGHT>
becomes:
(WEIGHT (@ (unit "pound"))
(NET (@ (certified)) 67)
(GROSS 95)
)
Choice of masters is not freedom.
Java?
Anyone? Ok, I'm actually serious, don't mod me up +1 Funny.
No.
XML is not a programming language, it's a markup language. You can't use it to compute anything. XSL-FO is not a programming language, it's a page description language. You can't use it to compute anything. XSL-T is a programming language, and a very elegant one, but it isn't (IMHO) well suited to this task, and certainly would not produce a compact output.
I'm old enough to remember when discussions on Slashdot were well informed.
I predict that the winner will probably be O'Caml, and for one reason only: it will beat the time limit. Moreover, this will have little to do with the speed of the O'Caml implementation.
Your program has to complete within a given wall time (not CPU time). This is supplied as a command-line argument and environment variable. The winner will be the tool which can stop computing before the time is up and produce the output. The winning program will be one that iteratively improves the input string, but is monitored by another thread which stops the optimiser thread when the time is almost up, then grabs the best solution so far and performs the output.
O'Caml just happens to have good built-in primitives to write this kind of "interrupt the thread when the time is up and let me know what you did" computation.
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
Thats because all of the good C engineers have jobs and are too busy to fsck around with stupid games like this. Caml programmers bored from a lack of any employment in the real world had no problem finding the time to dedicate to this problem.
Someone you trust is one of us.
You're missing the fact that the tags have to be paired. Ensuring the tags are paired isn't a problem, but ensuring the tags are paired optimally is where the difficulty arises.
:). I'm writing my entry in Haskell and I have a fairly decent optimizer except for these cases and it's currently a 110 line Haskell program.
Consider: <B><I>Hello</I></B>World&l t;B><I>Foo</I></B>
Should be: <B><I>Hello<PL>World</PL>F oo</I></B>
But how do you know if it's more optimal to go with a PL tag vs closing the B and I? You would need the array to go further down and see that you will need the B and I again so you don't bother to close it.
This is the problem I'm running in to now
--BEGIN SIG BLOCK--
I'd rather be trolling for goatse.cx.
Things you think are in the Constitution, but are not.
If you need me, I'll be doing a preliminary victory dance over in the QBASIC camp...
Anyhow, speed will be the deciding factor on this one.
I'll be pretty surprised if speed ends up being the deciding factor, at least for the first few places. This is a pretty complex problems with many ways you can optimize certain aspects, like overlap inversion, color nestsing, redundency elimination, etc. But to really minimize the size of the output file (the most important factor after qualification and validity) contestants have to come up with a great balance of optimizing all of those factors together. Because it of time constraints, contestants cannot effectively run multiple attempts across all optimizations to find the single smallest output (this would run in exponential time, so small inputs might work, but large ones would run for days). The winners will likely have the best algorithms for optimizing the output in some kind of polynomial time, regardless of the language used.
ie, it doesn't have to be a functional programming language.
As far as time limits are concerned, may I suggest Mercury. It's a functional/logical hybrid that's somewhat unorthodox for VHLLs in that it's a compile-only rather than interpreted-only or interpreted/compiled. Its designers claim that it can get similar performances to programs of similar functionality written in C, alhtough I haven't seen any benching, and I'll believe it when I see it. :)
Anyone think perl might be the language of choice? :)
No, because Perl isn't a functional language. *sigh*.
Did anyone else spot the similarity between the name of their mark-up language and another language?
No, your children are not the special ones. Nor are your pets.
- PLClub submitted two separate entries using OCaml, either of which would have won the contest.
- Camls 'R Us took second place.
- Galois Connections took third with their Haskell entry.
- The Merry Mercurians took fourth with their Mercury entry.
1999:- Camls 'R Us mopped up the competition with their 3585-line OCaml entry
- The 1250-line Haskell Entry that took 2nd place was written in a mere 24 hours.
1998:Thanks to relentless innovation from Redmond, the choice is clear. A team working in Visual Basic will clearly triumph.
Art At Home
You mean this story is thin, neat, and dresses well?
I think I'll use Scheme
Casual Games/Downloads
Everyone is welcome.
print "
<HTML>
<HEAD>
<TITLE>404 Not Found</TITLE>
</HEAD>
<BODY>
<H1>Not Found</H1>
The requested URL was not found on this server.
</BODY>
</HTML>";
"Your superior intellect is no match for our puny weapons!"