Entscheidbarkeit

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
PythonNeuling8
User
Beiträge: 5
Registriert: Sonntag 5. Februar 2023, 15:08

Hallo, ich habe eine Frage zu folgenden zwei ähnlichen Aufgaben:
a) Ist es möglich, ein Programm zu schreiben, das entscheidet, ob in einem beliebigen Programm die Anweisung print(100) vorkommt?
b) Ist es möglich, ein Programm zu schreiben, das entscheidet, ob in einem beliebigen Programm die Anweisung print(100) vorkommt UND ausgeführt wird?

zu a): Ist es möglich, den Text aus der zuvor eingelesenen Datei mit split() aufzuteilen und die sich daraus ergebende Liste nach print abzusuchen? Es kann ja vorkommen, dass 'print' als String vorkommt, also würde ich bei dem Absuchen der Liste dann Bedingungen geben, dass vor dem print kein Anführungszeichen kommt und danach auch etc. Würde dies alle möglichen Fälle bereits abdecken?

zu b): Ich vermute, dass dies nicht geht. Mit entsprechenden bool-Werten kann man sicherlich zeigen, dass dies nicht möglich ist oder?

Für Hilfe in den nächsten Tagen wäre ich sehr dankbar!
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

zu a) um den Programmcode nach `print` untersuchen zu können, muß man den Programmtext parsen. Dafür gibt es das ast-Modul. Aber dann ist noch nicht klar, was "Programm" eigentlich meint. Müssen auch alle Module, die die Hauptdatei importiert, mit untersucht werden? Kommt in einem Programm, das dynamisch die Anweisung `print(100)` erzeugt, diese Anweisung vor oder nicht?
zu b) die Frage ist nicht präzise genug. Darf das Programm, das prüfen soll, das zu prüfende Programm ausführen? Falls ja, ist die Prüfung einfach.
Benutzeravatar
pillmuncher
User
Beiträge: 1482
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

Im Allgemeinen ist es nicht entscheidbar, ob eine bestimmte Stelle im Code ausgeführt werden wird. Das folgt aus dem Satz von Rice. Im Speziellen kann man allerdings schon Aussagen treffen, etwa wenn dein Programm lediglich aus der Anweisung print(100) besteht. In der Aufgabe steht allerdings "...ob in einem beliebigen Programm...". Also: Was meinst du?
In specifications, Murphy's Law supersedes Ohm's.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@Sirius3: Zu b): ``if random() < 0.5: print(100)`` — einfach zu entscheiden ob das ausgeführt wird?
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
PythonNeuling8
User
Beiträge: 5
Registriert: Sonntag 5. Februar 2023, 15:08

@Sirius3 Hallo, danke für deine Antwort. zu a): Da wir in unserem Kurs noch nicht sehr fortgeschritten sind, werden unsere Programme relativ leicht gehalten, ohne Module, sondern nur mit den Standard-Programmierfähigkeiten wie for-Schleifen. Ich hab selbst einmal probiert, ein Programm zu schreiben, das einen beliebigen Text zerlegt und nach print(100) untersucht. Du kannst ja gerne Feedback dazu geben, darüber würde ich mich sehr freuen.

Code: Alles auswählen

# definieren funktion, die ein Python-Programm darauf prüft, ob print(100)-Anweisung vorkommt
def pruefe_print_100(datei):
    # Öffnen und Einlesen der Datei
    f = open(datei,"r")
    quelltext = f.read()
    # Aufteilen des Programmcodes in einzelne Elemente
    print(quelltext)
    l = quelltext.split()
    print(l)
    
    i = 0
    k = 0
    # jeden Code zwischen Anführungszeichen entfernen (falls 'print(100)' als String vorkommt)
    while k < len(l)-i:
        # Durchsuchen der Liste bis zum Finden des ersten ' oder "
        while l[i] != "'" and l[i] != '"' and i < len(l)-2:
            i += 1
            k += 1
        i += 1
        # Entferne alle Elemente bis zum nächsten Anführungszeichen
        while l[i] != "'" and l[i] != '"' and i < len(l)-2:
            l.remove(l[i])
            k += 1
        i += 1
    
    # Durchsuchen der neuen, von Anführungszeichen bereinigten Liste nach print
    kommt_vor = False
    for i in range(len(l)):
        # wenn print(100) sofort explizit gefunden wird, fertig
        if l[i] == 'print(100)':
            kommt_vor = True
            break
        # falls print vorkommt mit leerzeichen danach (z. B. in der Form print ( 100), prüfe weiter
        elif l[i] == 'print' or l[i] == 'print(' or l[i] == 'print(100':
            print_string = l[i]
            # prüfe die Elemente nach dem gefundenen print
            for j in range(i+1, i+4):
                print_string += l[j]
                # wenn sich print(100) ergibt, fertig
                if print_string == 'print(100)':
                    kommt_vor = True
                    break
            
    if kommt_vor == True:
        print("Die Anweisung print(100) kommt im Programm vor")
    else:
        print("Die Anweisung print(100) kommt nicht im Programm vor")


