Interpreter loop - best approach in Prolog? - PROLOG

On Oct 8, 2:37 pm, sbaker8...@aol.com wrote:
> A while back I developed a custom interpreted programming language,
> written in another language (not Prolog). I would like to write it in
> Prolog.
>
> The stack is the "global state" of the program that must be maintained
> as each line of code is executed. There will be an "interpreter loop"
> that gets a line of input, and does something to the stack (pushes
> something, pops something, etc). I see two basic approaches: 1)
> either maintain the stack as a "global variable" using assert/retract,
> or 2) pass the old stack into various predicates to obtain the new
> stack.
>
> I don't mind doing 2. My question is how to do this (if desirable, or
> recommended) without creating issues for the Prolog execution stack
> (not to be confused with the stack in the language I am
> implementing). In other words, how do I run the loop (getting input,
> processing it) without stacking up stack frames or activation records
> or whatever you want to call them through recursion?
>
> In fact, I suppose this could still be an issue even with assert/
> retract. Either way you have an essentially endless loop reading and
> processing input. How do Prologgers typically deal with these
> issues? Through tail-recursion? Or perhaps some special predicate
> that does looping without recursion?
>
> Thanks.

I'm not sure if I'm telling you something you already
know and have disregarded, but the typical way of
creating an endless loop in Prolog is through the
repeat/fail combination:

main_loop :-
repeat,
doSomethingUseful,
fail.

While fail is invariably a built-in predicate of Prolog,
you might have to define repeat for yourself. It acts
as if defined by:

repeat.
repeat :- repeat.

Given tail recursion/last call optimization, this will
not incur a stack overflow penalty.

regards, chip

On Mon, 08 Oct 2007 12:37:36 -0700, sbaker8688 wrote:

> I see two basic approaches: 1)
> either maintain the stack as a "global variable" using assert/retract,
> or 2) pass the old stack into various predicates to obtain the new
> stack.
>
> I don't mind doing 2. My question is how to do this (if desirable, or
> recommended) without creating issues for the Prolog execution stack
> (not to be confused with the stack in the language I am
> implementing). In other words, how do I run the loop (getting input,
> processing it) without stacking up stack frames or activation records
> or whatever you want to call them through recursion?

Determinism and tail-recursion.


> In fact, I suppose this could still be an issue even with assert/
> retract.

Indeed: without determinism, any assert/retract approach is bound to
cause brain damage during debugging (and stack overflows).

> Either way you have an essentially endless loop reading and
> processing input. How do Prologgers typically deal with these
> issues? Through tail-recursion?

Yes. Basically:

loop(State) :-
read_input(I),
process(I,State,NewState),
loop(NewState).


will do fine, if process/1 is determinstic (leaves behind no choicepoints).
If in doubt about that (this) determinism (is recognized by your Prolog
system), put a once() around it.

A failure driven loop will also help you out often, but, you will start
relying on assert/retract and find yourself in trouble eventually. Stick
with determinism+tail-recursion and your programs will come out better,
and often also more efficient.

Cheers

Bart Demoen

> I'm not sure if I'm telling you something you already
> know and have disregarded, but the typical way of
> creating an endless loop in Prolog is through the
> repeat/fail combination:

I knew about repeat, but didn't know if it would eventually blow the
stack or not if it was used in an endless loop. Now I know.

Very helpful - thanks.

Answers everything - thanks.


> loop(State) :-
> read_input(I),
> process(I,State,NewState),
> loop(NewState).
>
> will do fine, if process/1 is determinstic (leaves behind no choicepoints).
> If in doubt about that (this) determinism (is recognized by your Prolog
> system), put a once() around it.