A List Processing System for the 903 Computer
H.R.A. Townsend · ITNOW · 1968
The system to be described is written in SIR (Symbolic Input Routine) and provides a set of procedures which can be called by a normal ALGOL program to carry out list processing operations. This is a particular realisation of the idea suggested by Jenkins [Introduction to System Programming, Ed. Wagner, Academic Press, 1964]. Lists are held in the computer as a chain of addresses, the contents of each address indicating the location of the next. The actual items which are listed are called ‘atoms’. Lists are held in an area of store which is declared to the ALGOL compiler as an array, conveniently called LIST-SPACE. Lists are composed of p-words, each comprising a pair of computer words, and the structure of a simple list can be visualised as in Figure 1. In this simple list the first half of each p-word points to a location containing an atom, while the second half of each p-word points to the first of the pair of locations which contain the next p-word in the chain, the last p-word in the chain is of course a special case and the second half of this p-word is zero or null. More complex structures involve branched lists (cf Figure 2).