È possibile sapere se due funzioni Python sono funzionalmente equivalenti?

Diciamo che ho due funzioni pitone f e g:È possibile sapere se due funzioni Python sono funzionalmente equivalenti?

def f(x): 
    y = x**2 + 1 
    return y 

def g(x): 
    a = x**2 
    b = a + 1 
    return b

Queste due funzioni sono chiaramente funzionalmente equivalente (entrambi tornare x**2 + 1).

mia definizione di funzionalmente equivalente è la seguente:

Se due funzioni f e g produce sempre la stessa uscita dato lo stesso input, quindi f e g sono funzionalmente equivalenti.

Inoltre, diciamo che nessuna variabile globale è coinvolta in f e g.

È possibile determinare automaticamente (senza ispezione umana) se le funzioni python f e g sono funzionalmente equivalenti?

fonte

2016-04-25 applecider

Immagino che si possa verificare se sono compilati nello stesso bytecode, ma che potrebbero produrre falsi negativi. – TigerhawkT3

All'interno di un margine di errore, basta provare un gruppo di input casuali. –

@ TigerhawkT3 sapete se 'f' e' g' dell'esempio precedente saranno compilati nello stesso bytecode? – applecider

Per Rice's Theorem, n. Se è possibile farlo, è possibile risolvere il halting problem. (Questo è vero anche se f e g sono sempre garantiti per fermare.)

fonte

2016-04-25 23:36:04 user2357112

Ah in realtà questo non è * abbastanza * corretto, perché le funzioni python non sono oggetti astratti e opachi. Puoi confrontare per vedere se hanno lo stesso bytecode. – Marcin

@Marcin: Innanzitutto, [no, il confronto del bytecode non funziona. A tutti.] (Http://ideone.com/x0FiiZ) In secondo luogo, anche se si aggiungono le altre caratteristiche distintive che è necessario confrontare, il confronto continua a non riconoscere le due funzioni dalla domanda come equivalenti. In terzo luogo, anche le macchine di Turing non sono opache. Puoi confrontare e analizzare due macchine di Turing con la stessa facilità con cui puoi confrontare e analizzare due funzioni Python, ma nessuna delle due analisi sarà in grado di rispondere a domande non banali come "il mio nuovo algoritmo ha gli stessi risultati di quello vecchio?" – user2357112

Se le funzioni sono in realtà lo stesso oggetto, si può semplicemente fare f == g e vedere se sono lo stesso oggetto.

In secondo luogo, se le funzioni hanno lo stesso codice byte (f.func_code.co_code), sono equivalenti.

Equivalentemente (ma probabilmente più portabile), è possibile utilizzare dis.dis per ottenere le stesse informazioni. Si noti che questo sarà soggetto a falsi negativi, come in questo caso.

Capisco che dill andrà meglio, e ti permettono di recuperare il testo della funzione. Con queste informazioni, è possibile utilizzare ast per analizzare il testo ed eseguire analisi simili per ottimizzare i compilatori, per decidere se il codice può essere "ottimizzato" sullo stesso albero di sintassi. Ancora una volta, ci saranno funzioni funzionalmente equivalenti che non possono essere semplicemente ridotte allo stesso modo.

Quindi, sì per alcune coppie di funzioni funzionalmente equivalenti questo rilevamento è possibile, ma ci saranno sempre falsi negativi.

fonte

2016-04-26 01:42:28 Marcin

È possibile sapere se due funzioni Python sono funzionalmente equivalenti?

risposta

Problemi correlati