Domanda

Ero alla convention DevO di StackOverflow ieri e uno degli oratori stava parlando di Python. Ha mostrato una funzione Memoize e ho chiesto se ci fosse un modo per impedirne l'utilizzo su una funzione non pura. Ha detto di no, è praticamente impossibile, e se qualcuno potesse trovare un modo per farlo, farebbe un'ottima tesi di dottorato.

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

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 impedire la ricorsione infinita su funzioni reciprocamente dipendenti, ma non è troppo difficile da impostare.

Le funzioni di ordine superiore che accettano i puntatori a funzione potrebbero essere problematiche, poiché non possono essere verificate staticamente, ma la mia domanda originale presuppone che il compilatore abbia una sorta di vincolo di linguaggio per designare che solo un puntatore a funzione pura può essere passato a un determinato parametro. Se ne esistesse uno, potrebbe essere utilizzato per soddisfare la condizione.

Ovviamente questo sarebbe più facile in un linguaggio compilato che in un linguaggio interpretato, dal momento che tutto questo scricchiolio dei numeri sarebbe fatto prima che il programma fosse eseguito e quindi non rallentasse nulla, ma non vedo davvero alcun problema fondamentale che potrebbe rendere impossibile la valutazione.

Qualcuno con un po 'più di conoscenza in quest'area sa cosa mi sto perdendo?

È stato utile?

Soluzione

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

Altri suggerimenti

Devi anche annotare ogni chiamata di sistema, ogni FFI, ...

E inoltre la più piccola 'perdita' tende a penetrare nell'intera base di codice.

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

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

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

Oltre alle altre eccellenti risposte qui: il tuo pseudocodice esamina solo se una funzione modifica le variabili. Ma non è proprio quello che "puro" si intende. & Quot; Pure " 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 rendere quel fattore nel risultato (o leggere dall'input, o leggere lo stato della macchina, o ...) rende la funzione non pura senza modificare alcuna variabile.

Inoltre, potresti scrivere un " puro " funzione che ha modificato le variabili.

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

  

Gerarchie di classe

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

Ma considera i metodi virtuali. È necessario trovare ogni singolo tipo derivato e verificare che ogni singola sostituzione di quel metodo non muta lo stato. Determinare questo non è semplicemente possibile in nessun linguaggio / framework che consenta la generazione di codice dinamico o è semplicemente dinamico (se possibile, è estremamente difficile). Il motivo è che l'insieme di tipi derivati ??non è stato risolto perché è possibile generarne uno nuovo in fase di esecuzione.

Prendi C # come esempio. Non c'è nulla che mi impedisce di generare una classe derivata in fase di runtime che ignora quel metodo virtuale e modifica lo stato. Una verifica statica non sarebbe in grado di rilevare questo tipo di modifica e quindi non potrebbe validare il metodo era puro o no.

Penso che il problema principale sarebbe farlo in modo efficiente.

Il linguaggio D ha funzioni pure ma devi specificarle tu stesso, in modo che il compilatore sappia controllarle. Penso che se le specifichi manualmente, sarebbe più facile farlo.

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

Nota 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 può essere modificato in qualsiasi momento. Ad esempio:

  • il " if " Il comando può essere riscritto per utilizzare e aggiornare le variabili globali
  • il " return " comando, sulla stessa linea, potrebbe fare la stessa cosa
  • potrebbe essere una traccia di esecuzione sul comando if che, quando " if " viene utilizzato, il comando return viene ridefinito in base agli input del comando if

Certamente, 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.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top