O que Bill Gosper quis dizer ao dizer que uma estrutura de dados é apenas uma linguagem de programação estúpida? [fechadas]

16

Há uma citação de Ralph William Gosper Jr que diz:

Uma estrutura de dados é apenas uma linguagem de programação estúpida.

O que ele quis dizer com isso? Infelizmente, tudo o que posso encontrar no Google são cópias / pastas incansáveis ​​da própria cotação, sem qualquer contexto.

desaparecido
fonte
1
Esse tipo de pergunta está sendo discutido em nosso site de meta-discussão .
Existem idiomas nos sistemas do tipo Turing-complete. Alguns deles são estúpidos.
SK-logic
@ SK-logic: O que os sistemas de tipos, completos ou não, de Turing, têm a ver com essa citação?
missingfaktor
1
@RehnoLindeque, você já viu Agda ou Coq? Os tipos podem ser completos em Turing.
SK-logic

Respostas:

10

Bem, parece que o cerne da afirmação é:

Uma estrutura de dados é apenas uma ... linguagem de programação

O que é bem verdade se você pensar sobre isso. Afinal, os compiladores dependem dessa transitividade o tempo todo; eles pegam uma linguagem de programação, convertem em uma estrutura de dados, fazem algumas transformações nesses dados e depois transformam o resultado em outra linguagem de programação.

De fato, se você quiser, pode até enlouquecer algo como uma estrutura de dados C, que permite escrever código C chamando seus vários métodos - por exemplo (em um tipo de C #, porque é isso que estou usando agora):

var C = novo HorribleCObject ();
Função C. <int> ("main", typeof (char [] []), typeof (int))
  .Variável ("i", tipo de (int), 0)
  . Enquanto ("i", Func (i) => i <10))
     .Call ("printf", "% d", "i")
     .PostIncrement ("i")
  .EndWhile ();
  Retorno (0)
 .EndFunction ();

Agora, quanto à citação completa: por que algo assim seria estúpido em comparação com (digamos) a escrita em C? Deveria ser bastante óbvio que isso é detalhado e não é tão legível quanto seu equivalente em C (e, na prática, pode não suportar o escopo completo do que C pode fazer - typedefs seria complicado); portanto, essa estrutura de dados é apenas uma linguagem de programação "estúpida", incorporada a uma linguagem de programação "real". Essa mesma lógica pode ser generalizada para qualquer estrutura de dados que você possa imaginar; listas vinculadas são apenas uma versão "estúpida" do Lisp, e mapas de hash são apenas uma versão "estúpida" de alguma Linguagem de Programação Hash teórica (Hasp?).

O problema é que nem sempre queremos escrever Hasp para interagir com nossos mapas de hash. É o problema que todas as linguagens específicas de domínio têm - por um lado, uma DSL bem implementada é poderosa o suficiente para expressar tudo o que o modelo subjacente pode fazer; por outro lado, você precisa implementar o DSL em primeiro lugar e, em seguida, outras pessoas precisam aprender. Isso leva tempo e esforço que eles provavelmente não querem gastar; afinal, eu só quero colocar as coisas no meu mapa de hash e depois verificar se há outras coisas lá, não quero aprender todos os meandros da programação orientada a hash.

Portanto, praticamente sem pensar nisso, pegamos essas linguagens de programação teóricas altamente específicas e muito inteligentes e as destilamos para as poucas operações estúpidas incorporadas em uma estrutura de dados. Uma lista vinculada possui uma pequena coleção de métodos simples; um mapa de hash tem alguns outros. Ignoramos as outras operações mais poderosas que você poderia executar potencialmente sobre a estrutura de dados (a maioria das implementações do LinkedList não possui uma função .Map ou .ForEach, por exemplo, e eu nem consigo imaginar o que você faria no Hasp), a favor de implementá-los explicitamente na linguagem de programação pai - que é com a qual a maioria dos programadores se familiarizará.

