loops in prolog 
Author Message
 loops in prolog

Question: how would you code the following loop in (Edingburgh)
Prolog?

loop:
   action_1;
   IF condition_1 THEN
     action_2;
     goto loop
  END IF
  action_3;

Granted this is bad code, but the idea is to perform action_1 and
action_2 within the loop. action_1 would change some data, say, and
condition_1 would check the result. If condition_1 is satisfied, then
action_2 is performed and stays in the loop, otherwise rest of the
program is continued with action_3 WITHOUT doing action_2.

The code I came up with looks something like this:

loop :-
   action_1,
   (condition_1 -> action_2,loop),
   action_3.

This works, but the recursive call eats up memory and I get out of heap
errors. Is there some other way of doing this? A fail driven loop seems
an obvious alternative, but action_1 is a proven-once predicate (ie.
fails on backtrack). So, this doesn't seem to work:

loop :- action_1,condition_1,action_2,fail.
loop :- action_3.

Thanks in advance for any suggestions.
Vince.
--------------------------------------------



.



Tue, 28 Jul 1992 06:41:15 GMT  
 loops in prolog

Quote:

> Question: how would you code the following loop in (Edingburgh) Prolog?
> loop:
>    action_1;
>    IF condition_1 THEN action_2; goto loop END IF;
>   action_3;

The answer is dead simple.
        loop :-
                action_1,
                (   condition_1 ->
                    action_2,
                    loop
                ;/* ~condition_1 */
                    action_3
                ).

Quote:
> The code I came up with looks something like this:
> loop :-
>    action_1,
>    (condition_1 -> action_2,loop),
>    action_3.
> This works, but the recursive call eats up memory and I get out of heap

I have some bad news for you.  It DOESN'T work.  What this says is
to do action_3 WHETHER OR NOT condition_1 succeeds, and that's NOT
what the original sketch said!  You begin to convince me that Dijkstra
was right when he omitted the one-armed-IF-bandit from his notation.


Tue, 28 Jul 1992 18:09:46 GMT  
 loops in prolog

Quote:
> Question: how would you code the following loop in (Edingburgh)
> Prolog?

>loop:
>   action_1;
>   IF condition_1 THEN
>     action_2;
>     goto loop
>  END IF
>  action_3;

Answer

loop :-
        action1,
        loop1.

loop1 :-
        condition1,
        !,
        action2,
        loop.

loop1 :-
        action3.

Any other homework you want done, just post it.

--
Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN

`I have read your article, Mr Johnson, and I am no wiser now than when I
started'.  -- `Possibly not, sir, but far better informed.'



Thu, 30 Jul 1992 05:49:19 GMT  
 loops in prolog
Hello,

Try

loop:-
        repeat,
        action_1,
        (not condition_1;action_2,fail),
        action_3.

You must take care of backtracking. Use a predicate
like
        once_true(X):-call(X),!.
        once_true(_).

for calling action_? .

I hope this will help you

Stefan Bachert



Sat, 15 Aug 1992 22:01:40 GMT  
 loops in prolog

Quote:

> loop:-
>    repeat,
>    action_1,
>    (not condition_1;action_2,fail),
>    action_3.

BEWARE.  A 'repeat" loop should always have its cut in the same clause.
The cut is just as much part of the loop structure as the 'repeat'.
It is *extremely* confusing for human readers if you put the cut in
some other predicate (rather like putting the 'end loop' of an Ada
loop in a different procedure).

A tip:  if you have some rather scrambled control structure it may
be useful to first try to write down a regular expression that
describes the possible sequences of tests and actions, and use the
regular expression as the basis of your code.

In this example, I am guessing that the intention is
        action_1 (condition_1 action_2 action_1)* ~condition_1 action_3
which naturally leads to the structure

    p :-
        action_1,
        p_loop.

    p_loop :-
        (   condition_1 -> action_2, action_1, p_loop
        ;/* ~condition_1*/ action_3
        ).

All done by kindness.



Sun, 16 Aug 1992 17:36:30 GMT  
 loops in prolog
Hello,

you are right. A cut before action_3 will clarify the situation.
I am not sure that you get me right with the idea of
once_true. So I repeat it here

        once_true(X):-call(X),!.        % predicate X is determinated
        once_true(_).                   % and always true

        loop:-
                repeat,
                once_true(action_1),
                (not condition;once_true(action_2),fail),!,
                once_true(action_3).

You proposal will still eat up the stack. I think the basenote
author has to judge what proposal fit for his problem.

Stefan Bachert

PS: I don't like ->/2 because of its dubious definition.



Mon, 17 Aug 1992 19:19:31 GMT  
 loops in prolog

Quote:

