Alternative zu Methoden für rekursive Datenstruktur?

[sma]

Wie schon mehrfach erwähnt, baue ich aus Spaß einen Python-Interpreter in Python. Dieser zerlegt einen String in eine Liste von Symbolen, baut daraus einen abstrakten Syntaxbaum (AST) und bietet Methoden, die zusammen mit einem minimalen Laufzeitsystem den AST interpretieren können.

Der Scanner, der den String aufbricht, ist eine einzelne Funktion. Der Parser besteht jetzt ebenfalls aus einfachen Funktionen. Also dachte ich, ich könnte vielleicht komplett ohne Klassen auskommen. Den AST repräsentiere ich in guter Lisp-Tradition als (tief) verschachtelte Tupel:

Code: Alles auswählen

    ("Suite", [
        ("Def", "fib", ["n"], ("Suite", [
            ("If",
                ("Lt", ("Var", "n"), ("Lit", 2)),
                ("Return", ("Var", "n")),
                ("Return",
                    ("Add",
                        ("Call", ("Var", "fib"), [("Sub", ("Var", "n"), ("Lit", 1))]),
                        ("Call", ("Var", "fib"), [("Sub", ("Var", "n"), ("Lit", 2))]))))])),
        ("Call", ("Var", "fib"), [("Lit", 10)])])

Doch wie verarbeite ich diesen am geschicktesten?

Wären die AST-Knoten Exemplare von Klassen, würde ich entsprechende Methoden definieren:

Code: Alles auswählen

    class Var:
        def eval(self, f):
            return f.get(self.name)

    class Add:
        def eval(self, f):
            return self.left.eval(f) + self.right.eval(f)

Ich könnte explizit dispatchen:

Code: Alles auswählen

    def _eval(ast, f):
        # dies könnte auch ein eigenes dict sein, aber so ist's kürzer:
        return globals()[ast[0] + "_eval"](ast, f)
    
    def Var_eval(ast, f):
        return f.get(ast[1])
    
    def Add_eval(ast, f):
        return _eval(ast[1], f) + _eval(ast[2], f)

Oder als wenn ich ein switch-case hätte:

Code: Alles auswählen

    def _eval(ast, f):
        if ast[0] == "Var":
            return f.get(ast[1])
        if ast[0] == "Add":
            return _eval(ast[1]) + _eval(ast[2])
        ...

Oder indirekt, indem ich statt Strings direkt die Funktionsobjekte benutze:

Code: Alles auswählen

    def _eval(ast, f):
        return ast[0](ast, f)

    (Add_eval, (Var_eval, "n"), (Lit_eval, 1))

Dann kann ich aber nur eine Funktion auf dem AST definieren. Da fällt mir aber folgendes ein:

Code: Alles auswählen

    def _eval(ast, f):
        return ast[0][0](ast, f)

    def _set(ast, f, value):
        ast[0][1](ast, f, value)

    def Var_set(ast, f, value):
        f.set(ast[1], value)
    
    def None_set(ast, f, value):
        raise SyntaxError

    Var = (Var_eval, Var_set)
    Add = (Add_eval, None_set)
    
    (Add, (Var, "n"), (Lit, 1))

Gibt es Alternativen?

Mein Interpreter beherrscht leider keine Decorators und keine lokale Funktionen. Bevor ich diese angehe, wäre es einfacher, Klassen zu implementieren

Stefan

[Dauerbaustelle]

Oder indirekt, indem ich statt Strings direkt die Funktionsobjekte benutze:

Code: Alles auswählen

    def _eval(ast, f):
        return ast[0](ast, f)

    (Add_eval, (Var_eval, "n"), (Lit_eval, 1))

Dann kann ich aber nur eine Funktion auf dem AST definieren.

Kann ich nicht nachvollziehen. Wie meinen, "nur eine Funktion"? Abgesehen davon finde ich die Lösung am elegantesten, weil ubersimpel :)

[sma]

Wie meinen, "nur eine Funktion"? Abgesehen davon finde ich die Lösung am elegantesten, weil ubersimpel

Die vielen eval-"Methoden" bilden eine Funktion auf dem AST. Was, wenn ich auch noch "compile" haben will, wo es wieder für jeden AST-Knoten eine Methode geben muss? Dann kann ich da nicht direkt das Funktionsobjekt als erstes Element zur Unterscheidung eintragen.

Ich glaube, ich will hier zu clever sein und Klassen sind doch die einfachste Lösung. Mir gefällt zwar die Einfachheit von

Code: Alles auswählen

def Add(left, right): return "Add", left, right

um den AST zu bauen im Vergleich zu

Code: Alles auswählen

class Add:
    def __init__(self, left, right):
        self.left, self.right = left, right

aber um Klassen (mit einer Sematik irgendwo zwischen Python 1 und 3 zu implementieren, habe ich ca. 100 Zeilen Code im Laufzeitsystem gebraucht und die Klassen Class, Inst und Meth implementiert (die Namen passen so schön zu List, Dict und Func).

Stefan