Part of notes for CS:4980:4, Fall 2015
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

By the late 1950s, core memory sizes greater than 4K were natural, and high-level languages were starting to emerge. FORTRAN was introduced in 1957, preliminary discussions of Algol were being widely circulated in 1958, leading to a solid specification for Algol 60, released in 1960. FORTRAN II, released in 1958, had parameterized subroutines and functions, local variables, and global variables of a sort (named COMMON blocks). Algol 60 had hierarchical scope rules with nesting of blocks.

This required that programmers start to think about how to use memory in ways they had not in the era of very small memories. FORTRAN's memory model was based entirely on static storage allocation, but members of the Algol committee began to think in terms of dynamic allocation. How storage was to be allocated was not the subject of discussion, but the idea of using a stack was implicit in their thinking.

The paper assigned for this discussion (free if referenced from on campus, otherwise, extraordinarily expensive) is the first clear public discussion I know of to explain how to implement and use Algol-like languages with their implied use of a stack. For most programmers of the era, this paper was the first introduction to stacks, and as we will see, it had a huge influence on computer architecture, just as Algol 60 had a huge influence on programming languages.

An aside: Algol 60 begat CPL (Christopher Strachey's Combined or Cambridge Programming Language) which begat BCPL (Basic CPL) which begat B (at Bell Labs) which begat C and C++ (at Bell Labs) which begat Java (at Sun Microsystems). Algol 60 also begat Algol 68, Pascal and Simula 67. Simula 67 was upward compatable from Algol 60 and had objects (C++ added objects to C). Pascal (developed by Wirth) begat Ada (developed by Honeywell Bull in France).

Today, we take for granted the idea of local variables allocated on a stack allowing for the possibility of recursion and subroutine calls for granted. This was not always so. Programmers in 1960 assumed static memory alloction for just about everything, and Dijkstra's paper, the reading for today, demonstrates how hard it was to communicate these new ideas.