Understanding Programming Languages
Preface

The importance of programming languages

To say that a good programmer can write good software in any language is like saying that a good pilot can fly any aircraft: true, but irrelevant. A passenger aircraft is designed for safety, comfort and economic viability; a military aircraft is designed for performance and mission capability; an ultralite aircraft is designed for low cost and operational simplicity.

The role of language in programming has been downgraded in favor of software methodology and tools; not just downgraded, but totally repudiated when it is claimed that a well-designed system can be implemented equally well in any language. But programming languages are not just a tool; they furnish the raw material of software, the thing we look at on our screens most of the day. I believe that the programming language is one of the most important, not one of the leastimportant, factors that influence the ultimate quality of a software system. Unfortunately, too many programmers have poor linguistic skills. He/she is passionately in love with his/her ``native'' programming language, but is not able to analyze and compare language constructs, nor to understand the advantages and disadvantages of modern languages and language concepts. Too often, one hears statements that demonstrate conceptual confusion: ``Language L1 is more powerful (or more efficient) than language L2''.

This lack of knowledge is a contributing factor to two serious problems in software. The first is the ultra-conservatism that exists in the choice of programming languages. Despite the explosive advances in computer hardware and the sophistication of modern software systems, most programming is still done in languages that were developed about 1970, if not earlier. Extensive research in programming languages is never tested in practice, and software developers are forced to use tools and methodologies to compensate for obsolete language technology. It is as if airlines would refuse to try jet aircraft on the grounds that an old-fashioned propeller aircraft is perfectly capable of getting you from here to there.

The second problem is that language constructs are used indiscriminately, with little or no regard for safety or efficiency. This leads to unreliable software that cannot be maintained, as well as to inefficiencies that are solved by assembly language coding, rather than by refinement of the algorithms and the programming paradigms.

Programming languages exist only for the purpose of bridging the gap in the level of abstraction between the hardware and the real world. There is an inevitable tension between higher levels of abstraction that are easier to understand and safer to use, and lower levels of abstraction that are more flexible and can often be implemented more efficiently. To design or choose a programming language is to select an appropriate level of abstraction, and it is not surprising that different programmers prefer different levels, or that one language may be appropriate for one project and not for another. Within a specific language, a programmer should understand in depth the safety and efficiency implications of each construct in the language.

The aim of the book

The aim of this book is to help the student understand programming languages by analyzing and contrasting language constructs:

What alternatives are available to the language designer?
How are language constructs implemented?
How should they be used?


We have not hesitated to be prescriptive: to claim that accumulated experience shows that certain constructs are to be preferred, and others to be avoided or at least used with caution.

Of course, any book on programming languages should not be taken as a reference manual for any particular language. The goal is to learn to analyze languages and not to study the peculiarities of any language in depth. Nor is the book a guide to the choice of a language for any particular project. The goal is to supply the student with the conceptual tools needed to make such a decision.

Selection of the material

The author of a text on programming languages must necessarily offend at least 3975 of the 4000 or so inventors of programming languages! I made the conscious decision to focus on a very small number of languages (even if it means offending 3994 people), because I believe that I can explain most language concepts using these languages. Other languages are mentioned or surveyed only if they demonstrate some concept that is not found in the languages chosen for the mainstream of the presentation.

Much of the book is concerned with ``ordinary'' imperative languages and two languages have been chosen from this class. Representing languages with a low level of abstraction is C, which has overtaken Fortran as the dominant language in this category. To represent a higher level of abstraction we have chosen Ada which offers a much cleaner definition than the more widely known Pascal.

An additional justification for these choices is that both languages have extensions (C++ and Ada 95) that we can use to study language support for object-oriented programming, currently the dominant programming method.

Unfortunately (I believe) most programming today is still done in imperative languages, but in recent years the quality of implementations for non-imperative languages has improved so that they can be used to develop ``real'' software. The final chapters introduce functional (ML) and logic programming (Prolog) languages in the hope of convincing the student that imperative languages are not conceptual necessities for programming.

The theory of programming language syntax and semantics is beyond the scope of this text. These important subjects are best left to more advanced courses.

To prevent confusion when comparing examples from different languages, an indication like [C++] is attached to each example. In a section that discusses constructs in a specific language, no indication will be given.

Overview of the material

