Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!stretch.cs.mun.ca!leif!jgarland From: jgarland@kean.ucs.mun.ca Newsgroups: comp.lang.prolog Subject: Re: Prolog PROG TECH. II Message-ID: <126690@kean.ucs.mun.ca> Date: 19 Aug 90 19:29:28 GMT References: <3581@goanna.cs.rmit.oz.au> Organization: Memorial University. St.John's Nfld, Canada Lines: 98 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