Download Concepts in Programming Languages PDF

TitleConcepts in Programming Languages
TagsComputer Programming Subroutine Object Oriented Programming Computability Theory
File Size3.0 MB
Total Pages541
Table of Contents
                            Half-title
Title
Copyright
Contents
Preface
	Acknowledgments
PART 1 Functions and Foundations
	1 Introduction
		1.1 PROGRAMMING LANGUAGES
		1.2 GOALS
			1.2.1 General Goals
			1.2.2 Specific Themes
		1.3 PROGRAMMING LANGUAGE HISTORY
		1.4 ORGANIZATION: CONCEPTS AND LANGUAGES
	2 Computability
		2.1 PARTIAL FUNCTIONS AND COMPUTABILITY
			2.1.1 Expressions, Errors, and Nontermination
			2.1.2 Partial Functions
				Programs Define Partial Functions
			2.1.3 Computability
				Computable Functions
				Noncomputable Functions
				Applications
		2.2 CHAPTER SUMMARY
		EXERCISES
			2.1 Partial and Total Functions
			2.2 Halting Problem on No Input
			2.3 Halting Problem on All Input
	3 Lisp: Functions, Recursion, and Lists
		3.1 LISP HISTORY
		3.2 GOOD LANGUAGE DESIGN
			Motivating Application
			Program Execution Model
			Theoretical Foundations
		3.3 BRIEF LANGUAGE OVERVIEW
			Atoms
			S-Expressions and Lists
			Functions and Special Forms
			Evaluation of Expressions
			Static and Dynamic Scope
			Lisp and Scheme
		3.4 INNOVATIONS IN THE DESIGN OF LISP
			3.4.1 Statements and Expressions
			3.4.2 Conditional Expressions
			3.4.3 The Lisp Abstract Machine
				What is an Abstract Machine?
				The Abstract Machine for Lisp
				Cons Cells
				Representation of Lists by Cons Cells
			3.4.4 Programs as Data
			3.4.5 Function Expressions
			3.4.6 Recursion
			3.4.7 Higher-Order Functions
			3.4.8 Garbage Collection
				Mark-and-Sweep Garbage Collection
			3.4.9 Pure Lisp and Side Effects
		3.5 CHAPTER SUMMARY: CONTRIBUTIONS OF LISP
		EXERCISES
			3.1 Cons Cell Representations
			3.2 Conditional Expressions in Lisp
			3.3 Detecting Errors
			3.4 Lisp and Higher-Order Functions
			3.5 Definition of Garbage
			3.6 Reference Counting
			3.7 Regions and Memory Management
			3.8 Concurrency in Lisp
	4 Fundamentals
		4.1 COMPILERS AND SYNTAX
			4.1.1 Structure of Simple Compiler
				Lexical Analysis
				Syntax Analysis
				Semantic Analysis
				Intermediate Code Generation
				Code Optimization
				Code Generation
			4.1.2 Grammars and Parse Trees
				Grammars
				Derivations
				Parse Trees and Ambiguity
			4.1.3 Parsing and Precedence
		4.2 LAMBDA CALCULUS
			4.2.1 Functions and Function Expressions
			4.2.2 Lambda Expressions
				Syntax of Expressions
				Variable Binding
				Lambda Abstraction in Lisp and Algol
				Equivalence and Substitution
				Renaming Bound Variables
			4.2.3 Programming in Lambda Calculus
				Functions of Several Arguments
				Declarations
				Recursion and Fixed Points
			4.2.4 Reduction, Confluence, and Normal Forms
				Normal Forms
				Confluence
			4.2.5 Important Properties of Lambda Calculus
		4.3 DENOTATIONAL SEMANTICS
			Compositionality
			4.3.1 Object Language and Metalanguage
			4.3.2 Denotational Semantics of Binary Numbers
			4.3.3 Denotational Semantics of While Programs
				Expressions with Variables
				While Programs
				States and Commands
				Denotational Semantics
			4.3.4 Perspective and Nonstandard Semantics
		4.4 FUNCTIONAL AND IMPERATIVE LANGUAGES
			4.4.1 Imperative and Declarative Sentences
			4.4.2 Functional versus Imperative Programs
				Referential Transparency
				Historical Debate
				Functional Programming and Concurrency
				Practical Functional Programming
		4.5 CHAPTER SUMMARY
		EXERCISES
			4.1 Parse Tree
			4.2 Parsing and Precedence
			4.3 Lambda Calculus Reduction
			4.4 Symbolic Evaluation
			4.5 Lambda Reduction with Sugar
			4.6 Translation into Lambda Calculus
			4.7 Order of Evaluation
			4.8 Denotational Semantics
			4.9 Semantics of Initialize-Before-Use
			4.10 Semantics of Type Checking
			4.11 Lazy Evaluation and Parallelism
			4.12 Single-Assignment Languages
			4.13 Functional and Imperative Programs
			4.14 Functional Languages and Concurrency
