Declarative loops and list comprehensions
afa
After adding into B-Prolog 7.4 the foreach built-ins for describing
loops and the list comprehension notation for constructing lists, I
felt that these constructs could benefit Prolog in general. Therefore,
I have made the updated interpreter available at:
http://probp.com/download/foreach.pl
It can easily be ported to other Prolog systems. B-Prolog compiles
foeach and list comprehensions into tail-recursive predicates. The
command compile_foreach(File) outputs the translated matching clauses.
Here are several examples that illustrate the power of these new
constructs:
qsort([],[]).
qsort([H|T],S):-
L1 @= [X : X in T, X<H],
L2 @= [X : X in T, X>=H],
qsort(L1,S1),
qsort(L2,S2),
append(S1,[H|S2],S).
perms([],[[]]).
perms([X|Xs],Ps):-
perms(Xs,Ps1),
Ps @= [P : P1 in Ps1, I in 0..Xs^length,[P],insert(X,I,P1,P)].
insert(X,0,L,[X|L]).
insert(X,I,[Y|L1],[Y|L]):-
I>0,
I1 is I-1,
insert(X,I1,L1,L).
queens(N):-
length(Qs,N),
Qs :: 1..N,
foreach(I in 1..N-1, J in I+1..N,
(Qs[I] #\= Qs[J],
abs(Qs[I]-Qs[J]) #\= J-I)),
labeling([ff],Qs),
writeln(Qs).
bool_queens(N):-
new_array(Qs,[N,N]),
Vars @= [Qs[I,J] : I in 1..N, J in 1..N],
Vars :: 0..1,
foreach(I in 1..N,
sum([Qs[I,J] : J in 1..N]) #= 1),
foreach(J in 1..N,
sum([Qs[I,J] : I in 1..N]) #= 1),
foreach(K in 1-N..N-1,
sum([Qs[I,J] : I in 1..N, J in 1..N, I-J=:=K]) #=< 1),
foreach(K in 2..2*N,
sum([Qs[I,J] : I in 1..N, J in 1..N, I+J=:=K]) #=< 1),
labeling(Vars),
foreach(I in 1..N,[Row],
(Row @= [Qs[I,J] : J in 1..N], writeln(Row))).
More examples are available at:
http://probp.com/examples/index.html#FOREACH.
The manual hasn't been updated to reflect these new constructs, but a
short article on them is available at:
http://probp.com/download/loops.pdf
Comments and suggestions are welcome.
Cheers,
Neng-Fa
Paulo Moura
> Hi,
>
> After adding into B-Prolog 7.4 the foreach built-ins for describing
> loops and the list comprehension notation for constructing lists, I
> felt that these constructs could benefit Prolog in general. Therefore,
> I have made the updated interpreter available at:
>
> http://probp.com/download/foreach.pl
>
> It can easily be ported to other Prolog systems. B-Prolog compiles
> foeach and list comprehensions into tail-recursive predicates. The
> command compile_foreach(File) outputs the translated matching clauses.
>
> Here are several examples that illustrate the power of these new
> constructs:
>
> qsort([],[]).
> qsort([H|T],S):-
> L1 @= [X : X in T, X<H],
> L2 @= [X : X in T, X>=H],
> qsort(L1,S1),
> qsort(L2,S2),
> append(S1,[H|S2],S).
I would drop the example above. I find list comprehensions a nice
notation but Quicksort is a "hard split/easy join" sorting algorithm.
I.e. the sorting work is performed when partition the list elements
using a pivot. Above, the list T is traversed twice in order to
perform the partition at each recursive step.
Cheers,
Paulo
afa
> On Jan 5, 3:35 pm, afa <neng.z...@gmail.com> wrote:
>
> I would drop the example above. I find list comprehensions a nice
> notation but Quicksort is a "hard split/easy join" sorting algorithm.
qsort is a direct translation of a Haskell version. FP people always
boast that qsort can be described in two lines in Haskell. The Prolog
version is not as short as the Haskell one but is comparable in terms
of programming efforts.
I think list comprehension should be in the Prolog standard with some
sort of built-ins for loops. Now even Python supports it. You could
imagine how difficult it would be to write programs like bool_queens
without using list comprehension (the generated code of bool_queens in
standard Prolog syntax is almost ten times longer).
Cheers,
Neng-Fa
Markus Triska
thank you very much for making your interpreter available!
afa <neng...@gmail.com> writes:
> qsort is a direct translation of a Haskell version. FP people always
> boast that qsort can be described in two lines in Haskell. The Prolog
> version is not as short as the Haskell one but is comparable in terms
> of programming efforts.
I like the qsort example and suggest the following DCG version:
qsort([]) --> [].
qsort([L|Ls]) -->
{ L1 @= [X : X in Ls, X < L],
L2 @= [X : X in Ls, X >= L] },
qsort(L1), [L], qsort(L2).
--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
bart demoen
> qsort is a direct translation of a Haskell version. FP people always
> boast that qsort can be described in two lines in Haskell.
The recursive clause in Haskell is indeed one line
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
When written in (what I consider) better Haskell, it becomes:
qsort (x:xs) =
let low = (filter (< x) xs)
high = (filter (>= x) xs)
sortedlow = qsort low
sortedhigh = qsort high
in
sortedlow ++ (x:sortedhigh)
Not so short anymore.
> The Prolog version is not as short as the Haskell one but is comparable
> in terms of programming efforts.
The version you refer to has
qsort([],[]).
qsort([H|T],S):-
L1 @= [X : X in T, X<H],
L2 @= [X : X in T, X>=H],
qsort(L1,S1),
qsort(L2,S2),
append(S1,[H|S2],S).
I cannot see how this is shorter (in number of lines) than
qsort([],[]).
qsort([H|T],S):-
findall(X,(member(X,T), X<H),L1),
findall(X,(member(X,T), X>=H),L2),
qsort(L1,S1),
qsort(L2,S2),
append(S1,[H|S2],S).
Do you prefer functional notation, so that shorter (and more obscure)
programs can be written ? Ciao lets you do that: it's just syntax.
> I think list comprehension should be in the Prolog standard
Prolog had list comprehensions (findall) before Haskell or Python existed.
We just don't have a fancy syntax for them and most of all, we lack
equational reasoning on them. And that's partly due to not having modes
in Prolog. Does the list-comprehension syntax imply something about modes ?
If so, can someone make that explicit so that we can see the difference
between findall and list-comprehensions ? If not, is this "just" about syntax ?
Cheers
Bart Demoen
ps. <just_my_opinion> the DCG version by Markus is horrible </just_my_opinion>
Paulo Moura
> On Jan 8, 11:53 am, Paulo Moura <pjlmo...@gmail.com> wrote:
>
> > On Jan 5, 3:35 pm, afa <neng.z...@gmail.com> wrote:
>
> > I would drop the example above. I find list comprehensions a nice
> > notation but Quicksort is a "hard split/easy join" sorting algorithm.
>
> qsort is a direct translation of a Haskell version. FP people always
> boast that qsort can be described in two lines in Haskell. The Prolog
> version is not as short as the Haskell one but is comparable in terms
> of programming efforts.
What's the point of looking for a reduced number of lines of code when
you're *duplicating* the number of steps that will take to sort a
list?
In fact, this Quicksort example is perfect to illustrate the dangers
of fancy syntax when coding by botching up the computational
complexity of the implemented algorithm.
Cheers,
Paulo
Paulo Moura
> qsort is a direct translation of a Haskell version. FP people always
> boast that qsort can be described in two lines in Haskell. The Prolog
> version is not as short as the Haskell one but is comparable in terms
> of programming efforts.
Just for comparison, follows a no-frils, computational complexity
aware version:
quicksort(List, Sorted) :-
quicksort(List, [], Sorted).
quicksort([], Sorted, Sorted).
quicksort([Pivot| Rest], Acc, Sorted) :-
partition(Rest, Pivot, Smaller0, Bigger0),
quicksort(Smaller0, [Pivot| Bigger], Sorted),
quicksort(Bigger0, Acc, Bigger).
partition([], _, [], []).
partition([X| Xs], Pivot, Smalls, Bigs) :-
( X < Pivot ->
Smalls = [X| Rest],
partition(Xs, Pivot, Rest, Bigs)
; Bigs = [X| Rest],
partition(Xs, Pivot, Smalls, Rest)
).
A decent meta-predicate library will give you partition/4 (using a
closure for comparing list elements with a pivot). A good library will
take away the overhead of using a closure. This would reduce the
number of lines of code above to seven, the same number of lines of
code as in your list comprehension version. A version using append/3
instead of an accumulator would take six lines of code.
Cheers,
Paulo
afa
List comprehension is better than findall for the following reasons:
1. It is easier to understand than the "obscure" findall to most
beginners because everybody is familiar with the set builder notation.
I taught a course that covers both LP and FP, and my students had no
problem at all grabbing list comprehensions but struggled with fail-
dirven loops in Prolog.
2. findall and list-driven loops in general don't work with attributed
variables because you get copies of variables. That means list-dirven
loops cannot be used for posting constraints in CLP languages.
3. findall is more expensive than list comprehension. Your version of
qsort is 6 times slower than the one that uses list comprehension (you
need the latest version of B-Prolog to reproduce this result). List
comprehension is compiled into tail-recursive predicates and hence its
use has no penalty at all.
Cheers,
Neng-Fa
afa
> On Jan 9, 2:05 pm, bart demoen <b...@cs.kuleuven.be> wrote:
> 2. findall and list-driven loops in general don't work with attributed
Sorry. list-driven should be failure-driven.
bart demoen
> List comprehension is better than findall for the following reasons:
Everyone knows that one should "never get involved in a land war in
Asia" - but only slightly less well-known is this: "never go against
the author of his natural and easy to grasp pet construct" :-)
Anyway ...
> 1. It is easier to understand than the "obscure" findall to most
> beginners because everybody is familiar with the set builder notation.
> I taught a course that covers both LP and FP, and my students had no
> problem at all grabbing list comprehensions but struggled with fail-
> driven loops in Prolog.
There is no need to explain the implementation (by failure-driven
loop) of findall to beginners - just as I hope there is no need to
explain to beginners that the list-comprehension is actually
transformed to a piece of recursive code that can produce
bindings - e.g. how do you explain to beginners that
?- L = [f(X,Y),f(a,Z),f(U,b)],
Lnew @= [T : T in L, T = f(a,_) ],
write(L/Lnew), nl.
writes
[f(a,b),f(a,b),f(a,b)]/[f(a,b),f(a,b),f(a,b)]
(tested on B-Prolog 7.4b1.1)
> 2. findall and failure-driven loops in general don't work with attributed
> variables because you get copies of variables. That means failure-driven
> loops cannot be used for posting constraints in CLP languages.
True, but that's not an argument against using findall in case no
attributed variables are involved. Can you use list-comprehensions
easily to post constraints ? If not, your second argument seems
vacuous.
> 3. findall is more expensive than list comprehension. Your version of
> qsort is 6 times slower than the one that uses list comprehension (you
> need the latest version of B-Prolog to reproduce this result). List
> comprehension is compiled into tail-recursive predicates and hence its
> use has no penalty at all.
First of all, tere is an interesting assumption here, namely that the
template
findall(X,(member(X,L), condition(X)), Result)
cannot be transformed by a smart (your ?) compiler into the same loop
as results from
Result @= [X : X in L, condition(X)]
This stems for sure from assumptions on the modes/side-effects/... of
the constructs involved in both.
Secondly, I have the latest version of B-Prolog I think (7.4b1.1)
and I cannot reproduce the factor 6. I measure a small factor of 1.25
(or close) on average. I am including my benchmark, so that everyone
can see for himself. I have also included some variants of qsort (the
standard one with difflists that Paolo posted), and one with a
specialized loop instead of the list comprehension (but still using
append). The results are:
listcomprehension=724
findall=908
specialized=116
paolo=60
nosort=4
[nosort is a dummy loop- figures are msecs on my linux laptop]
The time is over all permutations of a list of 8 different integers.
Do ?- t(8).
So, what is the bottom line here: if speed is an issue (and I think it
is, but you made it into an argument), don't use list comprehensions
(as implemented in B-Prolog). The difference between list
comprehensions and findall (as implemented in B-Prolog) is small - and
I congratulate you with your efficient implementation of findall !
Now, we could try to look into the reason why the findall is sligthly
more expensive (albeit not a factor 6) than list comprehensions in
B-Prolog. But unfortunately, we are not able to see the implementation
of B-Prolog (still one of the few I have to use my imagination on how
its implementation code looks - but I guess very often correct -
remember your append/3 bug I pinpointed a few days ago) - how sad.
Cheers
Bart Demoen
t(N) :-
mkl(N,L),
s(L).
s(L) :-
statistics(runtime,[T1|_]),
(perm(L,S), qsort1(S,_), fail ; true),
statistics(runtime,[T2|_]),
report(T1,T2,listcomprehension).
s(L) :-
statistics(runtime,[T1|_]),
(perm(L,S), qsort2(S,_), fail ; true),
statistics(runtime,[T2|_]),
report(T1,T2,findall).
s(L) :-
statistics(runtime,[T1|_]),
(perm(L,S), qsort3(S,_), fail ; true),
statistics(runtime,[T2|_]),
report(T1,T2,specialized).
s(L) :-
statistics(runtime,[T1|_]),
(perm(L,S), qsort4(S,_), fail ; true),
statistics(runtime,[T2|_]),
report(T1,T2,paolo).
s(L) :-
statistics(runtime,[T1|_]),
(perm(L,S), qsort5(S,_), fail ; true),
statistics(runtime,[T2|_]),
report(T1,T2,nosort).
mkl(N,L) :-
(N == 0 ->
L = []
;
L = [N|R],
M is N - 1,
mkl(M,R)
).
report(T1,T2,Q) :-
T is T2 - T1,
write(Q = T), nl,
fail.
qsort1([],[]).
qsort1([H|T],S):-
L1 @= [X : X in T, X<H],
L2 @= [X : X in T, X>=H],
qsort1(L1,S1),
qsort1(L2,S2),
append(S1,[H|S2],S).
qsort2([],[]).
qsort2([H|T],S):-
findall(X,(member(X,T), X<H), L1),
findall(X,(member(X,T), X>=H), L2),
qsort2(L1,S1),
qsort2(L2,S2),
append(S1,[H|S2],S).
qsort3([],[]).
qsort3([H|T],S):-
findsmaller(T,H,L1),
findnotsmaller(T,H,L2),
qsort3(L1,S1),
qsort3(L2,S2),
append(S1,[H|S2],S).
findsmaller([],_,[]).
findsmaller([X|R],H,Out) :-
(X < H ->
Out = [X|RestOut],
findsmaller(R,H,RestOut)
;
findsmaller(R,H,Out)
).
findnotsmaller([],_,[]).
findnotsmaller([X|R],H,Out) :-
(X >= H ->
Out = [X|RestOut],
findnotsmaller(R,H,RestOut)
;
findnotsmaller(R,H,Out)
).
perm([],[]).
perm([X|R],O) :-
perm(R,RP),
ins(RP,X,O).
ins(L,X,[X|L]).
ins([Y|R],X,[Y|S]) :- ins(R,X,S).
qsort4(List, Sorted) :-
quicksort(List, [], Sorted).
quicksort([], Sorted, Sorted).
quicksort([Pivot| Rest], Acc, Sorted) :-
partition(Rest, Pivot, Smaller0, Bigger0),
quicksort(Smaller0, [Pivot| Bigger], Sorted),
quicksort(Bigger0, Acc, Bigger).
partition([], _, [], []).
partition([X| Xs], Pivot, Smalls, Bigs) :-
( X < Pivot ->
Smalls = [X| Rest],
partition(Xs, Pivot, Rest, Bigs)
; Bigs = [X| Rest],
partition(Xs, Pivot, Smalls, Rest)
).
qsort5(_,_).
afa
> On Mon, 11 Jan 2010 07:09:29 -0800, afa wrote:
> > List comprehension is better than findall for the following reasons:
>
> Everyone knows that one should "never get involved in a land war in
> Asia" - but only slightly less well-known is this: "never go against
> the author of his natural and easy to grasp pet construct" :-)
>
I guess you advice is for president Obama:-) I am in New York now. But
it's good that you agree the "pet construct" is natural and easy.
> ?- L = [f(X,Y),f(a,Z),f(U,b)],
> Lnew @= [T : T in L, T = f(a,_) ],
> write(L/Lnew), nl.
>
> writes
>
> [f(a,b),f(a,b),f(a,b)]/[f(a,b),f(a,b),f(a,b)]
>
> (tested on B-Prolog 7.4b1.1)
This is a heavy punch, but I expected that:-) In this example, the
anonymous variable _ is not declared local and thus you get the
result. I guess this is what you wanted:
?- L = [f(X,Y),f(a,Z),f(U,b)],Lnew @= [T : T in L, [LocalVar],T
= f(a,LocalVar)].
L = [f(a,Y),f(a,Z),f(a,b)]
X = a
U = a
Lnew = [f(a,Y),f(a,Z),f(a,b)]
I agree that treating an anonymous variable as global is strange, but
we don't have a better solution because you can't detect what variable
is anonymous after a clause is read. I thought about letting the
compiler issue a warning when a list comprehension contains singleton
variables, but it's not done yet. My advice for now is that don't use
anonymous variables in list comprehensions.
> True, but that's not an argument against using findall in case no
> attributed variables are involved. Can you use list-comprehensions
The very initial motive of foreach and list comprehension was to
enhance to modeling power of CLP(FD).
> This stems for sure from assumptions on the modes/side-effects/... of
> the constructs involved in both.
Do you know any system that translates findall into tail-recursive
loops. I am not aware of any.
>
> Secondly, I have the latest version of B-Prolog I think (7.4b1.1)
Sorry, I should have mentioned the version I used. It was b1.2. I
noticed that in b1.1, if-then-else was interpreted, not compiled. That
was why you couldn't confirm my results.
Cheers,
Neng-Fa
bart demoen
>> Secondly, I have the latest version of B-Prolog I think (7.4b1.1)
>
> Sorry, I should have mentioned the version I used. It was b1.2. I
> noticed that in b1.1, if-then-else was interpreted, not compiled. That
> was why you couldn't confirm my results.
b1.2 is not available :-(
So I still can't confirm your results.
Cheers
Bart Demoen
Jan Wielemaker
> On Jan 11, 3:30�pm, bart demoen <b...@cs.kuleuven.be> wrote:
> Do you know any system that translates findall into tail-recursive
> loops. I am not aware of any.
Worse, such a system would be broken. Note that
findall(X, member(X, L), Xs)
is the same as
maplist(copy_term, L, Xs).
[True, that is a nice tail recursive loop, but not what Bart
intended :-)]
So, I do agree that the future is in high-level constructs that can be
processed in `forward' mode. Unlike some people here, I think it is a
requirement that such constructs can be compiled safely. Finally, I very much
dislike all the non-Prolog syntax, notably new operators with functional
flavour, etc.
Cheers --- Jan
Bart Demoen
> On 2010-01-12, afa <neng...@gmail.com> wrote:
>> On Jan 11, 3:30 pm, bart demoen <b...@cs.kuleuven.be> wrote:
>
>> Do you know any system that translates findall into tail-recursive
>> loops. I am not aware of any.
>
> Worse, such a system would be broken. Note that
>
> findall(X, member(X, L), Xs)
>
> is the same as
>
> maplist(copy_term, L, Xs).
Not sure this is true: if X is an attributed variable, or ground,
it can be quite different.
That's the difference between equational reasoning in FP and LP:
in FP, the instantiation is always ground.
But you are right, given the right instantiation, the above is ok.
Given slightly more info on the instantiation, namely that L is a
ground list, one can even get rid of the maplist and the copy_term :-)
So, the difference between list-comprehension and findall boils down
to instantiation - and a bit of syntax.
Cheers
Bart Demoen
Jan Wielemaker
> On Tue, 12 Jan 2010 08:52:18 +0000, Jan Wielemaker wrote:
>
>> On 2010-01-12, afa <neng...@gmail.com> wrote:
>>> On Jan 11, 3:30 pm, bart demoen <b...@cs.kuleuven.be> wrote:
>>
>>> Do you know any system that translates findall into tail-recursive
>>> loops. I am not aware of any.
>>
>> Worse, such a system would be broken. Note that
>>
>> findall(X, member(X, L), Xs)
>>
>> is the same as
>>
>> maplist(copy_term, L, Xs).
>
> Not sure this is true: if X is an attributed variable, or ground,
> it can be quite different.
In SWI-Prolog, the behaviour of the two calls above is the same
for attributed variables (AFAIK). For ground terms, the findall
version behaves as duplicate_term/2; SWI-Prolog's copy_term/2
on a ground term simply unifies both sides.
> That's the difference between equational reasoning in FP and LP:
> in FP, the instantiation is always ground.
>
> But you are right, given the right instantiation, the above is ok.
> Given slightly more info on the instantiation, namely that L is a
> ground list, one can even get rid of the maplist and the copy_term :-)
>
> So, the difference between list-comprehension and findall boils down
> to instantiation - and a bit of syntax.
Yes. The copying semantics of findall/3 make it -in my opinion- a
rather undesirable predicate. Used to collect ground query-results,
it is totally fine, but in other cases the result can be awkward.
This often holds for lists ...
List-comprehension is -if WikiPedia is right- a combination of filtering
and applying a function. We have both, in separate predicates:
include/exclude/partition for filtering and maplist for applying a
function. If I understand this correctly, each list-comprehension
can be replaced by include+maplist, where you often need auxiliary
predicates or ... lambda-expressions.
If you do not need auxiliary predicates or lambda-expressions, I
like
include(Filter, In, Tmp),
maplist(Function, Tmp, Out)
at least as much as new syntax for list-comprehension. A smart
compiler may even be able to merge the two :-). In various projects,
we used a version of maplist that only mapped the input arguments
for which continuation succeeded, i.e.
map_true(_, [], []).
map_true(G, [H0|T0], [H|T]) :-
call(G, H0, H), !,
map_true(G, T0, T).
map_true(G, [_|T0], T) :-
map_true(G, T0, T).
There are some variations possible/desirable, but this should get
the idea. Now you do list-comprehension with a single aux-predicate
or lambda.
Seems some people here are in the contest `I can solve problem X in
N lines'. I do not care too much. Prolog is doing quite well in
the functionality you can program in N lines (as I think about it,
it often looses on small things, but seems to win on larger programs;
maybe being forced to break things in small reusable predicates isn't
such a bad idea :-).
Cheers -- Jan
Bart Demoen
>>> findall(X, member(X, L), Xs)
>>>
>>> is the same as
>>>
>>> maplist(copy_term, L, Xs).
>>
>> Not sure this is true: if X is an attributed variable, or ground, it
>> can be quite different.
>
> In SWI-Prolog, the behaviour of the two calls above is the same for
> attributed variables (AFAIK).
Here a little test:
t(X,L) :-
findall(X,member(X,L),Xs),
writeln(Xs),
fail.
t(X,L) :-
maplist(copy_term,L,Xs),
writeln(Xs),
fail.
?- t(3,[1,2,3]).
[3]
[1, 2, 3]
false.
?- freeze(X,writeln(X)), t(X,[1,2,3]).
1
2
3
[1, 2, 3]
[1, 2, 3]
false.
?- freeze(X,fail), t(X,[1,2,3]).
[]
[1, 2, 3]
false.
?- freeze(Z,fail), L = [Z], X = 1, t(X,L).
[]
[_G524]
false.
?- t(X,[f(X)]).
[f(**)]
[f(_G319)]
false.
Cheers
Bart Demoen
Jan Wielemaker
>
>>>> findall(X, member(X, L), Xs)
>>>>
>>>> is the same as
>>>>
>>>> maplist(copy_term, L, Xs).
>>>
>>> Not sure this is true: if X is an attributed variable, or ground, it
>>> can be quite different.
>>
>> In SWI-Prolog, the behaviour of the two calls above is the same for
>> attributed variables (AFAIK).
>
> Here a little test:
I stand corrected. I guess the extra condition must be that the
template variable must be unbound (also not attributed) and the
list cannot be partial. I was referring to attvars inside the
list-elements. Surely you'll find more oddities :-)
Cheers --- Jan
afa
The file name is still bp74b1_linux.tar.gz but the minor version is
b1.2.
Cheers,
Neng-Fa
afa
> On 2010-01-12, Bart Demoen <b...@cs.kuleuven.be> wrote:
> List-comprehension is -if WikiPedia is right- a combination of filtering
> and applying a function. We have both, in separate predicates:
> include/exclude/partition for filtering and maplist for applying a
> function. If I understand this correctly, each list-comprehension
> can be replaced by include+maplist, where you often need auxiliary
> predicates or ... lambda-expressions.
I'd like to see how you can program the permutations and bool queens
examples I posted before. You can do it with include+maplist but not
as nicely.
Cheers,
Neng-Fa
Jan Wielemaker
Yeah, you have array-syntax and generalise the list-comprehension over ranges
of integers. Ok, now you can solve the queens problem with fairly elegant
syntax.
I guess that by defining arrays and higher-order operations on them as
we have in lists, one also gets a reasonable result.
And, of course we the code below by Markus, which looks like a much more
Prolog-minded solution to the problem.
clpfd_queens(N, Cols) :-
queens(N, Cols),
labeling([ff], Cols).
queens(N, Qs) :-
length(Qs, N),
Qs ins 1..N,
safe_queens(Qs).
safe_queens([]).
safe_queens([Q|Qs]) :-
safe_queens(Qs, Q, 1),
safe_queens(Qs).
safe_queens([], _, _).
safe_queens([Q|Qs], Q0, D0) :-
Q0 #\= Q,
abs(Q0 - Q) #\= D0,
D1 #= D0 + 1,
safe_queens(Qs, Q0, D1).
True though, some problems have a nice known algorithm involving matrices
(e.g. shortest edit-distance between two strings) and your notation comes
handy.
Maybe I'm just sceptic wrt. adding more operator-based syntax to Prolog. I
would even like to drop some (e.g. =.. is much better written as univ(Term,
Name, ListOfArguments) and even better if we invent a better name). I've seen
quite a few of such syntaxes. Within a specific domain, they surely can
improve readability for insiders in the domain. For outsiders though, the
code generally gets less readable. So, symbolic operators are only generally
useful if they are widely understood.
Typically, those are things from math, comparison and assignment. If
anything, I'd sometimes want something to access elements in structure,
preferably by name. I know there are quite a few attempts around ...
SWI-Prolog has library(record) here, which is a very Prolog-minded
alternative without introducing anything new. Unfortunately, the
new syntax only works nice if you go for a functional notation :-(
Cheers --- Jan
Ulrich Neumerkel
>After adding into B-Prolog 7.4 the foreach built-ins for describing
>loops and the list comprehension notation for constructing lists, I
>felt that these constructs could benefit Prolog in general.
First, it is very fine that discussion on these issues start!
List comprehensions look very elegant in languages like Haskell. But
let us be very clear about one point here: One reason why functional
languages have developed that formalism is to get what Prolog has
built-in. I.e., chronological backtracking. Certainly,
comprehensions (alone) cannot emulate Prolog's entire functionality
inasmuch as Prolog cannot (directly) emulate the entire functionality
of list comprehensions. But there is a substantial overlap between
both.
When considering constructs for comprehensions, it is very seducing to
directly copy constructs from functional languages. Frequently a
direct transplantation is repelled. It is not without reason that
Prolog is considered to be of a different programming paradigm. So
these things do need some time and understanding. Discussing these
issues is the best we can do.
It seems very desirable to me that the following property holds:
Comprehensions/loops that have a direct correspondence to a pure,
monotonic program should behave exactly like that monotonic program.
Maybe, in the very worst case, the comprehension/loop might "bail out"
with a clean error.
The reason for this requirement is simply that pure, monotonic
programs should be replaced only by similarly pure, monotonic
constructs.
That requirement might look simple, but finding a good, roboust
construct is not that simple. For example, it is violated by current
loop constructs as the do-loops of ECLiPSe or SICStus.
So I will now comment on B-Prolog 7.4b1.2 as of 2010-01-11 15:44:
| ?- L @= [X-Y:X in[1,2],X = 1,Y in [3,4]].
*** Undefined procedure: throw/2
I tried to mimic
> [(x,y)|x<-[1,2],x==1,y<-[3,4]]
[(1,3),(1,4)]
Next, I try to understand the nature of backtracking in "predicates" -
i.e. the filter goal.
| ?- L@=[X-Y:X in [1,2],member(Y,[3,4])].
L = [1-3,2-3]
Y = 3 ?;
no
You are cutting away solutions. Why not use the soft-if-then-else?
In any case this seems to be most unfortunate in the presence of
constraints! There, it might happen that a goal only succeeds due to
the incompleteness of the sover!!
Other things:
| ?- L@=[t:t in t].
no
| ?- L@=[t:t in []].
L = []
yes
| ?- L@=[t:t in X].
*** wrong_domain(_29c)
That would be an ISO instantiation error. Here is a table of all ISO
error classes:
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/error_k#error_classes
| ?- L @= [X:X in[]].
L = []
yes
Fine. Now, I want to generalize part of that goal. I.e. I want to replace
X in [] by Y:
| ?- L @= [X:Y].
L = [X:Y]
yes
So a [] morphed into a one-element list due to a generalization!
Bart Demoen commented already on the variable scoping issue. I
entirely second him on this issue! The global by default approach
goes against "Prolog intuition".
So there are a lot of open questions. But the most fundamental behind
is the question about filter. A direct transliteration of filter into
Prolog leads to nonmonotonic programs. That's what I worry most about.
notprovable(Goal) :- % like \+ Goal
[] @= [t:t in [t], Goal].
The maplist/2... family does not have this problem. But then, they
are less expressive. Would be fine if we could get something that is
pure and monotonic.
I still hope that there are better ways - and I am very much convinced
that they will be compatible with lambda expressions:
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord
(It took some time in FP to find this, so why should it be free here?)
bart demoen
>> b1.2 is not available :-(
>> So I still can't confirm your results.
>
> The file name is still bp74b1_linux.tar.gz but the minor version is
> b1.2.
Thanks.
Now I get
listcomprehension=200
findall=956
specialized=108
paolo=60
nosort=4
A factor almost 5 - close enough to your factor 6 to consider it confirmed.
Why is the specialized version even a factor 2 faster than the listcomprehension
version ?
Cheers
Bart Demoen
bart demoen
> I'd like to see how you can program the permutations and bool queens
> examples I posted before. You can do it with include+maplist but not as
> nicely.
The point is not writing "nice" or "short" programs.
"Robustness" comes first. And a prerequisite to that is a clear semantics,
from which it is clear what happens with void/singleton variables, with
instantiated arguments, constrained variables, side-effects ...
As long as we just consider the free variable/ground list/no side effects
case, we all know that the difference between findall, list-comprehension,
maplist, filter ... is just a matter of syntax and/or libraries. What about
the other cases ? Is treating them systematically hindering performance in
the "normal" case ? Is it too hairy to specify completely ? After all, one
wants to put some more or less complete spec in the manual, no ?
I do not object to list-comprehensions, maplist, lambdas, ... into Prolog
(we can of course discuss about syntax forever, but preferably in a bar :-)
but I feel reluctant to go with a new construct just because it happens to be
handy for some particular (toy) program.
Cheers
Bart Demoen
afa
The compiled code tells why (see below). The generated predicates take
four arguments while findsmaller and findnotsmaller each takes three
arguments. The main overhead comes from the setups of the calls. When
the list is large, the difference should be smaller. Of course, the
compiler could be further improved.
Cheers,
Neng-Fa
?-compile_foreach(qsort).
qsort([], []).
qsort([A|B], C) :-
H=I,
'qsort_#_0'(B, A, I, J),
J=[],
H@=D,
K=L,
'qsort_#_1'(B, A, L, M),
M=[],
K@=E,
qsort(D, F),
qsort(E, G),
append(F, [A|G], C).
'qsort_#_1'([], _, A, B) :-
true:(A=B,true).
'qsort_#_1'([C|E], D, A, F) :-
true:((('_$initialize_var'(A),'_$initialize_var'(B)),'_
$if_then_else'(C>=D,A=[C|B],A=B)),'qsort_#_1'(E,D,B,F)).
'qsort_#_1'([_|A], B, _, C) :-
true:'qsort_#_1'(A,B,_,C).
'qsort_#_0'([], _, A, B) :-
true:(A=B,true).
'qsort_#_0'([C|E], D, A, F) :-
true:((('_$initialize_var'(A),'_$initialize_var'(B)),'_
$if_then_else'(C<D,A=[C|B],A=B)),'qsort_#_0'(E,D,B,F)).
'qsort_#_0'([_|A], B, _, C) :-
true:'qsort_#_0'(A,B,_,C).
bart demoen
> ?-compile_foreach(qsort).
[..]
> 'qsort_#_1'([], _, A, B) :-
> true:(A=B,true).
> 'qsort_#_1'([C|E], D, A, F) :-
> true:((('_$initialize_var'(A),'_$initialize_var'(B)),
> '_ $if_then_else'(C>=D,A=[C|B],A=B)),'qsort_#_1'(E,D,B,F)).
> 'qsort_#_1'([_|A], B, _, C) :-
> true:'qsort_#_1'(A,B,_,C).
Why this last clause ?
Cheers
Bart Demoen
afa
Neumerkel) wrote:
> afa <neng.z...@gmail.com> writes:
> So I will now comment on B-Prolog 7.4b1.2 as of 2010-01-11 15:44:
>
> | ?- L @= [X-Y:X in[1,2],X = 1,Y in [3,4]].
>
> *** Undefined procedure: throw/2
> I tried to mimic
>
> > [(x,y)|x<-[1,2],x==1,y<-[3,4]]
>
> [(1,3),(1,4)]
>
I guess you switched X=1 and Y in [3,4] on purpose. The correct syntax
for a list comprehension is:
[T : I1 in D1, ..., In in Dn, LocalVars, Goal]
where LocalVars and Goal are optional. I thought about allowing
conditions to be placed between iterators, but then we need to have
several arguments for local variables. In the current design, all
conditions must be written as part of Goal. It can be wasteful if
iterations are required only for certain combinations of the values.
The error messages are unfriendly now. Of course, this "undefined"
message was not intended. You can check this by reading the
interpreter.
> Next, I try to understand the nature of backtracking in "predicates" -
> i.e. the filter goal.
>
> | ?- L@=[X-Y:X in [1,2],member(Y,[3,4])].
>
> L = [1-3,2-3]
> Y = 3 ?;
> no
>
> You are cutting away solutions. Why not use the soft-if-then-else?
I think this is a reasonable restriction. Can a predicate in a set
builder be nondeterministic?
>
> Other things:
>
I agree that the constructs should be designed with a set of friendly
error messages. This will be the next step.
> Bart Demoen commented already on the variable scoping issue. I
> entirely second him on this issue! The global by default approach
> goes against "Prolog intuition".
It'd be impossible to interpret a construct if you take local-by-
default approach. So you like the ECLiPse proposal? I don't like the
param part. I noticed that most programs written using foreach and
list comprehension are much shorter than their counterparts in
ECLiPSe.
Thank you for your comments and thank you also for suggesting the ':'
operator for list comprehension. I like it because it is very close to
the '|' operator used in the set builder notation.
Cheers,
Neng-Fa
afa
That is a good question. I don't even know how it sneaked in:-). I'll
look into it.
Cheers,
Neng-Fa
Bart Demoen
> The error messages are unfriendly now. Of course, this "undefined"
> message was not intended. You can check this by reading the interpreter.
Where can I find the interpreter ?
Cheers
Bart Demoen
afa
Go back to the very first posting on this thread.
Cheers,
Neng-Fa
Ulrich Neumerkel
>On Jan 12, 12:45�pm, ulr...@mips.complang.tuwien.ac.at (Ulrich
>Neumerkel) wrote:
>> afa <neng.z...@gmail.com> writes:
>
>> So I will now comment on B-Prolog 7.4b1.2 as of 2010-01-11 15:44:
>>
>> | ?- L @= [X-Y:X in[1,2],X = 1,Y in [3,4]].
>>
>> *** �Undefined procedure: throw/2
>> I tried to mimic
>>
>> > [(x,y)|x<-[1,2],x==1,y<-[3,4]]
>>
>> [(1,3),(1,4)]
>>
>
>I guess you switched X=1 and Y in [3,4] on purpose. The correct syntax
>for a list comprehension is:
>
>[T : I1 in D1, ..., In in Dn, LocalVars, Goal]
>
>where LocalVars and Goal are optional. I thought about allowing
>conditions to be placed between iterators, but then we need to have
>several arguments for local variables. In the current design, all
>conditions must be written as part of Goal. It can be wasteful if
>iterations are required only for certain combinations of the values.
Not sure, but since lists are not lazy in Prolog, such an extension could
help to avoid otherwise useless production of intermediary lists.
>The error messages are unfriendly now. Of course, this "undefined"
>message was not intended. You can check this by reading the
>interpreter.
>
>> You are cutting away solutions. Why not use the soft-if-then-else?
>
>I think this is a reasonable restriction. Can a predicate in a set
>builder be nondeterministic?
In most of the cases this would be an error. Preserving at least this
nondeterminacy seems to be a good idea.
?- length(Xs, 4), maplist(between(1,4), Xs).
Getting here all solutions is vital.
>> Bart Demoen commented already on the variable scoping issue. I
>> entirely second him on this issue! The global by default approach
>> goes against "Prolog intuition".
>It'd be impossible to interpret a construct if you take local-by-
>default approach.
Not sure I understand you here. library(lambda) does exactly this.
And to my understanding quite consistently.
What I wanted to say is that having to declare local variables
explicitly by indicating their names is what goes against "Prolog
intuition". The _ is the most extreme example for this.
So in your example
http://en.wikipedia.org/wiki/List_comprehension#B-Prolog
L @= [Y : X in 1..100, [Y], (X*X>3, Y is 2*X)]
the declaration of the Y in [Y] is problematic, even more so if we
would have further local variables that appear only in the goal.
((as an aside, it seems that everyone uses a different (finite)
interval on the wikipage, some 1..20, some 0..100))
Compare this to Haskell:
[ 2*x | x <- [1..100], x^2 > 3 ]
and let's rewrite it to become more similar:
[ y | x <- [1..100], x^2 > 3, y <- [2*x] ]
So in Haskell the left side of the <- leads to an implicit local
declaration. Maybe this is a clue? Things are somewhat easier in
Haskell as less variables are required due to functional notation.
In Prolog variables are global-by-default. If we want something else,
we need a construct for it. The context of a lambda or - maybe - the
context of a list comprehensions might be a place where that default
rule is altered.
> So you like the ECLiPse proposal? I don't like the
>param part. I noticed that most programs written using foreach and
>list comprehension are much shorter than their counterparts in
>ECLiPSe.
There are very excellent ideas within ECLiPse loops but some need
reconsideration. You are referring here to the exact manner of
variable scoping which makes nested loops clumsy.
Maybe I illustrate this with an example from 2009-06-23 comparing
library(lambda)
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl and
ECLiPse.
http://groups.google.at/group/comp.lang.prolog/browse_thread/thread/81deddbd7baaed23
library(lambda):
?- Xs = [A,B], maplist(Y+\X^Z^(X+Y #= Z), Xs, Zs).
ECLiPse:
?- Xs = [A,B], (foreach(X,Xs),foreach(Z,Zs),param(Y) do X+Y #= Z).
Both need here to declare Y as a global variable. We can debate what
kind of declaration is more convenient but I would say both require
more or less the same mental effort.
Now, let us describe a similar relation with a list of integerlists.
library(lambda):
?- Xss = [[A,B],[C]], maplist(maplist(Y+\X^Z^(X+Y #= Z)), Xss, Zss).
ECLiPse:
?- Xss = [[A,B],[C]],
(foreach(Xs,Xss),foreach(Zs,Zss),param(Y) do
(foreach(X,Xs),foreach(Z,Zs),param(Y) do X+Y #= Z)).
The advantage of the combination of call/N and library(lambda) is that
both styles of variables scoping can go hand-in-hand.
What I hope is that we could put the compactness of purely call/N
based approached into loops that are more flexible than maplist alone.
And now what I really like of ECLiPse loops: Arguments are very
symmetric. This is Prolog's relational way to see things. Look at
the Xs and Zs above! Entirely symmetric! In list comprehensions,
things tend to become asymmetric.
PS: Never forget that elections were won with slogans like:
Yes B can!
Or was it rather:
Yes SWI can! (pronounced as swee).
bart demoen
>> Where can I find the interpreter ?
>
> Go back to the very first posting on this thread.
Thanks - I missed that.
Cheers
Bart Demoen
afa
Neumerkel) wrote:
> afa <neng.z...@gmail.com> writes:
> >On Jan 12, 12:45 pm, ulr...@mips.complang.tuwien.ac.at (Ulrich
> >Neumerkel) wrote:
> >> afa <neng.z...@gmail.com> writes:
> So in your examplehttp://en.wikipedia.org/wiki/List_comprehension#B-Prolog
>
> L @= [Y : X in 1..100, [Y], (X*X>3, Y is 2*X)]
>
> the declaration of the Y in [Y] is problematic, even more so if we
> would have further local variables that appear only in the goal.
You have a new Y for each iteration. Why is this problematic? If you
go local-by-default, then how do you do the following?
L @= [Y : X in 1..5]
L = [Y,Y,Y,Y,Y]
The array access notation X[I] for lists and structures significantly
alleviate the burden of declaring local variables. If you compare the
programs written in B-Prolog and ECLiPse, you will see that the burden
of declaring global variables is normally heavier than that of local
variables. Examples:
N-Queens:
B-Prolog: http://probp.com/examples/foreach/queens.pl
ECLiPse: http://87.230.22.228/examples/queens_simple.ecl.txt
Magic square:
B-Prolog: http://probp.com/examples/foreach/magic.pl
ECLiPse: http://87.230.22.228/examples/magicsquare.ecl.txt
> library(lambda):
>
> ?- Xss = [[A,B],[C]], maplist(maplist(Y+\X^Z^(X+Y #= Z)), Xss, Zss).
>
> ECLiPse:
>
> ?- Xss = [[A,B],[C]],
> (foreach(Xs,Xss),foreach(Zs,Zss),param(Y) do
> (foreach(X,Xs),foreach(Z,Zs),param(Y) do X+Y #= Z)).
>
> The advantage of the combination of call/N and library(lambda) is that
> both styles of variables scoping can go hand-in-hand.
I really don't like the idea of constructing lists using foreach.
Neither code is readable to me. I would do the following if you ask me
to write it:
?- Xss = [[A,B],[C]], copy_term(Xss,Zss), foreach((Xs,Zs) in
(Xss,Zss), (X,Z) in (Xs,Zs), X+Y#=Z).
In general, the iterator (I1,I2,...,In) in (D1,D2,...,Dn) does
simultaneous loops. Let Di=[e_i1,e_i2,...,e_im] (i=1,...,n). This
iterator means that for each tuple (I1,I2,...,In)=(e_1j,e_2j,...,e_nj)
(j=1,...,m) have an iteration.
We should use loop constructs only when they result in compact and
readable code. Otherwise, we should use recursion.
> PS: Never forget that elections were won with slogans like:
>
> Yes B can!
>
> Or was it rather:
>
> Yes SWI can! (pronounced as swee).
Why do you need one winner? Let one hundred flowers blossom:-)
Cheers,
Neng-Fa
Ulrich Neumerkel
>On Jan 13, 2:52 pm, ulr...@mips.complang.tuwien.ac.at (Ulrich Neumerkel) wrote:
>>
>> L @= [Y : X in 1..100, [Y], (X*X>3, Y is 2*X)]
>>
>> the declaration of the Y in [Y] is problematic, even more so if we
>> would have further local variables that appear only in the goal.
>
>You have a new Y for each iteration. Why is this problematic?
It is problematic that you have to declare the local variables
explicitly. Without a declaration, things are global in @=.
Within ECLiPse loops and also within library(lambda) it is possible
to detect forgotten declarations:
..., X, ... \ ( ... X ...)
This can be signalled as an error. You cannot do this. If you forget
to declare a variable local it will be global. No chance to
indicate that.
But it is worse:
Usually, replacing a term by a fresh new variable is (in a pure,
monotonic program) a generalization of the program. However, if you
replace the Y in [Y], you will get a different result instead!
| ?- L @= [Y : X in 1..100, [Y], (X*X>3, Y is 2*X)].
L = [4,6..200]
yes
| ?- L @= [Y : X in 1..100, [FreshNewVar], (X*X>3, Y is 2*X)].
L = [4]
Y = 4
yes
That means that your construct behaves differently to regular (pure,
monotonic) Prolog code. I consider this the biggest problem. It
makes declarative diagnosis impossible (or at least extremely complex
to implement). Here is a (very simple) form of a diagnosing program
that would be affected:
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/diadem.pl
This program is able to give a reason why something fails by
systematically generalizing the query.
Try to give a reason why the following query fails:
?- "caelum" = "caenum".
You find diadem's answer in the link above!
Of course, such justifications are primarily useful in the context of
constraints where verbose procedural step-by-step explanations overtax
a programmer's comprehension.
> If you
>go local-by-default, then how do you do the following?
>
>L @= [Y : X in 1..5]
>L = [Y,Y,Y,Y,Y]
By declaring that Y somehow global. With e.g. +\ or the parm/1 or
whatever else.
>The array access notation X[I] for lists and structures significantly
>alleviate the burden of declaring local variables. If you compare the
>programs written in B-Prolog and ECLiPse, you will see that the burden
>of declaring global variables is normally heavier than that of local
>variables. Examples:
The array notation is a kind of functional notation which avoids
intermediary variables. Fine. Why not use X->I or any other standard
syntax for it? Adding an extra operator declaration is no problem,
but changing the core syntax looks very problematic to me.
>> library(lambda):
>>
>> ?- Xss = [[A,B],[C]], maplist(maplist(Y+\X^Z^(X+Y #= Z)), Xss, Zss).
>>
>> ECLiPse:
>>
>> ?- Xss = [[A,B],[C]],
>> (foreach(Xs,Xss),foreach(Zs,Zss),param(Y) do
>> (foreach(X,Xs),foreach(Z,Zs),param(Y) do X+Y #= Z)).
>>
>> The advantage of the combination of call/N and library(lambda) is that
>> both styles of variables scoping can go hand-in-hand.
>
>I really don't like the idea of constructing lists using foreach.
>Neither code is readable to me.
The version with library(lambda) is probably minimal w.r.t the number
of things mentioned explicitly. You have to get used to that
notation, however. Also, the notation as it stands cannot be easily
extended to related problems. It just works as is for such nested
lists. It certainly would be nicer to have something more general -
for me that is the point of this discussion.
The foreach on the other hand is too heavy, but I still do like its
symmetry. In your constructs the symmetry is lost. That is not a
problem in FP from where you have taken list comprehensions literally.
But we talk about Prolog, not a functional language. FP has to break
the symmetry. LP does not have to.
BTW, did you look at the parallel list comprehension construct? I see
there a certain analogy to the ECLiPse loops... I.e. take the
parallel list comprehensions and forget that they are describing a
list: we only need them "reading" lists - "reading" in Prolog means
"unifying". That is, those lists can be also written...
> I would do the following if you ask me
>to write it:
>
>?- Xss = [[A,B],[C]], copy_term(Xss,Zss), foreach((Xs,Zs) in (Xss,Zss), (X,Z) in (Xs,Zs), X+Y#=Z).
You introduce an impure construct into an inherently pure problem.
The price for this: certain uses are now incorrect. Try it with
| ?- Xss = [[0]], Y=1, copy_term(Xss,Zss), foreach((Xs,Zs) in (Xss,Zss), (X,Z) in (Xs,Zs), X+Y#=Z).
no
Expected: Zss = [[1]].
Explicit uses of copy_term/2 almost always lead to mode sensitive
code. Lambdas are a "tamed" version of copy_term/2.
>We should use loop constructs only when they result in compact and
>readable code. Otherwise, we should use recursion.
So far we have not explored the entire space of possiblities. Let's
see if we have overlooked some corner here or there.
>Why do you need one winner? Let one hundred flowers blossom:-)
One? B, SWI it all rhymes with "we"!
afa
Neumerkel) wrote:
> It is problematic that you have to declare the local variables
> explicitly. Without a declaration, things are global in @=.
You have to either declare local variables or global variables.
Because local variables are never bound, they always have their
identities. Global variables, however, may loose their identities.
That is why it's impossible to interpret a construct if it declares
global variables only. When a global variable, say X, is bound to f
(Y,Z), do you treat Y and Z as global variables? During execution the
set of local variables is fixed but the set of global variables is
not. If you compile everything as is done in ECLiPSe, the story is
different because the set of variables accessible to the compiler is
always fixed.
> The array notation is a kind of functional notation which avoids
> intermediary variables. Fine. Why not use X->I or any other standard
> syntax for it? Adding an extra operator declaration is no problem,
> but changing the core syntax looks very problematic to me.
As you know, this notation was first adopted in ECLiPSe for
structures. It is generalized in B-Prolog for accessing not only
structures but also lists. This notation is better than other
notations because it is universal. If you take a look at C#, this
notation is used for accessing arrays, collections, and maps. It is
very convenient. Is it difficult for a Prolog system to support this
notation? No, it took me five minutes to change the parser to
accommodate this notation. If a variable token is followed by '[',
then '^' is inserted in between. So in arithmetic expressions and
constraints, X[I] is treated as the Ith element of X, and in any other
context X[I] is treated as the term X^[I].
Cheers,
Neng-Fa
Joachim Schimpf
> On Jan 14, 1:03 pm, ulr...@mips.complang.tuwien.ac.at (Ulrich
> Neumerkel) wrote:
>> It is problematic that you have to declare the local variables
>> explicitly. Without a declaration, things are global in @=.
>
> You have to either declare local variables or global variables.
Strictly speaking, this true for the interpreted case only. The
reason why people complain about the param() construct in ECLiPSe
loops is that when a loop occurs in _compiled_ code, it is often
obvious what the global variables are, namely the ones that occur
both inside and outside the loop. For example in
write_list(Stream, List) :-
( foreach(X,List), param(Stream) do
write(Stream, X)
).
it is pretty obvious that Stream is a global variable of the loop.
A compiler, having a global view of the clause, could figure this
out automatically, that's why the param() declaration seems silly.
However, when metacalling such code, standard Prolog technology is
unable to determine easily whether Stream occurs outside the loop
construct, and that's why we have the declaration.
> Because local variables are never bound, they always have their
> identities. Global variables, however, may loose their identities.
> That is why it's impossible to interpret a construct if it declares
> global variables only. When a global variable, say X, is bound to f
> (Y,Z), do you treat Y and Z as global variables?
You simply treat X as a term that is shared between iterations,
so yes, Y are Z are "global variables" in your sense. I don't
understand why you see this as an obstacle to interpretation.
There are indeed issues (so far unmentioned) with compile-time
vs execution-time expansion, but they apply similarly to local
and global declarations.
> If you compile everything as is done in ECLiPSe,
This is incorrect. ECLiPSe loops can be both compiled or meta-called,
as is clearly stated in the original paper. Also, the 200-line
implementation that has been publicly available for about 8 years
provides both, see http://www.eclipse-clp.org/software/loops
> the story is
> different because the set of variables accessible to the compiler is
> always fixed.
Let me give some reasons why declaring 'globals' may be better a
better idea than declaring 'locals':
* Other have already mentioned that with local declarations you can't
use anonymous variables in the loop body, as they would need to be
declared local.
* Once you have if-then-else and a good loop construct, people tend
to use less auxiliary clauses, and clause bodies (and loop bodies)
become bigger and more nested. Your loop examples all have tiny loop
bodies and the set of local variables is correspondingly small and
obvious. Typical ECLiPSe loops have larger bodies, often dozens of
lines, and it is unacceptable to require a programmer to adjust a
declaration 10 lines above, just for using a new variable when locally
modifying code. Also, such loops tend to have many more local than
global variables.
* The killer: when subgoals inside the loop body get goal-expanded,
new local variables may be introduced by the expansion, and need
to be made known to the enclosing loop - that's difficult.
And here is another argument in favour of 'global declarations':
They can be seen as just another form of iterating over data.
Consider the minimalist explanation of do-loops at
http://www.eclipse-clp.org/software/loops: the essence is
that any do-loop can be expressed solely in terms of
fromto(Start,In,Out,Stop) iterators, which embody the
concept of the logic programming accumulator.
The small example above can then be written in normalised form as
write_list(Stream, List) :-
( fromto(List,[X|Xs],Xs,[]), % short: foreach(X,List)
fromto(Stream,Stream,Stream,_) % short: param(Stream)
do
write(Stream, X)
).
As you see, the 'global declaration' param(Stream) is nothing but a
'constant iterator' i.e. a term that remains the same through all
iterations. I don't think you can do any simpler than that.
-- Joachim
Joachim Schimpf
> ...
>
> qsort([],[]).
> qsort([H|T],S):-
> L1 @= [X : X in T, X<H],
I think that interpreting certain list templates as comprehensions
is a really bad idea (see Ulrich's example, which is only the tip of
the iceberg), and too high a price to pay for "looking like Haskell".
At least consider using a dedicated functor, for example
L1 @= listof([X : X in T], X<H)
where it is clear that listof/2 is a function that returns a list.
For those who don't like functional notation you can provide a form
with result argument:
listof([X : X in T], X<H, L1)
And you don't need to invent anything new when you want to have
arrayof() for array comprehensions etc.
-- Joachim
Ulrich Neumerkel
>On Jan 14, 1:03 pm, ulr...@mips.complang.tuwien.ac.at (Ulrich
>Neumerkel) wrote:
>> It is problematic that you have to declare the local variables
>> explicitly. Without a declaration, things are global in @=.
>
>You have to either declare local variables or global variables.
>Because local variables are never bound, they always have their
>identities. Global variables, however, may loose their identities.
>That is why it's impossible to interpret a construct if it declares
>global variables only.
Here I disagree. library(lambda) was written in such a manner,
that you can wrap call/N whereever you like and still get *exactly*
the same semantics for the variables!
> When a global variable, say X, is bound to f(Y,Z),
>do you treat Y and Z as global variables?
Yes. Look at
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord#implementation
Dynamically, only the structure f(Y,Z) would be seen. What else makes
sense here?
> During execution the
>set of local variables is fixed but the set of global variables is
>not. If you compile everything as is done in ECLiPSe, the story is
>different because the set of variables accessible to the compiler is
>always fixed.
ECLiPSe cannot compile everything, I have not looked into its
implementation, but: p :- the_big_loop = T, call(G). should
be entirely dynamic. If not, just add something "undecidable"
to prevent static interpretation.
library(lambda) was designed with the goal that dynamic execution
and static compilation give the same result - and at the same time,
static compilation permits still the desired optimizations.
>> The array notation is a kind of functional notation which avoids
>> intermediary variables. Fine. Why not use X->I or any other standard
>> syntax for it? Adding an extra operator declaration is no problem,
>> but changing the core syntax looks very problematic to me.
>
>As you know, this notation was first adopted in ECLiPSe for
>structures. It is generalized in B-Prolog for accessing not only
>structures but also lists. This notation is better than other
>notations because it is universal. If you take a look at C#, this
>notation is used for accessing arrays, collections, and maps. It is
>very convenient. Is it difficult for a Prolog system to support this
>notation? No, it took me five minutes to change the parser to
>accommodate this notation.
Let us not imagine what Prolog would look like with every
five minute change applied. In fact, that was Prolog prior
to standardization. Full of tiny well meant extensions
for the (at that time very generously paying) customer.
This syntax extension makes typos accidentally valid. And that
is a nightmare for beginners - and teachers alike. Tiny errors
take away lots of time in a course. Think of
f([Xs[b]]). % Usually an error, actually meaning f([Xs,[b]]).
> If a variable token is followed by '[',
>then '^' is inserted in between. So in arithmetic expressions and
>constraints, X[I] is treated as the Ith element of X, and in any other
>context X[I] is treated as the term X^[I].
Try to see things from the user's side, not the implementor's.
Yes, it is easy to implement. But what are the consequences?
What about A[b]^c? Is it desirable that is now the same as
A^ ([b]^c) ? I have never seen that in any language so far.
Why not the notation X->[I] instead? Valid syntax.
No added complexity in unexpected places. Forces you to use
brackets in many situations.
Ulrich Neumerkel
>afa wrote:
>> On Jan 14, 1:03 pm, ulr...@mips.complang.tuwien.ac.at (Ulrich
>> Neumerkel) wrote:
>>> It is problematic that you have to declare the local variables
>>> explicitly. Without a declaration, things are global in @=.
>>
>> You have to either declare local variables or global variables.
>
>Strictly speaking, this true for the interpreted case only. The
>reason why people complain about the param() construct in ECLiPSe
>loops is that when a loop occurs in _compiled_ code, it is often
>obvious what the global variables are, namely the ones that occur
>both inside and outside the loop. For example in
>
>write_list(Stream, List) :-
> ( foreach(X,List), param(Stream) do
> write(Stream, X)
> ).
>
>it is pretty obvious that Stream is a global variable of the loop.
>A compiler, having a global view of the clause, could figure this
>out automatically, that's why the param() declaration seems silly.
Even for the static case the *functionality* of param/1 is very
useful to produce appropriate errors.
>However, when metacalling such code, standard Prolog technology is
>unable to determine easily whether Stream occurs outside the loop
>construct, and that's why we have the declaration.
The nonstandard Prolog technology you are alluding to would have
to maintain variables "in the context". But when should
that context switch in dynamic interpretation? For simple
code it is obvious: The next goal starts a new context.
But any unfolding would then become next to impossible.
>> Because local variables are never bound, they always have their
>> identities. Global variables, however, may loose their identities.
>> That is why it's impossible to interpret a construct if it declares
>> global variables only. When a global variable, say X, is bound to f
>> (Y,Z), do you treat Y and Z as global variables?
>
>You simply treat X as a term that is shared between iterations,
>so yes, Y are Z are "global variables" in your sense. I don't
>understand why you see this as an obstacle to interpretation.
>
>There are indeed issues (so far unmentioned) with compile-time
>vs execution-time expansion, but they apply similarly to local
>and global declarations.
Issues unrelated to variable scoping - I presume.
> > If you compile everything as is done in ECLiPSe,
>
>This is incorrect. ECLiPSe loops can be both compiled or meta-called,
>as is clearly stated in the original paper. Also, the 200-line
>implementation that has been publicly available for about 8 years
>provides both, see http://www.eclipse-clp.org/software/loops
>
>
> > the story is
> > different because the set of variables accessible to the compiler is
> > always fixed.
>
>Let me give some reasons why declaring 'globals' may be better a
>better idea than declaring 'locals':
(Agreed with all of them), but let me add two arguments against:
The declaration of globals goes against the traditional view
of variable scoping in lambda calculus and its incarnations.
A slavish reduplication will thus try to fine a way around
explicit declarations.
Nested loops often require verbose redeclarations of globals
for each level.
And then another argument in favor:
Globals are less in do-loops, because certain variables
are implicitely quantified. You mention this in passing below.
But it seems people will miss this point.
>* The killer: when subgoals inside the loop body get goal-expanded,
>new local variables may be introduced by the expansion, and need
>to be made known to the enclosing loop - that's difficult.
How often have I heard the argument: Oh - it will be fixed during
term-expansion &ct. But effectively, I have never seen a system
doing this.
>And here is another argument in favour of 'global declarations':
>They can be seen as just another form of iterating over data.
>
>Consider the minimalist explanation of do-loops at
>http://www.eclipse-clp.org/software/loops: the essence is
>that any do-loop can be expressed solely in terms of
>fromto(Start,In,Out,Stop) iterators, which embody the
>concept of the logic programming accumulator.
>
>The small example above can then be written in normalised form as
>
>write_list(Stream, List) :-
> ( fromto(List,[X|Xs],Xs,[]), % short: foreach(X,List)
> fromto(Stream,Stream,Stream,_) % short: param(Stream)
> do
> write(Stream, X)
> ).
>
>As you see, the 'global declaration' param(Stream) is nothing but a
>'constant iterator' i.e. a term that remains the same through all
>iterations. I don't think you can do any simpler than that.
These fromto/4 ... wouldn't they merit to be realized using
some call/N-compatible continuation? Often there is so much
to look at, and no way to remove it (except by resorting
to the implementation and adding a new construct).
afa
wrote:
>> If you compile everything as is done in ECLiPSe,
>This is incorrect. ECLiPSe loops can be both compiled or meta-called,
I thought loops in ECLiPSe were only compiled, but that was incorrect.
Thank you for your correction.
> Let me give some reasons why declaring 'globals' may be better a
> better idea than declaring 'locals':
>
> * Other have already mentioned that with local declarations you can't
> use anonymous variables in the loop body, as they would need to be
> declared local.
I agree that this is a weakness of the global-by-default approach. The
compiler should issue a warning if it sees a singleton variable in a
loop but it is not declared local. This will alleviate the problem.
> modifying code. Also, such loops tend to have many more local than
> global variables.
Can you show us an example that contains more local variables than
global ones? In the construct I am proposing,
foreach(I1 in D1,...,In in Dn, LocalVars,Goal)
all variables occurring in Ii's are assumed to be local and hence need
not to be declared. As I mentioned before, Array notations are also
assumed to be local. At least in the programs I have written, I see
more global variables than local ones. Your write_list example can be
written as follows, in which no variable declaration is needed:
write_list(Stream, List) :-
foreach(X in List, write(Stream, X)).
> * The killer: when subgoals inside the loop body get goal-expanded,
> new local variables may be introduced by the expansion, and need
> to be made known to the enclosing loop - that's difficult.
This does not happen in the B-Prolog compiler. When a loop is
expanded, its enclosing loop is also expanded. The compiler may
introduce new local variables for array notations but these variables
never need to be declared and never cause any problems.
I noticed that copy_term is used in your interpreter. This is
problematic because (1) it is expensive to copy everything, especially
when the term contains big hash tables and arrays; and (2) its
behavior is not well defined when the term contains attributed
variables including domain variables. So I believe that global-by-
default (i.e., declaring local variables) is the right approach we
should take.
Cheers,
Neng-Fa
afa
wrote:
> afa wrote:
> > ...
>
> > qsort([],[]).
> > qsort([H|T],S):-
> > L1 @= [X : X in T, X<H],
>
> I think that interpreting certain list templates as comprehensions
> is a really bad idea (see Ulrich's example, which is only the tip of
> the iceberg), and too high a price to pay for "looking like Haskell".
Could you elaborate on this? What is the price we need to pay to
support this notation?
Cheers,
Neng-Fa
Ulrich Neumerkel
>On Jan 18, 8:31=A0pm, Joachim Schimpf <jschi...@users.sourceforge.net>
>wrote:
>> * The killer: when subgoals inside the loop body get goal-expanded,
>> new local variables may be introduced by the expansion, and need
>> to be made known to the enclosing loop - that's difficult.
>
>This does not happen in the B-Prolog compiler. When a loop is
>expanded, its enclosing loop is also expanded. The compiler may
>introduce new local variables for array notations but these variables
>never need to be declared and never cause any problems.
I believe Joachim meant this in a more broader senses. There are more
goal expansions that just loops.
>I noticed that copy_term is used in your interpreter. This is
>problematic because (1) it is expensive to copy everything, especially
>when the term contains big hash tables and arrays; and (2) its
>behavior is not well defined when the term contains attributed
>variables including domain variables. So I believe that global-by-
>default (i.e., declaring local variables) is the right approach we
>should take.
The copy_term needed for local variables must not copy constraints.
In SWI, YAP it is called copy_term_nat/3. Or copy_term/3 with a void last
argument (similar to SICStus).
Ulrich Neumerkel
>On Jan 18, 11:37=A0pm, Joachim Schimpf <jschi...@users.sourceforge.net>
Ambiguity. What shall L @= [A] mean? Is this equivalent to L = [A]?
An instance of it with A = (t:t in []) and thus L = []...
So depending on the term within A, we interpret the list differently.
Usually, an instance is a specialization. Now, it becomes something
different.
afa
Neumerkel) wrote:
Hey, don't be picky on this little cute notation:-) What about its old
brothers and sisters.
?- E = (1+2), X is E.
?- A=(X=a), B=(X=b), C=(1>2->A), (C;B).
There is no ambiguity here. In a call to @=/2, if an argument is a
normal list you get the list and if it is a list constructor in the
form [E : I1 in D1,...,In in Dn,Goal] you get the list yielded from
the constructor.
Cheers,
Neng-Fa
Ulrich Neumerkel
>On Jan 19, 5:10=A0pm, ulr...@mips.complang.tuwien.ac.at (Ulrich
>Neumerkel) wrote:
>> Usually, an instance is a specialization. =A0Now, it becomes something
>> different.
>
>Hey, don't be picky on this little cute notation:-) What about its old
>brothers and sisters.
>
>?- E = (1+2), X is E.
No problem, since X is E produces an instantiation error.
So the inconsistency is hidden by the error. That's one
good point of the ISO error system.
>?- A=(X=a), B=(X=b), C=(1>2->A), (C;B).
That is a weak point of control constructs and their
exact treatment w.r.t 7.6. But that does not mean that
new construct shall have the same problems.
BTW: Do you ever use the control construct (A->B) directly,
without (;)/2 around? Looks like a good candidate for warnings.
>There is no ambiguity here. In a call to @=/2, if an argument is a
>normal list you get the list and if it is a list constructor in the
>form [E : I1 in D1,...,In in Dn,Goal] you get the list yielded from
>the constructor.
The ambiguity comes from (my) expectation that by removing
a single goal (=)/2 we get a generalization. This looks
like a very useful property of logic programs. Without
that property we can only rely on less declarative
reasoning.
Ulrich Neumerkel
>afa <neng...@gmail.com> writes:
>>On Jan 19, 5:10=A0pm, ulr...@mips.complang.tuwien.ac.at (Ulrich
>>Neumerkel) wrote:
>>> different.
>>
>>Hey, don't be picky on this little cute notation:-) What about its old
>>brothers and sisters.
You forgot to mention another black sheep: setof/3! Here, local
variables have to be declared explicitly - as in your loops. It is a
good example to enlighten variable scoping.
Similarly to your loops, anonymous variables behave in an unexpected
manner within setof/3. Consider a relation like
member(X-N,[a-1,b-1,a-2]). You want the list of all X.
?- setof(X,member(X-_,[a-1,b-1,a-2]),Xs).
Xs = [a, b]
Works! Almost... there is another solution:
Xs = [a].
Quite tricky do debug for the unexpected. What actually has been
described here corresponds to:
?- setof(X,member(X-N,[a-1,b-1,a-2]),Xs).
N = 1,
Xs = [a, b] ;
N = 2,
Xs = [a].
To get the expected list, we need a declaration for N as a local
variable:
?- setof(X,N^member(X-N,[a-1,b-1,a-2]),Xs).
Xs = [a, b].
Let us read above query from left-to-right in slow motion:
setof(X, ... this describes a list with elements of the form X
N^ ... alert! N is here a local variable, you can ignore
it outside. Please ignore N outside! Just
don't think about N - in the same manner you shall
never think about blue icebears! Don't put that mental
burden of N into your brain!
So prior to seeing what this goal is about - how variables might be
related to the outside, we get first the highly useless information
that something is only of local interest and - contrary to the 'let'
in FP - we only see the name of the variable, we do not see the
associated expression. So you read those variables ^ after ^ that are
important - not! As long as the goal is a short one this is harmless.
But if the goal is bigger it really hurts. Why shall we first talk
about the things that are *not* of interest?
It is not only anonymous variables, but also existential variables
that cause this pain in setof/3. Existential variables occur
when some intermediary result is needed.
Contrast this to declarations for global variables: They show you the
interfacing variables first. These are of relevance to both the user
of the goal as well as the writer of that same goal.
Have you ever written a Goal^Goal within setof/3? That's
tantamount to saying: No thanks, I don't like that scoping.
The only nice use is setof(t, Goal, _) which is the idiom to
remove redundant solutions.
Fortunately, setof/3 can be sanitized with the help of libary(lambda).
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord#setof
The original motivation for the convention in setof/3 was quite noble:
To make it behave like "normal" relations. A query like
?- setof(X,member(X-1,[a-1,b-1,a-2]), Xs).
Xs = [a, b].
can be generalized into:
?- setof(X,member(X-N,[a-1,b-1,a-2]), Xs).
N = 1,
Xs = [a, b] ;
N = 2,
Xs = [a].
By consequence,
?- N = 2, setof(X,member(X-N,[a-1,b-1,a-2]), Xs).
N = 2,
Xs = [a].
gives the same result (modulo termination, errors...) as
?- setof(X,member(X-N,[a-1,b-1,a-2]), Xs), N = 2.
N = 2,
Xs = [a].
However, this only holds for variables unrelated to the schema. It
does not hold for:
?- Gen = X-1, setof(X,member(X-1,[a-1,b-1,a-2]), Xs).
Gen = X-1,
Xs = [a, b].
?- setof(X,member(Gen,[a-1,b-1,a-2]), Xs), Gen = X-1.
X = a,
Gen = a-1,
Xs = [_G394] ;
X = b,
Gen = b-1,
Xs = [_G383].
So it works only for certain variables.
Joachim Schimpf
> On Jan 19, 5:10 pm, ulr...@mips.complang.tuwien.ac.at (Ulrich
> Neumerkel) wrote:
>> afa <neng.z...@gmail.com> writes:
>>> On Jan 18, 11:37=A0pm, Joachim Schimpf <jschi...@users.sourceforge.net>
>>> wrote:
>>>> afa wrote:
>>>>> ...
>>>>> qsort([],[]).
>>>>> qsort([H|T],S):-
>>>>> L1 @= [X : X in T, X<H],
>>>> I think that interpreting certain list templates as comprehensions
>>>> is a really bad idea (see Ulrich's example, which is only the tip of
>>>> the iceberg), and too high a price to pay for "looking like Haskell".
>>> Could you elaborate on this? What is the price we need to pay to
>>> support this notation?
>> Ambiguity. What shall L @= [A] mean? Is this equivalent to L = [A]?
>> An instance of it with A = (t:t in []) and thus L = []...
>> So depending on the term within A, we interpret the list differently.
>>
>> Usually, an instance is a specialization. Now, it becomes something
>> different.
>
> Hey, don't be picky on this little cute notation:-)
It's tempting to get wedded to something (or someone!) cute,
and easy to overlook the flaws your friends point out...
> What about its old
> brothers and sisters.
>
> ?- E = (1+2), X is E.
Not really the same thing. Remember I suggested to use a dedicated
function listof/2 that would return a list, analogous to +/2 returning
a number. I think that's fine.
Your notation is worse because what looks like a perfectly proper
2-element list, e.g. [X:X in 1..9, true] is actually meant to be a
9-element list. No generic list predicate will spot the error if
you forget to evaluate, e.g. length([X:X in 1..9, true],N) will
happily return 2, append/3 will happily append two comprehensions, etc.
> There is no ambiguity here. In a call to @=/2, if an argument is a
> normal list you get the list and if it is a list constructor in the
> form [E : I1 in D1,...,In in Dn,Goal] you get the list yielded from
> the constructor.
You are right that there is no ambiguity as long as you allow
comprehension terms only at the top level of the right hand side
of @=/2. But since it's so cute, you have already started to allow
them in other contexts, e.g. as arguments to constraints where normally
a proper list is expected. The more you do that, the harder it gets to
remember where they are evaluated and where not. E.g. I could
reasonably expect that it is accepted here:
?- Xs @= [1,2|[X:X in 3..9]].
Xs = [1, 2, X : X in 3 .. 9]
I get a list back, as expected, but find later that it's not the
one I wanted.
The quote/eval problem with functional notation is bad enough as it is.
If your unevaluated and evaluated terms are even of the same type,
you are making things worse.
>
> ?- A=(X=a), B=(X=b), C=(1>2->A), (C;B).
A historical mistake, not to be replicated. Leads to effects like:
p(X) :- A=(true->X=a), (A;X=b). % 2 solutions
q(X) :- A=(true->X=a), call((A;X=b)). % 1 solution
-- Joachim
Joachim Schimpf
> Joachim Schimpf <jsch...@users.sourceforge.net> writes:
>> There are indeed issues (so far unmentioned) with compile-time
>> vs execution-time expansion, but they apply similarly to local
>> and global declarations.
>
> Issues unrelated to variable scoping - I presume.
I was referring to cases where you get different behaviour
depending on whether you expand at compile-time or run-time.
They occur with both techniques:
With Neng-Fa's construct:
Compile-time expanded, X is correctly considered local:
?- X=foo, foreach(_ in 1..5, [X], writeq(X)).
_378_400_422_444_466
Run-time expanded (interpreted), X behaves as if global:
?- X=foo, call(foreach(_ in 1..5, [X], writeq(X))).
foofoofoofoofoo
ECLiPSe do-loops:
Compile-time expanded, X is correctly considered local:
?- X=foo, ( for(_,1,5) do writeq(X) ).
*** Warning: Singleton local variable X in do-loop, maybe param(X) missing?
_8083_8084_8085_8086_8087
Run-time expanded (interpreted), X behaves as if global:
?- X=foo, call(for(_,1,5) do writeq(X)).
foofoofoofoofoo
What that means is: it should be considered an error if a local loop
variable occurs also outside the loop, because then its locality
cannot be reliably enforced.
-- Joachim
Joachim Schimpf
>> use anonymous variables in the loop body, as they would need to be
>> declared local.
>
> I agree that this is a weakness of the global-by-default approach. The
> compiler should issue a warning if it sees a singleton variable in a
> loop but it is not declared local. This will alleviate the problem.
For a special purpose construct for the applications you have
considered, it may just be a weakness.
For a general purpose control construct (which is what ECLiPSe loops
are designed for) it is unacceptable: control constructs must work
with _any_ body goal. We should not repeat the bagof mistake.
By the way, you could use the existing bagof notation Localvar^Goal.
>
>> modifying code. Also, such loops tend to have many more local than
>> global variables.
>
> Can you show us an example that contains more local variables than
> global ones?
Will you change your mind if I give you one example? Probably not.
50 examples? You will probably say they should be rewritten with
auxiliary predicates. I can't win. If you want to see some, you
can look at some ECLiPSe source, e.g. the compiler, graph_algorithms
library etc. You'll see that many uses look _very_ different from
your examples.
Ok, I give one example from a contributed ECLiPSe library (not my
own code, and still a very small loop). You see that the param's
together with the foreach 'make sense', they tell you what data
the loop operates on. The 5(?) local variables are uninteresting.
update_residual_capacities(ResidualCapacities, Path, PathSize):-
(
foreach(e(S,D,ResCapacity),Path),
param(ResidualCapacities,PathSize)
do
NewResCapacity is ResCapacity - PathSize,
arg(S,ResidualCapacities,AdjEdges),
hash_set(AdjEdges,D,NewResCapacity),
% and _add_ PathSize to opposite direction
arg(D,ResidualCapacities,OppAdjEdges),
hash_get(OppAdjEdges,S,OppResCapacity),
NewOppResCapacity is OppResCapacity + PathSize,
hash_set(OppAdjEdges,S,NewOppResCapacity)
).
> In the construct I am proposing,
>
> foreach(I1 in D1,...,In in Dn, LocalVars,Goal)
>
> all variables occurring in Ii's are assumed to be local and hence need
> not to be declared.
Such ad-hoc rules break reasonable assumptions. Consider the different
behaviour of your construct in these cases, where all I have done is
factoring out a unification:
?- List=[f(A),f(B)], foreach(f(X) in List, writeq(f(X))).
f(_72)f(_83)
?- List=[f(A),f(B)], foreach(T in List, (T=f(X), writeq(f(X)))).
f(_72)f(_72)
> As I mentioned before, Array notations are also assumed to be local.
Another ad-hoc rule. Why should loops treat arrays specially?
>> * The killer: when subgoals inside the loop body get goal-expanded,
>> new local variables may be introduced by the expansion, and need
>> to be made known to the enclosing loop - that's difficult.
>
> This does not happen in the B-Prolog compiler. When a loop is
> expanded, its enclosing loop is also expanded. The compiler may
> introduce new local variables for array notations but these variables
> never need to be declared and never cause any problems.
When you goal-expand top-down, you can get around the problem.
It means you always have to expand the loop itself before you can
expand the body goals (which are then already safely inside an
auxiliary clause), and you must not compile-time expand any body
goals when the loop itself gets interpreted.
>
> I noticed that copy_term is used in your interpreter. This is
> problematic because (1) it is expensive to copy everything, especially
> when the term contains big hash tables and arrays;
The amount of copying depends on _whether_ variables are local/global,
not on _how_ this is specified. The amount of copying needed is
therefore the same for you and me. You are correct in that my published
code does some unnecessary copying in the interpreted case (basically
because it uses the same code for interpretation and compile-time
expansion), but that can be fixed, and is also not terribly important
since loops are rarely interpreted in practice.
> and (2) its
> behavior is not well defined when the term contains attributed
> variables including domain variables.
The published code is meant for plain Prolog systems. Systems with
attributed variables should strip attributes from local variables.
> So I believe that global-by-
> default (i.e., declaring local variables) is the right approach we
> should take.
"we"?
-- Joachim
Ulrich Neumerkel
>Ulrich Neumerkel wrote:
> > Joachim Schimpf <jsch...@users.sourceforge.net> writes:
> >> There are indeed issues (so far unmentioned) with compile-time
> >> vs execution-time expansion, but they apply similarly to local
> >> and global declarations.
> >
> > Issues unrelated to variable scoping - I presume.
>
>I was referring to cases where you get different behaviour
>depending on whether you expand at compile-time or run-time.
>They occur with both techniques:
They occur with both *implementations*.
I believe both - quite similar to library(lambda) should always
behave fully dynamically. If the compiler cannot prove
that this can be maintained then compilation must not take place.
Id est, everything is left untouched for dynamic interpretation;
or: compilation is refused with a clean error. Warnings
alone accompanied with incorrect compilation should be avoided.
By consequence, compilation cannot be performed with local goal
expansion since more information is needed about the context.
Wouldn't this be a nice occasion to hash out a better interface
than goal expansion that is more modular than term expansion?
Ulrich Neumerkel
>> ?- A=(X=a), B=(X=b), C=(1>2->A), (C;B).
>
>A historical mistake, not to be replicated.
What would have been *not* a mistake in your view?
Do you remember the compiler vs. interpreter wars? (Never
forget: don't say interpreter, dont' say compiler, just
say processor. And a processor neither compiles or interprets.
It prepares for execution and then it executes.) It is
astonishing that anything has been found with some agreement
at all. The primary concern was the !.
I.e. Shall X = !, ( X, fail ; true ) succeed or not.
> Leads to effects like:
>
>p(X) :- A=(true->X=a), (A;X=b). % 2 solutions
>
>q(X) :- A=(true->X=a), call((A;X=b)). % 1 solution
The only *economical* way out I see is to issue an existence
error for (->)/2 in p/1. Have you ever used (->)/2 alone
in a program?
Ulrich Neumerkel
>afa wrote:
> > On Jan 18, 8:31 pm, Joachim Schimpf <jschi...@users.sourceforge.net>
> >> global variables.
> >
> > Can you show us an example that contains more local variables than
> > global ones?
>
>Will you change your mind if I give you one example? Probably not.
>50 examples? You will probably say they should be rewritten with
>auxiliary predicates. I can't win.
Why not? We could have a to-be-discovered win-win-win situation!
There are some very good points in favor of Neng-Fa's current
foreach. I like very much the two-dimensional array loops. Admit
it: The nesting works more smoothly! Of course, ad-hoc rules
behind. But nevertheless. Neng-Fa developed his foreach with arrays
in mind. That kind of nesting does not work nicely with do-loops.
afa
wrote:
> afa wrote:
> By the way, you could use the existing bagof notation Localvar^Goal.
Thanks for your suggestion. In foreach this notation can be adopted
but in a list comprehension this notation doesn't work because no goal
may exist but there are still local variables as in:
?-[Y : X in 1..10,[Y]].
> update_residual_capacities(ResidualCapacities, Path, PathSize):-
There are five locals and two globals. True, there are more locals
than globals in this example. But if array notation could be used on
hash tables, as is the case in C#, then the number of locals could be
reduced to two. This is not the point. My claim is that in general,
there are more globals than locals (actually your example is the first
one I have ever seen that contains more locals than globals). Are you
aware of any other language in which you need to declare globals and
assume everything else local?
> ?- List=[f(A),f(B)], foreach(f(X) in List, writeq(f(X))).
> f(_72)f(_83)
>
> ?- List=[f(A),f(B)], foreach(T in List, (T=f(X), writeq(f(X)))).
> f(_72)f(_72)
With warnings, the user can be informed of it if a variable is
intended to be global or not. Here is what you get with B-Prolog
7.4b3.
| ?- List=[f(A),f(B)], foreach(f(X) in List, writeln(f(X))).
f(_2f8)
f(_348)
| ?- List=[f(A),f(B)], foreach(T in List, (T=f(X), writeln(f(X)))).
** Warning ** Variable X treated as global in foreach.
f(_2f8)
f(_2f8)
Cheers,
Neng-Fa
bart demoen
> ?- Xs @= [1,2|[X:X in 3..9]].
> Xs = [1, 2, X : X in 3 .. 9]
>
> I get a list back, as expected, but find later that it's not the one I
> wanted.
Worrying indeed.
I also worry about things like
Xs = [1,2|Z], functor(Z,'.',2), arg(1,Z,X), arg(2,X in 3 .. 9).
This sort of thing pops up any time one tries to introduce "functions"
in Prolog.
Cheers
Bart Demoen
Ulrich Neumerkel
>On Jan 21, 2:31=A0am, Joachim Schimpf <jschi...@users.sourceforge.net>
>wrote:
>> afa wrote:
>
>> By the way, you could use the existing bagof notation Localvar^Goal.
>
>Thanks for your suggestion. In foreach this notation can be adopted
>but in a list comprehension this notation doesn't work because no goal
>may exist but there are still local variables as in:
>
>?-[Y : X in 1..10,[Y]].
>
>> update_residual_capacities(ResidualCapacities, Path, PathSize):-
>
>There are five locals and two globals. True, there are more locals
>than globals in this example. But if array notation could be used on
>hash tables, as is the case in C#, then the number of locals could be
>reduced to two. This is not the point. My claim is that in general,
>there are more globals than locals (actually your example is the first
>one I have ever seen that contains more locals than globals). Are you
>aware of any other language in which you need to declare globals and
>assume everything else local?
The role of variables in Prolog is quite different to other languages.
In other languages, mentioning or referring to a variable has no effect
on the value of that variable. In most languages it has no effect at
all - except in the case of lazy evaluation, where reading a value might
result in nontermiation.
But in Prolog "mere" reading might set variables equal to each
other.
Consider
?- maplist(=(_), Xs).
Xs = [] ;
Xs = [_G1965] ;
Xs = [_G1965, _G1965] ;
Xs = [_G1965, _G1965, _G1965]
How do you implement this without ignoring this warning for
global variables?
afa
Neumerkel) wrote:
> Consider
>
> ?- maplist(=(_), Xs).
> Xs = [] ;
> Xs = [_G1965] ;
> Xs = [_G1965, _G1965] ;
> Xs = [_G1965, _G1965, _G1965]
>
> How do you implement this without ignoring this warning for
> global variables?
Yes, we can:-)
| ?- set_prolog_flag(warning,off)
| ?- Xs=[A,B,C],foreach(X in Xs, X=_)
Xs = [C,C,C]
A = C
B = C ?
Cheers,
Neng-Fa
Kish Shen
> My claim is that in general,
> there are more globals than locals (actually your example is the first
> one I have ever seen that contains more locals than globals).
As Joachim suggested, you can look at ECLiPSe's source for many examples
of do loops, and many of these have more local than global variables.
The do loops have been in ECLiPSe for quite a few years, so there is
quite a lot of experience in using them in many different situations.
Cheers,
Kish
Ulrich Neumerkel
>On Jan 21, 7:01=A0pm, ulr...@mips.complang.tuwien.ac.at (Ulrich
>Neumerkel) wrote:
>> Consider
>>
>> ?- maplist(=3D(_), Xs).
>> Xs =3D [] ;
>> Xs =3D [_G1965] ;
>> Xs =3D [_G1965, _G1965] ;
>> Xs =3D [_G1965, _G1965, _G1965]
>>
>> How do you implement this without ignoring this warning for
>> global variables?
>
>Yes, we can:-)
To equality?
>| ?- set_prolog_flag(warning,off)
>
>| ?- Xs=3D[A,B,C],foreach(X in Xs, X=_)
>Xs =3D [C,C,C]
>A =3D C
>B =3D C ?
Hmhm:
B-Prolog Version 7.4b3.1, All rights reserved, (C) Afany Software 1994-2010.
...
| ?- Xs=[A,B,C],foreach(X in Xs, X=_).
** Warning ** Variable _ is treated as global in foreach (0-0).
Xs = [C,C,C]
A = C
B = C ?;
no
| ?- foreach(X in Xs, X=_).
** Warning ** Variable _ is treated as global in foreach (0-0).
*** wrong_domain(_29c)
We know the battle ahead will be long...
afa
Neumerkel) wrote:
> afa <neng.z...@gmail.com> writes:
> >On Jan 21, 7:01=A0pm, ulr...@mips.complang.tuwien.ac.at (Ulrich
> >Neumerkel) wrote:
>
> >> How do you implement this without ignoring this warning for
>
> ^^^^^^^^^^^^^^^^
>
> >> global variables?
>
> >Yes, we can:-)
>
> To equality?
>
> >| ?- set_prolog_flag(warning,off)
How about this one then?
?- Xs=[A,B,C],G=G,foreach(X in Xs, X=G).
If a variable occurs outside foreach, you don't get a warning.
>| ?- foreach(X in Xs, X=_).
>** Warning ** Variable _ is treated as global in foreach (0-0).
>*** wrong_domain(_29c)
>We know the battle ahead will be long...
You cannot iterate over an incomplete list. I see this as an advantage
of the foreach I am proposing. When you use the same foreach to both
construct and iterate over lists (as you do in ECLiPSe), you get
really unreadable code.
Cheers,
Neng-Fa
Kish Shen
> You cannot iterate over an incomplete list. I see this as an advantage
> of the foreach I am proposing. When you use the same foreach to both
> construct and iterate over lists (as you do in ECLiPSe), you get
> really unreadable code.
I think it is no more unreadable than the equivalent in Prolog (i.e. if
an argument is input or output), and you can use the same conventions as
in Prolog for indicating an output argument to make things clearer.
(putting such for foreach last in your specifications, adding comments,
etc.)
ECLiPSe loops, as Joachim said, is designed to be a general control
construct, as an alternative way to write recursion, so that you don't
have to have all these auxiliary predicates that you have to invent
meaningful names for. There are many cases where I have used loops to
construct terms.
Cheers,
Kish
Ulrich Neumerkel
>afa wrote:
>> You cannot iterate over an incomplete list. I see this as an advantage
>> of the foreach I am proposing. When you use the same foreach to both
>> construct and iterate over lists (as you do in ECLiPSe), you get
>> really unreadable code.
>
>I think it is no more unreadable than the equivalent in Prolog (i.e. if
>an argument is input or output), and you can use the same conventions as
>in Prolog for indicating an output argument to make things clearer.
>(putting such for foreach last in your specifications, adding comments,
>etc.)
One strong point of ECLiPSe loops is this symmetry which reflects
the symmetry in the corresponding pure program. I like this a lot.
>ECLiPSe loops, as Joachim said, is designed to be a general control
>construct, as an alternative way to write recursion, so that you don't
>have to have all these auxiliary predicates that you have to invent
>meaningful names for. There are many cases where I have used loops to
>construct terms.
The control construct does not exactly replace the corresponding
pure program. To take the homologe of maplist(=(_), Xs).
Version 6.0 #105 (i386_linux), Wed Dec 2 00:09 2009
[eclipse 1]: ( foreach(X, Xs), param(X) do true ), Xs = [_|_].
...
ecl_compiler.eco loaded in 0.16 seconds
No (0.00s cpu)
So there is silent failure in place of an answer.
In this respect, I would prefer B (in particular, if
it would produce an instantiation error), as it does not
purpot that there is no solution.
Joachim Schimpf
> The control construct does not exactly replace the corresponding
> pure program. To take the homologe of maplist(=(_), Xs).
>
> Version 6.0 #105 (i386_linux), Wed Dec 2 00:09 2009
> [eclipse 1]: ( foreach(X, Xs), param(X) do true ), Xs = [_|_].
> ...
> ecl_compiler.eco loaded in 0.16 seconds
>
> No (0.00s cpu)
>
> So there is silent failure in place of an answer.
>
> In this respect, I would prefer B (in particular, if
> it would produce an instantiation error), as it does not
> purpot that there is no solution.
I'm getting a bit tired of you repeating the same complaint and
me giving the same answer. The behaviour is simply due to a cut,
and this cut is in the same spirit as the cut in if-then-else,
and causes the same effects. There is nothing new here.
?- ( Xs=[] -> true ; Xs = [a] ), Xs = [_|_].
No.
This cut is not essential to do-loops. It was more a practical
than a theoretical consideration (avoid accidental choicepoints),
and I decided 12 years ago to have it in the ECLiPSe implementation.
It has worked well, probably because we are working under the
assumption that a loop has a deterministic termination condition,
just like we work under the assumption that an if-then-else has
a deterministic condition.
I understand that you have different priorities for teaching.
In that case, just take the cut out, use it for a few years,
then we compare results.
-- Joachim
Ulrich Neumerkel
>Ulrich Neumerkel wrote:
>> The control construct does not exactly replace the corresponding
>> pure program. To take the homologe of maplist(=(_), Xs).
>>
>> Version 6.0 #105 (i386_linux), Wed Dec 2 00:09 2009
>> [eclipse 1]: ( foreach(X, Xs), param(X) do true ), Xs = [_|_].
>> ...
>> ecl_compiler.eco loaded in 0.16 seconds
>>
>> No (0.00s cpu)
>>
>> So there is silent failure in place of an answer.
>>
>> In this respect, I would prefer B (in particular, if
>> it would produce an instantiation error), as it does not
>> purpot that there is no solution.
>
>I'm getting a bit tired of you repeating the same complaint and
>me giving the same answer. The behaviour is simply due to a cut,
>and this cut is in the same spirit as the cut in if-then-else,
>and causes the same effects. There is nothing new here.
>
>?- ( Xs=[] -> true ; Xs = [a] ), Xs = [_|_].
>No.
The point of the discussion is to compare the various formalisms.
It seems - not surprisingly - they all have advantages and
disadvantages.
Do-loops are intended as an alternative way to write (some
simple forms of) recursion. See the "Description" in
http://87.230.22.228/doc/bips/kernel/control/do-2.html
But that alternative way introduces red cuts into programs that
have been pure before!
That means, to fully understand do-loops you will have to understand
that subtle interaction of cuts in that context. In most stituations
that is not necessary - however, when debugging a program (that
implies that we have a program where something is wrong), things
will become tricky. Seems that fromto/4 is most risque.
Neng-Fa at least produces an error - that avoids incorrect results.
Maybe there is even a better way than that.
>This cut is not essential to do-loops.
It is essential for for(_,1,4) do true. Same also for the
fromto/4 construct.
> It was more a practical
>than a theoretical consideration (avoid accidental choicepoints),
>and I decided 12 years ago to have it in the ECLiPSe implementation.
>It has worked well, probably because we are working under the
>assumption that a loop has a deterministic termination condition,
>just like we work under the assumption that an if-then-else has
>a deterministic condition.
In most situations that is a reasonable assumption. But even
for those programs do-loops have unexpected properties! See
below.
>I understand that you have different priorities for teaching.
>In that case, just take the cut out, use it for a few years,
>then we compare results.
Taking the cut out would make for(_,1,4) do true
nonterminating. So this is not only about efficiency.
Already for(_,1,3), for(_,1,2) do true.
does not terminate.
There are many areas -like variable scoping- where do-loops
are perfect. Why not strive to get the remaining issues solved?
This red cut is not the only thing. For nested loops, Neng-Fa
has the more compact formalism. Using call/N for the iterators
wouldn't hurt as well.
Ulrich Neumerkel
We need to distinguish two different situations:
Simple loops and nested loops.
I will discuss simple loops only - as they are the more frequent
case:
Even if Neng Fa's claim that globals outnumber locals would be true,
the explicit declaration of the global variables has advantages:
With ECLiPSe loops it is easy to tell the interface of a loop to
the outside: You only need to read the first argument of do.
There is no need to read the body of the loop. With time, loop
bodies seem to get bigger and bigger.
With B's foreach we have to scan the entire construct before
we can tell which variable is a global one. That looks very
cumbersome to me.
If you want to transform a loop into a new predicate, also
only the first argument of do is of relevance.
For nested loops and twodimensional arrays, the situation is
much less evident.
Joachim Schimpf
> Do-loops are intended as an alternative way to write (some
> simple forms of) recursion. See the "Description" in
> http://87.230.22.228/doc/bips/kernel/control/do-2.html
> But that alternative way introduces red cuts into programs that
> have been pure before!
I have never claimed that do-loops are pure. As I said, they
are in the spirit of if-then-else. In both cases, the implicit
cut is only red when you ignore the manual and use the construct
in a way that it is not intended for (i.e. has contradictory or
nondeterministic termination conditions).
I'm very happy for you to promote higher order stuff and lambda
expressions. Just as I have told you earlier, I started with maplist
and friends, then wrote library(apply_macros) implementing their
compiled forms, and ended up with do-loops. And the experience
after many years is that the loops are _much_ more widely used
than higher order constructs ever were.
> That means, to fully understand do-loops you will have to understand
> that subtle interaction of cuts in that context. In most stituations
> that is not necessary - however, when debugging a program (that
> implies that we have a program where something is wrong), things
> will become tricky. Seems that fromto/4 is most risque.
You keep using future tense "will have to", "will become", and it is
all very well to imagine such scenarios. But can I politely point
out that we have >12 years of in-production use of these constructs
and can therefore rely on some actual experience.
>> This cut is not essential to do-loops.
>
> It is essential for for(_,1,4) do true.
Oh, come on. You are smart enough to fill in the details.
Of course you will insert an extra test when you remove the cut.
> Same also for the fromto/4 construct.
No, why? Once it's nondeterministic, there is no problem.
> Taking the cut out would make for(_,1,4) do true
> nonterminating. So this is not only about efficiency.
> Already for(_,1,3), for(_,1,2) do true.
> does not terminate.
See above.
> Using call/N for the iterators wouldn't hurt as well.
I don't know what you mean.
-- Joachim
Ulrich Neumerkel
>Ulrich Neumerkel wrote:
>> Do-loops are intended as an alternative way to write (some
>> simple forms of) recursion. See the "Description" in
>> http://87.230.22.228/doc/bips/kernel/control/do-2.html
>> But that alternative way introduces red cuts into programs that
>> have been pure before!
>
>I have never claimed that do-loops are pure. As I said, they
>are in the spirit of if-then-else. In both cases, the implicit
>cut is only red when you ignore the manual and use the construct
>in a way that it is not intended for (i.e. has contradictory or
>nondeterministic termination conditions).
It is frequently (mis-) understood that they are pure. And I do not
see any warning pertaining to this in the link above. What did I
miss?
>I'm very happy for you to promote higher order stuff and lambda
>expressions. Just as I have told you earlier, I started with maplist
>and friends, then wrote library(apply_macros) implementing their
>compiled forms, and ended up with do-loops. And the experience
>after many years is that the loops are _much_ more widely used
>than higher order constructs ever were.
We agree that maplist/2,... alone is not enough. maplist/2,..
together with library(lambda) is better - but on the one hand it is
limited due to its expressiveness and on the other hand even for the
cases where it works, its inevitable argument order is often as
unintuitive as mapcar in Lisp. The reason is that the variable
denoting an element - say X and the corresponding list Xs are so far
apart:
?- maplist(\X^( r(X,Y), verylengthy_code(X), ...), Xs),
^ ^
Indentation does not solve this convincingly. Neither in Lisp nor
Prolog. It so more friendly to the eye, if X and Xs are next to each
other, as both ECLiPSe and B do it! In ECLiPSe, any further addition
to the body can be performed without hampering readability (speaking
about unnested loops):
?- ( foreach(X,Xs) do r(X,Y), verylengthy_code(X), ... ).
^
This small distance is really refreshing to look at! Ahh my eyestrain
fades... not completely - but let's keep us focused.
Something that is nice of maplist and do-loops is this (I tend to
repeat myself on this - but permit me say nice things too...)
preservation of the symmetry in the arguments. There is no inherent
input or output.
Another issue:
alldifferent([]).
alldifferent([X|Xs]) :-
maplist(dif(X),Xs),
alldifferent(Xs).
?- do(fromto(Xs0, [X|Xs],Xs, []), do( ( foreach(Y,Xs), param(X) ), dif(X,Y) ) ).
Compact formulation - but it could be more compact, could it not?
BTW how should the corresponding call/N based predicate be called? In
LISP it is maplist... I doubt that call/N based constructs ever got a
fair chance since their first public appearance in 1987.
>> That means, to fully understand do-loops you will have to understand
>> that subtle interaction of cuts in that context. In most stituations
>> that is not necessary - however, when debugging a program (that
>> implies that we have a program where something is wrong), things
>> will become tricky. Seems that fromto/4 is most risque.
>
>You keep using future tense "will have to", "will become", and it is
>all very well to imagine such scenarios. But can I politely point
>out that we have >12 years of in-production use of these constructs
>and can therefore rely on some actual experience.
I refer to the future as I would like to have it, indeed.
In that >12 years of in-production use what kind of debugging
techniques for constraints did you explore? Let me presume you are
not satisfied blaming everything on a failing labeling.
One of my points when insisting on these seemingly hairsplitting
properties is to have a safe basis for clean algebraic transformations
of programs such as to explain - e.g. failure in fd.
But take one example where you might agree with me: Termination
analysis. It is practically impossible to apply research results on
actual programs simply because implementation do not reflect the
orthogonality required.
But then there is progress:
At least SWI has an always terminating clpfd. No reason why not other
systems should do that as well. It so not that costly.
Also, it has a clean error producing occurs-check mode that can be
switched on and off (dynamically) with a Prolog flag. This is
strictly needed for most termination results.
Why not having a clean construct for loops as well? Everyone would
profit.
>> Using call/N for the iterators wouldn't hurt as well.
>
>I don't know what you mean.
Tomorrow.
Kish Shen
> alldifferent([]).
> alldifferent([X|Xs]) :-
> maplist(dif(X),Xs),
> alldifferent(Xs).
>
> ?- do(fromto(Xs0, [X|Xs],Xs, []), do( ( foreach(Y,Xs), param(X) ), dif(X,Y) ) ).
>
> Compact formulation - but it could be more compact, could it not?
I am not sure if being more compact is necessarily better, but there are
short-cuts for writing various nested do-loops patterns with a single
do, if the whole body of the outer loop is the inner loop. For example,
your example above can be written as:
(fromto(Xs0, [X|Xs], []) >> (foreach(Y,Xs), param(X)) do dif(X,Y)).
In fact, a very similar example (with writeln(X-Y) rather than dif(X,Y))
is given in the do loop documentation you point to.
(an aside: dif(X,Y) should be written as X ~= Y in ECLiPSe)
There are also iteration specifiers that allows you to avoid writing
nested do-loops, e.g. foreachelem/2, which iterates over all the
elements of a multi-dimensional array.
These were added to ECliPSe after Joachim's paper, so they are probably
less well known than the basic stuff, but they have been in ECLiPSe
since versions 5.8 and 5.9.
Cheers,
Kish
afa
> More examples are available at:
>
> http://probp.com/examples/index.html#FOREACH.
>
> a short article on them is available at:
>
> http://probp.com/download/loops.pdf
or
http://www.sci.brooklyn.cuny.edu/~zhou/papers/loops.pdf
I have just added a section into the article to compare the newly
proposed loop constructs with ECLiPSe's. The comparison is not
indented to be comprehensive, but a highlight of the differences,
weaknesses, and strengthens. I'll keep updating the article if
necessary. Comments are welcome.
Cheers,
Neng-Fa
Ulrich Neumerkel
>Ulrich Neumerkel wrote:
>> ?- do(fromto(Xs0, [X|Xs],Xs, []), do( ( foreach(Y,Xs), param(X) ), dif(X,Y) ) ).
>>
>> Compact formulation - but it could be more compact, could it not?
>
>I am not sure if being more compact is necessarily better, but there are
>short-cuts for writing various nested do-loops patterns with a single
>do, if the whole body of the outer loop is the inner loop.
I rather thought about this specifier fromto(Xs0, [X|Xs],Xs, []) and
not about abbreviating nested do-loops for the moment.
Suppose this specific use of fromto is used frequently, wouldn't it be
nicer to be able to give it a name *by the programmer*? Currently
there is an impressive collection of specifiers that are provided by
the system. Compactness in terms of character count is thus not the
goal.
Something alike:
nextl(_, _, [], done).
nextl(X, Xs, [X|Xs], next(Xs)).
Which would then be used via call/N.