From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA05014 for caml-red; Tue, 10 Oct 2000 12:36:51 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id MAA04148 for ; Tue, 10 Oct 2000 12:23:11 +0200 (MET DST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e9AAN1j14168; Tue, 10 Oct 2000 12:23:01 +0200 (MET DST) Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA04317; Tue, 10 Oct 2000 12:23:00 +0200 (MET DST) From: Pierre Weis Message-Id: <200010101023.MAA04317@pauillac.inria.fr> Subject: Re: WWW Page of Team PLClub (Re: ICFP programming contest: results) In-Reply-To: <39E0E68F.B2786DE7@ozemail.com.au> from John Max Skaller at "Oct 9, 100 08:26:39 am" To: skaller@ozemail.com.au (John Max Skaller) Date: Tue, 10 Oct 2000 12:23:00 +0200 (MET DST) Cc: caml-list@inria.fr X-Mailer: ELM [version 2.4ME+ PL28 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: weis@pauillac.inria.fr > 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/