Therese Hardin - Concepts and Semantics of Programming Languages 1

1 Cover

2 Title Page Series EditorJean-Charles Pomerol

3 Copyright 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

4 Foreword

5 Preface

6 1 From Hardware to Software 1.1. Computers: a low-level view 1.1. Computers: a low-level view Computer science is the science of rational processing of information by computers. Computers have the capacity to carry out a variety of processes, depending on the instructions given to them. Each item of information is an element of knowledge that may be transmitted using a signal and encoded using a sequence of symbols in conjunction with a set of rules used to decode them, i.e. to reconstruct the signal from the sequence of symbols. Computers use binary encoding, involving two symbols; these may be referred to as “true”/”false”, “0”/”1” or “high”/”low”; these terms are interchangeable, and all represent the two stable states of the electrical potential of digital electronic circuits. 1.2. Computers: a high-level view 1.2. Computers: a high-level view The low-level vision of a von Neumann machine presented in section 1.1 provides a good overview of the components of a computer and of program execution, without going into detail concerning the operations of electronic components. However, this view is not particularly helpful in the context of everyday programming activity. Programs in binary code, or even assembly code, are difficult to write as they need to take account of every detail of execution; they are, by nature, long and hard to review, understand and debug. The first “high-level” programming languages emerged very shortly after the first computers. These languages assign names to certain values and addresses in the memory, providing a set of instructions that can be split into low-level machine instructions. In other terms, programming languages offer an abstract vision of the computer, enabling users to ignore low-level details while writing a program. The “hello world” program in Figure 1.2 clearly demonstrates the power of abstraction of C compared to the X86 assembly language.

7 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

8 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

9 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

10 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

11 6 Data Types6.1. Basic types 6.2. Arrays 6.3. Strings 6.4. Type definitions 6.5. Generalized conditional 6.6. Equality

12 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

13 8 Exceptions8.1. Errors: notification and propagation 8.2. A simple formalization: ML-style exceptions 8.3. Exceptions in other languages

14 Conclusion

15 Appendix: Solutions to the Exercises

16 List of Notations

17 Index of Programs

18 References

19 Index

20 End User License Agreement

1 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

2 Chapter 5Figure 5.1. Covariance and contravariance. For a color version of this figure, s...

3 Chapter 6Figure 6.1 Encoding a floating point number over 32 bits. For a color version of...

4 Chapter 7Figure 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 ...

1 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

2 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

3 Chapter 4Table 4.1. Language of defintions Def3Table 4.2. Language of expressions Exp 3Table 4.3. Language of commands Lang 3Table 4.4. Evaluation of expressions in Exp 3Table 4.5. Extension of relation →Def 3 : procedures

4 Chapter 5Table 5.1. Type algebra for Exp 2Table 5.2. Type algebra of Lang 3

5 Chapter 6Table 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

6 Chapter 8Table 8.1. Extension of the syntax of Exp 2 to include exceptions

1 Cover

2 Table of Contents

3 Title Page Series EditorJean-Charles Pomerol

4 Copyright 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