ONT Re: Program Semantics
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| Algebraic Approaches to Program Semantics
|
| Part 1. Denotational Semantics of Control
|
| Chapter 1. An Introduction to Denotational Semantics
|
|
| 1.3. A Functional Programming Fragment
|
| In his provocative 1977 Turing Award Lecture, John Backus expressed concern
| that many programming languages were syntactically fat and unwieldy but
| semantically lean and inexpressive. In reaction, he proposed a new
| class of languages, the 'functional programming languages', in
| which a "program" is a symbolic input/output function whose
| inputs are not given names: there are no identifiers,
| assignments, or references of any kind to intermediate
| storage and hence there are no side effects (such as
| clashes between local and global variable identifiers)
| to concern the programmer. In this section we present
| a simple functional programming fragment whose principal
| data structures are trees similar to the "s-expressions"
| of the programming language Lisp but many of whose function
| constructors are patterned after those emphasized by Backus.
| Because we delay introduction of repetitive constructs into this
| fragment until our later discussion of recursion in Chapter 5, the
| version of this section temporarily fails to have full computing power.
|
| We shall call our language FPF for "Functional Programming Fragment".
| The syntax of FPF is given in Table 1. Here the colons and periods
| are not among the 32 symbols of the alphabet.
|
| Table 1. The Syntax of FPF
| -------------------------------------------------------------
|
| Alphabet of Symbols
|
| Digits: 0 1 ... 9
|
| Parentheses: ( ) < >
|
| Atomic Functions: id head tail + - * ÷ num =
|
| Function Constructors: !=! o if then else [ ] !a! /
|
| The set !DTN! of 'dynamic trees of numerals' (DTN's for short) is defined by:
|
| Basis Step.
|
| A 'numeral' (i.e., a nonempty string of digits) is a DTN.
|
| Inductive Step.
|
| If t_1 ... t_k are DTN's (k >= 0)
|
| then <t_1, ..., t_k> is a DTN.
|
| The set of 'functions' is defined by:
|
| Basis Step.
|
| An atomic function symbol is a function.
|
| If t is a DTN then !=!t is a function.
|
| Inductive Step.
|
| If f_1 ... f_k are functions (k >= 1)
|
| then so are (f_k o ... o f_1) and [f_1, ..., f_k].
|
| If p, f, g are functions then so is (if p then f else g).
|
| If f is a function then so are (!a!f) and (/f).
|
| -------------------------------------------------------------
|
| The reader need not feel uneasy if Table 1 fails to explain how FPF
| works, since that is the job of semantics: syntax has no meaning!
|
| Manes & Arbib, AAPS, pages 11-12.
|
| Ernest G. Manes & Michael A. Arbib,
|'Algebraic Approaches to Program Semantics',
| Springer-Verlag, New York, NY, 1986.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