CPython vs. Numba vs. Rust

[__blackjack__]

Das Reisebüro finde ich nicht so wirklich greifbar als Beispiel. Aber es ist genau umgekehrt: Wenn die Objekte da alle einen gemeinsamen Punkt hätten, bräuchte man den Besucher nicht, denn dann könnte man auf jedem Objekt ja einfach diesen Punkt abfragen. Also beispielsweise der AstPrinter: Wenn die Objekte alle eine `as_pretty_string()`-Methode hätten, könnte man die ja einfach aufrufen und hätte die Darstellung die man ausgeben will. Dann müsste aber auch jedes dieser Objekte selber wissen wie es denn als hübsche Zeichenkette aussehen muss. Bei der Besucher-Variante müssen die Objekte das überhaupt nicht wissen, dafür hat der Besucher für jeden Objekttyp eine Methode die auf den jeweiligen Typ zugeschnitten ist und weiss wie sie daraus eine hübsche Darstellung machen kann.

Mal als Gegenüberstellung ein AST wo man von den Knoten direkt die DATA-Werte abfragen kann und wo jeder Knoten selbst weiss wie er sich selbst auszuführen hat, und das gleiche dann nochmal mit komplett ”dummen” AST-Knoten und zwei Besuchern die jeweils die DATA-Werte abfragen oder einen AST ausführen:

”Schlaue” AST-Knoten:

Code: Alles auswählen

#!/usr/bin/env python3
import re
from operator import add, lt as is_less_than, sub as subtract

from attrs import define, field, frozen
from prettyprinter import cpprint as pprint, install_extras

install_extras(["attrs"])

SOURCE = """\
; Read in the data.
(READ n)
(DIM (t n n) (o n n))
(FOR i = 1 TO n
  (FOR j = 1 TO i
    (DO
      (READ k)
      ((t i j) = k)
      ((o i j) = k))))

; Calculate the result.
(FOR i = n DOWNTO 2
  (FOR j = 1 TO (i - 1)
    (DO
      (k = j)
      (IF ((t i j) < (t i (j + 1))) THEN (k = (k + 1)))
      ((t (i - 1) j) = ((t (i - 1) j) + (t i k))))))

(PRINT (t 1 1))

(DATA 15)  ; Row count to follow.

; The triangle values.
(DATA 75)
(DATA 95 64)
(DATA 17 47 82)
(DATA 18 35 87 10)
(DATA 20 4 82 47 65)
(DATA 19 1 23 75 3 34)
(DATA 88 2 77 73 7 63 67)
(DATA 99 65 4 28 6 16 70 92)
(DATA 41 41 26 56 83 40 80 70 33)
(DATA 41 48 72 33 47 32 37 16 94 29)
(DATA 53 71 44 65 25 43 91 52 97 51 14)
(DATA 70 11 33 28 77 73 17 78 39 68 17 57)
(DATA 91 71 52 38 17 14 91 43 58 50 27 29 48)
(DATA 63 66 4 68 89 53 67 30 73 16 69 87 40 31)
(DATA 4 62 98 27 23 9 70 98 73 93 38 53 60 4 23)
"""


@frozen
class Node:
    def iter_data_values(self):
        yield from ()

    def execute(self, _context):
        raise NotImplementedError


@frozen
class Literal(Node):
    value = field()

    def execute(self, _context):
        return self.value


@frozen
class ScalarVariable(Node):
    name = field()

    def execute(self, context):
        return context.scalars[self.name]


@frozen
class ArrayElement(Node):
    name = field()
    indices = field()

    def execute(self, context):
        result = context.arrays[self.name]
        for index in self.indices:
            result = result[index.execute(context)]
        return result


@frozen
class BinaryOperation(Node):
    SYMBOL_TO_FUNCTION = {"+": add, "-": subtract, "<": is_less_than}

    left_operand = field()
    operator = field()
    right_operand = field()

    def execute(self, context):
        return self.SYMBOL_TO_FUNCTION[self.operator](
            self.left_operand.execute(context),
            self.right_operand.execute(context),
        )


@frozen
class AssignScalar(Node):
    variable = field()
    expression = field()

    def execute(self, context):
        context.scalars[self.variable.name] = self.expression.execute(
            context
        )


@frozen
class AssignArrayElement(Node):
    array_element = field()
    expression = field()

    def execute(self, context):
        array = context.arrays[self.array_element.name]
        for index in self.array_element.indices[:-1]:
            array = array[index.execute(context)]
        array[self.array_element.indices[-1].execute(context)] = (
            self.expression.execute(context)
        )


@frozen
class Data(Node):
    values = field()

    def iter_data_values(self):
        return iter(self.values)

    def execute(self, _context):
        pass


@frozen
class Read(Node):
    variable = field()

    def execute(self, context):
        context.scalars[self.variable.name] = next(context.data_values)


@frozen
class Dim(Node):
    array_elements = field(factory=list)

    def execute(self, context):
        for array_element in self.array_elements:
            dimensions = (
                index.execute(context) + 1
                for index in reversed(array_element.indices)
            )
            array = [0] * next(dimensions)
            for dimension in dimensions:
                array = [array.copy() for _ in range(dimension)]
            context.arrays[array_element.name] = array


@frozen
class If(Node):
    condition = field()
    statement = field()

    def iter_data_values(self):
        return self.statement.iter_data_values()

    def execute(self, context):
        if self.condition.execute(context):
            self.statement.execute(context)


@frozen
class For(Node):
    variable = field()
    start = field()
    end = field()
    step = field()
    statement = field()

    def iter_data_values(self):
        return self.statement.iter_data_values()

    def execute(self, context):
        name = self.variable.name
        context.scalars[name] = self.start.execute(context)
        end_value = self.end.execute(context)
        step_value = self.step.execute(context)
        while True:
            self.statement.execute(context)
            value = context.scalars[name] + step_value
            if (
                step_value > 0
                and value > end_value
                or step_value < 0
                and value < end_value
            ):
                break
            context.scalars[name] = value


