Theories of Programming Languages: John C. Reynolds: 9780521594141: Book: Computers: eCampus.com

This textbook is a broad but rigorous survey of the theoretical basis for the design, definition, and implementation of programming languages, and of systems for specifying and proving program behavior. It encompasses imperative and functional programming, as well as the ways of integrating these aspects into more general languages. Basic concepts and their properties are described with mathematical rigor, but the mathematical development is balanced by numerous examples of applications, particularly of program specification and proof, concurrent programming, functional programming (including the use of continuations and lazy evaluation), and type systems (including subtyping, polymorphism, and modularization). Assuming only knowledge of elementary programming, this text is perfect for advanced undergraduate and beginning graduate courses in programming language theory, and will also appeal to researchers and professionals in designing or implementing computer languages.

A broad but rigorous survey of the theoretical basis for the design, definition, & implementation of programming languages, & of systems for specifying & proving program behavior. DLC: Programming languages (Electronic computers).

This text is perfect for advanced undergraduate and beginning graduate courses in programming language theory.

Preface

1 Predicate Logic

(23)

1.1 Abstract Syntax

(7)

1.2 Denotational Semantics of Predicate Logic

(4)

1.3 Validity and Inference

(3)

1.4 Binding and Substitution

(9)

2 The Simple Imperative Language

(30)

2.1 Syntax

(2)

2.2 Denotational Semantics

(3)

2.3 Domains and Continuous Functions

(6)

2.4 The Least Fixed-Point Theorem

(4)

2.5 Variable Declarations and Substitution

(6)

2.6 Syntactic Sugar: The for Command

(2)

2.7 Arithmetic Errors

(1)

2.8 Soundness and Full Abstraction

(6)

3 Program Specifications and Their Proofs

(27)

3.1 Syntax and Semantics of Specifications

(2)

3.2 Inference Rules

(1)

3.3 Rules for Assignment and Sequential Composition

(6)

3.4 Rules for while Commands

(3)

3.5 Further Rules

(3)

3.6 Computing Fibonacci Numbers

(2)

3.7 Fast Exponentiation

(3)

3.8 Complications and Limitations

(7)

4 Arrays

(16)

4.1 Abstract Syntax

(2)

4.2 Denotational Semantics

(2)

4.3 Binary Search

(5)

4.4 Inference Rules for Arrays

(3)

4.5 Higher-Order Assertions About Arrays

(4)

5 Failure, Input-Output, and Continuations

(29)

5.1 The fail Command

(4)

5.2 Intermediate Output and a Domain of Sequences

101

(6)

5.3 The Physical Argument for Continuity

107

(2)

5.4 Products and Disjoint Unions of Predomains

109

(2)

5.5 Recursive Domain Isomorphisms

111

(2)

5.6 Intermediate Input and a Domain of Resumptions

113

(2)

5.7 Continuation Semantics

115

(3)

5.8 Continuation Semantics of Extensions

118

(8)

6 Transition Semantics

126

(10)

6.1 Configurations and the Transition Relation

126

(1)

6.2 Inference Rules for the Simple Language

127

(4)

6.3 Transition Semantics of fail

131

(1)

6.4 Input and Output

132

(4)

7 Nondeterminism and Guarded Commands

136

(19)

7.1 Syntax and Transition Semantics

137

(2)

7.2 Bounded Nondeterminism and Powerdomains

139

(5)

7.3 Semantic Equations

144

(3)

7.4 Program Specification and Proof

147

(2)

7.5 Weakest Preconditions

149

(6)

8 Shared-Variable Concurrency

155

(26)

8.1 Concurrent Composition

155

(2)

8.2 Critical Regions

157

(2)

8.3 Mutual Exclusion and Conditional Critical Regions

159

(2)

8.4 Deadlock

161

(1)

8.5 Fairness

162

(2)

8.6 Resumption Semantics

164

(1)

8.7 Transition Traces

165

(6)

8.8 Stuttering and Mumbling

171

(10)

9 Communicating Sequential Processes

181

(13)

9.1 Syntax

181

(2)

9.2 Transition Semantics

183

(4)

9.3 Possible Restrictions

187

(1)

9.4 Examples

188

(1)

9.5 Deadlock

189

(1)

9.6 Fairness

189

(5)

10 The Lambda Calculus

