Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!stretch.cs.mun.ca!leif!jgarland From: jgarland@kean.ucs.mun.ca Newsgroups: comp.lang.prolog Subject: Re: Prolog Prog. Technique Question Message-ID: <124802@kean.ucs.mun.ca> Date: 13 Aug 90 19:41:20 GMT References: Organization: Memorial University. St.John's Nfld, Canada Lines: 112 In article , 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 *********************