[Haskell-cafe] Logic programming using lazy evaluation

[Henning Thielemann]

On Tue, 27 Feb 2007, Ulf Norell wrote:

> On 2/27/07, Henning Thielemann <lemming at henning-thielemann.de> wrote:
> >
> > I suspect that someone has already done this: A Haskell library which
> > solves a system of simple equations, where it is only necessary to derive
> > a value from an equation where all but one variables are determined. Say
>
> You might want to check out the following paper:
>
> http://www.cs.chalmers.se/~koen/pubs/entry-haskell00-typedlp.html

Thanks for the link!
It reminds me, that my problem differs from usual logic programming.
I'm not interested in multiple solutions, I expect only one.
If a variable is underdetermined, it shall be evaluated to "undefined".
If a variable is overdetermined,
that is different rules lead to different values for that variable,
one of these values shall be returned.
Checking for consistency per variable would require processing the whole
(possibly infinite) list of rules.
Instead one could check consistency per rule.
That is, the solver should return a list of Bools
which indicate which rules could be satisfied.
In this setting it should be possible to solve the equations lazily.

In contrast to the paper
I assume that I can neither use Int variable identifiers nor STRefs
because they would prevent the garbage collector
from freeing unreferenced variable substitutions.