@frozen
class Print(Node):
    expressions = field(factory=list)

    def execute(self, context):
        print(
            " ".join(
                str(expression.execute(context))
                for expression in self.expressions
            )
        )


@frozen
class Block(Node):
    statements = field(factory=list)

    def iter_data_values(self):
        for statement in self.statements:
            yield from statement.iter_data_values()

    def execute(self, context):
        for statement in self.statements:
            statement.execute(context)


SCANNER = re.Scanner(
    [
        (r"\s+|;.*$", None),
        (r"\(", "("),
        (r"\)", ")"),
        (r"-?\d+", lambda _, text: int(text)),
        (r"\w+|[-+=<]", lambda _, text: text),
    ],
    re.MULTILINE,
)


def parse(text):
    tokens, text = SCANNER.scan(text)
    if text:
        raise ValueError(f"expected end of source text, found:\n{text}")

    stack = []
    statements = []
    for token in tokens:
        if token == "(":
            stack.append(statements)
            statements = []

        elif token == ")":
            if not stack:
                raise ValueError("unexpected closing parenthesis")
            stack[-1].append(statements)
            statements = stack.pop()

        else:
            statements.append(token)

    if stack:
        raise ValueError(f"{len(stack)} unclosed parenthesis")

    return statements[0] if len(statements) == 1 else ["DO", *statements]


def build_ast(s_expression):
    match s_expression:
        case "DO", *statements:
            return Block(list(map(build_ast, statements)))

        case "DIM", *arrays:
            return Dim(list(map(build_ast, arrays)))

        case (
            "FOR",
            str(name),
            "=",
            start,
            "TO" | "DOWNTO" as direction,
            end,
            statement,
        ):
            return For(
                ScalarVariable(name),
                build_ast(start),
                build_ast(end),
                Literal(1 if direction == "TO" else -1),
                build_ast(statement),
            )

        case "IF", condition, "THEN", statement:
            return If(build_ast(condition), build_ast(statement))

        case "PRINT", *expressions:
            return Print(list(map(build_ast, expressions)))

        case "DATA", *values:
            return Data(values)

        case "READ", str(name):
            return Read(ScalarVariable(name))

        case [str(name), *indices], "=", expression:
            return AssignArrayElement(
                ArrayElement(name, list(map(build_ast, indices))),
                build_ast(expression),
            )

        case str(name), "=", expression:
            return AssignScalar(ScalarVariable(name), build_ast(expression))

        case left_operand, "+" | "-" | "<" as operator, right_operand:
            return BinaryOperation(
                build_ast(left_operand), operator, build_ast(right_operand)
            )

        case str(name), *indices:
            return ArrayElement(name, list(map(build_ast, indices)))

        case str(name):
            return ScalarVariable(name)

        case int(value):
            return Literal(value)

        case _:
            raise ValueError(f"can not handle {s_expression!r}")


@define
class Context:
    data_values = field(factory=lambda: iter([]))
    scalars = field(factory=dict)
    arrays = field(factory=dict)


def run(ast):
    context = Context(ast.iter_data_values())
    ast.execute(context)
    return context


def main():
    s_expression = parse(SOURCE)
    pprint(s_expression, indent=2, compact=True)
    ast = build_ast(s_expression)
    pprint(ast, indent=2, compact=True)
    context = run(ast)
    pprint(context.scalars, indent=2, compact=True)
    pprint(context.arrays["t"], indent=2, compact=True)


if __name__ == "__main__":
    main()

Versus ”dumme” AST-Knoten + Besucher:

Code: Alles auswählen

#!/usr/bin/env python3
import re
from operator import add, lt as is_less_than, sub as subtract

from attrs import define, field, frozen
from prettyprinter import cpprint as pprint, install_extras

install_extras(["attrs"])

SOURCE = """\
; Read in the data.
(READ n)
(DIM (t n n) (o n n))
(FOR i = 1 TO n
  (FOR j = 1 TO i
    (DO
      (READ k)
      ((t i j) = k)
      ((o i j) = k))))

; Calculate the result.
(FOR i = n DOWNTO 2
  (FOR j = 1 TO (i - 1)
    (DO
      (k = j)
      (IF ((t i j) < (t i (j + 1))) THEN (k = (k + 1)))
      ((t (i - 1) j) = ((t (i - 1) j) + (t i k))))))

(PRINT (t 1 1))

(DATA 15)  ; Row count to follow.

; The triangle values.
(DATA 75)
(DATA 95 64)
(DATA 17 47 82)
(DATA 18 35 87 10)
(DATA 20 4 82 47 65)
(DATA 19 1 23 75 3 34)
(DATA 88 2 77 73 7 63 67)
(DATA 99 65 4 28 6 16 70 92)
(DATA 41 41 26 56 83 40 80 70 33)
(DATA 41 48 72 33 47 32 37 16 94 29)
(DATA 53 71 44 65 25 43 91 52 97 51 14)
(DATA 70 11 33 28 77 73 17 78 39 68 17 57)
(DATA 91 71 52 38 17 14 91 43 58 50 27 29 48)
(DATA 63 66 4 68 89 53 67 30 73 16 69 87 40 31)
(DATA 4 62 98 27 23 9 70 98 73 93 38 53 60 4 23)
"""


@frozen
class Literal:
    value = field()


@frozen
class ScalarVariable:
    name = field()


@frozen
class ArrayElement:
    name = field()
    indices = field()


@frozen
class BinaryOperation:
    left_operand = field()
    operator = field()
    right_operand = field()


@frozen
class AssignScalar:
    variable = field()
    expression = field()


@frozen
class AssignArrayElement:
    array_element = field()
    expression = field()


@frozen
class Data:
    values = field()


@frozen
class Read:
    variable = field()


@frozen
class Dim:
    array_elements = field(factory=list)


@frozen
class If:
    condition = field()
    statement = field()


@frozen
class For:
    variable = field()
    start = field()
    end = field()
    step = field()
    statement = field()


@frozen
class Print:
    expressions = field(factory=list)


@frozen
class Block:
    statements = field(factory=list)


