vincel@fs0.ee.ubc.ca (vincent li) (02/09/90)
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.
--------------------------------------------
vincel@ee.ubc.ca
vinceli@triumfcl.bitnet
vincent@graham.uucp
.ok@goanna.oz.au (Richard O'keefe) (02/09/90)
In article <1032@fs1.ee.ubc.ca>, vincel@fs0.ee.ubc.ca (vincent li) writes: > 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 ). > 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.
ken@aiai.ed.ac.uk (Ken Johnson) (02/11/90)
> 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 E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 212 `I have read your article, Mr Johnson, and I am no wiser now than when I started'. -- `Possibly not, sir, but far better informed.'
stefan@hpbbi4.HP.COM (#Stefan Bachert) (02/27/90)
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
ok@goanna.oz.au (Richard O'keefe) (02/28/90)
In article <470002@hpbbi4.HP.COM>, stefan@hpbbi4.HP.COM (#Stefan Bachert) writes: > 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.
stefan@hpbbi4.HP.COM (#Stefan Bachert) (03/01/90)
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.
ok@goanna.oz.au (Richard O'keefe) (03/02/90)
In article <470003@hpbbi4.HP.COM>, stefan@hpbbi4.HP.COM (#Stefan Bachert) writes: > 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. > 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. > 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 nasty liitle infinite loop there. The recursive version has no such problem.) > 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?
stefan@hpbbi4.HP.COM (#Stefan Bachert) (03/05/90)
>> 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. >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! >> 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. >(Note that in the 'repeat' >form of the loop action_1 had better not fail, otherwise there's a nasty >liitle infinite loop there. The recursive version has no such problem.) That's why I introduce once_true/1 >> 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