[mercury-users] Re: Users List... stacks, collection

[Fergus Henderson]

On 10-Oct-2002, Noel  Pinto <cool4life at rediffmail.com> wrote:
> I want to know the exact purpose of det stack and nondet stack. 
> The rough idea I have is that det and nondet is part of 
> determinism. Why is it used? What is a part of these stacks?

The "det" and "nondet" stacks are used by the code generated by the
low-level backend of the Mercury compiler.  The "nondet" stack is used
for procedures with determinism "nondet" or "multi".  The "det" stack is
used for procedures with any other determinism (i.e. "det", "semidet",
"failure", "erroneous", "cc_nondet", or "cc_multi").  The reason for
using a different stack for procedures with determinism "nondet" or
"multi" is that this stack can only be popped when such procedures
fail, not when they succeed, whereas for procedures with other determinisms,
it is possible to pop the stack when the procecure succeeds.

For more information, see [1].

With the high-level backend, the "det" and "nondet" stacks are not used;
generated code instead uses the system stack (the same stack used by e.g.
C code).

> I also want to know what goes into 'conservative garbage collection'?

>From the gclist GC FAQ list <http://www.iecc.com/gclist/GC-faq.html>:

 | Conservative garbage collection makes use of the observation that if
 | you are not relocating (copying) objects, then you need not be quite so
 | certain about exactly what is a pointer. It suffices to scan the root
 | set (and objects) for any pointer-like bit patterns, and treat those
 | pointer-like bit patterns as actual pointers while marking. The result
 | is that the "true" reachable objects are all found, along with a few
 | others. This works surprisingly well in practice (if a few additional
 | tricks are added) and often permits the use of garbage collection with
 | oblivious source code and compilers.
 | 
 | Conservative collection is very important because it permits the use
 | of garbage collection with programs that were not written with garbage
 | collection in mind.  That is, it simpifies the use of garbage collection
 | with existing (non-garbage-collected) libraries of code.

For more information see [2, 3, 4].

> Why used and should be changed??

It is used for simplicity of implementation, for ease of interfacing,
and for performance.

There are some arguments as to why accurate garbage collection can
sometimes be preferable -- see [5] -- but currently this comes at a cost
of increased implementation complexity, increased difficulty interfacing
with third-party libraries, and/or worse performance.

References:
[1] Zoltan Somogyi, Fergus Henderson and Thomas Conway. 
    "The execution algorithm of Mercury: an efficient purely declarative
    logic programming language."  Journal of Logic Programming, volume 29,
    number 1-3, October-December 1996, pages 17-64.
[2] The Harlequin memory management glossary.  <http://www.memorymanagement.org/
    glossary/c.html#conservative.garbage.collection>
[3] Hans-J. Boehm, Mark Weiser. "Garbage collection in an uncooperative
    environment."  1988.  Available on the web.
[4] Hans-J. Boehm.  "Space Efficient Conservative Garbage Collection."  1993. 
    Available on the web.
[5] Fergus Henderson.  Accurate garbage collection in an uncooperative
    environment.  Proceedings of the 2002 International Symposium on Memory
    Management, Berlin, Germany, June 2002, pages 150-156.
    Available on the web (in the papers section of the Mercury home page).

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------