如何检测Python中的无限循环

Question

我正在学习Python 3，并且在做一个练习，要求写一个Python程序来模拟或读取一个BASIC程序作为输入。我现在卡在了写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是一个字符串列表，里面包含了BASIC程序（字符串的形式像是5 GOTO 30，10 GOTO 20等等）。

T是prog[location]中指向的目标字符串。

如果这个BASIC程序有无限循环，那么我的Python程序也会陷入无限循环。我知道如果有任何一行被访问了两次，那就说明它永远在循环，我的程序应该返回“无限循环”。

教程助手给的一个提示是：“初始化一个列表visited = [False] * len(prog)，当访问到prog[i]时，把visited[i]改为True。每次循环时，visited[]中的一个值会更新。想想如何改变列表中的一个值。然后再想想如何确定visited[]中哪个值需要改变。”

所以我现在卡在这一部分。我该如何跟踪prog中哪些字符串已经被访问过或循环过呢？

Answer 1

这是我根据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)

Answer 2

我不知道在Python中有没有自动检测无限循环的方法，但你可以通过分而治之的方法，逐个测试函数，找到出问题的函数或代码块，然后再进行调试。

如果你的Python程序有输出数据，但你却从来没有看到这些输出，这通常是一个很好的迹象，说明你可能有一个无限循环。你可以在交互式环境中测试所有函数，那个“没有返回”到命令提示符的函数，很可能就是问题所在。

你可以在某个调试变量下写输出信息，当一切正常时再关闭这个输出。这个变量可以是Python类的成员变量，这样你的代码随时都能访问，或者你可以使用一个模块级的变量，比如 Debug=1，通过不同的调试级别来打印不同量的调试信息，比如1打印一点，2多一点，3再多一点，4则非常详细。

举个例子，如果你在一个可疑的函数中打印了一个循环计数器的值，那么最终这个计数器会一直打印，超过你用来测试的数据（测试记录）的数量。

Answer 3

我不太同意说访问同一行两次就证明了有无限循环。可以看看问题下面的评论。不过我可以回答实际的问题。

这里有个提示：

教程助手给出的提示是：“初始化一个列表 visited = [False] * len(prog)，当访问 prog[i] 时，把 visited[i] 改为 True。每次循环时，visited[] 中的一个值会更新。想想你是如何在列表中改变一个值的。然后再想想你是如何确定 visited[] 中哪个值需要改变的。”

这就是说你应该有两个列表，一个是程序内容，另一个是用来标记的真假值。第二个列表叫做 visited，最开始里面全是 False。

Python 代码就像提示中说的那样：

visited = [False] * len(prog)

这里用到了 * 列表运算符，也就是“列表重复”，可以把一个长度为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))

现在我们有了一个单一的列表，每个项目都是一段 BASIC 代码和一个 visited 标志。

附注：上面的代码展示了一个明确的 for 循环，反复使用 .append() 来添加到列表中。一个有经验的 Python 开发者可能会用“列表推导式”来代替，但我想让这个过程尽可能简单易懂。

这是列表推导式。现在如果看起来有点奇怪也没关系；你的课程最终会教你这个的。

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