tg1e+@andrew.cmu.edu (Timothy R. Gottschalk) (08/19/90)
In my earlier post, I neglected to include a very important cut in my
loop. I am the first to admit cluelessness in Prolog programming, so
perhaps someone out there can give me some help optimizing use of the
heap w/ the following Turbo Prolog loop (in repeat ... fail form):
...........................................................................
run(Event_In):- % run takes a member of a special
call_eval(Event_In, Event_Out), % domain as an argument.
Event_Out = done,!. % loop finished when symbol 'done'
% is returned.
call_eval(Event, Event).
call_eval(Event_In, Event_Done):-
exec_event(Event_In, Event_Out), % SEE BELOW FOR exec_event***
call_eval(Event_Out, Event_Done).
Notes on flow patterns:
call_eval/2 is (i,o), exec_event/2 is (i,o), run/1 is (i)
*** exec_event takes an event and ultimately returns a new event from the
old one -- this is the root of my problem; I want to reuse the same
heap space since I won't need to ever backtrack. Using retract and
assert makes the program run unacceptably slow; I guess due to the
complexity of the event data structure. Could I use ref variables
or something like that? My compiler insists that call_eval is non-
deterministic, since putting a cut in the first instance of call_eval
would be contrary to the idea of the repeat..fail. But, wouldn't this
be the source of my heap leakage problem?
If you'd like to run this program yourself, insert a storage check in
call_eval, and then write a body for exec_event like:
exec_event(Event_In, Event_Out):-
Event_Out = Event_In,!.
Tim G.ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (08/19/90)
In article <ganNChe00WB2QF5VM0@andrew.cmu.edu>, tg1e+@andrew.cmu.edu (Timothy R. Gottschalk) writes: > run(Event_In):- % run takes a member of a special > call_eval(Event_In, Event_Out), % domain as an argument. > Event_Out = done,!. % loop finished when symbol 'done' > call_eval(Event, Event). > call_eval(Event_In, Event_Done):- > exec_event(Event_In, Event_Out), % SEE BELOW FOR exec_event*** > call_eval(Event_Out, Event_Done). I have no idea what Turbo (Latin for "I whirl around, make confused") Prolog does with the heap here. To be useful on a PC, a Prolog system has to have a garbage collector for the heap, so you shouldn't have to worry. (Try LPA Prolog Professional or ALS Prolog instead.) The code as shown is unduly complicated. All you want to do is to keep on calling exec_event/2 until it returns 'done'. The following two clauses do the whole thing: run(done) :- !. run(Event) :- /* Event ~= done */ exec_event(Event, NextEvent), run(NextEvent). If exec_event/2 is determinate, this is determinate. If exec_event/2 is not determinate, this is not determinate. > I want to reuse the same heap space since I won't need to ever backtrack. It is precisely the business of the garbage collector to make this happen without you lifting a finger. If Turbo Prolog doesn't do it, work out what your time is worth, and buy a PC Prolog that _does_ do it. > putting a cut in the first instance of call_eval > would be contrary to the idea of the repeat..fail. But your program isn't *using* a repeat/fail loop. It's doing recursive calls to exec_event/2. Don't get the two coding schemes muddled up! -- The taxonomy of Pleistocene equids is in a state of confusion.
jgarland@kean.ucs.mun.ca (08/20/90)
In article <3581@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) proposes the following structure to help Tim G. with some confused code and expresses doubts as to whether Mr. G's PDC Prolog can handle it. > run(done) :- !. > run(Event) :- /* Event ~= done */ > exec_event(Event, NextEvent), > run(NextEvent). > > If exec_event/2 is determinate, this is determinate. > If exec_event/2 is not determinate, this is not determinate. > I say again, that I agree PDC (Turbo) Prolog cannot directly do some of the interesting things other Prologs do. However, Tim's question revolved around memory conservation, not metaprogramming. Nothing he has proposed in any of his inquiries remotely requires that level of sophistication. His code is awful [sorry Tim]--but then mine, at least, was too...once. I wasn't going to reply to your question as I am clueless wrt your published code. However, I do want to mention some TP memory management points. I have taken the liberty of reworking the O'Keefe code in PDC Prolog. I implied in an earlier post to you that non-determinism is important for saving stack space on recursive calls. It is, but the crucial point is whether backtracking points are generated. Note that exec_event/2 below is non-deter- ministic--i.e. *capable* of generating backtracking points. With the proper ordering of exec_event/2 clauses, however, backtracking points can be elimi- nated by tail recursion optimization. Or, more brutally, you can simply place a cut after the non-deterministic clause and before the recursive call. BTW, it is important to differentiate between heap and stack usage as this gives you important information about errors. Running out of heap (also *global* stack) space comes from declaring super-long lists (e.g. 40,000 integers on my machine) having just plain too many database facts, windows, etc., or clumsy usage of the database predicates chain_terms/5 or ref_term/4. It's rarely a problem except with runaway loops. *Stack* space is consumed by recursive calls which cannot be eliminated through tail recursion, by parameter passing, by temporary storage of subgoals, etc. It is often a problem under any situation which generates large numbers of backtracking points (recursion being an easy way to do this). So, if the O'Keefe structure is of use to you, have no fear of using it. If it isn't, remember that backtracking points are the thing to focus on...there mustn't be any before the recursive call if you want to keep them from being multiplied. */ ****************************Listing*********************************** shorttrace predicates run(symbol) exec_event(symbol,symbol) clauses run(done) :- write("EVENT HAPPENED"),nl,!. run(Event) :- /* Event ~= done */ storage, exec_event(Event, Nextevent), % !, % putting a cut here would eliminate any % problems with leftover backtracking points % below, but by ordering in the suggested way, % you eliminate the need for a cut here. run(NextEvent). exec_event(_,NextEvent) :- % This clause should fail on all calls % but the last. random(100,Done_or_not), % loop for a random while and see if we generate % any backtracking points (or consume memory). Done_or_not < 10, % Succeed randomly 1/10th of the time. Nextevent = done. exec_event(_,not_done). % This clause should succeed leaving no untried % alternatives on every iteration but the last. goal run(xxx). % anything other than an underscore, a variable, or 'done' ****************end of listing********************************************** A last note: Prolog in general, including PDC Prolog, is generally very elegant--if your programme looks inelegant, that is usually a clue you haven't quite got the algorithm--and your thinking--down quite right yet. [This is not personal, it's part my own evaluation process for my own code.] John Garland jgarland@mun Bitnet jgarland@kean.ucs.mun.ca Internet
jgarland@kean.ucs.mun.ca (08/20/90)
In article <3581@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) proposes the following structure to help Tim G. with some confused code and expresses many doubts about his Tim's compiler of choice. > run(done) :- !. > run(Event) :- /* Event ~= done */ > exec_event(Event, NextEvent), > run(NextEvent). > > If exec_event/2 is determinate, this is determinate. > If exec_event/2 is not determinate, this is not determinate. I say, again, that I agree PDC Prolog cannot directly do some of interesting things other Prologs do. However, Tim's question revolves around memory conservation, not metaprogramming. Nothing in any of his recent inquiries requires the sophistication of more advanced Prologs, and in fact, if he's having speed problems with PDC, he's unlikely to solve them employing other implementations. His code is awful [sorry Tim], but then mine, at least, was too...once. It's certainly no reflection on the compiler itself. Anyway Tim, here's something I put together today- /* I wasn't going to reply to your question as I am clueless wrt your published code. However, I do want to lay out for you some important memory management techniques in PDC Prolog. I have taken the liberty of reworking the O'Keefe code in PDC Prolog. I implied in an earlier post to you that non-determinism is important for saving stack space on recursive calls. It is, but the crucial point is whether backtracking points are generated. Note that exec_event/2 below is non-deter- ministic--i.e. *capable* of generating backtracking points. With the proper ordering of exec_event/2 clauses, however, backtracking points can be elimi- nated by tail recursion optimization. Or, more brutally, you can simply place a cut after the non-deterministic clause and before the recursive call. BTW, it is important to differentiate between heap and stack usage as this gives you important information about errors. Running out of heap (also *global* stack) space comes from declaring super-long lists (e.g. 40,000 integers on my machine) having just plain too many database facts, windows, etc., or clumsy usage of the database predicates chain_terms/5 or ref_term/4. It's rarely a problem except with runaway loops. *Stack* space is consumed by recursive calls which cannot be eliminated through tail recursion, by parameter passing, by temporary storage of subgoals, etc. It is often a problem under any situation which generates large numbers of backtracking points (recursion being an easy way to do this). Also, just generating a heap overflow error is no guarantee that the heap is the trouble, so check what's happening with the storage or storage/3 predicates. Anyway, if the O'Keefe structure is of use to you, have no fear of using it. If it isn't, remember that backtracking points are the thing to focus on...there simply mustn't be any before the recursive call if you want to keep them from being multiplied. */ ****************************start of listing************************* shorttrace predicates run(symbol) exec_event(symbol,symbol) clauses run(done) :- write("EVENT HAPPENED"),nl,!. run(Event) :- /* Event ~= done */ storage, exec_event(Event, Nextevent), % !, % putting a cut here would eliminate any % problems with leftover backtracking points % below, but by ordering in the suggested way, % you eliminate the need for a cut here. run(NextEvent). exec_event(_,NextEvent) :- % This clause should fail on all calls % but the last. random(100,Done_or_not), % loop for a random while and see if we generate % any backtracking points (or consume memory). Done_or_not < 10, % Succeed randomly 1/10th of the time. Nextevent = done. exec_event(_,not_done). % This clause should succeed leaving no untried % alternatives on every iteration but the last. goal run(xxx). % or anything other than an underscore, a variable, or 'done' ***************************end of listing*********************** A last note: Prologs in general, specifically *including* PDC Prolog, are generally very elegant--if your programme looks inelegant, that is usually a clue you haven't quite got the algorithm, and your thinking, down quite right yet. [This is not personal, it's part my own evaluation process for my own code.] John Garland jgarland@mun Bitnet jgarland@kean.ucs.mun.ca Internet
jgarland@kean.ucs.mun.ca (08/20/90)
In article <3581@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) proposes the following structure to help Tim G. with some confused code and expresses many doubts about his Tim's compiler of choice. > run(done) :- !. > run(Event) :- /* Event ~= done */ > exec_event(Event, NextEvent), > run(NextEvent). > > If exec_event/2 is determinate, this is determinate. > If exec_event/2 is not determinate, this is not determinate. I say, again, that I agree PDC Prolog cannot directly do some of interesting things other Prologs do. However, Tim's question revolves around memory conservation, not metaprogramming. Nothing in any of his recent inquiries requires the sophistication of more advanced Prologs, and in fact, if he's having speed problems with PDC, he's unlikely to solve them employing other implementations. His code is awful [sorry Tim], but then mine, at least, was too...once. It's certainly no reflection on the compiler itself. Anyway Tim, here's something I put together today- /* I wasn't going to reply to your question as I am clueless wrt your published code. However, I do want to lay out for you some important memory management techniques in PDC Prolog. I have taken the liberty of reworking the O'Keefe code in PDC Prolog. I implied in an earlier post to you that non-determinism is important for saving stack space on recursive calls. It is, but the crucial point is whether backtracking points are generated. Note that exec_event/2 below is non-deter- ministic--i.e. *capable* of generating backtracking points. With the proper ordering of exec_event/2 clauses, however, backtracking points can be elimi- nated by tail recursion optimization. Or, more brutally, you can simply place a cut after the non-deterministic clause and before the recursive call. BTW, it is important to differentiate between heap and stack usage as this gives you important information about errors. Running out of heap (also *global* stack) space comes from declaring super-long lists (e.g. 40,000 integers on my machine), having just plain too many database facts, windows, etc., or clumsy usage of the database predicates chain_terms/5 or ref_term/4. It's rarely a problem except with runaway loops. *Stack* space is consumed by recursive calls which cannot be eliminated through tail recursion, by parameter passing, by temporary storage of subgoals, etc. It is often a problem under any situation which generates large numbers of backtracking points (recursion being an easy way to do this). Also, just generating a heap overflow error is no guarantee that the heap is the trouble, so check what's happening with the storage or storage/3 predicates. Anyway, if the O'Keefe structure is of use to you, have no fear of using it. If it isn't, remember that backtracking points are the thing to focus on...there simply mustn't be any withing the scope of the recursive call if you want to keep them from being multiplied. */ ****************************start of listing************************* shorttrace predicates run(symbol) exec_event(symbol,symbol) clauses run(done) :- write("EVENT HAPPENED"),nl,!. run(Event) :- /* Event ~= done */ storage, exec_event(Event, Nextevent), % !, % putting a cut here would eliminate any % problems with leftover backtracking points % below, but by ordering in the suggested way, % you eliminate the need for a cut here. run(NextEvent). exec_event(_,NextEvent) :- % This clause should fail on all calls % but the last. random(100,Done_or_not), % loop for a random while and see if we generate % any backtracking points (or consume memory). Done_or_not < 10, % Succeed randomly 1/10th of the time, else fail Nextevent = done. exec_event(_,not_done). % This clause should succeed leaving no untried % alternatives on every iteration but the last. goal run(xxx). % or anything other than an underscore, a variable, or 'done' ***************************end of listing*********************** A last note: Prologs in general, specifically *including* PDC Prolog, are generally very elegant--if your programme looks inelegant, that is usually a clue you haven't quite got the algorithm, and your thinking, down quite right yet. And no, I can't exactly define 'elegance'. [This is not personal, it's part my own evaluation process for my own code.] John Garland jgarland@mun Bitnet jgarland@kean.ucs.mun.ca Internet
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (08/31/90)
In article <126688@kean.ucs.mun.ca>, jgarland@kean.ucs.mun.ca writes: > In article <3581@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au [I wrote] > > run(done) :- !. > > run(Event) :- /* Event ~= done */ > > exec_event(Event, NextEvent), > > run(NextEvent). > > > > If exec_event/2 is determinate, this is determinate. > > If exec_event/2 is not determinate, this is not determinate. > > > I say again, that I agree PDC (Turbo) Prolog cannot directly do some of the > interesting things other Prologs do. However, Tim's question revolved around > memory conservation, not metaprogramming. Yes, but _I_ wasn't talking about meta-programming _either_. I too was talking about memory management. I was saying that this two-clause approach is determiniate and tail recursive (provided only that exec_event/2 is determinate) so that >>>it runs in bounded stack<<<. > Nothing he has proposed in any of > his inquiries remotely requires that level of sophistication. What on earth is sophisticated about a two-clause tail-recursive loop? This is one of the cases where thinking in Pascal _does_ pay off; it is the direct transliteration of while Event <> done do Event := exec_event(Event); If this is sophisticated, then heaven help us all. > So, if the O'Keefe structure is of use to you, have no fear of using it. If > it isn't, remember that backtracking points are the thing to focus on...there > mustn't be any before the recursive call if you want to keep them from being > multiplied. */ But that is _precisely_ what the comment about wanting exec_event/2 to be determinate was _about_. -- You can lie with statistics ... but not to a statistician.
jgarland@kean.ucs.mun.ca (08/31/90)
In article <3647@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > In article <126688@kean.ucs.mun.ca>, jgarland@kean.ucs.mun.ca writes: >> In article <3581@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au > [I wrote] >> > run(done) :- !. >> > run(Event) :- /* Event ~= done */ >> > exec_event(Event, NextEvent), >> > run(NextEvent). >> > >> > If exec_event/2 is determinate, this is determinate. >> > If exec_event/2 is not determinate, this is not determinate. >> > > this two-clause > approach is determiniate and tail recursive (provided only that exec_event/2 > is determinate) so that >>>it runs in bounded stack<<<. > > [this] is _precisely_ what the comment about wanting exec_event/2 to be > determinate was _about_. I have no disagreement with this at all. My point is that if the exec_event/2 clauses are ordered such that the last clause, and only the last clause, contains the recursive call on all iterations but the last, *it does not matter* (to the PDC compiler anyway) that exec_event/2 is deterministic or nondeterministic. No additional stack space is consumed on each iteration, nor are any [additional] backtracking points generated. Question: Is this tantamount to saying exec_event/2 *is* deterministic for all practical purposes??? What am I missing? John Garland jgarland@mun Bitnet jgarland@kean.ucs.mun.ca Internet