PART 2 Procedures, Types, Memory Management, and Control
	5 The Algol Family and ML
		5.1 THE ALGOL FAMILY OF PROGRAMMING LANGUAGES
			5.1.1 Algol 60
			5.1.2 Algol 68
			5.1.3 Pascal
			5.1.4 Modula
		5.2 THE DEVELOPMENT OF C
			C Arrays and Pointers
			Critique
		5.3 THE LCF SYSTEM AND ML
		5.4 THE ML PROGRAMMING LANGUAGE
			5.4.1 Interactive Sessions and the Run-Time System
				Expressions
				Declarations
			5.4.2 Basic Types and Type Constructors
				Unit
				Bool
				Integers
				Strings
				Real
				Tuples
				Records
				Lists
			5.4.3 Patterns, Declarations, and Function Expressions
				Value Declarations
				Function Declarations
			5.4.4 ML Data-Type Declaration
			5.4.5 ML Reference Cells and Assignment
				L-values and R-values
				ML Reference Cells
				Operations on Reference Cells
			5.4.6 ML Summary
		5.5 CHAPTER SUMMARY
		EXERCISES
			5.1 Algol 60 Procedure Types
			5.2 Algol 60 Pass-By-Name
			5.3 Nonlinear Pattern Matching
			5.4 ML Map for Trees
			5.5 ML Reduce for Trees
			5.6 Currying
			5.7 Disjoint Unions
			5.8 Lazy Evaluation and Functions
	6 Type Systems and Type Inference
		6.1 TYPES IN PROGRAMMING
			6.1.1 Program Organization and Documentation
			6.1.2 Type Errors
			6.1.3 Types and Optimization
		6.2 TYPE SAFETY AND TYPE CHECKING
			6.2.1 Type Safety
			6.2.2 Compile-Time and Run-Time Checking
		6.3 TYPE INFERENCE
			6.3.1 First Examples of Type Inference
			6.3.2 Type-Inference Algorithm
		6.4 POLYMORPHISM AND OVERLOADING
			6.4.1 Parametric Polymorphism
				C++ Function Templates
				Comparison with ML Polymorphism
			6.4.2 Implementation of Parametric Polymorphism
				C++ Implementation
				ML Implementation
				Comparison
			6.4.3 Overloading
		6.5 TYPE DECLARATIONS AND TYPE EQUALITY
			6.5.1 Transparent Type Declarations
			6.5.2 C Declarations and Structs
			6.5.3 ML Data-Type Declaration
		6.6 CHAPTER SUMMARY
			Reasons for Using Types
			Type Inference
			Polymorphism and Overloading
			Type Declarations and Type Equality
		EXERCISES
			6.1 ML Types
			6.2 Polymorphic Sorting
			6.3 Types and Garbage Collection
			6.4 Polymorphic Fixed Point
			6.5 Parse Graph
			6.6 Parse Graph
			6.7 Type Inference and Bugs
			6.8 Type Inference and Debugging
			6.9 Polymorphism in C
			6.10 Typing and Run-Time Behavior
			6.11 Dynamic Typing in ML
	7 Scope, Functions, and Storage Management
		7.1 BLOCK-STRUCTURED LANGUAGES
			Simplified Machine Model
			A Note about C
		7.2 IN-LINE BLOCKS
			7.2.1 Activation Records and Local Variables
				Intermediate Results
				Scope and Lifetime
				Blocks and Activation Records for ML
			7.2.2 Global Variables and Control Links
		7.3 FUNCTIONS AND PROCEDURES
			7.3.1 Activation Records for Functions
			7.3.2 Parameter Passing
				Semantics of Pass-by-Value
				Semantics of Pass-by-Reference
			7.3.3 Global Variables (First-Order Case)
				Access Links are Used to Maintain Static Scope
			7.3.4 Tail Recursion (First-Order Case)
				Tail Recursion as Iteration
		7.4 HIGHER-ORDER FUNCTIONS
			7.4.1 First-Class Functions
			7.4.2 Passing Functions to Functions
				Use of Closures
			7.4.3 Returning Functions from Nested Scope
				Solution to Storage Management Problem
		7.5 CHAPTER SUMMARY
		EXERCISES
			7.1 Activation Records for In-Line Blocks
			7.2 Tail Recursion and Iteration
			7.3 Time and Space Requirements
			7.4 Parameter Passing
			7.5 Aliasing and Static Analysis
			7.6 Pass-by-Value-Result
			7.7 Parameter-Passing Comparison
			7.8 Static and Dynamic Scope
			7.9 Static Scope in ML
			7.10 Eval and Scope
			7.11 Lambda Calculus and Scope
			7.12 Function Calls and Memory Management
			7.13 Function Returns and Memory Management
			7.14 Recursive Calls and Memory Management
			7.15 Closures
			7.16 Closures and Tail Recursion
			7.17 Tail Recursion and Order of Operations
	8 Control in Sequential Languages
		8.1 STRUCTURED CONTROL
			8.1.1 Spaghetti Code
			8.1.2 Structured Control
		8.2 EXCEPTIONS
			8.2.1 Purpose of an Exception Mechanism
			8.2.2 ML Exceptions
			8.2.3 C++ Exceptions
			8.2.4 More about Exceptions
				Exceptions for Error Conditions
				Exceptions for Efficiency
				Static and Dynamic Scope
				Typing and Exceptions
				Exceptions and Resource Allocation
		8.3 CONTINUATIONS
			8.3.1 A Function Representing “The Rest of the Program”
			8.3.2 Continuation-Passing Form and Tail Recursion
			8.3.3 Continuations in Compilation
		8.4 FUNCTIONS AND EVALUATION ORDER
		8.5 CHAPTER SUMMARY
		EXERCISES
			8.1 Exceptions
			8.2 Exceptions
			8.3 Exceptions
			8.4 Exceptions and Recursion
			8.5 Tail Recursion and Exception Handling
			8.6 Evaluation Order and Exceptions
			8.7 Control Flow and Memory Management
			8.8 Tail Recursion and Continuations
			8.9 Continuations
