Perché i programmi funzionali hanno una correlazione tra successo della compilazione e correttezza?

12

Ho seguito la programmazione funzionale per 4 anni, sin da quando ho iniziato a lavorare con LINQ. Recentemente, ho scritto un codice C # puramente funzionale e ho notato, di prima mano, quello che ho letto sui programmi funzionali - che una volta compilati tendono ad essere corretti.

Ho provato a mettere un dito sul perché questo è il caso, ma non ci sono riuscito.

Un'ipotesi è che applicando i principi OO, si ha un "livello di astrazione" che non è presente nei programmi funzionali e questo livello di astrazione rende possibile che i contratti tra gli oggetti siano corretti mentre l'implementazione è sbagliata.

Qualcuno ha pensato a questo e ha scoperto la sottostante ragione astratta per la correlazione tra successo della compilazione e correttezza del programma nella programmazione funzionale?

    
posta Aaron Anodide 19.11.2014 - 05:55
fonte

5 risposte

12

Posso scrivere questa risposta come qualcuno che dimostra molto le cose, quindi per me la correttezza non è solo ciò che funziona, ma ciò che funziona ed è facile da dimostrare.

In molti sensi, la programmazione funzionale è più restrittiva della programmazione imperativa. Dopo tutto, nulla ti impedisce di mutare mai una variabile in C! In effetti, la maggior parte delle funzionalità dei linguaggi FP sono semplici da discutere in termini di poche funzioni di base. Tutto si riduce a lambdas, applicazione di funzioni e pattern matching!

Tuttavia, poiché abbiamo pagato in anticipo il piper, abbiamo molto meno da gestire e abbiamo molte meno opzioni su come le cose possono andare storte. Se sei un fan del 1984, la libertà è davvero schiavitù! Utilizzando 101 diversi trucchetti per un programma, dobbiamo ragionare sulle cose come se una qualsiasi di queste 101 cose accadesse! È davvero difficile da fare in quanto risulta:)

Se inizi con le forbici di sicurezza invece di una spada, correre è moderatamente meno pericoloso.

Ora guardiamo alla tua domanda: in che modo tutto questo si inserisce nel "compila e funziona!" fenomeni. Penso che gran parte di questo sia lo stesso motivo per cui è facile provare il codice! Dopotutto, quando scrivi software stai costruendo alcune prove informali che è corretto. Per questo motivo, ciò che è coperto dalle tue prove di handwavy naturali e la nozione di correttezza dei compilatori (typechecking) è abbastanza.

Man mano che si aggiungono funzionalità e interazioni complesse tra di loro, ciò che non viene controllato dal sistema di tipi aumenta. Tuttavia, la tua capacità di costruire prove informali non sembra migliorare! Ciò significa che c'è di più che può scivolare attraverso l'ispezione iniziale e deve essere catturato in seguito.

    
risposta data 19.11.2014 - 06:10
fonte
12

the underlying abstract reason for the correlation between compilation success and program correctness in functional programming?

Stato mutevole.

I compilatori controllano le cose staticamente. Si assicurano che il tuo programma sia ben formato e il sistema di tipi fornisce un meccanismo per tentare di garantire che il giusto tipo di valori sia permesso nel giusto tipo di luoghi. Il sistema dei tipi cerca anche di garantire che il giusto tipo di semantica sia permesso nel giusto tipo di luoghi.

Non appena il tuo programma introduce lo stato, quest'ultimo vincolo diventa meno utile. Non solo devi preoccuparti dei valori giusti nei punti giusti, ma devi anche tener conto che il valore cambia in punti arbitrari del tuo programma. Devi tenere conto della semantica del tuo codice che cambia insieme a quello stato.

Se stai facendo bene la programmazione funzionale, non c'è (o molto poco) stato mutabile.

Tuttavia, c'è un dibattito sulla causalità in questo caso - se i programmi senza stato funzionano dopo la compilazione più frequentemente perché il compilatore può catturare più bug o programmi senza stato di lavoro dopo la compilazione più frequentemente perché quello stile di programmazione produce meno errori. p>

Probabilmente è un mix di entrambi nella mia esperienza.

    
risposta data 19.11.2014 - 17:36
fonte
7

Per dirla in parole povere, le restrizioni significano che ci sono meno modi corretti per mettere insieme le cose, e le funzioni di prima classe facilitano il calcolo di cose come le strutture del ciclo. Esegui il ciclo da questa risposta , ad esempio:

for (Iterator<String> iterator = list.iterator(); iterator.hasNext();) {
    String string = iterator.next();
    if (string.isEmpty()) {
        iterator.remove();
    }
}

Questo è l'unico modo imperativo sicuro in Java per rimuovere un elemento da una raccolta mentre si sta iterando attraverso di essa. Ci sono molti modi che sembrano molto vicini, ma sono sbagliati. Le persone che non sono a conoscenza di questo metodo a volte attraversano modi contorti per evitare il problema, ad esempio iterando attraverso una copia.

