Mein Fazit: hmmm... Es ist jedenfalls expressiver als das Visitor Pattern und in einfachen Fällen auch deutlich übersichtlicher, aber wenn die Pattern komplizierter werden, haben Sprachen wie Prolog oder Haskell die Nase immer noch vorn.
BTW: Expression Trees und Monaden sind cool.
Code: Alles auswählen
from ast import (
AST,
BinOp,
BitAnd as And,
BitOr as Or,
Name,
USub as Not,
UnaryOp,
dump
)
from collections import defaultdict
from dataclasses import dataclass
from functools import partial, reduce
from toolz.functoolz import compose
@dataclass
class Expression:
node: AST
def __repr__(self):
return dump(self.node)
def __str__(self):
return stringify(self.node)
unit = Expression
def bind(expr, mfunc):
return mfunc(expr.node)
def mlift(func):
return compose(unit, func)
@mlift
def name(id):
return Name(id=id)
def unary_op(op):
@mlift
def op_method(operand):
return UnaryOp(op(), operand.node)
return op_method
def binary_op(op):
@mlift
def op_method(left, right):
return BinOp(left.node, op(), right.node)
return op_method
Expression.__or__ = binary_op(Or)
Expression.__and__ = binary_op(And)
Expression.__neg__ = unary_op(Not)
def str_or(left, right):
return f'({left} | {right})'
def str_and(left, right):
return f'({left} & {right})'
def str_not(operand):
return f'-{operand}'
def stringify(node):
match node:
# Terminal:
case Name():
return node.id
# Disjunction:
case BinOp(op=Or()):
return str_or(stringify(node.left), stringify(node.right))
# Conjunction:
case BinOp(op=And()):
return str_and(stringify(node.left), stringify(node.right))
# Negation:
case UnaryOp(op=Not()):
return str_not(stringify(node.operand))
# Error:
case _:
raise TypeError(f'Unknown type: {type(node)}')
def op_or(left, right):
return BinOp(op=Or(), left=left, right=right)
def op_and(left, right):
return BinOp(op=And(), left=left, right=right)
def op_not(operand):
return UnaryOp(op=Not(), operand=operand)
def _normalize(node):
match node:
# Terminal:
case Name():
return node
# Disjunction:
case BinOp(op=Or()):
return _normalize_or(node.left, node.right)
# Conjunction:
case BinOp(op=And()):
return _normalize_and(node.left, node.right)
# Negation:
case UnaryOp(op=Not()):
return _normalize_not(node.operand)
# Error:
case _:
raise TypeError(f'Unknown type: {type(node)}')
def _normalize_or(left, right):
match [_normalize(left), _normalize(right)]:
# associate right (a | b) | c <==> a | (b | c):
case [BinOp(op=Or(), left=inner_left, right=inner_right), right]:
return _normalize(op_or(inner_left, op_and(inner_right, right)))
# already in normal form:
case [left, right]:
return op_or(left, right)
def _normalize_and(left, right):
match [_normalize(left), _normalize(right)]:
# distribute a & (b | c) <==> (a & b) | (a & c):
case [left, BinOp(op=Or(), left=inner_left, right=inner_right)]:
return _normalize(op_or(op_and(left, inner_left),
op_and(left, inner_right)))
# distribute (a | b) & c <==> (a & c) | (b & c):
case [BinOp(op=Or(), left=inner_left, right=inner_right), right]:
return _normalize(op_or(op_and(inner_left, right),
op_and(inner_right, right)))
# associate right (a & b) & c <==> a & (b & c):
case [BinOp(op=And(), left=inner_left, right=inner_right), right]:
return _normalize(op_and(inner_left, op_and(inner_right, right)))
# already in normal form:
case [left, right]:
return op_and(left, right)
def _normalize_not(operand):
match _normalize(operand):
# DeMorgan's Law -(p | q) <==> (-p & -q):
case BinOp(op=Or(), left=left, right=right):
return _normalize(op_and(op_not(left), op_not(right)))
# DeMorgan's Law -(p & q) <==> (-p | -q):
case BinOp(op=And(), left=left, right=right):
return _normalize(op_or(op_not(left), op_not(right)))
# double negation -(-p) <==> p:
case UnaryOp(op=Not(), operand=operand):
return operand
# already normalized:
case operand:
return op_not(operand)
normalize = partial(bind, mfunc=mlift(_normalize))
def evaluate(expr, **kwargs):
return _evaluate(expr.node, defaultdict(bool, kwargs))
def _evaluate(node, env):
match node:
# Terminal:
case Name():
return env[node.id]
# Disjunction:
case BinOp(op=Or()):
return _evaluate(node.left, env) or _evaluate(node.right, env)
# Conjunction:
case BinOp(op=And()):
return _evaluate(node.left, env) and _evaluate(node.right, env)
# Negation:
case UnaryOp(op=Not()):
return not _evaluate(node.operand, env)
# Error:
case _:
raise TypeError(f'Unknown type: {type(node)}')
a = name('a')
b = name('b')
c = name('c')
expr = (a | -(b & -c)) & b
print(repr(expr))
print(expr)
print(normalize(expr))
print(evaluate(expr, a=True, b=True, c=False))
Code: Alles auswählen
BinOp(left=BinOp(left=Name(id='a'), op=BitOr(), right=UnaryOp(op=USub(), operand=BinOp(left=Name(id='b'), op=BitAnd(), right=UnaryOp(op=USub(), operand=Name(id='c'))))), op=BitAnd(), right=Name(id='b'))
((a | -(b & -c)) & b)
((a & b) | ((-b & b) | (c & b)))
True