Desarrollar una heurística para probar funciones anónimas simples de Python para la equivalencia

Question

Sé cómo funciona la comparación de funciones en Python 3 (simplemente comparando la dirección en la memoria), y entiendo por qué.

También entiendo que la comparación "verdadera" (¿las funciones f y g devuelven el mismo resultado dados los mismos argumentos, para cualquier argumento?) Es prácticamente imposible.

Estoy buscando algo intermedio. Quiero la comparación para trabajar en los casos más simples de funciones idénticas, y, posiblemente, algunos menos triviales:

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 

Tenga en cuenta que estoy interesado en la solución de este problema para funciones anónimas (lambda), pero no le importaría si la solución también funciona para funciones nombradas.

La motivación para esto es que dentro del módulo blist, sería bueno verificar que dos instancias sortedset tengan la misma función de clasificación antes de realizar una unión, etc. en ellas.

Las funciones nombradas son de menor interés porque puedo asumir que son diferentes cuando no son idénticas. Después de todo, supongamos que alguien creó dos conjuntos ordenados con una función nombrada en el argumento key. Si pretenden que estas instancias sean "compatibles" para los propósitos de las operaciones de conjunto, probablemente usarían la misma función, en lugar de dos funciones nombradas separadas que realizan operaciones idénticas.

Solo puedo pensar en tres enfoques. Todos parecen difíciles, por lo que cualquier idea es apreciada.

1. bytecodes Comparando podrían funcionar pero podría ser molesto que es dependiente de la implementación (y por lo tanto el código que trabajó en uno de Python rompe en otro).

2. Comparar el código fuente tokenizado parece razonable y portátil. Por supuesto, es menos potente (ya que es más probable que se rechacen funciones idénticas).

3. Una heurística sólida tomada de un libro de texto simbólico de cálculo es teóricamente el mejor enfoque. Puede parecer demasiado pesado para mi propósito, pero en realidad podría ser una buena opción, ya que las funciones de lambda suelen ser muy pequeñas, por lo que funcionarían rápidamente.

EDITAR

Un ejemplo más complicado, basado en el comentario de @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()]) 

qué esperaría las funciones clave para s1 y s2 para evaluar como iguales?

Si el código de intervenir contiene cualquier llamada de función en absoluto, el valor de fields se pueden modificar, lo que resulta en diferentes funciones de las teclas para s1 y s2. Como claramente no haremos un análisis de flujo de control para resolver este problema, está claro que tenemos que evaluar estas dos funciones lambda como diferentes, si estamos tratando de realizar esta evaluación antes del tiempo de ejecución. (Incluso si fields no fuera global, podría tener otro nombre vinculado a él, etc.) Esto reduciría drásticamente la utilidad de todo este ejercicio, ya que pocas funciones lambda no tendrían ninguna dependencia del entorno.

EDIT 2:

me di cuenta de que es muy importante comparar los objetos de función tal como existen en tiempo de ejecución. Sin eso, no se pueden comparar todas las funciones que dependen de variables del alcance externo; y las funciones más útiles sí tienen tales dependencias. Considerado en tiempo de ejecución, todas las funciones con la misma firma son comparables de forma limpia y lógica, independientemente de en qué dependan, si son impuras, etc.

Como resultado, no solo necesito el bytecode sino también el estado global a partir del momento en que se creó el objeto de función (presumiblemente __globals__). Entonces tengo que unir todas las variables desde el alcance exterior a los valores de __globals__.

Answer 1

Editado para verificar si el estado externo afectará a la función de clasificación, así como si las dos funciones son equivalentes.

---

I hackeado dis.dis y amigos a la salida a un objeto de tipo fichero global. Luego eliminé los números de línea y normalicé los nombres de las variables (sin tocar las constantes) y comparé el resultado.

Puede limpiar esto tan dis.dis y amigos yield líneas editadas para que no tenga que atrapar sus resultados. Pero esta es una prueba de concepto que funciona para usar dis.dis para comparar funciones con cambios mínimos.

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 

La salida es True, True, False, y False y es estable. El bool "Polluted" es verdadero si la salida dependerá del estado externo, ya sea estado global o cierre.

Answer 2

Entonces, vamos a abordar algunos problemas técnicos primero.

1) Código de byte: probablemente no sea un problema porque, en lugar de inspeccionar el pyc (los archivos binarios), puede usar el módulo dis para obtener el "bytecode". p.ej.

>>> f = lambda x, y : x+y 
>>> dis.dis(f) 
    1   0 LOAD_FAST    0 (x) 
       3 LOAD_FAST    1 (y) 
       6 BINARY_ADD   
       7 RETURN_VALUE 

No hay necesidad de preocuparse por la plataforma.

2) Código fuente tokenizado. De nuevo, Python tiene todo lo que necesitas para hacer el trabajo. Puede usar el módulo ast para analizar el código y obtener el ast.

>>> a = ast.parse("f = lambda x, y : x+y") 
>>> ast.dump(a) 
"Module(body=[Assign(targets=[Name(id='f', ctx=Store())], value=Lambda(args=arguments(args=[Name(id='x', ctx=Param()), Name(id='y', ctx=Param())], vararg=None, kwarg=None, defaults=[]), body=BinOp(left=Name(id='x', ctx=Load()), op=Add(), right=Name(id='y', ctx=Load()))))])" 

Por lo tanto, la pregunta que realmente debería dirección es: ¿es factible determinar que dos funciones son equivalentes analíticamente?

Es fácil para los humanos decir es igual a x+x, pero ¿cómo podemos crear un algoritmo para probarlo?

Si es lo que quiere lograr, es posible que desee comprobar esto: http://en.wikipedia.org/wiki/Computer-assisted_proof

Sin embargo, si en última instancia, lo único que desea hacer valer dos conjuntos de datos diferentes se clasifican en el mismo orden, sólo tiene que ejecute la función de clasificación A en el conjunto de datos B y viceversa, y luego verifique el resultado. Si son idénticos, entonces las funciones probablemente sean funcionalmente idénticas. Por supuesto, el cheque solo es válido para dichos conjuntos de datos.