Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Programming IT Technology

ICFP 2001 Contest Results 101

Posted by michael from the copious-free-time dept.
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."
This discussion has been archived. No new comments can be posted.

ICFP 2001 Contest Results More

ICFP 2001 Contest Results

Comments Filter:

  • The task (Score:4, Informative)

    by damiam ( 409504 ) on Friday September 07, 2001 @05:41AM (#2262463)
    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.

  • Haskell, eh? (Score:3, Interesting)

    by PRobinson ( 471021 ) on Friday September 07, 2001 @05:42AM (#2262464)
    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 [sourceforge.net] 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????

    • Re:Haskell, eh? (Score:1, Interesting)

      by Anonymous Coward
      Erlang is used extensively throughout ericsson - it's not just R&D, it's "mission critical".

      Lots of people use rebol - it's actually quite a nice language, and the network-transparent desktop environment thing is cool, though it's probably destined to be a proof-of-concept footnote to mainstream history.

    • Re:Haskell, eh? (Score:5, Informative)

      by cthugha ( 185672 ) on Friday September 07, 2001 @06:05AM (#2262492)

      I really recommend that you do sit down with Haskell. IMO, the judges were correct in naming it language of choice for "discriminating hackers". It has:

      • clean, simple syntax (parentheses are used only to override default infix operator precedences, nothing more), including excellent list construction and comprehension;
      • 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);
      • lazy evaluation of expressions: only the parts of your program needed to produce a result are evaluated, which allows you to write programs that left to run would produce infinite computations (e.g. programs to calculate the Fibonnaci series or the sequence of primes) and only evaluate them for the subset of data you need; and
      • partially applied (or curried) functions: you really need to see these in practice, particularly in conjunction with the standard list-processing functions (e.g. map, scan, and fold) to understand their true power (the ability to create lists of partially-applied functions is very cool, although I have no idea how such things might be used).

      With regard to your qualms about lack of use, I understand Ericsson have created their own functional language for in-house use (the name escapes me). Arguably, since we've all got oodles of processor power to spare, there's no reason not to use functional languages in the general applications sector, given their greater reliability.

      If you want more info on Haskell, check out the official website [haskell.org] (especially the Ode to Haskell on the humour page, which should give you an idea as to the language's feature set ;)). There you will find interpreters, compilers and other tools for a variety of platforms (incl. Windows and Linux) as well as complete documentation.

      • With regard to your qualms about lack of use, I understand Ericsson have created their own functional language for in-house use(the name escapes me).


        Err, that would'nt be erlang by any chance
      • > 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 [bell-labs.com], for example.

        BTW. Did you know that, because of this type system, Haskell programs cannot segfault.?
        • 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.

          • 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.
      • perhaps you already knew this, but in case not (and besides, there may be others who don't): part of the prize in this contest is to have the judge proclaim the language you used to be the "language of choice for discriminating hackers". If the winning entry had been written in VB, they'd have to say it too.
    • Erlang escaped from Ericsson R+D a long time ago, and is used a lot outside Ericsson, especially in
      robustness applications. Theres a tough learning curve, but once you are there its difficult to go back to procedural programming

    • Haskell? yuck. (Score:1, Interesting)

      by Anonymous Coward
      We all get forced to use Haskell in our first & second years at Uni. and 95% of us hate it, especially those of us with previous programming experience.

      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.

    • don't dismiss erlang so quickly. while not widely used, it is a wonderful language for building distributed systems. among FP types, it is considered one of the more "real world" languages.

  • ICFP not a programming language comparison (Score:5, Insightful)

    by Anonymous Brave Guy ( 457657 ) on Friday September 07, 2001 @06:12AM (#2262497)

    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!

    • Not an expert, but isn't Forth used for a lot of embedded and instrument control code?

      Forth certainly has a lot in common with functional langauges.

      Functional/declarative langauges are great where bug-free precision is required because you specify what the results *are* rather than the steps required to produce the result. I'd feel much more comfortable with my mission-critical stuff written in Haskell than C/C++.

      • Re:ICFP not a programming language comparison (Score:5, Interesting)

        by Anonymous Brave Guy ( 457657 ) on Friday September 07, 2001 @07:05AM (#2262572)
        Functional/declarative langauges are great where bug-free precision is required because you specify what the results *are* rather than the steps required to produce the result. I'd feel much more comfortable with my mission-critical stuff written in Haskell than C/C++.

        That's a fair point. Playing devil's advocate somewhat, I'll contend that a purely functional paradigm can be more awkward for certain types of job than a procedural language such as C. Note the number of "functional" languages that now offer heavyweight extensions beyond strict lambda calculus style functionality as a result. In those extensions is found extra power, but also some of the risks present in the other languages.

        Being slightly more objective, I agree that for a 0% bug rate, C and C++ are not the solution (and I am a professional C++ programmer, so I have no axe to grind here). The catch is that most (not quite all) real-world programs can tolerate a 0.01% bug rate instead, and that can be reasonably achieved by a competent programmer in non-functional languages as well. At that point, the correctness argument loses a lot of its weight, and you have to consider many other factors as well. Like I said before, which language is most useful often depends deeply on the context in which it will be used.

        • Yeah, I totally agree that you should pick your langauge based on the context. I know enough different languages not to really care which one I use, so it usually comes down to who else will need to maintain the code (Java often wins in this regard....). I can live with 99.999% success rate, though some might regard that as heresy :-)

          Interestingly, I *used* to think that pure functional languges were inconvenient, particularly for stuff like IO and user interfaces.

          I have now changed my opinion after investigating a concept called "Monads". These are seriously cool, they are an abstract data type that effectively descibes an "operation". They basically allow you to capture procedural/OOP type concepts of state, communication etc. in a purely functional manner.

          Techniques like this may be the key to achieving the best of both functional and procedural/OOP worlds. You get all the accuracy and development speed advantages of functional languages, but gain the ability to manipulate state and interact with the world in a procedural style.

          Extremely cool, though it's a tricky concept probably best left to computer scientists and the more hardcore coders....

        • I agree that for a 0% bug rate, C and C++ are not the solution (and I am a professional C++ programmer, so I have no axe to grind here). The catch is that most (not quite all) real-world programs can tolerate a 0.01% bug rate instead, and that can be reasonably achieved by a competent programmer in non-functional languages as well.

          If only this were true. We've all seen here on /. the complaints about crappy programs with high defect rates. Are we to assume that all of these programs were written by un-competent programmers? I would guess that the average bug rate for C/C++ programs is quite a bit higher than 0.01%. I would also suggest that this kind of "This bug rate is low enough" attitude is why we have such crappy software.

        • 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.

          • Hmmmm.... you might be surprised how hard it is to write a buggy program in Haskell.

            There are no pointers. No segfaults, no pointer arithmetic, no array out of bounds.

            It's strongly typed, so most bugs just don't compile in the first place.

            It's a pure functional language with no side effects, which means that functions are nicely compartmentalised and can't mess with global variables, or indeed affect anything else in the program other than their return value. This is also great for testing.

            There are no mutable variables (though you can simulate them with Monads if you like). This avoids a lot of bugs since it encourages you to write in a style where you're not trying to keep track of a load of changing variables.

            You implement looping and control constructs with lists and/or recursion, which tends to avoid bugs with boundary conditions. Also leads to some impressively compact code.

            You get lots of reusability through polymorphism and first-class functions, which means you're not endlessly rewriting similar code (and invariably forgetting to update one instance...).

            Haskell uses Lazy evaluation, which means that things don't get calculated until they are needed. This allows amusing tricks like using infinite sized data structures:

            ones = 1 : ones

            (defines an infinite list of ones)

            or:

            numsfrom x = x : numsfrom (x+1)

            positiveintegers = numsfrom 0
            naturals = numsfrom 1

            (all positive integers and naturals)

            Numbers are arbitrary length integers, so no problem with data type size.

            Programs are written as declarations, so it is usually easier to spot logic errors. Check out the Haskell and C implementations of Quicksort for example.

            Basically, I reckon that if everyone coded in Haskell or some other functional language, there genuinely would be less coding errors, for quite a lot of concrete reasons as listed above. This goes quite a long way to explaining why the functional languages do so well in contests like the ICFP.

    • I wonder when people will get the notion that there is no "best" programming language. Discussing the suitability (or lack thereof) of a programming language without discussing what sorts of tasks the programming language is supposed to do is just plain dumb.

      --
      Onorio Catenacci
      • I wonder when people will get the notion that there is no "best" programming language.


        People will never get this. It's much like fat people getting exercise machines: if every time they watched an infomercial they'd just get on the floor and do sit ups and push ups for a half hour they'd be good to go. (ok maybe some aerobic too).

    • Boy, you sound nervous! If this were the "Object-oriented programming language contest," and C++ and Python and Eiffel won, I wonder if you wouldn't be saying just the opposite.

      No one (at least, no one associated with the contest) is saying this is an objective comparison of programming languages or that the winners are the best programming languages for any and all purposes. Indeed, the prize-winners' appelations ("language for discriminating hackers") are so laughable, no one in his right mind would take it seriously.

      This contest is about having fun, taking pride in your favorite language, giving a few kudos where they are deserved, and a little bit of advocacy for a class of programming languages that are overlooked by the programmer community at large. It's not a pissing contest.

      BTW, what is an "objective" language comparison anyway? I am a programming language researcher, and I can think of a few theoretical ways to compare programming languages, but I would think that most programmers-in-the-trenches would be more satisfied with tests that compare languages on real life problems, and these contest problems are not far off from that. So what are you so unhappy about?

      • Boy, you sound nervous! If this were the "Object-oriented programming language contest," and C++ and Python and Eiffel won, I wonder if you wouldn't be saying just the opposite.

        No, I wouldn't.

        No one (at least, no one associated with the contest) is saying this is an objective comparison of programming languages or that the winners are the best programming languages for any and all purposes. Indeed, the prize-winners' appelations ("language for discriminating hackers") are so laughable, no one in his right mind would take it seriously.

        Sadly, numerous people on /. do take these things as if they were a sudden divine indication of The Way To Go. Just look at any of the past threads on the subject; try OCaml as a keyword in a search. They are absolutely littered with silly language advocacy. I hoped that by getting this comment in early on this thread, we could avoid that this time around and stick to the interesting, factual discussion.

        BTW, what is an "objective" language comparison anyway?

        In real terms, there's probably no such thing.

    • 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!

      I don't think many are running out shouting "Haskell is the best programming language". Or that functional languages are great for everything ... However for the 4th time in a row, they did extremely well, on a fun and non-obvious programming task. Usually, *some* people claim functional languages are slow or hard to program with, or only useful for toy programs: to some extent the contests proved the contrary.

      I don't agree that the contest favored functional languages at all : the first one (1998) clearly didn't (how many chess or go programs are written in functional languages ?). This one didn't ; it was actually a document/optimization processing contest: it actually favored intelligence, and clever algorithms. Maybe such algorithms can be better be expressed in functional languages ?

      Don't treat this as an objective (no pun intended) programming language comparison!

      It isn't, but do you have more objective programming language comparisons ?

    • Note, for example, that some of the top OCaml entries in the past were from the designers and implementers of the OCaml language and compiler. This year, the Judge's Prize, for a program written in Erlang, went to a team including the original architect of Erlang, plus the author of the Erlang compiler. So the poster is correct in that this is not a battle of languages, but rather a battle of top notch programmers, each using his or her pet language.

      A serious C++ entry, for example, would be from a team headed by Bjarne Strousrup.
      • Note, for example, that some of the top OCaml entries in the past were from the designers and implementers of the OCaml language and compiler. This year, the Judge's Prize, for a program written in Erlang, went to a team including the original architect of Erlang, plus the author of the Erlang compiler. So the poster is correct in that this is not a battle of languages, but rather a battle of top notch programmers, each using his or her pet language.

        A serious C++ entry, for example, would be from a team headed by Bjarne Strousrup.

        There is probably a little validity to this, but I don't think it's the whole story.

        First, there are a lot more entries (171 this year) than there are languages used, so not *everyone* can be the designer of their language.

        It probably is a slight advantage to be the designer or implementor of the language just because that means that you're probably pretty familar with it. You also get to be able to fix any compiler or library bugs that you find during the contest, but that applies to anyone using an Open Source compiler, not just the original author. We didn't make any changes to the Dylan compiler during this contest but we did note a couple of performance problems in the standard library when it was abused with huge inputs, and we'll be fixing those soon.

        It's obviously not *necessary* to be the implementor of the language. The winning team (Haskell Carrots) didn't invent Haskell. The guy who wrote "Beamer" (which looked as if it might win until it failed on some later test files) certainly didn't design C++. And none of the Dylan Hackers invented Dylan. We weren't even the brilliant people at CMU who wrote the compiler we're using -- we're just running as hard as we can to prevent bitrot and make a few small enhancements to it.

        For myself, I'm probably far more expert in C++ and Java than I am in Dylan (my current job is taking a 400,000 line Windows program written in C++ by a couple of Russian guys and figuring out how to port it to Mac and Linux) but I know enough Dylan to know that it's the far better language. It's far faster to write in, far simpler than C++ while still offering all the power, and it can generate extremely fast programs.

        Some languages do have a reputation for requiring a PhD in order to understand them. I've tried writing programs in OCaml and Haskell and something about them just doesn't sit well with me. And I read the Haskell Carrots' scientific-paper writeup and my head spins about twice per paragraph. Did they really think about all that stuff during the 72 hours? We Dylan Hackers couldn't think of any "literature" to consult for algorithms, and didn't write any proofs -- I guess we were too busy hacking :-)

        Another factor is that with a language that doesn't yet have many users it's far more likely that it will be the language designer using it. Who else is there? Languages such as Dylan, Erlang and OCaml are virtually unknown among the general programming community, not because they are bad languages but just because they are new and they don't have Sun's or Microsoft's billions of $$ behind them -- and those companies design and use programming languages as political weapons rather than as the best programming languages they can be.

        Even if you still believe that this is really "a battle of top notch programmers" rather than a contest of languages, I think it's still pretty interesting to see what languages top programmers choose to use. Aren't they likely to choose pretty good languages?
    • It would be smashing if the results of the last four ICFP contests (the declarative languages generally left the imperative ones standing) at least encouraged more hackers to try functional programming and see what all the fuss is about.

      For the record, the ICFP problems can hardly be said to be tailored to FPLs, although there probably is some truth in the suggestion that you get a higher proportion of docs/post-docs using them (lo! another hint!)
    • There should be a c++ lab somewhere to run the dual constest of the ICFP. Same format, same rules, but have the challenge be similarly tinted towards imperative and OO programming.

      I'm sure it would inject great vigor in 4th generation language research. They need all the help they can to bring them away from traditionnaly functional problems.

      And it would make me happy. I hate waiting the whole year to see my favorite constest come back.

      • I would very much like to see a programming contest that is somehow tinted towards imperative and object-oriented programming. I am curious though -- what kinds of challenge tasks would you consider so tinted? It can be difficult to come up with programming problems that admit reasonably objective judging criteria, and for which submissions can be expected to span a spectrum of quality from good to bad.
        • Hard to say. Hard to say since any such judment of mine, if based on the values of the particular problem, would be subject to the bias of my own education.

          I would attempt maybe the acm programming constest were more imperative. Of particular notice, the problems where the best pure-functional code is provably less efficient (in the big-O sence, and they exists). Those problem will tend to have massive non-local garbage collecting going on and/or degenerative lazy-hunks allocations patterns.

      • FOR THE LAST TIME, THE ICFP CHALLENGES ARE NOT TAILORED FOR DECLARATIVE LANGUAGES!

        Do you think language researchers sit around thinking, "Hmm, today I will add yet another obscure and utility-free aspect to my carefully-constructed-to-be-useless language"?

        These languages are designed for universal utility and/or to do research into better ways to solve problems faced by contemporary programmers working with C/C++/Java/... They are not niche languages.

        It would be so nice if people would go and try these things out for real before spouting this sort of utility-divide crap.
        • >FOR THE LAST TIME, THE ICFP CHALLENGES ARE NOT
          >TAILORED FOR DECLARATIVE LANGUAGES!

          I refused to judge of the declarativeness of the challenges for fear of exposing my own bias. I would say though the orginizers are doing a might good job at comming up with cool challenges.

          >Do you think language researchers sit around
          >thinking, "Hmm, today I will add yet another
          >obscure and utility-free aspect to my carefully
          >constructed-to-be-useless language"?

          >These languages are designed for universal
          >utility and/or to do research into better ways to
          >solve problems faced by contemporary programmers
          >working with C/C++/Java/... They are not niche
          >languages.

          Well, I've seen alot of mislead language-design going on. I saw many preaching : "computers are getting faster so we can affort our language to be slow". It's sad to see how many languages failed because of this premise; Java is certainly surfering from it everyday.

          This, along with other pervasive misconceptions, the need to create niche languages to explore particular aspect of languages design, and just the raw fact that's it's pretty hard to grow a languages to full general usefulness; With all that, alot of languages don't make it, sadly enough.

          Anyway, do you have more examples of non-niche aspiring 4th generations languages? I'm somewhat familliar with the efforts of Ocaml and Haskell. Their aspiration as non-niche multi-paradims languages is fresh, difficult and brave.

    • People should also consider that the Camls R Us team (who have won the competition using OCaml) were the ones running the competition, so they didn't have an entry!
    • 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!)
    • Before everyone runs out and says "Haskell is the best programming language", as seemed to happen with things like OCaml in the past


      OCaml didn't happen to win this year, but there were a number of OCaml programs in the top 20 or 30 (out of 170) entries. It's still a great language and one that I admire a lot (but I still prefer Dylan...)


      please bear in mind that the ICFP tasks are somewhat biased toward functional languages


      In what way? I don't think that's true. With this year's task, for example, with a suitable amount of brains and understanding of the problem it turns out that you could write an *extremely* good entry quite simply in C -- using a technique called "Dynamic Programming" you could read the input and find its length (call it N), create an NxN array, and write a fairly simple 3-deep loop to iterate over the table to fill it in. I guggest you go and look at Tom Rokicki [rokicki.com]'s excellent page to see how. If he'd got it finished in the 72 hours then he would have won the contest.


      Of course that's the thing. He didn't get finished in time, which is the whole point of the contest. Tom was prototyping in Perl and then rewriting into C for speed. With Dylan we didn't need to do that. We could prototype in Dylan without worrying about declarations and types and fiddly things, and then when we found some part was too slow we could stay within Dylan and add a few declarations where they were most needed, rather than having to totally rewrite the program. That's the strength (by design) of Dylan.

      • I'd like to clarify on the role of dynamic programming in this
        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.

        • Congratulations from a member of the team that won the second prize.

          I thought about using dynamic programming for solving the problem, but rejected it quickly because I saw the cubic growth, and wasn't aware of the literature on solving the problem. Hats off to you.

          Still, our code runs five times faster than yours :).

  • Dylan links (Score:2, Informative)

    by menozero ( 134447 )
    More about the Dylan Hackers' entry [hoult.org]; they use (and maintain) Gwydion Dylan [gwydiondylan.org].

    Functional Objects [fun-o.com], Inc. sells Functional Developer, their Dylan implementation, for Windows and soon for Linux.

    • I clicked on the Dylan link [pcai.com] in the main post and got to the PCAI Dylan site. The first thing I saw was: "Overview: Dylan is a new object-oriented dynamic language (OODL) being developed by Apple. " Then I had a lok around and found out that Apple pulled the plug on Dylan in late 1995. Aparently, it had been being developed at Apple's Cambridge [apple.com] labs. (Don't bother trying to follow that link... it's DEAD!) A better link is http://dylanpro.com/DylanExchange.html [dylanpro.com]. Does anyone know if the Dylan language is being actively developed by anyone? Or do they have any other resources?
      • See the posting you're referring to, both the Gwydion Dylan compiler (open source) and the Functional Developer (closed source) are being actively maintained.
      • I clicked on the Dylan link [pcai.com] in the main post and got to the PCAI Dylan site. The first thing I saw was: "Overview: Dylan is a new object-oriented dynamic language (OODL) being developed by Apple. " Then I had a lok around and found out that Apple pulled the plug on Dylan in late 1995.

        I don't know why that particular link was used by whoever submitted the story. There are certainly more appropriate ones.

        Dylan started out around 1990 at Apple's Advanced Technology Group, which wanted a single language that would meet all the needs of different groups then using Common Lisp, Smalltalk and C++. Apple worked closely with people at Harlequin (who were selling Lisp and ML development systems and consulting services as well as a popular PostScript RIP) and Carnegie Mellon University (who do major programming language research, and produced the Open Source CMUCL compiler for Lisp).

        The three groups agreed on a spec and started implementing compilers for Windows (Harlequin), Macintosh (Apple) and Un*x (CMU).

        The subsequent history is sad.

        Apple started making big losses in its core business and cancelled projects and products all over: Dylan, Newton, OpenDoc... The Dylan group managed to get out an alpha-quality version and Apple sold it very cheaply ($30) for a while. Very very cool stuff, but still buggy :-( No doubt the source code for it all still exists somewhere within Apple. Maybe it will someday see the light of day.

        The CMU "Gwydion" project lost some funding and changed direction a little, and stopped Dylan development. Fortunately, they released their work to the public domain and we "Dylan Hackers" have been able to pick it up and (too slowly :-( ) polish it towards finished form.

        Harlequin hit some financial problems and were acquired by someone who wanted their PostScript technology. The language implementations were I think mostly closed down, but the Dylan team managed to get the rights to their work and formed a new company, Functional Objects, to continue it.

        Does anyone know if the Dylan language is being actively developed by anyone?

        Functional Objects has a very nice Windows IDE. Since getting the rights from Harlequin they have put out a 2.0 (and 2.01) version on Windows and just this month they have started an alpha test program for a Linux command-line compiler.

        The open-source Gwydion Dylan is being actively improved, with a significant new release being issued roughly every six months over the last three years (hmm ... I'm not even sure it that's deliberate ... we tend to do a release shortly after someone checks in some major improvement rather than to a time schedule...). We've taken the original CMU implementation which ran mainly on HPUX and extended it in a number of ways.
        • It now runs on Linux, LinuxPPC, MacOS 9, MacOS X, BeOS, FreeBSD, Windows and goodness knows what other versions of Unix -- I believe it may have been running on Itanic for quite some time, somewhere deep inside Intel and/or HP...
        • Improved language conformance. We're just about 100% DRM-compliant now. We work closely with Functional Objects on language extensions and library issues, so that source code is portable.
        • Performance improvements. The guys at CMU did a wonderful job, but sometimes they just wanted to make things work rather than make them work fast. The generated code is mostly excellent, but the compiler itself takes too long. We've made big advances in this but there's still a way to go.
        • Interfaces to the real world. We're working on automatically generating interfaces to C code. It's always been possible to write interface functions manually, and people have done it for the Mac toolbox, GTK, OpenGL and other such large libraries of code but it's rather tedious to do it manually. Automatically divining the intent of C header files is not however all that easy a problem :-(


        We're very pleased that Gwydion Dylan has recently become a standard package in the FreeBSD and Debian GNU/Linux distributions.

        So, in summary: Yes, Dylan is being actively developed, by more than one group.
  • Whilst looking through the winner's personal info, I came across this page [harvard.edu] which has quite a photo of ... something bloody attached to his arm ... and a god of vampires [godofvampires.com] 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!

  • Different ways of scoring (Score:3, Informative)

    by Anonymous Brave Guy ( 457657 ) on Friday September 07, 2001 @06:55AM (#2262557)

    Just found this interesting analysis [hoult.org] 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.

    • You neglect to mention the significant fact that the ranking on that page only takes into account the first round results.

    • As the author of Beamer (the C++ program mentioned), I'll add one comment. The program uses a beam search and produces excellent results for all the tests on the machine I used for development. Unfortunately, that machine has 512MB of RAM, and the contest machine has 256MB. I discovered after the deadline that the priority queue used for generating the set of next candidates in the beam search can grow unreasonably large in some cases. For the last two test cases used, this is enough to start the thing thrashing in 256MB, and then it never finishes. A hard limit on the queue size wouldn't have affected the quality of the results, but hindsight is 20/20. Given the oversight, Beamer clearly didn't deserve to win. Lesson: set a reasonable data size limit when developing :-).
    • Just found this interesting analysis [hoult.org] 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.

      Thanks for that.

      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.

      I'd been wondering what happened to "Beamer" myself, but it seems that it crashed&burned on several later input files by using too much VM and going into swapping and never terminating. A pity, because it was obviously a great effort, but it's those little correctness details that make or break an entry in a contest like this.

      On the correctness topic, it's interesting that both our programs and the winning Haskell Carrots entry failed on the empty input file and the <PL></PL;> test. In the case of the Haskell program they had a shell script to catch the crash and output a fallback solution (the original input). I refuse to do such things as a matter of principle -- I think you should be able to handle it within your program itself. Both Dylan and Haskell (and OCaml, and others...) are supposed to be "safe" languages that can never segfault. Do we believe our own propaganda, or not?

      So, these inputs caused an "array index out of bounds" exception in some part of our code that was making unwarranted assumptions about the input (that it actually contained at least one printable character!), and this exception was safely caught by a handler in the main program.
      • As you may already know, it is perfectly possible to do with Haskell what did with shell scripting, but we found shell scripting easier. I don't see Haskell as a hammer for every nail, even though you can hit a lot of things with it. (:

  • Dylan (Score:4, Informative)

    by Earlybird ( 56426 ) <slashdot&purefiction,net> on Friday September 07, 2001 @07:11AM (#2262590) Homepage
    Dylan is a lovely, lovely language. At times awfully verbose in a way that reminds me of Ada, but its syntax and design is different. Its design is consistent and thoughtful, and the language is blissfully free of the cruft we see in C++ and Java.

    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 [http] (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 [indiana.edu], "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 [http] site. They provide a Windows/Linux-based IDE and compiler for Dylan. The "Basic Edition" is free as in beer.

    • Re:Dylan (Score:2, Informative)

      by andreas ( 1964 )
      Well, according to the definition, a functional language is one where functions are first-class objects. In mathematics, the term "functional" means "a function that can be applied to other functions".

      By this definition, Dylan is a functional langugage, it even supports currying, function composition and closures.

      But Dylan isn't a purely functional language, like Haskell is, but supports a mixture of other paradigms. Also, Dylan has no parametric polymorphism. In this sense, it's close to Scheme.

      And "Dylan" does come from Bob and Thomas, but Apple could never admit that, otherwise they would have lost quite some law suits.
      • Well, it depends on which "the definition" you choose :-) Some people take "functional" to mean "like a mathematical function", that is, without any side effects. I usually just say "a language with higher-order functions" (or don't say anything, and just keep out of the discussion ;-).

        BTW, I used to work at Harlequin and heard once that (back at Apple) Dylan used to be called "Ralph", after some guy on the project, until he left the project. Could be a complete fallacy, though -- can anyone confirm that former name?
        • A former Apple developer confirmed that Dylan was called Ralph initially, back when it was used for the Newton.

          They even had a prototype operating system for the Newton written in Dylan, but management decided against that.
  • 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.
    • Good point. There is no langauge that "best for everything". If Perl can claim superiority at anything though, it would have to be for its unbeatable code obfuscation possibilities :-)

      I think the important areas for a langauge:
      -Readability
      -Development speed
      -Run time performance
      -Correctness (i.e. encouraging bug-free code)
      -Popularity (availability of skilled coders)
      -Portability (availability of platforms)
      -Libraries (availability of ready-made toolkits)
      -Conceptual fit with problem

      Work out what you want for your project, prioritise the above and make your langauge selection on that basis.

      I do often use Haskell (the winning language) myself, because it is pretty near the top in all except run-time performance (it's more than fast enough) and popularity (I'm a hobbyist, so don't care what anyone else uses)
  • 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.

    • Scheme was a huge influence... (Score:1)

      by Anonymous Coward
      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.
    • Dylan used to be a lot closer to scheme, using prefix notation complete with large numbers of paren's. Descriptive variable and function names are important in both Scheme and Dylan, things like 'full?' and 'set!.' A lot of early Dylan compiler work was done in Scheme & Lisp. Thomas, the Dylan-like compiler was written in Scheme, Apple's Dylan was written in MacLisp. The biggest difference is that everything in Dylan is an object, including functions, classes. Also, Dylan has a much stronger module system, some really interesting stuff in terms of sealing, and a flexible type system.
    • A comparison between Dylan and Scheme is available <a href="http://www.cs.indiana.edu/hyplan/jsobel/fors chemers.html">here</a>.

      Basically you're right, Scheme had a lot of influence on Dylan. The original Dylan even had prefix notation as known from Scheme and Lisp, but that was changed to infix, because it was perceived that more people would prefer the syntax as it is.

      Dylan adds some features not found in Scheme: hygienic macros, an object system inspired by Common Lisp, modules and libraries.

      The object system is especially interesting: it is based on the generic function model of OO, as opposed to the message passing model most people know from Smalltalk, C++, Java, or perl. Basically objects don't "own" methods anymore, they are standalone. To select the right method (or "virtual function" in C++ lingo), all the parameters are looked at at runtime, not just the first one.
  • This is the program that got the best results (if I can read the score table). Where is it?
  • 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.
    • http://www.fftw.org generates pretty damn good Fast Fourier Transform code using an OCaml engine.
    • 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.

      While designers of better languages like to spread the word far and wide, it seems that people actually using them often regard their choice of language as a competitive advantage and try to keep it a secret.

      An excellent example is described by Paul Graham [paulgraham.com] who got rich by writing what is now Yahoo! Store in Lisp but deliberately kept very quiet about that fact.

      So if you notice that I'm suddenly not mentioning Dylan any more then you'll know what is happening :-)
  • ..Who don't know what ICFP is (I didn't) and the site's a bit slashdotted, the google cache is Here [google.com].

    Editors, would it hurt to expand uncommon acronyms in stories?
  • 9th place baby!!!

    SML rulez!!!!!@!!!
  • 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 [unsw.edu.au]

Slashdot Top Deals

Some people claim that the UNIX learning curve is steep, but at least you only have to climb it once.

Close