Christopher Strachey—Understanding Programming Languages

Higher-Order and Symbolic Computation -     

Deriving very efficient algorithms for evaluating linear recurrence relations using the program transformation technique

Summary Using the program transformation technique we derive some algorithms for evaluating linear recurrence relations in logarithmic time. The particular case of the Fibonacci function is first considered and a comparison with the conventional matrix exponentiation algorithm is made. This comparison allows us also to contrast the transformation technique and the stepwise refinement technique underlining some interesting features of the former one. Through the examples given we also explain why those features are interesting for a useful and reliable program construction methodology.     

Inorganic Chromatography on Cellulose: Some Applications to the Analysis of Electroplating Solutions with Special Reference to Nickel Plating Baths

The paper describes the technique of inorganic chromatography using paper strips and columns of cellulose pulp in combination with organic solvents, for the detection and determination of metals in electroplating baths. Special reference is made to nickel plating baths in which sulphate ion is present. It is shown that satisfactory separations can be achieved of a number of metals as chlorides, even in the presence of sulphates, providing acidity of the sample solution and organic solvent are carefully controlled. The following metals have been examined: Ni, Co, Fe, Cu, Mn, Cd, Cr, Al and Pb. The methods for final determination have also been described.     

A system which automatically improves programs

Summary Here we give methods of mechanically converting programs that are easy to understand into more efficient ones, converting recursion equations using high level operations into lower level flowchart programs.The main transformations involved are (i) recursion removal (ii) eliminating common subexpressions and combining loops (iii) replacing procedure calls by their bodies (iv) introducing assignments which overwrite list cells no longer in use (compiletime garbage collection).The operations we use are based on the POP-2 language, Burstall, Collins and Popplestone [1]. The main features to note are that hd is the LISP car, tl the LISP cdr and concat joins two lists (the LISP append).