> I am not sure that you get me right with the idea of
> once_true. So I repeat it here
>    once_true(X):-call(X),!.        % predicate X is determinated
>    once_true(_).                   % and always true

I am *sick* of seeing people reinvent once/1 and giving it new names.
It is traditionally a library predicate in Edinburgh Prologs.

I've even *more* sick of people thinking it is a good idea.
If X is supposed to be determinate, then *WRITE* X so that it *IS*
determinate, don't patch it up in the calls.  When I see a program
using once/1 I am willing to bet that it is badly written in other
ways too.

Quote:
>    loop:-
>            repeat,
>            once_true(action_1),
>            (not condition  ;  once_true(action_2),fail),
                !,
>            once_true(action_3).

The actions should be written so that they are ALREADY determinate,
if that is truly what is intended.  The original author really did
not make it clear.  

Quote:
> Your proposal will still eat up the stack.

Not so.  Stack space is reclaimed on failure or on determinate exit,
and tail calls don't take stack space in a modern Prolog.  Recall
that the recursive form of the loop was
        p :- action_1, p_loop.
        p_loop :- ( condition -> action_2, action_1, p_loop ; action_3 ).
If action_1 and action_2 are determinate, then this loop does *NOT*
"eat up the stack" in a decent Prolog system.  (Note that in the 'repeat'
form of the loop action_1 had better not fail, otherwise there's a {*filter*}
liitle infinite loop there.  The recursive version has no such problem.)

Quote:
> PS: I don't like ->/2 because of its dubious definition.

*WHAT* dubious definition?  The if->then;else construct was defined
quite clearly in the DEC-10 Prolog manual, as far back as 1979:

        ( P -> Q ; R ) is like call(( P, !, Q ; R )) except that
        it is transparent to cuts in Q and R

        ( P -> Q ) is like call(( P, !, Q )) except that
        it is transparent to cuts in Q

How is this any more dubious than once/1?



Tue, 18 Aug 1992 12:24:46 GMT  
 loops in prolog

Quote:
>>        once_true(X):-call(X),!.        % predicate X is determinated
>>        once_true(_).                   % and always true
>I am *sick* of seeing people reinvent once/1 and giving it new names.
>It is traditionally a library predicate in Edinburgh Prologs.

once/1 is defined as

        once(X):-call(X),!.

and that for it can be FAILED.

Quote:
>I've even *more* sick of people thinking it is a good idea.
>If X is supposed to be determinate, then *WRITE* X so that it *IS*
>determinate, don't patch it up in the calls.  When I see a program
>using once/1 I am willing to bet that it is badly written in other
>ways too.

In your last comment you talked about clearness of programs.
Using once or once_true will clarify the situation. Your proposal
will do it not!

Quote:
>> Your proposal will still eat up the stack.
>Not so.  Stack space is reclaimed on failure or on determinate exit,
>and tail calls don't take stack space in a modern Prolog.  Recall
>that the recursive form of the loop was
>    p :- action_1, p_loop.
>    p_loop :- ( condition -> action_2, action_1, p_loop ; action_3 ).
>If action_1 and action_2 are determinate, then this loop does *NOT*
>"eat up the stack" in a decent Prolog system.

If so your proprosal will run just on your special implemention of prolog.
It takes a lot knowledge to detect that p_loop is determinated. And it is not
obvious to the programmers.
My proposal will run in any prolog.

Quote:
>(Note that in the 'repeat'
>form of the loop action_1 had better not fail, otherwise there's a {*filter*}
>liitle infinite loop there.  The recursive version has no such problem.)

That's why I introduce once_true/1

Quote:
>> PS: I don't like ->/2 because of its dubious definition.
>*WHAT* dubious definition?  The if->then;else construct was defined
>quite clearly in the DEC-10 Prolog manual, as far back as 1979:
>    ( P -> Q ; R ) is like call(( P, !, Q ; R )) except that
>    it is transparent to cuts in Q and R
>    ( P -> Q ) is like call(( P, !, Q )) except that
>    it is transparent to cuts in Q

Exactly that. Try to implement -> /2 in Prolog. (? exceptions)
->/2 is more a precompiler directive than a prolog predicate.

Stefan



Fri, 21 Aug 1992 19:16:21 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. How Double Loop in Prolog?

2. Please Help: Coding a for loop in prolog

3. Please Help: Coding for loop in prolog

4. Finding Closed Loops in Prolog

5. Prolog in a recursive loop

6. Looping constructs in Prolog...???

7. break one loop and skip one iteration of outer loop

8. 2 files: a loop within a loop??

9. Problem with loop inside other loop

10. Impelement for loop and do while loop

11. using while loops within while loops?

12. Fast loop inside a slow loop?

 

 
Powered by phpBB® Forum Software