Programming Language Design Concepts

by Watt, David A.

• ISBN13: 9780470853207
• ISBN10: 0470853204
• Edition: 1st
• Format: Paperback
• Copyright: 2004-05-21
• Publisher: WILEY

Summary

Programming languages exist to communicate with computers and also with people. A good language, like a good mathematical notation, helps us to formulate and communicate ideas more quickly. Yet there are many programming languages and many features to understand in each.

Author Biography

David Watt is a Professor of Computing Science at Glasgow University. His research interests include the design, specification, and implementation of programming languages, and he has published several books on the topic. He has many years of teaching experience on this and other programming subjects.

Table of Contents

Preface	xv
Part I: Introduction	1	(12)
Programming languages	3	(10)
Programming linguistics	3	(3)
Concepts and paradigms	3	(2)
Syntax, semantics, and pragmatics	5	(1)
Language processors	6	(1)
Historical development	6	(7)
Summary	10	(1)
Further reading	10	(1)
Exercises	10	(3)
Part II: Basic Concepts	13	(120)
Values and types	15	(42)
Types	15	(1)
Primitive types	16	(4)
Built-in primitive types	16	(2)
Defined primitive types	18	(1)
Discrete primitive types	19	(1)
Composite types	20	(13)
Cartesian products, structures, and records	21	(2)
Mappings, arrays, and functions	23	(4)
Disjoint unions, discriminated records, and objects	27	(6)
Recursive types	33	(4)
Lists	33	(2)
Strings	35	(1)
Recursive types in general	36	(1)
Type systems	37	(6)
Static vs dynamic typing	38	(2)
Type equivalence	40	(2)
The Type Completeness Principle	42	(1)
Expressions	43	(6)
Literals	43	(1)
Constructions	44	(2)
Function calls	46	(1)
Conditional expressions	47	(1)
Iterative expressions	48	(1)
Constant and variable accesses	49	(1)
Implementation notes	49	(8)
Representation of primitive types	49	(1)
Representation of Cartesian products	50	(1)
Representation of arrays	50	(1)
Representation of disjoint unions	51	(1)
Representation of recursive types	51	(1)
Summary	52	(1)
Further reading	52	(1)
Exercises	52	(5)
Variables and storage	57	(38)
Variables and storage	57	(1)
Simple variables	58	(1)
Composite variables	59	(4)
Total vs selective update	60	(1)
Static vs dynamic vs flexible arrays	61	(2)
Copy semantics vs reference semantics	63	(3)
Lifetime	66	(7)
Global and local variables	66	(2)
Heap variables	68	(3)
Persistent variables	71	(2)
Pointers	73	(4)
Pointers and recursive types	74	(1)
Dangling pointers	75	(2)
Commands	77	(8)
Skips	77	(1)
Assignments	77	(1)
Proper procedure calls	78	(1)
Sequential commands	79	(1)
Collateral commands	79	(1)
Conditional commands	80	(2)
Iterative commands	82	(3)
Expressions with side effects	85	(2)
Command expressions	86	(1)
Expression-oriented languages	87	(1)
Implementation notes	87	(8)
Storage for global and local variables	88	(1)
Storage for heap variables	89	(1)
Representation of dynamic and flexible arrays	90	(1)
Summary	91	(1)
Further reading	91	(1)
Exercises	92	(3)
Bindings and scope	95	(20)
Bindings and environments	95	(2)
Scope	97	(5)
Block structure	97	(2)
Scope and visibility	99	(1)
Static vs dynamic scoping	100	(2)
Declarations	102	(6)
Type declarations	102	(2)
Constant declarations	104	(1)
Variable declarations	104	(1)
Procedure definitions	105	(1)
Collateral declarations	105	(1)
Sequential declarations	106	(1)
Recursive declarations	107	(1)
Scopes of declarations	108	(1)
Blocks	108	(7)
Block commands	109	(1)
Block expressions	110	(1)
The Qualification Principle	110	(1)
Summary	111	(1)
Further reading	112	(1)
Exercises	112	(3)
Procedural abstraction	115	(18)
Function procedures and proper procedures	115	(7)
Function procedures	116	(2)
Proper procedures	118	(2)
The Abstraction Principle	120	(2)
Parameters and arguments	122	(7)
Copy parameter mechanisms	124	(1)
Reference parameter mechanisms	125	(3)
The Correspondence Principle	128	(1)
Implementation notes	129	(4)
Implementation of procedure calls	130	(1)
Implementation of parameter mechanisms	130	(1)
Summary	131	(1)
Further reading	131	(1)
Exercises	131	(2)
Part III: Advanced Concepts	133	(130)
Data abstraction	135	(36)
Program units, packages, and encapsulation	135	(5)
Packages	136	(1)
Encapsulation	137	(3)
Abstract types	140	(5)
Objects and classes	145	(19)
Classes	146	(5)
Subclasses and inheritance	151	(6)
Abstract classes	157	(3)
Single vs multiple inheritance	160	(2)
Interfaces	162	(2)
Implementation notes	164	(7)
Representation of objects	164	(1)
Implementation of method calls	165	(1)
Summary	166	(1)
Further reading	167	(1)
Exercises	167	(4)
Generic abstraction	171	(20)
Generic units and instantiation	171	(5)
Generic packages in ADA	172	(2)
Generic classes in C++	174	(2)
Type and class parameters	176	(10)
Type parameters in ADA	176	(4)
Type parameters in C++	180	(3)
Class parameters in JAVA	183	(3)
Implementation notes	186	(5)
Implementation of ADA generic units	186	(1)
Implementation of C++ generic units	187	(1)
Implementation of JAVA generic units	188	(1)
Summary	188	(1)
Further reading	189	(1)
Exercises	189	(2)
Type systems	191	(24)
Inclusion polymorphism	191	(7)
Types and subtypes	191	(4)
Classes and subclasses	195	(3)
Parametric polymorphism	198	(6)
Polymorphic procedures	198	(2)
Parameterized types	200	(2)
Type inference	202	(2)
Overloading	204	(3)
Type conversions	207	(1)
Implementation notes	208	(7)
Implementation of parametric polymorphism	208	(2)
Summary	210	(1)
Further reading	210	(1)
Exercises	211	(4)
Control flow	215	(16)
Sequencers	215	(1)
Jumps	216	(2)
Escapes	218	(3)
Exceptions	221	(5)
Implementation notes	226	(5)
Implementation of jumps and escapes	226	(1)
Implementation of exceptions	227	(1)
Summary	227	(1)
Further reading	228	(1)
Exercises	228	(3)
Concurrency	231	(32)
Why concurrency?	231	(2)
Programs and processes	233	(1)
Problems with concurrency	234	(4)
Nondeterminism	234	(1)
Speed dependence	234	(2)
Deadlock	236	(1)
Starvation	237	(1)
Process interactions	238	(2)
Independent processes	238	(1)
Competing processes	238	(1)
Communicating processes	239	(1)
Concurrency primitives	240	(13)
Process creation and control	241	(2)
Interrupts	243	(1)
Spin locks and wait-free algorithms	243	(5)
Events	248	(1)
Semaphores	249	(2)
Messages	251	(1)
Remote procedure calls	252	(1)
Concurrent control abstractions	253	(10)
Conditional critical regions	253	(2)
Monitors	255	(1)
Rendezvous	256	(2)
Summary	258	(1)
Further reading	258	(1)
Exercises	259	(4)
Part IV: Paradigms	263	(166)
Imperative programming	265	(32)
Key concepts	265	(1)
Pragmatics	266	(3)
A simple spellchecker	268	(1)
Case study: C	269	(12)
Values and types	269	(3)
Variables, storage, and control	272	(2)
Bindings and scope	274	(1)
Procedural abstraction	274	(1)
Independent compilation	275	(1)
Preprocessor directives	276	(1)
Function library	277	(1)
A simple spellchecker	278	(3)
Case study: ADA	281	(16)
Values and types	281	(1)
Variables, storage, and control	282	(1)
Bindings and scope	282	(1)
Procedural abstraction	283	(1)
Data abstraction	283	(2)
Generic abstraction	285	(3)
Separate compilation	288	(1)
Package library	289	(1)
A simple spellchecker	289	(3)
Summary	292	(1)
Further reading	293	(1)
Exercises	293	(4)
Object-oriented programming	297	(36)
Key concepts	297	(1)
Pragmatics	298	(1)
Case study: C++	299	(12)
Values and types	300	(1)
Variables, storage, and control	300	(1)
Bindings and scope	300	(1)
Procedural abstraction	301	(1)
Data abstraction	302	(4)
Generic abstraction	306	(1)
Independent compilation and preprocessor directives	307	(1)
Class and template library	307	(1)
A simple spellchecker	308	(3)
Case study: Java	311	(11)
Values and types	312	(1)
Variables, storage, and control	313	(1)
Bindings and scope	314	(1)
Procedural abstraction	314	(1)
Data abstraction	315	(2)
Generic abstraction	317	(1)
Separate compilation and dynamic linking	318	(1)
Class library	319	(1)
A simple spellchecker	320	(2)
Case study: ADA95	322	(11)
Types	322	(3)
Data abstraction	325	(3)
Summary	328	(1)
Further reading	328	(1)
Exercises	329	(4)
Concurrent programming	333	(34)
Key concepts	333	(1)
Pragmatics	334	(2)
Case study: ADA95	336	(19)
Process creation and termination	336	(2)
Mutual exclusion	338	(1)
Admission control	339	(8)
Scheduling away deadlock	347	(8)
Case study: Java	355	(6)
Process creation and termination	356	(2)
Mutual exclusion	358	(1)
Admission control	359	(2)
Implementation notes	361	(6)
Summary	363	(1)
Further reading	363	(1)
Exercises	363	(4)
Functional programming	367	(26)
Key concepts	367	(3)
Eager vs normal-order vs lazy evaluation	368	(2)
Pragmatics	370	(1)
Case study: Haskell	370	(23)
Values and types	370	(4)
Bindings and scope	374	(2)
Procedural abstraction	376	(3)
Lazy evaluation	379	(2)
Data abstraction	381	(1)
Generic abstraction	382	(2)
Modeling state	384	(2)
A simple spellchecker	386	(1)
Summary	387	(1)
Further reading	388	(1)
Exercises	389	(4)
Logic programming	393	(20)
Key concepts	393	(3)
Pragmatics	396	(1)
Case study: Prolog	396	(17)
Values, variables, and terms	396	(2)
Assertions and clauses	398	(1)
Relations	398	(4)
The closed-world assumption	402	(1)
Bindings and scope	403	(1)
Control	404	(2)
Input/output	406	(1)
A simple spellchecker	407	(2)
Summary	409	(1)
Further reading	410	(1)
Exercises	410	(3)
Scripting	413	(16)
Pragmatics	413	(1)
Key concepts	414	(3)
Regular expressions	415	(2)
Case study: Python	417	(12)
Values and types	418	(1)
Variables, storage, and control	419	(2)
Bindings and scope	421	(1)
Procedural abstraction	421	(1)
Data abstraction	422	(2)
Separate compilation	424	(1)
Module library	425	(2)
Summary	427	(1)
Further reading	427	(1)
Exercises	427	(2)
Part V: Conclusion	429	(20)
Language selection	431	(6)
Criteria	431	(2)
Evaluation	433	(4)
Summary	436	(1)
Exercises	436	(1)
Language design	437	(12)
Selection of concepts	437	(1)
Regularity	438	(1)
Simplicity	438	(3)
Efficiency	441	(1)
Syntax	442	(2)
Language life cycles	444	(1)
The future	445	(4)
Summary	446	(1)
Further reading	446	(1)
Exercises	447	(2)
Bibliography	449	(4)
Glossary	453	(12)
Index	465