Behavioral semantics of nonrecursive control structures

  • Carl Hewitt
  • Peter Bishop
  • Richard Steiger
  • Irene Greif
  • Brian Smith
  • Todd Matson
  • Roger Hale
Semantique Formelle Formal Semantics
Part of the Lecture Notes in Computer Science book series (LNCS, volume 19)


Knowledge Based Programming is programming in an environment which has substantial knowledge of the semantic domain for which the programs are being written and of the purposes that the programs are supposed to satisfy. Actors are a semantic concept in which no active process is ever allowed to treat anything as an object; instead a polite request must be extended to accomplish what the activator desires. Using actors the PLANNER Project is constructing a Programming Apprentice to make it easier for expert programmers to do knowledge based programming. The apprentice is to aid in establishing and maintaining consistency of specifications, validating that modules meet their specifications, answering questions about behavioral dependencies between modules, and analyzing the implications of perturbations in modules and their specifications.

In The course of this research we have found that we needed to make use of non-recursive control structures and to be able to rigorously formulate their semantics. Our semantics is a generalization of the mathematical semantics of Sco Scott for junctions. Thus it differs from the operational semantic models [such as the CONTOUR model and the Bobrow-Wegbreit mode] that have been proposed which are formulated in terms of operations on activation records. This paper reports some preliminary results and tentative conclusions.


