Sviluppo di un'euristica per testare semplici funzioni anonime Python per l'equivalenza

Question

So come funziona il confronto delle funzioni in Python 3 (basta confrontare l'indirizzo in memoria) e capisco perché.

Capisco anche che il confronto "vero" (le funzioni f e g restituiscono lo stesso risultato dato gli stessi argomenti, per qualsiasi argomento?) È praticamente impossibile.

Sto cercando qualcosa in mezzo. Voglio che il confronto di lavorare su casi più semplici di funzioni identiche, e forse alcuni tra quelli meno banali:

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 

nota che io sono interessato a risolvere questo problema per funzioni anonime (lambda), ma non mi dispiacerebbe se la soluzione funziona anche per le funzioni con nome.

La motivazione è che all'interno del modulo blist, sarebbe bello verificare che due istanze di sortedset abbiano la stessa funzione di ordinamento prima di eseguire un unione, ecc. Su di esse.

Le funzioni con nome sono di minore interesse perché posso assumere che siano diverse quando non sono identiche. Dopo tutto, supponiamo che qualcuno abbia creato due ordinamenti con una funzione con nome nell'argomento key. Se intendono che queste istanze siano "compatibili" ai fini delle operazioni di set, probabilmente utilizzerebbero la stessa funzione, piuttosto che due funzioni separate denominate che eseguono operazioni identiche.

Posso solo pensare a tre approcci. Tutti sembrano difficili, quindi ogni idea è apprezzata.

1. bytecodes Confrontando potrebbero funzionare ma potrebbe essere fastidioso che è attivazione dipendente (e quindi il codice che ha lavorato su un pitone rompe su un altro).

2. La comparazione del codice sorgente con token sembra ragionevole e portabile. Certo, è meno potente (dal momento che è più probabile che le stesse funzioni vengano rifiutate).

3. Un euristico solido preso in prestito da alcuni libri di calcolo simbolici è teoricamente l'approccio migliore. Potrebbe sembrare troppo pesante per il mio scopo, ma in realtà potrebbe essere una buona misura in quanto le funzioni lambda sono in genere minuscole e quindi potrebbe funzionare velocemente.

EDIT

Un esempio più complesso, sulla base del commento di @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()]) 

Sarebbe mi aspetto che le funzioni chiave per s1 e s2 per valutare come uguali?

Se il codice di intervento contiene una qualsiasi chiamata di funzione, il valore di fields può essere modificato, determinando diverse funzioni chiave per s1 e s2. Dal momento che chiaramente non faremo analisi del flusso di controllo per risolvere questo problema, è chiaro che dobbiamo valutare queste due funzioni lambda come diverse, se stiamo cercando di eseguire questa valutazione prima del runtime. (Anche se fields non fosse globale, avrebbe potuto esserci un altro nome associato ad esso, ecc.) Ciò ridurrebbe drasticamente l'utilità di tutto questo esercizio, poiché poche funzioni lambda non avrebbero alcuna dipendenza dall'ambiente.

EDIT 2:

mi sono reso conto che è molto importante confrontare gli oggetti funzione come esistono in fase di esecuzione. Senza di ciò, tutte le funzioni che dipendono dalle variabili dall'ambito esterno non possono essere confrontate; e le funzioni più utili hanno tali dipendenze. Considerato in runtime, tutte le funzioni con la stessa firma sono comparabili in modo pulito e logico, indipendentemente da cosa dipendono, se sono impure, ecc.

Di conseguenza, ho bisogno non solo del bytecode ma anche del stato globale al momento della creazione dell'oggetto funzione (presumibilmente __globals__). Quindi devo abbinare tutte le variabili dall'ambito esterno ai valori da __globals__.

Answer 1

Modificato per controllare se lo stato esterno influisce sulla funzione di ordinamento e se le due funzioni sono equivalenti.

---

ho inciso fino dis.dis e gli amici per output in un oggetto simile a file globale. Ho quindi estratto i numeri di riga e i nomi delle variabili normalizzati (senza toccare le costanti) e ho confrontato il risultato.

È possibile pulire questo in modo che dis.dis e gli amici yield e fuori le righe in modo da non dover intercettare il loro output. Ma questo è un proof of concept funzionante per l'utilizzo di dis.dis per il confronto delle funzioni con modifiche minime.

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 

L'uscita è True, True, False e False ed è stabile. Il bool "Inquinato" è vero se l'output dipenderà dallo stato esterno - uno stato globale o una chiusura.

Answer 2

Quindi, prima affrontiamo alcuni problemi tecnici.

1) Codice byte: probabilmente non è un problema perché, invece di ispezionare il pyc (i file binari), è possibile utilizzare il modulo dis per ottenere il "bytecode". per esempio.

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

Non c'è bisogno di preoccuparsi della piattaforma.

2) Codice sorgente con codice. Ancora una volta python ha tutto il necessario per fare il lavoro. È possibile utilizzare il modulo ast per analizzare il codice e ottenere l'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()))))])" 

Quindi, la domanda che in realtà dovrebbe indirizzo è: è fattibile per determinare che due funzioni sono equivalenti analiticamente?

È facile per gli umani dire uguale a x+x, ma come possiamo creare un algoritmo per dimostrarlo?

Se si tratta di ciò che si vuole raggiungere, si consiglia di controllare questo fuori: http://en.wikipedia.org/wiki/Computer-assisted_proof

Tuttavia, se in ultima analisi, si vuole semplicemente affermare due diversi set di dati sono allineati nello stesso ordine, è sufficiente eseguire la funzione di ordinamento A sul set di dati B e viceversa, quindi controllare il risultato. Se sono identici, allora le funzioni sono probabilmente identiche dal punto di vista funzionale. Ovviamente, il controllo è valido solo per i suddetti set di dati.