Term reuse

[fku]

Hi there!

Let's assume we have the following program:

make_huge_list(L1), append(L1,[foo],L2), use_list(L2).

Let's further assume that all these predicates are deterministic.

In executing append, could a Prolog implementation figure out that L1
is no longer needed and somehow reuse it for L2, or after append we
will have two huge lists in memory?

Thanks,
Jan

[Bart Demoen]

Prolog implementations typically end up with two huge lists - except that
garbage collection might kick in before the append is finished and the part
of List1 that is no longer needed can be reclaimed.
You can see this for yourself with the following program (just a variant of
yours with some statistics):

t(N) :-
statistics(globalused,U0), writeln(U0),
length(List1,N),
statistics(globalused,U1), writeln(U1),
append(List1,[foo],List2),
statistics(globalused,U2), writeln(U2).

Prolog systems usually don't do determinism analysis nor enough liveness analysis.
And then one needs what is named "compile time garbage collection", i.e. one
must emit code that reuses the List1-cells immediately.
Such a thing exists in Mercury. There, the cells of List1 would be reused for
List2.
If you are really interested in this, have a look at the PhD of Nancy Mazur.

Cheers

Bart Demoen

[Ulrich Neumerkel]

fku <fic...@bluebottle.com> writes:
>In executing append, could a Prolog implementation figure out that L1
>is no longer needed and somehow reuse it for L2, or after append we
>will have two huge lists in memory?

Current implementations do not use such techniques. You would need
some kind of static analysis or dynamic reference counting.
Nondeterminism might complicate things too much. One-bit reference
counting [1] could be an option. There have been several hardware
implementations for PSI [2] while unaware of [1]. Up to 30% gain is
reported which is not too much when considering a dedicated hardware
implementation.

In software it is even less attractive, although some native code
compilation might profit from it, since in one-bit reference counting
the bit is stored in the pointer and not the data.

[1] Wise, David S., & Friedmann, Daniel P., The One-Bit Reference
Count, BIT, 17, 351-359, (1977).

[2] Kenji Nishida, Yasunori Kimura, Akira Matsumoto, Atsuhiro Goto:
Evaluation of MRB Garbage Collection on Parallel Logic Programming
Architectures. ICLP 1990: 83-95