Edsger W. Dijkstra - Edsger W. Dijkstra

Edsger W. Dijkstra
Edsger Wybe Dijkstra.jpg
Dijkstra em 2002
Nascer ( 11/05/1930 )11 de maio de 1930
Rotterdam , Holanda
Faleceu 6 de agosto de 2002 (06/08/2002)(72 anos)
Nuenen , Holanda
Cidadania Holanda
Educação Leiden University (BS, MS)
University of Amsterdam (Ph.D.)
Conhecido por Veja abaixo
Cônjuge (s) Maria (Ria) C. Debets
Prêmios
Carreira científica
Campos
Instituições
Tese Comunicação com um computador automático  (1959)
Orientador de doutorado Adriaan van Wijngaarden
Alunos de doutorado
Influências
Influenciado

Edsger Dijkstra Wybe ( / d k s t r ə / DIQUE -strə ; holandesa:  [ɛtsxər ʋibə dɛikstra] ( ouvir )Sobre este som ; 11 de maio de 1930 - 06 de agosto de 2002) foi um holandês cientista da computação , programador , engenheiro de software , cientista sistemas , ensaísta de ciências e pioneira em ciência da computação . Um físico teórico por formação, ele trabalhou como programador no Mathematisch Centrum (Amsterdam) de 1952 a 1962. Um professor universitário durante grande parte da sua vida, Dijkstra realizada a Centennial Presidente Schlumberger em Ciências da Computação na Universidade do Texas em Austin de 1984 até sua aposentadoria em 1999. Ele foi professor de matemática na Eindhoven University of Technology (1962–1984) e pesquisador na Burroughs Corporation (1973–1984). Em 1972, ele se tornou a primeira pessoa que não era americana nem britânica a ganhar o Prêmio Turing .

Uma das figuras mais influentes da geração fundadora da ciência da computação, Dijkstra ajudou a moldar a nova disciplina como engenheiro e teórico . Suas contribuições fundamentais cobrir diversas áreas da ciência da computação, incluindo construção de compiladores , sistemas operacionais , sistemas distribuídos , seqüencial e programação concorrente, paradigma e metodologia de programação, programação de pesquisa de linguagem , concepção do programa, desenvolvimento de programas, verificação de programas, princípios de engenharia de software, algoritmos de grafos, e fundamentos filosóficos de programação de computadores e ciência da computação. Muitos de seus artigos são fonte de novas áreas de pesquisa. Vários conceitos e problemas que agora são padrão na ciência da computação foram identificados pela primeira vez por Dijkstra ou carregam nomes cunhados por ele.

Até meados da década de 1960, a programação de computadores era considerada mais uma arte (ou um ofício) do que uma disciplina científica. Nas palavras de Harlan Mills (1986), "a programação [antes dos anos 1970] era considerada uma atividade privada de resolução de quebra-cabeças de escrever instruções de computador para funcionar como um programa". No final da década de 1960, a programação de computadores estava em crise . Dijkstra fazia parte de um pequeno grupo de acadêmicos e programadores industriais que defendiam um novo estilo de programação para melhorar a qualidade dos programas . Dijkstra, que tinha formação em matemática e física, foi uma das forças motrizes por trás da aceitação da programação de computadores como disciplina científica. Ele cunhou a frase " programação estruturada " e, durante a década de 1970, isso se tornou a nova ortodoxia da programação. Como o criador do movimento de programação estruturada (o primeiro movimento notável na história da programação de computadores), suas idéias sobre metodologia de programação ajudaram a lançar as bases para o nascimento e desenvolvimento da disciplina profissional de engenharia de software , permitindo aos programadores organizar e gerenciar cada vez mais projetos complexos de software. Como Bertrand Meyer (2009) observou, "A revolução nas visões da programação iniciada pela iconoclastia de Dijkstra levou a um movimento conhecido como programação estruturada, que defendia uma abordagem sistemática e racional para a construção do programa. A programação estruturada é a base de tudo o que foi feito já que na metodologia de programação , incluindo a programação orientada a objetos . "

O estudo acadêmico da computação concorrente começou na década de 1960, com Dijkstra (1965) sendo considerado o primeiro artigo neste campo, identificando e resolvendo o problema da exclusão mútua . Ele também foi um dos primeiros pioneiros da pesquisa sobre os princípios da computação distribuída . Seu trabalho fundamental em simultaneidade , semáforos , exclusão mútua, impasse (abraço mortal), encontrando caminhos mais curtos em gráficos , tolerância a falhas , auto-estabilização , entre muitas outras contribuições, compreende muitos dos pilares sobre os quais o campo da computação distribuída é construído. Pouco antes de sua morte em 2002, ele recebeu o prêmio ACM PODC Influential-Paper em computação distribuída por seu trabalho em autoestabilização de computação de programa. Este prêmio anual foi renomeado para Prêmio Dijkstra ( Prêmio Edsger W. Dijkstra de Computação Distribuída) no ano seguinte. Como o prêmio, patrocinado conjuntamente pelo Simpósio sobre Princípios de Computação Distribuída (PODC) da Associação para Máquinas de Computação (ACM) e o Simpósio Internacional sobre Computação Distribuída (DISC) da Associação Europeia para Ciência da Computação Teórica (EATCS ), reconhece que "Nenhum outro indivíduo teve uma influência maior na pesquisa em princípios de computação distribuída ".

Biografia

Primeiros anos

Edsger W. Dijkstra nasceu em Rotterdam . Seu pai era um químico presidente da Sociedade Química Holandesa ; ele ensinou química em uma escola secundária e mais tarde foi seu superintendente. Sua mãe era matemática, mas nunca teve um emprego formal.

Dijkstra havia pensado em seguir carreira no direito e esperava representar a Holanda nas Nações Unidas . No entanto, depois de se formar na escola em 1948, por sugestão de seus pais, ele estudou matemática e física e, em seguida, física teórica na Universidade de Leiden .

No início dos anos 1950, os computadores eletrônicos eram uma novidade. Dijkstra tropeçou em sua carreira por acidente e, por meio de seu supervisor, o professor A. Haantjes, conheceu Adriaan van Wijngaarden , diretor do Departamento de Computação do Centro de Matemática de Amsterdã , que ofereceu um emprego a Dijkstra; ele se tornou oficialmente o primeiro "programador" da Holanda em março de 1952.

Por algum tempo, Dijkstra permaneceu comprometido com a física, trabalhando nela em Leiden, três dias por semana. Com o aumento da exposição à computação, no entanto, seu foco começou a mudar. Como ele lembrou:

Depois de ter programado por cerca de três anos, tive uma discussão com A. van Wijngaarden , que era meu chefe no Centro de Matemática de Amsterdã , discussão pela qual continuarei grato enquanto viver. A questão é que eu deveria estudar física teórica na Universidade de Leiden simultaneamente e, como achei as duas atividades cada vez mais difíceis de combinar, tive que me decidir se deveria parar de programar e me tornar um teórico real e respeitável físico , ou levar o meu estudo da física apenas para uma conclusão formal, com um mínimo de esforço, e tornar-se ....., sim o quê? Um programador ? Mas essa era uma profissão respeitável? Afinal, o que era programação ? Onde estava o corpo sólido de conhecimento que poderia sustentá-lo como uma disciplina intelectualmente respeitável? Lembro-me muito bem de como invejei meus colegas de hardware, que, ao serem questionados sobre sua competência profissional, puderam pelo menos apontar que sabiam tudo sobre válvulas-válvulas, amplificadores e tudo o mais, ao passo que senti que, diante dessa questão, eu ficaria de mãos vazias. Cheio de dúvidas, bati na porta do escritório de Van Wijngaarden, perguntando se eu poderia "falar com ele por um momento"; quando saí de seu escritório algumas horas depois, era outra pessoa. Pois depois de ter ouvido meus problemas com paciência, ele concordou que até aquele momento não havia muita disciplina de programação, mas então ele passou a explicar calmamente que os computadores automáticos vieram para ficar, que estávamos apenas no início e poderíamos não serei uma das pessoas chamadas a fazer da programação uma disciplina respeitável nos anos que virão? Este foi um momento decisivo em minha vida e concluí meu estudo de física formalmente o mais rápido que pude.

