Page 1 of 1

how to avoid increasing the stack for facts matching that fails

Posted: 29 Dec 2017 7:11
by mdosnov2016
hello, I have the following clause:

Code: Select all

    add_local_conditionally(Module_name, In_local_list, In_local_entry, Out_list, Last_entry) :-         local_object(local_OBJECT(Module_name, In_local_entry, _, Object_name, _, _, _, _, _)),         Next_local_entry = In_local_entry + 1,         hierarchy_PART(1, Top_package_module, 0, _, _, _, _),         !,         local_object(local_OBJECT(Top_package_module, _, _, Object_name, _, _, _, _, _)),         !,         % it exists also in the package         Top_package_module <> Module_name,         % and the current module is not the Top package         Next_local_list = In_local_list,         % in this case the list is not updated with this local         get_and_append_local(Module_name, Next_local_list, Next_local_entry, Out_list, Last_entry).
according to recent instructions by VP colleagues I added the cut (!) after non-deterministic facts
matching commands to avoid increasing the stack.
However, I have now a situation that the following call:

Code: Select all

        local_object(local_OBJECT(Top_package_module, _, _, Object_name, _, _, _, _, _)),
fails and because of the succeeding cut, predicate
add_local_conditionally
fails as well, and so on and my top-level procedure fails and so my program.
This is a situation that I didn't have before in my project.
How can I deal with this, still maintaining the small stack feature?

thank you and Happy Holidays,
Michael

Re: how to avoid increasing the stack for facts matching that fails

Posted: 29 Dec 2017 23:58
by Thomas Linder Puls
A cut that ruins the logic of the program is clearly wrong. Such a cut should obviously not be there.

You do not place cuts to avoid stack growth, you place cuts to remove unwanted/unnecessary backtracking. Leaving open backtracking possibilities also have a great chance of making the stack grow (unnecessarily). But cuts are for backtracking not for the stack.

There are many "cowboy tricks" about cuts, but in the end you really have to understand it. Why place a cut here? Why not place a cut here? Where exactly to place the cut?

Please read Programming Pragmatics#Cut.

Place a cut everywhere where it removes unnecessary/unwanted backtracking, but do not place more cuts than that.

Until you master it, I will give you one "cowboy trick": It is almost always wrong to more than one cut in a clause.

Re: how to avoid increasing the stack for facts matching that fails

Posted: 30 Dec 2017 0:05
by Harrison Pratt
fails and because of the succeeding cut, predicate
add_local_conditionally
fails as well, and so on and my top-level procedure fails and so my program.
This is a situation that I didn't have before in my project.
Well, add_local_conditionally is not failing because of the cut.

If you have more than one cut ("!") in a clause, you don't fully understand the logical flow in that clause. One cut will suffice.

Is add_local_conditionally declared as determ or procedure (it is implicit procedure if not declared otherwise) or some other behavior? You write as though you expect it to be procedure but you shouldn't require cuts in a single-clause procedure.

What do you expect to happen if the local_object predicate call fails? You need to deal with that somehow, either by making local_object a procedure or by figuring out how you want to handle failure of local_object when it is called by another predicate.

I have the feeling that you don't clearly understand procedure, determ, nondeterm, etc.

Re: how to avoid increasing the stack for facts matching that fails

Posted: 2 Jan 2018 13:48
by Paul Cerkez
I am not an expert on the latest version of VIP (still need to upgrade from 7.5) but looking at your code block the logic looks iffy.

(Assuming hierarchy_PART(...) and local_object(...) are fact bases)

To see it, try re-ordering the clauses;