PART 3 Modularity, Abstraction, and Object-Oriented Programming
	9 Data Abstraction and Modularity
		9.1 STRUCTURED PROGRAMMING
			9.1.1 Data Refinement
			9.1.2 Modularity
		9.2 LANGUAGE SUPPORT FOR ABSTRACTION
			9.2.1 Abstraction
				Procedural Abstraction
				Data Abstraction
			9.2.2 Abstract Data Types
			9.2.3 ML abstype
				Clu Clusters
			9.2.4 Representation Independence
			9.2.5 Data-Type Induction
				Partition Operations
				Induction over Constructors
		9.3 MODULES
			9.3.1 Modula and Ada
				Ada Packages
			9.3.2 ML Modules
		9.4 GENERIC ABSTRACTIONS
			9.4.1 C++ Function Templates
				Simple Polymorphic Function
				Operations on Type Parameters
				Comparison with ML Polymorphism
			9.4.2 Standard ML Functors
			9.4.3 C++ Standard Template Library
		9.5 CHAPTER SUMMARY
			Structured Programming
			Language Support for Abstraction
			Modules and Generic Programming
		EXERCISES
			9.1 Efficiency vs. Modularity
			9.2 Equivalence of Abstract Data Types
			9.3 Equivalence of Closures
			9.4 Modularity of Concrete Data Types
			9.5 Templates and Polymorphism
	10 Concepts in Object-Oriented Languages
		10.1 OBJECT-ORIENTED DESIGN
		10.2 FOUR BASIC CONCEPTS IN OBJECT-ORIENTED LANGUAGES
			10.2.1 Dynamic Lookup
			10.2.2 Abstraction
			10.2.3 Subtyping
			10.2.4 Inheritance
				Inheritance and Abstraction
			10.2.5 Closures as Objects
			10.2.6 Inheritance Is Not Subtyping
		10.3 PROGRAM STRUCTURE
			Comparison of Examples 10.1 and 10.2
		10.4 DESIGN PATTERNS
			Motivation
			Implementation
			Sample Code
			Motivation
			Implementation
			Example of Façade Pattern
		10.5 CHAPTER SUMMARY
		10.6 LOOKING FORWARD: SIMULA, SMALLTALK, C++, JAVA
		EXERCISES
			10.1 Expression Objects
			10.2 Objects vs. Type Case
			10.3 Visitor Design Pattern
	11 History of Objects: Simula and Smalltalk
		11.1 ORIGIN OF OBJECTS IN SIMULA
			11.1.1 Object and Simulation
			11.1.2 Main Concepts in Simula
		11.2 OBJECTS IN SIMULA
			11.2.1 Basic Object-Oriented Features in Simula
			11.2.2 An Example: Points, Lines, Circles
				Problem
				Algorithm
				Methodology
				Point
				Line
			11.2.3 Sample Code and Representation of Objects
		11.3 SUBCLASSES AND SUBTYPES IN SIMULA
			11.3.1 Subclasses and Inheritance
			11.3.2 Object Types and Subtypes
		11.4 DEVELOPMENT OF SMALLTALK
			Dynabook
		11.5 SMALLTALK LANGUAGE FEATURES
			11.5.1 Terminology
			11.5.2 Classes and Objects
				Run-Time Representation of Objects
			11.5.3 Inheritance
				Run-Time Structure to Support Inheritance
			11.5.4 Abstraction in Smalltalk
		11.6 SMALLTALK FLEXIBILITY
			11.6.1 Dynamic Lookup and Polymorphism
			11.6.2 Booleans and Blocks
			11.6.3 Self and Super
			11.6.4 System Extensibility: The Ingalls Test
				Why is This Important?
				What Are the Implementation Costs?
		11.7 RELATIONSHIP BETWEEN SUBTYPING AND INHERITANCE
			11.7.1 Interfaces as Object Types
			11.7.2 Subtyping
			11.7.3 Subtyping and Inheritance
		11.8 CHAPTER SUMMARY
			Simula
			Smalltalk
		EXERCISES
			11.1 Simula Inheritance and Access Links
			11.2 Loophole in Encapsulation
			11.3 Subtyping of Refs in Simula
			11.4 Smalltalk Run-Time Structures
			11.5 Smalltalk Implementation Decisions
			11.6 Protocol Conformance
			11.7 Removing a Method
			11.8 Subtyping and Binary Methods
			11.9 Delegation-Based Object-Oriented Languages
	12 Objects and Run-Time Efficiency: C++
		12.1 DESIGN GOALS AND CONSTRAINTS
			12.1.1 Compatibility with C
			12.1.2 Success of C++
		12.2 OVERVIEW OF C++
			12.2.1 Additions to C Not Related to Objects
				Type bool
				Reference Type and Pass-By Reference
				User-Defined Overloading
			12.2.2 Object-Oriented Features
			12.2.3 Good Decisions and Problem Areas
				Problem Areas
		12.3 CLASSES, INHERITANCE, AND VIRTUAL FUNCTIONS
			12.3.1 C++ Classes and Objects
			12.3.2 C++ Derived Classes (Inheritance)
			12.3.3 Virtual Functions
			12.3.4 Why is C++ Lookup Simpler than Smalltalk Lookup?
				Arguments to Member Functions and this
				Scope Qualifiers
				Nonvirtual and Overloaded Functions
		12.4 SUBTYPING
			12.4.1 Subtyping Principles
			12.4.2 Public Base Classes
			12.4.3 Specializing Types of Public Members
			12.4.4 Abstract Base Classes
		12.5 MULTIPLE INHERITANCE
			12.5.1 Implementation of Multiple Inheritance
			12.5.2 Name Clashes, Diamond Inheritance, and Virtual Base Classes
				Name Clashes
				Diamond Inheritance
				Virtual Base Classes
		12.6 CHAPTER SUMMARY
		EXERCISES
			12.1 Assignment and Derived Classes
			12.2 Function Objects
			12.3 Function Subtyping
			12.4 Subtyping and Public Data
			12.5 Phantom Members
			12.6 Subtyping and Visibility
			12.7 Private Virtual Functions
			12.8 “Like Current” in Eiffel
			12.9 Subtyping and Specifications
			12.10 C++ Multiple Inheritance and Casts
			12.11 Multiple Inheritance and Thunks
			12.12 Dispatch on State
	13 Portability and Safety: Java
		13.1 JAVA LANGUAGE OVERVIEW
			13.1.1 Java Language Goals
			13.1.2 Design Decisions
		13.2 JAVA CLASSES AND INHERITANCE
			13.2.1 Classes and Objects
			13.2.2 Packages and Visibility
			13.2.3 Inheritance
			13.2.4 Abstract Classes and Interfaces
		13.3 JAVA TYPES AND SUBTYPING
			13.3.1 Classification of Types
			13.3.2 Subtyping for Classes and Interfaces
			13.3.3 Arrays, Covariance, and Contravariance
			13.3.4 Java Exception Class Hierarchy
			13.3.5 Subtype Polymorphism and Generic Programming
		13.4 JAVA SYSTEM ARCHITECTURE
			13.4.1 Java Virtual Machine
			13.4.2 Class Loader
			13.4.3 Java Linker, Verifier, and Type Discipline
			13.4.4 Bytecode Interpreter and Method Lookup
				Finding a Virtual Method by Class
				Finding a Virtual Method by Interface
		13.5 SECURITY FEATURES
			13.5.1 Buffer Overflow Attack
			13.5.2 The Java Sandbox
				Class Loader
				The Bytecode Verifier and Virtual Machine Run-Time Tests
				The Security Manager
			13.5.3 Security and Type Safety
		13.6 JAVA SUMMARY
			Objects and Classes
			Dynamic Lookup
			Encapsulation
			Inheritance
			Subtyping
			Virtual Machine Architecture
			Security
		EXERCISES
			13.1 Initializing Static Fields
			13.2 Java final and finalize
			13.3 Subtyping and Exceptions
			13.4 Java Interfaces and Multiple Inheritance
			13.5 Array Covariance in Java
			13.6 Java Bytecode Analysis
			13.7 Exceptions, Memory Management, and Concurrency
			13.8 Adding Pointers to Java
			13.9 Stack Inspection