SCANNER = re.Scanner(
    [
        (r"\s+|;.*$", None),
        (r"\(", "("),
        (r"\)", ")"),
        (r"-?\d+", lambda _, text: int(text)),
        (r"\w+|[-+=<]", lambda _, text: text),
    ],
    re.MULTILINE,
)


def parse(text):
    tokens, text = SCANNER.scan(text)
    if text:
        raise ValueError(f"expected end of source text, found:\n{text}")

    stack = []
    statements = []
    for token in tokens:
        if token == "(":
            stack.append(statements)
            statements = []

        elif token == ")":
            if not stack:
                raise ValueError("unexpected closing parenthesis")
            stack[-1].append(statements)
            statements = stack.pop()

        else:
            statements.append(token)

    if stack:
        raise ValueError(f"{len(stack)} unclosed parenthesis")

    return statements[0] if len(statements) == 1 else ["DO", *statements]


def build_ast(s_expression):
    match s_expression:
        case "DO", *statements:
            return Block(list(map(build_ast, statements)))

        case "DIM", *arrays:
            return Dim(list(map(build_ast, arrays)))

        case (
            "FOR",
            str(name),
            "=",
            start,
            "TO" | "DOWNTO" as direction,
            end,
            statement,
        ):
            return For(
                ScalarVariable(name),
                build_ast(start),
                build_ast(end),
                Literal(1 if direction == "TO" else -1),
                build_ast(statement),
            )

        case "IF", condition, "THEN", statement:
            return If(build_ast(condition), build_ast(statement))

        case "PRINT", *expressions:
            return Print(list(map(build_ast, expressions)))

        case "DATA", *values:
            return Data(values)

        case "READ", str(name):
            return Read(ScalarVariable(name))

        case [str(name), *indices], "=", expression:
            return AssignArrayElement(
                ArrayElement(name, list(map(build_ast, indices))),
                build_ast(expression),
            )

        case str(name), "=", expression:
            return AssignScalar(ScalarVariable(name), build_ast(expression))

        case left_operand, "+" | "-" | "<" as operator, right_operand:
            return BinaryOperation(
                build_ast(left_operand), operator, build_ast(right_operand)
            )

        case str(name), *indices:
            return ArrayElement(name, list(map(build_ast, indices)))

        case str(name):
            return ScalarVariable(name)

        case int(value):
            return Literal(value)

        case _:
            raise ValueError(f"can not handle {s_expression!r}")


@define
class Visitor:
    def visit_any(self, _node):
        return None

    def visit(self, node):
        return getattr(
            self, "visit_" + node.__class__.__name__, self.visit_any
        )(node)


@define
class DataVisitor(Visitor):
    def visit_any(self, _node):
        return iter([])

    def visit_Data(self, node):
        return iter(node.values)

    def visit_Block(self, node):
        for statement in node.statements:
            yield from self.visit(statement)

    def visit_For(self, node):
        return self.visit(node.statement)

    def visit_If(self, node):
        return self.visit(node.statement)


@define
class ExecutionVisitor(Visitor):
    SYMBOL_TO_FUNCTION = {"+": add, "-": subtract, "<": is_less_than}

    data_values = field(factory=lambda: iter([]))
    scalars = field(factory=dict)
    arrays = field(factory=dict)

    def visit_any(self, node):
        raise RuntimeError(f"can not execute {node!r}")

    def visit_Literal(self, node):
        return node.value

    def visit_ScalarVariable(self, node):
        return self.scalars[node.name]

    def visit_ArrayElement(self, node):
        result = self.arrays[node.name]
        for index in node.indices:
            result = result[self.visit(index)]
        return result

    def visit_BinaryOperation(self, node):
        return self.SYMBOL_TO_FUNCTION[node.operator](
            self.visit(node.left_operand), self.visit(node.right_operand)
        )

    def visit_AssignScalar(self, node):
        self.scalars[node.variable.name] = self.visit(node.expression)

    def visit_AssignArrayElement(self, node):
        array = self.arrays[node.array_element.name]
        for index in node.array_element.indices[:-1]:
            array = array[self.visit(index)]
        array[self.visit(node.array_element.indices[-1])] = self.visit(
            node.expression
        )

    def visit_Data(self, _node):
        pass

    def visit_Read(self, node):
        self.scalars[node.variable.name] = next(self.data_values)

    def visit_Dim(self, node):
        for array_element in node.array_elements:
            dimensions = (
                self.visit(index) + 1
                for index in reversed(array_element.indices)
            )
            array = [0] * next(dimensions)
            for dimension in dimensions:
                array = [array.copy() for _ in range(dimension)]
            self.arrays[array_element.name] = array

    def visit_If(self, node):
        if self.visit(node.condition):
            self.visit(node.statement)

    def visit_For(self, node):
        name = node.variable.name
        self.scalars[name] = self.visit(node.start)
        end_value = self.visit(node.end)
        step_value = self.visit(node.step)
        while True:
            self.visit(node.statement)
            value = self.scalars[name] + step_value
            if (
                step_value > 0
                and value > end_value
                or step_value < 0
                and value < end_value
            ):
                break
            self.scalars[name] = value

    def visit_Print(self, node):
        print(
            " ".join(
                str(self.visit(expression)) for expression in node.expressions
            )
        )

    def visit_Block(self, node):
        for statement in node.statements:
            self.visit(statement)


def run(ast):
    executioner = ExecutionVisitor(DataVisitor().visit(ast))
    executioner.visit(ast)
    return executioner


def main():
    s_expression = parse(SOURCE)
    pprint(s_expression, indent=2, compact=True)
    ast = build_ast(s_expression)
    pprint(ast, indent=2, compact=True)
    executioner = run(ast)
    pprint(executioner.scalars, indent=2, compact=True)
    pprint(executioner.arrays["t"], indent=2, compact=True)


if __name__ == "__main__":
    main()

[grubenfox]

Ach, __blackjack__ war schneller-... egal, ich lasse meinen Text jetzt so...

