如何在python中检测无限循环

Question

我正在学习Python 3，并且正在进行一个练习，该练习要求编写一个Python程序，该程序模拟/读取一个基本程序作为输入。我一直在写Python程序中应该检测无限循环的部分。这是我目前掌握的代码：

def execute(prog):
   while True:
      location = 0
      if prog[location] == len(prog) - 1:
         break
         return "success"
      getT = prog[location].split()
      T = len(getT) - 1
      location = findLine(prog, T)
   visited = [False] * len(prog)

这里，prog是包含基本程序的字符串列表（字符串的形式是5 GOTO 30、10 GOTO 20等）。

T是prog[位置]中指示的目标字符串。

如果基本程序有一个无限循环，那么我的Python程序将有一个无限循环。我知道如果任何一行被访问两次，那么它将永远循环，我的程序将返回“无限循环”。

教程助手给出的提示是“初始化访问的列表=[False]*len（prog），并在访问prog[i]时将visited[i]更改为True。每次通过循环，都会更新visited[]中的一个值。考虑如何更改列表中的单个值。然后考虑如何确定访问的[]中的哪个值需要更改。”

所以这就是我一直坚持的部分。如何跟踪prog中的哪些字符串已被访问/循环？

Answer 1

我知道Python中没有自动的无限循环检测方法，但是通过使用分而治之的方法和测试单个函数，您可以找到有问题的函数或代码块，然后继续进行调试。

如果Python程序输出数据，但您从未看到该输出，那么这是一个很好的指示器，表示您有一个无限循环。您可以在repl中测试所有函数，而“不返回”的函数[返回到命令提示符]很可能是可疑的。

您可以在某种调试变量下编写输出，以便在一切正常时关闭。这可能是Python类的一个成员变量，您的代码在任何时候都必须访问它，或者您可以有一个模块范围的变量，比如Debug=1，并使用调试级别打印不同数量的调试信息，比如1一点、2点、3点、甚至更多和4点详细信息。

例如，如果您在可疑函数中打印循环计数器的值，那么最终该循环计数器将保持打印远远超出您用于测试的数据（测试记录）的计数。

Answer 2

我不确定我是否同意两次访问一条线证明了一个无限循环。请参阅问题下面的评论。但我能回答实际的问题。

提示如下：

A hint given by the tutorial assistant says "initialize a list visited = [False] * len(prog) and change visited[i] to True when prog[i] is visited. Each time through the loop, one value updates in visited[]. Think about how you change a single value in a list. Then think about how you identify which value in visited[] needs to change."

这意味着您应该有两个列表，一个包含程序，一个包含true/false标志。第二个名为visited，最初包含False值。

Python代码就像提示所说的：

visited = [False] * len(prog)

这使用*list操作符“list repetition”来重复length-1列表并生成一个更长的新列表。

将visited[i]更改为True很简单：

visited[i] = True

然后你可以这样做：

if visited[i]:
    print("We have already visited line {}".format(i))
    print("Infinite loop?  Exiting.")
    sys.exit(1)

注意，我们只是通过简单地说if visited[i]:来测试True值

我们也可以编写if visited[i] == True:，但是较短的格式就足够了，而且在Python社区中是很常见的。这里记录了这个习惯用法和其他习惯用法：http://python.net/~goodger/projects/pycon/2007/idiomatic/handout.html

对于一个这么小的程序来说，保留两个这样的列表并不算太坏。对于更大更复杂的程序，我更喜欢把所有东西放在一个地方。这将使用一个你可能还没学会的“类”。像这样的：

class ProgramCode(object):
    def __init__(self, statement):
        self.code = statement
        self.visited = False

prog = []
with open(input_basic_program_file, "rt") as f:
    for line in f:
        prog.append(ProgramCode(line))

现在，我们没有两个列表，而是有一个列表，其中每个项都是一些基本代码和一个visited标志。

p.S.上面显示了一个显式的for循环，它反复使用.append()来添加到列表中。一个有经验的Python开发人员可能会使用“列表理解”来代替，但我希望尽可能容易地理解它。

这是对列表的理解。别担心现在看起来有点怪，你的课最终会教给你的。

with open(input_basic_program_file, "rt") as f:
    prog = [ProgramCode(line) for line in f]

Answer 3

下面是我用J.Carlos p.的部分答案和steveha给出的提示以及指令给出的提示得出的一个组合：

def execute(prog):
   location = 0
   visited = [False] * len(prog)
   while True:
      if location==len(prog)-1: 
         return "success" 
      findT = prog[location].split()
      T = findT[- 1]
      if visited[location]:
         return "infinite loop"
      visited[location] = True
      location = findLine(prog, T)