PART4 Concurrency and Logic Programming
	14 Concurrent and Distributed Programming
		14.1 BASIC CONCEPTS IN CONCURRENCY
			14.1.1 Execution Order and Nondeterminism
			14.1.2 Communication, Coordination, and Atomicity
			14.1.3 Mutual Exclusion and Locking
				Mutual Exclusion
				Locks and Busy Waiting
				Deadlock
			14.1.4 Semaphores
			14.1.5 Monitors
		14.2 THE ACTOR MODEL
		14.3 CONCURRENT ML
			14.3.1 Threads and Channels
				Functions Using Threads and Channels
			14.3.2 Selective Communication and Guarded Commands
			14.3.3 First-Class Synchronous Operations: Events
				Selective Communication with Events
		14.4 JAVA CONCURRENCY
			14.4.1 Threads, Communication, and Synchronization
				Communication between threads
				Synchronization Primitives
			14.4.2 Synchronized Methods
				Synchronized Methods and Inheritance
			14.4.3 Virtual Machine and Memory Model
				Concurrent Garbage Collection
				Java Memory Model
			14.4.4 Distributed Programming and Remote Method Invocation
				Creating Remote Objects
				Dynamic Class Loading
				The RMI Registry
		14.5 CHAPTER SUMMARY
			General Issues in Concurrency
			Actor Systems
			Concurrent ML
			Java Threads and Synchronization
			Distributed Java Programming and Remote Method Invocation
		EXERCISES
			14.1 Mutual Exclusion
			14.2 Fairness
			14.3 Actor Computing
			14.4 Message Passing
			14.5 CML Events
			14.6 Concurrent Access to Objects
			14.7 Java Synchronized Objects
			14.8 Resources and Java Garbage Collection
			14.9 Separate read and write Synchronization
			14.10 Java Memory Model
	15 The Logic Programming Paradigm and Prolog
		15.1 HISTORY OF LOGIC PROGRAMMING
		15.2 BRIEF OVERVIEW OF THE LOGIC PROGRAMMING PARADIGM
			15.2.1 Declarative Programming
			15.2.2 Interactive Programming
		15.3 EQUATIONS SOLVED BY UNIFICATION AS ATOMIC ACTIONS
			15.3.1 Terms
			15.3.2 Substitutions
			15.3.3 Most General Unifiers
			15.3.4 A Unification Algorithm
				MARTELLI–MONTANARI ALGORITHM
		15.4 CLAUSES AS PARTS OF PROCEDURE DECLARATIONS
			15.4.1 Simple Clauses
			15.4.2 Computation Process
			15.4.3 Clauses
		15.5 PROLOG’S APPROACH TO PROGRAMMING
			15.5.1 Multiple Uses of a Single Program
			15.5.2 Logical Variables
				A type assignment
				A Sequence Program
				Difference lists
		15.6 ARITHMETIC IN PROLOG
			15.6.1 Arithmetic Operators
			15.6.2 Arithmetic Comparison Relations
			15.6.3 Evaluation of Arithmetic Expressions
		15.7 CONTROL, AMBIVALENT SYNTAX, AND META-VARIABLES
			15.7.1 Cut
			15.7.2 Ambivalent Syntax and Meta-variables
			15.7.3 Control Facilities
				Disjunction
				If-then-else
				Negation
				Call
			15.7.4 Negation as Failure
			15.7.5 Higher-Order Programming and Meta-Programming in Prolog
				Term Inspection Facilities
				Program manipulation facilities
		15.8 ASSESSMENT OF PROLOG
			Lack of Types
			Subtle Arithmetic
			Idiosyncratic Control
			Complex Semantics of Various Built-ins
			No Modules and No Objects
		15.9 BIBLIOGRAPHIC REMARKS
		15.10 CHAPTER SUMMARY
		Acknowledgements
