lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


If any programming language allows implementing a Turing machine (it is the case of Lua), then there's a demonstrated theorem that says that we cannot prove that program will terminate or not in a finite time and allow a program running on a Turing Machine (Lua, or any language running on existing CPUs) to verify that assertion in a finite time; worse, this problem is NP-complete (meaning that the time to compute the veracity of that assertion takes a non-polynomial time) and this is the kind of problems that a Turing Machine cannot solve about the state of another Turing Machine or about itself.

So all that can be done is to find heuristics that may detect some obvious cases of infinite loops. Or some languages reduce the capabilities of the language so that it is no longer capable of implementing a generic Turing Machine (such languages exist in various niches, notably those concerned by checking the security of systems, and they use their own specific languages for specific classes of problems; classic regular _expression_ engines are good examples of non-Turing machines that even if they can resolve very complex problems, but at least we can assert their validity, i.e. expect a response in a finite time when processing a finite amount of input data, even if that data can be arbitrarily large).

But in general, it's not possible to assert that before running the actual program. The same occurs for time complexity and for space complexity (being able to assert that a program allocating dynamic memory will not claim an infinite amount of memory, or infinite amount of other resources (e.g. storage space, memory space, network bandwidth, extra CPUs on a network grid, or total amount of energy needed to complete, i.e. a total amount of money to spend for it.)

So the only solution is to implement watchdogs, or quotas of allowed resources, on the system running that program, and then make that system interrupt the program taking too much ressources. Another measure is also to implement resource monitors, so that not just a system will interrupt the program automatically, but some human user admininstrating the system can decide what to do and when.

Usually all systems support quotas and will automatically break the program abruptly when the amounts of ressources allocated (including execution time, storage space consume, bandwidth used on networks, energy consumption) is exhausted (that forced interruption may eventually be resumable if the system is capable of producing a snapshot before freezing the program in its state and then stopping it once the snapshot is created; if the storage of the snapshot requires also too much ressources, or requires additional costs notably on a network, there's generally no way to recover as there's no way to create a resumable snapshot).


Le mer. 16 févr. 2022 à 08:30, Flyer31 Test <flyer31@googlemail.com> a écrit :
Hello,
in my C code I want to define some special Lua functions, which should
be only invoked inside a sort of "main function", and these functions
also should NOT be invoiked inside any code blocks if...end, as well
as not in any loops for ...end / while ...end / repeat ... until.

Witth the debug interface and lua_getinfo I can get info about the
function currently active ... so I can restrict the invocation of this
"special function" easily to be called only insde my "main function".

But I did not find an easy way to know, whether any "block"
(if/for/while/do/repeat) is active. Is there a way for my C code to
get this information?