194

(28)

10.1 Syntax

196

(1)

10.2 Reduction

197

(4)

10.3 Normal-Order Evaluation

201

(5)

10.4 Eager Evaluation

206

(2)

10.5 Denotational Semantics

208

(8)

10.6 Programming in the Lambda Calculus

216

(6)

11 An Eager Functional Language

222

(29)

11.1 Concrete Syntax

222

(1)

11.2 Evaluation Semantics

223

(5)

11.3 Definitions, Patterns, and Recursion

228

(3)

11.4 Lists

231

(1)

11.5 Examples

232

(3)

11.6 Direct Denotational Semantics

235

(7)

11.7 Dynamic Binding

242

(9)

12 Continuations in a Functional Language

251

(22)

12.1 Continuation Semantics

251

(4)

12.2 Continuation as Values

255

(2)

12.3 Continuations as a Programming Technique

257

(1)

12.4 Deriving a First-Order Semantics

258

(6)

12.5 First-Order Semantics Summarized

264

(5)

12.6 Relating First-Order and Continuation Semantics

269

(4)

13 Iswim-like Languages

273

(25)

13.1 Aliasing, References, and States

273

(3)

13.2 Evaluation Semantics

276

(2)

13.3 Continuation Semantics

278

(4)

13.4 Some Syntactic Sugar

282

(1)

13.5 First-Order Semantics

282

(2)

13.6 Examples

284

(3)

13.7 Exceptions

287

(2)

13.8 Backtracking

289

(2)

13.9 Input and Output

291

(2)

13.10 Some Complications

293

(5)

14 A Normal-Order Language

298

(17)

14.1 Evaluation Semantics

298

(3)

14.2 Syntactic Sugar

301

(1)

14.3 Examples

302

(2)

14.4 Direct Denotational Semantics

304

(2)

14.5 Reduction Revisited

306

(1)

14.6 Lazy Evaluation

307

(8)

15 The Simple Type System

315

(34)

15.1 Types, Contexts, and Judgements

316

(2)

15.2 Inference Rules

318

(6)

15.3 Explicit Typing

324

(3)

15.4 The Extrinsic Meaning of Types

327

(7)

15.5 The Intrinsic View

334

(5)

15.6 Set-Theoretic Semantics

339

(2)

15.7 Recursive Types

341

(6)

16 Subtypes and Intersection Types

349

(30)

16.1 Inference Rules for Subtyping

349

(3)

16.2 Named Products and Sums

352

(2)

16.3 Intersection Types

354

(4)

16.4 Extrinsic Semantics

358

(4)

16.5 Generic Operators

362

(3)

16.6 Intrinsic Semantics

365

(14)

17 Polymorphism

379

(19)

17.1 Syntax and Inference Rules

380

(3)

17.2 Polymorphic Programming

383

(7)

17.3 Extrinsic Semantics

390

(8)

18 Module Specification

398

(17)

18.1 Type Definitions

398

(3)

18.2 Existential Quantification and Modules

401

(5)

18.3 Implementing One Abstraction in Terms of Another

406

(9)

19 Algo-like Languages

415

(32)

19.1 Data Types and Phrase Types

416

(3)

19.2 Phrases and Type Inference Rules

419

(4)

19.3 Examples

423

(3)

19.4 Arrays and Declarators

426

(2)

19.5 A Semantics Embodying the Stack Discipline

428

(6)

19.6 The Semantics of Variables

434

(2)

19.7 The Semantics of Procedures

436

(3)

19.8 Some Extensions and Simplifications

439

(8)

Appendix: Mathematical Background

447

(20)

A.1 Sets

448

(2)

A.2 Relations

450

(2)

A.3 Functions

452

(4)

A.4 Relations and Functions Between Sets

456

(3)

A.5 More About Products and Disjoint Unions

459

(3)

A.6 More About Relations

462

(5)

Bibliography

467

(16)

Index

483


	Buy Textbooks Sell Textbooks College Apparel Shop by School Virtual Bookstores	Order Status Shipping Rates Return Policy Marketplace Info F.A.S.T.	Contact Us Privacy Policy Legal Notices Site Security Employment	Help Desk eCampus Blog Affiliate Program Bulk Orders College Marketing

Need Help? eService@ecampus.com Copyright© 1999-2008
.