-  Edsger Dijkstra, The Humble Programmer (EWD340), Communications of the ACM

Quando Dijkstra se casou com Maria (Ria) C. Debets em 1957, ele foi obrigado a declarar sua profissão como parte dos ritos de casamento. Afirmou que era programador, o que não era aceitável para as autoridades, uma vez que nessa altura não existia essa profissão nos Países Baixos.

Em 1959, ele recebeu seu PhD da Universidade de Amsterdã com uma tese intitulada 'Comunicação com um computador automático', dedicada a uma descrição da linguagem de montagem projetada para o primeiro computador comercial desenvolvido na Holanda, o Electrologica X1 . Seu orientador de tese foi Van Wijngaarden.

Mathematisch Centrum, Amsterdã

De 1952 a 1962, Dijkstra trabalhou no Mathematisch Centrum em Amsterdã, onde trabalhou em estreita colaboração com Bram Jan Loopstra e Carel S. Scholten , que havia sido contratado para construir um computador. Seu modo de interação era disciplinado: eles primeiro decidiriam sobre a interface entre o hardware e o software, escrevendo um manual de programação. Em seguida, os projetistas de hardware teriam que ser fiéis à sua parte do contrato, enquanto Dijkstra, o programador, escreveria o software para a máquina inexistente. Duas das lições que ele aprendeu com essa experiência foram a importância de uma documentação clara e que a depuração do programa pode ser amplamente evitada por meio de um design cuidadoso. Dijkstra formulou e resolveu o problema do caminho mais curto para uma demonstração na inauguração oficial do computador ARMAC em 1956. Por causa da ausência de periódicos dedicados à computação automática, ele não publicou o resultado até 1959.

No Centro de Matemática, Dijkstra e seu colega Jaap Zonneveld  [ nl ] desenvolveram o primeiro compilador para a linguagem de programação ALGOL 60 em agosto de 1960, mais de um ano antes de um compilador ser produzido por outro grupo. Teve uma influência profunda em seu pensamento posterior sobre a programação como uma atividade científica.

Universidade de Tecnologia de Eindhoven

A Universidade de Tecnologia de Eindhoven , localizada em Eindhoven, no sul da Holanda, onde Dijkstra foi professor de matemática de 1962 a 1984.

Em 1962, Dijkstra mudou-se para Eindhoven e, posteriormente, para Nuenen , no sul da Holanda, onde se tornou professor do Departamento de Matemática da Universidade de Tecnologia de Eindhoven . A universidade não tinha um departamento de ciência da computação separado e a cultura do departamento de matemática não combinava muito com ele. Dijkstra tentou formar um grupo de cientistas da computação que pudessem colaborar na solução de problemas. Este era um modelo incomum de pesquisa para o Departamento de Matemática. No final dos anos 1960, ele construiu o sistema operacional THE (batizado em homenagem à universidade, então conhecido como Technische Hogeschool Eindhoven ), que influenciou os projetos de sistemas operacionais subsequentes por meio do uso de memória virtual paginada baseada em software.

Burroughs Corporation

Dijkstra ingressou na Burroughs Corporation , uma empresa conhecida na época por produzir computadores baseados em uma arquitetura de hardware inovadora, como bolsista de pesquisa em agosto de 1973. Suas funções consistiam em visitar alguns dos centros de pesquisa da empresa algumas vezes por ano e realizar suas próprias pesquisas, o que ele fez no menor centro de pesquisa de Burroughs, ou seja, seu escritório no segundo andar de sua casa em Nuenen. Na verdade, Dijkstra era o único pesquisador da Burroughs e trabalhava para ela de casa, ocasionalmente viajando para suas filiais nos Estados Unidos. Como resultado, ele reduziu sua nomeação na universidade para um dia por semana. Aquele dia, terça-feira, logo ficou conhecido como o dia do famoso 'Clube da Tarde da Terça-feira', seminário durante o qual discutia com seus colegas artigos científicos, olhando todos os aspectos: notação, organização, apresentação, linguagem, conteúdo, etc. depois que ele se mudou em 1984 para a Universidade do Texas em Austin (EUA), uma nova 'filial' do Tuesday Afternoon Club surgiu em Austin, Texas .

Os anos de Burroughs viram-no no seu estado mais prolífico na produção de artigos de pesquisa. Ele escreveu cerca de 500 documentos da série EWD (descritos abaixo), a maioria deles relatórios técnicos, para circulação privada dentro de um grupo seleto.

Universidade do Texas em Austin

A Universidade do Texas em Austin , onde Dijkstra ocupou a Cátedra Centenária da Schlumberger em Ciências da Computação de 1984 a 1999.

Dijkstra aceitou a Cátedra do Centenário da Schlumberger no Departamento de Ciência da Computação da Universidade do Texas em Austin em 1984.

Últimos anos

Dijkstra trabalhou em Austin até sua aposentadoria em novembro de 1999. Para marcar a ocasião e comemorar seus mais de quarenta anos de contribuições seminais para a ciência da computação , o Departamento de Ciências da Computação organizou um simpósio, que aconteceu em seu 70º aniversário em maio de 2000.

Dijkstra e sua esposa voltaram de Austin para sua casa original em Nuenen (Holanda), onde ele descobriu que tinha apenas alguns meses de vida. Ele disse que queria se aposentar em Austin, Texas , mas morrer na Holanda. Dijkstra morreu em 6 de agosto de 2002, após uma longa luta contra o câncer. Ele e sua esposa Maria (Ria) Debets deixaram seus três filhos: Marcus, Femke e o cientista da computação Rutger M. Dijkstra.

Contribuições pioneiras e impacto na ciência da computação

Embora um físico teórico por formação, Dijkstra tornou-se uma das figuras mais influentes da geração fundadora da ciência da computação. Como um dos primeiros pioneiros em muitas áreas de pesquisa da ciência da computação , ele ajudou a moldar a nova disciplina tanto da perspectiva da engenharia quanto da acadêmica . Muitos de seus artigos são fonte de novas áreas de pesquisa. Muitos conceitos que agora são padrão na ciência da computação foram identificados pela primeira vez por Dijkstra ou carregam nomes cunhados por ele. Vários problemas importantes também foram formulados e resolvidos pela primeira vez por ele. Uma pesquisa de 1994 com mais de mil professores de ciência da computação foi conduzida para obter uma lista dos 38 artigos acadêmicos mais influentes na área, e Dijkstra é autor de cinco artigos. Aos 42 anos, ele se tornou o primeiro vencedor não americano, não britânico e europeu continental do Prêmio Turing .

Durante seus mais de quarenta anos como cientista da computação, o que incluiu cargos na academia e na indústria, Dijkstra fez inúmeras contribuições seminais para muitas áreas da ciência da computação , incluindo construção de compiladores , sistemas operacionais , computação concorrente ( programação concorrente ), computação distribuída , programação paradigma e metodologia , pesquisa de linguagem de programação , design de programa , desenvolvimento de programa , verificação de programa , princípios de engenharia de software , design de algoritmo e fundamentos filosóficos de programação de computadores e ciência da computação . Além disso, Dijkstra estava intensamente interessado no ensino de ciência da computação e nas relações entre a ciência da computação acadêmica e a indústria de software .

Suas principais contribuições pioneiras (incluindo ideias, invenções e inovações) incluem:

Trabalho algorítmico

Tempo de execução do algoritmo de Dijkstra
Algoritmo de Dijkstra. Ele escolhe o vértice não visitado com a distância mais baixa, calcula a distância através dele até cada vizinho não visitado e atualiza a distância do vizinho se for menor. Marque visitado (definido como vermelho) quando terminar com os vizinhos.

