代码之家 › 专栏 › 技术社区 › Andrey Tyukin

在Python 3.6中解释AST:isinstance vs.monkey patching vs.visit\u NodeType vs.macros?

algebraic-data-types visitor-pattern monkeypatching python-3.x python

Andrey Tyukin · 技术社区 · 8 年前

假设我想写一个小小的解释器可以使用二进制操作计算表达式 Plus ,一元运算 Negate 和整数常量。

我现在只对AST的解释感兴趣, 为了简单起见,让我们跳过标记化和解析。

在Haskell中,或多或少有一种规范的方法可以做到这一点:

data Ast = Plus Ast Ast | Negate Ast | IntConst Int

ev :: Ast -> Int
ev (Plus a b) = (ev a) + (ev b)
ev (Negate x) = - (ev x)
ev (IntConst i) = i

main = print $ show $ ev $ (Plus (IntConst 50) (Negate $ IntConst 8))

现在,Python 3.6似乎没有代数数据类型。我的问题是似乎有许多可能的解决办法。最明显的一个正在使用 isinstance :

class Plus:
  def __init__(self, first, second):
    self.first = first
    self.second = second

class Negate:
  def __init__(self, first):
    self.first = first

class IntConst:
  def __init__(self, value):
    self.value = value

def ev(ast):
  if isinstance(ast, Plus):
    return ev(ast.first) + ev(ast.second)
  elif isinstance(ast, Negate):
    return - ev(ast.first)
  elif isinstance(ast, IntConst):
    return ast.value

print(ev(Plus(IntConst(50), Negate(IntConst(8)))))

这可以工作和打印 42 正如所料,但看起来有点吵。

这里还有几个选项,但每个选项都有一些缺点:

使用猴子补丁:例如。 this example 定义一组 ???_execute 方法,然后将它们附加到表示AST的元素。这看起来很可怕对我来说(我不想知道如果我试图执行两个独立的AST,两个不同的口译员并行:一切都会
定义 generic NodeVisitor 有一个 visit_??? -方法,然后执行一些调度传递给的实例的 visit -方法。这似乎更可靠,但我不喜欢永久性地重建方法名称:解释器应专注于AST, 而不是生成自己的源代码(方法名称)。
使用一些其他宏小控件 apparently can generate case-classes 。我目前不想使用任何第三方工具,我想要一点尽可能独立于其他所有内容的脚本。

我没有找到答案 this related question 令人满意,因为唯一的答案只是链接到一些外部工具, 此外,它不再被维护。

那么,Python 3.6中是否有一些标准方法。x为AST定义解释器没有上述缺点吗?还是我应该坚持 isinstance公司 Visitor (不确定是否被视为肾盂)?

编辑

使用 functools 由@juanpa提出。arrivillaga,我想到了以下几点:

使用 collections.namedtuple 和 functools.singledispatch :

from collections import namedtuple
from functools import singledispatch

Plus = namedtuple('Plus', ['left', 'right'])
Negate = namedtuple('Negate', ['arg'])
IntConst = namedtuple('IntConst', ['value'])

@singledispatch 
def ev(x): raise NotImplementedError("not exhaustive: %r" % (type(x)))
ev.register(Plus, lambda p: ev(p.left) + ev(p.right))
ev.register(Negate, lambda n: -ev(n.arg))
ev.register(IntConst, lambda c: c.value)

print(ev(Plus(IntConst(50), Negate(IntConst(8)))))

然而 如果 ev 是一种方法 ,因为它无法在 self -参数(请参见 this related question ),所以我只能得到一个函数 ,但没有表示interperter的实例。

1 回复 | 直到 8 年前

juanpa.arrivillaga 8 年前

如果您正在寻找更干净的代码,我认为 functools.singledispatch 在这种情况下,decorator将起作用:

import functools

class Plus:
  def __init__(self, first, second):
    self.first = first
    self.second = second

class Negate:
  def __init__(self, first):
    self.first = first

class IntConst:
  def __init__(self, value):
    self.value = value

@functools.singledispatch
def ev(ast):
    raise NotImplementedError('Unsupported type')

@ev.register(Plus)
def _(ast):
    return ev(ast.first) + ev(ast.second)

@ev.register(Negate)
def _(ast):
    return -ev(ast.first)

@ev.register(IntConst)
def _(ast):
    return ast.value

print(ev(Plus(IntConst(50), Negate(IntConst(8)))))