On Mon, Sep 20, 2021 at 9:50 PM Peter J. Holzer <hjp-python@hjp.at> wrote:
> > 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".

Fair point. Or combining them both: Writing a language interpreter in
Python as if you were writing it in C, and then complaining that it is
slow, is only going to elicit "well uhh yes?" responses.

Languages like NetRexx (and, I think, Jython, although I can't find
any definitive and current answers) are slightly different from their
"parent" languages, because they make good use of their implementation
languages' features. This Prolog interpreter might not even need to be
different in functionality, but its implementation would be different,
and it could take advantage of the underlying garbage collection.

ChrisA

The sweep_trail() is not an issue. There must be a bottleneck
somewhere else in Python. The sweep_trail() respectively the
paremt call gc() only takes a very small fraction of the runtime:

Check the "gc" timing, the bottleneck is somewhere else?

Mostowski Collapse schrieb am Freitag, 17. September 2021 um 10:58:57 UTC+2:
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> % Standard Python Version, Warm Run
> % ?- time(fibo(23,X)).
> % % Wall 3865 ms, gc 94 ms, 71991 lips
> % X = 46368.
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> % GraalVM Python Version, Warm Warm Run
> % ?- time(fibo(23,X)).
> % % Wall 695 ms, gc 14 ms, 400356 lips
> % X = 46368.

Also my code is not C-style. If I would use C-style code, I would
use address calculations and the adress operator &. But you
don't find and according C-style in the Python or JavaScript code.

Also there is no substitute for such coding style in the for
of value holders or some such. Its all plain Python respectively
JavaScript not at all inspired by the C programming language.

The single linked list is not some indicative of C programming
language style. With C programming language sytle one would
do other tricks, you cannot read off from my Python or JavaScript

code, since I cannot apply them to Python or JavaScript. Among
the other C programming language tricks not available in Python
or JavaScript would for example be inlining the args in Compound

and so on. But I am not sure whether this is the bottleneck.

Chris Angelico schrieb am Montag, 20. September 2021 um 14:25:12 UTC+2:
> On Mon, Sep 20, 2021 at 9:50 PM Peter J. Holzer <hjp-p...@hjp.at> wrote:
> > > 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".
> Fair point. Or combining them both: Writing a language interpreter in
> Python as if you were writing it in C, and then complaining that it is
> slow, is only going to elicit "well uhh yes?" responses.
>
> Languages like NetRexx (and, I think, Jython, although I can't find
> any definitive and current answers) are slightly different from their
> "parent" languages, because they make good use of their implementation
> languages' features. This Prolog interpreter might not even need to be
> different in functionality, but its implementation would be different,
> and it could take advantage of the underlying garbage collection.
>
> ChrisA

Also I am not a C programmer. The last time I was programming C
was 30 years ago. I am mostly a Java programmer the recent years.
Dogelog Runtime adopts a lot of implementation details from

Jekejeke Prolog which is a Prolog written in Java. The difference
betweeen the two is that Jekejeke Prolog has another Prolog term
model where Prolog terms are passed around as molecs, which

are pairs of skeleton and display. On the other in Dogelog Runtime
uses a simpler representation, Prolog terms are passed around
as only one object. Programming language wise the difference

between using Java and JavaScript or Python, is that Java has
types. So variables need a type declaration. Otherwise Java is
very similar to JavaScript or Python, it also provides a runtime with

a garbage collection. The idea I would use C-style is a little absurd. It
would also require that a free() objects manually. But sweep_trail() has
nothing to do with freeing objects manually, its the anti-thesis to

freeing objects manually, its a Prolog garbage collector after all!

Mostowski Collapse schrieb am Montag, 20. September 2021 um 14:36:01 UTC+2:
> The sweep_trail() is not an issue. There must be a bottleneck
> somewhere else in Python. The sweep_trail() respectively the
> paremt call gc() only takes a very small fraction of the runtime:
>
> Check the "gc" timing, the bottleneck is somewhere else?
> Mostowski Collapse schrieb am Freitag, 17. September 2021 um 10:58:57 UTC+2:
> > %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> > % Standard Python Version, Warm Run
> > % ?- time(fibo(23,X)).
> > % % Wall 3865 ms, gc 94 ms, 71991 lips
> > % X = 46368.
> >
> > %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> > % GraalVM Python Version, Warm Warm Run
> > % ?- time(fibo(23,X)).
> > % % Wall 695 ms, gc 14 ms, 400356 lips
> > % X = 46368.
> Also my code is not C-style. If I would use C-style code, I would
> use address calculations and the adress operator &. But you
> don't find and according C-style in the Python or JavaScript code.
>
> Also there is no substitute for such coding style in the for
> of value holders or some such. Its all plain Python respectively
> JavaScript not at all inspired by the C programming language.
>
> The single linked list is not some indicative of C programming
> language style. With C programming language sytle one would
> do other tricks, you cannot read off from my Python or JavaScript
>
> code, since I cannot apply them to Python or JavaScript. Among
> the other C programming language tricks not available in Python
> or JavaScript would for example be inlining the args in Compound
>
> and so on. But I am not sure whether this is the bottleneck.
> Chris Angelico schrieb am Montag, 20. September 2021 um 14:25:12 UTC+2:
> > On Mon, Sep 20, 2021 at 9:50 PM Peter J. Holzer <hjp-p...@hjp.at> wrote:
> > > > 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".
> > Fair point. Or combining them both: Writing a language interpreter in
> > Python as if you were writing it in C, and then complaining that it is
> > slow, is only going to elicit "well uhh yes?" responses.
> >
> > Languages like NetRexx (and, I think, Jython, although I can't find
> > any definitive and current answers) are slightly different from their
> > "parent" languages, because they make good use of their implementation
> > languages' features. This Prolog interpreter might not even need to be
> > different in functionality, but its implementation would be different,
> > and it could take advantage of the underlying garbage collection.
> >
> > ChrisA