Part I is descriptive, defining and surveying programming languages and environments. Part II explains in great detail the basic constructs of programming languages: types, statements and subprograms. Part III continues the discussion of more advanced programming constructs such as: real numbers, static polymorphism, error handling and concurrency. Part IV is devoted to programming large systems with emphasis on language support for object-oriented programming. Finally, Part V surveys the basic concepts of functional and logic programming.

Teaching recommendations

The prerequisite for this book is at least one year of programming in some language such as Pascal or C. In any case, the student should have a basic reading knowledge of C. A familiarity with the structure and machine code of some computer will also be helpful.

There is too much material for a single course. Parts I and II together with portions of Part IV on modules and object-oriented programming can form the basis of a one-semester course for second-year undergraduates. For advanced undergraduates, the first half can be quickly reviewed in order to concentrate on the more difficult material in Parts III and IV. An advanced course should certainly include Part V supplemented by more material on some non-imperative language chosen by the instructor. Starred sections are more appropriate for advanced students.

It is possible to obtain free compilers for most languages as discussed in Appendix A. Students should also be taught how to examine the assembly language instructions that are emitted by the compilers that they use.

Exercises: since this is a book on programming languages and not on programming, the emphasis in the exercises is not on programming projects. Instead, we ask the students to dig into language descriptions, compare languages and verify compiler implementations of language constructs. The instructor is encouraged to tailor the exercises and append others, according to personal taste and the availability of tools.

The book will also be useful to programmers who wish to deepen their knowledge of the tools they use daily: programming languages.

A personal note

I admit that I prefer higher to lower levels of abstraction. This is not a prejudice, but a ``post-judice''. We software engineers have an exceedingly dismal record when it comes to producing reliable software systems, and I believe that part of the solution lies in higher levels of abstraction in programming languages. To expand on Dijkstra's saying: if you have a 100,000-line program that you can't understand, you should rewrite it as a 10,000-line program in a higher-level programming language.

My formative experience was in the early 1970's as a member of a large team of programmers working on a financial transaction system. We actually installed a new on-line system, even though we knew the system had a bug that we could not locate. Several weeks later the bug was finally trapped: it turned out that poor design of the programming language being used had turned a trivial typographical mistake into a type mismatch. A couple of years later when I first saw Pascal, I was hooked. The addiction deepened each time I helped a scientist who had wasted weeks of his/her life searching for a bug that would not have compiled successfully in Pascal. While type mismatch is certainly not the only source of programming error, it is so common and so dangerous, yet so simple to catch, that I would no more abandon strong type checking than I would drive without a seat-belt: it may be uncomfortable but even the best drivers can be involved in an accident and the discomfort is trivial relative to the potential damage.

I do not wish to get involved in language ``wars'' claiming that one language is better than another for any specific machine or application. I have attempted to analyze language constructs as objectively as I can in the hope that this will contribute to making discussions about language more scientific.

Acknowledgements

I would like to thank Kevlin A.P. Henney and David W. Barron for comprehensive reviews of the manuscript, as well as Harry Mairson, Tamar Benaya and Bruria Haberman who read portions of the manuscript. I am indebted to Amiram Yehudai for serving as my object-oriented guru: guiding me during numerous discussions and carefully checking the relevant chapters. Edmond Schonberg, Robert Dewar and their team at NYU quickly responded to my questions on GNAT, making it possible for me to learn and to write about Ada 95 even before a full compiler was available. Ian Joyner kindly provided his unpublished analysis of C++ which was most helpful. Like my previous books, this book would probably not have been written without Leslie Lamport's LaTeX!

It has been my privilege to work with a very professional and efficient publishing team at John Wiley, and I would like to thank them, especially my editor Gaynor Redvers-Mutton, for this opportunity.

Table of Contents