O trabalho algorítmico de Dijkstra (especialmente algoritmos de gráfico , algoritmos concorrentes e algoritmos distribuídos ) desempenha um papel importante em muitas áreas da ciência da computação. De acordo com Leslie Lamport (2002), Dijkstra "iniciou o campo de algoritmos concorrentes e distribuídos com seu artigo CACM de 1965" Solução de um problema no controle de programação simultânea ", no qual ele primeiro declarou e resolveu o problema de exclusão mútua." Como explica Lamport, "esse artigo é provavelmente a razão da existência do PODC (...). Ele permanece até hoje o artigo mais influente na área. O fato de não ter ganhado um Prêmio de Papel Influente PODC reflete uma separação artificial entre algoritmos concorrentes e distribuídos –Uma separação que nunca existiu na obra de Dijkstra. "

Em 1959, Dijkstra publicou em um artigo de 3 páginas 'Uma nota sobre dois problemas em conexão com gráficos' o algoritmo para encontrar o caminho mais curto em um gráfico entre dois nós dados, agora chamado de algoritmo de Dijkstra . Seu impacto ao longo dos próximos 40 anos é resumido do artigo de Mikkel Thorup , 'Undirected Single Source Shortest Paths with Positive Integer Weights in Linear Time' (1999): "Desde 1959, todos os desenvolvimentos teóricos em SSSP [Single-Source Shortest Paths] para gráficos direcionados e não direcionados gerais foram baseados no algoritmo de Dijkstra. " O algoritmo de Dijkstra é usado em SPF, Shortest Path First , que é usado nos protocolos de roteamento OSPF e IS-IS . Várias modificações no algoritmo de Dijkstra foram propostas por muitos autores usando heurísticas para reduzir o tempo de execução da busca do caminho mais curto . Um dos algoritmos heurísticos mais usados ​​é o algoritmo de busca A * (descrito pela primeira vez por Peter Hart , Nils Nilsson e Bertram Raphael do Stanford Research Institute em 1968), o objetivo principal é reduzir o tempo de execução reduzindo o espaço de busca. Dijkstra pensou sobre o problema do caminho mais curto quando trabalhava no Centro de Matemática em Amsterdã em 1956 como um programador para demonstrar as capacidades de um novo computador chamado ARMAC. Seu objetivo era escolher um problema e uma resposta (que seria produzida por computador) que pessoas que não eram da área de informática pudessem entender. Ele projetou o algoritmo de caminho mais curto em cerca de 20 minutos sem ajuda de papel e caneta e mais tarde o implementou para ARMAC para um mapa de transporte ligeiramente simplificado de 64 cidades na Holanda (de modo que 6 bits seriam suficientes para representar a cidade no algoritmo). Como ele lembrou, em entrevista publicada em 2001:

Qual é o caminho mais curto para viajar de Rotterdam para Groningen , em geral: de determinada cidade para determinada cidade? É o algoritmo para o caminho mais curto , que projetei em cerca de vinte minutos. Certa manhã, eu estava fazendo compras em Amsterdã com minha jovem noiva e, cansados, sentamos no terraço do café para tomar uma xícara de café e eu estava pensando se poderia fazer isso, e então projetei o algoritmo para o caminho mais curto . Como eu disse, foi uma invenção de vinte minutos. Na verdade, foi publicado em 1959, com três anos de atraso. A publicação ainda é legível, é, de fato, muito boa. Uma das razões por que é tão bom é que eu o desenhei sem lápis e papel. Aprendi mais tarde que uma das vantagens de projetar sem lápis e papel é que você é quase forçado a evitar todas as complexidades evitáveis. Eventualmente, esse algoritmo se tornou, para minha grande surpresa, uma das pedras angulares da minha fama.

-  Edsger Dijkstra, em uma entrevista com Philip L. Frana, Communications of the ACM 53 (8), 2001.

Um ano depois, ele se deparou com outro problema de engenheiros de hardware que trabalhavam no próximo computador do instituto: minimizar a quantidade de fio necessária para conectar os pinos no painel traseiro da máquina. Como solução, ele redescobriu o algoritmo conhecido como algoritmo de árvore geradora mínima de Prim . O algoritmo do Prim foi originalmente desenvolvido em 1930 pelo matemático tcheco Vojtěch Jarník . e mais tarde redescoberto e republicado independentemente por Robert C. Prim em 1957 e Dijkstra em 1959. Portanto, às vezes também é chamado de algoritmo DJP .

Em 1961, Dijkstra descreveu pela primeira vez o algoritmo do pátio de manobras , um método para analisar expressões matemáticas especificadas em notação de infixo , no relatório Mathematisch Centrum . Ele pode ser usado para produzir saída em notação polonesa reversa (RPN) ou como uma árvore de sintaxe abstrata (AST). O algoritmo foi denominado algoritmo de pátio de manobras porque sua operação se assemelha à de um pátio de manobras de ferrovia . O algoritmo do pátio de manobras é comumente usado para implementar analisadores de precedência do operador .

Em 1962 ou 1963, Dijkstra propôs o mecanismo de semáforo para algoritmo de exclusão mútua para n processos (uma generalização do algoritmo de Dekker ), que foi provavelmente o primeiro algoritmo concorrente publicado e que introduziu uma nova área de pesquisa algorítmica. Ele também identificou o problema de deadlock e propôs o algoritmo do banqueiro que evita o deadlock .

Em 1974, Dijkstra apresentou três algoritmos de autoestabilização para exclusão mútua em um anel. Este trabalho é considerado o primeiro a apresentar e demonstrar o conceito de autoestabilização.

Em meados da década de 1970, Dijkstra (junto com outros autores) introduziu duas abstrações úteis (mutador e coletor) para o estudo da coleta de lixo . O modificador abstrai o processo que executa a computação, incluindo a alocação de uma nova célula de armazenamento. O coletor é o processo que recupera automaticamente o lixo. Além disso, este artigo fornece uma formalização da marcação tricolor que é básica para a coleta de lixo incremental.

No início dos anos 1980, Dijkstra e Carel S. Scholten propuseram o algoritmo Dijkstra – Scholten para detectar terminação em sistemas distribuídos .

Em 1981, Dijkstra desenvolveu smoothsort , um algoritmo de classificação baseado em comparação e uma variação do heapsort .

Construção de compiladores e pesquisa de linguagem de programação

O ALGOL 60 foi criado como resultado da conferência ALGOL de janeiro de 1960 em Paris. Em agosto de 1960, Dijkstra e seu colega Jaap Zonneveld colocaram em operação o primeiro compilador ALGOL 60 completo (para o computador Electrologica X1 ) do mundo. O compilador Dijkstra – Zonneveld antecede o segundo compilador ALGOL 60 (por outro grupo) em mais de um ano.

Dijkstra era conhecido por ser um fã da linguagem de programação ALGOL e trabalhou na equipe que implementou o primeiro compilador para ALGOL 60 , que ele esteve intimamente envolvido no desenvolvimento, realização e popularização. Conforme discutido por Peter Naur no artigo 'O lado europeu da última fase do desenvolvimento do ALGOL 60', nos Anais da Primeira Conferência ACM SIGPLAN sobre História das Linguagens de Programação , janeiro de 1978, Dijkstra participou do período 1958– 1959 em uma série de reuniões que culminaram com a publicação do relatório definidor da linguagem do ALGOL 60. O nome de Dijkstra não aparece na lista de 13 autores do relatório final, mas ele era um membro oficial do Grupo de Trabalho 2.1 da IFIP sobre Idiomas Algorítmicos e Cálculos da Federação Internacional para Processamento de Informações (IFIP) , que especifica, apóia e mantém o ALGOL 60 e ALGOL 68 . Ele acabou deixando o comitê, aparentemente porque não concordava com as opiniões da maioria. Ainda assim, enquanto estava no Mathematisch Centrum (Amsterdam), ele escreveu juntamente com Jaap Zonneveld o primeiro compilador ALGOL 60 . Em agosto de 1960, ele e Zonneveld colocaram em operação o primeiro compilador ALGOL 60 completo em funcionamento (para o computador Electrologica X1 ), mais de um ano antes de um compilador ser produzido por outro grupo. Dijkstra e Zonneveld, que colaboraram no compilador, concordaram em não se barbear até que o projeto fosse concluído. Zonneveld fez a barba pouco depois, mas Dijkstra manteve a barba pelo resto da vida.

