LITHP(ID:3897/lit002)RWL Trundle SHAPE, the Haugue 1963 List Processing language as extension set to ALGOL Related languages
References: The form of the LITHP program For the I.C.T. 1905 the LITHP program is written as a normal ALGOL block, except that an additional end must be used to terminate the program. The program does not require any other blocks to be supplied with it. The program is compiled by means of the LITHP compiler which is a standard ALGOL compiler except that the array of list variables X [l], X [2], . . . X [l001 is supplied as a standard array, and the list processing functions hd, tl, cons, atom, eq, and null are supplied as standard functions. In addition four standard inputloutput procedures readlist, printlist, readatom and printatom are supplied. The compiler outputs a translated program on magnetic tape which can then be loaded into the computer. As an example, the LITHP program to read two lists, to append the first to the second, and to print the result is as follows: begin integer procedure Ap (X, y); value X, y; integer X, y; Ap : = if null (X) then y else cons (hd(x), Ap(tl(x), y)) ; readlist (X [l]); readlist (X [2]) ; X [31 := AP(X 111, X [W; printlist (X [3]) end end As in the Elliott 503 LITHP system, all list processing begin integer procedure Flatten (X); value X; functions must be defined as integer procedures and all integer X; list variables must be specified as integer variables. Abstract: The ALGOL list processing system LITHP, developed originally for the Elliott 503 and Ferranti Pegasus in collaboration with Mr. R. Trundle and outlined in the preceding article, is now being implemented on the I.C.T. 1905 at Northampton College. However, the implementation is slightly different from that outlined by Mr. Trundle. This note explains these differences. Extract: Further developments Further developments The LITHP implementation is part of a wider project to offer list processing facilities to users of the I.C.T. 1905, irrespective of the language in which they wish to program. The LITHP system enables list processing programs to be written within the ALGOL system. We are indebted to the Atlas Computer Laboratory at Chilton for permission to implement the SLIP system on the I.C.T. 1905, thus allowing list processing programs to be written within the FORTRAN system. At the same time work is progressing on a machine-code list processing system, and on a CPL compiler which will incorporate list processing. in The Computer Journal 9(2) August 1966 view details A list processing package was written in collaboration with Mr. P. Hammersley of Northampton College of Advanced Technology for use on the Elliott 503, and the Ferranti Pegasus, though further development was halted on the Pegasus due to lack of store and also on the 503 due to limitations of the Elliott ALGOL. The list processing methods used here depend very heavily on those of Woodward and Jenkins of The Royal Radar Establishment (Woodward and Jenkins, 1961 ; Jenkins, 1964)-in fact, the processes used in this paper are a slight variation on their exposition of McCarthy's LISP (McCarthy, 1960). The object of this paper is to facilitate the implementation of a list processing procedure on any machine that has an adequate ALGOL compiler, and for descriptive purposes the program is called LITHP. As list processing is essentially recursive, an ALGOL implementation that is not fullv recursive itself, such as that of the 503, may impose secure restrictions on the capability of the machine to handle LITHP. However, no such difficulties should occur with machines which have a full ALGOL implementation. This package consists of sixteen procedures which can be subdivided into four groups: 1. THE CODE PRIMITIVES type, assemble, tag, extract, inword and put, which are used to construct the other procedures of the package. 2. THE LIST PROCESSING PROCEDURES hd, tl, cons, atom, equ and null from which all list processing operations can be constructed. 3. THE HOUSEKEEPING PROCEDURES clear and start, used for garbage collection and initiation. 4. INPUT/OUTPUT by inatom and out. The whole package is nested within two block headings to enable global variables and arrays to be declared for the package and the user program. Thus the overall structure is: begin (global variables) begin (global arrays) (LITHP package) begin (user program) end end end ; Machine representation of lists Two sorts of elements comprise the main list processing these are atoms (the basic data to be manipulated) and p-words (the link elements that form the structure of the lists). All other words in the store are on the lists of available space. p-words and atoms can be shown schematically as in Fig. 1 where x is the name of a list and A is an atom. Every word in the stack is divided into three parts: (i) tag-which consists of a single bit, and in the current implementations this is taken as the sign bit; its use will be discussed under garbage collection. (ii) type-which consists of two or three bits sufficient to enumerate the types of atoms and p-words that are in the stack. (iii) body-which comprises the remainder of the word and is subdivided according to the integer represented by type: for a p-word, body is divided into two parts (head and tail) for an atom, body is divided into a number of characters that constitute the atom. These subdivisions are illustrated in Fig. 2 with reference to the 39-bit word of the Elliott 503. For a p-word, type = 1; for an atom, type = 2; while for a word on the list of available space, type = 0. A useful extension would be to increase the length of an atom by having two types of atom words, an intermediate and a terminal, so that an atom could become a simple non-branching list. in The Computer Journal 9(2) August 1966 view details |