Python is (mostly) made of syntactic sugar

Posted Aug 30, 2023 17:48 UTC (Wed) by NYKevin (subscriber, #129325)
In reply to: Python is (mostly) made of syntactic sugar by mb
Parent article: Python is (mostly) made of syntactic sugar

It's not that easy.

When we speak of "limited" memory in the context of Turing completeness, we usually mean limited *heap* memory. Heap memory is only strictly bounded by two things:

1. The amount of physical memory (plus swap) in the system.
2. The size of the virtual address space.

In practice, we don't see this as a "real" limit in the context of Turing completeness, because (1) can be remedied by adding more RAM (or swap), and (2) is huge on 64-bit systems.

However, the Python recursion limit is bounded by the size of the C stack.[1] If you try to increase it beyond what the stack size can handle, it'll overflow and cause UB. To some extent, it is possible to increase the size of the stack at runtime, but most modern operating systems are designed under the assumption that your stack size is no larger than (say) several megabytes or so. If you want to use a multi-gigabyte stack, I imagine that at least some operating systems will let you do that, but I find it hard to believe that they will perform gracefully under those conditions.

The other problem, of course, is that Python does not offer a standard facility for increasing the size of its C stack. You have to go monkeying around with ctypes or something and call into an OS-specific C API, so you can argue that "make a bigger C stack" is not within the competency of the language proper. In this interpretation, the Python recursion limit can only be safely adjusted up to whatever the default stack size will accommodate, and then it's not a matter of "limited memory" at all (the default stack size is a fixed value that does not depend on the amount of physical memory installed).

[1]: https://docs.python.org/3/library/sys.html#sys.setrecursi...

Python is (mostly) made of syntactic sugar

Posted Aug 30, 2023 18:48 UTC (Wed) by mb (subscriber, #50428) [Link] (3 responses)

What's your point? I know how Python and C work w.r.t. the stack.

It's been said, that recursive Python cannot be turing complete, because recursion is limited.
But that would mean that no recursive language could ever be turing complete, because they all hit a limit at some point.
Therefore, I don't consider the original statement as valid.

Python is (mostly) made of syntactic sugar

Posted Aug 30, 2023 19:18 UTC (Wed) by NYKevin (subscriber, #129325) [Link] (2 responses)

> But that would mean that no recursive language could ever be turing complete, because they all hit a limit at some point.

Most if not all "recursive" languages (as you call them) do tail call elimination as a mandatory language feature (i.e. the language explicitly specifies that tail calls will not cause stack overflow), which is enough to give you access to the equivalent of an unrestricted while loop. The fact that you can also write non-tail recursion is irrelevant, because you could always rewrite it as tail recursion with a separate stack that is passed as an explicit parameter.

Python, on the other hand, not only does not provide tail call elimination as a language feature, it does not even provide it as an optimization.

Python is (mostly) made of syntactic sugar

Posted Aug 30, 2023 19:48 UTC (Wed) by mb (subscriber, #50428) [Link] (1 responses)

>because you could always rewrite it as tail recursion with a separate stack that is passed as an explicit parameter.

Which will eventually be full, just like the Python call stack.
There's no fundamental difference. It's just an implementation detail.

Python is (mostly) made of syntactic sugar

Posted Aug 30, 2023 19:51 UTC (Wed) by NYKevin (subscriber, #129325) [Link]

The "separate stack" would be a heap-allocated object, so as I already described upthread, its limit is much closer to the "we can just shove more RAM in the computer as needed" model than the "there is a static limit that must not be exceeded" model.