Binding time optimization in programming languages: Some thoughts toward the design of an ideal language

ABSTRACT

A new approach to the design of a programming language and its processor is proposed and some of the techniques necessary to realize the design are investigated. The language would have a precisely specified syntax and semantics, with both designed to provide the programmer maximal expressive power and to be as easily understood as possible. The semantics would be based on extremely late binding times, which provide great power to the programmer and are consistent with ease of understanding of the execution process. It would be the responsibility of the processor to implement each program in the most efficient manner consistent with its being correctly executed. Implications of this design philosophy and some of the techniques to be used are discussed in greater detail, focusing particularly on data types and storage allocation.

REFERENCES

• 1: Frances E. Allen, Control flow analysis, Proceedings of a symposium on Compiler optimization, p.1-19, July 27-28, 1970, Urbana-Champaign, Illinois
• 2: Bauer, Alan M. & Harry J. Saal, Does APL Really Need Run-time Checking?, Software—Practice and Experience, Vol. 4, 1974, pp. 129-138.
• 3: Daniel G. Bobrow , Bertram Raphael, New Programming Languages for Artificial Intelligence Research, ACM Computing Surveys (CSUR), v.6 n.3, p.153-174, Sept. 1974 [doi>10.1145/356631.356632]
• 4: Daniel G. Bobrow , Ben Wegbreit, A model and stack implementation of multiple environments, Communications of the ACM, v.16 n.10, p.591-603, Oct. 1973 [doi>10.1145/362375.362379]
• 5: John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
• 6: Dijkstra, Edsger W., On the Design of Machine Independent Programming Languages, in Richard Goodman (ed.), Annual Review in Automatic Programming, Vol. 3, pp. 27-42, 1963.
• 7: Susan L. Graham , Mark Wegman, A fast and usually linear algorithm for global flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.22-34, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512979]
• 8: K Jensen , N Wirth , A B Mickel , J F Miner, Pascal user manual and report; 3rd ed., Springer-Verlag New York, Inc., New York, NY, 1985
• 9: Neil D. Jones , S. S. Muchnick, Tempo: A Unified Treatment of Binding Time and Parameter Passing Concepts in Programming Languages, Springer-Verlag New York, Inc., Secaucus, NJ, 1978
• 10: K. W. Kennedy, Node listings applied to data flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.10-21, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512978]
• 11: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 12: Melvin Klerer , Jack May, Automatic dimensioning, Communications of the ACM, v.10 n.3, p.165-166, March 1967 [doi>10.1145/363162.363190]
• 13: B. M. Leavenworth, Syntax macros and extended translation, Communications of the ACM, v.9 n.11, p.790-793, Nov. 1966 [doi>10.1145/365876.365879]
• 14: Barbara Liskov , Stephen Zilles, Programming with abstract data types, ACM SIGPLAN Notices, v.9 n.4, p.50-59, April 1974
• 15: The MAD Manual, Computing Center, The University of Michigan, Ann Arbor, 1967.
• 16: Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
• 17: Pratt, T. W., A Theory of Programming Languages: Part I, UTEX-CCSN-41, Dept. of Computer Sciences, Univ. of Texas at Austin, July 1975.
• 18: Tenenbaum, Aaron M., Type Determination in Very High Level Languages, Report No. NSO-3, Courant Inst. of Math. Sciences, New York Univ., 1974.
• 19: Terry Winograd, Breaking the complexity barrier again, Proceedings of the 1973 meeting on Programming languages and information retrieval, p.13-30, November 04-06, 1973, Gaithersburg, Maryland
• 20: Wulf, William A., ALPHARD: Towards a Language to Support Structured Programs, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa., April 1974.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Algorithms, Languages, Performance, Theory