Concepts and Semantics of Programming Languages 2
Description
Concepts and Semantics of Programming Languages 2 presents an original semantic model, collectively taking into account all of the constructs and operations of modules and classes: visibility, import, export, delayed definitions, parameterization by types and values, extensions, etc. The model serves for the study of Ada and OCaml modules, as well as C header files. It can be deployed to model object and class features, and is thus used to describe Java, C++, OCaml and Python classes.
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.
More details
Other editions
Additional editions
Persons
Mathieu Jaume is a lecturer at the Laboratoire d'Informatique de Paris 6 (LIP6), Sorbonne University, France.
François Pessaux is Associate Professor in the Computer Science and Systems Engineering Unit (U2IS) of ENSTA Paris, France.
Veronique Viguie Donzeau-Gouge is Professor Emeritus at the Centre d'études et de recherche en informatique (CEDRIC) of the Conservatoire national des arts et métiers (Cnam Paris), France.
Content
Preface xi
Chapter 1. Namespaces: Model and Operations 1
1.1. Reusing, dividing, confining 2
1.1.1. Analysis of some developer needs 2
1.1.2. Meeting developer needs 3
1.2. Namespaces 5
1.2.1. Namespaces definition 6
1.2.2. Extending notions of environment and binding 8
1.3. kit development 12
1.3.1. Namespace of a kit 14
1.3.2. Order of fields introduction 15
1.3.3. Typing kits 15
1.3.4. kit values 18
1.3.5. kit export, confining fields 22
1.3.6. kits import 28
1.3.7. Stages of kit development 32
1.4. Incomplete kits 33
1.4.1. Type and value of an incomplete kit 34
1.4.2. Completion of an incomplete kit 34
1.4.3. Confining an incomplete kit 36
1.5. Parameterized kits 36
1.5.1. kits parameterized by a type 36
1.5.2. kits parameterized by types and values 41
1.5.3. Confinement, parametrization, incomplete kits and export 45
1.6. Functors of kits 46
1.7. kit extension 49
1.7.1. Presentation of extension 49
1.7.2. Confinement and extension 55
1.8. Conclusion 59
Chapter 2. Modules 61
2.1. Modules in Ada 62
2.1.1. Developing modules 62
2.1.2. Export and confinement 65
2.1.3. Nesting modules 66
2.1.4. Importing a module 66
2.1.5. Flattening an import 67
2.1.6. Generic modules 68
2.1.7. Modules and separate compilation 71
2.2. Modules in OCaml 71
2.2.1. Module definition 72
2.2.2. Export and confinement 73
2.2.3. Confinement of type definitions 78
2.2.4. Functors 82
2.3. Modularity, namespaces and W-kit 85
2.3.1. Declaration interfaces 85
2.3.2. W-kits 86
2.3.3. Modularity and header files in C 86
Chapter 3. Class and Object Features 93
3.1. Object-oriented features 93
3.1.1. Objects 94
3.1.2. Classes 95
3.2. kits and object features 104
3.2.1. Modeling classes 104
3.2.2. Modeling objects 107
3.2.3. Inheritance, redefinition and late binding 109
3.2.4. Incomplete C-kits, parameterized C-kits 113
3.2.5. Subclassing, subtyping 115
3.2.6. Type languages, classes and objects 119
Chapter 4. Classes in Selected Languages 123
4.1. Classes in Java 123
4.1.1. General presentation 123
4.1.2. Modules and packages 124
4.1.3. Classes 125
4.1.4. Marks 131
4.1.5. Developing classes 134
4.2. Classes in C++ 144
4.2.1. Header files, namespaces, confinement 145
4.2.2. Classes 148
4.2.3. Inheritance and confinement 155
4.2.4. Overloading in C++ 165
4.2.5. Parameterized classes 168
4.3. Classes in OCaml 174
4.3.1. Presentation 174
4.3.2. An overview of classes 174
4.3.3. Marks, incomplete classes, parametrization 181
4.3.4. Objects 186
4.3.5. Class signatures: confinement and inheritance 192
4.3.6. Multiple inheritance 195
4.3.7. Other features 197
4.4. Presentation of Python 197
4.4.1. Getting started 198
4.4.2. An overview of classes, modules and types 199
4.4.3. Names and assignment 208
4.4.4. Assignment and typechecking 211
4.4.5. Overloading 213
4.4.6. Modules and packages 217
4.4.7. Confinement 218
4.4.8. Inheritance 219
4.4.9. Incomplete C-kits and abstract classes 221
4.4.10. Other features 222
Appendix: Questions to Guide Learning 225
List of Notations 229
References 231
Index 233
2
Modules
The need to split source files, to confine, to reuse fragments of programs to achieve the rational development for a software system arose very early in the history of programming [PAR 72]. This has been studied in Chapter 1 where kits are presented as a model that is a general answer to this need. To implement this model, some programming languages provide a dedicated construct often referred to by the generic name module. We examine them in this chapter.
Modules appeared in the early 1980s, under the name structure in STANDARD ML [MIL 19], module in OCaml [INR 19], package in Ada [AUT 19] or cluster [LIS 81] for instance.
At the same time as module creation, the theory of algebraic abstract data types (ADT) [GOG 78] was under development. It formally models the notion of a data set associated with operations as a term algebra whose properties are stated by equations between terms. This allows one to formally reason about these sets independently from their implementation. Any model consistent with these equations defines a semantics of the ADT. ADTs have been a great source of inspiration for designing the modules of the current languages.
Modules of programming languages are implementations of kits. They all allow us to manipulate a collection of type definitions and values but also, depending on the language, of constants, variables, functions, procedures, classes, exceptions or modules. Thus, we find in this list all the ingredients of a kit. Whatever the language, modules define their own namespace and provide import, export and flattening operations, as presented in Chapter 1. Their semantics is built on that of the imperative and/or functional features of the language, especially on the notions of typing and scope. These features have been studied in Volume 1.
This chapter presents implementations of kits in several languages and answers, in this context, some of the questions raised in Chapter 1. These languages are the following:
- - Ada is one of the first programming languages (the first compiler was released in 1983), still used today, providing constructs that allow real modular programming. Its module language is pretty simple and allows a nearly immediate illustration of the study made in Chapter 1;
- - OCaml, which is more recent, offers a powerful module language: a module is a first-class value, hence it can be typed, computed, handled as any other value. The semantics of OCaml's modules is an enrichment of the kits' semantics;
- - C is a language with no real dedicated constructs for modular programming. It only provides a few features, allowing us to implement a weak notion of a kit, called a W-kit. Section 2.3.3, dedicated to C, gives some hints on a programming discipline to follow along implementations of W-kits in order to achieve a modular development.
2.1. Modules in Ada
Ada is an imperative language with a static scope. Types of components must be declared. It is strongly and statically typed, with type verification. It allows the overloading of functions and constants with different types (see section 5.7.2 of Volume 1). It is compiled into native code (Ans. 1.1). Ada provides constructs for modular but also for real-time, concurrent and distributed programming. Since [ADA 95], the language supports object-oriented features and since [ADA 12], it allows contract-based development: properties are stated by pre- and post-conditions which are checked at runtime (see section 4.7.2 of Volume 1 where pre- and post-conditions are studied). The definition and management of modules were available in the first versions of the language. They were enriched as successive versions progressed. The different evolutions of this language [ADA 95, ADA 05, ADA 12] have always been internationally standardized, a point which guarantees the full compatibility of the object code produced by the various compilers on the market. To get a complete presentation of Ada, the reader may refer to the reference manuals [AUT 19]. In this book, we only present modules.
2.1.1. Developing modules
A module of Ada is an implementation of a kit (Ans. 1.2). It is introduced by the keyword package and defined in two steps, by first providing its specification, then its body. The specification (also called the interface) introduces the module name and the declarations of the fields the developer does not confine. These declarations of functions, procedures, variables, types, constants, modules and exceptions can also be defined at this point. Example 2.1 introduces a module to define a list of integers implemented using pointers. The specification part declares the name of the module, the types used to build values, the operations to manipulate these values and an exception. The mutual recursion between types link and int_l requires a preliminary introduction of the name link. The same can be said for the mutual recursion between functions. There is no dedicated keyword for recursion (Ans. 1.10 and Ans. 1.11).
EXAMPLE 2.1.-
Ada -- Specification part package L_integers is type link ; -- Declaration of an element's type. type int_l is access link ; -- Type pointer to a link. type link is -- Definition of type link. record v: integer; s: int_l ; end record ; function cons (n: integer; l: int_l) return int_l ; function empty return int_l ; function is_empty (l: int_l) return boolean ; function head (l: int_l) return integer ; function tail (l: int_l) return int_l ; specification_error: exception ; end L_integers ; The body of the module contains the definitions of all the fields only declared in the specification part of the module and these definitions repeat the declarations of the completed fields.
New functions/procedures, variables, types, modules, etc. can be defined in the body of the module, without being declared in the specification part, and then they are confined inside the body.
Example 2.2 extends example 2.1 by defining the body of the module L_integers.
EXAMPLE 2.2.-
Ada package body L_integers is function cons (n: integer; l: int_l) return int_l is ... function empty return int_l is ... function is_empty (l: int_l) return boolean is ... function head (l: int_l) return integer is ... function tail (l: int_l) return int_l is ... procedure proc ( ... raise specification_error ...) end L_integers ; A module specification can be seen as an incomplete kit, completion being performed in one unique step by the definition of the module's body (Ans. 1.27 and Ans. 1.28). Definition and declaration types must be identical.
2.1.1.1. Namespace
As with any kit, a module introduces a namespace in which names are accessible from outside using the dot-notation. In Ada, this namespace is not divided into sub-spaces. Thus, it contains all the names of types, variables and functions, etc. introduced by this module. This implies that types, variables, functions cannot have the same names (except in the case of overloading, which is described later) (Ans. 1.3 and Ans. 1.9).
Thus, the namespace introduced by the module L_integers of example 2.2 is: (link, int_l, cons, empty, ..., specification_error, proc).
2.1.1.2. Type and value of a module
Types and values are defined and computed as indicated for kits (Ans. 1.5 and Ans. 1.6). For instance, the type of L_integers involves the name of the module and the names and types of the fields:
L_integers: link: (v: integer; s: int_l) ; int_l: (access link) ; cons: (integer * int_l -> int_l) ; ... If we had defined another module M containing the same fields as L_integers, then types M.link and L_integers.link would be different (Ans. 1.7): typing is nominal.
As for kits, declarations are sequentially evaluated, i.e. they follow the order of the text. Any declaration can make reference to a previous one but never to a future one. This is the reason for the preliminary declaration of link (Ans. 1.10 and Ans. 1.11).
Evaluating an Ada module requires two steps. First, the evaluation of the specification of L_integers in the current environment Env1 binds the name L_integers to the result of the evaluation of the fields declared and defined in this specification. Next comes the evaluation of the module's body in the current environment Env2, which completes the value. Beware, Env1 and Env2 can be different and the memory Mem may have changed between the two steps.
Let us detail the evaluation of L_integers. Let Env be the current environment:
- 1) the name
L_integersis bound in Env to the value to be defined and denoted by ??, which produces the environment (L_integers, ??) ? Env; - 2) by sequential evaluation of the specification's fields, a temporary value
v_L_integers = (cons: ?? ; empty: ?? ; ...; specification_error: exception)is built. This value only introduces the names of the fields, bound to "temporary" values ??;
- 3) the binding of...