Dann müssen die zu besuchenden Objekte aber zumindest alle so aufgebaut sein, dass sie einen "Punkt" haben, an dem die Informationen gesammelt abgeholt werden können? Also dass mein Besucher beispielsweise durch alle Klassen geht und sich überall ein Wörterbuch abholen kann?
Ich kann keinen Besucher erstellen, der auf unterschiedlichen Klassen unterschiedliche Attribute abfragt um so die Informationen zu sammeln. Wäre das soweit richtig?

Meiner bescheidenen Meinung nach: Nein, genau anders herum... (Von "Ich bin der Meinung, man hat etwas verstanden, wenn man es in eigenen Worte erklären kann." bin ich hier aber auch noch weit entfernt.)
Die Besucher haben eine einheitliche Schnittstelle die man aufrufen kann und jeder Besucher fragt auf den unterschiedlichen Klassen die er besucht unterschiedliche Attribute ab um die gewünschten Informationen zu sammeln. (Das schließt natürlich nicht die Möglichkeit aus, dass die zu besuchenden Objekte doch eine einheitlich Schnittstelle haben, aber in den Beispielen ist das nie so.)

Ich habe da noch ein paar Links:
https://refactoring.guru/design-patterns/visitor
https://refactoring.guru/design-pattern ... g-features
https://www.geeksforgeeks.org/visitor-m ... -patterns/

Ansonsten halte ich es hier mit diesem Text aus dem zweiten Link:

Usage examples: Visitor isn’t a very common pattern because of its complexity and narrow applicability.

[__blackjack__]

Zu dem „isn't a very common pattern“ muss man halt speziell zu dem Thema hier sagen: Bei ASTs ist es halt doch üblich, weil das genau einer der Einsatzzwecke ist, bei dem das praktisch ist. Weil man sonst immer mehr und mehr, und teilweise immer speziellere Methoden auf den AST-Knoten-Klassen bekommt, und die am Ende total überfrachtet werden.

[Kebap]

Dann müssen die zu besuchenden Objekte aber zumindest alle so aufgebaut sein, dass sie einen "Punkt" haben, an dem die Informationen gesammelt abgeholt werden können? Also dass mein Besucher beispielsweise durch alle Klassen geht und sich überall ein Wörterbuch abholen kann?
Ich kann keinen Besucher erstellen, der auf unterschiedlichen Klassen unterschiedliche Attribute abfragt um so die Informationen zu sammeln. Wäre das soweit richtig?

Ich denke, der Besucher ist schlau genug zu erkennen, wen er gerade besucht, und wie er die Informationen dort sammeln und aufbereiten muss. Das ist ja gerade der Punkt: Die besuchten Klassen müssen keine neue einheitliche Funktionalität erhalten.

edit: Huch, es gibt ja schon eine zweite Seite..

[Dennis89]

Vielen Dank für eure Antworten.
Habe nur lange den schlauen und den dummen AST-Knoten angeschaut. Ich würde mal vorsichtig behaupten, dass ich die Idee hinter dem Visitor-Pattern etwas verstehe. Wenn ich den Code des schlauen AST-Knoten anschaue, dann kann ich anhand des Codes verstehen, was abläuft, für den dummen bin ich zu dumm. Mit verschiedenen Ausgaben an verschiedenen Punkten, wird der Ablauf dann schon klar.
Ich speichere mir das jetzt so mal ab, das ich grob die Idee hinter dem Visitor-Pattern verstanden habe und lese das Buch mal weiter.

Wer weis, vielleicht gibt es tatsächlich mal einen Anwendungsfall und ich erinnere mich hier her wieder zurück. Habe immer etwas mein Berechnungsprogramm im Hinterkopf, das auch einige unterschiedliche Klassen haben wird und am Schluss brauche ich von allen Ergebnisse. Aber ich muss auch darauf achten, dass der Code nicht unnötig komplex wird.


Grüße
Dennis

[__blackjack__]

@Dennis89: Für das konkrete Beispiel mit dem „Lispy BASIC“ würde ich einfach die “schlauen“ AST-Knoten verwenden, weil es da ja nur zwei Operationen und damit nur zwei Methoden gibt. Bei der Lox-Programmiersprache wird in dem Kapitel mit dem Besucher-Entwurfsmuster angedeutet, dass da mehr Operationen kommen werden. Und wahrscheinlich auch zu verschiedenen Themengebieten, also beispielsweise mindestens Interpreter und Bytecode-Compiler. Vielleicht Optimierungsschritte auf dem AST, von denen Interpreter *und* Compiler profitieren.

Wenn man die Klassen nicht ändern *kann*, zum Beispiel weil man sie nicht selbst geschrieben hat, dann ist das Besucher-Muster aus OOP-Sicht *die* Möglichkeit das umzusetzen. Ähnliches Beispiel zu Crafting Interpreters, diesmal mit Python selbst, denn man hat im `ast`-Modul alles was man braucht um Python-Quelltext in einen AST zu übersetzen:

Code: Alles auswählen

#!/usr/bin/env python3
from ast import Add, Mult, NodeVisitor, Sub, USub, parse
from operator import add, mul, neg, sub

OPERATOR_TYPE_TO_FUNCTION = {
    Add: add,
    Mult: mul,
    Sub: sub,
    USub: neg,
}

OPERATOR_TYPE_TO_SYMBOL = {
    Add: "+",
    Mult: "*",
    Sub: "-",
    USub: "-",
}


class Lispyfier(NodeVisitor):
    def _parenthesize(self, name, nodes):
        arguments = " ".join(map(self.visit, nodes))
        return f"({name} {arguments})"

    def visit_BinOp(self, node):
        return self._parenthesize(
            OPERATOR_TYPE_TO_SYMBOL[type(node.op)], [node.left, node.right]
        )

    def visit_Constant(self, node):
        return repr(node.value)

    def visit_Expression(self, node):
        return self.visit(node.body)

    def visit_UnaryOp(self, node):
        return self._parenthesize(
            OPERATOR_TYPE_TO_SYMBOL[type(node.op)], [node.operand]
        )