# Testprogramm 
pruefe_print_100("test.py")
pruefe_print_100("test2.py")
und das hat soweit auf jeden Fall funktioniert

zu b) Dabei sollte tatsächlich alles möglich sein, also auch, dass das Programm das zu prüfende selber ausführt. Das ganze ist ja angelehnt an das Halteproblem. Meine Idee:

Code: Alles auswählen

# Wenn ein solches Programm, das ein anderes darauf prüft, ob die print-Anweisung ausgeführt wird, existiert, dann 
# muss es eine Funktion geben, die in diesem Fall den Rückgabewert True oder eben False liefern kann, wenn 
# das Prüfen positiv oder negativ war.
def print100_kommt_vor(filename):

    f = open(filename)
    text = f.read()
    f.close()
    
    # Analysiert den gelesenen Python-Code (in text),
    # ob die Anweisung print(100) ausgeführt wird.
    # ...
    
    # Liefert in diesem Fall True zurück, sonst False.
    return b

# Dann kann man aber folgendes Hauptprogramm schreiben und das GESAMTE Programm als print100_kommt_vor.py speichern.
if print100_kommt_vor('print100_kommt_vor.py'):
    pass
else:
    print(100)
    
    
In den beiden Fällen unten, also sowohl im if als auch im else-Zweig sollte sich doch nun ein Widerspruch ergeben. Denn:
Wird True zurückgegeben, also wurde die print-Anweisung entdeckt, so wird der Zweig übersprungen und nichts wird ausgeführt.
Wird False zurückgegeben, so wird die print-Anweisung ausgeführt. Also stets ein Widerspruch zur Annahme, dass ein solches
Programm existiert.
PythonNeuling8
User
Beiträge: 5
Registriert: Sonntag 5. Februar 2023, 15:08

@pillmuncher Hallo, Danke dir für deine Antwort. Das ganze ist angelehnt an das Halteproblem bzw. wie du es schon meintest. Also soll es für jedes beliebe Programm gelten. Meine Idee war nun diese:

Code: Alles auswählen

# Wenn ein solches Programm, das ein anderes darauf prüft, ob die print-Anweisung ausgeführt wird, existiert, dann 
# muss es eine Funktion geben, die in diesem Fall den Rückgabewert True oder eben False liefern kann, wenn 
# das Prüfen positiv oder negativ war.
def print100_kommt_vor(filename):

    f = open(filename)
    text = f.read()
    f.close()
    
    # Analysiert den gelesenen Python-Code (in text),
    # ob die Anweisung print(100) ausgeführt wird.
    # ...
    
    # Liefert in diesem Fall True zurück, sonst False.
    return b

# Dann kann man aber folgendes Hauptprogramm schreiben und das GESAMTE Programm als print100_kommt_vor.py speichern.
if print100_kommt_vor('print100_kommt_vor.py'):
    pass
else:
    print(100)
    
    
In den beiden Fällen unten, also sowohl im if als auch im else-Zweig sollte sich doch nun ein Widerspruch ergeben. Denn:
Wird True zurückgegeben, also wurde die print-Anweisung entdeckt, so wird der Zweig übersprungen und nichts wird ausgeführt.
Wird False zurückgegeben, so wird die print-Anweisung ausgeführt. Also stets ein Widerspruch zur Annahme, dass ein solches
Programm existiert.

Du kannst mir gerne sagen, was du davon hältst, oder ob du eine Lücke findest in meinem Beweis
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@PythonNeuling8: Das Programm zum suchen von ``print(100)`` funktioniert ganz sicher nicht. Der Quelltext wird mit `split()` zerlegt und dann wird versucht der Inhalt von Zeichenketten mit Tests von einzelnen Elementen auf " oder ' zu entfernen, aber `split()` opereriert auf ”whitespace”, das heisst schon ein ganz einfaches "print(100)" wird nicht so zerlegt, das die " durch Test auf einzelne " gefunden werden.

Dann ist dem Code offensichtlich egal ob Anfang und Ende der Zeichenkettenbegrenzungen überhaupt zusammenpassen. Eine literale Zeichenkette ist erst zuende wenn die *passende* Endbegrenzung gefunden wird, also Paare von " und ' und beispielsweise nicht " am Anfange und ' am Ende.

Mit \ entwertete Zeichenkettenbegrenzer werden auch nirgends behandelt.

Kommentare werden nicht berücksichtigt. In dem Beispielcode selbst kommt `print(100)` ja mehrmals in Kommentaren vor, das Programm um zu entscheiden ob ``print(100)`` als *Code* vorkommt, funktioniert also auf sich selbst angewendet nicht richtig.