APPENDIX A Additional Program Examples
	A.1 PROCEDURAL AND OBJECT-ORIENTED ORGANIZATION
		A.1.1 Shape Program: Typecase Version
		A.1.2 Shape Program: Object-Oriented Version
Glossary
Index
                        
Document Text Contents
Page 1

http://www.cambridge.org/0521780985

Page 2

This page intentionally left blank

Page 270

258 Data Abstraction and Modularity

val y coord : point - real
val move p : point * real * real � point

end;
signature Circle =

sig
include Point
type circle
val mk circle : point * real � circle
val center : circle � point
val radius : circle � real
val move c : circle * real * real � circle

end;
signature Rect =

sig
include Point
type rect

(* make rectangle from lower right, upper left corners *)
val mk rect : point * point � rect
val lleft : rect � point
val uright : rect � point
val move r : rect * real * real � rect

end;

Here is the code for the Point, Circle, and Rect structures:

structure pt : Point =
struct

type point = real*real
fun mk point(x,y) = (x,y)
fun x coord(x,y) = x
fun y coord(x,y) = y
fun move p((x,y):point,dx,dy) = (x+dx, y+dy)

end;
structure cr : Circle =

struct
open pt
type circle = point*real
fun mk circle(x,y) = (x,y)
fun center(x,y) = x
fun radius(x,y) = y
fun move c(((x,y),r):circle,dx,dy) = ((x+dx, y+dy),r)

