AMZI! Prolog and for/4
Author Message
AMZI! Prolog and for/4

Hi there,

in AMZI! Prolog, the predicate for(Index, Start, End, Increment) is
defined as follows (quoted from the User's Guide & Reference):

for provides a shorthand for implementing repeat/fail loops that execute
a prespecified number of times. Bottom, Top and Increment must be bound
to integers with Bottom being less than or equal to Top. When first
proved Index is unified with Bottom and checked to see whether it is less
than or equal to Top. If so, for succeeds otherwise it fails.
On backtracking Increment is added to the current value of Index and
Index is bound to this new value. Again a range check is performed.

?- for(X, 1, 5, 1), write(X), fail.
12345
no

I can't find it listed as a part of ISO Prolog, and I think it's more than
just "a shorthand for implementing repeat/fail loops that execute a
prespecified number of times": on backtracking Index is bound to
the sum of Increment and the current value of Index.
Would this be possible in ISO Prolog? On backtracking Index becomes
unbound, so you won't be able to use its last value to calculate the next
one, right?

Leon

Mon, 17 Mar 2003 03:00:00 GMT
AMZI! Prolog and for/4

Quote:

>  ?- for(X, 1, 5, 1), write(X), fail.
>  12345
>  no

Think of the recursive definition:

X is between 1 and 5  <=>  X=1  or  X is between 2 and 5

--
Joachim Schimpf              /             phone: +44 20 7594 8187

London SW7 2AZ, UK         /    http://www.icparc.ic.ac.uk/eclipse

Mon, 17 Mar 2003 03:00:00 GMT
AMZI! Prolog and for/4

Quote:

> >  ?- for(X, 1, 5, 1), write(X), fail.
> >  12345
> >  no

> Think of the recursive definition:

> X is between 1 and 5  <=>  X=1  or  X is between 2 and 5

I know how to do it recursively, but in my original posting I wrote that
the manual mentioned that it was in some way short for a repeat...fail
loop, or, in other words, for an iterative solution.
So my question is: can the for/4 predicate be substituted by another
iterative solution?

Leon

Mon, 17 Mar 2003 03:00:00 GMT
AMZI! Prolog and for/4

Quote:

> I know how to do it recursively, but in my original posting I wrote that
> the manual mentioned that it was in some way short for a repeat...fail
> loop, or, in other words, for an iterative solution.

Ok, another hint: the definition of repeat is:

repeat.
repeat :- repeat.

member/2 looks very similar, and so does for/4...

--
Joachim Schimpf              /             phone: +44 20 7594 8187

London SW7 2AZ, UK         /    http://www.icparc.ic.ac.uk/eclipse

Mon, 17 Mar 2003 03:00:00 GMT
AMZI! Prolog and for/4

...

Quote:
> Hi there,

> in AMZI! Prolog, the predicate for(Index, Start, End, Increment)
> is defined as follows (quoted from the User's Guide & Reference):

>  for provides a shorthand for implementing repeat/fail loops that
>  execute a prespecified number of times. Bottom, Top and Increment
>  must be bound to integers with Bottom being less than or equal to
>  Top. When first proved Index is unified with Bottom and checked
>  to see whether it is less than or equal to Top. If so, for
>  succeeds otherwise it fails.  On backtracking Increment is added
>  to the current value of Index and Index is bound to this new
>  value. Again a range check is performed.

>  ?- for(X, 1, 5, 1), write(X), fail.
>  12345
>  no

> I can't find it listed as a part of ISO Prolog, and I think it's
> more than just "a shorthand for implementing repeat/fail loops
> that execute a prespecified number of times": on backtracking
> Index is bound to the sum of Increment and the current value of
> Index. Would this be possible in ISO Prolog?

Yes.

Quote:
> On backtracking Index becomes unbound, so you won't be able to
> use its last value to calculate the next one, right?

No. The definition of the for/4 predicate is self-explanatory:

/* 3-arity version - incremental only */
for(Num,_,Num).
for(Start,Stop,NumOut):-
Start1 = Start + 1,
Start1 <= Stop,
for(Start1,Stop,NumOut).

/* 4-arity version - incremental only */
for(Num,_,Num,_).
for(Start,Stop,NumOut,Step):-
Start1 = Start + Step,
Start1 <= Stop,
for(Start1,Stop,NumOut,Step).

and decremental values.

As Joachim pointed out, predicate functionality is dependant upon
recursive calls. But it is also dependant upon non-determinism.
The first call to the predicate succeeds with the first clause but
it also leaves a choice point to the second clause. Subsequent
failure in the calling predicate causes backtracking into the
second clause and the looping process (success on the first clause
and a new choice point on the second clause) is re-invoked by the
recursive last call. Repetition continues until the 'stop' value
has been reached. It's the first clause that returns the current
value (in the 1st call to the calling predicate, in subsequent
calls to the calling second clause). The second clause (with each
'new' choice point) holds the current value until it is backtracked
into, upon which it is incremented/decremented by the step value.

Daniel

Mon, 17 Mar 2003 03:00:00 GMT
AMZI! Prolog and for/4
hi,
where can I find the codes or index for build-in functions of sicstus
prolog?

thanks.

Mon, 17 Mar 2003 03:00:00 GMT
AMZI! Prolog and for/4
The program listing of for/N contains Visual prolog syntax. :-(
The lines

Start1 = Start + 1,
and
Start1 = Start + Step,

should be replaced with

Start1 is Start + 1,
and
Start1 is Start + Step,

respectively.

Sorry,
Daniel

[snipped]

Quote:
>     /* 3-arity version - incremental only */
>     for(Num,_,Num).
>     for(Start,Stop,NumOut):-
>         Start1 = Start + 1,
>         Start1 <= Stop,
>         for(Start1,Stop,NumOut).

>     /* 4-arity version - incremental only */
>     for(Num,_,Num,_).
>     for(Start,Stop,NumOut,Step):-
>         Start1 = Start + Step,
>         Start1 <= Stop,
>         for(Start1,Stop,NumOut,Step).

[snipped]

Tue, 18 Mar 2003 06:33:46 GMT
AMZI! Prolog and for/4
The program listing of for/N contains Visual Prolog syntax. :-(
The lines

Start1 = Start + 1,
and
Start1 = Start + Step,

should be replaced with

Start1 is Start + 1,
and
Start1 is Start + Step,

respectively.

Sorry,
Daniel

[snipped]

Quote:
>     /* 3-arity version - incremental only */
>     for(Num,_,Num).
>     for(Start,Stop,NumOut):-
>         Start1 = Start + 1,
>         Start1 <= Stop,
>         for(Start1,Stop,NumOut).

>     /* 4-arity version - incremental only */
>     for(Num,_,Num,_).
>     for(Start,Stop,NumOut,Step):-
>         Start1 = Start + Step,
>         Start1 <= Stop,
>         for(Start1,Stop,NumOut,Step).

[snipped]

Tue, 18 Mar 2003 06:35:04 GMT
AMZI! Prolog and for/4
The program listing of for/N contains Visual Prolog syntax. :-(
The lines

Start1 = Start + 1,
and
Start1 = Start + Step,

should be replaced with

Start1 is Start + 1,
and
Start1 is Start + Step,

respectively.

Sorry,
Daniel

[snipped]

Quote:
>     /* 3-arity version - incremental only */
>     for(Num,_,Num).
>     for(Start,Stop,NumOut):-
>         Start1 = Start + 1,
>         Start1 <= Stop,
>         for(Start1,Stop,NumOut).

>     /* 4-arity version - incremental only */
>     for(Num,_,Num,_).
>     for(Start,Stop,NumOut,Step):-
>         Start1 = Start + Step,
>         Start1 <= Stop,
>         for(Start1,Stop,NumOut,Step).

[snipped]

Tue, 18 Mar 2003 06:35:44 GMT
AMZI! Prolog and for/4

Quote:

> > I know how to do it recursively, but in my original posting I wrote that
> > the manual mentioned that it was in some way short for a repeat...fail
> > loop, or, in other words, for an iterative solution.

> Ok, another hint: the definition of repeat is:

> repeat.
> repeat :- repeat.

> member/2 looks very similar, and so does for/4...

I'm not sure, but I think you're missing my point. I'm looking for an
implementation of for/4 using a repeat...fail loop (though I now realize
that's not an iterative solution either), since the Amzi! Prolog User's
Guide describes the for/4 predicate as a shorthand for such a loop.
An example of a recursive solution for for/4 is this:

for(Index, Index, End, _):-
Index =< End.
for(Index, Start, End, Increment):-
Next = Start + Increment,
for(Index, Next, End, Increment).

But I still don't see how to implement it without explicit recursion,
using a repeat...fail loop.

Leon

Tue, 18 Mar 2003 03:00:00 GMT
AMZI! Prolog and for/4

Quote:

> > > I know how to do it recursively, but in my original posting I wrote that
> > > the manual mentioned that it was in some way short for a repeat...fail
> > > loop, or, in other words, for an iterative solution.

> > Ok, another hint: the definition of repeat is:

> > repeat.
> > repeat :- repeat.

> > member/2 looks very similar, and so does for/4...

> I'm not sure, but I think you're missing my point. I'm looking for an
> implementation of for/4 using a repeat...fail loop (though I now realize
> that's not an iterative solution either), since the Amzi! Prolog User's
> Guide describes the for/4 predicate as a shorthand for such a loop.
> An example of a recursive solution for for/4 is this:

> for(Index, Index, End, _):-
>  Index =< End.
> for(Index, Start, End, Increment):-
>  Next = Start + Increment,
>  for(Index, Next, End, Increment).

Oops. This is a correct implementation:

for(Index, Index, End, _).
for(Index, Start, End, Increment):-
Start < End,
Next is Start + Increment,
for(Index, Next, End, Increment).

Still, when executing

for(X, 1, 10000, 1), write(X), nl, fail.

I run out of stack space for X = 6000 something,
and when executing

repeat, write('test'), nl, fail.

I don't run out of stack space. So I think repeat is actually implemented
in an iterative way.

Leon

Tue, 18 Mar 2003 03:00:00 GMT
AMZI! Prolog and for/4

Quote:
> Oops. This is a correct implementation:
> for(Index, Index, End, _).
> for(Index, Start, End, Increment):-
>  Start < End,
>  Next is Start + Increment,
>  for(Index, Next, End, Increment).
> Still, when executing
>  for(X, 1, 10000, 1), write(X), nl, fail.
> I run out of stack space for X = 6000 something,
> and when executing
>  repeat, write('test'), nl, fail.
> I don't run out of stack space. So I think repeat is actually implemented
> in an iterative way.

Which Prolog are you using?

A decent prolog will have last-call optimization that ensures that you
would not run out of stack space for such examples. In SICStus Prolog
repeat is really implemented as

repeat.
repeat :- repeat.

and it has no problems, even for astronomic values of the third argument.
Right now it is at 2000000, memory usage is constant, as reported by `top'.

--
Gertjan van Noord Alfa-informatica, RUG,  Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl            http://www.let.rug.nl/~vannoord

Tue, 18 Mar 2003 03:00:00 GMT
AMZI! Prolog and for/4

Quote:

> > I'm not sure, but I think you're missing my point. I'm looking for an
> > implementation of for/4 using a repeat...fail loop (though I now realize
> > that's not an iterative solution either), since the Amzi! Prolog User's
> > Guide describes the for/4 predicate as a shorthand for such a loop.

I think you are taking that User guide a bit too literally here.
All they are saying is that analogous to repeat...fail which allows
you to write an infinite failure-driven loop, for/4...fail allows
you to write a finite failure-driven loop.

Quote:
> Still, when executing

>  for(X, 1, 10000, 1), write(X), nl, fail.

> I run out of stack space for X = 6000 something,

This is something that Amzi needs to fix then. Last-call and
last-alternative optimization should be standard in all Prologs.

Quote:
> and when executing

>  repeat, write('test'), nl, fail.

> I don't run out of stack space. So I think repeat is actually implemented
> in an iterative way.

Actually, on the WAM level it is possible to implement repeat
as if it were written with infinitely many clauses like

repeat.
repeat.
...
repeat.

however, that should just affect speed, not memory,
compared to the 2-clause recursive version.

--
Joachim Schimpf              /             phone: +44 20 7594 8187

London SW7 2AZ, UK         /    http://www.icparc.ic.ac.uk/eclipse

Tue, 18 Mar 2003 03:00:00 GMT

 Page 1 of 2 [ 15 post ]

Relevant Pages