nach oben

2018 | Buch

Kapitel lesen Erstes Kapitel lesen

Routines of Substitution

John von Neumann’s Work on Software Development, 1945–1948

verfasst von: Dr. Mark Priestley

Verlag: Springer International Publishing

Buchreihe : SpringerBriefs in History of Computing

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This work is a historical and philosophical study of the programming work carried out by John von Neumann in the period 1945-8. At the heart of the book is an examination of a manuscript featuring the earliest known surviving example of von Neumann’s coding, a routine written in 1945 to ‘mesh’ two sequences of data and intended to be part of a larger program implementing the algorithm now known as mergesort.

The text of the manuscript itself, along with a preliminary document describing the code he used to write this program, are reproduced as appendices. The program is approached in three chapters describing the historical background to von Neumann’s work, the significance of the sorting application itself, and the development of the EDVAC, the machine for which the program was written. The subsequent chapters widen the focus again, discussing the subsequent evolution of the program and the crucial topic of subroutines, before concluding by situating von Neumann’s work in a number of wider contexts. The book also offers a unifying philosophical interpretation of von Neumann’s approach to coding.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

In the summer of 1945, the mathematician John von Neumann coded a ‘meshing’ routine for the EDVAC. The routine merged two sorted sequences, and von Neumann intended to use it as part of a larger program implementing the mergesort algorithm. Von Neumann’s code is preserved in the 23-page manuscript reproduced in Appendix B, which documents the development of the routine in considerable detail. This chapter describes the background of von Neumann’s involvement with the EDVAC project and his work on sorting applications. The question of whether historic programs are best studied as texts, artefacts, or a combination of both is considered, and the material production of the manuscript containing the meshing routine is described.

Mark Priestley

Chapter 2. Sorting and Collating

Abstract

Why did von Neumann choose to code a sorting routine for a machine intended as a high-speed scientific computer? This chapter explores the connections between von Neumann’s code and established data-processing procedures used on punched card machines. Starting in late 1944, John Mauchly interviewed several intensive users of punched cards in a variety of governmental agencies, and his notes allow us to pinpoint the moment at which the EDVAC team decided that sorting and numerical computing needed to be unified and implemented in a single high-speed machine. The early history of the mergesort algorithm and the beginnings of a systematic study of sorting procedures for electronic computers are described.

Mark Priestley

Chapter 3. EDVAC and Its Codes

Abstract

Von Neumann’s meshing routine is written for a virtual EDVAC with a different architecture from the machine described in the famous First Draft of a Report on the EDVAC. This chapter describes the ‘programmers’ interface’ and the code of both versions of the machine. The familar EDVAC of the First Draft is described in relation to the proposals for the Bell Labs Relay Calculator, and the unfamiliar manuscript reproduced in Appendix A allows us to give a detailed description of how the plans for EDVAC had evolved by the summer of 1945. The revised code that von Neumann proposed and used in the meshing routine is described in detail. Examples of the use of the both codes are given and the way that von Neumann laid out the code in the manuscript is explained. The notion of substitution is identified as the unifying concept underlying von Neumann’s design of these codes.

Mark Priestley

Chapter 4. The 1945 Meshing Routine

Abstract

Von Neumann’s manuscript is a substantial technical document written in unfamiliar notation. This chapter provides a guide to the development of the meshing routine that explains the step-by-step process followed by von Neumann. He began with a slightly ‘high-level’ version of the code and by a process of repeated substitution reduced this to a form that could be straightforwardly translated into binary code. The intermediate and final versions of the routine implicit in the manuscript are tabulated for ease of reference. Von Neumann also considered how the routine would be loaded and called as a subroutine in a more general sorting program, and the manuscript concludes with a discussion of the routine’s performance.

Mark Priestley

Chapter 5. Planning and Coding

Abstract

Both the meshing routine code and the process that von Neumann used to develop it were important foundations for the series of reports on Planning and Coding of Problems for an Electronic Computing Instrument that he wrote with Herman Goldstine. This chapter describes the transition from EDVAC to the early plans and code for the computer project started at the Institute for Advanced Study. Examination of a little-known 1946 draft of the Planning and Coding reports illuminates the development of key ideas such as the use of flow diagrams to document program structure and the use of subroutines in programming. These reports also contain later versions of the meshing routine, and also the earliest surviving version of a sorting routine using the mergesort algorithm.

Mark Priestley

Chapter 6. Subroutines

Abstract

The importance of subroutines as a way of enabling code reuse was clear to von Neumann from the beginning of his work on the EDVAC code. However, the need for subroutines to be relocatable within EDVAC’s memory raised technical issues that the users of earlier machines had not had to face. This chapter examines how Goldstine and von Neumann’s ideas about subroutines evolved over the period of writing the Planning and Coding reports, examining the role of subroutines in the process of program design, the representation of subroutines on flow diagrams, and the practical issues involved in the use of a subroutine library. Their approach is contrasted with the better-known proposals formulated for the EDSAC machine in Cambridge.

Mark Priestley

Chapter 7. Contexts and Conclusions

Abstract

This chapter examines von Neumann’s programming work in the period 1945–8 in the large and in wider historiographical contexts. The role of ‘all-purpose’ machines is discussed and differentiated from the concept of the ‘stored-program computer’. The history of programming is distinguished from the history of computing, and the parallel yet independent histories of hardware and software illustrated. The importance of the concepts of planning and substitution to von Neumann’s work on software development are highlighted.

Mark Priestley

Backmatter

Titel: Routines of Substitution
verfasst von: Dr. Mark Priestley
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-91671-2
Print ISBN: 978-3-319-91670-5
DOI: https://doi.org/10.1007/978-3-319-91671-2

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Chapter 2. Sorting and Collating

Chapter 3. EDVAC and Its Codes

Chapter 4. The 1945 Meshing Routine

Chapter 5. Planning and Coding

Chapter 6. Subroutines

Chapter 7. Contexts and Conclusions

Backmatter

Premium Partner