home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / specific / 525 < prev    next >
Encoding:
Text File  |  1992-11-11  |  4.0 KB  |  82 lines
  1. Newsgroups: comp.specification
  2. Path: sparky!uunet!ukma!darwin.sura.net!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!seal.cis.ohio-state.edu!ogden
  3. From: ogden@seal.cis.ohio-state.edu (William F Ogden)
  4. Subject: Re: Semantic definition style
  5. Message-ID: <1992Nov11.195443.23006@cis.ohio-state.edu>
  6. Sender: news@cis.ohio-state.edu (NETnews        )
  7. Organization: The Ohio State University Dept. of Computer and Info. Science
  8. References: <720801988.16035@minster.york.ac.uk>
  9. Date: Wed, 11 Nov 1992 19:54:43 GMT
  10. Lines: 70
  11.  
  12. In article <720801988.16035@minster.york.ac.uk> song@minster.york.ac.uk writes:
  13.  
  14. >I am aware that there are four different styles to define semantics.
  15. >    operational
  16. >    denotational
  17. >    algebraic 
  18. >    axiomatic
  19.  
  20. First, so called `axiomatic' semantics are an unfortunate misclassification
  21. of a proof system as a style of semantics.
  22.  
  23. One of the primary objectiv of semantics is to allow us to formalize the
  24. intuitive notion of correctness of a program. We then have meaningful
  25. basis for discussions of questions about various validation schemes
  26. such as the adequacy of a proposed testing scheme or the soundness of
  27. a proof system or the (relative) completeness of a proof system, etc.
  28.  
  29. Our muddling together of the notions of correctness and provability
  30. is not, I suppose, too surprising in light of the fact that a clear
  31. recognition of this distinction in mathematics awaited the development
  32. of model theory in the 1940's.
  33.  
  34. >Could anyone give some comments on the following questions:
  35. >        what is the relations among these semantics,
  36. >        what is the purpose of each,
  37.  
  38. Another primary objective of semantics is to define formally for users
  39. precisely what they can expect a program will do in all possible
  40. situations. To meet this objective, operational semantics are a very
  41. tempting approach. They generally can be viewed as defining some sort of
  42. automaton and reducing the problem of giving semantics for the programming
  43. language to one of translating the high level language programs into
  44. programs for the automata and then using the usual sequence of states
  45. (computational history) semantics which are the norm when supplying
  46. semantics for automata. The intermediate automata usually have a simpler
  47. and more appropriate architecture than say a 68000 presents. but the
  48. idea is still roughly to explain the semantics of a program by examining
  49. what happens when you compile it for a machine with a really nice
  50. architecture. This implementation oriented approach could be expected
  51. to communicate better with programmers.
  52.  
  53. A third major objective of semantics is to define formally for
  54. implementors precisely what effect their compilers/interpreters are
  55. supposed to produce under all circumstances. This is the objective
  56. which seems to favor denotational semantics. Denotational semantics
  57. are explicit semantics, as opposed to the implicit semantics which result
  58. from the operational approach. I.e., operational semantics produce a
  59. welter of irrelevant information (computational histories), from which the
  60. essential information (the input/output pairs, in the case of sequential
  61. programs) must be extracted. If, for example, a compiler writer has a
  62. target architecture that is wildly different from that of the automaton
  63. used in the operational semantics for his source language or even if
  64. he's just writing a highly optimizing compiler, he's got a real problem
  65. in relating the computational histories his output code will produce
  66. to those described by the semantics. Denotational semantics address this
  67. problem by attempting to produce minimalist semantics which tell the
  68. compiler writer exactly the effect his compiled code should produce and
  69. nothing more. The main drawback of this Spartan approach seems to be
  70. that, of necessity, it leads us into such unfamiliar topics as minimal
  71. fixed points, etc. and thereby makes it more difficult to meet the other
  72. two primary objectives of semantics.
  73.  
  74. Now algebraic semantics would seem to be predicated on the dubious
  75. proposition that computation is entirely describable within a limited
  76. first-order subarea of mathematics -- namely algebra.
  77.  
  78. -- 
  79.  
  80. /Bill
  81.  
  82.