Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A study on transformational semantics

  • III. Program Development By Transformation
  • Chapter
  • First Online:
Program Construction

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 69))

  • 301 Accesses

Abstract

The semantics of a programming language is specified — relative to a kernel language — by reducing certain constructs of the language to more elementary ones by means of definitional transformations. Parallels to the algebraic specification of abstract data types are discussed. This approach of "transformational semantics" is illustrated by explaining program variables in terms of purely applicative constructs.

Dissertation submitted to the Fachbereich Mathematik der Technischen Universität München. This research was carried out within the Sonderforschungsbereich 49, Programmiertechnik, München.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 54.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 69.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. J. W. Thatcher, E.G. Wagner, J.B. Wright: Specification of Abstract Data Types Using Conditional Axioms. IBM Research Report RC-6214, September 1976

    Google Scholar 

  2. A.J. Goguen, J.W. Thatcher, E.G. Wagner: An Initial Algebra Approach to the Specification, Correctness, and Implementation of Abstract Data Types. IBM Research Report RC-6487, October 1976

    Google Scholar 

  3. J.A. Goguen, J.W. Thatcher, E.G. Wagner, J.B. Wright: Initial Algebra Semantics and Continuous Algebras. JACM 24, 1, 68–95 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  4. J.W. Thatcher, E.G. Wagner, J.B. Wright: Data Type Specification: Parametrization and the Power of Specification Techniques. Proc. SIGACT loth Annual Symposium on Theory of Computation, 1978

    Google Scholar 

  5. J. Backus: Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. CACM 21, 8, 613–641 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  6. J.W. de Bakker: Formal Definition of Programming Languages. Mathematical Center Tracts 16, Mathematisch Centrum, Amsterdam (1967)

    Google Scholar 

  7. J.W. de Bakker: Semantics of Programming Languages. In: Tou (ed.): Advances in Information System Science 2, New York: Plenum Press, 1969

    Google Scholar 

  8. J.W. de Bakker: Least Fixed Points Revisited. Theoretical Computer Science 2, 155–181 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  9. F.L. Bauer, H. Wössner: Algorithmic Language and Program Development. Prentice Hall International, London 1979 (to appear)

    Google Scholar 

  10. K.J. Berkling: Reduction Languages for Reduction Machines. GMD, Institut für Informationsforschung, Interner Bericht ISF-76-8, Sept. 1976

    Google Scholar 

  11. G. Birkhoff, J.D. Lipson: Heterogeneous Algebras. Journal of Combinatorial Theory, 8, 115–133 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  12. C. Böhm, G. Jacopini: Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules. CACM 9, 5, 366–371 (1966)

    Article  MATH  Google Scholar 

  13. R.M. Burstall: Semantics of Assignment. In: E. Dale, D. Michie (eds.): Machine Intelligence 2, 3–20, Oliver and Boyd, Edinburgh (1968)

    Google Scholar 

  14. R.M. Burstall: Formal Description of Program Structure and Semantics in First Order Logic. In: B. Meltzer, E. Michie (eds.): Machine Intelligence 5, 79–98, Edinburgh University Press 1970

    Google Scholar 

  15. R.M. Burstall, J. Darlington: Some Transformations for Developing Recursive Programs. Proc. of 1975 Int. Conf. on Reliable Software, Los Angeles 1975, 465–472. Also (revised version) JACM 24: 1, 44–67 (1977)

    Article  MATH  Google Scholar 

  16. R.M. Burstall, J.A. Goguen: Putting Theories Together to Make Specifications. Proc. Int. Joint Conf. on Artificial Intelligence 1977

    Google Scholar 

  17. C. Christensen, C.J. Shaw (eds.): Proc. of the Extensible Languages Symposium, Boston, Mass., May 1969, SIGPLAN Notices 4, 8 (1969)

    Google Scholar 

  18. F.L. Bauer, H. Partsch, P. Pepper, H. Wössner: Techniques for Program Development. Technische Universität München, Institut für Informatik, Internal Report, Sept. 1976. Also in: Software Engineering Techniques. Infotech State of the Art Report 34, 1977

    Google Scholar 

  19. F.L. Bauer, H. Partsch, P. Pepper, H. Wössner: Notes on the Project CIP: Outline of a Transformation System. Technische Universität München, Institut für Informatik, TUM-INFO-7729, July 1977

    Google Scholar 

  20. F.L. Bauer, M. Broy, R. Gnatz, W. Hesse, B. Krieg-Brückner, H. Partsch, P. Pepper, H. Wössner: Towards a Wide Spectrum Language to Support Program Specification and Program Development. SIGPLAN Notices 13 (12), 15–24 (1978). See also this volume.

    Article  MATH  Google Scholar 

  21. M. Broy, W. Dosch, H. Partsch, P. Pepper, M. Wirsing: Abstract Data Types: Some Theoretical Aspects and their Practical Consequences. Technische Universität München (to appear)

    Google Scholar 

  22. M. Broy, R. Gnatz, M. Wirsing: Semantics of Nondeterministic and Noncontinuous Constructs. Proc. International Summer School on Program Construction, Marktoberdorf 1978. This volume.

    Google Scholar 

  23. D.C. Cooper: The Equivalence of Certain Computations. Comp. J. 9, 45–52 (1966)

    Article  MathSciNet  MATH  Google Scholar 

  24. J. Darlington, R.M. Burstall: A System which Automatically Improves Programs. Acta Informatica 6, 41–60 (1976)

    Article  MATH  Google Scholar 

  25. E.W. Dijkstra: Guarded Commands, Nondeterminacy and Formal Derivation of Programs. CACM 18, 453–457 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  26. E.W. Dijkstra: A Discipline of Programming. Prentice Hall, Englewood Cliffs, N.J., 1976

    MATH  Google Scholar 

  27. A.P. Ershov: Problems in Many-Language Systems. Proc. International Summer School on Language Hierarchies and Interfaces, Marktoberdorf 1975, LNCS 46, Berlin-Heidelberg-New York: Springer 1976

    Book  MATH  Google Scholar 

  28. R.W. Floyd: Assigning Meanings to Programs. Proc. American Math. Society Symp. in Appl. Math. 19, 19–32 (1967)

    Article  MathSciNet  MATH  Google Scholar 

  29. S. Gill: Automatic Computing: Its Problems and Prizes. Comp. J. 8, 177–189 (1965)

    Article  Google Scholar 

  30. J.A. Goguen: Abstract Errors for Abstract Data Types. Univ. of California at Los Angeles, Comp. Sc. Dept., Semantics and Theory of Computation Report No. 6, May 1977

    Google Scholar 

  31. D. Gries: The Multiple Assignment Statement. IEEE Trans. on Software Eng., SE-4, 89–91, March 1978

    Google Scholar 

  32. D. Gries: Current Ideas in Programming Methodology. In: P. Wegner (ed.): Research Directions in Software Technology. (to appear)

    Google Scholar 

  33. J.V. Guttag: The Specification and Application to Programming of Abstract Data Types. Univ. of Toronto, Comp. Syst. Research Group, Techn. Report CSRG-59, Sept. 1975

    Google Scholar 

  34. C.A.R. Hoare: An Axiomatic Basis for Computer Programming. CACM 12, 10, 576–581 (1969)

    Article  MATH  Google Scholar 

  35. C.A.R. Hoare: Some Properties of Predicate Transformers. JACM 25, 3, 461–480 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  36. C.A.R. Hoare, P.E. Lauer: Consistent and Complementary Formal Theories of the Semantics of Programming Languages. Acta Informatica, 3, 135–153 (1974)

    MathSciNet  MATH  Google Scholar 

  37. C.A.R. Hoare, N. Wirth: An Axiomatic Definition of the Programming Language PASCAL. Acta Informatica 2, 335–355 (1973)

    Article  MATH  Google Scholar 

  38. S. Igarashi: An Axiomatic Approach to the Equivalence Problems of Algorithms with Applications. PhD Thesis, University of Tokyo (1964). Reprinted in: Report of the Computer Center Univ. of Tokyo 1, 1-1o1 (1968)

    Google Scholar 

  39. D.M. Kaplan: Some Completeness Results in the Mathematical Theory of Computation. JACM 15, 124–134 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  40. D.E. Knuth: Structured Programming with goto Statements. Computing Surveys 8, 261–301 (1974)

    Article  MATH  Google Scholar 

  41. P.J. Landin: The Mechanical Evaluation of Expressions. Comp. J. 6, 4, 308–320 (1964)

    Article  MATH  Google Scholar 

  42. P.J. Landin: A Formal Description of ALGOL 60. In: T.B. Steel jr. (ed.): Formal Language Description Languages for Computer Programming. Proc. IFIP Working Conf. 1964, 266–294, North Holland, Amsterdam (1966)

    Google Scholar 

  43. P.J. Landin: The Next 700 Programming Languages. CACM 9, 157–166 (1966)

    Article  MATH  Google Scholar 

  44. P. Lukas, K. Walk: On the Formal Description of PL/1. In: M.I. Halpern, C.J. Shaw (eds.): Annual Review in Automatic Programming 6, 105–182 (1970)

    Article  Google Scholar 

  45. J. McCarthy: Recursive Functions of Symbolic Expressions and Their Computation by Machine, pt. 1. CACM 3, 4, 184–195 (1960)

    Article  MATH  Google Scholar 

  46. J. McCarthy: Towards a Mathematical Science of Computation. In: C.M. Popplewell (ed.): Information Processing 1962, Proc. IFIP Congress 1962, Amsterdam: North-Holland Publishing Co., 21–28, 1963

    Google Scholar 

  47. J. McCarthy: A Basis for a Mathematical Theory of Computation. In: P. Braffort, D. Hirschberg (eds.): Computer Programming and Formal Systems. North-Holland Publishing Co., Amsterdam 1963

    Google Scholar 

  48. J. McCarthy: A Formal Description of a Subset of ALGOL. In: T.B. Steel jr. (ed.): Formal Language Description Languages for Computer Programming. Proc. IFIP Working Conference 1964, 1–12, North Holland, Amsterdam (1966)

    Google Scholar 

  49. R. Milne, C. Strachey: A Theory of Programming Language Semantics. (2 Volumes) London: Chapman and Hall 1976

    MATH  Google Scholar 

  50. P. Naur: Proof of Algorithms by General Snapshots. BIT 6, 4, 310–316 (1966)

    Article  MathSciNet  Google Scholar 

  51. W.V.D. Quine: Word and Object. MIT Press, Cambridge, Mass. (1960)

    MATH  Google Scholar 

  52. P. Pepper: Theoretische Ansätze für den Entwurf von Prozessoren für wohlstrukturierten Steuerfluß. Technische Universität München, Diplomarbeit 1974

    Google Scholar 

  53. A.J. Perlis, K. Samlson: Preliminary Report — International Algebraic Language. CACM 1, 12, 8–22 (1958)

    Article  MATH  Google Scholar 

  54. A. Salomaa: Formal Languages. New York: Academic Press 1973

    MATH  Google Scholar 

  55. S.A. Schuman, Ph. Jorrand: Definition Mechanisms in Extensible Programming Languages. Proc. AFIPS 1970 Fall Joint Computer Conf., 33, 2, 9–20, 1970

    Google Scholar 

  56. D. Scott: Continuous Lattices. Proc. 1971 Dalhousie Conference, Lecture Notes in Mathematics 274. New York: Springer 1972, 97–136

    Google Scholar 

  57. D. Scott: Data Types as Lattices. Siam J. Comp. 5, 3, 522–587 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  58. D. Scott, C. Strachey: Towards a Mathematical Semantics for Computer Languages. Oxford University, Computing Lab. Techn. Monograph PRG 6, 1971. Also in: J. Fox (ed.): Computers and Automata. Wiley, New York, 1971. pp. 19–46

    Google Scholar 

  59. T.B. Steel jr. (ed.): Formal Language Description Languages for Computer Programming. Proc. IFIP Working Conf. 1964, North Holland, Amsterdam (1966)

    MATH  Google Scholar 

  60. R. Steinbrüggen: Reguläre Baumbereiche. Technische Universität München, Internal Report, August 1977

    Google Scholar 

  61. J.E. Stoy: Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. The MIT Press, Cambridge, Mass. and London, 1977

    MATH  Google Scholar 

  62. C. Strachey: Towards a Formal Semantics. In: T.B. Steel jr. (ed.): Formal Language Description Languages for Computer Programming. North Holland, Amsterdam, 198–220, 1966

    Google Scholar 

  63. R.D. Tennent: The Denotational Semantics of Programming Languages. CACM 19, 8, 437–453 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  64. R.D. Tennent: A Denotational Definition of the Programming Language PASCAL. Queen's University, Kingston, Ontario, Dept. of Computing and Information Sc., Techn. Report 77–47, July 1977

    Google Scholar 

  65. A.N. Whitehead, B. Russell: Principia Mathematica. Cambridge (1910–1913), (2nd ed. 1925–1927)

    Google Scholar 

  66. A. van Wijngaarden: Generalized ALGOL. In: Symbolic Languages in Data Processing, Proc. ICC Symp. Rome, 409–419, Gordon and Breach, New York (1962). Also in: R. Goodman (ed.): Annual Review in Automatic Programming 3, 17–26, Pergamon Press, New York (1963)

    Google Scholar 

  67. A. van Wijngaarden: Recursive Definition of Syntax and Semantics. In: T.B. Steel jr. (ed.): Formal Language Description Languages for Computer Programming. Proc. IFIP Working Conf. 1964, 13–24, North Holland, Amsterdam (1966)

    Google Scholar 

  68. A. van Wijngaarden et al.: Revised Report on the Algorithmic Language ALGOL 68. Acta Informatica 5, 1–236 (1975)

    Article  MATH  Google Scholar 

  69. N. Wirth: A Generallization of ALGOL. CACM 6, 547–554 (1963)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Technische Universität München, Postfach 20 24 20, D-8000, München, Germany

    P. Pepper

Authors
  1. P. Pepper
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Friedrich L. Bauer Manfred Broy E. W. Dijkstra S. L. Gerhart D. Gries M. Griffiths J. V. Guttag J. J. Horning S. S. Owicki C. Pair H. Partsch P. Pepper M. Wirsing H. Wössner

Rights and permissions

Reprints and permissions

Copyright information

© 1979 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Pepper, P. (1979). A study on transformational semantics. In: Bauer, F.L., et al. Program Construction. Lecture Notes in Computer Science, vol 69. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014674

Download citation

  • DOI: https://doi.org/10.1007/BFb0014674

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-09251-3

  • Online ISBN: 978-3-540-35312-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation