tg1e+@andrew.cmu.edu (Timothy R. Gottschalk) (08/13/90)
I took a course that introduced Prolog syntax, but never touched prog.
techniques. Thus, I am feeling my way through. I am writing code similiar
to the following structure (in Turbo Prolog V2.0):
loop(In):-
check_mouse,
do_eval(In, Out),
loop(Out).
loop(_):-
do_exit.
The compiler recognizes that it is tail-recursive, but still allocates memory
off the heap during each iteration. As the loop should only be run when
the mouse button is pressed, the check_mouse succeeds when the button is
pressed, but fails otherwise. Commenting out the check_mouse or do_eval
call does not necessarily stop the heap allocation, although commenting
out both certainly does (of course). The easiest solution would be to
make a predicate fail somewhere, but, then, how would I be able to get a
return value? (Using reference vars or internal dbases seems to make the
program run unacceptably slow).
Tim G.fore057@canterbury.ac.nz (08/13/90)
In article <kalQPim00WB242VkMS@andrew.cmu.edu>, tg1e+@andrew.cmu.edu (Timothy R. Gottschalk) writes: > I took a course that introduced Prolog syntax, but never touched prog. > techniques. Thus, I am feeling my way through. I am writing code similiar > to the following structure (in Turbo Prolog V2.0): > > loop(In):- > check_mouse, > do_eval(In, Out), > loop(Out). > loop(_):- > do_exit. > > The compiler recognizes that it is tail-recursive, but still allocates memory > off the heap during each iteration. As the loop should only be run when > the mouse button is pressed, the check_mouse succeeds when the button is > pressed, but fails otherwise. Commenting out the check_mouse or do_eval > call does not necessarily stop the heap allocation, although commenting > out both certainly does (of course). The easiest solution would be to > make a predicate fail somewhere, but, then, how would I be able to get a > return value? (Using reference vars or internal dbases seems to make the > program run unacceptably slow). > > Tim G. If you want both input to and output from a predicate, it must have a arity greater than one: loop(In,Out):- check_mouse, process(In,Out). It's not clear from your example why you need a recursive structure. However, Prolog will eat lots of memory if a non-deterministic predicate is called within the clause. To avoid this, ensure that called predicates are non-deterministic, or use a cut after the non-deterministic call: loop(In,In):- condition(satisfied). loop(In,Out):- process(In,In2),!, %"process" is non-deterministic .... loop(In2,Out). Note that variable "Out" remains unbound until the desired condition is satisfied. 'Hope this helps, Euan Mason University of Canterbury, NZ.
jgarland@kean.ucs.mun.ca (08/14/90)
In article <kalQPim00WB242VkMS@andrew.cmu.edu>, tg1e+@andrew.cmu.edu (Timothy R. Gottschalk) writes: > Re the following Turbo (PDC) Prolog structure: > > loop(In):- > check_mouse, > do_eval(In, Out), > loop(Out). > loop(_):- > do_exit. > > The compiler recognizes that it is tail-recursive, but still allocates memory ^^^^^^^^^^^^^^????? mine does'nt--it says loop is nondeterminstic > off the heap during each iteration. As the loop should only be run when ^^^^??? Did you check this--mine allocates *stack* space which is a clue to what's happening > The easiest solution would be to > make a predicate fail somewhere, but, then, how would I be able to get a > return value? See below. > > Tim G. The structure you're trying to use is common in Turbo (now PDC) Prolog--though it does violate many principles of good Prolog programming practice in other implementations. Below you'll find 2 listings which get at your trouble. Trace through them. Note that the main problem is that your predicate is NOT able to take advantage of tail recursion optimization and so *stack*, not heap, space is used on each iteration as you trace through the predicate loop_1/1 but not when you trace through loop_1_withcut/1 As these listings are in PDC Prolog (next version up from TP2) you'll need to change the storage predicate back to the Turbo way of doing things and add a few write statements. A last note is that the PDC Prolog Toolbox includes a number of mouse-handling predicates that are quite fast. I also seem to remember these being published in the now-defunct Turbo Technix magazine in 1988. /********* Listing 1 ************************************/ shorttrace % Don't use 'trace' as it turns tail recursion off diagnostics % NOTE loop_1 will be NONdeterministic and will generate % backtracking points on each iteration and consume % stack space predicates loop_1(integer) clauses loop_1(X) :- storage, % PDC PREDICATE--REPLACE WITH TP2 PREDICATE AND WRITES X < 10, % equivalent to check_mouse Out=X+1, % equivalent to do_eval loop_1(Out). % recursive call, push this iteration on to stack as we may % want to return to backtrack points loop_1(_). % succeed gracefully goal loop_1(1). % NOTE that the *stack* space is decremented each iteration /*********** Listing 2 ***********************************/ shorttrace % Don't use 'trace' as it turns tail recursion off diagnostics % NOTE loop_1_withcut will be deterministic and will not % generate backtracking points on each iteration and % so will not consume stack space (with t-r % optimization on) predicates loop_1_withcut(integer) clauses loop_1_withcut(X) :- storage, % PDC PREDICATE--REPLACE WITH TP2 PREDICATE AND WRITES X < 10, % equivalent to check_mouse !, % NULLIFY BACKTRACKING POSSIBILITY once we pass check % NOTE: put as early in the clause as you logically can Out=X+1, % equivalent to do_eval loop_1_withcut(Out). % tail recursive call, do not push this iteration % on to stack loop_1_withcut(_). % succeed gracefully goal loop_1_withcut(1). % NOTE that *no* space is lost each iteration *************************** end of listings *********************