ALGOL foi o resultado de uma colaboração de comitês americanos e europeus. ALGOL 60 (abreviação de ALGOrithmic Language 1960) é um membro da família ALGOL de linguagens de programação de computador. Ele se seguiu ao ALGOL 58 e inspirou muitas línguas que o seguiram. Deu origem a muitas outras línguas, incluindo BCPL , B , Pascal , Simula e C . Algol 60 era uma linguagem de computador projetada sofisticadamente e oferecia um grande número de desafios de implementação até então desconhecidos . Como observa Bjarne Stroustrup , "um problema com o Algol60 era que ninguém sabia como implementá-lo". Um novo desafio importante na implementação do Algol 60 foi a alocação e gerenciamento de dados em tempo de execução. Em 1960, Dijkstra e Zonneveld mostraram como procedimentos recursivos podem ser executados usando uma pilha de registros de ativação em tempo de execução e como acessar identificadores de forma eficiente a partir de escopos estaticamente fechados usando o chamado display . O compilador ALGOL 60 foi um dos primeiros a oferecer suporte à recursão, empregando um novo método para isso. O pequeno livro de Dijkstra, Primer of Algol 60 Programming , publicado originalmente em 1962, foi a referência padrão para a linguagem por vários anos.

Papel da metodologia de programação e o nascimento do movimento de programação estruturada

Em 1965, Dijkstra escreveu suas famosas notas sobre programação estruturada e declarou a programação como uma disciplina em contraste com um ofício . Também em 1965, Hoare publicou um importante artigo sobre estruturação de dados. Essas ideias tiveram uma profunda influência na nova linguagem de programação , em particular no Pascal . As línguas são os veículos nos quais essas idéias deveriam ser expressas. A programação estruturada passou a ser suportada por uma linguagem de programação estruturada .

-  Niklaus Wirth , IEEE Annals of the History of Computing (2008)

A revolução nas visões da programação iniciada pela iconoclastia de Dijkstra levou a um movimento conhecido como programação estruturada, que defendia uma abordagem sistemática e racional para a construção do programa. A programação estruturada é a base para tudo o que foi feito desde então na metodologia de programação , incluindo a programação orientada a objetos .

-  Bertrand Meyer , Touch of Class: Learning to Program Well with Objects and Contracts (2009)

A programação de computadores nas décadas de 1950 a 1960 não era reconhecida como uma disciplina acadêmica e, ao contrário das ciências maduras, não havia conceitos teóricos ou sistemas de codificação. A programação como atividade profissional era pouco entendida naquela época. No final dos anos 1960, a programação de computadores estava em crise. Crise de software é um termo usado nos primórdios da ciência da computação para a dificuldade de escrever programas de computador úteis e eficientes no tempo necessário. A crise do software deveu-se ao rápido aumento da capacidade do computador e à complexidade dos problemas que podiam ser resolvidos. Com o aumento da complexidade do software , muitos problemas de software surgiram porque os métodos existentes eram insuficientes. O termo "crise de software" foi cunhado por alguns participantes na primeira das Conferências de Engenharia de Software da OTAN em 1968 em Garmisch , Alemanha. Sua palestra para o Prêmio Turing ACM de 1972 faz referência a este mesmo problema: "A principal causa da crise do software é que as máquinas se tornaram várias ordens de magnitude mais poderosas! Para ser franco: enquanto não havia máquinas, a programação era nenhum problema; quando tínhamos alguns computadores fracos, a programação tornou-se um problema leve, e agora temos computadores gigantes, a programação tornou-se um problema igualmente gigantesco. "

Embora Dijkstra tenha programado extensivamente em código de máquina na década de 1950, ele chegou à conclusão de que, em linguagens de alto nível, o uso frequente da instrução GOTO costumava ser um sintoma de estrutura deficiente. Em 1968, ele escreveu um artigo privado "Um caso contra a declaração GO TO", que foi então publicado como uma carta no CACM. O editor Niklaus Wirth deu a esta carta o título " Go To Statement Considered Harmful ", que introduziu a frase " considerado prejudicial " na computação.

Dijkstra argumentou que a instrução de programação GOTO, encontrada em muitas linguagens de programação de alto nível, é a principal fonte de erros e, portanto, deve ser eliminada. Esta carta causou um grande debate na comunidade de programação. Alguns chegaram a igualar uma boa programação com a eliminação de GO TO . Dijkstra recusou-se a mencionar o debate, ou mesmo a declaração GO TO, em seu artigo "Notas sobre Programação Estruturada". O debate já morreu há muito tempo; as linguagens de programação fornecem alternativas ao GO TO, poucos programadores hoje o usam liberalmente e a maioria nunca o usa.

A tese de Dijkstra era que os desvios do fluxo de controle linear eram mais claros se permitidos apenas em estruturas disciplinadas de nível superior, como a instrução if-then-else e o loop while . Essa metodologia foi desenvolvida em movimento de programação estruturada , título de seu livro de 1972, em co-autoria com Tony Hoare e Ole-Johan Dahl . Considerada por muitos como o primeiro movimento significativo na história da programação de computadores, a programação estruturada se tornou a nova ortodoxia da programação durante os anos 1970.

A programação estruturada é freqüentemente considerada como "programação sem goto". Mas, como Bertrand Meyer observa, "Como mostra o primeiro livro sobre o tópico [ Programação Estruturada por Dijkstra, Dahl e Hoare], a programação estruturada envolve muito mais do que estruturas de controle e o goto . Sua mensagem principal é que a programação deve ser considerada um disciplina científica baseada no rigor matemático. " Como paradigma de programação , a programação estruturada - especialmente nas décadas de 1970 e 1980 - influenciou significativamente o nascimento de muitas linguagens de programação modernas , como Pascal , C , Modula-2 e Ada . A versão Fortran 77 que incorpora os conceitos de programação estruturada, foi lançada em 1978. A linguagem C ++ foi uma versão consideravelmente ampliada e aprimorada da popular linguagem de programação estruturada C (veja também: lista de linguagens de programação baseadas em C ). Como o C ++ foi desenvolvido a partir de uma linguagem estruturada mais tradicional , é uma ' linguagem híbrida ', em vez de uma linguagem de programação puramente orientada a objetos .

Em seu artigo Structured Programming: Retrospect and Prospect (1986), Harlan Mills escreve: "O artigo de Programação Estruturada de Edsger W. Dijkstra de 1969 precipitou uma década de intenso foco em técnicas de programação que alteraram fundamentalmente as expectativas e realizações humanas no desenvolvimento de software . Antes desta década de foco intenso, a programação era considerada uma atividade privada de resolução de quebra-cabeças, de escrever instruções de computador para funcionar como um programa. Após esta década, a programação poderia ser considerada uma atividade pública baseada na matemática de reestruturação de especificações em programas. Antes, o O desafio era fazer com que os programas fossem executados e depois depurá-los para fazer as coisas certas. Depois, era de se esperar que os programas executassem e fizessem as coisas certas com pouca ou nenhuma depuração. Antes, era senso comum que nenhum programa de tamanho considerável poderia estar livre de erros. Depois, muitos programas de tamanho considerável foram executados por um ano ou mais sem erros detectados. Essas expectativas e as conquistas não são universais devido à inércia das práticas industriais. Mas eles estão bem estabelecidos para anunciar uma mudança fundamental no desenvolvimento de software. "

O livro Concise Encyclopedia of Computer Science (2004), editado por Edwin D. Reilly, observa que "as principais contribuições da programação estruturada foram duplas - a elevação da técnica de programação a algo menos de uma arte e mais de uma ciência, e a demonstração de que programas cuidadosamente estruturados podem ser obras criativas de mérito literário suficiente para merecer ser lido por humanos e não apenas por computador. "

Pesquisa sobre design e desenvolvimento de programas no início da engenharia de software

As ideias de Dijkstra sobre metodologia de programação (especialmente o movimento de programação estruturada) ajudaram a lançar as bases para o nascimento e desenvolvimento da disciplina profissional de engenharia de software (em particular o design e desenvolvimento de software), permitindo aos programadores organizar e gerenciar projetos de software cada vez mais complexos. No final dos anos 1960, Dijkstra discutiu o conceito de famílias de programas. Em meados da década de 1970, David Parnas e outros esclareceram a ideia e mostraram como aplicá-la nos princípios da engenharia de software.

