Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!sm.unisys.com!randvax!narain
From: narain@randvax.UUCP (Sanjai Narain)
Newsgroups: comp.lang.prolog
Subject: Constraint satisfaction in LOG(F)
Message-ID: <1919@randvax.UUCP>
Date: 27 Mar 89 06:10:26 GMT
Organization: Rand Corp., Santa Monica, Ca.
Lines: 102

SEND+MORE=MONEY is not a good problem for exhibiting one of the main
virtues of constraint languages: that coroutining between generation and
testing is performed *automatically*.  It does not have to be programmed
by the user.

Programming coroutining can greatly obscure the logic of final program.
This is not so obvious with Prolog formulations of SMM.  For example,
Moss's first Prolog program contains coroutining, as it is verifying
addition from left to right while also generating the digits in the
summands.  Still, its logic is fairly close to that of its statement in
English.

Here is another problem where a solution in straight Prolog would not be
so clear.  Given a number K, and a set S of positive numbers, generate all
those subsets of S, the sum of whose members is equal to K.  Clearly, for
members U1,..,Uk of S, if their sum is greater than K, then generation of
all subsets of the form [U1,..,Uk|X] can be suppressed.  This can be
accomplished by coroutining between generation of subsets, and their
testing.

I now show how the problem can be stated in F*, without programming
coroutining. The coroutining is performed automatically, by lazy
evaluation. Curiously enough, Prolog itself is utilized, via compilation,
to accomplish this:

	subset([])=>[].
	subset([U|V])=>[U|subset(V)].
	subset([U|V])=>subset(V).

	sum_eq([],S,K)=>if_2(equal(S,K),[]).
	sum_eq([U|V],S,K)=>if_2((U+S)=<K,[U|sum_eq(V,S+U,K)]).

	if_2(true,X)=>X.

	ans=>sum_eq(subset([1,11,2,12,3,13,4,14,5,15,6,16,
			    7,17,8,18,9,19,10,20]),0,10).

The first three rules compute subsets of a list. The second two
rules determine whether S plus the sum of elements of a list
is equal to K. If so, they return the list itself, otherwise they
return nothing, and simply fail. Now, the term sum_eq(subset(S,0,K))
has as value precisely those subsets of S whose members add up to K.

Their compilation into Prolog is listed below.  Try reduce(ans,Z).  The
ten or so solutions are found in a breeze.  The total number of subsets is
2**20 (about a million), so exhaustive search would take quite long.

Thus, in LOG(F), one can program arbitrary constraints, not just
in a fixed domain. I am curious to see the formulation of this
problem, and the above optimization, in CLP, or CHIP.

Sanjai Narain

=============================================================================
:-op(650,xfx,=>).

reduce(true,true).
reduce(false,false).
reduce([],[]).
reduce([A|B],[A|B]).
reduce(ans,A) :-
        ans=>B,
        reduce(B,A).
reduce(subset(A),B) :-
        reduce(A,C),
        subset(C)=>D,
        reduce(D,B).
reduce(if_2(A,B),C) :-
        reduce(A,D),
        if_2(D,B)=>E,
        reduce(E,C).
reduce(solution(A,B),C) :-
        solution(A,B)=>D,
        reduce(D,C).
reduce(sum_eq(A,B,C),D) :-
        reduce(A,E),
        sum_eq(E,B,C)=>F,
        reduce(F,D).

subset([])=>[].
subset([A|B])=>[A|subset(B)].
subset([A|B])=>subset(B).
sum_eq([],A,B)=>if_2(C,[]) :-
        equal(A,B,C).
sum_eq([A|B],C,D)=>if_2(E,[A|sum_eq(B,F,D)]) :-
        G is A+C,
        less_than_equal(G,D,E),
        F is C+A.
ans=>sum_eq(subset([1,11,2,12,3,13,4,14,5,15,6,16,7,17,8,18,9,19,10,20]),0,10).
solution(A,B)=>sum_eq(subset(A),0,B).
if_2(true,A)=>A.

equal(A,A,true):-!.
equal(A,B,false).

less_than_equal(A,B,true):-A=<B,!.
less_than_equal(A,B,false).

make_list(X,Y):-reduce(X,Z),make_list_1(Z,Y).

make_list_1([],[]).
make_list_1([U|V],[U|Z]):-make_list(V,Z).