Now I am expecting somebody telling me I should not
program Java style in Python. So I wonder what would have
happened if I would tell you I am FORTRAN programmer.

Then somebody would tell me I should not program
FORTRAN style in Python. Hopefully this makes it evident
that this argumentation is moot.

Better would be more facts on the table based on
the existing code of Dogelog runtime. The future Dogelog
runtime code will possibly use ast.parse() and compile().

Thats why I am conducting this experiment which has only
been half way completed. The experiment is conducted
because Python belongs to the champ of dynamic languages:

Dynamic programming language
https://en.wikipedia.org/wiki/Dynamic_programming_language

The experiment will be completed when the ast.parse()
and compile() thingy was explored as well. As it happens I
am conducting the experiment in parallel for JavaScript and

Python, both being dynamic programming languages.

Mostowski Collapse schrieb am Montag, 20. September 2021 um 14:43:01 UTC+2:
> Also I am not a C programmer. The last time I was programming C
> was 30 years ago. I am mostly a Java programmer the recent years.
> Dogelog Runtime adopts a lot of implementation details from
>
> Jekejeke Prolog which is a Prolog written in Java. The difference
> betweeen the two is that Jekejeke Prolog has another Prolog term
> model where Prolog terms are passed around as molecs, which
>
> are pairs of skeleton and display. On the other in Dogelog Runtime
> uses a simpler representation, Prolog terms are passed around
> as only one object. Programming language wise the difference
>
> between using Java and JavaScript or Python, is that Java has
> types. So variables need a type declaration. Otherwise Java is
> very similar to JavaScript or Python, it also provides a runtime with
>
> a garbage collection. The idea I would use C-style is a little absurd. It
> would also require that a free() objects manually. But sweep_trail() has
> nothing to do with freeing objects manually, its the anti-thesis to
>
> freeing objects manually, its a Prolog garbage collector after all!
> Mostowski Collapse schrieb am Montag, 20. September 2021 um 14:36:01 UTC+2:
> > The sweep_trail() is not an issue. There must be a bottleneck
> > somewhere else in Python. The sweep_trail() respectively the
> > paremt call gc() only takes a very small fraction of the runtime:
> >
> > Check the "gc" timing, the bottleneck is somewhere else?
> > Mostowski Collapse schrieb am Freitag, 17. September 2021 um 10:58:57 UTC+2:
> > > %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> > > % Standard Python Version, Warm Run
> > > % ?- time(fibo(23,X)).
> > > % % Wall 3865 ms, gc 94 ms, 71991 lips
> > > % X = 46368.
> > >
> > > %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> > > % GraalVM Python Version, Warm Warm Run
> > > % ?- time(fibo(23,X)).
> > > % % Wall 695 ms, gc 14 ms, 400356 lips
> > > % X = 46368.
> > Also my code is not C-style. If I would use C-style code, I would
> > use address calculations and the adress operator &. But you
> > don't find and according C-style in the Python or JavaScript code.
> >
> > Also there is no substitute for such coding style in the for
> > of value holders or some such. Its all plain Python respectively
> > JavaScript not at all inspired by the C programming language.
> >
> > The single linked list is not some indicative of C programming
> > language style. With C programming language sytle one would
> > do other tricks, you cannot read off from my Python or JavaScript
> >
> > code, since I cannot apply them to Python or JavaScript. Among
> > the other C programming language tricks not available in Python
> > or JavaScript would for example be inlining the args in Compound
> >
> > and so on. But I am not sure whether this is the bottleneck.
> > Chris Angelico schrieb am Montag, 20. September 2021 um 14:25:12 UTC+2:
> > > On Mon, Sep 20, 2021 at 9:50 PM Peter J. Holzer <hjp-p...@hjp.at> wrote:
> > > > > 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".
> > > Fair point. Or combining them both: Writing a language interpreter in
> > > Python as if you were writing it in C, and then complaining that it is
> > > slow, is only going to elicit "well uhh yes?" responses.
> > >
> > > Languages like NetRexx (and, I think, Jython, although I can't find
> > > any definitive and current answers) are slightly different from their
> > > "parent" languages, because they make good use of their implementation
> > > languages' features. This Prolog interpreter might not even need to be
> > > different in functionality, but its implementation would be different,
> > > and it could take advantage of the underlying garbage collection.
> > >
> > > ChrisA

On Tue, Sep 21, 2021 at 3:51 AM Mostowski Collapse <janburse@fastmail.fm> wrote:
>
> sympy also builds a language on top of Python.
> pandas also builds a language on top of Python.
>
> Is there some pope that says this wouldn't be
> allowed, I dont think so, otherwise sympy, pandas, etc..
>
> wouldn't exist. I dont understand your argument.
>

That's not the same thing as reimplementing your own low-level
features on top of a high level language.

ChrisA