A ascensão do movimento de programação estruturada levou a muitas outras abordagens estruturadas aplicadas ao design de software . As técnicas de análise estruturada e design estruturado são conseqüências de conceitos e técnicas de programação estruturada e das primeiras ideias sobre design modular. Princípios de modularidade foram fortalecidos pelos conceitos de Larry Constantine de acoplamento (a ser minimizado entre os módulos) e coesão (a ser maximizado dentro dos módulos), pelas técnicas de David Parnas de ocultação de informações e por tipos de dados abstratos . Uma série de ferramentas e métodos que empregam conceitos estruturados foram desenvolvidos, como o projeto estruturado , Programação Estruturada de Jackson , Ross ' Structured Analysis and Design Técnica (SADT), estruturado Método de Yourdon , Estruturada Análise de Sistemas e Métodos Projeto de (SSADM), e James Martin informações engenharia de tecnologia . O campo das métricas de software é frequentemente considerado como uma influência direta do movimento de programação estruturada na engenharia de software na década de 1970.

Separação de interesses (SoC), um dos princípios básicos da engenharia de software , é um princípio de design para separar um programa de computador em seções distintas, de modo que cada seção trate de um assunto separado . O termo separação de interesses foi cunhado por Dijkstra em seu artigo de 1974 "Sobre o papel do pensamento científico".

Pesquisa de sistema operacional

Na década de 1960, Dijkstra e seus colegas em Eindhoven projetaram e implementaram o sistema operacional THE (que significa ' Technische Hogeschool Eindhoven ') , que foi organizado em camadas de abstração claramente identificadas . Seu artigo de 1968 sobre este assunto forneceu a base para designs subsequentes dos sistemas operacionais. David Alan Grier , da IEEE Computer Society, escreve: "Geralmente rastreamos a ideia de construir sistemas de computador em camadas em um artigo de 1967 que o cientista da computação holandês Edsger Dijkstra deu a uma conferência conjunta da IEEE Computer Society / ACM. Antes deste artigo, engenheiros tinha lutado com o problema de como organizar software. Se você olhar os primeiros exemplos de programas e encontrar muitos na biblioteca eletrônica da Sociedade da Computação, descobrirá que a maior parte do código daquela época é complicado, difícil de ler, difícil de modificar e difícil de reutilizar. Em seu artigo de 1967, Dijkstra descreveu como o software pode ser construído em camadas e deu um exemplo de sistema operacional simples que usava cinco camadas. Ele admitiu que esse sistema pode não ser um teste realista de seu idéias, mas ele argumentou que quanto "maior o projeto, mais essencial a estruturação!" A idéia de usar camadas para controlar a complexidade tornou-se um esteio da arquitetura de software. Vemos isso em muitas formas e aplique-o a muitos problemas. Vemos isso na hierarquia de classes na programação orientada a objetos e na estrutura da arquitetura orientada a serviços (SOA). SOA é uma aplicação relativamente recente de camadas na ciência da computação. Foi articulado em 2007 como um meio de controlar a complexidade em sistemas de negócios, especialmente sistemas distribuídos que fazem uso substancial da Internet. Como o plano da Dijkstra para o desenvolvimento do sistema, seu sistema de camadas é chamado de SOA Solution Stack ou S3. As nove camadas do S3 são: 1) sistemas operacionais, 2) componentes de serviço, 3) serviços, 4) processos de negócios, 5) ações do consumidor, 6) integração de sistema, 7) controle de qualidade e garantia, 8) arquitetura de informação e 9) governança e políticas do sistema. "

Dijkstra organizou o design do sistema em camadas para reduzir a complexidade geral do software. Embora o termo 'arquitetura' ainda não tenha sido usado para descrever o design de software , este foi certamente considerado o primeiro vislumbre da arquitetura de software . Ele introduziu uma série de princípios de design que se tornaram parte do vocabulário de trabalho de todo programador profissional: níveis de abstração, programação em camadas, o semáforo e processos sequenciais cooperativos . Seu artigo original sobre o sistema operacional THE foi reimpresso na edição do 25º aniversário da Communications of the ACM, em janeiro de 1983. A título de introdução, o Editor-Chefe diz: "Este projeto iniciou uma longa linha de pesquisa em sistemas multinível arquitetura - uma linha que continua até os dias atuais porque a modularidade hierárquica é uma abordagem poderosa para organizar grandes sistemas. "

Computação simultânea (programação simultânea)

Embora a execução simultânea de programas tenha sido considerada por anos, a ciência da computação da simultaneidade começou com o artigo seminal de Edsger Dijkstra de 1965 que introduziu o problema de exclusão mútua . (...) O segundo problema fundamental de programação concorrente a ser estudado foi a sincronização produtor-consumidor. Essa forma de sincronização foi usada no nível de hardware nos primeiros computadores, mas foi identificada pela primeira vez como um problema de concorrência por Dijkstra em 1965, embora não tenha sido publicada nesta formulação até 1968. (...) Depois dos sistemas distribuídos , o próximo principal A etapa dos algoritmos concorrentes foi o estudo da tolerância a falhas . O primeiro exame científico da tolerância a falhas foi o artigo seminal de Dijkstra de 1974 sobre a autoestabilização . No entanto, como às vezes acontece com trabalhos à frente de seu tempo, esse artigo recebeu pouca atenção e foi essencialmente esquecido por uma década. (...) As décadas seguintes viram um grande crescimento do interesse em simultaneidade, particularmente em sistemas distribuídos. Olhando para as origens do campo, o que se destaca é o papel fundamental desempenhado por Edsger Dijkstra, a quem esta história é dedicada.

-  Leslie Lamport , Turing Lecture: The Computer Science of Concurrency: The Early Years (junho de 2015)
Um semáforo ( holandês : seinpaal ), o termo usado no artigo original de Dijkstra. No início dos anos 1960, Dijkstra propôs o primeiro mecanismo de sincronização para processos concorrentes, o semáforo com suas duas operações, P e V.

Em um artigo de uma página de 1965, Dijkstra introduziu o ' problema de exclusão mútua ' para n processos e discutiu uma solução para ele. Provavelmente foi o primeiro algoritmo concorrente publicado . A noção, padrão até agora, de uma ' seção crítica ' também foi introduzida neste artigo. Per Brinch Hansen , um pioneiro no campo da computação concorrente , considera o Cooperating Sequential Processes de Dijkstra (1965) como o primeiro artigo clássico em programação concorrente. Como observa Brinch Hansen, 'Dijkstra estabelece a base conceitual para a programação simultânea abstrata' com esse artigo.

Um exemplo simples de dois processos que modificam uma lista vinculada ao mesmo tempo, causando um conflito. O requisito de exclusão mútua foi identificado e resolvido pela primeira vez por Dijkstra em seu artigo seminal de 1965 intitulado Solução de um problema no controle de programação simultânea , e é creditado como o primeiro tópico no estudo de algoritmos concorrentes .

Em 1968, Dijkstra publicou seu artigo seminal ' Processos sequenciais cooperativos ', um ensaio de 70 páginas que originou o campo da programação concorrente . Ele discutiu nele a noção de exclusão mútua ( mutex ) e os critérios que uma solução satisfatória deve satisfazer. Ele também corrigiu a perspectiva histórica deixada de fora de seu artigo de 1965, incluindo a primeira solução correta conhecida para o problema de exclusão mútua , para dois processos, devido a Theodorus Dekker . Dijkstra posteriormente generalizou a solução de Dekker para n processos. Além disso, ele propôs o primeiro mecanismo de sincronização para processos concorrentes, o semáforo com suas duas operações, P e V. Ele também identificou o ' problema de deadlock ' (chamado aqui de 'o problema do abraço mortal ') e propôs um elegante ' algoritmo de banqueiro 'que evita o impasse . A detecção e prevenção de deadlock tornaram-se problemas de pesquisa perenes no campo da programação concorrente.

Ilustração do problema dos filósofos jantando