Non è terribilmente difficile renderlo generico, quindi lavorerà su più di semplici raccolte di Strings , ma senza funzioni di prima classe, non puoi sostituire il predicato (la condizione all'interno di if ), quindi questo codice tende a essere copiato e incollato e modificato leggermente.

Combina funzioni di prima classe che ti danno l'abilità di passare il predicato come parametro, con la restrizione dell'immutabilità che lo rende molto fastidioso se non lo fai, e ti viene in mente semplici blocchi elementari come filter , come in questo codice Scala che fa la stessa cosa:

list filter (!_.isEmpty)

Ora pensa a ciò che il sistema di tipi ti controlla, al momento della compilazione nel caso di Scala, ma questi controlli vengono eseguiti anche dai sistemi di tipo dinamico la prima volta che lo esegui:

  • list deve essere un tipo di tipo che supporta il metodo filter , ovvero una raccolta.
  • Gli elementi di list devono avere un metodo isEmpty che restituisce un valore booleano.
  • L'output sarà una raccolta (potenzialmente) più piccola con lo stesso tipo di elementi.

Una volta verificate queste cose, quali altri modi sono rimasti per il programmatore di rovinare? Ho dimenticato per sbaglio il ! , che ha causato un fallimento del test case estremamente ovvio. Questo è praticamente l'unico errore disponibile, e l'ho fatto solo perché stavo traducendo direttamente dal codice testato per la condizione inversa.

Questo schema viene ripetuto più e più volte. Le funzioni di prima classe ti consentono di riordinare le cose in piccole utility riutilizzabili con una semantica precisa, le restrizioni come l'immutabilità ti danno la spinta per farlo, e digitare il controllo dei parametri di quelle utility lascia poco spazio per rovinarle.

Naturalmente, tutto dipende dal programmatore sapendo che la funzione di semplificazione come filter esiste già, ed è in grado di trovarla, o di riconoscere il vantaggio di crearne una tu stesso. Prova a implementare questo te stesso ovunque usando solo la ricorsione a coda, e sei di nuovo nella stessa barca della complessità della versione imperativa, solo peggio. Solo perché puoi scriverlo molto semplicemente, non significa che la versione semplice sia ovvia.

    
risposta data 20.11.2014 - 06:16
fonte
2

Non penso che esista una correlazione significativa tra la compilazione della programmazione funzionale e la correttezza del tempo di esecuzione. Potrebbe esserci una correlazione tra la compilazione tipizzata in modo statico e la correttezza in fase di esecuzione, poiché almeno potresti avere i tipi giusti, se non stai trasmettendo.

L'aspetto del linguaggio di programmazione che potrebbe in qualche modo correlare la compilazione di successo con la correttezza del tipo di runtime, come si descrive, è la tipizzazione statica, e anche in questo caso, solo se non si indebolisce il correttore di tipi con cast che può essere affermato solo in fase di esecuzione ( in ambienti con valori o posizioni strongmente tipizzati, ad es. Java o .Net) o per niente (in ambienti in cui le informazioni sul tipo sono perse o con una digitazione debole, ad esempio C e C ++).

Tuttavia, la programmazione funzionale di per sé può aiutare in altri modi, come evitare dati condivisi e stato mutabile.

Entrambi gli aspetti possono avere una correlazione significativa nella correttezza, ma devi essere consapevole del fatto che non avere errori di compilazione e runtime non dice nulla, in senso stretto, sulla correttezza in senso lato, poiché nel programma fa ciò che dovrebbe fare e fallisce velocemente in caso di input non valido o errore di runtime incontrollabile. Per questo, hai bisogno di regole aziendali, requisiti, casi d'uso, asserzioni, test unitari, test di integrazione, ecc. Alla fine, almeno secondo me, forniscono molta più confidenza della programmazione funzionale, della tipizzazione statica o di entrambi.

    
risposta data 19.11.2014 - 17:23
fonte
2

Spiegazione per i gestori:

Un programma funzionale è come una grande macchina in cui tutto è connesso, tubi, cavi. [Una macchina]

Un programma procedurale è come un edificio con stanze contenenti una piccola macchina, che immagazzina prodotti parziali nei cassonetti, ottenendo prodotti parziali da altre parti. [A factory]

Quindi, quando la macchina funzionale è già in sintonia: è destinata a produrre qualcosa. Se un complesso procedurale viene eseguito, potresti aver supervisionato effetti specifici, introdotto il caos, non garantito il funzionamento. Anche se hai una lista di controllo di tutto correttamente integrato, ci sono così tanti stati, situazioni possibili (prodotti parziali in giro, secchi traboccanti, mancanti), che le garanzie sono difficili da dare.

Ma seriamente, il codice procedurale non specifica la semantica del risultato desiderato tanto quanto il codice funzionale. I programmatori procedurali possono allontanarsi più facilmente dal codice e dai dati circostanziali e introdurre diversi modi per fare una cosa (alcuni dei quali imperfetti). Generalmente vengono creati dati estranei. I programmatori funzionali potrebbero impiegare più tempo quando il problema diventa più complesso?

Un linguaggio funzionale strongmente tipizzato può ancora migliorare l'analisi dei dati e del flusso. Con un linguaggio procedurale, l'obiettivo di un programma deve spesso essere definito al di fuori del programma, come un'analisi formale di correttezza.

    
risposta data 19.11.2014 - 18:46
fonte

Leggi altre domande sui tag