15A: Komt er een einde aan?

Oefeningen 15A, 15B, en 15C kunnen in elke willekeurige volgorde worden doorgewerkt.

In deze les zul je een lang en complexe opgave afmaken dat in delen voor je wordt gepresenteerd. In deze les wordt str.split(), een nuttige methode om een string te splitsen, gepresenteerd, waarbij alle spaties worden verwijderd en waarbij een lijst wordt teruggegeven met alle woorden in de string. De originele string wordt niet aangetast.

Voorbeeld
Voorbeelden van str.split()

Je kunt split() aanroepen met specifieke argumenten om meer geavanceerd te splitsen, maar we hebben deze mogelijkheid hier beneden niet nodig. Wanneer je geïnteresseerd bent, ga dan naar de Python documentie.

We gaan nu naar het eigenlijke probleem. De oude programmeertaal BASIC was beroemd door zijn regels die waren voorzien van een nummer en goto statements. In deze oefening gaat het erom om een sterk vereenvoudigde versie van BASIC te maken dei juist deze eigenschap heeft. In het bijzonder zal de invoer van je programma bestaan uit een aantal regels van de vrom

«label» goto «target»

waarbij «label» en «target» positieve gehele getallen zijn. Het  label functioneert als de naam van een adres van de regel; alle labels zijn uniek. De target geeft aan welke regel vervolgens moet worden uitgevoerd. De laatste regel van het programma is «label» END dat aangeeft dat je meet stoppen zodra je deze regel hebt bereikt. Hier volgt een voorbeeld van een programma in BASIC:

5 GOTO 30
10 GOTO 20
20 GOTO 10
30 GOTO 40
40 END
Als BASIC dit programma uitvoert dan gebeurt het volgende. Begonnen wordt met de eerste regel (die met label 5). De regel met label 5 heeft target 30, dus door naar regel met label 30. Regel 30 zegt om verder te gaan naar regel 40. Regel 40 geeft aan om het programma te stoppen. Het programma komt op een correcte wijze tot een einde.

Het is aan de nadere kant ook mogelijk dat een BASIC programma in oneindig lange loop zit. Hier volgt een voorbeeld:

10 GOTO 21
21 GOTO 37
37 GOTO 21
40 END
Het programma begint op regel 10 maar daarna blijft het in een oneindige lus tussen regel 21 en 37.

Het is jouw taak om een Python programma te schrijven, dat een BASIC programma als input heeft. Wanneer het programma eindigt dan zal het programma success afdrukken. Wanneer het programma in een oneindige loop terecht komt dan dient het programma infinite loop afdrukken. Neem aan dat iedere target wijst naar een bestaand label en dat alle labels uniek zijn, het is dus niet nodig om het BASIC-programma te controleren op fouten.

Er zijn meerdere manieren om dit te doen, maar in deze les hebben we gekozen voor een eenvoudige aanpak, waarbij het programma wordt opgedeeld in 3 sub-taken. (In les 15C krijg je een omvangrijk probleem en moet je de sub-taken zelf ontwerpen.)

Sub-taak 1: Het inlezen van het programma

Om het programma in te lezen dienen we herhaald input() aan te roepen. We dienen echter te stoppen met aanroepen van input() zodra de laatste regel (die met END) wordt bereikt, dit om een EOFError te vermijden.

Programmeeroefening: Lees het programma in
Schrijf een functie getBASIC() die geen argumenten heeft, en het volgende doet: het leest de regels vanaf input met behulp van een while loop; wanneer het einde bereikt wordt zal het hele programma worden teruggeven in de vorm van een lijst van strings. (Hints: lijsten en stoppen)
Tik de invoer voor je programma hieronder in.

Sub-taak 2: Daar gaan we!

Wanneer we eenmaal het programma hebben ingelezen moeten we van regel naar regel kunnen gaan in het programma. Om dit voor elkaar te kunnen krijgen, vragen we je om de volgende subroutine te schijven.

Programmeeroefening: Go to it!
Definieer een functie findLine(prog, target) dat het volgende doet. Neem aan dat prog een lijst is met strings dat een BASIC programma weergeeft, net zoals het type dat gegenereerd wordt door getBASIC(); neem aan dat target een string is dat een regelnummer bevat, die de target vormt van een GOTO statement. De functie moet dan de index i teruggegeven (een getal tussen 0 en len(prog)-1) waarbij prog[i] de regel is waarvan het label gelijk is aan target. Hint 
Sample input/output: Wanneer je 

findLine(['10 GOTO 20','20 END'], '10')
aanroept dan moet de output 0 zijn,  want item 0 uit de lijst is de regel met label 10.
Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Sub-taak 3: Slim het programma nabootsen

In de vorige twee oefeningen hebben we de input routine en de zoek taak gerealiseerd. Dit helpt om het programma korter te maken. Er is echter nog een belangrijke vraag onbeantwoord: hoe kunnen we het probleem dat we ons gesteld hebben oplossen? De meest rechttoe rechtaan weg zou het nabootsen van het BASIC programma zijn:

  • laat prog het BASIC programma zijn (een array met strings)
  • start een teller location met beginwaarde 0, omdat we beginnen met de eerste regel van het programma
  • while True (zolang True),
    • als prog[location] de END regel is, geef "success" terug and stop.
    • zorg ervoor dat T de target string is in prog[location]
    • zorg ervoor dat de nieuwe waarde van location findLine(prog, T) is.

Maar er is een probleem: hiermee worden geen oneindige loops gedetecteerd, en als het BASIC programma een oneindige loop heeft, dan zal ook het Python programma in een oneindige loop blijven doorgaan. Wat we wilden was dat het programma in deze situatie "infinite loop" zou afdrukken. Aan jou om dit probleem op te lossen; we geven hier beneden een hint.

Programmeeroefening: Slim nabootsen
Schrijf een functie execute(prog) dat het volgende doet. Stel dat prog een lijst met strings is dat een BASIC programma bevat zoals eerder. Dan moet je programma ofwel "success" ofwel "infinite loop" teruggeven, afhankelijk of het programma wordt beeindigd, of voor altijd in een loop blijft. Belangrijk: je moet doen alsof de procedure findLine(prog, target) zoals gedefinieerd in sub-taak 2 al gedefinieerd is, je hoeft die niet nog een keer te schrijven. Hint
Voer testcommando's zoals print(myfunction("test argument")) hieronder in.

Alles samenvoegen

Om je programma te testen als complete oplossing kopieer je je deelprogramma's in het volgende template.

Programmeeroefening: BASIC Simulator
Put together your BASIC simulator.
Tik de invoer voor je programma hieronder in.

Wanneer je programma een beetje ingewikkelder is, dan is het onmogelijk om een een programma te schrijven dat nagaat of het eindigt. Dit was de eerste belangrijke stelling in de Informatica, bewezen door Alan Turing in de  jaren 30 van de vorige eeuw, en tegenwoordig wordt eraan gerefereerd als "het Halting Problem is onbeslisbaar."