end;
structure rc : Rect =

struct
open pt

Page 271

9.4 Generic Abstractions 259

type rect = point * point
fun mk rect(x,y) = (x,y)
fun lleft(x,y) = x
fun uright (x,y) = y
fun move r(((x1,y1),(x2,y2)):rect,dx,dy) =

((x1+dx,y1+dy),(x2+dx,y2+dy))
end;

9.4 GENERIC ABSTRACTIONS

Abstract data types such as stacks or queues are useful for storingmany kinds of data.
In typed programming languages, however, the code for stacks of integers is different
from the code for stacks of strings. The two different versions of stacks are written
with different type declarations andmay be compiled to code that allocates different
amounts of space for local variables. However, it is time consuming to write different
versions of stacks for different types of elements and essentially pointless because
the code for the two cases is almost identical. Thus, over time, most typed languages
that emphasize abstraction and encapsulation have incorporated some form of type
parameterization.

9.4.1 C++ Function Templates

For many readers, the most familiar type-parameterization mechanism is the C++
template mechanism. Although some C++ programmers associate templates with
classes and object-oriented programming, function templates are also useful for pro-
grams that do not declare any classes. We look at function templates briefly before
considering module-parameterization mechanisms from other languages.

Simple Polymorphic Function
Suppose you write a simple function to swap the values of two integer variables:

