Explanation required: infinite recursion, choice points and memory growth.

[Sean Charles]

Hello,

Can somebody provide a clear explanation so I can hope to understand how choice points and recursion could cause a program to fail please?

I'm considering porting my gprolog SDL2 binding to SWI but before I do I want to know if it is viable.

In an SDL2 event loop, you continue until an SDL_QUIT message or user generated abort is detected, typicall I ended up with code that looked like this:

SDL_Init(...),

Init_State(State),

ui_loop(State),

SDL_Quit.

ui_loop(State) :-

   %% do stuff to State

   ui_events(State, NewState),

   ui_render(State),

   ui_loop(NewState).

ui_loop(_) :-

   %% perform shutdown stuff

   .

My reasoning as an intermediate/beginner level prolog hacker is that each iteration of the loop may or may not change State, e.g. a user presses a key that affects the model etc. If the ui_events() `fail`s then that means to stop so the catch all ui_loop predicate is used to perform cleanup and then it returns and SDL_Quit is called.

My concern / worry / question relates to the style, as in *how* do I write code so that I don't leabe choice points on the stack and that the stack does not continue to grow eventually failing and halting my application code?

To be honest, I am not fully sure I 100% understand choice points and *exactly* when and where they occur. I have used findall/3 etc. with the http and xpath modules and that was a struggle until pennies dropped. I have actual paperbacks of Clocksin & Mellish, Shapiro and Covington/Shute books, all of which are both (a) fantastic, (b) bewildering and (c) old! as in not in line with SWI at times.

I am gradually getting to like Prolog more and more and more and I really want to get into its head more. Sometimes I can't understand how I wrote a Redis connection that is now bundled with Logtalk, thanks for the compliment Paulo!

Cheers,

Sean Charles.

[Jan Wielemaker]

On 11/18/2017 09:28 AM, Sean Charles wrote:
> Hello,
>
> Can somebody provide a clear explanation so I can hope to understand how
> choice points and recursion could cause a program to fail please?
>
> I'm considering porting my gprolog SDL2 binding to SWI but before I do I
> want to know if it is viable.
>
> In an SDL2 event loop, you continue until an SDL_QUIT message or user
> generated abort is detected, typicall I ended up with code that looked
> like this:
>
> SDL_Init(...),
> Init_State(State),
> ui_loop(State),
> SDL_Quit.
>
> ui_loop(State) :-
>    %% do stuff to State
>    ui_events(State, NewState),
>    ui_render(State),
>    ui_loop(NewState).
>
> ui_loop(_) :-
>    %% perform shutdown stuff
>    .

A recusive last call is subject to `last call optimization' iff no
choice point is still open that has been created since the goal was
started. This is unavoidable as if there is a choice point we must
be able to restore its context, which includes the current goal and
thus we cannot destroy it.

This means no choice point may be alive as we get at the ui_loop/1
recursive call. In your case you have two clauses for ui_loop/1
both with a variable first argument, so both match and a choice point
is created as we enter the first clause. You must kill this before
the recursive call. I'd write this as

ui_loop(State) :-
catch(once(do_stuff(State)), E,
print_message(error, E)),
( ui_events(State, NewState)
-> ui_render(State),
ui_loop(NewState)
; shutdown(NewState)
).

I assume the do_stuff is not supposed to backtrack either. The catch
and once enforce that the choice point is killed and a possible
exception is printed rather than aborting the program.

This loop runs in finite state, provided ui_render/1 is deterministic
and State remains finite in size. It will run stack-GC from time to
time. If State gets really big this may result in poor realtime
behaviour. If we assume a couple of millisec lack acceptable I'd
guess your state may grow into the megabytes, but this needs
experimenting. Stack-GC time is linear in the current
stack size and size after GC, with a much smaller factor for data
that will be reclaimed than for the data that needs to be kept.

Cheers --- Jan

P.s. Note that you can use interactor/0 to start a second console
before you start the UI loop, so you can update the program,
set spy-points for the debugger, look around in the DB, etc).

>
> My reasoning as an intermediate/beginner level prolog hacker is that
> each iteration of the loop may or may not change State, e.g. a user
> presses a key that affects the model etc. If the ui_events() `fail`s
> then that means to stop so the catch all ui_loop predicate is used to
> perform cleanup and then it returns and SDL_Quit is called.
>
> My concern / worry / question relates to the style, as in *how* do I
> write code so that I don't leabe choice points on the stack and that the
> stack does not continue to grow eventually failing and halting my
> application code?
>
> To be honest, I am not fully sure I 100% understand choice points and
> *exactly* when and where they occur. I have used findall/3 etc. with the
> http and xpath modules and that was a struggle until pennies dropped. I
> have actual paperbacks of Clocksin & Mellish, Shapiro and
> Covington/Shute books, all of which are both (a) fantastic, (b)
> bewildering and (c) old! as in not in line with SWI at times.
>
> I am gradually getting to like Prolog more and more and more and I
> really want to get into its head more. Sometimes I can't understand how
> I wrote a Redis connection that is now bundled with Logtalk, thanks for
> the compliment Paulo!
>
> Cheers,
> Sean Charles.
>
>

> --
> You received this message because you are subscribed to the Google
> Groups "SWI-Prolog" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to swi-prolog+...@googlegroups.com
> <mailto:swi-prolog+...@googlegroups.com>.
> Visit this group at https://groups.google.com/group/swi-prolog.
> For more options, visit https://groups.google.com/d/optout.

[emacstheviking]

Jan,

Great reply! Totally laden down with details that my small brain will avidly digest until I "get it".

Your assumption about do_stuff not backtracking is correct. Also, I do not envisage the state record to be much more than  a few tens of kilobytes as  intended it to mainly manage the running state. I was contemplating using global variables (I know, I know...) to maybe hold other data like texture handles, sounds, font data etc. Who knows, that's half the fun of exploratory coding isn't it! :)

I am particularly excited about the interactor/0... I didn't even know that existed, that'll be fun!

Many thanks for the detailed reply, I know it takes time and time is precious.

Sean.

To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com <mailto:swi-prolog+unsubscribe@googlegroups.com>.