As estruturas de dados são, essencialmente, uma extensão estúpida de sua língua-mãe no espaço de problemas que elas representam conceitualmente. Uma extensão suficientemente inteligente exigiria uma nova linguagem de programação específica, e a maioria das pessoas não vai querer aprender isso.

Tacroy
fonte
2

Uma estrutura de dados é uma REPRESENTAÇÃO de uma linguagem de programação. Mas não particularmente "agudo".

Isso pode ser visto em um "diagrama de nó" como o do artigo da wiki abaixo:

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

No entanto, uma estrutura de dados é INCOMPLETA como linguagem de programação, porque carece de sintaxe e de pensamentos completos que seriam inteligíveis para um programador. A "linguagem" de uma estrutura de dados pode ser comparada a uma criança que disse algo como: "Eu, com frio. Pegue um casaco".

A "linguagem" está fraturada, mas pode ser entendida. A criança está dizendo que "está com frio e gostaria de mais roupas como cobertura". O enunciado da criança é uma versão "estúpida" do idioma inglês e da mesma forma estrutura de dados em relação a uma linguagem de programação.

Tom Au
fonte
1

Eu acredito que o que Bill Gosper pretendia é que todas as estruturas de dados sejam apenas construções de programação com aplicabilidade limitada . Isso também está relacionado à idéia de que "design de linguagem é design de biblioteca e design de biblioteca é design de linguagem" [1].

Uma maneira de pensar sobre a questão é considerar estruturas de dados apenas com base em algoritmos. Esqueça os requisitos de armazenamento ou digite anotações no momento, porque elas são simplesmente auxiliares.

Por exemplo, você pode codificar uma matriz associativa (chamada de map em algumas linguagens) de duas maneiras: Usando algum tipo de índice armazenado na memória ou usando uma expressão de caso simples.

Em Haskell, você pode codificar uma matriz associativa como uma estrutura de dados ...

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

... ou usando uma expressão de caso ...

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

... ou ainda mais diretamente ...

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

É fácil garantir que esse tipo de espelhamento entre estruturas de dados e código seja possível observando o cálculo lambda. Qualquer valor pode ser representado por uma função no cálculo lambda e o próprio cálculo é universal (conclusão completa).

[1] A citação é graças a Bjarne Stroustrup.

Rehno Lindeque
fonte
0

Considere Javascript, onde todos os dados são código. Considere o LISP, onde todos os dados são código e todo código é dados.

No começo, no fim e em todos os lugares, os dados são apenas bits. O fato de tentarmos ontologizar bits com texto e símbolos para torná-los facilmente legíveis e transformáveis ​​é uma camada de abstração que requer a) Você aprende a linguagem de definição eb) aprende o vazamento da abstração.

Por exemplo, em C #, aprender a diferença entre uma estrutura e uma classe requer que você aprenda a diferença na comparação de igualdade entre tipos de valor e tipos de referência. Toda ontologia de dados requer seu próprio conjunto de regras que você deve aprender e seguir. E, como qualquer idioma, ele permite que você chegue rapidamente à ideia geral, mas quanto mais perto você quiser abordar a verdade real do assunto, mais você deve olhar para o binário.

Finalmente, quando se considera uma árvore B ou estrutura de dados semelhante, navegar na estrutura da árvore e executar outros tipos de operações requer um tipo especializado de sintaxe que não é necessariamente transferível entre árvores, estruturas ou idiomas.

Legatou
fonte
3
Não tenho certeza se isso realmente chega ao cerne disso. A programação genérica, por exemplo, é especificamente sobre algoritmos agnósticos da estrutura de dados (normalmente com iteradores ou intervalos).
Jon Purdy
4
Tem certeza de que é isso que Ralph William Gosper, Jr. realmente quis dizer?
Robert Harvey
No Common Lisp, nem todos os dados podem ser compilados como código, mas todo o código pode ser tratado como dados. Não existem muitas regras de sintaxe, mas todo o código deve ser expressões S, pelo menos após o processamento da macro, e nem todos os dados são expressões S.
precisa