On 20/09/2021 07.08, Mostowski Collapse wrote:
> 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 ]
Do you happen to know what the asymptotic complexity of the
remove operation is?

>>> l = ["A1","A2","An","B","C1","C2","Cm"]
>>> l.remove("B")
>>> l
['A1', 'A2', 'An', 'C1', 'C2', 'Cm']
>>>

I can't figure out any way to benchmark it that doesn't involve
creation of ever-longer lists, which would probably mask its effects.

--
Michael F. Stemper
Deuteronomy 24:17

Again, I don't implement any low level features,
that would explain any bottleneck in the performance
of Python. gc() is only a very small percentage.

You are halucinating.

Chris Angelico schrieb am Montag, 20. September 2021 um 19:53:36 UTC+2:
> On Tue, Sep 21, 2021 at 3:51 AM Mostowski Collapse <janb...@fastmail.fm> wrote:
> >
> > sympy also builds a language on top of Python.
> > pandas also builds a language on top of Python.
> >
> > Is there some pope that says this wouldn't be
> > allowed, I dont think so, otherwise sympy, pandas, etc..
> >
> > wouldn't exist. I dont understand your argument.
> >
> That's not the same thing as reimplementing your own low-level
> features on top of a high level language.
>
> ChrisA

Maybe you could stop spamming my thread with
your idee fix, about something low level. Thats
just absurd. The language itself, Prolog, is extremly

highlevel, and I am using Python in a very highlevel
fashion. There is nothing C-ish in my code. You
are just spamming the ever same nonsense.

Mostowski Collapse schrieb am Montag, 20. September 2021 um 19:58:36 UTC+2:
> Again, I don't implement any low level features,
> that would explain any bottleneck in the performance
> of Python. gc() is only a very small percentage.
>
> You are halucinating.
> Chris Angelico schrieb am Montag, 20. September 2021 um 19:53:36 UTC+2:
> > On Tue, Sep 21, 2021 at 3:51 AM Mostowski Collapse <janb...@fastmail.fm> wrote:
> > >
> > > sympy also builds a language on top of Python.
> > > pandas also builds a language on top of Python.
> > >
> > > Is there some pope that says this wouldn't be
> > > allowed, I dont think so, otherwise sympy, pandas, etc..
> > >
> > > wouldn't exist. I dont understand your argument.
> > >
> > That's not the same thing as reimplementing your own low-level
> > features on top of a high level language.
> >
> > ChrisA

If you don't know the index of the element, you
need first to find the element which is O(n).
And then removing it is O(n) again.

See also here:

> 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

Michael F. Stemper schrieb am Montag, 20. September 2021 um 19:56:59 UTC+2:
> Do you happen to know what the asymptotic complexity of the
> remove operation is?

On Tue, Sep 21, 2021 at 3:58 AM Mostowski Collapse <bursejan@gmail.com> wrote:
>
> 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).
>

How about, instead: Use a Python list, and instead of removing
individual items one by one, filter out the ones you don't want, using
a list comprehension? That would be O(n) to completely remove all the
ones you don't want, instead of O(n) for each individual removal.

Also, have you actually benchmarked a version that uses Python's
lists, or are you simply assuming that the removals will be slow?
Implementing your own singly-linked list was clearly suboptimal, but
have you tried writing simpler code and seeing if it is also faster?

ChrisA

Its a good idea to use list comprehension. But its
an incomplete solution.

I don't think the single list is suboptimal, it has complexity
O(n). How would you solve the adjust_mark() problem with
list comprehension?

Also I am not using anything low-level. I don't use a
module unsafe or some such. I even don't know whether
Python has a module unsafe, but other high level

languages do it by a module unsafe. There are now
3 claims by Chris Angelico that are completely baseless
and just polute this thread:

- Baseless Claim 1: Need to optimize gc(), but
it takes only 2-3% of runtime. Why would I optimize gc().

- Baseless Claim 2: My single list is subobtimal,
but it is O(n), the same complexity as list comprehension,
but there is no list comprehension solution around
that also solves the adjust_mark() issue.

- Baseless Claim 3: My code is low level. But nothing
in the code is low level, its all programmed in proper
Python high level. List comprehension, that doesn't
solve the problem is not more high level than single
linked lists. Its just a failed attempt at a solution.

The adjust_mark() is also explained here. See section
"Sweeping the Stack" (Page 22). The paper does it slightly
different than Dogelog Runtime. Dogelog Runtime does it:

/* Dogelog Runtime */
adjust_mark() /* which is the SICStus sweep_stack() */
sweep_stack() /* which includes the SICStus compact_heap(), so to speak */

SICStus has sweep_stack() without compact_heap() first.
The paper shows C-code. But this doesn't imply that
I want C-code. I am only using it as an algorithmic

template, not as a verbatim code template.

Mostowski Collapse schrieb am Montag, 20. September 2021 um 14:22:05 UTC+2:
> Garbage Collection for Prolog Based on WAM
> January 1986
> Karen Appleby, Mats Carlsson, Seif Haridi, Dan Sahlin
> https://www.researchgate.net/publication/279463524

