Re: WWW Page of Team PLClub (Re: ICFP programming contest: results)
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Pierre Weis <Pierre.Weis@i...> 
Subject:  Re: WWW Page of Team PLClub (Re: ICFP programming contest: results) 
> 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 betareduction is not a trivial kind of iteration (map or fold) on the basic one step betareducer (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 betareduction 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 doublechecked 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 betareducer (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 betareducer. 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 betareduction 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 betareduction 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/