O problema dos jantares filósofos é um exemplo de problema frequentemente usado no projeto de algoritmos concorrentes para ilustrar problemas de sincronização e técnicas para resolvê-los. Foi originalmente formulado em 1965 por Dijkstra como um exercício de exame de estudante, apresentado em termos de computadores competindo pelo acesso a periféricos de unidade de fita . Logo depois, Tony Hoare deu ao problema sua formulação atual. O problema do barbeiro adormecido também é atribuído a Dijkstra.

Michel Raynal (2012) escreve: "Desde o trabalho inicial de EW Dijkstra (1965), que introduziu o problema de exclusão mútua, o conceito de um processo, o objeto semáforo, a noção de uma precondição mais fraca e comandos protegidos (entre muitos outros contribuições), a sincronização não é mais um catálogo de truques, mas um domínio da ciência da computação com seus próprios conceitos, mecanismos e técnicas, cujos resultados podem ser aplicados em muitos domínios. Isso significa que a sincronização de processos deve ser um tópico importante de qualquer ciência da computação currículo."

John W. McCormick et al. (2011) observa, "A noção do programa concorrente como um meio para escrever programas paralelos sem levar em conta o hardware subjacente foi introduzida pela primeira vez por Edsger Dijkstra (1968). Moti Ben-Ari (1982) elegantemente resumiu a ideia de Dijkstra em três frases : 'Programação simultânea é o nome dado à notação de programação e técnicas para expressar o paralelismo potencial e resolver os problemas de sincronização e comunicação resultantes. A implementação do paralelismo é um tópico em sistemas de computador (hardware e software) que é essencialmente independente da programação simultânea. Programação simultânea é importante porque fornece uma configuração abstrata na qual estudar o paralelismo sem se prender aos detalhes de implementação. '"

Computação distribuída (programação distribuída)

Dijkstra foi um dos primeiros pioneiros da pesquisa sobre os princípios da computação distribuída . Os patrocinadores do Prêmio Dijkstra reconhecem que "nenhum outro indivíduo teve uma influência maior na pesquisa dos princípios da computação distribuída". Alguns de seus trabalhos são até considerados os que estabeleceram o campo. O artigo de Dijkstra de 1965, Solução de um problema no controle de programação simultânea, foi o primeiro a apresentar a solução correta para o problema de exclusão mútua . Leslie Lamport escreve que este trabalho "é provavelmente porque existe o PODC " e "iniciou o campo dos algoritmos concorrentes e distribuídos ".

Em particular, seu artigo "Sistemas auto-estabilizadores apesar do controle distribuído" (1974) iniciou o subcampo da autoestabilização . É também considerado o primeiro exame científico de sistemas tolerantes a falhas . O artigo de Dijkstra não foi amplamente notado até a palestra convidada de Leslie Lamport no Simpósio ACM sobre Princípios de Computação Distribuída ( PODC ) em 1983. Em seu relatório sobre o trabalho de Dijkstra em sistemas distribuídos auto-estabilizados , Lamport considerou-o 'um marco no trabalho em tolerância a falhas 'e' um campo muito fértil para pesquisa '.

Especificação formal e verificação

A partir da década de 1970, o principal interesse de Dijkstra era a verificação formal . Em 1976, Dijkstra publicou um livro seminal, A Discipline of Programming , que apresentou seu método de desenvolvimento sistemático de programas junto com suas provas de correção. Em sua exposição, ele usou sua ' Linguagem de Comando Protegido '. A linguagem, com sua dependência do não determinismo, a semântica de pré-condição mais fraca adotada e o método de desenvolvimento proposto, teve um impacto considerável no campo até os dias de hoje. O cálculo de refinamento , originalmente proposto por Ralph-Johan Back e desenvolvido por Carroll Morgan , é uma extensão do cálculo de pré-condição mais fraco de Dijkstra , em que as instruções do programa são modeladas como transformadores de predicado .

Em 1984, para adicionar mais suporte a essa abordagem de programação, ele publicou, juntamente com Wim Feijen, um livro introdutório para alunos do primeiro ano de ciência da computação. O livro, publicado pela primeira vez em holandês, foi intitulado Een methode van programmeren . A edição em inglês apareceu em 1988 como A Method of Programming .

Sobre a natureza da ciência da computação e da programação de computadores

Muitas das opiniões de Dijkstra sobre ciência da computação e programação se espalharam. Por exemplo, a frase de programação "dois ou mais, use um para" (uma regra prática quando usar um loop) às vezes é atribuída a ele.

Ele foi o primeiro a afirmar que a programação é tão inerentemente complexa que, para gerenciá-la com sucesso, os programadores precisam aproveitar todos os truques e abstrações possíveis.

Dijkstra foi um dos mais famosos oponentes da visão da engenharia da ciência da computação. Como Peter Naur e Kristen Nygaard , Dijkstra não gostava do próprio termo 'ciência da computação'. A ciência da computação , como Dijkstra apontou, merece um nome melhor. Ele sugere que pode ser chamado de 'ciência da computação'. Em vez do computador, ou tecnologia de computação, Dijkstra queria enfatizar os mecanismos abstratos que a ciência da computação usa para dominar a complexidade. Ao expressar a natureza abstrata da ciência da computação , ele escreveu:

Uma confusão ainda maior veio do fato de que os despreparados incluíam os engenheiros eletrônicos que deveriam projetar, construir e manter as máquinas. O trabalho estava, na verdade, além da tecnologia eletrônica da época e, como resultado, a questão de como obter e manter o equipamento físico mais ou menos em condições de funcionamento tornou-se, nos primeiros dias, a preocupação principal. Como resultado, o tópico tornou-se - principalmente nos EUA - prematuramente conhecido como ' ciência da computação ' - o que, na verdade, é como se referir à cirurgia como 'ciência da faca' - e foi firmemente implantado na mente das pessoas que a ciência da computação tem a ver com máquinas e seus equipamentos periféricos. Quod non [Latim: "O que não é verdade"]. Agora sabemos que a tecnologia eletrônica não tem mais a contribuir para a computação do que o equipamento físico. Agora sabemos que o computador programável não é mais nem menos do que um dispositivo extremamente útil para realizar qualquer mecanismo concebível sem alterar um único fio, e que o principal desafio para a ciência da computação é, portanto, conceitual, a saber, quais mecanismos (abstratos) podemos conceber sem nos perdermos nas complexidades de nossa própria criação.

Em The Humble Programmer (1972), Dijkstra escreveu: "Não devemos esquecer que não é nosso negócio [dos cientistas da computação] fazer programas, é nosso negócio projetar classes de computação que exibam um comportamento desejado."

Dijkstra também se opôs à inclusão da engenharia de software sob o guarda-chuva da ciência da computação acadêmica. Ele escreveu que, "Como a economia é conhecida como" A Ciência Miserável ", a engenharia de software deveria ser conhecida como" A Disciplina Doomed ", condenada porque não pode nem mesmo se aproximar de seu objetivo, já que seu objetivo é contraditório." E "a engenharia de software aceitou como seu estatuto 'Como programar se você não puder'".

Personalidade e estilo de trabalho

Dijkstra no quadro-negro durante uma conferência na ETH Zurique em 1994. Certa vez, ele comentou: " Uma imagem pode valer mais que mil palavras , uma fórmula vale mais que mil fotos."

Simplicidade é uma grande virtude, mas requer muito trabalho para alcançá-la e educação para apreciá-la. E para piorar as coisas: a complexidade vende melhor. A indústria da computação não é a única que descobriu essa verdade dolorosa: o mundo acadêmico também. Se você fizer uma palestra que seja clara como cristal do início ao fim, seu público se sentirá enganado e murmurará ao sair da sala de aula: "Isso tudo foi bastante trivial, não foi?"

-  EW Dijkstra, "On the Nature of Computing Science" (EWD896), agosto de 1984

Você dificilmente pode culpar o MIT por não notar um obscuro cientista da computação em uma pequena cidade na Holanda.

-  Dijkstra costumava se descrever com humor em Nuenen em meados dos anos 1960.

