Bookmarks

Programming Language Design Concepts

Cover

Contents

Preface

Part I: Introduction

1 Programming languages

1.1 Programming linguistics

1.1.1 Concepts and paradigms

1.1.2 Syntax, semantics, and pragmatics

1.1.3 Language processors

1.2 Historical development

Summary

Further reading

Exercises

Part II: Basic Concepts

2 Values and types

2.1 Types

2.2 Primitive types

2.2.1 Built-in primitive types

2.2.2 Defined primitive types

2.2.3 Discrete primitive types

2.3 Composite types

2.3.1 Cartesian products, structures, and records

2.3.2 Mappings, arrays, and functions

2.3.3 Disjoint unions, discriminated records, and objects

2.4 Recursive types

2.4.1 Lists

2.4.2 Strings

2.4.3 Recursive types in general

2.5 Type systems

2.5.1 Static vs dynamic typing

2.5.2 Type equivalence

2.5.3 The Type Completeness Principle

2.6 Expressions

2.6.1 Literals

2.6.2 Constructions

2.6.3 Function calls

2.6.4 Conditional expressions

2.6.5 Iterative expressions

2.6.6 Constant and variable accesses

2.7 Implementation notes

2.7.1 Representation of primitive types

2.7.2 Representation of Cartesian products

2.7.3 Representation of arrays

2.7.4 Representation of disjoint unions

2.7.5 Representation of recursive types

Summary

Further reading

Exercises

3 Variables and storage

3.1 Variables and storage

3.2 Simple variables

3.3 Composite variables

3.3.1 Total vs selective update

3.3.2 Static vs dynamic vs flexible arrays

3.4 Copy semantics vs reference semantics

3.5 Lifetime

3.5.1 Global and local variables

3.5.2 Heap variables

3.5.3 Persistent variables

3.6 Pointers

3.6.1 Pointers and recursive types

3.6.2 Dangling pointers

3.7 Commands

3.7.1 Skips

3.7.2 Assignments

3.7.3 Proper procedure calls

3.7.4 Sequential commands

3.7.5 Collateral commands

3.7.6 Conditional commands

3.7.7 Iterative commands

3.8 Expressions with side effects

3.8.1 Command expressions

3.8.2 Expression-oriented languages

3.9 Implementation notes

3.9.1 Storage for global and local variables

3.9.2 Storage for heap variables

3.9.3 Representation of dynamic and flexible arrays

Summary

Further reading

Exercises

4 Bindings and scope

4.1 Bindings and environments

4.2 Scope

4.2.1 Block structure

4.2.2 Scope and visibility

4.2.3 Static vs dynamic scoping

4.3 Declarations

4.3.1 Type declarations

4.3.2 Constant declarations

4.3.3 Variable declarations

4.3.4 Procedure definitions

4.3.5 Collateral declarations

4.3.6 Sequential declarations

4.3.7 Recursive declarations

4.3.8 Scopes of declarations

4.4 Blocks

4.4.1 Block commands

4.4.2 Block expressions

4.4.3 The Qualification Principle

Summary

Further reading

Exercises

5 Procedural abstraction

5.1 Function procedures and proper procedures

5.1.1 Function procedures

5.1.2 Proper procedures

5.1.3 The Abstraction Principle

5.2 Parameters and arguments

5.2.1 Copy parameter mechanisms

5.2.2 Reference parameter mechanisms

5.2.3 The Correspondence Principle

5.3 Implementation notes

5.3.1 Implementation of procedure calls

5.3.2 Implementation of parameter mechanisms

Summary

Further reading

Exercises

Part III: Advanced Concepts

6 Data abstraction

6.1 Program units, packages, and encapsulation

6.1.1 Packages

6.1.2 Encapsulation

6.2 Abstract types

6.3 Objects and classes

6.3.1 Classes

6.3.2 Subclasses and inheritance

6.3.3 Abstract classes

6.3.4 Single vs multiple inheritance

6.3.5 Interfaces

6.4 Implementation notes

6.4.1 Representation of objects

6.4.2 Implementation of method calls

Summary

Further reading

Exercises

7 Generic abstraction

7.1 Generic units and instantiation

7.1.1 Generic packages in ADA

7.1.2 Generic classes in C++

7.2 Type and class parameters

7.2.1 Type parameters in ADA

7.2.2 Type parameters in C++

7.2.3 Class parameters in JAVA

7.3 Implementation notes

7.3.1 Implementation of ADA generic units

7.3.2 Implementation of C++ generic units

7.3.3 Implementation of JAVA generic units

Summary

Further reading

Exercises

8 Type systems

8.1 Inclusion polymorphism

8.1.1 Types and subtypes

8.1.2 Classes and subclasses

8.2 Parametric polymorphism

8.2.1 Polymorphic procedures

8.2.2 Parameterized types

8.2.3 Type inference

8.3 Overloading

8.4 Type conversions

8.5 Implementation notes

8.5.1 Implementation of parametric polymorphism

