python - 开发启发式方法来测试简单的匿名 Python 函数的等效性

Question

我知道函数比较在 Python 3 中是如何工作的(只是比较内存中的地址)，我明白为什么。

我也明白“真正的”比较(函数 f 和 g 在给定相同参数的情况下返回相同的结果，对于任何参数？)实际上是不可能的。

我正在寻找介于两者之间的东西。我希望比较适用于具有相同功能的最简单情况，并且可能适用于一些不那么琐碎的情况:

lambda x : x == lambda x : x # True
lambda x : 2 * x == lambda y : 2 * y # True
lambda x : 2 * x == lambda x : x * 2 # True or False is fine, but must be stable
lambda x : 2 * x == lambda x : x + x # True or False is fine, but must be stable

请注意，我有兴趣为匿名函数 ( lambda ) 解决这个问题，但不介意该解决方案是否也适用于命名函数。

这样做的动机是内部 blist模块，最好验证两个 sortedset实例在对它们执行联合等操作之前具有相同的排序功能。

命名函数不太有趣，因为当它们不相同时我可以假设它们是不同的。毕竟，假设有人在 key 中创建了两个带有命名函数的排序集。争论。如果他们希望这些实例为了集合操作而“兼容”，他们可能会使用相同的函数，而不是执行相同操作的两个单独的命名函数。

我只能想到三种方法。所有这些看起来都很难，所以任何想法都会受到赞赏。

1. 比较字节码可能有用，但它依赖于实现可能会很烦人(因此在一个 Python 上工作的代码在另一个 Python 上会中断)。

2. 比较标记化的源代码似乎是合理且可移植的。当然，它没有那么强大(因为相同的功能更有可能被拒绝)。

3. 从一些符号计算教科书中借鉴的可靠启发式算法在理论上是最好的方法。对于我的目的来说，它可能看起来太重了，但它实际上可能很合适，因为 lambda 函数通常很小，所以它运行得很快。

编辑

一个更复杂的例子，基于@delnan 的评论:

# global variable
fields = ['id', 'name']

def my_function():
  global fields
  s1 = sortedset(key = lambda x : x[fields[0].lower()])
  # some intervening code here
  # ...
  s2 = sortedset(key = lambda x : x[fields[0].lower()])

我会期待 s1 的关键功能吗？和 s2评估为平等？

如果中间代码包含任何函数调用，fields 的值可能会被修改，导致 s1 的不同键功能和 s2 .由于我们显然不会通过控制流分析来解决这个问题，所以很明显，如果我们试图在运行时之前执行此评估，我们必须将这两个 lambda 函数评估为不同的。 (即使 fields 不是全局的，它也可能绑定(bind)了另一个名称，等等)这将严重削弱整个练习的实用性，因为很少有 lambda 函数不依赖于环境。

编辑 2:

我意识到比较运行时存在的函数对象非常重要。否则，所有依赖于外部作用域变量的函数都无法进行比较；大多数有用的函数都有这样的依赖性。在运行时考虑，所有具有相同签名的函数都可以以一种干净、合乎逻辑的方式进行比较，无论它们依赖什么，是否不纯等等。

因此，我不仅需要字节码，还需要创建函数对象时的全局状态(大概是 __globals__ )。然后我必须将外部作用域中的所有变量与 __globals__ 中的值进行匹配.

Answer 1

编辑以检查外部状态是否会影响排序功能以及这两个功能是否等效。

---

我破解了 dis.dis 和 friend 们输出到一个全局文件类对象。然后，我删除了行号和规范化的变量名(不涉及常量)并比较了结果。

您可以清理它，以便 dis.dis 和 friend yield 输出行，这样您就不必捕获他们的输出。但这是使用 dis.dis 进行最小更改的功能比较的有效概念验证。

import types
from opcode import *
_have_code = (types.MethodType, types.FunctionType, types.CodeType,
              types.ClassType, type)

def dis(x):
    """Disassemble classes, methods, functions, or code.

    With no argument, disassemble the last traceback.

    """
    if isinstance(x, types.InstanceType):
        x = x.__class__
    if hasattr(x, 'im_func'):
        x = x.im_func
    if hasattr(x, 'func_code'):
        x = x.func_code
    if hasattr(x, '__dict__'):
        items = x.__dict__.items()
        items.sort()
        for name, x1 in items:
            if isinstance(x1, _have_code):
                print >> out,  "Disassembly of %s:" % name
                try:
                    dis(x1)
                except TypeError, msg:
                    print >> out,  "Sorry:", msg
                print >> out
    elif hasattr(x, 'co_code'):
        disassemble(x)
    elif isinstance(x, str):
        disassemble_string(x)
    else:
        raise TypeError, \
              "don't know how to disassemble %s objects" % \
              type(x).__name__

