The heap/substitution concept - an implementation of functional operations on data structures for a reduction machine

ABSTRACT

At first the concept of reduction by direct substitution is described. The syntax of a subset of Berkling's reduction language is given and then its semantics is defined by a set of substitution rules. An example - a program operating on a data structure - will demonstrate two aspects: firstly, it shows how reduction using substitution works, and secondly, it points out the n2-problem, i.e. the time taken to run the program is proportional to n2, where n is the number of items in the data structure. We discuss the problem and then give a solution, which we call the heap/substitution concept. The solution is an extension of the substitution concept and we get it by adding a restricted use of an environment. All advantages of reduction by substitution remain in effect but the time taken to evaluate programs operating on large data structures is now proportional to n. It is also shown that the heap/substitution concept can be used to implement an efficient implementation of recursive function calls.

REFERENCES

• 1: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 2: Berkling, K.J. Reduction Languages for Reduction Machines Technical Report ISF-76-08, 1976, GMD, D-5205 St.Augustin
• 3: Berkling, K.J. A Symmetric Complement to the Lambda Calculus Technical Report ISF-76-07, 1976, GMD, D-5205 St.Augustin
• 4: Peter Henderson, Functional Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 5: Kluge, Werner; Schluetter, Heinz An Architecture for Direct Execution of Reduction Languages in: Proceedings of the International Workshop on High-Level Language Computer Architecture, 1980, Fort Lauderdale, Florida
• 6: Mago, Gyula A. A Celluar Computer Architecture for Functional Programming University of North Carolina, Chapel Hill N.C. 27514
• 7: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 8: PACTEL GmbH - PA Computer und Telekommunikation Evaluation of the Reduction Machine Final Report, April 1979, Prepared for GMD
• 9: Turner, D. A. A New Implementation Technique for Applicative Languages in: Software-Practice and Experience, Vol. 9, pp.31-49, 1979.
• 10: Wilner, W.T. Recursive Machines Xerox Palo Alto Research Center, June 24, 1980

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

  E. Data
  E.1 DATA STRUCTURES

General Terms:
Languages