Man braucht keinen kompletten AST aufbauen, ein Tokenizer (also zum Beispiel der aus der Standardbibliothek) sollte reichen. Oder man schreibt sich selbst einen der zumindest „whitespace“, Kommentare, Bezeichner, Klammern, und alle Variationen von Zeichenkettenliteralen verarbeiten kann. Wenn man dann aus der Token-Folge ”whitespace”-Tokens und Kommentare heraus filtert, muss man nur noch nach der Token-Folge "print", "(", "100", und ")" suchen.

Falls man sich das Zerlegen in Token selbst schreibt, dürften literale Zeichenketten mit all den Randfällen die grösste Herausforderung sein.

Die API von der Funktion ist nicht so günstig, weil man jeden Testfall in eine eigene Datei schreiben muss. Besser wäre eine Testfunktion die als Argument nicht den Dateinamen, sondern den Quelltext bekommt. Dann kann man die ganzen Testfälle in einer Python-Datei als literale Zeichenketten unterbringen. Sogar in der gleichen Datei in der sich die Testfunktion befindet.

Dateien die man öffnet, sollte man auch wieder schliessen. Dazu bietet sich die ``with``-Anweisung an.

Beim öffnen von Textdateien sollte man immer die Kodierung explizit angeben.

Namen sollten nicht kryptisch abgekürzt werden. Also nicht `f` wenn man `file` meint, oder `l` wenn man — ja was eigentlich meint? Zudem ist `l` in vielen Schriftarten nur schlecht von `1` oder `I` unterscheidbar.

Beim innersten Test wo `kommt_vor` auf `True` gesetzt werden kann, wirkt das `break` nur auf die innere Schleife, es wird also trotzdem noch (unnötig) weiter gesucht.

Man macht keine Vergleiche mit literalen Wahrheitswerten. Bei dem Vergleich kommt doch nur wieder ein Wahrheitswert bei heraus. Entweder der, den man sowieso schon hatte; dann kann man den auch gleich nehmen. Oder das Gegenteil davon; dafür gibt es ``not``.

Es wäre besser wenn die Funktion einen Wahrheitswert zurück gibt, statt eine Ausgabe mit `print()` zu machen. Dann könnte man das Ergebnis beim Aufrufer auswerten. Zum Beispiel in dem man dort eine Schleife über mehrere Testfälle laufen lässt und zählen kann wie oft das Ergebnis (in)korrekt ist.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Also nur in Token zerlegen setzt natürlich voraus, dass man davon ausgehen kann, dass es sich um gültige Python-Syntax handelt und man *das* nicht auch noch prüfen muss.

Und man muss zusätzlich zu dem bisher gesagten noch berücksichtigen wo Ausdrücke zuende sind, also das hier enthät keinen ``print(100)``-Aufruf:

Code: Alles auswählen

print
(100)
Die folgenden beiden Beispiele aber schon:

Code: Alles auswählen

print \
(100)

Code: Alles auswählen

(
    print
    (100)
)
Letzeres Beispiel steht stellvertretend für beliebige Klammerkonstrukte. Auch beliebig komplex verschachtelt. Das ist also nicht so einfach wie es auf den ersten Blick erscheinen mag.

Ein Lösungsansatz der von syntaktisch korrekten Quelltexten ausgeht und das `tokenize`-Modul aus der Standardbibliothek verwendet, könnte so aussehen (nicht weiter getestet als in dem Quelltext zu sehen ist):

Code: Alles auswählen

#!/usr/bin/env python3
import io
from token import COMMENT, DEDENT, ENCODING, ENDMARKER, INDENT, NEWLINE, NL
from tokenize import tokenize

from more_itertools import sliding_window


def iter_tokens(source):
    return (
        (token.type, token.string)
        for token in tokenize(io.BytesIO(source).readline)
        if token.type not in {COMMENT, DEDENT, ENCODING, ENDMARKER, INDENT, NL}
    )


def check_for_tokens(source, tokens):
    return tokens in sliding_window(iter_tokens(source), len(tokens))


def main():
    tokens = tuple(iter_tokens(b"print(100)"))
    assert tokens[-1][0] == NEWLINE
    tokens = tokens[:-1]
    
    print(check_for_tokens(b"print ( \n100 # comment\n), 42", tokens))


if __name__ == "__main__":
    main()
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Und noch die AST-Lösung, die ist im Grunde noch einfacher wenn man die Werkzeuge aus der Standardbibliothek verwendet, die einem die ganze harte Arbeit abnehmen:

Code: Alles auswählen

#!/usr/bin/env python3
from ast import Call, Constant, Name, parse, walk


def is_print_100(node):
    return (
        isinstance(node, Call)
        and isinstance(node.func, Name)
        and node.func.id == "print"
        and len(node.args) == 1
        and isinstance(node.args[0], Constant)
        and node.args[0].value == 100
    )


def check_for_print_100(source):
    return any(map(is_print_100, walk(parse(source))))


def main():
    print(check_for_print_100("print ( \n100 # comment\n), 42"))


if __name__ == "__main__":
    main()
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Antworten