Derivation Tree Terminal Symbol Lambda Calculus Garbage Collector Actor Streamer 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. Barton, R.S."Ideas for Computer Systems Organization: A personal Survey" Software Engineering 1. Academic Press. 1970.Google Scholar
  2. Bobrow D., and Wegbreit, Ben."A Model for Control Structures for Artific Artificial Intelligence Programming Languages" IJCAI-73. August, 1973.Google Scholar
  3. Bochmann, G.V."Multiple Exits from a loop Without the GOTO" CACM. July, 1973. pp.443–444.Google Scholar
  4. Cadiou, J.M. and Levy,"Mechanizable Proofs about Parallel Processes" SWAT. October, 73.Google Scholar
  5. Church, A."The Calculi of Lambda Concersion" Annals of Mathematical Studies 6. Princeton University Press. 1941, 2nd edition 1951.Google Scholar
  6. Davies, D.J.M."POPLER 1.5 Reference Manual" TPU Report No.1. Theoretical Psychology Unit, School of Artificial Intelligence, University of Edinburgh. May, 1973.Google Scholar
  7. Dennis, Jack B."On the Design and Specification of a Common Base Language" Computation Structures Group Memo 60. November 1971.Google Scholar
  8. Dennis, Jack B."Modularity". Computation Structures Group Memo 70. June 1972.Google Scholar
  9. Dijkstra, E.W."The Humble Programmer" CACM. October, 1972.Google Scholar
  10. Dijkstra, E.W."Notes on structured Programming" Aug. 1969.Google Scholar
  11. Evans, A."PAL — A Language for Teaching Programming Linguistics", Proceedings of 23rd National Conference. 1968.Google Scholar
  12. Fischer, M.J."Lambda Calculus Schemata" ACM Conference on Proving Assertions about Programs".Google Scholar
  13. Fisher, D.A. "Control Structures for Programming Languages" Phd. Carnegie 1970.Google Scholar
  14. Floyd, R.W."Assigning Meaning to Programs" Mathematical Aspects of Computer Science. J.T.Schwartz (ed.) Vol 19. Am. Math. Soc. pp.19–32. Providence Rhode Island. 1967.Google Scholar
  15. Greif, I.G. and Hewitt,C. "Behavioral Semantics of ACTOR Systems" Google Scholar
  16. Hewitt,C. and Paterson M."Comparative Schematology" Record of Project MAC Conference on Concurrent Systems and Parallel Computation. June 2–5, 1970. Available from ACM.Google Scholar
  17. Hewitt,C."Procedural Semantics" in Natural Language Processing Courant Computer Science Symposium 8. Randall Rustin, editor. Algorithmics Press. 1971.Google Scholar
  18. Hewitt, C., Bishop P., and Steiger, R."A Universal Modular Actor Formalism for Artificial Intelligence" IJCAI-73. Stanford, Calif. Aug, 1973. pp.235–245.Google Scholar
  19. Hewitt, Carl; Bishop, Peter; Greif, Irene; Smith, Brian; Matson, Todd; and Steiger, R."Actor Induction and Meta-evaluation" Conference Record of ACM Symposium on Principles of Programming Languages. Boston. Oct, 1973.Google Scholar
  20. Hoare, C. A. R."An Axiomatic Definition of the Programming Language PASCAL" February 1972.Google Scholar
  21. Johnston, J.B."The Contour Model of Block Structured Processes" Proceedings of a Symposium on Data Structures in Programming Languages. SIGPLAN Notices 6, 55–82. 1971.Google Scholar
  22. Kahn, G."A Preliminary Theory for Parallel Programs" May 1973.Google Scholar
  23. Kay, Alan C."FLEX, A Flexible Extendible Language" CS Tech. Rept. U. of Utah. 1968.Google Scholar
  24. Kay, Alan C."Reactive Engine" Ph. D. thesis at University of Utah, 1970.Google Scholar
  25. Kay, Alan C. and the Learning Research Group."The SMALL TALK Note Book" Forthcoming.Google Scholar
  26. Kosinski, P."A Data Flow Programming Language" IBM Research Report RC4264. March, 1973.Google Scholar
  27. Landin, P.J."A Correspondence Between ALGOL 60 and Church's Lambda-Natation" CACM. February, 1965.Google Scholar
  28. Liskov, B H."A Design Methodology for Reliable Software Systems" The Last FJCC. December, 1972. Pt. 1, 191–199.Google Scholar
  29. Manna, Z.; Ness,S.; Vuillemin J."Inductive Methods for Proving Properties of Programs" Proceeding of an ACM Conference on Proving Assertions about Programs — January, 1972.Google Scholar
  30. McDermott D.V.; and Sussman G.J."The Conniver Reference Manual" A.I.Memo No. 259. 1972.Google Scholar
  31. McCarthy,J;; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; and Levin, Michael I. "Lisp 1.5. Programmer's Manual, M.I.T.Press" Google Scholar
  32. Minsky, M.L."A LISP Garbage Collector Algorithm Using Serial Secondary Storage" Memorandum MAC-M-129 and AI Memo 58, M.I.T. Project MAC, December 1963.Google Scholar
  33. Mitchell, J.G."The Modular Programming System: Processes and Ports" NIC 7359. June, 1971.Google Scholar
  34. Morris, J.H."Verification-oriented Language Design" Technical Report 7. December, 1972.Google Scholar
  35. Park,D."Fixpoint Induction and Proofs of Program Properties" Machine Intelligence 5. Edinburgh University Press. 1969.Google Scholar
  36. Reynolds,J.C."GEDANKEN-A Simple Typeless Language Based on the Principle of Completeness and the reference Concept" CACM, 1970.Google Scholar
  37. Reynolds,J.C."Definitional Interpreters for Higher-Order Programming Languages" Proceedings of ACM National Convention 1972.Google Scholar
  38. Rulifson Johns F., Derksen J.A., and Waldinger R.J."QA4: A Procedural Calculus for Intuitive Reasoning" Phd. Stanford. November 1972.Google Scholar
  39. Samson,P."STRING" A.I. Memo 142. Sept, 1967.Google Scholar
  40. Scott,D."Outline of a Mathematical Theory of Computation" Proc. Fourth Annual Princeton Conf. on Information Science and Systems. 1970. pp.169–176Google Scholar
  41. Smith, Brian; Waters, Dick; and Lieberman, Henry."COMMENTS ON COMMENTS or the Purpose of Intentions, and the Intentions of Purposes" Term Project for M.I.T. course "Automating Knowledge Based Programming and Validation Using ACTORS" Fall, 1973.Google Scholar
  42. Stoy,J.E. and Strachey,C."OS6-An Experimental Operation System for a Small Computer" Parts 1 and 2. Computer journal. Vol.15, no.2–3. 1972.Google Scholar
  43. Tennent,R.D."Mathematical Semantics of SNOBOL4" Conference Record of ACM Symposium on Principles of Programming Languages. Boston. Oct, 1973.Google Scholar
  44. Tesler, L.G.; Enea, H.J.; and Smith,D.C."The LISP70 Pattern Matching System" IJCAI-73. August 1973.Google Scholar
  45. Wang A. and Dahl O."Coroutine Sequencing in a Block Structured Environment" BIT 11 425–449.Google Scholar
  46. Wirth, N."Program Development by Stepwise Refinement" CACM 14, 221–227. 1971.Google Scholar
  47. Wulf W., et al."BLISS Reference Manual" 1971.Google Scholar
  48. Wulf, W., et al."HYDRA: The Kernel of a Multiprocessor Operating System" CMU. June, 1973.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1974

Authors and Affiliations

  • Carl Hewitt
    • 1
  • Peter Bishop
    • 1
  • Richard Steiger
    • 1
  • Irene Greif
    • 1
  • Brian Smith
    • 1
  • Todd Matson
    • 1
  • Roger Hale
    • 1
  1. 1.Massachusetts Institute of TechnologyUSA

Personalised recommendations