CODEWITHSUNDEEP
pythonpython-3.xinfinite-loop
JCP510
JCP510

Reputation: 31

how can I detect infinite loops in python

I am learning Python 3 and working on an exercise that calls for writing a Python program which simulates/reads a BASIC program as input. I am stuck on writing the part of the Python program that should detect infinite loops. Here is the code I have so far:

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)

Here, prog is a list of strings containing the BASIC program (strings are in the form of 5 GOTO 30, 10 GOTO 20, etc.).

T is the target string indicated in prog[location].

If the BASIC program has an infinite loop, then my Python program will have an infinite loop. I know that if any line is visited twice, then it loops forever, and my program should return "infinite loop".

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."

So this is the part I am stuck on. How do I keep track of which strings in prog have been visited/looped through?

Upvotes: 3

Views: 19690

Answers (3)

Justin C.
Justin C.

Reputation: 11

Here is a combination I came up with using parts of J. Carlos P.'s answer with the hints that steveha gave and using the hint that the instructions gave: 

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)

Upvotes: 1

octopusgrabbus
octopusgrabbus

Reputation: 10695

I know of no automatic way of infinite loop detection in Python, but by using divide and conquer methods and testing individual functions, you can find the offending function or block of code and then proceed to debug further.

If the Python program outputs data, but you never see that output, that's a good indicator you have an infinite loop. You can test all your functions in the repl, and the function that does "not come back" [to the command prompt] is a likely suspect.

You can write output under a debug variable of some sort, to be shut off when everything works. This could be a member variable of a Python class to which your code would have to have access to at any time, or you could have a module-scoped variable like Debug=1 and use debug levels to print varying amounts of debug info, like 1 a little, 2 more, 3, even more, and 4 verbose.

As an example, if you printed the value of a loop counter in a suspected function, then eventually that loop counter would keep printing well beyond the count of data (test records) you were using to test.

Upvotes: 1

steveha
steveha

Reputation: 76745

I'm not sure I agree that visiting a line twice proves an infinite loop. See the comments under the question. But I can answer the actual question.

Here's the hint:

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."

This is saying you should have two lists, one that contains the program, and one that contains true/false flags. The second one is to be named visited and initially contains False values.

The Python code is just like the hint says:

visited = [False] * len(prog)

This uses the * list operator, "list repetition", to repeat a length-1 list and make a new list of a longer length.

To change visited[i] to True is simple:

visited[i] = True

Then you can do something like this:

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

Note that we are testing for the True value by simply saying if visited[i]:

We could also write if visited[i] == True: but the shorter form is sufficient and is customary in the Python community. This and other customary idioms are documented here: http://python.net/~goodger/projects/pycon/2007/idiomatic/handout.html

For a program this small, it's not too bad to keep two lists like this. For larger and complex programs, I prefer to keep everything together in one place. This would use a "class" which you might not have learned yet. Something like this:

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))

Now instead of two lists, we have a single list where each item is a bit of BASIC code and a visited flag.

P.S. The above shows an explicit for loop that repeatedly uses .append() to add to a list. An experienced Python developer would likely use a "list comprehension" instead, but I wanted to make this as easy to follow as possible.

Here's the list comprehension. Don't worry if it looks weird now; your class will teach this to you eventually.

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

Upvotes: 8

Related Questions