Code: Select all

    add_local_conditionally(Module_name, In_local_list, In_local_entry, Out_list, Last_entry) :-         hierarchy_PART(1, Top_package_module, 0, _, _, _, _), % PSC - will always succeed assuming a record exists         local_object(local_OBJECT(Module_name, In_local_entry, _, Object_name, _, _, _, _, _)), % PSC - will always succeed assuming a record exists for that Module_name AND In_local_entry. The AND here is important.         local_object(local_OBJECT(Top_package_module, _, _, Object_name, _, _, _, _, _)),  % PSC - will only succeed if there is a record with Top_package_module AND Object_name.  The AND here is important.           % it exists also in the package         Top_package_module <> Module_name,  % PSC - this is your conditional check to start backtracking.  If this succeeds, move on to the assertion.         % and the current module is not the Top package         !, % PSC - moved to here         %PSC- the rest of this is the action to take once the above condition has been met.         % Next_local_list = In_local_list,         % in this case the list is not updated with this local         % PSC - so why are you creating a new variable, just use the existing one?         Next_local_entry = In_local_entry + 1,         % not needed until you are ready to assert the new fact.         get_and_append_local(Module_name, In_local_list, Next_local_entry, Out_list, Last_entry).
Some things to think about:
What happens when there is no entry for hierarchy_PART(...)? If you do not have a 'graceful fail' clause to account for that, the program will fail all the up until there is one (a 'graceful fail' ) or it crashes.

What happens when there is no Module_name entry in local_Object? That would be your first failure. Do you have a graceful fail clause to catch that?

What happens when the Module _name submitted actually is the Top_package_module. Do you have a graceful fail clause to catch that?

What happens when nothing meets your conditions? Do you have a graceful fail clause to catch that?

In this search, is Object_Name really needed? You already know the Top_Package_module and the Module_name.

Can a Module have more than one Object_name or can Object_name be associated with more than one module?
  • If not, is Object_name really needed in this search?
    If Object_name and Module_Name are 1:1, then comment out the local_object(Top_module_name ...) clause.
    If a module can have more than one object associated with it then do not comment it out.
    Also, if an Object_name can be associated with more than one module, do not comment it out.

Re: how to avoid increasing the stack for facts matching that fails

Posted: 2 Jan 2018 18:31
by mdosnov2016
Thank all for feedback.
Dear Thomas, can please list to me all the cases that the stack increases (I know about the recursion already),
so that I have a clear picture, since I couldn't find this in the documentation.
thanks and Happy New Year,
Michael

Re: how to avoid increasing the stack for facts matching that fails

Posted: 2 Jan 2018 22:07
by Thomas Linder Puls
I find it rather strange to list complex descriptions of stack growth and schrinkage. I think it is much more relevant to discuss good and bad programming practice.
  • Calls consume stack
  • Returning from calls release stack, unless there is an active backtrack point in the predicate
  • Last calls (often/sometimes) release stack

Re: how to avoid increasing the stack for facts matching that fails

Posted: 3 Jan 2018 9:30
by mdosnov2016
OK so you confirmed what I already know about the stack, thank you.
Actually, the strategy that I had followed in this project is that the algorithm goes through
a fact sequence, beginning with the #1, and at every step a new predicate is called that
process the next boung of facts and so on. This predicate in turn calls other predicates,
which in turn may call the original predicate.

The problem is that I need to have a lot of predicate calls in order to process the sequence.
I don't know any other policy to implement my optimization algorithm in Prolog.
The problem now, is that because I cannot increase the stack limit, I am limited
to only small applications that have certainly only a few predicate calls.

Is there another way to do this without increasing the stack in general?
Michael

Re: how to avoid increasing the stack for facts matching that fails

Posted: 3 Jan 2018 10:09
by Thomas Linder Puls
Well your explanation seem to contain at least one crucial issue: it both iterates the facts and calls itself recursively.

It may be correct, but it certainly sounds bad/dangerous/wrong. It is quite likely that your algorithm has a very high complexity (both in space and time), perhaps exponentially or even like the faculty function. Such a growth simply cannot be compensated by increasing stack sizes. And even if you could increase the stack size exponentially then I doubt that you are willing to increase the time consumption exponentially.
Is there another way to do this without increasing the stack in general?
No. Each problem will have to have its own efficient algorithm developed specifically for that problem. And there exist many problems for which efficient algorithms has not/cannot been found.

Re: how to avoid increasing the stack for facts matching that fails

Posted: 3 Jan 2018 10:15
by mdosnov2016
Thank you for your answer.
Does the new VP support loops? what about global variables? (I recall seeing in some example
a foreach command...).
I could then store the sequence number of the fact in the loop index or the global variable,
instead of iterate around predicate calls. Of course this will require that I re-implement the
scheduler from scratch.
Michael