No mundo da ciência da computação, Dijkstra é bem conhecido como um "personagem". No prefácio de seu livro A Discipline of Programming (1976), ele afirmou o seguinte: "Pela ausência de uma bibliografia, não ofereço explicação nem desculpas." Na verdade, a maioria de seus artigos e livros não contém nenhuma referência. Essa abordagem das referências foi deplorada por alguns pesquisadores. Mas Dijkstra escolheu essa forma de trabalhar para preservar sua autossuficiência.

Como professor universitário durante grande parte de sua vida, Dijkstra via o ensino não apenas como uma atividade obrigatória, mas como um sério esforço de pesquisa. Sua abordagem de ensino não era convencional. Seu estilo de palestra foi descrito como idiossincrático. Durante a palestra, as longas pausas entre as frases costumam ser atribuídas ao fato de que o inglês não é a primeira língua de Dijkstra. No entanto, as pausas também serviam como uma forma de ele pensar com os próprios pés e ele era considerado um pensador rápido e profundo enquanto se dedicava ao ato de pregar. Seus cursos para alunos em Austin tinham pouco a ver com ciência da computação, mas lidavam com a apresentação de provas matemáticas. No início de cada semestre ele tirava uma foto de cada um dos alunos, para memorizar seus nomes. Ele nunca seguiu um livro didático , com a possível exceção do seu próprio enquanto estava sendo preparado. Ao palestrar, ele escrevia as provas em giz em um quadro-negro, em vez de usar folhas retráteis. Ele convidou os alunos a sugerir ideias, que ele então explorou, ou se recusou a explorar porque violavam alguns de seus princípios. Ele atribuiu problemas desafiadores de lição de casa e estudou as soluções de seus alunos por completo. Ele conduziu seus exames finais oralmente, durante uma semana inteira. Cada aluno foi examinado no escritório ou em casa de Dijkstra, e um exame durou várias horas.

Não é tarefa da Universidade oferecer o que a sociedade pede, mas o que a sociedade necessita. [As coisas que a sociedade pede são geralmente compreendidas, e você não precisa de uma Universidade para isso; a universidade tem a oferecer o que ninguém mais pode oferecer.]

-  EW Dijkstra, "Respostas às perguntas dos alunos de Engenharia de Software" (EWD1305), novembro de 2000

Dijkstra também era muito original em sua maneira de avaliar a capacidade das pessoas para um trabalho. Quando Vladimir Lifschitz veio a Austin em 1990 para uma entrevista de emprego, Dijkstra lhe deu um quebra-cabeça. Vladimir resolveu e está trabalhando em Austin desde então.

Apesar de ter inventado grande parte da tecnologia de software, ele evitou o uso de computadores em seu próprio trabalho por muitas décadas. Mesmo depois de sucumbir ao incentivo de seus colegas da UT e adquirir um computador Macintosh , ele o usou apenas para e-mail e para navegar na World Wide Web . Dijkstra nunca escreveu seus artigos usando um computador. Ele preferiu confiar em sua máquina de escrever e mais tarde em sua caneta Montblanc . O instrumento de escrita favorito de Dijkstra era a caneta-tinteiro Montblanc Meisterstück . Ele tentou várias vezes outras canetas, mas nenhuma jamais substituiu a Montblanc.

Ele não tinha uso para processadores de texto , acreditando que alguém deveria ser capaz de escrever uma carta ou artigo sem rascunhos, reescrita ou qualquer edição significativa. Ele resolvia tudo em sua cabeça antes de colocar a caneta no papel, e uma vez mencionou que quando era estudante de física resolveria mentalmente seus problemas de dever de casa enquanto caminhava pelas ruas de Leiden . A maioria das publicações de Dijkstra foi escrita somente por ele. Ele nunca teve secretária e cuidava de toda a sua correspondência sozinho. Quando os colegas prepararam um Festschrift para seu sexagésimo aniversário, publicado pela Springer-Verlag , ele se deu ao trabalho de agradecer a cada um dos 61 colaboradores separadamente, em uma carta escrita à mão.

Ao longo da carreira de Dijkstra, seu trabalho foi caracterizado pela elegância e economia. Um escritor prolífico (especialmente como ensaísta), Dijkstra escreveu mais de 1.300 artigos, muitos deles escritos à mão em sua escrita precisa. Eles eram ensaios e parábolas; contos de fadas e avisos; explicação abrangente e pretexto pedagógico. A maioria era sobre matemática e ciência da computação; outros eram relatos de viagens mais reveladores sobre seu autor do que sobre as pessoas e lugares visitados. Ele tinha o hábito de copiar cada artigo e distribuí-lo a um pequeno grupo de colegas, que copiava e enviava os artigos a outro grupo limitado de cientistas. Seu caso de amor com a simplicidade surgiu em uma idade precoce e sob a orientação de sua mãe. Certa vez, ele disse que perguntou à mãe se a trigonometria era um assunto difícil. Ela respondeu que ele deveria aprender todas as fórmulas e que além disso, se ele precisasse de mais de cinco linhas para provar algo, ele estava no caminho errado.

Dijkstra era famoso por sua sagacidade, eloqüência, rudeza, brusquidão e muitas vezes crueldade para com outros profissionais, e jeito com as palavras, como em sua observação: "A questão de saber se as máquinas podem pensar (...) é tão relevante quanto a questão de saber se Submarinos podem nadar. " Seu conselho a um pesquisador promissor, que perguntou como selecionar um tema para pesquisa, foram as sábias palavras: "Faça apenas o que só você pode fazer". Dijkstra também era conhecido por sua crítica vocal e ausência de habilidades sociais ao interagir com os colegas. Como um visionário franco e crítico, ele se opôs fortemente ao ensino do BASIC .

Em muitos de seus ensaios mais espirituosos, Dijkstra descreveu uma empresa fictícia da qual atuou como presidente. A empresa chamava-se Mathematics, Inc., uma empresa que ele imaginava ter comercializado a produção de teoremas matemáticos da mesma forma que as empresas de software comercializavam a produção de programas de computador. Ele inventou uma série de atividades e desafios da Mathematics Inc. e documentou-os em vários artigos da série EWD. A empresa imaginária produziu uma prova da hipótese de Riemann, mas depois teve grandes dificuldades em coletar royalties de matemáticos que provaram resultados assumindo a hipótese de Riemann. A prova em si era um segredo comercial . Muitas das provas da empresa foram descartadas e, em seguida, grande parte do esforço da empresa teve de ser gasto em manutenção . Um esforço mais bem-sucedido foi a Prova Padrão para o Teorema de Pitágoras , que substituiu as mais de 100 provas existentes incompatíveis. Dijkstra descreveu a Mathematics Inc. como "o negócio mais empolgante e miserável já concebido". EWD 443 (1974) descreve sua empresa fictícia como tendo mais de 75% da participação no mercado mundial.

Manuscritos EWD

Dijkstra era bem conhecido por seu hábito de compor manuscritos cuidadosamente com sua caneta-tinteiro . Os manuscritos são chamados de EWDs, já que Dijkstra os numerou com EWD , suas iniciais, como prefixo. De acordo com o próprio Dijkstra, os EWDs começaram quando ele se mudou do Centro de Matemática em Amsterdã para a Universidade de Tecnologia de Eindhoven (então Technische Hogeschool Eindhoven). Depois de ir para Eindhoven , Dijkstra passou por um bloqueio de escritor por mais de um ano. Dijkstra distribuiu fotocópias de um novo EWD entre seus colegas. Muitos destinatários fotocopiaram e encaminharam suas cópias, de modo que os EWDs se espalharam pela comunidade internacional de ciência da computação. Os tópicos eram ciência da computação e matemática, e incluíam relatórios de viagens, cartas e discursos. Esses artigos curtos abrangem um período de 40 anos. Quase todos os EWDs que apareceram após 1972 foram escritos à mão. Eles raramente têm mais de 15 páginas e são numerados consecutivamente. O último, nº 1318, é de 14 de abril de 2002. Dentro da informática, são conhecidos como relatórios EWD, ou simplesmente EWDs. Mais de 1300 EWDs foram digitalizados, com um número crescente de transcritos para facilitar a pesquisa, e estão disponíveis online no arquivo Dijkstra da Universidade do Texas.

