How Can I simulate a while loop in Prolog with unchangeable conditions?

Question

So basically I am trying to simulate some C code in Prolog.

It is easy to simulate while loop in Prolog Here is the case:

C code:

int a = 1;

while(N)
{
  N--;
  a++; 
}

Prolog code:

prolog_while(0) : !
prolog_while(N, A) :
   N1 is N -1,
   A1 is A + 1,
prolog_while(N1, A1).

One problem is how to simulate a while loop in Prolog with unchangeable conditions?

Here is the case:

int n = 1;
int a = 1;

while(1)
{
   if (N==0)
     goto while_end;
   else
    {
        N--; A++;
    }       
}

Or

while(1)
{
   if (N==0)
     break;
   else
    {
        N--; A++;
    }       
}

I know it is kinda of weird but basically these kind of C code is automatically generated by a source code analysis tool, so I have to deal with it...

Then basically how can I simulate in Prolog? Is it doable?

Could anyone give me some help?

===================update============

I tried to write some Prolog code in this way, but basically I still don't know how to handle test clause.

main :- loop_entry(2, 1), write(N), nl, write(A), nl.

do(A, N, A1, N1) :- A1 is (A + 1), N1 is (N - 1).
test(N) :- ...                 <----- # How to write this part?
loop_entry(N, A) :-
    test(N),
    do(A, N, A1, N1),
    loop_entry(N1,A1).

How are you expecting `main/1` to work? The variables `N` and `A` aren't instantiated anywhere, so `write/1` will only end up writing the name of the anonymous variable--something like `_G978`. More importantly the cut operator `!` does not mean `false`, and doesn't function like a "break" statement, so `N = 0 -> !` won't work to induce failure of `test/1`. — Shon, Apr 05 '14 at 22:00

Daniel Lyons · Accepted Answer · 2014-04-06T06:10:27.847

10

The most obvious way to do an infinite loop in Prolog is with repeat/0, and it looks like this:

while(1)
    do_something();

becomes

repeat,
do_something.

The real problem then becomes that there's no obvious analog to goto or break in Prolog. So I would be inclined to look for a pattern like this:

while(1) {
  if (test)
    break;
  do_something();
}

and convert it to Prolog like this:

loop_entry :-
  test,
  do_something,
  loop_entry.

You will of course need to add your local variables as parameters to loop_entry/0 and implement test, but this way when test fails the loop will end naturally.

Following your example with N and A leads to this kind of thing:

loop_entry(N, A) :-
  N > 0,
  succ(N0, N),
  succ(A, A1),
  loop_entry(N0, A1).

The "test" in this case is simply N > 0. If it isn't true, the predicate will simply fail and you can go on with life the Prolog way.

Edit #2. If you want the results (N and A) then add additional parameters for the values you want to return and add one more clause:

loop_entry(N, A, ResultN, ResultA) :-
  N > 0, !, 
  succ(N0, N),
  succ(A, A1),
  loop_entry(N0, A1, ResultN, ResultA).
loop_entry(N, A, N, A).

You can either add a cut after the condition or put the inverse condition in this new clause.

edited Apr 06 '14 at 06:10

answered Apr 05 '14 at 19:46

Daniel Lyons

22,421
2
50
77

1

Hi Daniel, thank you for your answer, I tried to write a sample prolog code follow your answer, but I still don't know how to handle **test** clause... – lllllllllllll Apr 05 '14 at 20:25
1

Hi Daniel, Thank you for your reply, but basically how can I get the results(I mean final A and N), because when N = 0, N >0 will fail and all the previous recursive call of loop_entry will all fail and then prolog program will just fail.... – lllllllllllll Apr 06 '14 at 05:32
I am sorry but I am actually not very familiar with Prolog, forgive me if I asked a stupid question... – lllllllllllll Apr 06 '14 at 05:33
@computereasy I've edited the answer again. :) Keep the faith, you're going to get there. – Daniel Lyons Apr 06 '14 at 06:10
Do your self-referring `loop_entry` predicates create a call stack? – Lori Jul 19 '18 at 12:42
1

@Lori I don't know. I don't think so, because that's a pretty obvious candidate for tail call elimination, and I think the major implementations all do tail call elimination. But I'm not 100% sure. – Daniel Lyons Jul 19 '18 at 14:22

jschimpf · Answer 2 · 2014-04-06T12:48:44.967

Not very different from your prolog_while predicate:

prolog_while(N, A) :-
    ( N==0 ->
         true
    ;
         N1 is N -1,
         A1 is A + 1,
         prolog_while(N1, A1)
    ).

But most likely you want the final value of A be available to the caller of this predicate, so you have to return it via an additional argument:

prolog_while(N, A, AFinal) :-
    ( N==0 ->
         AFinal = A
    ;
         N1 is N -1,
         A1 is A + 1,
         prolog_while(N1, A1, AFinal)
    ).

Paulo Moura · Answer 3 · 2016-06-08T10:00:30.183

2

From the Logtalk standard library:

:- meta_predicate(whiledo(0, 0)).
whiledo(Condition, Action) :-
    (   call(Condition) ->
        \+ \+ call(Action),
        whiledo(Condition, Action)
    ;   true
    ).

For other traditional loop constructs see: https://github.com/LogtalkDotOrg/logtalk3/blob/master/library/loopp.lgt https://github.com/LogtalkDotOrg/logtalk3/blob/master/library/loop.lgt

edited Jun 08 '16 at 10:00

answered Apr 05 '14 at 20:47

