Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!lll-lcc!lll-winken!uunet!munnari!murtoa.cs.mu.oz.au!!lee
From: lee@.cs.mu.oz (Lee Naish)
Newsgroups: comp.lang.prolog
Subject: Re: Constraint satisfaction in LOG(F)
Message-ID: <1333@murtoa.cs.mu.oz.au>
Date: 4 Apr 89 02:09:04 GMT
References: <1919@randvax.UUCP>
Sender: news@cs.mu.oz.au
Reply-To: lee@munmurra.UUCP (Lee Naish)
Organization: University of Melbourne, Comp Sci Dept
Lines: 51

In article <1919@randvax.UUCP> narain@randvax.UUCP (Sanjai Narain) writes:
>	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).
>
>Their compilation into Prolog is listed below.  Try reduce(ans,Z).
Doesn't work - try make_list(ans, Z) (defined in the Prolog version)
instead!

Here is the equivalent NU-Prolog version.  Note that sum_eq is simpler
in Prolog because it is a simple test and doesn't have to return a
value.

subset([], []).
subset([A|B], [A|C]) :-
	subset(B, C).
subset([A|B], C) :-
	subset(B, C).

?- sum_eq(A, B, C) when A.
sum_eq([], A, A).
sum_eq([A|B], C, D) :-
	E is C + A,
	E =< D,
	sum_eq(B, E, D).

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

The code was run through a program called nac to add control information
automatically.  Nac is able to determine that sum_eq should only be
called when its first argument is instantiated, and that it is a test.
Nac therefore reorders the calls in ans so sum_eq is before subset and
the two calls will act as coroutines.  Under NU-Prolog, this code runs
about 4-5 times as fast as the transformed LOG(F) code.  The main
reasons are (probably) that it interpreted functions are not passed
around and clause indexing is better because the '=>' predicate in the
LOG(F) version really needs an extra level of indexing to make it as
efficient.  Because the control is so simple, it should be easy to get
this running under Sicstus, which would make it even faster.

	Lee Naish