Vida pessoal e morte

Dijkstra levava um estilo de vida modesto , ao ponto de ser espartano. A casa dele e da esposa em Nuenen era simples, pequena e modesta. Ele não tinha TV, videocassete ou telefone celular e não ia ao cinema. Ele tocava piano e, enquanto estava em Austin , gostava de ir a shows . Ouvinte entusiasta de música clássica , o compositor favorito de Dijkstra era Mozart .

Dijkstra morreu em 6 de agosto de 2002. De acordo com funcionários da Universidade do Texas, a causa da morte foi câncer.

Influência e reconhecimento

A diferença entre um programador de computador e um cientista da computação é uma questão de cargo. Edsger Dijkstra deseja orgulhosamente ser chamado de "programador de computador", embora não toque em um computador há alguns anos. (...) Sua grande força é que ele é intransigente. Pensar em programação em C ++ o deixaria fisicamente doente.

-  Donald Knuth (1996), uma entrevista com Donald Knuth por Jack Woehr do Dr. Dobb's Journal .

Em 1972, a Association for Computing Machinery (ACM) reconheceu as contribuições seminais de Dijkstra para o campo, concedendo-lhe o distinto Prêmio Turing. A citação para o prêmio é:

Edsger Dijkstra foi o principal contribuinte no final dos anos 1950 para o desenvolvimento do ALGOL , uma linguagem de programação de alto nível que se tornou um modelo de clareza e rigor matemático. Ele é um dos principais expoentes da ciência e da arte das linguagens de programação em geral e contribuiu muito para o nosso entendimento de sua estrutura, representação e implementação. Seus quinze anos de publicações se estendem de artigos teóricos sobre teoria dos grafos a manuais básicos, textos expositivos e contemplações filosóficas no campo das linguagens de programação.

A introdução dada na cerimônia de premiação é uma homenagem a Dijkstra:

O vocabulário de trabalho dos programadores em todos os lugares é repleto de palavras originadas ou promulgadas à força por EW Dijkstra - exibição, abraço mortal , semáforo, programação sem saída, programação estruturada . Mas sua influência na programação é mais difundida do que qualquer glossário pode indicar. O presente precioso que este Prêmio Turing reconhece é o estilo de Dijkstra: sua abordagem da programação como um desafio intelectual elevado; sua eloqüente insistência e demonstração prática de que os programas devem ser compostos corretamente, não apenas depurados para correção ; e sua percepção esclarecedora dos problemas nas bases do design do programa . (…) Passamos a valorizar os bons programas da mesma forma que valorizamos a boa literatura. E no centro desse movimento, criando e refletindo padrões não menos bonitos do que úteis, está EW Dijkstra.

Nas palavras de Sir Tony Hoare , FRS , proferidas por ele no funeral de Dijkstra:

Edsger é amplamente reconhecido como um homem que refletiu profundamente sobre muitas questões profundas; e entre as questões mais profundas está a da filosofia moral tradicional: como é que uma pessoa deve viver sua vida? Edsger encontrou sua resposta para essa pergunta no início de sua vida: ele decidiu que viveria como um cientista acadêmico, conduzindo pesquisas em um novo ramo da ciência, a ciência da computação. Ele lançaria as bases que estabeleceriam a computação como uma disciplina científica rigorosa; e em sua pesquisa e em seu ensino e em sua escrita, ele buscaria a perfeição com a exclusão de todas as outras preocupações. Desses compromissos ele nunca se desviou, e é assim que deu ao tema de estudo que escolheu a maior contribuição que qualquer pessoa poderia dar em qualquer vida.

Em março de 2003, o seguinte e-mail foi enviado à comunidade de computação distribuída :

O objetivo é anunciar que o prêmio anteriormente conhecido como " PODC Influential-Paper Award " foi renomeado como " Prêmio Edsger W. Dijkstra em Computação Distribuída " em homenagem ao falecido Edsger W. Dijkstra, um pioneiro na área de computação distribuída. Seu trabalho fundamental em primitivos de simultaneidade (como o semáforo), problemas de simultaneidade (como exclusão mútua e impasse ), raciocínio sobre sistemas concorrentes e autoestabilização compreende um dos suportes mais importantes sobre os quais o campo da computação distribuída é construído. Nenhum outro indivíduo teve uma influência maior na pesquisa em princípios de computação distribuída.

O ex- presidente da ACM , Peter J. Denning, escreveu sobre Dijkstra:

Edsger Dijkstra, um dos gigantes do nosso campo e um crente apaixonado na visão matemática de programas e programação (...) Durante o quarto de século anterior, ele formulou muitos dos grandes desafios intelectuais do campo como programação - o instrução goto, programação estruturada, processos concorrentes, semáforos, deadlocks, programação recursiva em Algol e derivação de programas corretos.

Premios e honras

Entre os prêmios e homenagens de Dijkstra estão:

Em 1969, a British Computer Society (BCS) recebeu a aprovação para um prêmio e bolsa, Distinguished Fellow da British Computer Society (DFBCS), a ser concedida de acordo com o estatuto 7 de sua carta real . Em 1971, foi feita a primeira eleição, para Dijkstra.

Em 1990, por ocasião do 60º aniversário de Dijkstra, o Departamento de Ciência da Computação (UTCS) da Universidade do Texas em Austin organizou um seminário de dois dias em sua homenagem. Os palestrantes vieram de todos os Estados Unidos e Europa, e um grupo de cientistas da computação contribuiu com artigos de pesquisa que foram editados em um livro.

Em 2002, a Fundação C&C do Japão reconheceu Dijkstra "por suas contribuições pioneiras para o estabelecimento da base científica para software de computador por meio de pesquisa criativa em teoria básica de software, teoria de algoritmo, programação estruturada e semáforos". Dijkstra estava vivo para receber a notificação do prêmio, mas ele foi aceito por sua família em uma cerimônia de premiação após sua morte.

Pouco antes de sua morte em 2002, Dijkstra recebeu o prêmio ACM PODC Influential-Paper em computação distribuída por seu trabalho em autoestabilização de computação de programa. Este prêmio anual foi renomeado para Prêmio Dijkstra ( Prêmio Edsger W. Dijkstra de Computação Distribuída ) no ano seguinte, em sua homenagem.

O Prêmio Dijkstra de Excelência Acadêmica em Ciência da Computação ( Loyola University Chicago , Departamento de Ciência da Computação) foi nomeado em homenagem a Edsger W. Dijkstra. Com início em 2005, este prêmio reconhece o melhor desempenho acadêmico de um graduando em ciência da computação. A seleção é baseada no GPA em todos os cursos principais e na eleição pelo corpo docente do departamento.

O Departamento de Ciência da Computação (UTCS) da Universidade do Texas em Austin sediou a Palestra Memorial Edsger W. Dijkstra inaugural em 12 de outubro de 2010. Tony Hoare , Professor Emérito em Oxford e Pesquisador Principal da Microsoft Research, foi o palestrante do evento. Esta série de palestras foi possível graças a uma generosa doação da Schlumberger para homenagear a memória de Dijkstra.

Veja também

Publicações selecionadas

Livros
  • - (1962). A Primer of ALGOL 60 Programming: Together with Report on the Algorithmic Language ALGOL 60 . Academic Press. ISBN 978-0122162503.
  • -; Dahl, Ole-Johan ; Hoare, CAR (1972). Programação estruturada . Academic Press . ISBN 978-0-12-200550-3.
  • - (1976). A Discipline of Programming . Prentice Hall. ISBN 978-0132158718.
  • - (1982). Escritos Selecionados sobre Computação: Uma Perspectiva Pessoal . Monografias em Ciência da Computação. Springer. ISBN 978-0387906522.
  • -; Feijen, WHJ; Sterringa, Joke (1988). Um método de programação . Addison-Wesley. ISBN 978-0201175363.
  • -; Scholten, Carel S. (1990). Cálculo de predicado e semântica de programas . Textos e Monografias em Ciência da Computação. Springer-Verlag. ISBN 978-0387969572.
Artigos selecionados

Referências

Leitura adicional

links externos