ICFP programming contest: results

ICFP programming contest: results

[Xavier Leroy]

Here are the official results for the ICFP 2000 programming contest:

First prize: the PLClub team from University of Pennsylvania
(J. Vouillon, H. Hosoya, V. Gapeyev, E. Sumii).  Language used: OCaml.

Second prize: the Camls 'R Us team from INRIA Rocquencourt
(S. Ailleret, P. Cuoq, D. Doligez, R. Harley, F. Le Fessant, X. Leroy,
A. Schmitt).  Language used: OCaml.

Third place: the Galois Connection team from the start-up company with
the same name (J. Launchbury and 4 other persons whose names I
couldn't write down).  Language used: Haskell.

Fourth place: a team of 13 distributed among Australia, Belgium and
the UK, including F. Henderson.  Language used: Mercury.

Judge's prize for the best sample image: a chess game by team Helikopter
(A. Rossberg, L. Kornstaed) from U. Saarlandes (I think).

There were 39 entries, with teams ranging from 1 to 13 persons.
Breakdown by language used:

        C, C++          7
        Clean           1
        Dylan           1
        Eiffel          1
        Haskell         6
        Java            6
        Mercury         1
        ML              9
        Perl            2
        Python          1
        Scheme          2
        Smalltalk       2

Not a bad year for OCaml.  And my personal congratulations to Jérôme
Vouillon and his friends for a truly outstanding performance!

- Xavier Leroy

Re: ICFP programming contest: results

[Brock]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: TEXT/PLAIN; charset=X-UNKNOWN, Size: 470 bytes --]




On Thu, 21 Sep 2000, Xavier Leroy wrote:

> ...
> Second prize: the Camls 'R Us team from INRIA Rocquencourt
> (S. Ailleret, P. Cuoq, D. Doligez, R. Harley, F. Le Fessant, X. Leroy,
> A. Schmitt).  Language used: OCaml.
> ...
> 
> Not a bad year for OCaml.  And my personal congratulations to Jérôme
> Vouillon and his friends for a truly outstanding performance!
> 
> - Xavier Leroy
> 

And to you at the Camls 'R Us team as well.

--Brock

Re: ICFP programming contest: results

[Eijiro Sumii]

Thanks for kind words, and sorry for having been silent so far -- we
thought it would be more fun to keep silence until the official
announcement, especially when people weren't aware of us.;)

I heard the 3rd place entry was 100 times faster than the 4th, and the
2nd (Xavier's) was 5.5 times faster than the 3rd, but the 1st (ours)
wasn't so much faster than the 2nd.  Doesn't this mean Caml is a
_much_ better language than others---though the contest judge seemed
somewhat reluctant to say Caml is "a fine programming tool for many
applications" and "the programming tool of choice for discriminating
hackers"---or, at least, its developers are much better programmers
than others?:-)  (Jerome was the main programmer in our team, and his
coding was amazingly fast.)

By the way, we are going to make a web page to describe what we did in
detail.  We'll announce it in this list when it's ready.

// Eijiro Sumii (http://www.yl.is.s.u-tokyo.ac.jp/~sumii/)
// 
// Ph.D. Student at Department of IS, University of Tokyo
// Visiting Scholar at Department of CIS, University of Pennsylvania

> From: Xavier Leroy <Xavier.Leroy@inria.fr>
> Subject: ICFP programming contest: results
> Date: Thu, 21 Sep 2000 09:12:56 +0200
> 
> Here are the official results for the ICFP 2000 programming contest:
...
> Not a bad year for OCaml.  And my personal congratulations to Jérôme
> Vouillon and his friends for a truly outstanding performance!
> 
> - Xavier Leroy

Re: ICFP programming contest: results

[Jean-Francois Monin]

Your web page will be of great interest.

Could you also tell us to what extent the knowledge of the
implementation of Ocaml was needed in order to get good performance ?

-- 
Jean-Francois Monin, France Telecom R&D DTL/MSV, Tel +33 2 96 05 26 79
2 av. Pierre Marzin, 22307 Lannion, France       Fax +33 2 96 05 39 45

