在Python 3.6中解释AST：isinstance vs. monkey-patching vs. visit_NodeType vs. macros？

Question

在Python 3.6中解释AST：isinstance vs. monkey-patching vs. visit_NodeType vs. macros？

pythonpython-3.xmonkeypatchingvisitor-patternalgebraic-data-types

5

假设我想编写一个小型解释器，可以评估具有二进制操作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，但是看起来有些混乱。

以下是几个更多的选项，但是每个选项都有一些缺点：

使用猴子补丁：例如这个例子在解释器中定义了一堆???_execute方法，然后将它们附加到表示AST元素的类上。对我来说看起来非常可怕（如果我尝试并行执行两个不同解释器的两个单独的AST会发生什么事情，一切都会崩溃，对吧？）。
定义一个通用的NodeVisitor，为每种类型的AST节点都有一个visit_???方法，然后进行一些分派，将字符串中的正确方法名和传递给visit方法的实例的类的名称粘合在一起。这似乎更加健壮，但我不喜欢方法名称被持续重建：解释器应该专注于AST，而不是生成自己的源代码（方法名称）。
使用一些额外的宏小玩意，显然可以生成case类。我目前不想使用任何第三方工具，我想要一个尽可能独立于其他所有内容的微小脚本。

我没有找到这个相关问题的令人满意的答案，因为唯一的答案只是链接到一些外部工具，而且这些工具也已经不再维护。

那么，在Python 3.6.x中是否有某种标准方法来定义AST的解释器，以避免上述缺点？还是应该坚持使用isinstance？或者实现好老式的Java风格的Visitor（不确定它是否被认为是Pythonic）？

编辑

使用 @juanpa.arrivillaga 提出的 functools，我得到了以下结果：

Use collections.namedtuple and 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)))))

However, it does not seem to work if ev is a method, because it cannot dispatch on the self-argument (see this related question), so I can get only a function ev, but no instance that represents the interperter.

- Andrey Tyukin

我不确定你的意思是什么：“这似乎更加健壮，但我不喜欢方法名称被永久重建：解释器应该集中于AST，而不是生成自己的源代码(方法名称)。” 你能详细说明一下吗？ - juanpa.arrivillaga

@juanpa.arrivillaga 抱歉，链接的博客文章确实有点长... 我指的是 def visit(self, node): method_name = 'visit_' + type(node).__name__ [...] 部分。如果我理解正确，它会在每次调用 NodeVisitor 上的 visit 方法时构建 method_name。这反过来意味着算术表达式的简单求值器将浪费比实际计算多一个数量级的时间在字符串操作上。 - Andrey Tyukin

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- juanpa.arrivillaga · Accepted Answer

如果您正在寻找更简洁的代码，我认为functools.singledispatch装饰器在这种情况下会很有用：

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)))))