Calcola se una funzione è pura

Sì, è possibile, a seconda della lingua.

In JavaScript, puoi capire se una funzione è pura secondo i seguenti criteri:

• Legge solo parametri e locals;

• Scrive solo i locali;

• sui non locali, chiama solo funzioni pure;

• Tutte le funzioni che chiama implicitamente sono pure, ad esempio toString ; e

• Scrive solo le proprietà dei locali se non sono alias non locali.

Aliasing non è possibile determinare in JavaScript nel caso generale, perché puoi sempre cercare proprietà di un oggetto in modo dinamico ( object["property"] ). Se non lo fai mai e hai la fonte dell'intero programma, allora penso che il problema sia trattabile. Avresti anche bisogno di informazioni su quali funzioni native hanno effetti collaterali, come console.log o quasi tutto ciò che riguarda il DOM.

Il termine "puro" potrebbe anche usare qualche chiarimento. Anche in un linguaggio di programmazione strongmente, tipizzato staticamente, puramente funzionale, in cui tutte le funzioni sono referenzialmente trasparenti, una funzione può ancora non riuscire a terminare. Quindi, quando parliamo di id :: a -> a , quello che stiamo realmente dicendo non è:

Given some value of type a, the function id produces a value of type a.

Piuttosto:

Given some value of type a, the function id does not produce a value which is not of type a.

Perché un'implementazione valida di id è error "Not implemented!" . Come sottolinea Peteris, questa non totalità potrebbe essere vista come una sorta di impurità. Koka è un linguaggio di programmazione funzionale, con sintassi modellata su JavaScript, che può dedurre possibili effetti come la divergenza (nonterminazione), trasparenza referenziale, lancio di eccezioni e azioni I / O.

No. Puoi facilmente verificare se una funzione esegue solo operazioni "pure-safe", come descritto nella risposta di Jon Purdy, ma che non è IMO sufficiente per rispondere alla domanda.

Considera questa funzione:

function possiblyPure(x) {
    if (someCheck(x)) {
        return x+1; // pure code path
    }
    else {
        console.log("I'm so unpure..."); // unpure code path
    }
}

Ovviamente, se someCheck non è sicuro, così è possiblyPure . Ma, se someCheck è puro e restituisce true per ogni possibile valore di x , possiblyPure è puro, poiché il percorso del codice non protetto è irraggiungibile!

E qui arriva la parte difficile: determinare se someCheck restituisce true per ogni input possibile. Cercare di rispondere a questa domanda ti porta immeditamente nel regno del problema e di simili problemi indecidibili.

EDIT: Prova che è impossibile

C'è qualche incertezza se o no una funzione pura deve terminare su ogni input possibile. Ma in entrambi i casi, il problema dell'arresto può essere usato per mostrare che il controllo della purezza è impossibile.

Caso A) Se per terminare su ogni input possibile è necessaria una pura funzione, avere per risolvere il problema di interruzione per determinare se la funzione è pura o meno. Poiché questo è noto per essere impossibile, con questa definizione, la purezza non può essere calcolata.

Caso B) Se una funzione pura è autorizzata a non terminare su alcuni input, possiamo costruire qualcosa del genere: Supponiamo che isPure(f) calcoli se f è una stringa che definisce una funzione pura.

function halts(f) {
   var fescaped = f.replace(/\"/g, '\"');
   var upf = 'function() { '+f+'("'+fescaped+'\); console.log("unpure"); }';
   return isPure(upf);
}

Ora isPure deve determinare se f si arresta o meno sulla propria fonte come input. Se si ferma, upf non è sicuro; se non termina, upf è puro iff f è puro.

Se isPure ha funzionato come previsto (restituisce risultati corretti e termina su ogni input), avremmo risolto il problema di interruzione (*)! Poiché questo è noto per essere impossibile, isPure non può esistere.

(*) per le funzioni JavaScript pure, che è sufficiente per risolverlo anche per il turing machine.

Questa domanda stackoverflow ha una risposta da yfeldblum che è rilevante qui. (E ha qualche svantaggio per qualche ragione che non riesco a capire: sarebbe una cattiva etichetta sputare qualcosa di vecchio di 3 anni?). Dà una dimostrazione che se una funzione è pura è riducibile al problema dell'arresto in un commento.

Penso che da un punto di vista pratico non sarebbe troppo difficile per alcune lingue se si lascia che la funzione restituisca sì, no o forse. Stavo guardando un video su Clojure un paio di giorni fa, e l'oratore aveva fatto un conteggio di casi di impurità in una base di codice cercando per circa 4 diverse stringhe (come "ref"). A causa dell'enfasi posta da Clojure sulla purezza e segregazione delle cose impure, era banale, ma non era esattamente quello che cercavi.

Quindi, teoricamente impossibile, praticamente possibile se modifichi un po 'la questione, e penso che quanto sarebbe difficile dipenderebbe molto dalla lingua. Linguaggi più semplici / più puliti con un focus sull'immutabilità e una buona riflessione sarebbero più facili.

Ottima domanda.

Il meglio che puoi fare nella pratica, assumendo che non sia possibile ascoltare le azioni di I / O per chiamare la funzione più volte possibile. Quindi controlla se il valore restituito è consistente.

Ma non puoi farlo in generale. Probabilmente, i programmi senza interruzioni non sono puri e non possiamo decidere il problema di interruzione.

Non è possibile nel caso generale. Vedi problema di interruzione . In breve, è impossibile scrivere un programma che, data una funzione e un input arbitrari, determini se il programma si fermerà o verrà eseguito per sempre. Se funziona per sempre, non è una funzione pura che corrisponde alla definizione che hai dato.