class Evaluator(NodeVisitor):
    def visit_BinOp(self, node):
        return OPERATOR_TYPE_TO_FUNCTION[type(node.op)](
            self.visit(node.left), self.visit(node.right)
        )

    def visit_Constant(self, node):
        return node.value

    def visit_Expression(self, node):
        return self.visit(node.body)

    def visit_UnaryOp(self, node):
        return OPERATOR_TYPE_TO_FUNCTION[type(node.op)](
            self.visit(node.operand)
        )


def main():
    for text, expected_result in [
        ("1 + 2 * 3", 7),
        ("-1 * (45.67)", -45.67),
        ("(1 + 2) * (4 - 3)", 3),
    ]:
        expression_node = parse(text, mode="eval")

        result = Evaluator().visit(expression_node)
        print(
            Lispyfier().visit(expression_node),
            "->",
            result,
            result == expected_result,
        )


if __name__ == "__main__":
    main()

Ausgabe:

Code: Alles auswählen

(+ 1 (* 2 3)) -> 7 True
(* (- 1) 45.67) -> -45.67 True
(* (+ 1 2) (- 4 3)) -> 3 True

[narpfel]

Nur mal als „Gegenbeispiel“ zum Visitor-Pattern: Pattern Matching ist quasi das Äquivalent dazu aus der funktionalen Programmierung. IMHO ist das hier viel einfacher.

Code: Alles auswählen

#!/usr/bin/env python3
from ast import Add, Mult, NodeVisitor, Sub, USub, parse, BinOp, Constant, Expression, UnaryOp
from operator import add, mul, neg, sub

OPERATOR_TYPE_TO_FUNCTION = {
    Add: add,
    Mult: mul,
    Sub: sub,
    USub: neg,
}

OPERATOR_TYPE_TO_SYMBOL = {
    Add: "+",
    Mult: "*",
    Sub: "-",
    USub: "-",
}


class Lispyfier(NodeVisitor):
    def _parenthesize(self, name, nodes):
        arguments = " ".join(map(self.visit, nodes))
        return f"({name} {arguments})"

    def visit_BinOp(self, node):
        return self._parenthesize(
            OPERATOR_TYPE_TO_SYMBOL[type(node.op)], [node.left, node.right]
        )

    def visit_Constant(self, node):
        return repr(node.value)

    def visit_Expression(self, node):
        return self.visit(node.body)

    def visit_UnaryOp(self, node):
        return self._parenthesize(
            OPERATOR_TYPE_TO_SYMBOL[type(node.op)], [node.operand]
        )


class Evaluator(NodeVisitor):
    def visit_BinOp(self, node):
        return OPERATOR_TYPE_TO_FUNCTION[type(node.op)](
            self.visit(node.left), self.visit(node.right)
        )

    def visit_Constant(self, node):
        return node.value

    def visit_Expression(self, node):
        return self.visit(node.body)

    def visit_UnaryOp(self, node):
        return OPERATOR_TYPE_TO_FUNCTION[type(node.op)](
            self.visit(node.operand)
        )


def _parenthesize(name, nodes):
    arguments = " ".join(map(lispify, nodes))
    return f"({name} {arguments})"


def lispify(node):
    match node:
        case BinOp(left=left, op=op, right=right):
            return _parenthesize(OPERATOR_TYPE_TO_SYMBOL[type(op)], [left, right])
        case Constant(value=value):
            return repr(value)
        case Expression(body=body):
            return lispify(body)
        case UnaryOp(op=op, operand=operand):
            return _parenthesize(OPERATOR_TYPE_TO_SYMBOL[type(op)], [operand])
        case _:
            raise AssertionError(node)


def evaluate(node):
    match node:
        case BinOp(left=left, op=op, right=right):
            return OPERATOR_TYPE_TO_FUNCTION[type(op)](evaluate(left), evaluate(right))
        case Constant(value=value):
            return value
        case Expression(body=body):
            return evaluate(body)
        case UnaryOp(op=op, operand=operand):
            return OPERATOR_TYPE_TO_FUNCTION[type(op)](evaluate(operand))
        case _:
            raise AssertionError(node)


def main():
    for text, expected_result in [
        ("1 + 2 * 3", 7),
        ("-1 * (45.67)", -45.67),
        ("(1 + 2) * (4 - 3)", 3),
    ]:
        expression_node = parse(text, mode="eval")

        result = Evaluator().visit(expression_node)
        print(
            Lispyfier().visit(expression_node),
            "->",
            result,
            result == expected_result,
        )

        result = evaluate(expression_node)
        print(lispify(expression_node), "->", result, result == expected_result)


if __name__ == "__main__":
    main()

[Dennis89]

Danke für die weitere Erklärung.

Das Beispiel ist jetzt auf eine Art wirklich geschickt. Ich schaue mir immer wieder gerne Rätsel bzw. Programmieraufgaben an und heute Mittag sah ich eins, dass ich mir auf die "das muss ich mal versuchen" - Seite gelegt habe und die Aufgabenstellung lautet:

Instructions

Given a mathematical expression as a string you must return the result as a number.
Numbers

Number may be both whole numbers and/or decimal numbers. The same goes for the returned result.
Operators

You need to support the following mathematical operators:

Multiplication *
Division / (as floating point division)
Addition +
Subtraction -

Operators are always evaluated from left-to-right, and * and / must be evaluated before + and -.
Parentheses

You need to support multiple levels of nested parentheses, ex. (2 / (2 + 3.33) * 4) - -6
Whitespace

There may or may not be whitespace between numbers and operators.

An addition to this rule is that the minus sign (-) used for negating numbers and parentheses will never be separated by whitespace. I.e all of the following are valid expressions.

1-1 // 0
1 -1 // 0
1- 1 // 0
1 - 1 // 0
1- -1 // 2
1 - -1 // 2
1--1 // 2

6 + -(4) // 2
6 + -( -4) // 10

And the following are invalid expressions

1 - - 1 // Invalid
1- - 1 // Invalid
6 + - (4) // Invalid
6 + -(- 4) // Invalid

Validation

You do not need to worry about validation - you will only receive valid mathematical expressions following the above rules.
Restricted APIs

