# 15A: Termination Determination

**Source**: https://cscircles.cemc.uwaterloo.ca/15a-basic/
**Parent**: https://cscircles.cemc.uwaterloo.ca/

*Exercises 15A, 15B, and 15C can be completed in any order.*

In this lesson you will complete a long and complex problem that has been broken into parts for you. This lesson also introduces `str.split()`, a useful method for splitting strings: it deletes all of the spaces, and then returns a list of all of the words in the string. The original string is not modified.

Example

Examples of `str.split()`

S = 'This is a string'
words = S.split()
print(words)
print(len(words))
print(words[1])
print(S) # S is not changed
print(' Another example of split '.split())

|  |  |  |
| --- | --- | --- |
|  |  |  |

|  |  |
| --- | --- |
|  | You can call `split()` with special arguments to do more sophisticated splitting, but we don't need this ability below. If you are interested, check the [Python documentation](http://docs.python.org/py3k/library/stdtypes.html#str.split). |

Now we get to the task at hand. The old programming language [BASIC](http://en.wikipedia.org/wiki/BASIC) was famous for its numbered lines and `goto` statements. For this exercise, you will implement a simple version of BASIC with just these features. Specifically, the input to your program will consist of several lines in the format

`«label» goto «target»`

where `«label»` and `«target»` are positive integers. The *label* is like the name or address of the line; *all labels are unique.* The *target* tells you the label of the line to move to next. The last line of the program is `«label» END` indicating that you should stop once you move to this line. Here is a sample BASIC program:

```
5 GOTO 30
10 GOTO 20
20 GOTO 10
30 GOTO 40
40 END
```

When BASIC runs the program, this is what happens. We begin at the first line (with label 5). The line with label 5 has target 30, so next we go to the line with label 30. Then line 30 tells us to go to line 40. Line 40 tells us to END. So, the program terminated successfully.

On the other hand, a BASIC program can also loop forever. Here is an example:

```
10 GOTO 21
21 GOTO 37
37 GOTO 21
40 END
```

The program starts at line 10, but then it loops forever between lines 21 and 37.

**Your task** is to write a Python program, which reads a BASIC program as input. If the program terminates, your program should print `success`. If the program enters an infinite loop, your program should print `infinite loop`. Assume each target equals some valid label and that all labels are unique, so you do not have to do error-checking.

There are several ways you could do this, but in this lesson we have chosen one simple approach that breaks the problem in to 3 sub-tasks. (In lesson 15C you have one large problem and design the sub-tasks yourself.)

## Sub-task 1: Reading the program

To read the program, we need to keep calling `input()`. However, we need to stop calling `input()` once the last line (the one with `END`) is reached, to avoid an `EOFError`.

Coding Exercise: Reading the Program

Write a function `getBASIC()` which takes no arguments, and does the following: it should keep reading lines from input using a while loop; when it reaches the end it should return the whole program in the form of a list of strings. (Hints: about lists and stopping)

You need to create an account and log in to ask a question.

# delete this comment and enter your code here

You may enter input for the program in the box below.

|  |  |  |  |
| --- | --- | --- | --- |
|  |  |  |  |

More actions...
History
Help

## Sub-task 2: Go to it!

Once we have read the program, we need to be able to move from line to line in the program. To accomplish this, we ask you to write the following subroutine.\

Coding Exercise: Go to it!

Define a function `findLine(prog, target)` to perform the following. Assume `prog` is a list of strings containing a BASIC program, like the type generated by `getBASIC()`; assume `target` is a string containing a line number, which is the target of a GOTO statement. The function should return the index `i` (a number between `0` and `len(prog)-1`) such that `prog[i]` is the line whose label equals `target`. Hint \
**Sample input/output:** If you call

```
findLine(['10 GOTO 20','20 END'], '10')
```

then the output should be `0`, since item 0 of the list is the line with label 10.

You need to create an account and log in to ask a question.

# delete this comment and enter your code here

Enter testing statements like `print(myfunction("test argument"))` below.

|  |  |  |  |
| --- | --- | --- | --- |
|  |  |  |  |

More actions...
History
Help

## Sub-task 3: Smart Simulation

In the previous two exercises, we handled the *input routine* and the *searching task*. These will be useful to make writing the main program shorter. However, there is still a major question: how can we actually solve the original problem? The most straightforward way would be to simulate the BASIC program:

- let `prog` be the BASIC program (an array of strings)
- start a counter called `location` at 0, since we begin on the first line of the program
- while True,
  - if `prog[location]` is the END line, return "success" and stop.
  - let `T` be the target string indicated in `prog[location]`
  - let the new value of `location` be `findLine(prog, T)`

But, there is a major problem: this doesn't detect infinite loops, and if the BASIC program has an infinite loop, then the Python program will also loop forever. What we wanted was that the program should print "infinite loop" in this situation. We leave this problem for you to solve; we give a hint below.

Coding Exercise: Smart Simulation

Write a function `execute(prog)` to do the following. Assume `prog` is a list of strings containing the BASIC program, like before. Then, your function should return either "`success`" or "`infinite loop`" depending on whether the program terminates, or loops forever. **Important**: you should assume the procedure `findLine(prog, target)` defined in sub-task 2 is already defined, you do not need to re-write it. Hint

You need to create an account and log in to ask a question.

# here is a broken solution to get you started
def execute(prog):
location = 0
while True:
if location==len(prog)-1: return "success"
#get T from prog[location] via str.split
location = findLine(prog, T)

Enter testing statements like `print(myfunction("test argument"))` below.

|  |  |  |  |
| --- | --- | --- | --- |
|  |  |  |  |

More actions...
History
Reset code to default
Help

## Putting it all together

To test your code as a complete solution, copy and paste your previous solutions into the following template.

Coding Exercise: BASIC Simulator

Put together your BASIC simulator.

You need to create an account and log in to ask a question.

# def getBASIC from subtask 1
# def findLine from subtask 2
# def execute from subtask 3
print(execute(getBASIC()))

You may enter input for the program in the box below.

|  |  |  |  |
| --- | --- | --- | --- |
|  |  |  |  |

More actions...
History
Reset code to default
Help

|  |  |
| --- | --- |
|  | If your programming language is slightly more complicated, then it's *impossible* to write a termination-checking program. This was the earliest important theorem in computer science, proven by [Alan Turing](http://en.wikipedia.org/wiki/Alan_Turing) in the 1930s, and nowadays people refer to the result by saying "the [Halting Problem](http://en.wikipedia.org/wiki/Halting_problem) is undecidable." |