Chapter 1 What Are Programming Languages? 3
1.1 The wrong question 3
1.2 Imperative languages 5
1.3 Data-oriented languages 10
1.4 Object-oriented languages 14
1.5 Non-imperative languages 15
1.6 Standardization 16
1.7 Computer architecture 17
1.8 * Computability 20
1.9 Exercises 21
Chapter 2 Elements of Programming Languages 23
2.1 Syntax 23
2.2 * Semantics 25
2.3 Data 27
2.4 The assignment statement 28
2.5 Type checking 29
2.6 Control statements 30
2.7 Subprograms 31
2.8 Modules 31
2.9 Exercises 33
Chapter 3 Programming Environments 35
3.1 Editor 36
3.2 Compiler 36
3.3 Librarian 39
3.4 Linker 40
3.5 Loader 41
3.6 Debugger 41
3.7 Profiler 42
3.8 Testing tools 43
3.9 Configuration tools 43
3.10 Interpreters 44
3.11 Exercises 45
Chapter 4 Elementary Data Types 49
4.1 Integer types 49
4.2 Enumeration types 54
4.3 Character type 57
4.4 Boolean type 59
4.5 * Subtypes 60
4.6 * Derived types 61
4.7 Expressions 63
4.8 Assignment statements 67
4.9 Exercises 69
Chapter 5 Composite Data Types 71
5.1 Records 71
5.2 Arrays 74
5.3 Arrays and type checking 77
5.4 * Array subtypes in Ada 80
5.5 String type 81
5.6 Multi-dimensional arrays 83
5.7 Array implementation 84
5.8 * Representation specification 88
5.9 Exercises 93
Chapter 6 Control Structures 95
6.1 switch -/ case -statements 95
6.2 if -statements 100
6.3 Loop statements 105
6.4 for -statements 108
6.5 Sentinels 114
6.6 * Invariants 115
6.7 goto -statements 117
6.8 Exercises 119
Chapter 7 Subprograms 121
7.1 Subprograms: procedures and functions 121
7.2 Parameters 123
7.3 Passing parameters to a subprogram 125
7.4 Block structure 135
7.5 Recursion 141
7.6 Stack architecture 143
7.7 More on stack architecture 150
7.8 * Implementation on the 8086 153
7.9 Exercises 155
Chapter 8 Pointers 159
8.1 Pointer types 159
8.2 Data structures 166
8.3 Memory allocation 172
8.4 Algorithms for heap allocation 176
8.5 Exercises 179
Chapter 9 Real Numbers 181
9.1 Representations of real numbers 181
9.2 Language support for real numbers 185
9.3 The three deadly sins 189
9.4 * Real types in Ada 191
9.5 Exercises 192
Chapter 10 Polymorphism 195
10.1 Type conversion 195
10.2 Overloading 197
10.3 Generics 198
10.4 Variant records 202
10.5 Dynamic dispatching 206
10.6 Exercises 206
Chapter 11 Exceptions 209
11.1 Exception handling requirements 209
11.2 Exceptions in PL/I 211
11.3 Exceptions in Ada 211
11.4 Exceptions in C++ 214
11.5 Error handling in Eiffel 215
11.6 Exercises 219
Chapter 12 Concurrency 221
12.1 What is concurrency? 221
12.2 Shared memory 222
12.3 The mutual exclusion problem 224
12.4 Monitors and protected objects 226
12.5 Message passing 228
12.6 occam 228
12.7 Ada rendezvous 229
12.8 Linda 232
12.9 Exercises 233
Chapter 13 Program Decomposition 239
13.1 Separate compilation 240
13.2 Why are modules needed? 245
13.3 Packages in Ada 246
13.4 Abstract data types in Ada 251
13.5 How to write modules in C++ 257
13.6 Exercises 260
Chapter 14 Object-Oriented Programming 263
14.1 Object-oriented design 263
14.2 Object-oriented programming in C++ 266
14.3 Inheritance 268
14.4 Dynamic polymorphism in C++ 270
14.5 Object-oriented programming in Ada 95 277
14.6 Exercises 283
Chapter 15 More on Object-Oriented Programming 285
15.1 Structuring classes 286
15.2 Access to private components 293
15.3 Class data 298
15.4 The Eiffel programming language 302
15.5 Design considerations 309
15.6 Methods of dynamic polymorphism 313
15.7 Exercises 313
Chapter 16 Functional Programming 317
16.1 Why functional programming? 317
16.2 Functions 318
16.3 Compound types 320
16.4 Higher-order functions 322
16.5 Lazy and eager evaluation 325
16.6 Exceptions 327
16.7 Environments 328
16.8 Exercises 329
Chapter 17 Logic Programming 331
17.1 Pure logic programming 332
17.2 Unification 335
17.3 Prolog 337
17.4 Advanced logic programming concepts 345
17.5 Exercises 347
Chapter 18 Java 349
18.1 The Java model 349
18.2 The Java Language 352
18.3 Reference semantics 352
18.4 Polymorphic data structures 356
18.5 Encapsulation 357
18.6 Concurrency 360
18.7 The Java Libraries 362
18.8 Exercises 363
Appendix A Where to Get Compilers 365
Appendix B Selected Bibliography 367