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

[Mostowski Collapse]

I read the following, and you should also know:

> Python's [] is implemented as an array, not a linked list. 
> Although resizing is O(n), appending to it is amortized O(1), 
> because resizes happen very rarely. 
https://stackoverflow.com/a/5932364/502187

The list type doesn't have an O(1) operation to remove
an element during sweep. The list type, not like its name 
would suggest, in Python is an array.

These arrays are not so expensive when you append()
an element. Because they are allocated with some excess
capacity. And they grow exponentially.

So amortisized you can append() a lot of elements to
a Python list, which is an array. But you cannot poke so
cheaply holes into it. So if you have this scenario:

Before:
     - [ A1, .., An , B, C1, .., Cm ]

After:
     - [ A1, .., An , C1, .., Cm ]
   
You have to copy C1,..,Cm one position down. On the other
hand, when scanning the single list, removing the
element is just pointer swizzling.

The code is here, the positive if-then-else branch keeps
the element, the negative if-then-else branch drops the
element. Thats quite standard algorithm for linked lists:

     /* pointer swizzling */
    while temp is not None:
        term = temp
        temp = term.tail
        if (term.flags & MASK_VAR_MARK) != 0:
            term.flags &= ~MASK_VAR_MARK
            if back is not None:
                back.tail = term
            else:
                trail = term
            back = term
        else:
            term.instantiated = NotImplemented
            term.tail = None
            count -= 1

https://github.com/jburse/dogelog-moon/blob/main/devel/runtimepy/drawer/machine.py#L163

There is nothing wrong with implementing a single list
in Python. Only you never saw that one maybe. If you would
indeed use Python lists which are arrays, you would

maybe get a much slower sweep_trail() and this would
be seen. But currently its not seen. It happens that 1000000
of elements are sweeped, if you would do this with copy

inside a Python list which are arrays, it would get much
more expensive, and the extremly cheap Prolog garbage
collection, as it stands now, wouldn't be that cheap anymore.

You can try yourself. My sweep_trail() needs frequent resize,
which would be O(n) each, so that sweep_trail becomes O(n^2).
Which the current implementation its only O(n).

Peter J. Holzer schrieb am Montag, 20. September 2021 um 13:49:49 UTC+2:
> On 2021-09-20 04:33:39 +1000, Chris Angelico wrote: 
> > On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse <janb... at fastmail.fm> wrote:
> > > 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. 
> > > 
> >
> > I don't know. I don't understand your code well enough to offer advice 
> > like that, because *your code is too complicated* and not nearly clear 
> > enough. 
> > 
> > But however it is that you're doing things, the best way is almost 
> > always to directly refer to objects. Don't fiddle around with creating 
> > your own concept of a doubly-linked list and a set of objects; just 
> > refer directly to the objects.
> And almost certainly: Just use the builtin list type if you need a list. 
> Don't build one yourself.
> > Let Python be Python, don't try to build your own language on top of 
> > it.
> Well, he's writing a Prolog interpreter, so building his own language on 
> top of Python is sort of the point. I think a better way to put it is 
> "Don't try to write Python as if it was C". A C operation may be 
> compiled to a single machine instruction which is executed in a fraction 
> of a nanosecond. A Python instruction (in CPython) always includes at 
> least the interpreter overhead and often several method lookups and method 
> calls. You want to amortize that overhead over as much work as possible. 
> 
> hp 
> 
> -- 
> _ | Peter J. Holzer | Story must make more sense than reality. 
> |_|_) | | 
> | | | h... at hjp.at | -- Charles Stross, "Creative writing 
> __/ | http://www.hjp.at/ | challenge!"