Paulo Moura

18,373
3
23
33

`Z = 1, whiledo(Z < 4,Z=Z+1)` always seems to fail. Is there any documentation that explains how to use this predicate? – Anderson Green Jun 08 '16 at 04:43
1

@AndersonGreen Not that the goal `Z=Z+1` (or `Z is Z+1`, likely what you wanted to write) is always false. Thus, the definition above is not usable in this case. But see the other "loop" meta-predicates in the links in my answer. E.g. `loop::forto(Z, 1, 4, write(Z))` will write `1234`. – Paulo Moura Jun 08 '16 at 10:22

score 1 · Answer 4 · answered Nov 11 '18 at 06:47

In order to implement while-loops in Prolog, I wrote a small interpreter for an imperative language.

Using this interpreter, a while-loop can be written like this:

:- initialization(main).
:- set_prolog_flag('double_quotes','chars').

main :-
    imperative_statements((
        A=1,
        N=0,
        while(A<50,(
            A=A+2,
            N=N-1
        ))
        D = increment_var(1)
    )),
    writeln(A),
    writeln(N),
    writeln(D).

increment_var(A,B) :-
    imperative_statements((
        B=A,
        while(B<50,(
            B=B*2
        ))
    )).

print(A,true) :-
    writeln(A).

imperative_statements(A) :-
    term_variables(A,Names),
    length(Names,L),
    length(Input,L),
    length(Output,L),
    set_var(A,Names,Input,Output),
    Names=Output.

set_var(A,Names,Input) :-
    length(Input,L),
    length(Output,L),
    set_var(A,Names,Input,Output),
    Names=Output.

set_var((A,B),Var_names,Input,Output) :-
        set_var(A,Var_names,Input,Output1),
        set_var(B,Var_names,Output1,Output).

set_var(Name=Value,Var_names,Input,Output) :-
    get_var(Value,[Var_names,Input],Value1),
    set_var_(Name=Value1,Var_names,Input,Output).

set_var_(_,[],[],[]).
set_var_(Name=Value1,[Name1|Name2],[Var1|Var2],[Output1|Output2]) :-
    (Name==Name1,Output1=Value1;
    Name \== Name1,Output1=Var1),
    set_var_(Name=Value1,Name2,Var2,Output2).

set_var(while(A,B),Names,Vars,Result) :-
    get_var(A,[Names,Vars],A1),
    (((A1==true)->(set_var(B,Names,Vars,Result1),set_var(while(A,B),Names,Result1,Result)));
    A1==false,Vars=Result).

get_var(Name,[[Name1],[Var1]],Output) :-
    var(Name),Name==Name1,
    Output=Var1.
get_var(Name,[[Name1|Name2],[Var1|Var2]],Output) :-
    var(Name),(Name==Name1,get_var(Name,[[Name1],[Var1]],Output);
    Name \== Name1,get_var(Name,[Name2,Var2],Output)).

get_var([],_,[]).
get_var([Name1|Name2],Vars,[Name3|Name4]) :-
    get_var(Name1,Vars,Name3),
    get_var(Name2,Vars,Name4).

get_var(Name,_,Name) :-
    number(Name);atom(Name).
get_var(A+B,Vars,Output) :-
    get_var(A,Vars,A1),
    get_var(B,Vars,B1),
    Output is A1+B1.
get_var(A-B,Vars,Output) :-
    get_var(A,Vars,A1),
    get_var(B,Vars,B1),
    Output is A1-B1.
get_var(A*B,Vars,Output) :-
    get_var(A,Vars,A1),
    get_var(B,Vars,B1),
    Output is A1*B1.
get_var(A/B,Vars,Output) :-
    get_var(A,Vars,A1),
    get_var(B,Vars,B1),
    Output is A1/B1.
get_var(A**B,Vars,Output) :-
    get_var(A,Vars,A1),
    get_var(B,Vars,B1),
    Output is A1**B1.

get_var((A,B),Vars,Result) :-
    get_var([A,B],Vars,[A1,B1]),
    (A1,B1,Result=true;([A1,B1]=[true,false];[A1,B1]=[false,true]),Result=false).

get_var((A;B),Vars,Result) :-
    (get_var(A,Vars,A1),call(A1);
    get_var(B,Vars,B1),call(B1)) -> (Result = true);
    (get_var(A,Vars,A1),A1=false,Result=false).

get_var(A<B,Vars,Result) :-
    get_var(B>A,Vars,Result).
get_var(A>B,Vars,Result) :-
    %comparison of variables
    get_var([A,B],Vars,[A1,B1]),
    (A1>B1,Result=true;A1<B1,Result=false).

get_var(A==B,Vars,Result) :-
    %comparison of variables
    get_var([A,B],Vars,[A1,B1]),
    (A1==B1,Result=true;A1\=B1,Result=false).

get_var(Input,Vars,Output1) :-
    (\+number(Input)),
    Input =.. [Name|Params],
    \+member(Name,['=',==,'->',not,'[|]',',',';',+,-,*,/,**,^,writeln]),
    length(Params,Params_length),
    Params_length > 0,
    get_var(Params,Vars,Params1),
    append([Name|Params1],[Output1],Input0),
    Input1 =.. Input0,
    call(Input1).

Thank you Anderson. This makes a lot of sense to me. – lllllllllllll Nov 12 '18 at 09:25 — lllllllllllll, Nov 12 '18 at 09:25

How Can I simulate a while loop in Prolog with unchangeable conditions?

4 Answers4

Linked