Summary

Further reading

Exercises

9 Control flow

9.1 Sequencers

9.2 Jumps

9.3 Escapes

9.4 Exceptions

9.5 Implementation notes

9.5.1 Implementation of jumps and escapes

9.5.2 Implementation of exceptions

Summary

Further reading

Exercises

10 Concurrency

10.1 Why concurrency?

10.2 Programs and processes

10.3 Problems with concurrency

10.3.1 Nondeterminism

10.3.2 Speed dependence

10.3.3 Deadlock

10.3.4 Starvation

10.4 Process interactions

10.4.1 Independent processes

10.4.2 Competing processes

10.4.3 Communicating processes

10.5 Concurrency primitives

10.5.1 Process creation and control

10.5.2 Interrupts

10.5.3 Spin locks and wait-free algorithms

10.5.4 Events

10.5.5 Semaphores

10.5.6 Messages

10.5.7 Remote procedure calls

10.6 Concurrent control abstractions

10.6.1 Conditional critical regions

10.6.2 Monitors

10.6.3 Rendezvous

Summary

Further reading

Exercises

Part IV: Paradigms

11 Imperative programming

11.1 Key concepts

11.2 Pragmatics

11.2.1 A simple spellchecker

11.3 Case study: C

11.3.1 Values and types

11.3.2 Variables, storage, and control

11.3.3 Bindings and scope

11.3.4 Procedural abstraction

11.3.5 Independent compilation

11.3.6 Preprocessor directives

11.3.7 Function library

11.3.8 A simple spellchecker

11.4 Case study: ADA

11.4.1 Values and types

11.4.2 Variables, storage, and control

11.4.3 Bindings and scope

11.4.4 Procedural abstraction

11.4.5 Data abstraction

11.4.6 Generic abstraction

11.4.7 Separate compilation

11.4.8 Package library

11.4.9 A simple spellchecker

Summary

Further reading

Exercises

12 Object-oriented programming

12.1 Key concepts

12.2 Pragmatics

12.3 Case study: C++

12.3.1 Values and types

12.3.2 Variables, storage, and control

12.3.3 Bindings and scope

12.3.4 Procedural abstraction

12.3.5 Data abstraction

12.3.6 Generic abstraction

12.3.7 Independent compilation and preprocessor directives

12.3.8 Class and template library

12.3.9 A simple spellchecker

12.4 Case study: JAVA

12.4.1 Values and types

12.4.2 Variables, storage, and control

12.4.3 Bindings and scope

12.4.4 Procedural abstraction

12.4.5 Data abstraction

12.4.6 Generic abstraction

12.4.7 Separate compilation and dynamic linking

12.4.8 Class library

12.4.9 A simple spellchecker

12.5 Case study: ADA95

12.5.1 Types

12.5.2 Data abstraction

Summary

Further reading

Exercises

13 Concurrent programming

13.1 Key concepts

13.2 Pragmatics

13.3 Case study: ADA95

13.3.1 Process creation and termination

13.3.2 Mutual exclusion

13.3.3 Admission control

13.3.4 Scheduling away deadlock

13.4 Case study: JAVA

13.4.1 Process creation and termination

13.4.2 Mutual exclusion

13.4.3 Admission control

13.5 Implementation notes

Summary

Further reading

Exercises

14 Functional programming

14.1 Key concepts

14.1.1 Eager vs normal-order vs lazy evaluation

14.2 Pragmatics

14.3 Case study: HASKELL

14.3.1 Values and types

14.3.2 Bindings and scope

14.3.3 Procedural abstraction

14.3.4 Lazy evaluation

14.3.5 Data abstraction

14.3.6 Generic abstraction

14.3.7 Modeling state

14.3.8 A simple spellchecker

Summary

Further reading

Exercises

15 Logic programming

15.1 Key concepts

15.2 Pragmatics

15.3 Case study: PROLOG

15.3.1 Values, variables, and terms

15.3.2 Assertions and clauses

15.3.3 Relations

15.3.4 The closed-world assumption

15.3.5 Bindings and scope

15.3.6 Control

15.3.7 Input/output

15.3.8 A simple spellchecker

Summary

Further reading

Exercises

16 Scripting

16.1 Pragmatics

16.2 Key concepts

16.2.1 Regular expressions

16.3 Case study: PYTHON

16.3.1 Values and types

16.3.2 Variables, storage, and control

16.3.3 Bindings and scope

16.3.4 Procedural abstraction

16.3.5 Data abstraction

16.3.6 Separate compilation

16.3.7 Module library

Summary

Further reading

Exercises

Part V: Conclusion

17 Language selection

17.1 Criteria

17.2 Evaluation

Summary

Exercises

18 Language design

18.1 Selection of concepts

18.2 Regularity

18.3 Simplicity

18.4 Efficiency

18.5 Syntax

18.6 Language life cycles

18.7 The future

Summary

Further reading

Exercises

Bibliography

Glossary

Index

Team DDU