Co miał na myśli Bill Gosper, mówiąc, że struktura danych to tylko głupi język programowania? [Zamknięte]

Jest cytat Ralpha Williama Gospera, Jr, który mówi:

Struktura danych to tylko głupi język programowania.

Co miał przez to na myśli? Niestety, wszystko, co mogę znaleźć w Google na ten temat, to nieustanne kopiowanie / wklejanie samego cytatu, bez żadnego kontekstu.

Wydaje się, że sednem tego stwierdzenia jest:

Struktura danych to tylko ... język programowania

Co jest całkiem prawdą, jeśli się nad tym zastanowić. W końcu kompilatory cały czas polegają na tej przechodniości; biorą język programowania, przekształcają go w strukturę danych, wykonują pewne przekształcenia tych danych, a następnie przekształcają wynik w inny język programowania.

W rzeczywistości, jeśli chcesz, możesz nawet zrobić coś szalonego, na przykład strukturę danych C, która pozwala pisać kod C, wywołując jego różne metody - na przykład (w pewnym sensie C #, ponieważ właśnie tego właśnie używam):

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

Co do pełnego cytatu: dlaczego coś takiego byłoby głupie w porównaniu do (powiedzmy) pisania w samym C? Powinno być całkiem oczywiste, że jest to pełne i nie tak czytelne jak jego odpowiednik w C (i w praktyce może nie obsługiwać pełnego zakresu możliwości C - typedefy byłyby trudne); stąd ta struktura danych jest po prostu „głupim” językiem programowania, osadzonym w „prawdziwym” języku programowania. Tę samą logikę można uogólnić na dowolną strukturę danych, o której myślisz; połączone listy są po prostu „głupią” wersją Lisp, a mapy skrótów są po prostu „głupią” wersją jakiegoś teoretycznego języka programowania hash (Hasp?).

Chodzi o to, że nie zawsze chcemy pisać Hasp w celu interakcji z naszymi mapami skrótów. Jest to problem wszystkich języków specyficznych dla domeny - z jednej strony dobrze zaimplementowana DSL jest wystarczająco potężna, aby wyrazić wszystko, co może zrobić podstawowy model; z drugiej strony musisz wdrożyć DSL, a następnie inni ludzie muszą się go nauczyć. To wymaga czasu i wysiłku, którego prawdopodobnie nie chcą wydać; w końcu chcę po prostu umieścić rzeczy na mojej mapie skrótów, a następnie sprawdzić, czy tam są inne rzeczy, nie chcę uczyć się wszystkich zawiłości programowania zorientowanego na skróty.

Tak więc, prawie o tym nie myśląc, bierzemy te teoretyczne, bardzo specyficzne i bardzo inteligentne języki programowania i destylujemy je do kilku głupich operacji zawartych w strukturze danych. Połączona lista ma jeden mały zbiór prostych metod; mapa hash ma kilka innych. Ignorujemy inne, bardziej wydajne operacje, które potencjalnie możesz wykonać na strukturze danych (na przykład większość implementacji LinkedList nie ma funkcji .Map ani .ForEach, a nawet nie wyobrażam sobie, co byś zrobił w Hasp), na rzecz ich wyraźnego wdrożenia w nadrzędnym języku programowania - z czym większość programistów się zapozna.

Struktury danych są w gruncie rzeczy głupim rozszerzeniem ich języka ojczystego na przestrzeń problemową, którą reprezentują koncepcyjnie. Wystarczająco inteligentne rozszerzenie wymagałoby nowego, określonego języka programowania, a większość ludzi nie będzie chciała się tego uczyć.

Struktura danych jest REPREZENTACJĄ języka programowania. Ale niezbyt „ostry”.

Można to zobaczyć na „diagramie węzłów”, takim jak ten w poniższym artykule wiki:

http://en.wikipedia.org/wiki/Root_node#Terminology

Niemniej jednak struktura danych jest NIEKOMPLETNA jako język programowania, ponieważ brakuje jej składni i kompletnych myśli, które byłyby zrozumiałe dla programisty. „Język” struktury danych można porównać do dziecka, które powiedziało coś w stylu „Ja, zimno. Zdobądź płaszcz”.

„Język” jest rozbity, ale można go zrozumieć. Dziecko mówi, że „jest mu zimno i chciałby więcej ubrań jako przykrycia”. Wypowiedź dziecka jest „głupią” wersją języka angielskiego, a także strukturą danych w odniesieniu do języka programowania.

Uważam, że to, co zamierzał Bill Gosper, polega na tym, że wszystkie struktury danych są tylko konstrukcjami programistycznymi o ograniczonym zastosowaniu . Jest to również związane z ideą tego „Projektowanie języków to projektowanie bibliotek, a projektowanie bibliotek to projektowanie języków” [1].

Jednym ze sposobów myślenia na ten temat jest rozważenie struktur danych jedynie w oparciu o algorytm. Na razie zapomnij o wymaganiach dotyczących miejsca lub wpisz adnotacje, ponieważ są one po prostu pomocnicze.

Na przykład możesz skodyfikować tablicę asocjacyjną (zwaną a map w niektórych językach a) na dwa sposoby: Albo używając jakiegoś indeksu przechowywanego w pamięci lub używając prostego wyrażenia wielkości liter.

W Haskell możesz skodyfikować tablicę asocjacyjną jako strukturę danych ...

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

... lub za pomocą wyrażenia wielkości liter ...

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

... lub nawet bardziej bezpośrednio ...

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

Łatwo zauważyć, że tego rodzaju dublowanie między strukturami danych a kodem jest możliwe, patrząc na rachunek lambda. Każda wartość może być reprezentowana przez funkcję w rachunku lambda, a sam rachunek jest uniwersalny (Turing zakończony).

[1] Cytat jest dziełem Bjarne Stroustrup.

Rozważ Javascript, gdzie wszystkie dane to kod. Rozważmy LISP, gdzie wszystkie dane to kod, a cały kod to dane.

Na początku, na końcu i wszędzie pomiędzy, dane są tylko bitami. To, że staramy się ontologizować bity za pomocą tekstu i symboli, aby były czytelne dla człowieka i przekształcalne przez człowieka, jest warstwą abstrakcji, która wymaga a) uczysz się języka definicji ib) uczysz się nieszczelności abstrakcji.

Na przykład w języku C # uczenie się różnicy między strukturą a klasą wymaga poznania różnicy w porównaniu równości między typami wartości i typami referencyjnymi. Każda ontologia danych wymaga własnego zestawu zasad, których musisz się nauczyć i przestrzegać. I, jak w każdym języku, pozwala szybko przejść do ogólnego pomysłu, ale im bardziej chcesz zbliżyć się do prawdziwej prawdy, tym bardziej powinieneś po prostu spojrzeć na plik binarny.

Wreszcie, jeśli weźmie się pod uwagę drzewo B lub podobną strukturę danych, poruszanie się po strukturze drzewa i wykonywanie innych operacji na nim wymaga specjalistycznej składni, która niekoniecznie może być przenoszona między drzewami, strukturami lub językami.