rcastelletto@lion.waterloo.edu (Ron Castelletto) (03/30/90)
Can someone out there please help me with a Prolog question??
I am using Turbo Prolog on an IBM-compatible 286 machine and I'm having
problems understanding why certain functions do NOT return heap space
when the function returns.
For example, I am using the following two function: findPos and ndel,
when I call findPos, all heap storage is returned at the end of the call,
BUT when I call ndel, I lose a few bytes of memory (heap storage) on every
call. I suspect it has something to do with non-deterministic functions and/or
tail-recusive functions but I can't figure out what the conditions are for a
functions to return its storage.
I will try to explain the 2 functions now.
% ------------------------------ findPos
findPos : does NOT lose heap memory
parameter 1: a integer, known at time of call
2: a list of nodes as follows ( [n(1,2), n(3,4)...n(5,2) ] ) also
known at time of call.
3: the second value of the node having a first value of Pos, note
only one node will match Pos. (i.e. first value of a node in
the list is unique).
Ex: findPos( 3, [ n(1,2), n(4,3), n(3,6), n(12,5)], X )
will return X = 6. (2nd clause)
if no node matches, the call will fail. (1st clause)
findPos(_, [], 0) :-
fail.
findPos(Pos, [n(Pos,Cnt)|Rest], Cnt) :-
!.
findPos(Pos, [n(Pos2,Cnt2)|Rest], Cnt) :-
findPos(Pos, Rest, Cnt).
% ------------------------- delnode
ndel : LOSES heap memory on every call
parameter 1: a integer, known at time of call
2: a list of nodes as follows ( [n(1,2), n(3,4)...n(5,2) ] ) also
known at time of call.
3: a list which is the the result of removing the node having Pos
as the first value.
Note: the list is guaranteed to contain a node (exactly one) that should
be removed.
Ex: ndel( 3, [ n(1,2), n(4,3), n(3,6), n(12,5)], X )
will return X = [ (n(1,2), n(4,3), n(12,5)].
ndel(Posn, [n(Posn, _)|Tail], Tail ) :-
!.
ndel(Posn, [Node|Tail], [Node|NewList] ) :-
ndel(Posn, Tail, NewList ).
Since, both functions use tail-recursion and cuts at appropriate places, I
do not understand why one function LOSES heap storage and the other doesn't.
Does anybody know what conditions cause a function to waste heap storage??
Please reply through e-mail.
Thanks,
Ron Castelletto
rcastelletto@lion.waterloo.edu