Backtracking (Was: What do you think about Mercury?)

[Fergus Henderson]

On 09-Apr-2001, Jerzy Karczmarczuk <karczma@info.unicaen.fr> wrote:
> Fergus Henderson wrote:
> > The usual way of handling backtracking in Haskell is using lazy lists.
...
> This is a way to deal with *data backtracking*. Sure, most of 
> classical combinatoric algorithms belong to this category, the gene-
> ration of permutations/combinations, 8 queens, etc. And of course
> the non-deterministic parsing.
> 
> But there is also the question of *control backtracking*, used to
> emulate iterations, etc. This may be implemented functionally as
> well by using continuations.

Using continuations to implement backtracking is another important idiom,
I agree.  (In fact, that is how the new back-end for the Mercury compiler 
deals with backtracking Mercury code: it converts it into C (or IL, or Java)
code that uses continuation passing to handle the backtracing.)

However, in a lazy functional language, I'm not sure that you can so easily
or usefully distinguish between _control_ backtracking and _data_ backtracking.
In a lazy functional language the control flow is mainly implicit
rather than explicit, and is determined by the data flow.

> You may have conditional continuations, multiple continuations,... 

If you use other lazy data structures, e.g. lazy trees rather than lazy
lists, then you can do the same kinds of things that you could do using
conditional or multiple continuations.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.