Please create an account to participate in the Slashdot moderation system


Forgot your password?
Programming IT Technology

ICFP 2001 Task 110

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? :)
This discussion has been archived. No new comments can be posted.

ICFP 2001 Task

Comments Filter:
  • by Anonymous Coward

    For those who are actually participating the competition, SAVE THE DOCUMENT!!! Don't give yourself an excuse for LOSING when the page is SLASHDOTTED and you can't lookup the task again!!!!!

  • by Anonymous Coward

    Now what was the article about ?
  • by Anonymous Coward
    the winning entry will be written in Intercal :)
  • by Anonymous Coward
    That would be historical. Never before has a markup language challenged the dominance of a programming language.
  • by Anonymous Coward
    > ie, it doesn't have to be a functional programming language.

    Of course. Go ahead, and ridiculize yourself by submitting an non-functional entry.

    Those guy are functional from the bottom up, and their preaching about it. The contest is _designed_ to make non-functional languages ridiculized.

    I bet that the SML/NG input to the software will be tailored to make functional software win (ie: you will have incredibely complex input, that will only be suitable for languages with built-in matching, so functional languages will be standing on the shoulders og giants).

    Using C or C++ in this constest is akin using perl to write a linux kernel module.

    Note that it is not a bad contest, on the contrary. It shows the areas where functional languages shine. Of course, I'll be rotfmalo the day where someone will submit a winning C entry (for instance, by having a library that would implement most of the goodies functional languages are good at)


  • by Anonymous Coward
    not that there's anything wrong with that.
  • by Anonymous Coward
    Parsing is easy. Very easy. The problem is finding possible optimisation transformation on the parsed form.

    I am really short of time, but I am pretty sure that there are case where an optimisation will depend on very distant tags. This is the place where you C program will have a very hard time (in particular because the time limit imposes non-brute force heuristics).

    That beeing said, 3 days is a lot of time, and the contest *looks* easier than the preceeding ones.


  • by Anonymous Coward
    Java 1.4 has regex pattern matching in the standard libraries.
  • by Anonymous Coward
    Slashdot editors suck, and that's the story i'm sticking to!
  • ...I must admit, I've never seen someone post a reply to a reply to their own message.

  • I see what I'm missing. Color nesting makes it hard.

    Hint: There are also EM/S nesting, size nesting, and underline nesting optimizations.

    Local optimizations can be done on the fly as you initially indicated. The global optimization problems for nesting are algorithmically "hard." My guess is it is NP. The global optimization problem can be stated as a path minimization problem in a fairly large state space (naive size is 2x2x2x2x2x4x10x8) with ordered waypoints. The state space is actually a bit smaller than that.

    Oh, and the state transition distances are different. A <B>,</B> pair costs 7 bytes, but a <PL>,</PL> pair costs 9. I bet that linear programming will choke on this problem too. There are a bunch of local minima. Time to dust off my Numerical Recipes book and read up on simulated annealing.

    Of course, what do I know?
  • First pass optimizations should be able to guard against stupidity. My first cut just clears out whitespace and trivial redundancies, like:

    <B></B>This is not Bold<B></B>


    <B><B>This was already Bold</B></B>

    The first pass optimization will worst case include all of the original tags and should therefore pass the stupidity test. Of course, after this initial cleanup, then the real work has to start.
  • We don't need = (except in initializers, of course)...

    Hmm... I have better things to do than figuring out an algorithm for this, really I do...
  • Sorry to upset the apple-cart, but might a combination of XML and XSL challenge the dominance of Perl? I'm afraid I am not suffinciently advanced in these languages to bet on them, but I reckon they would give the other contenders a run for their money.

    Barry de la Rosa,

  • the corrolary to this is that O'Caml is only used by grad students who have tons of free time, while C/C++ is used by people who get paid.

  • Lots of tests aren't implemented for Mercury, which explains its low score.. but it isn't doing to well in the ones that are implemented, anyway.

    Doug forgot to enable the Mercury compiler's optimizations! He's fixed that now, so we now do a lot better than before.

    Nonetheless, I think the Mercury folks took a prize last year though, didn't they?

    We came fourth, which was good enough to rate a mention, but not good enough for a prize.

  • Or in Objective Oberon with an object orientated design, or perl, or c, or c++, or shell with awk and sed.
    i suppose if you are a real glutton you could use assembler *shakes head*

    actually a language with excellent string manipulation is also Business Basic (Basis Business Basic [] or ProvideX Basic) []

    pick your favorite language
  • [Dilbert] Not so good, you just authored IIS.

    Remember: it's a "Microsoft virus", not an "email virus",

  • Actually, perl is a fully functional language in a pure sense; functions are values, and the language features anonymous functions and closures. Arguments are passed as a list, meaning you can curry if you feel like it.

    You just very rarely see perl being used functionally because despite the fact it has functional features, its functional features are really quite clumsy to use, and anyone prone to functional programming would probably prefer another language anyway.. in other words, you can be as functional as you like in perl. It just isn't worth the bother.

    Larry Wall likes LISP, though.
  • by DGolden ( 17848 ) on Friday July 27, 2001 @05:24AM (#2189893) Homepage Journal
    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 []

    for example: <WEIGHT unit="pound">
    <NET certified="certified"> 67 </NET>
    <GROSS> 95 </GROSS>

    (WEIGHT (@ (unit "pound"))
    (NET (@ (certified)) 67)
    (GROSS 95)

  • by ChrisBennett ( 18205 ) on Friday July 27, 2001 @02:08AM (#2189894)
    Anyone? Ok, I'm actually serious, don't mod me up +1 Funny.
  • I'm sure that there will be quite a few hacks out there using lex & yacc & C :-)
  • To do it with a regular expression.
  • Why go for third party add-ons? You do know there's support for regular expressions [] in Java these days?

  • I'm joining the contest. That is if this damn semantic analyzer works, I can get on to the optimization part. :P
  • No, no, no . . . you got it all wrong. The winner will be in C#
  • No, because Perl isn't a functional language. *sigh*.
    Read the rules first.

    Check out comment 28 [], it's his point.


  • #!/bin/bash

    gzip *.html
  • Yes, and open source software sucks because if Linus et al had real jobs, they wouldn't have time to futz around in their spare time...
  • Sorry to upset the apple-cart, but might a combination of XML and XSL challenge the dominance of Perl? I'm afraid I am not suffinciently advanced in these languages to bet on them, but I reckon they would give the other contenders a run for their money.


    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.

  • While that's partly true, it won't help you. The task is designed for functional languages, and it shows. Functional languages have algebraic data types and pattern matching built in. In C you'd have to implement this yourself, plus all the code required for memory management and write the optimiser, all in three days.

    That's why I predict O'Caml will win. Of all the languages which have native support for precisely this kind of task, it's the one that also has the support for beating the time limit.

  • Java does not have pattern matching, unless you think method dispatch is pattern matching. :-)

    Having said that, Java would be a good general-purpose language to solve this problem in. I don't like your chances given the three day limit, though.

  • Anyhow, speed will be the deciding factor on this one.

    No, flexibility will be the deciding factor, closely followed by speed of development. Speed of execution won't make a huge difference, because the judges are going to throw in a test case so large and complex that no program can find the "optimal" sequence in the given wall time on the test machine. So the winner will be the program which can make the best use of the time available.

    The winner will use a set of optimisation techniques (from simple transformations to expanding the string out into decorated characters and re-encoding), and will be able to combine these techniques seamlessly. And this will be coded in three days.

    This is not a test for a systems programming language like C. This is a test for a language in which you can write complex decision logic quickly.

  • by Pseudonym ( 62607 ) on Thursday July 26, 2001 @11:54PM (#2189907)

    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.

  • ...would be my bet ;)
  • by selectspec ( 74651 ) on Friday July 27, 2001 @06:11AM (#2189909)
    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.
  • No INTERCAL [] beers? That one could be interesting :-)

    - Steeltoe

  • Java? Memory management - check; pattern matching - check; threads - check. All there and done for you, just have to write the actual optimiser. I might even give it a go and see how it handles it...
  • Heck, now that's funny!
    I'd give you +2 Funny, were it possible.
    Mind you, that's not because of the Java suggestion; rather it's the mod point filer request that cracks me up.
  • Not AS unreasonable as you might think.

    Still, this isn't exactly Javas' core competency.

  • echo Server: Microsoft IIS/5.0
    echo Content-Type: text/html
    echo <html><title>Server overloaded</title>
    echo <body bgcolor="#0000FF">
    echo <font face="Courier, Courier New, Fixed">
    echo IIS.EXE caused a general protection fault in
    echo module BLUESCREEN.DLL at 0123:45F00F00
    # Yes, I know it's not exactly clean HTML
    # It'll work in almost all browsers though, and
    # they DID say compressed...
  • Since most can handle it, you may even want to "compress" head and body statements... And, of course, leave out closing tags.

    print "404 Not FoundThe requested URL was not found on this server.";
  • At least for correctness. Think about it..

    All you have to do, is parse the document, and then spew it back out in a smaller representation. There are lots of booleans in there, and those are as far as i can see what you really need to worry about.

    Of course, I'm not gonna bother to do this one...

    Anyhow, speed will be the deciding factor on this one. I wouldn't be surprised if the winner is written in plain ole C.
  • Yeah, it's those french guys and their secret war of Caml vs SML. =)
  • You mean, they are too busy debugging their core dumps and memory leaks? ;)
  • C is a poor language for rapid development because it is not safe -- it's too easy to have a space leak or a myserious crashing bug. Manipulating strings and data structures in C is also rather tedious.

    I would expect that a good C implementation would not be faster, either, because using a higher-level, safe language would allow you to make more optimizations to your program (since you can write it faster).

    Go ahead and prove me wrong, though!
  • Well said, dude.

    I'd like to see a java entry in this, but having written compilers in java before, I know it is very painful. (Not as painful as C, mind you, but painful.) The ML family and related languages have a huge advantage here.
  • > or perl, or c, or c++, or shell with awk and sed.

    Ha, good luck with those. This is not just simple string manipulation...

  • Well, that would be Microsoft Research, actually, and last I checked Peyton-Jones was at the Cambridge one.

  • Here's benchmarks:

    Lots of tests aren't implemented for Mercury, which explains its low score.. but it isn't doing to well in the ones that are implemented, anyway.

    Nonetheless, I think the Mercury folks took a prize last year though, didn't they? (Don't get me wrong, I'm all for unorthodox new languages.)

  • I don't think lisp is the most popular functional language any more.. I would say it's probably SML or O'Caml. Lisp hasn't won in any of the previous years, I don't think.

    I agree wholeheartedly, though, that Perl won't be powerful enough for this kind of AST manipulation. I like that the task will probably make slashdot kids think that perl is extremely appropriate -- that will put them in their place all right. ;) Bring it on!
  • I am positive Brainf*ck [] will be on the podium.
  • I'm afraid I am not suffinciently advanced in these languages to bet on them, but I reckon they would give the other contenders a run for their money.

    XSLT is designed not to have side effects and is instead more of a functional language meaning that you can't assign values to variables dynamically. Considering that this task may require quite a lot of storing of state before deciding which optimization to make I think it is rather unlikely that XSLT is a good language to use to solve this particular problem.

    Then again I didn't look too hard at the task but it may be that the judges have designed it in such a way that it is amenable to functional programming considering that it is the being run by the International Conference on Functional Programming []. Even then most functional languages do allow you to store state, even Lisp so an XSLT solution would have to be rather clever.

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

    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 :). 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.

    I'd rather be trolling for [].
  • wouldn't it be possible to use lex/flex to generate a C scanner that could parse the data just as easily as perl? C by itself may not be the answer, but there are some tools that use C that can make life a lot easier.
  • by Nastard ( 124180 ) on Thursday July 26, 2001 @11:33PM (#2189929)
    If you need me, I'll be doing a preliminary victory dance over in the QBASIC camp...
  • Not to mention that an OCaml team has won the last ICFP contests. Perhaps it's not the language inherently, but the intelligent people who chose it. :)
  • My bad. 1998's entry was written in Cilk, a version of C with parallel extensions.
  • A helluva lot simpler. One form- (function-name param1 param2... paramN). Not a whole bucket of syntax rules like you find in those BCPL derived languages. Oh well, let the children speak their C, C++, and Java and leave the meat to the parents.
  • Perhaps. But C++ never was very usable for a big project to me either. So much work for so little result. Smalltalk has worked for me, but to each his own I supose.
  • by stilwebm ( 129567 ) on Friday July 27, 2001 @06:17AM (#2189934)

    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.

  • Yes, but regex pattern matching has nothing to do with pattern matching when speaking of (functional) computer languages.

    Instead it refers to a convenient mechanism for building switch-like statements over algebraic datatypes. Since the language in the task is described by a grammar, it can be represented as an algebraic datatype in a functional language.

    In Java-programmer-friendly lingo, this would mean: Make one constructor (differently named) for each element in the grammar. That way you can build a tree from the text you parse. Then you can make recursive functions, either modifying or returning a new tree, where you will typically use switch-statements on the data, differentiating each elemeent by the constructor used to create it.

    Most functional languages are quite convenient when working with data represented in a tree-form, because algebraic datatypes are so extremely convenient. In Java, one would have to use classes and subclasses instead of one simple definition of an algebraic datatype, and lot's of casting and if-statements instead of pattern matching. It's not that it can't be done, it is just a bit more to write (which happens to be somewhat important when having limited time available, but certainly not all-important, if you type fast).

  • I've got to go to work today, here's a cool contest, maybe I should call in sick? Work all day today and tonight.
    1. Check Coffee Supply
    2. Check Mountain Dew Supply
    3. Damn..Users calling already!
    4. Join Mailing List, wait for next year.
  • No, because Perl isn't a functional language. *sigh*.

    No, Perl has too many capabilities to be considered a purely functional language, however it does have first-class functions, so any program that can be created in more than one functional language (say Lisp and ML) can also be created in Perl: []

  • by Sapien__ ( 156881 ) on Friday July 27, 2001 @12:20AM (#2189938)
    You can do this easily in other languages too, such as alarm() in C (and Perl too!)
  • by Sapien__ ( 156881 ) on Friday July 27, 2001 @12:05AM (#2189939)
    Umm... from the website:

    This programming contest is being conducted by ICFP, which implies a context of functional programming. However, rather than debate the definition of a "functional programming language," we will allow submitted programs to be written in any language whatsoever, as long as it has an implementation for Pentium PCs running Linux. Mixing languages is entirely acceptable; perhaps you will write in Caml and Haskell, with a Tcl script to do the gluing.

    ie, it doesn't have to be a functional programming language.

  • Would that be anything like a little rat dance on a keyboard??
  • Logo! Logo! Bow before the awesome power of the turtle!
  • by cthugha ( 185672 ) on Friday July 27, 2001 @01:55AM (#2189942)

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

  • They'll simply buy out the winning team and divvy them up.
  • Actually, they say they will test with inputs as large as ``a few megabytes''. Note that it is always legal to merely echo an input if you can't figure out how to optimize it...

    Regardless of how we do in the competition, we're learning a lot about our programming language [] and its implementation, anyhow. The task isn't a perfect fit for our language, which is good, since it has tickled some of the dark corners already.

    Two days to go!

  • No, Perl has too many capabilities to be considered a purely functional language, however it does have first-class functions, so any program that can be created in more than one functional language (say Lisp and ML) can also be created in Perl

    Lisp is not just a functional language, as any functional purist will tell you with an air of disdain. It supports multiple paradigms.

    I don't know Perl, so the following is a real question, not merely rhetorical: Can you create new functions on the fly in Perl as you can in Lisp? That is, can you have a function1 that returns a new function2 as its value, where function2's definition is relative to the parameters that were passed into function1 at its time of creation? That is, can you create closures in Perl? In Lisp, this is done as follows:
    ? (defun make-adder (addend1) (lambda (addend2) (+ addend1 addend2)))

    ? (make-adder 3)
    ? (funcall (make-adder 3) 2)
    => 5
    Just passigning functions around does not make a language functional. Heck, C can do this function pointer. Truly functional languages support the creation of closures (among other things). Can Perl do this?
  • why would C be inferior for solving this task?

    It's a great choice. You'll kill the guys working in x86 assembler.
  • I think lots of {if time > limit then return} statements would be a better idea than threads. Anyway, better or not, its still easy to do it in any of those jurassic procedural languages. Still, ocaml has good chances of winning coz its a powerful language with a great implementation.
  • Just choose your favorite language amongst the ones used in the "99 Bottles of Beer on the Wall" [] gallery.
    I'll personally offer 99 bottles of Chimay Belgian beer to the winner of he does it in BrainF*** []!
  • I'd like to create a Forth Team as I consider this rather ignored language as one of the most elegant solutions in terms of language simplicity as well as interpreter efficiency.
  • by Godwin O'Hitler ( 205945 ) on Thursday July 26, 2001 @11:55PM (#2189950) Journal
    Did anyone else spot the similarity between the name of their mark-up language and another language?
  • It takes a little up-front learning if you're used to, say, C. The syntax is different from other languages, but actually simpler.
  • MSFT was among the 1999 winners [], but their entry was in Haskell, not Visual Basic. Unfortunately their writeup has disappeared from the MSFT web site.
  • Hint: 20 levels of bracing means you should be breaking that function down into smaller, reusable functions. You don't tend to do that in C++ because it's such a drag -- cut, paste, declare, etc. In Scheme new functions are cheap and easy.

    That aside, who says you have to use it for a large project before it's fun? I'm having fun with a couple of 3KLOC projects.

  • by brlewis ( 214632 ) on Friday July 27, 2001 @05:01AM (#2189954) Homepage
    2000 []
    1. PLClub [] submitted two separate entries using OCaml, either of which would have won the contest.
    2. Camls 'R Us [] took second place.
    3. Galois Connections took third with their Haskell entry [].
    4. The Merry Mercurians took fourth with their Mercury entry [].
    1999 []:
    1. Camls 'R Us mopped up the competition with their 3585-line OCaml entry []
    2. The 1250-line Haskell Entry that took 2nd place was written in a mere 24 hours.
    1998 []:
    1. First prize was a Cilk entry []. Winning the contest doesn't seem to have made the language take off in popularity.
    2. Second prize: an OCaml entry [] ``beat out 23 C and C++ entries, many of these being highly tuned programs produced by extremely competent programmers skilled in game-playing algorithms.''
  • for it to be Ruby, but I imagine some type of Lisp-like language would be best. Maybe Scheme as others have mentioned.
  • when i first read SML/NG i actually read "smiling"

    maybe you know something i don't.


  • Everyone knows that Integer Basic had much better performance than Applesoft, as long as you can tolerate only having integers. 10 COLOR=3 20 PLOT 10,10 umm, what else was the program supposed to do ?
  • Don't let all the Irritating Parentheses [] fool you, LISP WILL WIN!
  • Pick me [], pick me! []
    JOVIAL will kick some serious buttocks! :)

  • by rfsayre ( 255559 ) on Thursday July 26, 2001 @11:43PM (#2189960) Homepage
    Thanks to relentless innovation from Redmond, the choice is clear. A team working in Visual Basic will clearly triumph.

    Art At Home []
  • Perl hasn't a chance. As much as we all love it, it is not up to the task of writing complex programs such as this. The winner will probably be written in LISP, because it is the most popular functional language. The only other possible winners are better functional languages such as Caml or Haskell.
  • I think the winner could quite well be SNOBOL.

    It sure would be nice to hear some positive news about SNOBOLing

    I know, bad joke :-)
  • by Patrick May ( 305709 ) on Thursday July 26, 2001 @11:41PM (#2189963)
    You mean this story is thin, neat, and dresses well?
  • Perl does in fact have proper closures. E.g.

    #!/usr/bin/perl -w
    use strict;

    sub make_adder {
    my $addend = shift;
    sub {my $x = shift; $x + $addend}}

    my $adder = make_adder(3);
    print &$adder(2), "\n";

    IMHO not as nice as Lisp or ML, but there nonetheless.
  • i got it!

    10 print "please have a cup of coffee"
    20 compress data
    30 goto 10

  • It's nice to see that Microsoft supports some more advanced and academice computer science, after two decades of making fun of companies that did. I think most of the work on Haskell happened before the people involved got hired by Microsoft, so this isn't a sign yet of "Microsoft innovation" yet. But, there is hope.
  • by crealf ( 414283 ) on Friday July 27, 2001 @01:19AM (#2189970)
    A Python team is trying to solve the task:

    Everyone is welcome.

  • by gnovos ( 447128 ) <(gnovos) (at) (> on Thursday July 26, 2001 @11:41PM (#2189971) Homepage Journal
    print "
    <TITLE>404 Not Found</TITLE>
    <H1>Not Found</H1>
    The requested URL was not found on this server.
  • I think I will just submit cat(1). Should beat all others in the "correctness" and "speed of optimisation" department!
  • by SilentChris ( 452960 ) on Friday July 27, 2001 @04:16AM (#2189973) Homepage
    I might try to hack it in assembler on my TI-99/4A. :)

    By the way, what exactly do we win if we have the best entry?

  • ...but it might be hard to make it really fast. Maybe if you wrote it in assembly?

    A somewhat simple but slow way of doing it would be to create an array in which each non-tag character has a set of flags for bold, italic, whatever and a set of fields for color, size, etc. Then simply go through the newly created array and put in tags when ever the flags of fields change.

    It should be possible to optimize that... but I imagine significantly more efficient ways to do it will be found.

    I think this method will create highly optimized output... I can't think of anything to screw it up off the top of my head... but maybe I'm just missing something really obvious.

    Perhaps if some of the tags turn other tags off? I don't remember. That could screw it up.


Real programmers don't bring brown-bag lunches. If the vending machine doesn't sell it, they don't eat it. Vending machines don't sell quiche.