Understanding Programming Languages

This book is about describing the meaning of programming languages. The author teaches the skill of writing semantic descriptions as an efficient way to understand the features of a language. While a compiler or an interpreter offers a form of formal description of a language, it is not something that can be used as a basis for reasoning about that language nor can it serve as a definition of a programming language itself since this must allow a range of implementations. By writing a formal semantics of a language a designer can yield a far shorter description and tease out, analyse and record design choices. Early in the book the author introduces a simple notation, a meta-language, used to record descriptions of the semantics of languages. In a practical approach, he considers dozens of issues that arise in current programming languages and the key techniques that must be mastered in order to write the required formal semantic descriptions. The book concludes with a discussion of the eight key challenges: delimiting a language (concrete representation), delimiting the abstract content of a language, recording semantics (deterministic languages), operational semantics (non-determinism), context dependency, modelling sharing, modelling concurrency, and modelling exits. The content is class-tested and suitable for final-year undergraduate and postgraduate courses. It is also suitable for any designer who wants to understand languages at a deep level. Most chapters offer projects, some of these quite advanced exercises that ask for complete descriptions of languages, and the book is supported throughout with pointers to further reading and resources. As a prerequisite the reader should know at least one imperative high-level language and have some knowledge of discrete mathematics notation for logic and set theory. Preface 5 Using this book 7 Writing style 7 Acknowledgements 8 Contents 9 Chapter 1 Programming languages and their description 12 1.1 Digital computers and programming languages 12 1.2 The importance of HLLs 13 1.3 Translators, etc. 16 1.4 Insights from natural languages 18 1.5 Approaches to describing semantics 18 1.6 A meta-language 22 1.7 Further material 25 1.7.1 Further reading 25 1.7.2 Classes of languages 26 1.7.3 Logic of Partial Functions 26 Chapter 2 Delimiting a language 29 2.1 Concrete syntax 29 2.2 Abstract syntax 35 2.3 Further material 41 Projects 41 Further reading 42 Historical notes 42 Chapter 3 Operational semantics 43 3.1 Operational semantics 43 3.2 Structural Operational Semantics 48 3.2.1 Relations 49 3.2.2 Inference rules 50 3.2.3 Non-deterministic iteration 54 3.3 Further material 55 Projects 55 Alternatives 56 Further reading 57 Historical notes 57 Chapter 4 Constraining types 60 4.1 Static vs. dynamic error detection 61 4.2 Context conditions 62 4.3 Semantic objects 66 4.3.1 Input/output 66 4.3.2 Arrays 68 4.3.3 Records 69 4.4 Further material 71 Projects 71 Further reading 71 Chapter 5 Block structure 73 5.1 Blocks 73 5.2 Abstract locations 76 5.3 Procedures 81 5.4 Parameter passing 84 5.4.1 Passing “by reference” 85 5.4.2 Passing “by value” 87 5.5 Further material 88 Projects 88 Further reading 89 Chapter 6 Further issues in sequential languages 90 6.1 Own variables 90 6.2 Objects and methods 91 6.3 Pascal variant records 92 6.4 Heap variables 94 6.5 Functions 96 6.5.1 Marking the return value 96 6.5.2 Side effects 97 6.5.3 Recursion 98 6.5.4 Passing functions as parameters [*] 98 Procedure variables/results 99 6.6 Further material 100 Projects 100 Chapter 7 Other semantic approaches 101 7.1 Denotational semantics 102 7.2 Further material 105 7.3 The axiomatic approach 107 7.3.1 Assertions on states 107 7.3.2 Hoare’s axioms 109 7.3.3 Specification as statements 113 7.3.4 Formal development 114 7.3.5 Data abstraction and reification 118 7.4 Further material 119 7.5 Roles for semantic approaches 122 Chapter 8 Shared-variable concurrency 124 8.1 Interference 124 8.2 Small-step semantics 126 8.3 Granularity 127 8.4 Rely/Guarantee reasoning [*] 129 8.5 Concurrent Separation Logic [*] 131 8.6 Further material 133 Projects 133 Further reading 133 Chapter 9 Concurrent OOLs 135 9.1 Objects for concurrency 136 9.1.1 An example program 136 9.1.2 Semantic objects 138 9.2 Expressions 141 9.3 Simple statements 142 9.4 Creating objects 144 9.5 Method activation and synchronisation 145 9.5.1 Method activation 146 9.5.2 Method synchronisation 147 9.5.3 Delegation 150 9.6 Reviewing COOL 153 The example class 153 COOL summary 154 9.7 Further material 155 Chapter 10 Exceptional ordering [*] 157 10.1 Abnormal exit model 158 10.2 Continuations 160 10.3 Relating the approaches 160 10.4 Further material 161 Projects 161 Historical notes 162 Chapter 11 Conclusions 163 11.1 Review of challenges 163 11.2 Capabilities of formal description methods 164 11.3 Envoi 166 Appendix A Simple language 167 A.1 Concrete syntax 168 A.1.1 Dijkstra style 168 A.1.2 Java-style statement syntax 168 A.2 Abstract syntax 169 A.3 Semantics 170 Statements 170 Expressions 171 Appendix B Typed language 172 B.1 Abstract syntax 173 B.2 Context conditions 174 B.3 Semantics 176 Appendix C Blocks language 178 C.1 Auxiliary objects 179 Objects needed for context conditions 179 Semantic objects 179 C.2 Programs 180 C.3 Statements 180 C.4 Simple statements Assignment 181 C.5 Compound statements 182 C.6 Blocks 183 C.7 Call statements 184 C.8 Expressions 186 Appendix D COOL 187 Abbreviations 187 D.1 Auxiliary objects 188 Types for context conditions 188 Types for semantics 188 D.2 Expressions 189 D.3 Statements 190 D.3.1 Assignments 190 D.3.2 If statements 191 D.4 Methods 192 D.4.1 Activate method 193 D.4.2 Call method 194 D.4.3 Rendezvous 195 D.4.4 Method termination 195 D.4.5 Delegation 196 D.5 Classes 197 D.5.1 Creating objects 198 D.5.2 Discarding references 199 D.6 Programs 200 Appendix E VDM notation 202 E.1 Logical operators 202 E.2 Set notation 203 E.3 List (sequence) notation 204 E.4 Map notation 205 E.5 Record notation 206 E.6 Function notation 206 Appendix F Notes on influential people 207 References 211 Index 225 In This Textbook The Author Focuses On Describing The Semantics Of Programming Languages At A Deep Level. The Topics Covered Include Programming Languages, Operational Semantics, Typing, Block Structure, And Concurrency. The Book Is Suitable For Undergraduate And Graduate Courses In Computer Science And Electronics Engineering.