-- 
Eijiro Sumii wrote :
 > Thanks for kind words, and sorry for having been silent so far -- we
 > thought it would be more fun to keep silence until the official
 > announcement, especially when people weren't aware of us.;)
 > 
 > I heard the 3rd place entry was 100 times faster than the 4th, and the
 > 2nd (Xavier's) was 5.5 times faster than the 3rd, but the 1st (ours)
 > wasn't so much faster than the 2nd.  Doesn't this mean Caml is a
 > _much_ better language than others---though the contest judge seemed
 > somewhat reluctant to say Caml is "a fine programming tool for many
 > applications" and "the programming tool of choice for discriminating
 > hackers"---or, at least, its developers are much better programmers
 > than others?:-)  (Jerome was the main programmer in our team, and his
 > coding was amazingly fast.)
 > 
 > By the way, we are going to make a web page to describe what we did in
 > detail.  We'll announce it in this list when it's ready.
 > 
 > // Eijiro Sumii (http://www.yl.is.s.u-tokyo.ac.jp/~sumii/)
 > // 
 > // Ph.D. Student at Department of IS, University of Tokyo
 > // Visiting Scholar at Department of CIS, University of Pennsylvania
 > 
 > > From: Xavier Leroy <Xavier.Leroy@inria.fr>
 > > Subject: ICFP programming contest: results
 > > Date: Thu, 21 Sep 2000 09:12:56 +0200
 > > 
 > > Here are the official results for the ICFP 2000 programming contest:
 > ...
 > > Not a bad year for OCaml.  And my personal congratulations to Jérôme
 > > Vouillon and his friends for a truly outstanding performance!
 > > 
 > > - Xavier Leroy

Re: ICFP programming contest: results

[Xavier Leroy]

> Could you also tell us to what extent the knowledge of the
> implementation of Ocaml was needed in order to get good performance ?

The only important thing to know was that a record with three float
fields is more efficient than a triple of floats.

Actually, all you needed to know (and much more) about the OCaml
performance model for the contest is documented in the OCaml
"Questions and answers" pages, especially
        http://caml.inria.fr/ocaml/speed.html
and
        http://caml.inria.fr/ocaml/numerical.html

- Xavier Leroy

WWW Page of Team PLClub (Re: ICFP programming contest: results)

[eijiro_sumii]

Dear Camlers,

> By the way, we are going to make a web page to describe what we did in
> detail.  We'll announce it in this list when it's ready.

Here it is.

  http://www.cis.upenn.edu/~sumii/icfp/

Enjoy,

Team PLClub