void swap(int& x, int& y){
int tmp = x; x = y; y = tmp;

}

Although this code is useful for exchanging values of integer variables, it is notwritten
in the most general way possible. If you wish to swap values of variables of other
types, then you can define a function template that uses a type variable T in place of
the type name int:

template<typename T>
void swap(T& x, T& y){

T tmp = x; x = y; y = tmp;
}

Page 540

528 Index

polymorphism, 141, 145
ad hoc, 145
parametric, 145
subtype, 145

precedence in parsing, 56
prefix form, 492
prescient store, 463
priority, 492
priority queue, 240
private, 286
private base class in C++, 348
private member in C++, 347
private methods, 304
procedural abstraction, 242
procedural interpretation, 477
procedure, 170
process, 433
process communication, 435
program component, 239
program analysis, 74
Dylan, 279

propositional symbol, 483
protected, 286
protected member in C++, 347
protection domain, 415
prototyping, 239
public, 286
public base class in C++, 348
public member in C++, 347
public methods, 304
pure Lisp, 23
Python, 362

query, 483

raise exception, 207
range of a function, 12
reduction, 65
reentrant locking, 457
ref in Simula, 306
reference cell, 118
reference implementation, 164
reference type, 396
referential transparency, 78
relation symbol, 483
remote interface, 465
representation independence, 248, 249,

270
resolution of overloading, 151
R-value, 118
Roussel, Ph., 476
rule in Prolog, 485

sandbox, 412, 414, 419
scope, 25, 59
dynamic, 176
of declaration, 167
of binding, 59

resolution operator, 344
static, 176

second-order function, 35
security, 412
selector, 312
Self, 279
semantic analysis, 51
semantics, 48
semaphore, 440
Shapiro, E., 507
side effect, 23, 39
signal, 438
signature in SML, 255
simple clause, 483
simple logic program, 483
single dispatch, 281
source language, 50
special forms, 24
specification, 239, 269
stack frame, 165
start symbol (of grammar), 53
state, 67
statement, 26
static field, 390
static link, 178
static methods, 390
static scope, 25, 176
Sterling, L., 507
Steele, Guy, 205
STL
iterators, 267
range, 267

strictness, 27
strong typing, 121
Stroustrup, Bjarne, 338
structural type equality, 153
structure in SML, 255
stub for remote object, 465
subclass, 308, 312, 344, 392, 418
substitutivity, 284
subtype polymorphism, 145, 401
subtyping, 278, 284, 293, 309
super, 393
superclass, 308, 344, 392, 418
synchronized object, 441
synchronous communication, 435, 467
syntactic sugar, 61
syntax, 48

tail call, 180
tail recursion, 180
tail recursive, 180
target language, 50
task, 433
terminal, 53
test-and-set, 439
thread, 433, 445
throw exception, 207, 398

Page 541

Index 529

token, 50
transparent type, 244
true in Lisp, 24
try-finally in Java, 399
Turing complete, 14
Turing machine, 14
type, 129
casts, 133
checking, 135
confusion, 416
constructors, 121
declaration
opaque, 254
transparent, 254

error, 130, 309
inference, 135
safety, 387, 416
variables, 135

unbuffered communication, 467
unbuffered message passing, 435

undecidable, 134
unification problem, 481
uniform data representation,

149
upcall, 183, 218

variable
anonymous, 486

verification, 406
virtual, 281
base classes, 365
function in C++, 343, 347, 349,

366
function table (vtable), 349
machine (VM), 404

von Neumann bottleneck, 81
vtable, 349
vtbl, 349

wait, 438
Warren, D.H, 476

Similer Documents