Chris Angelico schrieb am Montag, 20. September 2021 um 20:09:52 UTC+2:
> On Tue, Sep 21, 2021 at 3:58 AM Mostowski Collapse <burs...@gmail.com> wrote:
> >
> > 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).
> >
> How about, instead: Use a Python list, and instead of removing
> individual items one by one, filter out the ones you don't want, using
> a list comprehension? That would be O(n) to completely remove all the
> ones you don't want, instead of O(n) for each individual removal.
>
> Also, have you actually benchmarked a version that uses Python's
> lists, or are you simply assuming that the removals will be slow?
> Implementing your own singly-linked list was clearly suboptimal, but
> have you tried writing simpler code and seeing if it is also faster?
>
> ChrisA

On Monday, September 20, 2021 at 1:52:18 PM UTC+1, Mostowski Collapse wrote:
> Now I am expecting somebody telling me I should not
> program Java style in Python. So I wonder what would have
> happened if I would tell you I am FORTRAN programmer.
>

http://dirtsimple.org/2004/12/python-is-not-java.html
http://dirtsimple.org/2004/12/java-is-not-python-either.html

A good picture in the paper is on Page 25. The picture
as 3 diagrams. The following diagrams correspond
to Dogelog runtime code:

2. Diagram: Updating the Choice Points, this my adjust_mark()
3. Diagram: Sliding the Trail, this is my sweep_trail()

The above solution is linked list based. If you can
provide an array based solution, using list comprehension,
why not? But is it possible? And how?

I am refering to this paper:

Mostowski Collapse schrieb am Montag, 20. September 2021 um 14:22:05 UTC+2:
> Garbage Collection for Prolog Based on WAM
> January 1986
> Karen Appleby, Mats Carlsson, Seif Haridi, Dan Sahlin
> https://www.researchgate.net/publication/279463524

P.S.: I know how it could be done with list comprehension,
in that you do a kind of double comprehension, or two separate
comprehensions with some variable remembering the last

non-marked trail. This would require to traverse the choice
points from the bottom, in parallel to the trail. But it would
require to replace the choice points by another datastructure,

because the choice points also point only from top to bottom,
and there is no order from bottom to top. But even if you
manage to implement this circus act, it still begs the

question what you gain? Since garbage collection only
takes 2-3% of execution time?

Mostowski Collapse schrieb am Montag, 20. September 2021 um 20:28:12 UTC+2:
> Its a good idea to use list comprehension. But its
> an incomplete solution.
>
> I don't think the single list is suboptimal, it has complexity
> O(n). How would you solve the adjust_mark() problem with
> list comprehension?
>
> Also I am not using anything low-level. I don't use a
> module unsafe or some such. I even don't know whether
> Python has a module unsafe, but other high level
>
> languages do it by a module unsafe. There are now
> 3 claims by Chris Angelico that are completely baseless
> and just polute this thread:
>
> - Baseless Claim 1: Need to optimize gc(), but
> it takes only 2-3% of runtime. Why would I optimize gc().
>
> - Baseless Claim 2: My single list is subobtimal,
> but it is O(n), the same complexity as list comprehension,
> but there is no list comprehension solution around
> that also solves the adjust_mark() issue.
>
> - Baseless Claim 3: My code is low level. But nothing
> in the code is low level, its all programmed in proper
> Python high level. List comprehension, that doesn't
> solve the problem is not more high level than single
> linked lists. Its just a failed attempt at a solution.
>
> The adjust_mark() is also explained here. See section
> "Sweeping the Stack" (Page 22). The paper does it slightly
> different than Dogelog Runtime. Dogelog Runtime does it:
>
> /* Dogelog Runtime */
> adjust_mark() /* which is the SICStus sweep_stack() */
> sweep_stack() /* which includes the SICStus compact_heap(), so to speak */
>
> SICStus has sweep_stack() without compact_heap() first.
> The paper shows C-code. But this doesn't imply that
> I want C-code. I am only using it as an algorithmic
>
> template, not as a verbatim code template.
> Mostowski Collapse schrieb am Montag, 20. September 2021 um 14:22:05 UTC+2:
> > Garbage Collection for Prolog Based on WAM
> > January 1986
> > Karen Appleby, Mats Carlsson, Seif Haridi, Dan Sahlin
> > https://www.researchgate.net/publication/279463524
> Chris Angelico schrieb am Montag, 20. September 2021 um 20:09:52 UTC+2:
> > On Tue, Sep 21, 2021 at 3:58 AM Mostowski Collapse <burs...@gmail.com> wrote:
> > >
> > > 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).
> > >
> > How about, instead: Use a Python list, and instead of removing
> > individual items one by one, filter out the ones you don't want, using
> > a list comprehension? That would be O(n) to completely remove all the
> > ones you don't want, instead of O(n) for each individual removal.
> >
> > Also, have you actually benchmarked a version that uses Python's
> > lists, or are you simply assuming that the removals will be slow?
> > Implementing your own singly-linked list was clearly suboptimal, but
> > have you tried writing simpler code and seeing if it is also faster?
> >
> > ChrisA

The double comprehension, might even spare some double
work. It can happen that two different adjust_mark() calls
for two different choice points, run over the same

unmarked trail segment. I did not yet measure how often
this happened. Initially, the early Dogelog Runtime versions,
every clause had at least one variable for the continuation,

and therefore this double work didn't happen. But release 0.9.6
eliminated this variable. This makes the trail also smaller.
But now it becomes possible that adjust_mark() slides

along longer unmarked trail segments, and different adjust_mark()
might even have such segments in common now.