P.S.  Could you please add a link to the web page above in the contest
result page (http://www.cs.cornell.edu/icfp/contest_results.htm), Greg?

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[malc]

On Wed, 4 Oct 2000 eijiro_sumii@anet.ne.jp wrote:

> Dear Camlers,
> 
> > By the way, we are going to make a web page to describe what we did in
> > detail.  We'll announce it in this list when it's ready.
> 
> Here it is.
> 
>   http://www.cis.upenn.edu/~sumii/icfp/
> 
> Enjoy,
> 
> Team PLClub
> 
> P.S.  Could you please add a link to the web page above in the contest
> result page (http://www.cs.cornell.edu/icfp/contest_results.htm), Greg?
> 
> 
Duh! It cant even handle 1e-3! It enters endless loop on
http://caml.inria.fr/icfp00-contest/images/kal.gml, what a piece of ... :)
Just kidding, great work, rendered adrenalin at the speed i cant even
dream of.

But can someone of your team describe the rationale behind usage of arrays
as representation of matrices/vectors, likewise it will be also intersting
to hear corresponding rationale behind record based version of Caml's R Us
implementation.
 
-- 
mailto:malc@pulsesoft.com

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[Julian Assange]

> But can someone of your team describe the rationale behind usage of arrays
> as representation of matrices/vectors, likewise it will be also intersting
> to hear corresponding rationale behind record based version of Caml's R Us
> implementation.
>  
> -- 
> mailto:malc@pulsesoft.com

There's no use of Ocaml's objective features either. Jerome, can you comment
on that? The classes of 3d shapes were represented as types, for instance.
As the `O' in Ocaml, when do you think it is appropriate to use the objective
style? 

Cheers,
Julian.

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[eijiro_sumii]

> It cant even handle 1e-3!

We're sorry about that...:-)

> It enters endless loop on http://caml.inria.fr/icfp00-contest/images/kal.gml

It doesn't.  It's just slow for images like kal, because we forgot to
implement reflection cutting (as Camls 'R Us did).

Eijiro

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[eijiro_sumii]

P.S.

> But can someone of your team describe the rationale behind usage of arrays
> as representation of matrices/vectors,

(It was Jerome who decided that, but anyway...)  The reason was
convenience: we could write matrix/vector multiplication by using
for-loops, for instance.  As for the efficiency,
"records > tuples = arrays (without boundary checks)" and as for the
safety, "records = tuples > arrays", I suppose.

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[eijiro_sumii]

Oops, sorry,

> It doesn't.  It's just slow for images like kal, because we forgot to
> implement reflection cutting (as Camls 'R Us did).

I mean, Camls 'R Us did implement reflection cutting but we didn't.

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[eijiro_sumii]

> > (It was Jerome who decided that, but anyway...)  The reason was
> > convenience: we could write matrix/vector multiplication by using
> > for-loops, for instance.  As for the efficiency,
> > "records > tuples = arrays (without boundary checks)" and as for the
> > safety, "records = tuples > arrays", I suppose.

Oh, sorry, I meant "to represent matrices and vectors" only.

> Not exactly, for efficiency:
> 
> records = tuples = array without boundary checks

Excuse me, but I'm a bit confused here...  What did Xavier mean in the
message below then?

| Subject: Re: ICFP programming contest: results
| From: Xavier Leroy <Xavier.Leroy@inria.fr>
| Date: Tue, 26 Sep 2000 10:55:21 +0200
| 
| > Could you also tell us to what extent the knowledge of the
| > implementation of Ocaml was needed in order to get good performance ?
| 
| The only important thing to know was that a record with three float
| fields is more efficient than a triple of floats.

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[Pierre Weis]

> > Not exactly, for efficiency:
> > 
> > records = tuples = array without boundary checks
> 
> Excuse me, but I'm a bit confused here...  What did Xavier mean in the
> message below then?
> 
> | Subject: Re: ICFP programming contest: results
> | From: Xavier Leroy <Xavier.Leroy@inria.fr>
> | Date: Tue, 26 Sep 2000 10:55:21 +0200
> | 
> | > Could you also tell us to what extent the knowledge of the
> | > implementation of Ocaml was needed in order to get good performance ?
> | 
> | The only important thing to know was that a record with three float
> | fields is more efficient than a triple of floats.

Oups, sorry. There is a special treatment in the compiler for float
arrays and float records but no one for float tuples. So for the special
case of floats, array and record are more efficient than tuples. For
all other types there is no difference in efficiency.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[Pierre Weis]

> Pierre Weis wrote:
> 
> > the body of f. This operation is trivial if you use a conventional
> > beta reducer, but it is surprisingly difficult if you use De Bruijn
> > indices.
> 
> 	Just out of curiousity, what do you mean
> by a 'difficult' algorithm?

I did not mention the word algorithm. I meant here that implementing
the parallel beta-reduction is not a trivial kind of iteration (map or
fold) on the basic one step beta-reducer (if you do want to obtain a
one pass reduction).

BTW (joking):

Definition: an algorithm is said to be difficult iff it it not
trivial to implement in Caml !

> 	To explain my question in slightly more depth: given
> some fixed problems with known algorithms, all these algorithms,
> in the first instance, have equal 'difficulty', namely,  'trivial':
> if the algorithm is known, it can be implemented. (In general,
> coding a known algorithm is so easy compared with other programming
> tasks that I would classify coding by how laborious it is: the only
> 'difficulty' involved is staying awake long enough to finish the job :-)

So, let's me tell a story about this ``difficult'' problem: having
problems to implement the parallel beta-reduction using the De Bruijn
indices, I looked in the litterature and found a thesis that claimed
to specify this transformation and used it in the rest of the
thesis. So, I turned the specification into a piece of Caml program;
it gave wrong answers. Fortunately, I had the thesis's author at hand;
hence, we sat together at the terminal and double-checked the
implementation wrt the specification; we were not able to find any
discrepancy in the program; then we changed the specification; then we
changed the program accordingly; it was still giving wrong answers on
some examples!

I gave up, and revert to multiple calls to the beta-reducer (and
accordingly to inefficient multiple rewritings of the function body).

I do not claim this problem is impossible to solve; I just claimed it
is ``surprisingly difficult'' compared to the trivial solution you
give to the same problem when you use a conventional beta-reducer.  It
is at least so difficult that a carefully written thesis may give a
wrong specification of the solution, even if it has been reviewed by
experts of the domain.

I think the De Bruijn indices solution to this problem may not be
worth the efforts it needs.

> 	It is sometimes difficult to _find_ an algorithm for a problem,
> and one may say that some algorithms are 'inflexible' in the sense
> that small variations in the problem make finding a solution
> by considering the 'original' algorithm difficult.

That's exactly what I observed for parallel beta-reduction in one pass.

> 	It may also be hard to tranform a correct algorithm into
> a more efficient version.

That's exactly the intention in using parallel beta-reduction in one pass.

> 	Also, it is clear that some algorithms are difficult to
> understand. And, some algorithms, coded incorrectly, may be difficult
> to debug.

Also true with De Bruijn indices transformations.

So, this problem meets all your criteria: that's why I think we can
say ``it is a surprisingly difficult problem''.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[Benjamin Pierce]

Fanning the fire on deBruijn indices...

> - you have to manipulate indices anyway to mimmick alpha-conversion
> when performing beta-reduction (the operation is named the ``lifting''
> of De Bruijn indices), and you know that this is at least as difficult
> and error prone as performing alpha-renaming. As an example, consider
> ...

There's an important difference, though, in the ways that these errors
show up: bugs in deBruijn-indexing schemes tend to manifest immediately
and catastrophically -- if you miss a 'shift' everything quickly gets all
screwed up and you can see that you did something wrong and fix it right
away -- while name-based implementations of substitution tend to fail
only six months later, when someone makes an unlucky choice of variable
names. 

There's a story that a substitution bug in the original LCS theorem
prover persisted for six *years* before anybody noticed...

> - as a consequence of these two properties, debugging code that
> manipulates and transforms lambda code in De Bruijn form is just a
> nightmare (each time I had to do it, I ended by writing a
> pretty-printer that reverts De Bruijn notation to good old names for
> variables!)

I usually do this too.  The pretty-printer can also do a little
consistency checking on the deBruijn indices: each variable is
represented as a pair of its index and the expected size of the context;
if the printing routine sees that the actual context does not have this
size, it complains.  

One drawback of deBruijn indices that you did not mention is that, at
least when implemented naively, they are pretty expensive in terms of
the amount of consing that's required to perform substitutions. 

At the end of the day, I'm not that big a fan of *either* deBruijn or
named presentations of terms... both are pretty ugly to work with, in
different ways.  In fact, I find both distressing and fascinating that,
after so many years of thought by so many smart people, we're still in
such an unsatisfactory state wrt. binding.

    B

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[John Max Skaller]

Pierre Weis wrote:

> the body of f. This operation is trivial if you use a conventional
> beta reducer, but it is surprisingly difficult if you use De Bruijn
> indices.

	Just out of curiousity, what do you mean
by a 'difficult' algorithm?

	To explain my question in slightly more depth: given
some fixed problems with known algorithms, all these algorithms,
in the first instance, have equal 'difficulty', namely,  'trivial':
if the algorithm is known, it can be implemented. (In general,
coding a known algorithm is so easy compared with other programming
tasks that I would classify coding by how laborious it is: the only
'difficulty' involved is staying awake long enough to finish the job :-)

	It is sometimes difficult to _find_ an algorithm for a problem,
and one may say that some algorithms are 'inflexible' in the sense
that small variations in the problem make finding a solution
by considering the 'original' algorithm difficult.

	It may also be hard to tranform a correct algorithm into
a more efficient version.

	Also, it is clear that some algorithms are difficult to
understand. And, some algorithms, coded incorrectly, may be difficult
to debug.
 
-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[Pierre Weis]

> Markus Mottl wrote:

> On Sat, 07 Oct 2000, Pierre Weis wrote:
> > Also consider that the Caml Light compiler does not optimize and
> > symbolycally manipulate programs: that's devoted to the next ``tour de
> > force'', the Objective Caml optimizing compiler, which does not use
> > the De Bruijn indices notation for lambda terms...
> 
> This sounds interesting! - May I ask what optimisations are considered?

Classical: inlining, type-directed optimizations for primitives,
compile time beta-reductions, constant folding, ...

A bit more hairy: direct calls to functions (including curried
functions and functions whose argument is a tuple), 0-cfa like
analysis to access globals in modules, ...

Xavier is the right man to tell you what's going on inside the compiler,
but you can also read the compiler's source files ...

> Will there be documentation for the (new) intermediate representation on
> which optimisations operate? It would be really important to have
> information about side effects there, too.

Yes, you need a purity analysis for some of those optimizations...

> I could imagine playing around with such representations in LambdaProlog
> (extremely convenient for prototyping transformation systems). I don't know
> whether anything useful will come out, but it may be fun - for others as
> well.

I'm sure many people will be interested at reading your code and
conclusions about implementing transformations in Lambdaprolog ...

Best regards,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[Markus Mottl]

On Sat, 07 Oct 2000, Pierre Weis wrote:
> Also consider that the Caml Light compiler does not optimize and
> symbolycally manipulate programs: that's devoted to the next ``tour de
> force'', the Objective Caml optimizing compiler, which does not use
> the De Bruijn indices notation for lambda terms...

This sounds interesting! - May I ask what optimisations are considered?
Will there be documentation for the (new) intermediate representation on
which optimisations operate? It would be really important to have
information about side effects there, too.

I could imagine playing around with such representations in LambdaProlog
(extremely convenient for prototyping transformation systems). I don't know
whether anything useful will come out, but it may be fun - for others as
well.

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[Pierre Weis]

Xavier explained de Bruijn indices

> Notice that a de Bruijn index is relative to the position of the
> variable reference.  Hence the same variable can be referenced by
> different de Bruijn indices depending on context, e.g.
> 
>         fun x -> print_int x; fun y -> x + y
> 
> becomes
>         fun -> print_int var0; fun -> var1 + var0
>                          ^^^^         ^^^^
>                        this is x     this is x too!
> 
> De Bruijn indices are interesting for several reasons.  One is
> that they totally eliminate any alpha-conversion problems: expressions
> have unique representations, without any need to work modulo renaming of
> bound variables; moreover, substitution of variables by non-closed
> expressions works very well, without any risk of name clashes as in
> the normal, name-based notation.
> 
> Another reason is that if you represent the evaluation environment as
> a stack, with each new binding simply pushing the bound value on top,
> then the de Bruijn index for a variable is simply the position of the
> variable's value in the stack, relative to the top of the stack.
> (Substitute "list" for "stack" to deal with persistent, heap-allocated
> environments, e.g. for closures.)  This leads to very simple
> translations into abstract machine code.

All this is perfectly true and correct, but in my humble opinion you
forgot to mention the dark side of De Bruijn indices:

- they are perfect for machines but not convenient for human beings!
(We cannot easily consider that the same variable have plenty of
different names in an expression.)

- you have to manipulate indices anyway to mimmick alpha-conversion
when performing beta-reduction (the operation is named the ``lifting''
of De Bruijn indices), and you know that this is at least as difficult
and error prone as performing alpha-renaming. As an example, consider
the parallel (or multiple) beta-reduction: the problem is to calculate
f e1 e2 ... en by substituting e1 e2 ... en, in the body of f,
supposed to be defined by lambda expression with n binders fun -> fun
-> ... -> body. The problem is to perform the reduction in one pass on
the body of f. This operation is trivial if you use a conventional
beta reducer, but it is surprisingly difficult if you use De Bruijn
indices.

- as a consequence of these two properties, debugging code that
manipulates and transforms lambda code in De Bruijn form is just a
nightmare (each time I had to do it, I ended by writing a
pretty-printer that reverts De Bruijn notation to good old names for
variables!)

That's why I consider a ``tour de force'' the Caml Light compiler that
uses De Bruijn indices for the whole language. However, remember the
famous ``De Bruijn wins again!'' leitmotiv we used to ear in the
building when someone was desesperately fighting with wrong indices
generated by the compiler!

Also consider that the Caml Light compiler does not optimize and
symbolycally manipulate programs: that's devoted to the next ``tour de
force'', the Objective Caml optimizing compiler, which does not use
the De Bruijn indices notation for lambda terms...

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[eijiro_sumii]

> > Could you provide a reference to de Bruijin indexing?

Xavier kindly gave a nice explanation.:) Thanks!

> On a related note, how would that compare (performancewise) to an
> approach like "abstract syntax" (represent a function not
> as (<id>, <exp>) and neither as <exp> (as in the case of deBruijn)
> but as fn x => <exp>) ?

As far as I know, to use that "higher-order abstract syntax" approach,
we have to _translate_ a GML program into a Caml code and evaluate it
at runtime.  That is exactly what I did in the "compiling" version
(PLClubCN) of our entry, but it didn't work well because the
compilation itself (including ocamlopt.opt) took some time, which
didn't pay.

Eijiro

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[Xavier Leroy]

David McClain asks:

> Could you provide a reference to de Bruijin indexing? I recall reading about
> it some time ago, and after having searched my books here, I cannot find any
> references to it.

The idea behind de Bruijn indices is to represent variable references
not by name, but by the number of binders to cross to get at the
binder for the variable in question.  An example shoud make this
clearer:

        fun x -> fun y -> x + y

is represented in de Bruijn notation as

        fun -> fun -> var1 + var0

"var1" means "go up one binder", so this refers to the variable bound
by the first "fun".
"var0" means "go to the closest binder", so this refers to the
variable bound by the second "fun".

Notice that a de Bruijn index is relative to the position of the
variable reference.  Hence the same variable can be referenced by
different de Bruijn indices depending on context, e.g.

        fun x -> print_int x; fun y -> x + y

becomes
        fun -> print_int var0; fun -> var1 + var0
                         ^^^^         ^^^^
                       this is x     this is x too!

De Bruijn indices are interesting for several reasons.  One is
that they totally eliminate any alpha-conversion problems: expressions
have unique representations, without any need to work modulo renaming of
bound variables; moreover, substitution of variables by non-closed
expressions works very well, without any risk of name clashes as in
the normal, name-based notation.

Another reason is that if you represent the evaluation environment as
a stack, with each new binding simply pushing the bound value on top,
then the de Bruijn index for a variable is simply the position of the
variable's value in the stack, relative to the top of the stack.
(Substitute "list" for "stack" to deal with persistent, heap-allocated
environments, e.g. for closures.)  This leads to very simple
translations into abstract machine code.

Stefan Monnier asks:

> On a related note, how would that compare (performancewise) to an
> approach like "abstract syntax" (represent a function not
> as (<id>, <exp>) and neither as <exp> (as in the case of deBruijn)
> but as fn x => <exp>) ?

My feeling is that higher-order abstract syntax isn't applicable to
the GML language, because the language has variable assignment, which
I don't see how to fit in the h.o.a.s. representation.

- Xavier Leroy

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[David McClain]

I would think that you would get into trouble with a closure representation
because there is no equality operation defined on them, and you would have
to evaluate the closure to obtain the value representing the name... that
sounds overly expensive in time and space.

- DM

-----Original Message-----
From: Stefan Monnier <monnier+lists/caml/news/@RUM.CS.YALE.EDU>
Newsgroups: lists.caml
To: caml-list@inria.fr <caml-list@inria.fr>
Date: Thursday, October 05, 2000 1:35 PM
Subject: Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)


>>>>>> "David" == David McClain <dmcclain@azstarnet.com> writes:
>> Could you provide a reference to de Bruijin indexing? I recall reading
about
>
>On a related note, how would that compare (performancewise) to an
>approach like "abstract syntax" (represent a function not
>as (<id>, <exp>) and neither as <exp> (as in the case of deBruijn)
>but as fn x => <exp>) ?
>
>
>        Stefan
>

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[Stefan Monnier]

>>>>> "David" == David McClain <dmcclain@azstarnet.com> writes:
> Could you provide a reference to de Bruijin indexing? I recall reading about

On a related note, how would that compare (performancewise) to an
approach like "abstract syntax" (represent a function not
as (<id>, <exp>) and neither as <exp> (as in the case of deBruijn)
but as fn x => <exp>) ?


        Stefan

Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)

[David McClain]

Hi, Congratulations!!!!

Could you provide a reference to de Bruijin indexing? I recall reading about
it some time ago, and after having searched my books here, I cannot find any
references to it. So I probably saw it in a paper some time ago... Anyway, I
would be interested since I have an interpreter name-lookup problem here
too.

Thanks in advance,

Congrats!!!

- David McClain

-----Original Message-----
From: eijiro_sumii@anet.ne.jp <eijiro_sumii@anet.ne.jp>
To: caml-list@inria.fr <caml-list@inria.fr>
Cc: jgm@cs.cornell.edu <jgm@cs.cornell.edu>; vouillon@saul.cis.upenn.edu
<vouillon@saul.cis.upenn.edu>; vgapeyev@seas.upenn.edu
<vgapeyev@seas.upenn.edu>; hahosoya@saul.cis.upenn.edu
<hahosoya@saul.cis.upenn.edu>; sumii@saul.cis.upenn.edu
<sumii@saul.cis.upenn.edu>
Date: Wednesday, October 04, 2000 10:26 PM
Subject: WWW Page of Team PLClub (Re: ICFP programming contest: results)


>Dear Camlers,
>
>> By the way, we are going to make a web page to describe what we did in
>> detail.  We'll announce it in this list when it's ready.
>
>Here it is.
>
>  http://www.cis.upenn.edu/~sumii/icfp/
>
>Enjoy,
>
>Team PLClub
>
>P.S.  Could you please add a link to the web page above in the contest
>result page (http://www.cs.cornell.edu/icfp/contest_results.htm), Greg?
>