Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!um-math!sharkey!shadooby!accuvax.nwu.edu!tank!ncar!ames!hc!lll-winken!uunet!mcvax!tuvie!brock
From: brock@tuvie (Inst.f.Prakt.Info 1802)
Newsgroups: comp.lang.prolog
Subject: Re: Committed Choice
Summary: shared structures might produce garbage
Keywords: cut if-then-else Garbage on the stacks
Message-ID: <674@tuvie>
Date: 6 Apr 89 03:22:09 GMT
References: <11500012@hpldola.HP.COM> <733@gould.doc.ic.ac.uk> <18798@adm.BRL.MIL> <192@aucsv.UUCP> <751@gould.doc.ic.ac.uk>
Reply-To: ulrich@vip.UUCP (Ulrich Neumerkel)
Organization: Technical University of Vienna, EDP-Center
Lines: 31

In article <751@gould.doc.ic.ac.uk> cdsm@doc.ic.ac.uk (Chris Moss) writes:
[...]
>so they can be represented by parameterless procedures (or procedures that
>take only input bindings). Thus they do not produce garbage on the stack
                                      ^^^^^^^^^^^^^^^^^^^^^^
>if the top level is a tail recursive procedure.
>Is there any way such a program can run out of memory?

It just depends what You mean by garbage. Try the following little program
which implements the equivalent of LISP's "blam"-lists:

blam(0,[]).
blam(N,[L|L]) :- N > 0, M is N - 1, blam(M,L).
 
..., blam(32,L), assert(little_fact(L)),...

Even if this would be successfully executed - is there any Prolog which
can do this? Quite shure not (Might be - that some LISP-based implementation 
take this, but this is only a very vage speculation) 
However You'll also have problems when just trying to copy such a blam list.

Now this was the worst case which might occur: You had a term represented
by N lists which implements a term consisting of 2^N - 1 lists. In practical 
programs You`ll probably get only some growth nearer to k*N when You use
shared variables heaviliy. Most probably when transforming graphs. 

So my question is just. Do You or anyone else have applications using shared
variables <which are later on bound to some structures> ? :-)
 
Ulrich Neumerkel  (ulrich@vip.UUCP  UUCP: ...!mcvax!tuvie!vip!ulrich) 
<<please don't type "r", but mail to the adress above>>