Trasparenza referenziale usando Zero References?

Question

Trasparenza referenziale usando Zero References?

#1 da (7 voti)
#2 da (5 voti)

4

La trasparenza referenziale è una delle pietre angolari della programmazione funzionale che ci consente di applicare il ragionamento equativo al nostro codice. Tuttavia lo fa a un costo per le prestazioni, mediante l'uso di oggetti immutabili.

Alcuni linguaggi di programmazione funzionale come Idris risolvono questo problema di prestazioni tramite l'uso di Tipi di unicità e Tipi presi in prestito per consentire aggiornamenti sul posto degli oggetti (effetti collaterali) finché l'effetto complessivo è come se stessimo ancora utilizzando oggetti immutabili.

Idris mi porta a pensare a C. Quando si programma in C senza alcun riferimento (riferimento zero), allora tutti i riferimenti zero potrebbero essere considerati trasparenti?

Vale a dire. Se si programma in C l'aggiornamento di tutte le variabili in atto con effetti collaterali, mentre si utilizza solo lo spazio di stack (nessun puntatore, nessun heap), quindi hai raggiunto la trasparenza referenziale? E puoi applicare ancora il ragionamento equazionale al tuo codice?

Devo ammettere che non ho pensato affatto alle variabili globali, e questo si spezzerà RT.

Ecco un esempio di quello che ho immaginato:

#include <stdio.h>

struct A5 {
    int x[5];
};

A5 basicSort5(A5 nums) {
    int n = 5;
    for (int i = 0; i < n-1; ++i) {
        for (int j = i+1; j < n; ++j) {
            if (nums.x[i] > nums.x[j]) {
                int tmp = nums.x[i];
                nums.x[i] = nums.x[j];
                nums.x[j] = tmp;
            }
        }
    }
    return nums;
}

int main() {
    A5 nums = {7,3,2,8,9};
    A5 sortedNums = basicSort5(nums);
    for (int i = 0; i < 5; ++i) {
        printf("%i\n", sortedNums.x[i]);
    }
    return 0;
}

basicSort5 è referentially transparent (e thread safe) perché non sta usando riferimenti. Lo stesso identico codice in Java non è referenzialmente trasparente perché costringe tutto a essere un riferimento.

Dovrei estendere questa domanda al C ++. Perché credo che se si utilizza la semantica di spostamento e il codice in uno stile tipizzato in modo lineare, si mantiene RT e si ottengono anche i vantaggi prestazionali dei tipi unici di Idris. E se commetti un errore nella codifica in stile tipizzato lineare, devi solo indossare il costo di una memcpy e mantenere comunque RT. Voglio solo che questa teoria sia confermata.

Penso di aver fatto un errore. Move semantic ti aiuterà solo se sto usando lo spazio heap nascosto all'interno di una classe. Avrò sempre una sorta di copia in corso, anche se è un puntatore a 4 byte.

c functional-programming theory

posta clinux 01.06.2016 - 12:18

fonte

2 risposte

7

Penso che quello che hai raccolto sia che, in un linguaggio referenzialmente trasparente, tutto ha una semantica del valore. E se non leggi o scrivi globals o I / O, allora questo è sufficiente per darti trasparenza referenziale. Se, in aggiunta , non utilizzi la mutazione locale, otterrai anche maggiori vantaggi del ragionamento equazionale.

E, per ragioni di efficienza, le cose possono essere implementate usando la semantica di riferimento sotto la cappa a causa dell'immutabilità. Poiché gli oggetti non hanno identità, nessuno può distinguere tra un riferimento e una copia!

prepend42 :: [Int] -> [Int]
prepend42 list = 42 : list

Qui list non viene modificato. Nella semantica del valore, stiamo creando un nuovo elenco che contiene tutti gli elementi di list , con una cella aggiuntiva nella parte anteriore contenente 42 . Tuttavia, poiché list è immutabile, possiamo implementarlo utilizzando la semantica di riferimento: abbiamo solo bisogno di allocare una nuova cella di lista e il resto della struttura è condiviso.

let someList  = [10, 20, 30]
let someList' = prepend42 someList

+----+   +----+   +----+   +----+
| 42 |-->| 10 |-->| 20 |-->| 30 |
+----+   +----+   +----+   +----+
  ^        ^
  |        |
  |        someList
  |
  prepend42 someList

Una cosa simile accade per esempio un tipo di dati persistente Set , che viene implementato come un albero binario bilanciato in base alle dimensioni: l'inserimento di un elemento fa solo allocazioni O (log n ) per nuovo "dorso" della struttura (dalla radice al nodo inserito) e il resto della struttura è condiviso.

Quindi non è necessariamente il caso in cui gli oggetti immutabili portano a più copie; dipende dalla struttura dei dati in questione e dal modo in cui vengono utilizzati.

risposta data 03.06.2016 - 03:46

fonte

Leggi altre domande sui tag c functional-programming theory

Condivisione della funzionalità dell'interfaccia di database tra più applicazioni In cui nella metodologia mischia si definisce l'approccio / concetto per un determinato compito

score 5 · Accepted Answer

I puntatori sono ortogonali alla trasparenza referenziale.

Move semantics funziona bene in C, anche se con più file rispetto al C ++.

Nessuno stato mutabile globale + nessuna funzione consentita per mutare i suoi argomenti sarebbe sufficiente per la trasparenza referenziale, anche quando si passa per puntatore. Basta non hackerare nulla. La modifica delle variabili locali va bene - il chiamante non può vederle.

Questa strategia non funziona bene con C che non ha più tipi di ritorno. Chiamare pop su una pila deve restituire sia un elemento che una nuova pila, solitamente più piccola. Forse anche un codice di errore. Quindi anneghi nelle strutture fatte per restituire più valori.

Altrimenti, funziona piuttosto bene.