Per ogni funzione imperativa, esiste una controparte funzionale con prestazioni identiche o addirittura istruzioni?

Question

Attualmente, non ho imparato su un linguaggio funzionale che può ottenere le stesse prestazioni di C / C ++. E ho imparato che alcune lingue che favoriscono la programmazione funzionale alla programmazione imperativa, come Scala e ruggine, utilizzare modi imperativi per attuare le loro funzioni della libreria per una migliore efficienza.

Quindi ecco la mia domanda, sui comptutori di oggi che eseguono istruzioni imperative, è questa una limitazione del compilatore o della programmazione funzionale stessa? Per ogni funzione imperativa senza effetti collaterali, in una lingua senza GC come C / C ++ / ruggine / assemblaggio o uno con GC come Java, esiste una controparte funzionale pura in Haskell, Scala, ecc. Che può essere compilato a Corri con prestazioni identiche in tempo e spazio (non solo asintotiche ma esattamente uguali) o addirittura alle stesse istruzioni, con un compilatore funzionale ottimale che utilizza tutte tecniche di ottimizzazione moderna e persino non scoperta come la ricaduzione della coda, la pigrizia, l'analisi statica, la verifica formale , e così via su cui non so?

Sono consapevole dell'equivalenza tra λ-calcolabile e turing computabile, ma ma non riuscivo a trovare una risposta a questa domanda online. Se c'è, si prega di condividere un esempio di compilatore o una prova. In caso contrario, spiegare perché e mostrare un contatore. O è questa una domanda aperta non banali?

---

.

Modifiche supplementari come suggerito da Andrej Bauer :

Per essere più specifici, qui ci sono 2 esempi che hanno portato a pensare a questa domanda.

Ad esempio, la ricorsione della coda e gli accumulatori possono migliorare le prestazioni di alcune funzioni ricorsive per essere identiche a un'implementazione imperativa utilizzando for. In alcuni casi potrebbero persino avere le stesse istruzioni.

Un altro esempio riguarda la pigrizia a Haskell. La pigrizia può aiutare a evitare la copia non necessaria delle strutture dei dati e migliorare le prestazioni. Tuttavia, la pigrizia lascia i wrappings, le chiusure, ecc. Nel runtime e non riescono a rendere il programma veloce come un'implementazione imperativa in cui non ci sono cose del genere. Quindi mi chiedo se tali cose possono essere rimosse staticamente prima del runtime durante la compilazione.

Modifiche supplementari come suggerito da Vicinoo :

La domanda può anche essere indicata in questo modo: c'è un linguaggio che supporta sia la programmazione funzionale pura che la programmazione imperativa, abbinata a un compilatore ottimizzato, in cui ogni funzione senza effetti collaterali implementati imperativamente può essere sostituita con uno implementato esclusivamente funzionalmente, senza alcun costo della performance o addirittura compilato alle stesse istruzioni?

Answer 1

.

1. Performance non è una proprietà di lingua, è una proprietà di programmi specifici all'interno di una lingua. Alcune lingue potrebbero essere molto veloci in alcune cose e lenti agli altri.

   Ad esempio, lo schema di Chez può a volte trovare prestazioni paragonabili a C, non perché la lingua è più efficiente, ma poiché pratiche difensive che i programmatori spesso utilizzano in C sono meno necessari nella combinazione.

   Allo stesso modo, ci sono momenti in cui Haskell può fare parallelismo o concorrenza molto efficiente, non perché è più veloce di c, ma poiché le garanzie di immutabilità della lingua consentono al programmatore di evitare cose come blocchi e altre tecniche di sincronizzazione. E, le prestazioni variano dall'attuazione all'attuazione. Posso tirare a mano un interpretro C, ma sicuramente non sarà veloce. C non è veloce, GCC e Clang sono.

2. Cosa è considerato una lingua "funzionale"? Ogni pratico linguaggio funzionale ha alcune strutture per lo Stato mutabile: OCAML, Haskell, Scala, Lisp, Schema, ecc. La ricorsione della coda dà qualcosa di approssimativamente equivalente alla mutazione all'interno di un loop. Ma quando questo non è abbastanza, le lingue funzionali danno l'accesso al programmatore allo stato mutabile. Nel caso di Haskell, questo è controllato dal sistema di tipo, quindi non c'è mai stato mutabile implicito , ma la mutazione è molto ammessa e persino incoraggiata a Haskell. Guarda qualsiasi codice Haskell, e vedrai l'Io Monad ovunque. Allo stesso modo, le lingue ml distinguono tra tipi T e ref T, in modo da poter dire dai tipi se una variabile è mutabile o meno.

3. Non c'è un compilatore "ottimale", grazie al teorema del riso. Tutti i compilatori, imperativi o funzionali, sono "miglior sforzo:" l'uso approssimazioni conservatori per ottimizzare il codice.

   Se avessimo un compilatore ottimale, la risposta sarebbe che ogni programma corresse sempre utilizzando le istruzioni più efficienti possibili, e non importa quale lingua hai codificato il problema. La sequenza ottimale delle istruzioni che calcola un problema dipende dalla lingua di origine. Ma se avessimo questo, allora questo compilatore si compilerebbe ogni programma non arrestato in while(0), il che significa che potremmo rilevare programmi non-fermi, che è impossibile.

4. Per le macchine di turing e il calcolo della lambda, penso che sia piuttosto banale implementare un interprete di calcolo lambda per le macchine di tentazione che è asintoticamente equivalente a una macchina di turing universale. La complessità della Big-o non è ciò che la gente significa quando dicono "lingue funzionali sono lente". Di solito stanno parlando di costante sopraelevato, che è molto diverso. Non abbiamo il bene dei modi per modellare matematicamente questo, quindi di solito finiamo per usare esperimenti per misurare prestazioni precise.