Mostowski Collapse schrieb am Montag, 20. September 2021 um 20:39:43 UTC+2:
> A good picture in the paper is on Page 25. The picture
> as 3 diagrams. The following diagrams correspond
> to Dogelog runtime code:
>
> 2. Diagram: Updating the Choice Points, this my adjust_mark()
> 3. Diagram: Sliding the Trail, this is my sweep_trail()
>
> The above solution is linked list based. If you can
> provide an array based solution, using list comprehension,
> why not? But is it possible? And how?
>
> I am refering to this paper:
> Mostowski Collapse schrieb am Montag, 20. September 2021 um 14:22:05 UTC+2:
> > Garbage Collection for Prolog Based on WAM
> > January 1986
> > Karen Appleby, Mats Carlsson, Seif Haridi, Dan Sahlin
> > https://www.researchgate.net/publication/279463524
> P.S.: I know how it could be done with list comprehension,
> in that you do a kind of double comprehension, or two separate
> comprehensions with some variable remembering the last
>
> non-marked trail. This would require to traverse the choice
> points from the bottom, in parallel to the trail. But it would
> require to replace the choice points by another datastructure,
>
> because the choice points also point only from top to bottom,
> and there is no order from bottom to top. But even if you
> manage to implement this circus act, it still begs the
>
> question what you gain? Since garbage collection only
> takes 2-3% of execution time?
> Mostowski Collapse schrieb am Montag, 20. September 2021 um 20:28:12 UTC+2:
> > Its a good idea to use list comprehension. But its
> > an incomplete solution.
> >
> > I don't think the single list is suboptimal, it has complexity
> > O(n). How would you solve the adjust_mark() problem with
> > list comprehension?
> >
> > Also I am not using anything low-level. I don't use a
> > module unsafe or some such. I even don't know whether
> > Python has a module unsafe, but other high level
> >
> > languages do it by a module unsafe. There are now
> > 3 claims by Chris Angelico that are completely baseless
> > and just polute this thread:
> >
> > - Baseless Claim 1: Need to optimize gc(), but
> > it takes only 2-3% of runtime. Why would I optimize gc().
> >
> > - Baseless Claim 2: My single list is subobtimal,
> > but it is O(n), the same complexity as list comprehension,
> > but there is no list comprehension solution around
> > that also solves the adjust_mark() issue.
> >
> > - Baseless Claim 3: My code is low level. But nothing
> > in the code is low level, its all programmed in proper
> > Python high level. List comprehension, that doesn't
> > solve the problem is not more high level than single
> > linked lists. Its just a failed attempt at a solution.
> >
> > The adjust_mark() is also explained here. See section
> > "Sweeping the Stack" (Page 22). The paper does it slightly
> > different than Dogelog Runtime. Dogelog Runtime does it:
> >
> > /* Dogelog Runtime */
> > adjust_mark() /* which is the SICStus sweep_stack() */
> > sweep_stack() /* which includes the SICStus compact_heap(), so to speak */
> >
> > SICStus has sweep_stack() without compact_heap() first.
> > The paper shows C-code. But this doesn't imply that
> > I want C-code. I am only using it as an algorithmic
> >
> > template, not as a verbatim code template.
> > Mostowski Collapse schrieb am Montag, 20. September 2021 um 14:22:05 UTC+2:
> > > Garbage Collection for Prolog Based on WAM
> > > January 1986
> > > Karen Appleby, Mats Carlsson, Seif Haridi, Dan Sahlin
> > > https://www.researchgate.net/publication/279463524
> > Chris Angelico schrieb am Montag, 20. September 2021 um 20:09:52 UTC+2:
> > > On Tue, Sep 21, 2021 at 3:58 AM Mostowski Collapse <burs...@gmail.com> wrote:
> > > >
> > > > 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).
> > > >
> > > How about, instead: Use a Python list, and instead of removing
> > > individual items one by one, filter out the ones you don't want, using
> > > a list comprehension? That would be O(n) to completely remove all the
> > > ones you don't want, instead of O(n) for each individual removal.
> > >
> > > Also, have you actually benchmarked a version that uses Python's
> > > lists, or are you simply assuming that the removals will be slow?
> > > Implementing your own singly-linked list was clearly suboptimal, but
> > > have you tried writing simpler code and seeing if it is also faster?
> > >
> > > ChrisA

On 2021-09-20 05:08:55 -0700, Mostowski Collapse wrote:
> 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.

That's the problem. You think that pointer swizzling is fast because you
are used to languages where this is compiled into a few machine
instructions. (Even there it depends a lot on locality: A random memory
access can take hundreds of clock cycles.)

In Python something like «a.next = b.next» normally does a dict lookup
on both objects, plus it also has to check for the existence of special
methods on both objects. You can probably copy quite a few contiguous
bytes while this is happening.

Here is a simple demo:

------------------------------------------------------------------------
#!/usr/bin/python3

import time

n = 10000

def build_linked_list(n):
head = [None, None]
tail = head
for i in range(n):
tail[1] = [i, None]
tail = tail[1]
return head

def empty_list(ls):
while ls[1]:
ls[1] = ls[1][1]

t0 = time.monotonic()
ll = build_linked_list(n)
t1 = time.monotonic()
empty_list(ll)
t2 = time.monotonic()
print(n, t1 - t0, t2 - t1)
------------------------------------------------------------------------
#!/usr/bin/python3

import time

n = 10000

def build_list(n):
return list(range(n))