NOTE: eval and exec are disallowed in your solution.

`Div` und `truediv` einfügen und dann funktioniert zumindest der Beispiel-String schon.

Kann jetzt aber nicht alle Testfälle durchspielen, wenn das funktioniert, dann bekomme ich Punkte für einen Code, der nicht von mir ist. Aber cool zu sehen, wie man das umsetzen kann.

@narpfel sah deinen Beitrag erst, als ich den bisherigen schon geschrieben hatte. Danke für dein Beispiel. Das ist tatsächlich leichter zu verstehen. Allerdings steige ich nicht bis ins Detail durch.

Code: Alles auswählen

case BinOp(left=left, op=op, right=right):

So wie ich es gewohnt bin, habe ich mich jetzt auf die Suche gemacht, wo den `left, `op` und `right` her kommt. In der Doku zu `BinOp` steht zwar, was die drei bedeuten, aber ich sehe nicht wo die definiert sind. "Holt" `match` die Namen aus `node` raus? Konnte zu dem auch in der Doku zu `parse` finden, dass das ein `node`-Objekt zurückgibt, aber leider nicht wie ich da "rein schauen" kann.


Grüße
Dennis


Grüße
Dennis

[narpfel]

Code: Alles auswählen

case BinOp(left=left, op=op, right=right):

So wie ich es gewohnt bin, habe ich mich jetzt auf die Suche gemacht, wo den `left, `op` und `right` her kommt.

Das ist einfach wie `match` in Python funktioniert:

Code: Alles auswählen

class BinOp:
    def __init__(self):
        self.left = 42
        self.op = "+"
        self.right = 27


def main():
    bin_op = BinOp()
    match bin_op:
        case BinOp(left=left, op=op, right=right):
            print(left, op, right)


if __name__ == "__main__":
    main()

Code: Alles auswählen

$ python -m t
42 + 27

Wenn man in einem `case` ein Pattern schreibt, das wie ein Aufruf mit Keywordargumenten aussieht, dann bedeutet das im Prinzip (vereinfacht) das hier:

Code: Alles auswählen

match bin_op:
    case BinOp(left=left, op=op, right=right):
        ...

=>

Code: Alles auswählen

if isinstance(bin_op, BinOp) and hasattr(bin_op, "left") and hasattr(bin_op, "op") and hasattr(bin_op, "right"):
    left = bin_op.left
    op = bin_op.op
    right = bin_op.right
    ...

In PEP 634 ist das im Abschnitt „Class Patterns“ definiert.

Konnte zu dem auch in der Doku zu `parse` finden, dass das ein `node`-Objekt zurückgibt, aber leider nicht wie ich da "rein schauen" kann.

Dafür gibt es `ast.dump`.

[__blackjack__]

Das mit ``match`` und Klassen hatte ich doch hier schon drin: viewtopic.php?p=431473#p431473

[narpfel]

@__blackjack__: Ich hab den Thread überflogen, aber nicht in den einzelnen Codeblöcken runtergescrollt. Naja, doppelt hält besser.

[Dennis89]

Guten Morgen,

danke für die weiteren Antworten.
Ich hatte das mit `match` in dem Beispiel von @__blackjack__ auch schon gesehen, aber zu dem Zeitpunkt war ich wohl zu sehr auf Visitor-Pattern konzentriert, um das im Detail zu hinterfragen.


Grüße
Dennis

[Dennis89]

Hallo,

ich beschäftige mich noch einmal mit `Ast` und zwar ist das Ziel, das ich nicht nur mathematische Ausdrücke auswerten kann, sondern das ich auch Zuweisungen machen kann. Also `x = 3` oder `x = 5 + 3`.

Visitor-Pattern lege ich erst mal auf die Seite und habe mir als Vorlage Pattern-Matching hier aus den Beispielen genommen.

In der Doku zu `Ast.parse()` steht:

The mode argument specifies what kind of code must be compiled; it can be 'exec' if source consists of a sequence of statements, 'eval' if it consists of a single expression, or 'single' if it consists of a single interactive statement (in the latter case, expression statements that evaluate to something other than None will be printed).

Ich verstehe das so, das wenn ich Code einlese, der aus einer Zuweisung oder einem mathematischen Ausdruck oder beidem besteht, dann soll ich `mode=single` verwenden. Weil ich mache ja eigentlich nichts anderes, als eine interaktive Python Shell auch macht.

Ich habe erwartet das folgendes:

Code: Alles auswählen

#!/usr/bin/env python3
from ast import Add, Mult, Sub, USub, Div, parse, BinOp, Constant, Expression, UnaryOp, dump
from operator import add, mul, neg, sub, truediv

OPERATOR_TYPE_TO_FUNCTION = {
    Add: add,
    Mult: mul,
    Sub: sub,
    USub: neg,
    Div: truediv
}

def evaluate(node):
    match node:
        case BinOp(left=left, op=op, right=right):
            return OPERATOR_TYPE_TO_FUNCTION[type(op)](evaluate(left), evaluate(right))
        case Constant(value=value):
            return value
        case Expression(body=body):
            return evaluate(body)
        case UnaryOp(op=op, operand=operand):
            return OPERATOR_TYPE_TO_FUNCTION[type(op)](evaluate(operand))
        case _:
            raise AssertionError(node)


def main():
    expression_node = parse("(1 + 2) * (4 - 3)", mode="single")
    print(dump(expression_node))
    result = evaluate(expression_node)
    print(result)



if __name__ == "__main__":
    main()

funktioniert. Ich bekomme aber:

Code: Alles auswählen

/home/dennis/PycharmProjects/Forum/.venv/bin/python /home/dennis/PycharmProjects/Forum/Ast_test.py 
Interactive(body=[Expr(value=BinOp(left=BinOp(left=Constant(value=1), op=Add(), right=Constant(value=2)), op=Mult(), right=BinOp(left=Constant(value=4), op=Sub(), right=Constant(value=3))))])
Traceback (most recent call last):
  File "/home/dennis/PycharmProjects/Forum/Ast_test.py", line 36, in <module>
    main()
  File "/home/dennis/PycharmProjects/Forum/Ast_test.py", line 30, in main
    result = evaluate(expression_node)
             ^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/dennis/PycharmProjects/Forum/Ast_test.py", line 24, in evaluate
    raise AssertionError(node)