def disassemble(co, lasti=-1):
    """Disassemble a code object."""
    code = co.co_code
    labels = findlabels(code)
    linestarts = dict(findlinestarts(co))
    n = len(code)
    i = 0
    extended_arg = 0
    free = None
    while i < n:
        c = code[i]
        op = ord(c)
        if i in linestarts:
            if i > 0:
                print >> out
            print >> out,  "%3d" % linestarts[i],
        else:
            print >> out,  '   ',

        if i == lasti: print >> out,  '-->',
        else: print >> out,  '   ',
        if i in labels: print >> out,  '>>',
        else: print >> out,  '  ',
        print >> out,  repr(i).rjust(4),
        print >> out,  opname[op].ljust(20),
        i = i+1
        if op >= HAVE_ARGUMENT:
            oparg = ord(code[i]) + ord(code[i+1])*256 + extended_arg
            extended_arg = 0
            i = i+2
            if op == EXTENDED_ARG:
                extended_arg = oparg*65536L
            print >> out,  repr(oparg).rjust(5),
            if op in hasconst:
                print >> out,  '(' + repr(co.co_consts[oparg]) + ')',
            elif op in hasname:
                print >> out,  '(' + co.co_names[oparg] + ')',
            elif op in hasjrel:
                print >> out,  '(to ' + repr(i + oparg) + ')',
            elif op in haslocal:
                print >> out,  '(' + co.co_varnames[oparg] + ')',
            elif op in hascompare:
                print >> out,  '(' + cmp_op[oparg] + ')',
            elif op in hasfree:
                if free is None:
                    free = co.co_cellvars + co.co_freevars
                print >> out,  '(' + free[oparg] + ')',
        print >> out

def disassemble_string(code, lasti=-1, varnames=None, names=None,
                       constants=None):
    labels = findlabels(code)
    n = len(code)
    i = 0
    while i < n:
        c = code[i]
        op = ord(c)
        if i == lasti: print >> out,  '-->',
        else: print >> out,  '   ',
        if i in labels: print >> out,  '>>',
        else: print >> out,  '  ',
        print >> out,  repr(i).rjust(4),
        print >> out,  opname[op].ljust(15),
        i = i+1
        if op >= HAVE_ARGUMENT:
            oparg = ord(code[i]) + ord(code[i+1])*256
            i = i+2
            print >> out,  repr(oparg).rjust(5),
            if op in hasconst:
                if constants:
                    print >> out,  '(' + repr(constants[oparg]) + ')',
                else:
                    print >> out,  '(%d)'%oparg,
            elif op in hasname:
                if names is not None:
                    print >> out,  '(' + names[oparg] + ')',
                else:
                    print >> out,  '(%d)'%oparg,
            elif op in hasjrel:
                print >> out,  '(to ' + repr(i + oparg) + ')',
            elif op in haslocal:
                if varnames:
                    print >> out,  '(' + varnames[oparg] + ')',
                else:
                    print >> out,  '(%d)' % oparg,
            elif op in hascompare:
                print >> out,  '(' + cmp_op[oparg] + ')',
        print >> out

def findlabels(code):
    """Detect all offsets in a byte code which are jump targets.

    Return the list of offsets.

    """
    labels = []
    n = len(code)
    i = 0
    while i < n:
        c = code[i]
        op = ord(c)
        i = i+1
        if op >= HAVE_ARGUMENT:
            oparg = ord(code[i]) + ord(code[i+1])*256
            i = i+2
            label = -1
            if op in hasjrel:
                label = i+oparg
            elif op in hasjabs:
                label = oparg
            if label >= 0:
                if label not in labels:
                    labels.append(label)
    return labels

def findlinestarts(code):
    """Find the offsets in a byte code which are start of lines in the source.

    Generate pairs (offset, lineno) as described in Python/compile.c.

    """
    byte_increments = [ord(c) for c in code.co_lnotab[0::2]]
    line_increments = [ord(c) for c in code.co_lnotab[1::2]]

    lastlineno = None
    lineno = code.co_firstlineno
    addr = 0
    for byte_incr, line_incr in zip(byte_increments, line_increments):
        if byte_incr:
            if lineno != lastlineno:
                yield (addr, lineno)
                lastlineno = lineno
            addr += byte_incr
        lineno += line_incr
    if lineno != lastlineno:
        yield (addr, lineno)

class FakeFile(object):
    def __init__(self):
        self.store = []
    def write(self, data):
        self.store.append(data)

a = lambda x : x
b = lambda x : x # True
c = lambda x : 2 * x
d = lambda y : 2 * y # True
e = lambda x : 2 * x
f = lambda x : x * 2 # True or False is fine, but must be stable
g = lambda x : 2 * x
h = lambda x : x + x # True or False is fine, but must be stable

funcs = a, b, c, d, e, f, g, h

outs = []
for func in funcs:
    out = FakeFile()
    dis(func)
    outs.append(out.store)

import ast

def outfilter(out):
    for i in out:
        if i.strip().isdigit():
            continue
        if '(' in i:
            try:
                ast.literal_eval(i)
            except ValueError:
                i = "(x)"
        yield i

processed_outs = [(out, 'LOAD_GLOBAL' in out or 'LOAD_DECREF' in out)
                            for out in (''.join(outfilter(out)) for out in outs)]

for (out1, polluted1), (out2, polluted2) in zip(processed_outs[::2], processed_outs[1::2]):
    print 'Bytecode Equivalent:', out1 == out2, '\nPolluted by state:', polluted1 or polluted2

输出为True、True、False 和False，并且是稳定的。如果输出将取决于外部状态——全局状态或闭包，则“污染” bool 值为真。