Generate Popular Tags for instagram or facebook
Before we proceed let me make it clear we are not scraping tags from any website. We will "Generate" them using simple code in python. So, How does it work? First, I have collected all popular tags and saved it in a text file as list. [Read More] https://pysnakeblog.blogspot.com/2021/09/generate-popular-tags-for-instagram-or.html -- https://mail.python.org/mailman/listinfo/python-list
Re: Explaining exec(globals, separate_locals)
On 9/20/21, Terry Reedy wrote: > > "If exec gets two separate objects as globals and locals, the code will > be executed as if it were embedded in a class definition." Note that, unlike exec(), the body of a class definition can modify closure variables in nonlocal function scopes. For example: >>> def f(): ... x = 'spam' ... class C: ... nonlocal x ... x = 'eggs' ... return x ... >>> f() 'eggs' -- https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
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 = 1 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 = 1 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!" signature.asc Description: PGP signature -- https://mail.python.org/mailman/listinfo/python-list
Explaining exec(globals, separate_locals)
The second paragraph of the current exec entry https://docs.python.org/3.11/library/functions.html#exec ends with a sentence I wrote. "If exec gets two separate objects as globals and locals, the code will be executed as if it were embedded in a class definition." Would the following would be clearer? "If exec gets two separate objects as globals and locals, the code will be executed in two namespaces, the same as is done with the suite of a class statements." In either case, does the following help even more? "(The difference is that the locals for exec is not passed to type() to become a class dict.)" I am asking because the current sentence engenders questions. Today I got a private email with "This behavior seems really peculiar to me, and I would love to know if you know about why this behavior was chosen to be as it is." The answer is that the choice is made by the user by what the user passes. Top level code is executed in one namespace serving as both globals and locals. Class definition code is executed in two separate namespaces serving the two role. The populated local namespace is then passed to type() to become the __dict__ of the resulting class. An interpreter written in Python could use exec for the two cases. IDLE, for instance, uses exec, with *one* namespace, to execute user code as toplevel code. The third type of code is function code, which executes in 2 *or more* namespaces, with peculiar locals behavior, and with 'return', 'yield', and 'nonlocal' valid. It would make no sense to treat the code passed to exec as a function suite. -- Terry Jan Reedy -- https://mail.python.org/mailman/listinfo/python-list
Inheriting from str
Hello
class NewStr(str):
def __init__(self, s):
self.l = len(s)
Normaly str is an immutable type so it can't be modified
after creation with __new__
But the previous code is working well
obj = NewStr("qwerty")
obj.l
6
I don't understand why it's working ?
(python 3.9)
--
https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
On Tue, Sep 21, 2021 at 3:58 AM 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 ] > > 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 100 > 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
On Tue, Sep 21, 2021 at 3:51 AM Mostowski Collapse 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
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 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
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
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 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: Inheriting from str
On 2021-09-20, ast wrote:
> Hello
>
> class NewStr(str):
> def __init__(self, s):
> self.l = len(s)
>
> Normaly str is an immutable type so it can't be modified
> after creation with __new__
>
> But the previous code is working well
>
> obj = NewStr("qwerty")
> obj.l
> 6
>
> I don't understand why it's working ?
The string itself is immutable. If it's a subclass then it may have
attributes that are not immutable:
>>> s = 'hello'
>>> s.jam = 3
Traceback (most recent call last):
File "", line 1, in
AttributeError: 'str' object has no attribute 'jam'
>>> class foo(str): pass
...
>>> s = foo('hello')
>>> s.jam = 3
>>> s.jam
3
There's a lot of places in Python where you can break standard
assumptions with sufficiently evil or badly-written classes.
e.g.:
>>> class intt(int):
... def __add__(self, other):
... return int(self) + int(other) * 2
...
>>> a = intt(2)
>>> b = intt(3)
>>> a + b
8
>>> b + a
7
--
https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
In general the algorithm I am using is from a paper by Matts Carlson from SICStus Prolog. Its this paper here: Garbage Collection for Prolog Based on WAM January 1986 Karen Appleby, Mats Carlsson, Seif Haridi, Dan Sahlin https://www.researchgate.net/publication/279463524 But since you guys are so facinated with the Prolog garbage collection aspect, which is not the locus where you can do a lot of optimizations, feel free to investigate and come up with a solution. It will not change the performance of Dogelog runtime, but it could be an academic experiment neverthless. There is nothing wrong with the simgle linked list as it stands, since it has O(n) sweep_trail(). It uses a litte more storage than an array would do. Mostowski Collapse wrote: What would be maybe possible, is to scan the trail from the other side, and use a first pass to determine the new size, and use a second pass to fill a new array with the remaining elments. This would be two times O(n), so it would be linear and not quadratic O(n^2) as when you scan from the top and poke holes. But then something else doesn't work so easily. Namely: def adjust_mark(temp): while temp is not None: if (temp.flags & MASK_VAR_MARK) != 0: return temp else: temp = temp.tail return temp https://github.com/jburse/dogelog-moon/blob/main/devel/runtimepy/drawer/machine.py#L151 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. I havent come up with an array solution yet for the trail, since I dont see any utility in investing too much time with the Prolog garbage collection of Dogelog runtime. It is only a small share of the execution time: 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. 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 ] 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 100 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 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
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
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 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
This strategy works if you use failure driven loops. It doesn't work you program recursive loops that go on forever. Like Erlang processes. foo(X) :- bar(X,Y), foo(Y). Typically Y is a fresh variable. A good Prolog system with good Garbage Collection can run such a process for days and months. If you don't clean up the trail, you exhaust the memory after a few minutes or seconds. Greg Ewing schrieb: On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse wrote: On the other hand if I would use the trigger from Python, I possibly would need a double linked list, to remove an element. Here's another idea: Put weak references in the trail, but don't bother with the scanning -- just skip over dead ones during backtracking. Seems to me you would be doing about the same amount of work either way, just doing it at different times. -- https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
What would be maybe possible, is to scan the trail from the other side, and use a first pass to determine the new size, and use a second pass to fill a new array with the remaining elments. This would be two times O(n), so it would be linear and not quadratic O(n^2) as when you scan from the top and poke holes. But then something else doesn't work so easily. Namely: def adjust_mark(temp): while temp is not None: if (temp.flags & MASK_VAR_MARK) != 0: return temp else: temp = temp.tail return temp https://github.com/jburse/dogelog-moon/blob/main/devel/runtimepy/drawer/machine.py#L151 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. I havent come up with an array solution yet for the trail, since I dont see any utility in investing too much time with the Prolog garbage collection of Dogelog runtime. It is only a small share of the execution time: 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. 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 ] 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 100 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 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
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
Please be patient. A big problem with development can be
burnout. So I am trying to slow down things at the moment.
The ideas are easy to sketch, but implementation can take
weeks. Here is the idea again in a nutshell: use ast.parse()
and compile(). Or build directly an AST, not using the string
detour as in ast.parse(). How long will it take to have a
working solution? 11 years ago there was:
Pyrolog: Prolog written in Python using PyPy's RPython tool chain
https://www.reddit.com/r/prolog/comments/fbuz1/pyrolog_prolog_written_in_python_using_pypys/
RPython is a framework for implementing interpreters and virtual
machines for programming languages, especially dynamic languages.
https://rpython.readthedocs.io/en/latest/faq.html
Currently I am not planning to use RPython, want to to use
standard Python AST and compile(). Might have a look at
RPython or similar stuff later.
Mostowski Collapse schrieb am Sonntag, 19. September 2021 um 22:02:41 UTC+2:
> Also I nowhere wrote that I would use doubly-linked list or
> a set of objects. The trail is neither, its a single linked list. I
> also refer directly to objects, I do not need the trail to refer
>
> to objects. The Prolog trail is only a logbook. The Prolog trail
> has similarity to a database log:
>
> transaction journal, database log, binary log or audit **trail**
> https://en.wikipedia.org/wiki/Transaction_log
>
> Do you say Python should not be used to implement
> such things? In my opinion, Python has a high potential
> to implement Prolog, because it has also ast.parse()
>
> and compile(). But I do not yet have a showcase that uses
> these features of Python to compile Prolog. I dont work 24/7
> and I cannot clone myself. Currently the Prolog code is interpreted.
>
> I have a prototype where Prolog code is compiled into JavaScript,
> but I did not yet try this approach with Python. Here you see how
> JavaScript closures are generated, a first prototype:
>
> const alt4 = make_defined([new Clause(1, [0, 0], function(
> display, actual, cont) {return(new Compound(".", [new Compound(
> "==", [deref(actual.args[0]), "end_of_file"]), new Compound(
> ".", [new Compound("$CUT", [deref(display[0])]), cont
> ])]))}, 0, undefined), new Clause(1, [0, 0], function(
> display, actual, cont) {return(new Compound(".", [new Compound(
> "expand_include", [deref(actual.args[0]), deref(actual.args[1]
> ), display[0] = new Variable()]), new Compound(".",
> [new Compound("handle_term", [deref(display[0])]), new Compound(
> ".", ["fail", cont])])]))}, -1, undefined)]);
>
> add("next_term", 1, new Clause(2, [0], function(display, actual,
> cont) {return(new Compound(".", [new Compound("read_term",
> [deref(actual.args[0]), display[0] = new Variable(),
> new Compound(".", [new Compound("variable_names", [
> display[1] = new Variable()]), "[]"])]), new Compound(
> ".", [new Compound(alt4, [deref(display[0]), deref(
> display[1])]), cont])]))}, -1, undefined));
>
> https://github.com/jburse/dogelog-moon/issues/184
>
> Will do the same for Python in the next weeks. Then later this approach
> will be combined with a few planned optimizations. So far got a 25%
> speed increase for JavaScript with this new compilation scheme, but
>
> there is no official release out yet, that features this approach. And
> there should be much more in it, also for Python.
> Mostowski Collapse schrieb am Sonntag, 19. September 2021 um 21:46:20 UTC+2:
> > 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.
> >
> > Chris Angelico schrieb:
> > > On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse
> > > wrote:
> > >>
> > >> 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.
> > >>
> > >
> > > I don't know. I don't understand your code well enough to offer advice
> > > like that, because *your c
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
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 100 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 > > 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...@hjp.at | -- Charles Stross, "Creative writing > __/ | http://www.hjp.at/ | challenge!" -- https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
Also I nowhere wrote that I would use doubly-linked list or
a set of objects. The trail is neither, its a single linked list. I
also refer directly to objects, I do not need the trail to refer
to objects. The Prolog trail is only a logbook. The Prolog trail
has similarity to a database log:
transaction journal, database log, binary log or audit **trail**
https://en.wikipedia.org/wiki/Transaction_log
Do you say Python should not be used to implement
such things? In my opinion, Python has a high potential
to implement Prolog, because it has also ast.parse()
and compile(). But I do not yet have a showcase that uses
these features of Python to compile Prolog. I dont work 24/7
and I cannot clone myself. Currently the Prolog code is interpreted.
I have a prototype where Prolog code is compiled into JavaScript,
but I did not yet try this approach with Python. Here you see how
JavaScript closures are generated, a first prototype:
const alt4 = make_defined([new Clause(1, [0, 0], function(
display, actual, cont) {return(new Compound(".", [new Compound(
"==", [deref(actual.args[0]), "end_of_file"]), new Compound(
".", [new Compound("$CUT", [deref(display[0])]), cont
])]))}, 0, undefined), new Clause(1, [0, 0], function(
display, actual, cont) {return(new Compound(".", [new Compound(
"expand_include", [deref(actual.args[0]), deref(actual.args[1]
), display[0] = new Variable()]), new Compound(".",
[new Compound("handle_term", [deref(display[0])]), new Compound(
".", ["fail", cont])])]))}, -1, undefined)]);
add("next_term", 1, new Clause(2, [0], function(display, actual,
cont) {return(new Compound(".", [new Compound("read_term",
[deref(actual.args[0]), display[0] = new Variable(),
new Compound(".", [new Compound("variable_names", [
display[1] = new Variable()]), "[]"])]), new Compound(
".", [new Compound(alt4, [deref(display[0]), deref(
display[1])]), cont])]))}, -1, undefined));
https://github.com/jburse/dogelog-moon/issues/184
Will do the same for Python in the next weeks. Then later this approach
will be combined with a few planned optimizations. So far got a 25%
speed increase for JavaScript with this new compilation scheme, but
there is no official release out yet, that features this approach. And
there should be much more in it, also for Python.
Mostowski Collapse schrieb am Sonntag, 19. September 2021 um 21:46:20 UTC+2:
> 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.
>
> Chris Angelico schrieb:
> > On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse
> > wrote:
> >>
> >> 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.
> >>
> >
> > 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. Let Python be Python, don't try to
> > build your own language on top of it.
> >
> > ChrisA
> >
--
https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
But I dont see any utility in investing too much time with the Prolog garbage collection of Dogelog runtime. It is only a small share of the execution time: 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. > > The "gc" timing measures Prolog garbage > collection. So you get the following percentage > of time spent in Prolog garbage collection: > > Standard Python: 94 / 3865 = 2.4% > > GraalVM Python: 14 / 695 = 2.0% If you spare these 2-3% it will not speed-up Dogelog runtime. The Prolog garbage collection is there to allow Erlang processes. And its also there to allow more Prolog search without exhausting the memory. But it cost you only 2-3% judging from the Fibonnacci Numbers example. Need to check with other examples whether its higher. But since the ratio between Garbage and non-Garbage is usually high, and non-Garbage is easily identified, and the Garbage is also easily removed, the time will possibly not exceed much more than the same 2-3% for other examples. So in conclusion I am least worried about the Prolog garbage collection. You guys are only worried because its something new. But its nothing that does any harm and costs a lot, it only does good and is very cheap in terms of extra runtime effort. Mostowski Collapse schrieb am Montag, 20. September 2021 um 08:44:49 UTC+2: > This strategy works if you use failure driven loops. > It doesn't work you program recursive loops that go > on forever. Like Erlang processes. > > foo(X) :- > bar(X,Y), foo(Y). > > Typically Y is a fresh variable. A good Prolog system > with good Garbage Collection can run such a process > for days and months. > > If you don't clean up the trail, you exhaust the > memory after a few minutes or seconds. > > Greg Ewing schrieb: > >> On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse > >> wrote: > >>> > >>> On the other hand if I would use the trigger > >>> from Python, I possibly would need a double linked > >>> list, to remove an element. > > > > Here's another idea: Put weak references in the trail, but > > don't bother with the scanning -- just skip over dead ones > > during backtracking. > > > > Seems to me you would be doing about the same amount of > > work either way, just doing it at different times. > > -- https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
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. Chris Angelico schrieb: On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse wrote: 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. 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. Let Python be Python, don't try to build your own language on top of it. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse wrote: On the other hand if I would use the trigger from Python, I possibly would need a double linked list, to remove an element. Here's another idea: Put weak references in the trail, but don't bother with the scanning -- just skip over dead ones during backtracking. Seems to me you would be doing about the same amount of work either way, just doing it at different times. -- Greg -- https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
On Mon, Sep 20, 2021 at 9:50 PM Peter J. Holzer 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: ANN: Dogelog Runtime, Prolog to the Moon (2021)
On 2021-09-20 04:33:39 +1000, Chris Angelico wrote: > On Mon, Sep 20, 2021 at 3:19 AM Mostowski Collapse > 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...@hjp.at |-- Charles Stross, "Creative writing __/ | http://www.hjp.at/ | challenge!" signature.asc Description: PGP signature -- https://mail.python.org/mailman/listinfo/python-list
