Che cosa intendeva dire Bill Gosper dicendo che una struttura di dati è solo uno stupido linguaggio di programmazione? [chiuso]

Bene, sembra che il cuore dell'affermazione sia:

A data structure is just a ... programming language

Il che è del tutto vero se ci pensi. Dopo tutto, i compilatori fanno affidamento su questa transitività tutto il tempo; prendono un linguaggio di programmazione, lo convertono in una struttura dati, eseguono alcune trasformazioni su quei dati e quindi trasformano il risultato in un altro linguaggio di programmazione.

In effetti, se volessi, potresti persino creare qualcosa di pazzo come una struttura dati C, che ti permette di scrivere codice C chiamando i suoi vari metodi - per esempio (in kinda C #, perché è quello che sto usando in questo momento ):

var C = new HorribleCObject();
C.Function<int>("main", typeof(char[][]), typeof(int))
  .Variable("i", typeof(int), 0)
  .While("i", Func(i) => i < 10))
     .Call("printf", "%d", "i")
     .PostIncrement("i")
  .EndWhile();
  .Return(0)
 .EndFunction();

Ora, per quanto riguarda la citazione completa: perché una cosa del genere sarebbe stupida rispetto a (diciamo) scrivendo in C? Dovrebbe essere abbastanza ovvio che questo è prolisso e non quasi leggibile quanto il suo equivalente in C (e, in pratica, potrebbe non supportare l'intero ambito di ciò che C può fare - typedefs sarebbe difficile); quindi, questa struttura dati è solo un linguaggio di programmazione "stupido", incorporato in un linguaggio di programmazione "reale". Quella stessa logica può essere generalizzata a qualsiasi struttura di dati che si possa pensare; le liste concatenate sono solo una versione "stupida" di Lisp e le mappe di hash sono solo una versione "stupida" di alcuni Hash Programming Language (Hasp?) teorici.

Il fatto è, tuttavia, che non vogliamo sempre scrivere Hasp per interagire con le nostre mappe di hash. È il problema che tutti i lingue specifiche del dominio hanno - da un lato, un DSL ben implementato è abbastanza potente da esprimere tutto il il modello sottostante può fare; d'altra parte, devi implementare il DSL in primo luogo e poi le altre persone devono impararlo. Ciò richiede tempo e fatica che probabilmente non vogliono spendere; dopotutto, voglio solo mettere le cose nella mia mappa di hash e poi controllare che ci siano altre cose lì dentro, non voglio imparare tutte le complessità di Hash Oriented Programming.

Quindi, praticamente senza pensarci, prendiamo questi linguaggi di programmazione teorici altamente specifici e molto intelligenti e li distilliamo nelle poche e stupide operazioni incorporate in una struttura dati. Una lista collegata ha una piccola raccolta di metodi semplici; una mappa hash ne ha altre. Ignoriamo le altre operazioni più potenti che potreste potenzialmente eseguire sulla struttura dei dati (la maggior parte delle implementazioni di LinkedList non ha una funzione .Map o .ForEach, ad esempio, e non riesco nemmeno a immaginare cosa fareste in Hasp), a favore di implementarle esplicitamente nel linguaggio di programmazione principale, che è ciò che la maggior parte dei programmatori avrà familiarità con.

Le strutture dati sono, in sostanza, un'estensione stupida del loro linguaggio genitore nello spazio del problema che rappresentano concettualmente. Un'estensione sufficientemente intelligente richiederebbe un nuovo linguaggio di programmazione specifico e molte persone non vorranno apprenderlo.

Una struttura dati è una RAPPRESENTAZIONE di un linguaggio di programmazione. Ma non particolarmente "acuto".

Questo può essere visto da un "diagramma dei nodi" come quello nell'articolo della wiki qui sotto:

link

Tuttavia, una struttura di dati è INCOMPLETA come linguaggio di programmazione, perché manca sintassi e pensieri completi che sarebbero comprensibili per un programmatore. Il "linguaggio" di una struttura di dati potrebbe essere paragonato a un bambino che ha detto qualcosa del tipo "Io, freddo, prendi il cappotto".

La "lingua" è fratturata, ma può essere capita. Il bambino sta dicendo che "lui / lei è freddo e vorrebbe più vestiti come copertura". L'espressione del bambino è una versione "stupida" della lingua inglese, e similmente la struttura dei dati in relazione a un linguaggio di programmazione.

Credo che ciò che Bill Gosper intendeva fosse che tutte le strutture dati sono solo costrutti di programmazione con applicabilità limitata . Questo è anche legato all'idea che "Il design della lingua è design della biblioteca e il design della libreria è design della lingua" [1].

Un modo di pensare al problema è considerare le strutture di dati semplicemente su una base algoritmica. Dimentica i requisiti di archiviazione o scrivi annotazioni per il momento perché sono semplicemente accessori.

Ad esempio, potresti codificare un array associativo (chiamato map in alcune lingue) in due modi: usando un qualche tipo di indice memorizzato in memoria o usando una semplice espressione del caso.

In Haskell puoi codificare un array associativo come struttura dati ...

let assocArray = [("a", 1),("b", 2),("c", 3)]
let key = "b"
lookup key assocArray

... o usando un'espressione case ...

let key = "b"
case key of 
  "a" -> 1
  "b" -> 2
  "c" -> 3

... o anche più direttamente ...

let key = "b"
if key == "a" 
  then 1 
  else if key == "b"
    then 2
    else if key == "c"
      then 3
      else undefined

È facile vedere che questo tipo di mirroring tra strutture dati e codice è possibile osservando il calcolo lambda. Qualsiasi valore può essere rappresentato da una funzione nel calcolo lambda e il calcolo stesso è universale (completamento completo).

[1] La citazione è grazie a Bjarne Stroustrup.

Considera Javascript, in cui tutti i dati sono codice. Considera LISP, dove tutti i dati sono codice e tutto il codice è dati.

All'inizio, alla fine e ovunque nel mezzo, i dati sono solo bit. Il tentativo di ontologizzare i bit con testo e simboli per renderli facilmente leggibili dall'uomo e trasformabili dall'uomo è uno strato di astrazione che richiede a) Si impara il linguaggio di definizione eb) si impara la dispersione dell'astrazione.

Ad esempio, in C #, l'apprendimento della differenza tra una struttura e una classe richiede l'apprendimento della differenza nel confronto di uguaglianza tra tipi di valori e tipi di riferimento. Ogni ontologia dei dati richiede il proprio insieme di regole che è necessario apprendere e rispettare. E, come in ogni linguaggio, ti permette di arrivare rapidamente all'idea generale, ma più ti avvicini alla vera verità della questione, più dovresti solo guardare il file binario da solo.

Infine, quando si considera un albero B o una struttura dati simile, la navigazione della struttura dell'albero e l'esecuzione di altri tipi di operazioni su di essa richiede un tipo specializzato di sintassi che non è necessariamente trasferibile attraverso alberi, strutture o lingue.