Что имел в виду Билл Госпер, говоря, что структура данных - это просто глупый язык программирования? [закрыто]

16

Есть цитата Ральфа Уильяма Госпера-младшего, которая гласит:

Структура данных - это просто глупый язык программирования.

Что он имел в виду под этим? Увы, все, что я могу найти в Google об этом, - это безжалостное копирование / вставка самой цитаты, без какого-либо контекста.

missingfaktor
источник
Существуют языки с системами полного типа по Тьюрингу. Некоторые из них глупы.
SK-логика
@ SK-logic: Как системы типов, Тьюринга или как-то иначе, связаны с этой цитатой?
фактор
1
@RehnoLindeque, ты когда-нибудь видел Agda или Coq? Типы могут быть тьюрингово-полными.
SK-logic

Ответы:

10

Ну, похоже, суть заявления такова:

Структура данных - это просто ... язык программирования

Что довольно верно, если вы думаете об этом. В конце концов, компиляторы все время полагаются на эту транзитивность; они берут язык программирования, преобразуют его в структуру данных, выполняют некоторые преобразования этих данных, а затем превращают результат в другой язык программирования.

На самом деле, если бы вы захотели, вы могли бы даже создать что-то сумасшедшее, например структуру данных C, которая позволит вам писать код на C, вызывая его различные методы - например (в некотором роде C #, потому что это то, что я сейчас использую):

var C = новый 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 ( "я")
  .EndWhile ();
  Возвращенная (0)
 .EndFunction ();

Теперь, что касается полной цитаты: почему что-то подобное было бы глупо по сравнению с (скажем) написанием на самом C? Должно быть совершенно очевидно, что это многословно и далеко не так разборчиво, как его эквивалент в C (и на практике может не поддерживать весь объем возможностей C - typedefs будет непросто); следовательно, эта структура данных является просто «глупым» языком программирования, встроенным в «настоящий» язык программирования. Та же самая логика может быть обобщена для любой структуры данных, о которой вы только можете подумать; связанные списки - это просто «глупая» версия Lisp, а хэш-карты - это просто «глупая» версия некоторого теоретического языка хэш-программирования (Hasp?).

Дело в том, что мы не всегда хотим писать Hasp для взаимодействия с нашими хэш-картами. Это проблема всех доменных языков - с одной стороны, хорошо реализованный DSL достаточно мощный, чтобы выразить все, что может сделать базовая модель; с другой стороны, вы должны сначала внедрить DSL, а затем другие люди должны изучить его. Это требует времени и усилий, которые они, вероятно, не хотят тратить; в конце концов, я просто хочу поместить вещи в мою хэш-карту и затем проверить, есть ли там другие вещи, я не хочу изучать все тонкости хэш-ориентированного программирования.

Итак, почти не задумываясь об этом, мы берем эти теоретически очень специфичные и очень умные языки программирования и подгоняем их к нескольким глупым операциям, воплощенным в структуре данных. Связанный список имеет одну небольшую коллекцию простых методов; хэш-карта имеет некоторые другие. Мы игнорируем другие, более мощные операции, которые вы могли бы потенциально выполнить над структурой данных (большинство реализаций LinkedList, например, не имеют функции .Map или .ForEach, и я даже не представляю, что вы будете делать в Hasp), в пользу их явной реализации на родительском языке программирования - с этим большинство программистов знакомо.

Структуры данных, по сути, являются глупым расширением их родительского языка в проблемное пространство, которое они концептуально представляют. Достаточно умное расширение потребовало бы нового, специфического языка программирования, и большинство людей не хотят изучать это.

Tacroy
источник
2

Структура данных - это ПРЕДСТАВЛЕНИЕ языка программирования. Но не особенно "острый".

Это можно увидеть из "диаграммы узла", подобной той, что приведена в статье ниже:

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

Тем не менее, структура данных НЕПРАВИЛЬНА как язык программирования, потому что ей не хватает синтаксиса и полных мыслей, которые были бы понятны программисту. «Язык» структуры данных можно сравнить с ребенком, который сказал что-то вроде: «Мне холодно, возьми пальто».

«Язык» сломан, но его можно понять. Ребенок говорит, что ему холодно, и он хотел бы больше одежды для прикрытия. Речь ребенка - это «глупая» версия английского языка, а также структура данных по отношению к языку программирования.

Том Ау
источник
1

Я полагаю, что Билл Госпер задумал, чтобы все структуры данных были просто программными конструкциями с ограниченной применимостью . Это также связано с идеей, что «Языковой дизайн - это дизайн библиотеки, а библиотечный дизайн - это дизайн языка» [1].

Один из способов решения этой проблемы заключается в рассмотрении структур данных только на алгоритмической основе. Забудьте о требованиях к хранилищу или типовых аннотациях на данный момент, потому что они просто вспомогательные.

Например, вы можете кодифицировать ассоциативный массив (называемый mapв некоторых языках a ) двумя способами: либо с помощью какого-либо индекса, хранящегося в памяти, либо с помощью простого выражения case.

В Haskell вы можете кодифицировать ассоциативный массив как структуру данных ...

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

... или используя выражение case ...

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

... или даже более прямо ...

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

Нетрудно видеть, что такое зеркалирование между структурами данных и кодом возможно, если взглянуть на лямбда-исчисление. Любое значение может быть представлено функцией в лямбда-исчислении, а само исчисление является универсальным (полное выполнение).

[1] Цитата благодарна Бьярне Страуструпу.

Рено Линдек
источник
0

Рассмотрим Javascript, где все данные являются кодом. Рассмотрим LISP, где все данные - это код, а весь код - данные.

В начале, в конце и везде между ними данные - это просто биты. То, что мы пытаемся онтологизировать биты с текстом и символами, чтобы сделать их легко читаемыми и трансформируемыми человеком, - это уровень абстракции, требующий: а) изучения языка определения и б) изучения утечки абстракции.

Например, в C # изучение различий между структурой и классом требует изучения различий в сравнении равенства между типами значений и ссылочными типами. Каждая онтология данных требует своего собственного набора правил, которые вы должны выучить и соблюдать. И, как и любой язык, он позволяет вам быстро прийти к общей идее, но чем ближе вы хотите приблизиться к истинной сути вопроса, тем больше вам нужно просто взглянуть на двоичный файл самостоятельно.

Наконец, когда рассматривается B-дерево или аналогичная структура данных, для навигации по структуре дерева и выполнения других видов операций с ним требуется специальный тип синтаксиса, который не обязательно переносится между деревьями, структурами или языками.

Legatou
источник
3
Я не уверен, что это действительно доходит до сути. Например, общее программирование касается конкретно алгоритмов, не зависящих от структуры данных (обычно с итераторами или диапазонами).
Джон Парди
4
Вы уверены, что именно это имел в виду Ральф Уильям Госпер-младший?
Роберт Харви
В Common Lisp не все данные могут быть скомпилированы как код, но весь код может рассматриваться как данные. Синтаксических правил не так много, но весь код должен быть S-выражением, по крайней мере, после обработки макроса, и не все данные являются S-выражениями.
Дэвид Торнли