ANN: Dogelog Runtime, Prolog to the Moon (2021)

[Mostowski Collapse]

The trail itself can possibly not be eliminated. Its like a
database logfile. The trail is used during backtracking to
undo variable bindings. Which is like a database rollback.

Here is an example where a tail is used:

/* X equals 1 or X equals 2 */
?- X=1; X=2.
X = 1;
X = 2.

In the first answer the trail will have recorded that X
was bound to 1. When the second answer is requested,
the trail is used to unbind X, so that it can be bound to 2.

The Prolog garbage collection is a compactification
of the trail. Maybe databases can do the same with their
logfiles, for example if a logfile contains an insert and

then a delete of the same row, then these two logentries
can be merged. The only difference here is that Prolog
garbage collection primarily compactes towards trail

entries that have become irrelevant. This is part of 
intelligent bracktracking, and backjumping over multiple
goal invocations, that didn't record a choice point.

The Prolog garbage collection can compact the trail
before backjumping happens. So that Prolog search
has more space available.

Mostowski Collapse schrieb am Sonntag, 19. September 2021 um 10:51:03 UTC+2:
> I am refering to: 
> 
> Greg Ewing schrieb:
> > where [w] is a weak reference object. Then you could periodically 
> > scan the trail looking for dead weakref objects and remove the 
> > corresponding [*] node from the list. 
> > 
> > You can also attach callbacks to weakref objects that are triggered 
> > when the referenced object dies. You might be able to make use of 
> > that to remove items from the trail instead of the periodic scanning.
> Question to Chris Angelico: If I stay with my 
> sweep_trail(), which is the periodically scanning, 
> I can use a single linked list. 
> 
> On the other hand if I would use the trigger 
> from Python, I possibly would need a double linked 
> list, to remove an element. 
> 
> Chris Angelico, is there a third option, that I have 
> overlooked? Single linked list uses less space 
> than double linked list, this why I go with scan. 
> 
> Chris Angelico schrieb:
> > On Sun, Sep 19, 2021 at 11:46 AM Mostowski Collapse <burs... at gmail.com> wrote: 
> >> 
> >> Yeah, it seems weak references could indeed spare 
> >> me mark_term(). But then I am stil left with sweep_trail(). 
> >> I did not yet measure what takes more time mark_term() 
> >> or sweep_trail(). The displayed "gc" is the sum of both. 
> >> 
> >> From what I have seen, very large trail practically reduced 
> >> to a zero trail during Prolog GC, I am assuming that 
> >> mark_term() is not the working horse. Usually mark_term() 
> >> only marks what is not-Garbage, and sweep_trail() 
> >> 
> >> has to deal with Garbage and not-Garbage. And there 
> >> is usually a lot of Garbage, much more than not-Garbage. 
> >> Finding the objects that survive, is like finding the needle 
> >> in the haystack, except we do not have to scan the 
> > 
> > If you stop referring to something, it is garbage. Python will dispose of it. 
> > 
> > You literally need to do nothing at all, and let the language take 
> > care of things. 
> > 
> > ChrisA 
> >