AssertionError: <ast.Interactive object at 0x7ffaebc8e8d0>

Process finished with exit code 1

Das liegt daran, dass der `case _:` ausgeführt wird. Dann hab ich geblickt, das ich den Fall `Interactive` gar nicht abfange und `Expr` brauche ich auch noch.

Code: Alles auswählen

#!/usr/bin/env python3
from ast import Add, Mult, Sub, USub, Div, parse, BinOp, Constant, Expr, Interactive, UnaryOp, dump
from operator import add, mul, neg, sub, truediv

OPERATOR_TYPE_TO_FUNCTION = {
    Add: add,
    Mult: mul,
    Sub: sub,
    USub: neg,
    Div: truediv
}

def evaluate(node):
    match node:
        case BinOp(left=left, op=op, right=right):
            return OPERATOR_TYPE_TO_FUNCTION[type(op)](evaluate(left), evaluate(right))
        case Constant(value=value):
            return value
        case Expr(value=body):
            return evaluate(body)
        case UnaryOp(op=op, operand=operand):
            return OPERATOR_TYPE_TO_FUNCTION[type(op)](evaluate(operand))
        case Interactive(body=body):
            return evaluate(body)
        case _:
            print(dump(*node, indent=4))
            raise AssertionError(node)


def main():
    expression_node = parse("(1 + 2) * (4 - 3)", mode="single")
    print(dump(expression_node))
    result = evaluate(expression_node)
    print(result)



if __name__ == "__main__":
    main()

ergibt aber leider:

Code: Alles auswählen

/home/dennis/PycharmProjects/Forum/.venv/bin/python /home/dennis/PycharmProjects/Forum/Ast_test.py 
Interactive(body=[Expr(value=BinOp(left=BinOp(left=Constant(value=1), op=Add(), right=Constant(value=2)), op=Mult(), right=BinOp(left=Constant(value=4), op=Sub(), right=Constant(value=3))))])
Expr(
    value=BinOp(
        left=BinOp(
            left=Constant(value=1),
            op=Add(),
            right=Constant(value=2)),
        op=Mult(),
        right=BinOp(
            left=Constant(value=4),
            op=Sub(),
            right=Constant(value=3))))
Traceback (most recent call last):
  File "/home/dennis/PycharmProjects/Forum/Ast_test.py", line 39, in <module>
    main()
  File "/home/dennis/PycharmProjects/Forum/Ast_test.py", line 33, in main
    result = evaluate(expression_node)
             ^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/dennis/PycharmProjects/Forum/Ast_test.py", line 24, in evaluate
    return evaluate(body)
           ^^^^^^^^^^^^^^
  File "/home/dennis/PycharmProjects/Forum/Ast_test.py", line 27, in evaluate
    raise AssertionError(node)
AssertionError: [<ast.Expr object at 0x7f1a2e297790>]

Process finished with exit code 1

Dabei sieht meine Ausgabe, doch vom Aufbau wie in der Doku aus:
https://docs.python.org/3/library/ast.html#ast.Expr

Ja ich versuche und hier viel hin und her und das durch die Doku zum ausführen zu bringen, aber vielleicht fehlt auch noch Verständnis in dem Thema.

Wäre nett, wenn ihr mir etwas helfen könnten.

Vielen Dank und Grüße
Dennis

[narpfel]

Guck dir mal genau an, was da im `AssertionError` landet:

Code: Alles auswählen

AssertionError: [<ast.Expr object at 0x7f1a2e297790>]

und wie sich das von dem Fall unterscheidet, bei dem das `case` für `Interactive` fehlt.

Und wenn es nicht klar wird, ist der Unterschied auch in der Dokumentation von `Interactive` beschrieben.

[Dennis89]

Ach die Liste.

Code: Alles auswählen

case Interactive(body=body):
    return evaluate(*body)

So funktioniert das schon mal, weil die Liste nur ein Objekt enthält.

Vielen Dank.

Ich schau mal weiter, ob ich jetzt die Zuweisung eingebaut bekomme.


Grüße
Dennis

[narpfel]

Und was ist, wenn die Liste mehr als ein Element enthält? `1 + 2; 3 * 4` ist eine gültige Eingabe für `mode="single"`.

[Dennis89]

Dann funktioniert es nicht
Das war mit bewusst, deswegen schrieb ich, das es nur funktioniert, weil die Liste ein Objekt enthält. Das Problem muss ich noch lösen.

Das ganze ist wieder eine "Rätsel"-Aufgabe, es gibt verschiedene Testfälle, die öffentlich sind und wenn man die bestanden hat, wird der Code noch auf weitere Daten getestet. Ich bin gerade dabei die öffentlichen Testfälle abzuarbeiten. Für heute reicht es mir aber.

Wollte trotzdem noch meinen aktuellen Stand posten, damit ihr sehr, was ich so mache. Die Klasse, wie auch die `input`-Methode war vorgegeben und auch wenn die Built-In Funktion damit überschrieben wird, muss ich es so lassen, sonst funktionieren auf der Webseite die Testfälle nicht.

Code: Alles auswählen

#!/usr/bin/env python
from ast import (Add, Assign, BinOp, Constant, Div, Expr, Interactive, Mult,
                 Sub, UnaryOp, USub, parse)
from operator import add, mul, neg, sub, truediv

OPERATOR_TYPE_TO_FUNCTION = {Add: add, Mult: mul, Sub: sub, USub: neg, Div: truediv}


class Interpreter:
    def __init__(self):
        self.variables = {}

    def input(self, expression):
        try:
            return self.variables[expression]
        except KeyError:
            pass
        expression_node = parse(expression, mode="single")
        if isinstance(expression_node.body[0], Assign):
            result = evaluate(expression_node)
            self.variables[expression_node.body[0].targets[0].id] = int(expression_node.body[0].value.value)
            return result
        return evaluate(expression_node)



