> 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/