gsat, Mercury vs functional languages, nondeterminism

[Don Smith]

Hi,

Henk wrote:
> I believe there is nothing wrong with Mercury to implement
> GSAT-algorithm based on probabilistic methods. 

Thank you for the program code. I did "grep det gsat.m."  Here's what I
got back:

:- pred main(io__state::di, io__state::uo) is det.
:- mode start(in, in, in, array_di, array_uo, in, in, mdi, in, in, out, out) is det.
:- mode start_climb(in, in, array_di, array_uo, in, out, mdi, muo, in, out) is det.
:- mode climb(in, array_di, array_uo, mdi, muo) is det.
:- mode catch(in, in, out) is det.
:- mode flip(in, array_di, array_uo) is det.
:- mode climb_iter(in, in, in, in, out, in, array_di, array_uo) is det.
:- mode check(in, array_ui, out) is det.
:- mode check_disj(in, array_ui) is semidet.
:- mode read_formula(in, out, out, out, out, di, uo) is det.
:- mode read_token(in, out, in, out, in, out, di, uo) is det.
:- mode read_formula(in, out, in, out, in, out, out, di, uo) is det.

It didn't even use Mercury's backtracking.

Tyson wrote:
> You don't pay anything for non-determinism if you don't use it.

That's my point:  few applications even need Mercury's nondeterminism. :(

But you won't pay for it only so long as Mercury's support for full
unification doesn't infect the deterministic code with overhead.  I can
see why the Mercury designers want to start with a simple language. But
so many applications need really expressive support for things like
unification, intelligent backtracking, stateful computation, and
randomness.  Unfortunately there's no free lunch.  (But there sure are
over-priced lunches.)

Fergus wrote:
> OK, so your next question is why use Mercury rather than ML?
> ... ML does of course provide imperative features such as 
> destructive update, but it doesn't give them a declarative interface.

OK, so how about a pure, eager functional language?  Pure ML with linear
types/monads. Or eager Haskell.  (Is it possible? How essential is 
laziness for monads?)

"Well," you may say, "Mercury is pure and has an eager functional
sublanguage." I wonder how many Haskell/ML applications Mercury can
usurp.  But I'm wondering, on the one hand, if Mercury has the right
sort of backtracking/search primitives for AI applications, and on the
other hand whether search is used enough in mainstream applications to
make Mercury worth it for them.

  Don