Perché determinare se una funzione è puramente difficile?

Question

Ieri ero alla convention di StackOverflow Dev Days e uno dei relatori parlava di Python. Mostrò una funzione Memoize e chiesi se esistesse un modo per impedirne l'uso su una funzione non pura. Ha detto no, è praticamente impossibile, e se qualcuno riuscisse a trovare un modo per farlo sarebbe una grande tesi di dottorato.

Questo tipo di mi ha confuso, perché non sembra così difficile per un compilatore/interprete risolvere in modo ricorsivo. In pseudocode:

function isPure(functionMetadata): boolean; 
begin 
    result = true; 
    for each variable in functionMetadata.variablesModified 
     result = result and variable.isLocalToThisFunction; 
    for each dependency in functionMetadata.functionsCalled 
     result = result and isPure(dependency); 
end; 

Questa è l'idea di base. Ovviamente avresti bisogno di una sorta di controllo per prevenire la ricorsione infinita su funzioni reciprocamente dipendenti, ma non è troppo difficile da configurare.

Le funzioni di ordine superiore che prendono i puntatori di funzione potrebbero essere problematiche, poiché non possono essere verificate staticamente, ma la mia domanda iniziale presuppone che il compilatore abbia una sorta di vincolo di linguaggio per indicare che è possibile passare solo un puntatore a funzione pura ad un certo parametro. Se esistesse, ciò potrebbe essere usato per soddisfare la condizione.

Ovviamente questo sarebbe più semplice in un linguaggio compilato che in uno interpretato, dal momento che tutto questo crunch numerico sarebbe fatto prima che il programma venga eseguito e quindi non rallentare nulla, ma non vedo davvero alcun problema fondamentale che renderebbe impossibile la valutazione.

Qualcuno con un po 'più di conoscenza in questo settore sa cosa mi manca?

Answer 1

È particolarmente difficile in Python. Poiché anObject.aFunc può essere modificato arbitrariamente in fase di runtime, non è possibile determinare in fase di compilazione quale funzione effettuerà la chiamata anObject.aFunc() o anche se sarà una funzione.

Answer 2

Ecco la prima cosa che mi è venuta in mente quando ho letto la tua domanda.

Classe gerarchie

Determinare se una variabile viene modificata include l'atto di scavare attraverso ogni singolo metodo che è chiamato sulla variabile per determinare se è mutazione. Questo è ... un po 'semplice per un tipo sigillato con un metodo non virtuale.

Ma considera metodi virtuali. È necessario trovare ogni singolo tipo derivato e verificare che ogni singolo override di quel metodo non muti lo stato. Determinare ciò è semplicemente impossibile in qualsiasi linguaggio/framework che consenta la generazione di codice dinamico o sia semplicemente dinamico (se possibile, è estremamente difficile). Il motivo per cui è che il set di tipi derivati ​​non è stato risolto perché ne può essere generato uno nuovo in fase di runtime.

Prendere C# come esempio. Non c'è nulla che mi impedisca di generare una classe derivata in fase di esecuzione, che sovrascrive quel metodo virtuale e modifica lo stato. Una verifica statica non sarebbe in grado di rilevare questo tipo di modifica e quindi non è stato possibile validare il metodo è stato puro o no.

Answer 3

È inoltre necessario annotare ogni chiamata di sistema, ogni FFI, ...

E, inoltre, il più piccolo 'fuga' tende a fuoriuscire in tutta la base di codice.

Non è un problema teoricamente intrattabile, ma in pratica è molto molto difficile fare in un modo che l'intero sistema non si senta fragile.

Per inciso, non penso che questo faccia una buona tesi di dottorato; Haskell ha già effettivamente (una versione di) questo, con la monade IO.

E sono sicuro che molte persone continuano a guardare questo "in pratica". (speculazione selvaggia) In 20 anni potremmo avere questo.

Answer 4

In aggiunta alle altre risposte eccellenti qui: Lo pseudocodice controlla solo se una funzione modifica le variabili. Ma non è proprio quello che significa "puro". "Puro" in genere significa qualcosa di più vicino a "referenzialmente trasparente". In altre parole, l'output dipende completamente dall'input. Quindi qualcosa di semplice come leggere l'ora corrente e farne un fattore nel risultato (o leggere dall'input, o leggere lo stato della macchina, o ...) rende la funzione non pura senza modificare alcuna variabile.

Inoltre, è possibile scrivere una funzione "pura" che ha modificato le variabili.

Answer 5

Penso che il problema principale sarebbe farlo in modo efficiente.

D-language ha funzioni pure, ma è necessario specificarle da soli, in modo che il compilatore sappia controllarle. Penso che se li specifichi manualmente, sarebbe più facile da fare.

Answer 6

Decidere se una determinata funzione è pura, in generale, è riducibile a decidere se un determinato programma si fermerà - ed è noto che il problema di interruzione è il tipo di problema che non può essere risolto in modo efficiente.

Answer 7

Si noti che la complessità dipende anche dalla lingua. Per i linguaggi più dinamici, è possibile ridefinire qualsiasi cosa in qualsiasi momento. Ad esempio, in Tcl

proc myproc {a b} { 
    if { $a > $b } { 
     return $a 
    } else { 
     return $b 
    } 
} 

Ogni singolo pezzo di esso può essere modificato in qualsiasi momento. Ad esempio:

• il comando "if" potrebbe essere riscritto da usare e aggiornare le variabili globali
• il comando "ritorno", lungo le stesse linee, potrebbe fare la stessa cosa
• il potrebbe essere un'esecuzione traccia sul comando if che, quando viene usato "if", il comando di ritorno viene ridefinito in base agli input al comando if

Certo, Tcl è un caso estremo; uno dei linguaggi più dinamici che ci sia. Detto questo, evidenzia il problema che può essere difficile determinare la purezza di una funzione anche dopo averla inserita.