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

[Jerzy Karczmarczuk]

Fergus Henderson wrote:

> On 08-Apr-2001, Terrence Brannon wrote:
> >
> > 1- Haskell is a pure functional language, but I don't see any support
> > for backtracking or other logic features... but my guess is you have
> > some way of handling this? How?
> 
> The usual way of handling backtracking in Haskell is using lazy lists.
> See Phil Wadler's 1985 paper [1].
> 
> For an example of this, I've attached a program for solving the
> 8-queens problem; you can compare this one with the Mercury version
...

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. You may have conditional continuations,
multiple continuations,... 
Unfortunately such techniques are rarely taught.

I suspect that Mark Jones' Prolog implementation in Haskell/Gofer
used them, but I don't remember the details.


Jerzy Karczmarczuk
Caen, France