139,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
This book the first of two volumes explores the syntactical constructs of the most common programming languages, and sheds a mathematical light on their semantics, while also providing an accurate presentation of the material aspects that interfere with coding. Concepts and Semantics of Programming Languages 1 is dedicated to functional and imperative features. Included is the formal study of the semantics of typing and execution; their acquisition is facilitated by implementation into OCaml and Python, as well as by worked examples. Data representation is considered in detail: endianness, pointers, memory management, union types and pattern-matching, etc., with examples in OCaml, C and C++. The second volume introduces a specific model for studying modular and object features and uses this model to present Ada and OCaml modules, and subsequently Java, C++, OCaml and Python classes and objects. This book is intended not only for computer science students and teachers but also seasoned programmers, who will find a guide to reading reference manuals and the foundations of program verification.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 453
Veröffentlichungsjahr: 2021
Ähnliche
Table of Contents
Cover
Title Page
Copyright
Foreword
Preface
1 From Hardware to Software
1.1. Computers: a low-level view
1.2. Computers: a high-level view
2 Introduction to Semantics of Programming Languages
2.1. Environment, memory and state
2.2. Evaluation of expressions
2.3. Definition and assignment
2.4. Exercises
3 Semantics of Functional Features
3.1. Syntactic aspects
3.2. Execution semantics: evaluation functions
3.3. Execution semantics: operational semantics
3.4. Evaluation functions versus evaluation relations
3.5. Semantic properties
3.6. Exercises
4 Semantics of Imperative Features
4.1. Syntax of a kernel of an imperative language
4.2. Evaluation of expressions
4.3. Evaluation of definitions
4.4. Operational semantics
4.5. Semantic properties
4.6. Procedures
4.7. Other approaches
4.8. Exercises
5 Types
5.1. Type checking: when and how?
5.2. Informal typing of a program Exp
2
5.3. Typing rules in Exp
2
5.4. Type inference algorithm in Exp
2
5.5. Properties
5.6. Typechecking of imperative constructs
5.7. Subtyping and overloading
6 Data Types
6.1. Basic types
6.2. Arrays
6.3. Strings
6.4. Type definitions
6.5. Generalized conditional
6.6. Equality
7 Pointers and Memory Management
7.1. Addresses and pointers
7.2. Endianness
7.3. Pointers and arrays
7.4. Passing parameters by address
7.5. References
7.6. Memory management
8 Exceptions
8.1. Errors: notification and propagation
8.2. A simple formalization: ML-style exceptions
8.3. Exceptions in other languages
Conclusion
Appendix: Solutions to the Exercises
List of Notations
Index of Programs
References
Index
End User License Agreement
List of Illustrations
Chapter 1
Figure 1.1.
Binary half-adder
Figure 1.2.
“Hello world!” in C and in x86-64 instructions
Figure 1.3.
Function calls and return addresses
Figure 1.4.
Coding the ADD instruction in MIPS32®
Figure 1.5.
Compilation process
Chapter 5
Figure 5.1. Covariance and contravariance. For a color version of this figure, s...
Chapter 6
Figure 6.1 Encoding a floating point number over 32 bits. For a color version of...
Chapter 7
Figure 7.1. Schematic representation of memory and address. For a color version ...
Figure 7.2. Pointer to a pointer. For a color version of this figure, see www.is...
Figure 7.3.
Cycle and reference counter. For a color version of this figure, see
...
Figure 7.4.
List of free blocks. For a color version of this figure, see
www.ist...
Figure 7.5.
Freeing and fragmentation. For a color version of this figure, see
w...
Figure 7.6. Copying and compacting in a copying GC. For a color version of this ...
List of Tables
Chapter 2
Table 2.1.
Language of expressions
Exp
1
Table 2.2.
Evaluation of the expressions of
Exp
1
Table 2.3.
Language
Def 1
of definitions
Chapter 3
Table 3.1.
Syntax of the language of expressions
Exp
2
Table 3.2.
Interpretation of operators
Table 3.3.
Evaluation of expressions in
Exp
2
Chapter 4
Table 4.1.
Language of defintions
Def3
Table 4.2.
Language of expressions
Exp
3
Table 4.3.
Language of commands
Lang
3
Table 4.4.
Evaluation of expressions in
Exp
3
Table 4.5.
Extension of relation
→Def
3
: procedures
Chapter 5
Table 5.1.
Type algebra for
Exp
2
Table 5.2.
Type algebra of
Lang
3
Chapter 6
Table 6.1.
Integer size by language
Table 6.2.
Data range by type
Table 6.3.
Extension of the syntax of
Exp
2
for pattern matching
Chapter 8
Table 8.1.
Extension of the syntax of
Exp
2
to include exceptions
Guide
Cover
Table of Contents
Title Page
Copyright
Foreword
Preface
Begin Reading
Conclusion
Appendix: Solutions to the Exercises
List of Notations
Index of Programs
References
Index
End User License Agreement
Pages
v
iii
iv
xi
xii
xiii
xiv
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
257
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
287
288
289
290
291
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
Series EditorJean-Charles Pomerol
Concepts and Semantics of Programming Languages 1
A Semantical Approach with OCaml and Python
Thérèse Hardin
Mathieu Jaume
François Pessaux
Véronique Viguié Donzeau-Gouge
First published 2021 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
part from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd
John Wiley & Sons, Inc.
27-37 St George’s Road
111 River Street
London SW19 4EU
Hoboken, NJ 07030
UK
USA
www.iste.co.uk
www.wiley.com
© ISTE Ltd 2021
The rights of Thérèse Hardin, Mathieu Jaume, François Pessaux and Véronique Viguié Donzeau-Gouge to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2021930488
British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British Library
ISBN 978-1-78630-530-5
Foreword
Computer programs have played an increasingly central role in our lives since the 1940s, and the quality of these programs has thus become a crucial question. Writing a high-quality program – a program that performs the required task and is efficient, robust, easy to modify, easy to extend, etc. – is an intellectually challenging task, requiring the use of rigorous development methods. First and foremost, however, the creation of such a program is dependent on an in-depth knowledge of the programming language used, its syntax and, crucially, its semantics, i.e. what happens when a program is executed.
The description of this semantics puts the most fundamental concepts into light, including those of value, reference, exception or object. These concepts are the foundations of programming language theory. Mastering these concepts is what sets experienced programmers apart from beginners. Certain concepts – like that of value – are common to all programming languages; others – such as the notion of functions – operate differently in different languages; finally, other concepts – such as that of objects – only exist in certain languages. Computer scientists often refer to “programming paradigms” to consider sets of concepts shared by a family of languages, which imply a certain programming style: imperative, functional, object-oriented, logical, concurrent, etc. Nevertheless, an understanding of the concepts themselves is essential, as several paradigms may be interwoven within the same language.
Introductory texts on programming in any given language are not difficult to find, and a number of published books address the fundamental concepts of language semantics. Much rarer are those, like the present volume, which establish and examine the links between concepts and their implementation in languages used by programmers on a daily basis, such as C, C++, Ada, Java, OCaml and Python. The authors provide a wealth of examples in these languages, illustrating and giving life to the notions that they present. They propose general models, such as the kitpresented in Volume 2, permitting a unified view of different notions; this makes it easier for readers to understand the constructs used in popular programming languages and facilitates comparison. This thorough and detailed work provides readers with an understanding of these notions and, above all, an understanding of the ways of using the latter to create high-quality programs, building a safer and more reliable future in computing.
Gilles DOWEKResearch Director, InriaProfessor at the École normale supérieure, Paris-Saclay
Catherine DUBOIS
Professor at the École nationale supérieure
d’informatique pour l’industrie et l’entreprise
January 2021
Preface
This two-volume work relates to the field of programming. First and foremost, it is intended to give readers a solid grounding in the bases of functional or imperative programming, along with a thorough knowledge of the module and class mechanisms involved. In our view, the semantics approach is most appropriate when studying programming, as the impact of interlanguage syntax differences is limited. Practical considerations, determined by the material characteristics of computers and/or “smart” devices, will also be addressed. The same approach will be taken in both volumes, using both mathematical formulas and memory state diagrams. With this book, we hope to help readers understand the meaning of the constructs described in the reference manuals of programming languages and to establish solid foundations for reasoning and assessing the correctness of their own programs through critical review. In short, our aim is to facilitate the development of safe and reliable programs.
Volume 1 begins with a presentation of the computer, in Chapter 1, first at the material level – as an assemblage of components – then as a tool for executing programs. Chapter 2 is an intuitive, step-by-step introduction to language semantics, intended to familiarize readers with this approach to programming. In Chapter 3, we provide a detailed discussion on the subject, with a formal presentation of the execution semantics of functional features. Chapter 4 continues with the same topic, looking at the execution semantics of imperative features. In these two chapters, a clear mathematical framework is used to support our presentation. Also, all of the notions which we introduce in these chapters are implemented in both Python and OCaml to assist readers learning about the semantic concepts in question for the first time. Multiple exercises, with detailed solutions, are provided in both cases. Chapter 5, on the subject of typing, begins by addressing typing rules, which are used to check programs; we then present the algorithm used to infer polymorphic types, along with the associated mathematical notions, all implemented in both languages. Finally, the extension of typing to imperative features is addressed. In Chapter 6, we present the main data types and methods of pattern matching, using a range of examples expressed in different programming languages. Chapter 7 focuses on low-level programming features: endianness, pointers and memory management; these notions are mostly presented using C and C++. Volume 1 ends with a discussion of error processing using exceptions, their semantics is presented in OCaml, and the exception management mechanisms used in Python, Java and C++ are also described (see Chapter 8).
Thus, Volume 1 is intended to give a broad overview of the functional and imperative features of programming, from notions that can be modeled mathematically to notions that are linked to the hardware configuration of computers themselves. Volume 2 focuses on modular and object programming, building on the foundations laid down in Volume 1 since modules, classes and objects are, in essence, the means of organizing functional or imperative constructs. Volume 2 first analyzes the needs of developers in terms of tools for software architecture. Based on this study, an original semantic model, called a kit, is drawn up, jointly presenting all the features of the modules and objects that can meet these needs. The semantics of these kits are defined in a rather informal way, as research in this field has not yet led to a mathematical model of this set of features, while remaining relatively simple. From this model, we consider a set of emerging questions, the objective of which is to guide the acquisition of a language. This approach is then exemplified by the study of the module systems of Ada, OCaml and C. Finally, the same approach will be used to deduce a semantic model of class and object features, which will serve to present classes in Java, C++, OCaml and Python from a unified perspective.
This work is aimed at a relatively wide audience, from experienced developers – who will find valuable additional information on language semantics – to beginners who have only written short programs. For beginners, we recommend working on the semantic concepts described in Volume 1 using the implementations in OCaml or Python to ease assimilation. All readers may benefit from studying the reference manual of a programming language, while comparing the presentations of constructs given in the manual with those given here, guided by the questions mentioned in Volume 2.
Note that we do not discuss the algorithmic aspect of data processing here. However, choosing the algorithm and the data representation that fit the requirements of the specification is an essential step in program development. Many excellent works have been published on this subject, and we encourage readers to explore the subject further. We also recommend using the standard libraries provided by the chosen programming language. These libraries include tried and tested implementations for many different algorithms, which may generally be assumed to be correct.
