O programa foi escrito em 1945, pouco tempo depois do relatório sobre o EDVAC, mas refere-se a uma versão ligeiramente modificada da máquina em relação ao projeto original. O problema proposto é o da classificação de uma série de dados em ordem não decrescente de uma chave. A própria escolha do problema é muito significativa e até um certo ponto surpreendente. Tendo em vista as origens e as motivações de von Neumann, seria de se esperar que o exemplo de programação escolhido para ``testar'' a consistência do projeto fosse, por exemplo, um programa para resolver numericamente equações diferenciais. Entretanto, a adequação da máquina proposta para cálculos numéricos era óbvia. Assim, a escolha de uma aplicação não numérica mais complexa é perfeitamente compreensível e denota uma visão muito grande. Além disto, von Neumann queria mostrar que este tipo de máquina poderia realizar, de maneira muito eficiente, uma tarefa que era executada então pelas classificadoras de cartões da IBM, máquinas eletro-mecânicas especialmente projetadas para esta finalidade. Ficaria demonstrada assim a aplicabilidade do EDVAC não apenas a cálculos científicos mas também para propósitos mais gerais.
Von Neumann propôs o método que ficou conhecido mais tarde como classificação por intercalação,13 até hoje o algoritmo mais usado para classificar dados em memórias secundárias. Na realidade, o manuscrito de von Neumann contém a codificação de apenas uma parte do método que é o processo de intercalação de duas seqüências já em ordem. Em linhas gerais, a codificação segue exatamente o padrão que seria esperado para resolver este problema. Nota-se apenas que a arquitetura mais primitiva do que as de hoje exigia que, na falta de indexadores ou de enedereçamento indireto, o efeito de indexação fosse conseguido através de modificação das próprias instruções do programa. Toda a codificação foi feita em nível que seria chamado mais tarde de linguagem de máquina. Entretanto, von Neumann usa alguns expedientes que prenunciam o surgimento das linguagens de montagem,14 utilizando símbolos para denotar algumas grandezas. A atribuição de endereços é feita em relação a uma origem arbitrária, para ser preenchida mais tarde. Consegue-se, assim, o efeito de relocação manual de código para que possa ser usado como uma subrotina aberta. Uma outra preocupação de von Neumann é com a eficiência. A seqüenciação das instruções leva em consideração a latência da memória constituída de linhas de atraso. A descrição do programa termina com uma análise do tempo de execução, de forma muito semelhante às análises que foram difundidas mais tarde pelo próprio Knuth. Este primeiro programa de von Neumann nunca pôde ser testado pois o EDVAC ficou operacional somente vários anos mais tarde, e na realidade tem um pequeno erro. Uma versão mais completa e mais polida do programa apareceu em [20] e será comentada mais adiante.
O projeto da máquina do IAS contou com uma descrição muito mais completa e mais divulgada do que a do EDVAC. A primeira parte foi comentada na seção 3. A segunda parte, escrita por Goldstine e von Neumann, compõe-se de três volumes [19,20,21] intitulados Planning and Coding of Problems for an Electronic Computing Instrument. Havia previsão para a publicação de um quarto volume, mas este, aparentemente, nunca foi escrito. Os três volumes constituem um verdadeiro manual de técnicas de programação com múltiplos exemplos.
O primeiro volume [19] é dedicado à metodologia de programação. Sugere que a tarefa seja separada em duas fases: uma primeira referente à parte lógica da solução a ser representada por diagramas de fluxo15 e uma segunda que é a codificação propriamente dita. Nota que o problema de codificação é um problema de tradução da linguagem matemática em que o problema e sua solução foram concebidos para uma outra linguagem, a da máquina. Explica a utilização de construções iterativas e de decisão e a correspondente notação em termos de diagramas. Explicita a conexão óbvia entre iteração e indução. O treino de von Neumann em lógica aparece na discussão de primeiros conceitos de linguagens de programação: constantes, variáveis livres (isto é, parâmetros) e variáveis ligadas (isto é, variáveis locais) de um programa. Outra conseqüência dos seus conhecimentos de lógica é a introdução de asserções indutivas para descrever o estado da computação em pontos selecionados dos diagramas. Através de pequenos exemplos são introduzidos vários conceitos como por exemplo indexação e subrotinas. Novamente é dada ênfase à análise de eficiência de execução dos programas codificados. O documento chega a sugerir uma técnica para modificação de programas, após a deteção de algum erro, através de inserção de desvios incondicionais para o fim do programa e subseqüente retorno. Esta técnica é utilizada até hoje com o nome de patches. Finalmente, há uma seção com subrotinas para conversão entre as notações decimal e binária, bem como para aritmética de precisão dupla.
O segundo volume desta parte da documentação [20] traz vários exemplos de programação. Os primeiros são de natureza numérica, envolvendo os problemas de integração pelo método de Simpson e de interpolação. É discutido o problema de erros de arredondamento e são apresentados alguns variantes conforme a maneira de representar dados. Como sempre, há análises de tempo de execução.
Uma grande parte do segundo volume é dedicada novamente ao problema de classificação por intercalação, apresentando de maneira mais completa e acabada o mesmo algoritmo codificado no manuscrito analisado por Knuth. Há uma justificativa explícita para a utilização deste problema a fim de testar a eficiência das partes não aritméticas da máquina: memória e controle lógico. O problema de intercalação é resolvido de maneira muito semelhante à apresentada anteriormente. O problema de classificação é apresentado então como um problema de repetição da intercalação com seqüências de comprimentos crescentes 1, 2, 4, 8, 16, .... A análise de tempo de execução produz o resultado que hoje é bem conhecido, com número de operações proporcional a n log n. A descrição da implementação do algoritmo termina com uma comparação com a eficiência das máquinas classificadoras de cartões mostrando que, com hipóteses razoáveis sobre o tamanho dos registros classificados e das suas chaves, o computador deve ser de 15 a 30 vezes mais veloz, para uma massa de dados que caberia na memória. Finalmente, há considerações sobre a utilização do mesmo métdo para a classificação externa com dados em memória secundária como, por exemplo, numa fita magnética.
A escolha do problema de classificação e a solução adotada não podem ser subestimadas. Mesmo antes do advento dos computadores eletrônicos, classificadoras e intercaladoras eletro-mecânicas eram muito usadas em aplicações empresariais e em processamento de grandes volumes de dados. Durante muitos anos, as aplicações de computadores dependiam em boa parte de sua capacidade de classificação, principalmente de grandes arquivos de dados contidos em fitas magnéticas. Knuth [25] menciona, em 1973, que, de acordo com as estimativas dos fabricantes de computadores daquela época, mais de 25% do tempo de uso dos seus computadores eram dedicados à classificação, chegando a mais de 50% em muitas instalações. Os projetistas do EDVAC estavam muito cientes disto, tanto que a aplicação desta máquina para resolver o problema da classificação constava do programa do curso organizado pela Escola Moore em 1946, mencionado na seção 3.
É muito significativo que von Neumann, ao resolver o problema de classificação para exemplificar aplicações não numéricas, não tenha utilizado algum método mais óbvio e muito mais simples de programar, como por exemplo o conhecido método de ``bolha.''16 Uma razão aparente é que este último não poderia ser estendido para classificação externa; outra é que von Neumann havia percebido que os métodos óbvios necessitam da ordem de n2 operações para classificar n registros, o que poderia tornar o computador mais lento do que as máquinas eletro-mecânicas.
O último volume [21] desta parte da documentação do computador do IAS é dedicado à construção de subrotinas reutilizáveis e à formação de bibliotecas destas subrotinas. São tratados os problemas de passagem de parâmetros e de retorno de subrotinas. A maior parte do volume trata do problema de relocação de uma subrotina, ou seja o deslocamento das instruções da subrotina para localizações que dependem da posição de outras subrotinas que devem fazer parte do mesmo programa e já foram relocadas. O problema é resolvido por uma rotina especial, denominada rotina preparatória, que nada mais é que uma versão ainda primitiva do que posteriormente seria denominado de ligador/relocador. O documento apresenta código completo para esta rotina que supõe que as subrotinas relocáveis estão armazenadas num meio externo e com alguns dados fornecidos manualmente inicia a sua leitura e relocação automática na memória. A própria rotina preparatória é colocada no fim da memória para que o espaço por ela ocupado possa ser reaproveitado após o término da relocação.
Não podemos deixar de notar, entretanto, que aparentemente von Neumann não estava convencido da necessidade de ferramentas de programação mais avançadas como linguagens de montagem ou linguagens de alto nível, como FORTRAN cujo projeto estava sendo iniciado em 1954 por John Backus (vide [26]). Esta informação, caso seja exata, não seria surpreendente. Devemos lembrar que naquela época o custo dos computadores e, conseqüentemente, da sua utilização era muito alto. Assim, era natural uma certa ênfase em que os programas fossem tão eficientes quanto possível, e que o computador fosse utilizado apenas para a sua execução. Além disto, a própria limitação dos computadores impunha que os programas fossem relativamente pequenos.
Concluímos esta seção notando que esta descrição tão minunciosa e precisa de conceitos mais diversos de programação foi feita sem que os autores pudessem testá-los, pois não havia ainda nenhum computador disponível!