def evaluate(node):
    match node:
        case BinOp(left=left, op=op, right=right):
            return OPERATOR_TYPE_TO_FUNCTION[type(op)](evaluate(left), evaluate(right))
        case Constant(value=value):
            return value
        case Expr(value=body):
            return evaluate(body)
        case UnaryOp(op=op, operand=operand):
            return OPERATOR_TYPE_TO_FUNCTION[type(op)](evaluate(operand))
        case Interactive(body=body):
            return evaluate(*body)
        case Assign(value=value):
            return evaluate(value)
        case _:
            raise AssertionError(node)


def main():
    interpreter = Interpreter()
    assert interpreter.input("1 + 1") == 2
    assert interpreter.input("2 - 1") == 1
    assert interpreter.input("2 * 3") == 6
    assert interpreter.input("8 / 4") == 2
    #
    # Can't find Modulo in `Ast`
    assert interpreter.input("7 % 4") == 3
    assert interpreter.input("x = 1") == 1
    assert interpreter.input("x") == 1
    #
    # No idea how to handle something like that
    assert interpreter.input("x + 3") == 4
    print("Done!")
    # interpreter.input("y")


if __name__ == "__main__":
    main()

Hilfestellung zu meinen Problemen, die ich kommentiert habe, wie allgemeine Kritik ist wie immer gerne gesehen.
Wie das von @narpfel angesprochene Problem mit der Liste gelöst wird, dazu bitte nichts schreiben, da will ich erst selbst noch einmal versuchen, das zu lösen.


Danke und Grüße
Dennis

[narpfel]

Hilfestellung zu meinen Problemen, die ich kommentiert habe, wie allgemeine Kritik ist wie immer gerne gesehen.

Meine persönliche Vorgehensweise wäre, für das gewünschte Feature einen Test Case zu schreiben (hast du schon), den Test Case auszuführen und dann in der Fehlermeldung zu gucken, wo was noch nicht implementiert ist. Zum Beispiel für Modulo bekommst du einen `KeyError`, der dir sagt, welcher Key in welchem Dictionary fehlt und wo der Zugriff stattfindet. Also muss man da den passenden Key (den kennst du ja, der steht im Traceback) in das passende Dict einfügen. Hint

[__blackjack__]

@Dennis89: Durch eine `input()`-Methode wird doch die eingebaute Funktion nicht überschrieben. Die kann man weiterhin benutzen. Selbst in der `input()`-Methode ginge das doch ohne Probleme.

Das mit dem `ast.Assign` sollte nicht in der `input()`-Methode stehen sondern auch in der `evaluate()`-Funktion. Dazu muss die Funktion natürlich die Variablen kennen. Also entweder reicht man die durch die `evaluate()`-Aufrufe durch, oder man macht `evaluate()` zu einer Methode von `Interpreter` und kann über `self` auf die Variablen zugreifen.

[Dennis89]

Danke für eure Antworten.

Das mit `%` war ja easy, oh man.

Das mit `input` war Quatsch von mir.

Das mit dem `ast.Assign` sollte nicht in der `input()`-Methode stehen sondern auch in der `evaluate()`-Funktion

Du meintest den Teil mit `isinstance` ? Das führte zu Probleme, weil `evaluate` immer wieder aufgerufen wird und ich will, dass die `if`-Abfrage nur ein Mal ausgeführt wird, weil nicht alle `Assign`-Objekte auch die gleichen Attribute haben.

Mit folgendem Code habe ich jetzt alle Tests erfolgreich bestanden:

Code: Alles auswählen

#!/usr/bin/env python
from ast import (Add, Assign, BinOp, Constant, Div, Expr, Interactive, Mod,
                 Mult, Name, Sub, UnaryOp, USub, parse)
from operator import add, mod, mul, neg, sub, truediv

OPERATOR_TYPE_TO_FUNCTION = {
    Add: add,
    Mult: mul,
    Sub: sub,
    USub: neg,
    Div: truediv,
    Mod: mod,
}


class Interpreter:
    def __init__(self):
        self.variables = {}

    def input(self, expression):
        if expression.isspace() or not expression:
            return ""
        try:
            return self.variables[expression]
        except KeyError:
            pass
        node = parse(expression, mode="single")
        if isinstance(node.body[0], Assign):
            result = self.evaluate(node)
            self.variables[node.body[0].targets[0].id] = result
            return result
        return self.evaluate(node)

    def evaluate(self, node):
        match node:
            case BinOp(left=left, op=op, right=right):
                return OPERATOR_TYPE_TO_FUNCTION[type(op)](
                    self.evaluate(left), self.evaluate(right)
                )
            case Constant(value=value):
                return value
            case Expr(value=body):
                return self.evaluate(body)
            case UnaryOp(op=op, operand=operand):
                return OPERATOR_TYPE_TO_FUNCTION[type(op)](self.evaluate(operand))
            case Interactive(body=body):
                return self.evaluate(*body)
            case Assign(value=value):
                return self.evaluate(value)
            case Name(id=id):
                try:
                    return self.evaluate(Constant(value=self.variables[id]))
                except KeyError:
                    raise ValueError(
                        f"ERROR: Invalid identifier. No variable with name '{id}'"
                        f"was found."
                    )
            case _:
                raise AssertionError(node)


def main():
    interpreter = Interpreter()
    assert interpreter.input("1 + 1") == 2
    assert interpreter.input("2 - 1") == 1
    assert interpreter.input("2 * 3") == 6
    assert interpreter.input("8 / 4") == 2
    assert interpreter.input("7 % 4") == 3
    assert interpreter.input("x = 1") == 1
    assert interpreter.input("x") == 1
    assert interpreter.input("x + 3") == 4
    assert interpreter.input(" ") == ""
    assert interpreter.input("") == ""
    print("Done!")


if __name__ == "__main__":
    main()

TODO:
- Den Teil mit der Liste
- Je nach der Antwort, den Teil mit der `isinstance`-Abfrage aus lagern.


Grüße
Dennis