def empty_list(ls):
while ls:
ls.pop(0)

t0 = time.monotonic()
ll = build_list(n)
t1 = time.monotonic()
empty_list(ll)
t2 = time.monotonic()
print(n, t1 - t0, t2 - t1)
------------------------------------------------------------------------

Both scripts create a list of n integers, then repeatedly pop off the
first element until the list is empty. The first uses a linked list
(where each element is a Python list - I guess this is faster than an
object although I haven't timed it) the second a python list. Popping
off the first element is the worst case for a python list since it is
implemented as an array of pointers and n-1 pointers have to be copied
for each operation and the best case for a linked list.

Still, on my laptop with CPython 3.8, the builtin list is faster for
lists of less than 100 elements, they are about on par between 100 and
1000 elements and only for longer lists does the linked list become
faster.

With Pypy 6.0 (yes, I know it's old), the linked list seems to be always
a bit faster although the difference is very small for lists shorter
than 100 elements - GraalVM is probably closer to PyPy than to CPython
in its performance characteristics, but the point is that the dynamic
nature of Python makes some seemingly cheap operations much more costly
than one would expect - a good optimizing compiler may be able to detect
that all that is not needed in a specific case and produce
straightforward code. But unlike for JavaScript (which has a very
similar problem) no company has spent millions of dollars on an
optimizing JIT compiler for Python yet.

hp

--
_ | Peter J. Holzer | Story must make more sense than reality.
|_|_) | |
| | | hjp@hjp.at | -- Charles Stross, "Creative writing
__/ | http://www.hjp.at/ | challenge!"

ls.pop() is probably also, not only attribute access. Just check
out the figures here, its not pop() but append():

>>> %%timeit
out = []
for x in range(10**6):
out.append(x**2)
....
1 loops, best of 3: 510 ms per loop

>>> %%timeit
out = [];append=out.append
for x in range(10**6):
append(x**2)
....
1 loops, best of 3: 467 ms per loop

https://stackoverflow.com/a/30097520/502187

Peter J. Holzer schrieb am Montag, 20. September 2021 um 21:51:59 UTC+2:
> On 2021-09-20 05:08:55 -0700, Mostowski Collapse wrote:
> > 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.
> That's the problem. You think that pointer swizzling is fast because you
> are used to languages where this is compiled into a few machine
> instructions. (Even there it depends a lot on locality: A random memory
> access can take hundreds of clock cycles.)
>
> In Python something like «a.next = b.next» normally does a dict lookup
> on both objects, plus it also has to check for the existence of special
> methods on both objects. You can probably copy quite a few contiguous
> bytes while this is happening.
>
> Here is a simple demo:
>
> ------------------------------------------------------------------------
> #!/usr/bin/python3
>
> import time
>
> n = 10000
>
> def build_linked_list(n):
> head = [None, None]
> tail = head
> for i in range(n):
> tail[1] = [i, None]
> tail = tail[1]
> return head
>
> def empty_list(ls):
> while ls[1]:
> ls[1] = ls[1][1]
>
> t0 = time.monotonic()
> ll = build_linked_list(n)
> t1 = time.monotonic()
> empty_list(ll)
> t2 = time.monotonic()
> print(n, t1 - t0, t2 - t1)
> ------------------------------------------------------------------------
> #!/usr/bin/python3
>
> import time
>
> n = 10000
>
> def build_list(n):
> return list(range(n))
>
> def empty_list(ls):
> while ls:
> ls.pop(0)
>
> t0 = time.monotonic()
> ll = build_list(n)
> t1 = time.monotonic()
> empty_list(ll)
> t2 = time.monotonic()
> print(n, t1 - t0, t2 - t1)
> ------------------------------------------------------------------------
>
> Both scripts create a list of n integers, then repeatedly pop off the
> first element until the list is empty. The first uses a linked list
> (where each element is a Python list - I guess this is faster than an
> object although I haven't timed it) the second a python list. Popping
> off the first element is the worst case for a python list since it is
> implemented as an array of pointers and n-1 pointers have to be copied
> for each operation and the best case for a linked list.
>
> Still, on my laptop with CPython 3.8, the builtin list is faster for
> lists of less than 100 elements, they are about on par between 100 and
> 1000 elements and only for longer lists does the linked list become
> faster.
>
> With Pypy 6.0 (yes, I know it's old), the linked list seems to be always
> a bit faster although the difference is very small for lists shorter
> than 100 elements - GraalVM is probably closer to PyPy than to CPython
> in its performance characteristics, but the point is that the dynamic
> nature of Python makes some seemingly cheap operations much more costly
> than one would expect - a good optimizing compiler may be able to detect
> that all that is not needed in a specific case and produce
> straightforward code. But unlike for JavaScript (which has a very
> similar problem) no company has spent millions of dollars on an
> optimizing JIT compiler for Python yet.
> hp
>
> --
> _ | Peter J. Holzer | Story must make more sense than reality.
> |_|_) | |
> | | | h...@hjp.at | -- Charles Stross, "Creative writing
> __/ | http://www.hjp.at/ | challenge!"

Woa! PyPy is faster! Faster than GraalVM. Now I get
for my usual benchmark, figures in milliseconds:

Standard GraalVM PyPy
170'996 28'523 9'755

Not bad. Only like 2x times slower than node.exe.
Now imaging I can realize the ast.parse() and

compile() idea as well! (Made an experiment
today, testing some corner with evaluation)

BTW: Here the full results. Was using:
pypy3.7-v7.3.5-win64\pypy3.exe

Test Standard GraalVM PyPy
nrev 20'389 3'611 1'254
crypt 17'103 3'248 960
deriv 20'808 3'111 1'250
poly 17'518 3'045 1'149
qsort 20'191 3'243 1'127
tictac 13'761 2'469 783
queens 17'691 3'242 1'024
query 6'161 1'155 313
mtak 17'209 2'300 907
perfect 20'165 3'099 988
calc N/A N/A N/A
Total 170'996 28'523 9'755

Mostowski Collapse schrieb am Montag, 20. September 2021 um 23:53:32 UTC+2:
> ls.pop() is probably also, not only attribute access. Just check
> out the figures here, its not pop() but append():
>
> >>> %%timeit
> out = []
> for x in range(10**6):
> out.append(x**2)
> ...
> 1 loops, best of 3: 510 ms per loop
>
> >>> %%timeit
> out = [];append=out.append
> for x in range(10**6):
> append(x**2)
> ...
> 1 loops, best of 3: 467 ms per loop
>
> https://stackoverflow.com/a/30097520/502187
> Peter J. Holzer schrieb am Montag, 20. September 2021 um 21:51:59 UTC+2:
> > On 2021-09-20 05:08:55 -0700, Mostowski Collapse wrote:
> > > 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.
> > That's the problem. You think that pointer swizzling is fast because you
> > are used to languages where this is compiled into a few machine
> > instructions. (Even there it depends a lot on locality: A random memory
> > access can take hundreds of clock cycles.)
> >
> > In Python something like «a.next = b.next» normally does a dict lookup
> > on both objects, plus it also has to check for the existence of special
> > methods on both objects. You can probably copy quite a few contiguous
> > bytes while this is happening.
> >
> > Here is a simple demo:
> >
> > ------------------------------------------------------------------------
> > #!/usr/bin/python3
> >
> > import time
> >
> > n = 10000
> >
> > def build_linked_list(n):
> > head = [None, None]
> > tail = head
> > for i in range(n):
> > tail[1] = [i, None]
> > tail = tail[1]
> > return head
> >
> > def empty_list(ls):
> > while ls[1]:
> > ls[1] = ls[1][1]
> >
> > t0 = time.monotonic()
> > ll = build_linked_list(n)
> > t1 = time.monotonic()
> > empty_list(ll)
> > t2 = time.monotonic()
> > print(n, t1 - t0, t2 - t1)
> > ------------------------------------------------------------------------
> > #!/usr/bin/python3
> >
> > import time
> >
> > n = 10000
> >
> > def build_list(n):
> > return list(range(n))
> >
> > def empty_list(ls):
> > while ls:
> > ls.pop(0)
> >
> > t0 = time.monotonic()
> > ll = build_list(n)
> > t1 = time.monotonic()
> > empty_list(ll)
> > t2 = time.monotonic()
> > print(n, t1 - t0, t2 - t1)
> > ------------------------------------------------------------------------
> >
> > Both scripts create a list of n integers, then repeatedly pop off the
> > first element until the list is empty. The first uses a linked list
> > (where each element is a Python list - I guess this is faster than an
> > object although I haven't timed it) the second a python list. Popping
> > off the first element is the worst case for a python list since it is
> > implemented as an array of pointers and n-1 pointers have to be copied
> > for each operation and the best case for a linked list.
> >
> > Still, on my laptop with CPython 3.8, the builtin list is faster for
> > lists of less than 100 elements, they are about on par between 100 and
> > 1000 elements and only for longer lists does the linked list become
> > faster.
> >
> > With Pypy 6.0 (yes, I know it's old), the linked list seems to be always
> > a bit faster although the difference is very small for lists shorter
> > than 100 elements - GraalVM is probably closer to PyPy than to CPython
> > in its performance characteristics, but the point is that the dynamic
> > nature of Python makes some seemingly cheap operations much more costly
> > than one would expect - a good optimizing compiler may be able to detect
> > that all that is not needed in a specific case and produce
> > straightforward code. But unlike for JavaScript (which has a very
> > similar problem) no company has spent millions of dollars on an
> > optimizing JIT compiler for Python yet.
> > hp
> >
> > --
> > _ | Peter J. Holzer | Story must make more sense than reality.
> > |_|_) | |
> > | | | h...@hjp.at | -- Charles Stross, "Creative writing
> > __/ | http://www.hjp.at/ | challenge!"

The Java vs Python articles are utterly outdated.
For example they think a difference between Java
and Python is that Java is interface centric.

The articles are from 2004. But the ABC PEP is from 2007:

https://www.python.org/dev/peps/pep-3119/

https://www.python.org/dev/peps/pep-3141/

You find also write-ups like:

https://realpython.com/python-interface/

Hope this helps!

Mark Lawrence wrote:
> On Monday, September 20, 2021 at 1:52:18 PM UTC+1, Mostowski Collapse wrote:
>> Now I am expecting somebody telling me I should not
>> program Java style in Python. So I wonder what would have
>> happened if I would tell you I am FORTRAN programmer.
>>
>
> http://dirtsimple.org/2004/12/python-is-not-java.html
> http://dirtsimple.org/2004/12/java-is-not-python-either.html
>

On 21/09/21 12:16 am, Mostowski Collapse wrote:
> This is needed to adjust the choice points.
> If you have an array instead of a linked
> listed as I have now, you would need
> to adjust array indexes instead pointers
> into linked list elements.

All right, so you don't just have a list, you have a more complicated
data structure. The way you're doing it is probably reasonable, and
good enough given it's not a significant part of the running time.

--
Greg

A nice project could now be to redo this one,
see how the prover would perform:

FLiP, a Logical Framework in Python
http://staff.washington.edu/jon/flip/www/index.html

The prover is listed here:

Proof checkers - Joseph Vidal-Rosset
https://www.vidal-rosset.net/proof_checkers.html

Ha Ha, the prover was just right in front of my nose
all the time. But before venturing into such a quest,
need to add occurs check to the Dogelog runtime.

I had some very good dynamic optimization for
occurs check in Jekejeke Prolog, but for Dogelog
runtime everything is new, need to figure out what

optimizations could be applied there. There is a ticket
for occurs check already on GitHub:

Bring occurs check to Dogelog runtime #143
https://github.com/jburse/dogelog-moon/issues/143

Greg Ewing schrieb am Dienstag, 21. September 2021 um 01:34:38 UTC+2:
> On 21/09/21 12:16 am, Mostowski Collapse wrote:
> > This is needed to adjust the choice points.
> > If you have an array instead of a linked
> > listed as I have now, you would need
> > to adjust array indexes instead pointers
> > into linked list elements.
> All right, so you don't just have a list, you have a more complicated
> data structure. The way you're doing it is probably reasonable, and
> good enough given it's not a significant part of the running time.
>
> --
> Greg

That I get censored on Python pipermail, is possibly an
out burst of taking Python too literal, like here:

Monty Python - She's a witch!
https://www.youtube.com/watch?v=zrzMhU_4m-g

But we can turn this into a FLiP, a Logical Framework in Python exercise:

"There are ways of telling whether she's a witch."
"What do you do with witches?" "Burn them!"
Ax.(Witch(x) -> Burn(x)) (1) Given
"Why do witches burn?" "'Cause they're made of wood!"
Ax.(Wood(x) -> Witch(x)) (2) Given
"How do we tell if she's made of wood?" "Does wood sink in water?" "It floats!"
Ax.(Floats(x) -> Wood(x)) (3) Given
"What also floats in water?" "A duck!"
Floats(duck) (4) Given
"Exactly! So, logically ..."
"If she weights the same as a duck, she's made of wood!"
Ax.Ay.((Floats(x) & (weight(x) = weight(y))) -> Floats(y)) (5) Given
"We shall use my largest scales. ... Remove the supports!"
weight(duck) = weight(girl) (6) Given
Ay.((Floats(duck) & (weight(duck) = weight(y))) -> Floats(y)) (7) A-Elimination (5)
(Floats(duck) & (weight(duck) = weight(girl))) -> Floats(girl) (8) A-Elimination (7)
Floats(duck) & (weight(duck) = weight(girl)) (9) And-Introduction (4) (6)
Floats(girl) (10) Implication-Elimination (Modus Ponens) (8) (9)
Floats(girl) -> Wood(girl) (11) A-Elimination (3)
Wood(girl) (12) Implication-Elimination (Modus Ponens) (11) (10)
"A witch! A witch!"
Wood(girl) -> Witch(girl) (13) A-Elimination (2)
Witch(girl) (14) Implication-Elimination (Modus Ponens) (13) (12)
"Burn her! Burn!"
Witch(girl) -> Burn(girl) (15) A-Elimination (1)
Burn(girl) (16) Implication-Elimination (Modus Ponens) (15) (14)
http://staff.washington.edu/jon/flip/www/witch.html

Mostowski Collapse schrieb am Donnerstag, 23. September 2021 um 18:18:30 UTC+2:
> A nice project could now be to redo this one,
> see how the prover would perform:
>
> FLiP, a Logical Framework in Python
> http://staff.washington.edu/jon/flip/www/index.html
>
> The prover is listed here:
>
> Proof checkers - Joseph Vidal-Rosset
> https://www.vidal-rosset.net/proof_checkers.html
>
> Ha Ha, the prover was just right in front of my nose
> all the time. But before venturing into such a quest,
> need to add occurs check to the Dogelog runtime.
>
> I had some very good dynamic optimization for
> occurs check in Jekejeke Prolog, but for Dogelog
> runtime everything is new, need to figure out what
>
> optimizations could be applied there. There is a ticket
> for occurs check already on GitHub:
>
> Bring occurs check to Dogelog runtime #143
> https://github.com/jburse/dogelog-moon/issues/143
> Greg Ewing schrieb am Dienstag, 21. September 2021 um 01:34:38 UTC+2:
> > On 21/09/21 12:16 am, Mostowski Collapse wrote:
> > > This is needed to adjust the choice points.
> > > If you have an array instead of a linked
> > > listed as I have now, you would need
> > > to adjust array indexes instead pointers
> > > into linked list elements.
> > All right, so you don't just have a list, you have a more complicated
> > data structure. The way you're doing it is probably reasonable, and
> > good enough given it's not a significant part of the running time.
> >
> > --
> > Greg

Dogelogs new signature sound:

Led Zeppelin Immigrant song (Racing Beat remix)
https://www.youtube.com/watch?v=oryBBkmIVCc

LoL