Advanced Programming Language Design / Edition 1

by Raphael Finkel

Overview

Written for the student or professional interested in programming language design, this new book examines a wide range of programming language paradigms and issues. Author Raphael Finkel, University of Kentucky, intersperses the discussion of these models with in-depth coverage of the key languages to reinforce them. Finkel begins his presentation with control structures and types, and then introduces the reader to seven programming paradigms: imperative, functional, object-oriented, dataflow, concurrent, logic, and aggregate-based. He concludes the book with a discussion of formal syntax and semantics.

The author integrates this range of material by developing several themes, including the interplay between what can be done at compile time and what must be deferred to runtime; how patterns and pattern matching play a large role in programming languages; and the quest for uniformity seen in polymorphism. Written in a conversational style, this book challenges and encourages readers to launch into their own research in the field.

Features

• Starts with a review of imperative programming languages.
• Illustrates and reinforces key programming paradigms with in-depth discussions of several languages:

• functional: ML, Lisp
• object-oriented: Simula, Smalltalk, C++
• dataflow: Val
• concurrent: CSP, Linda, SR
• logic: Prolog, Goedel
• aggregate-based: SNOBOL, Icon, APL, SQL, Mathematica

• Refers to over 70 languages, including well-known ones (Algol, Pascal, C, C++, LISP, Ada, FORTRAN); important but lesser-known ones (ML, SR, Modula-3, SNOBOL); significant research languages(CLU, Alphard, Linda); and little-known languages with important concepts (Io, CLP(R), Goedel).
• Moves beyond traditional material by challenging readers with more unusual constructs such as power loops, Io continuations, CLU iterators, and APL array manipulation.
• Contains an appendix listing further reading and source locations for language implementations and documentation.
• Includes review and challenge exercises in each chapter.

Read Full Overview

Product Details

ISBN-13:	9780805311914
Publisher:	Pearson
Publication date:	12/21/1995
Edition description:	New Edition
Pages:	512
Product dimensions:	7.30(w) x 10.30(h) x 1.20(d)

Read an Excerpt

This book stems in part from courses taught at the University of Kentucky and at the University of Wisconsin-Madison on programming language design. There are many good books that deal with the subject at an undergraduate level, but there are few that are suitable for a one semester graduate-level course. This book is my attempt to fill that gap.

The goal of this course, and hence of this book, is to expose first-year graduate students to a wide range of programming language paradigms and issues, so that they can understand the literature on programming languages and even conduct research in this field. It should improve the students' appreciation of the art of designing programming languages and, to a limited degree, their skill in programming.

This book does not focus on any one language, or even on a few languages; it mentions, at least in passing, over seventy languages, including well-known ones (Algol, Pascal, C, C++, LISP, Ada, FORTRAN), important but less known ones (ML, SR, Modula-3, SNOBOL), significant research languages (CLU, Alphard, Linda), and little-known languages with important concepts (Io, Go .. del). Several languages are discussed in some depth, primarily to reinforce particular programming paradigms. ML and LISP demonstrate functional programming, Smalltalk and C++ demonstrate object-oriented programming, and Prolog demonstrates logic programming.

Students are expected to have taken an undergraduate course in programming languages before using this book. The first chapter includes a review of much of the material on imperative programming languages that would be covered in such a course. This review makes the book self-contained, andalso makes it accessible to advanced undergraduate students.

Most textbooks on programming languages cover the well-trodden areas of the field. In contrast, this book tries to go beyond the standard territory, making brief forays into regions that are under current research or that have been proposed and even rejected in the past. There are many fascinating constructs that appear in very few, if any, production programming languages. Some (like power loops) should most likely not be included in a programming language. Others (like Io continuations) are so strange that it is not clear how to program with them. Some (APL arrays) show alternative ways to structure languages. These unusual ideas are important even though they do not pass the test of current usage, because they elucidate important aspects of programming language design, and they allow students to evaluate novel concepts.

Certain themes flow through the entire book. One is the interplay between what can be done at compile time and what must be deferred to runtime. Actions performed at compile time make for more efficient and less error-prone execution. Decisions deferred until runtime lead to greater flexibility. Another theme is how patterns and pattern matching play a large role in many ways in programming languages. Pattern matching is immediately important for string manipulation, but it is also critical in steering logic programming, helpful for extracting data from structures in ML, and for associating caller and callee in CSP. A third theme is the quest for uniformity. It is very much like the mathematical urge to generalize. It can be seen in polymorphism, which generalizes the concept of type, and in overloading, which begins by unifying operators and functions and then unifies disparate functions under one roof. It can be seen in the homoiconic forms of LISP, in which program and data are both presented in the same uniform way.

Two organizing principles suggest themselves for a book on programming languages. The first is to deal separately with such issues as syntax, types, encapsulation, parallelism, object-oriented programming, pattern matching, dataflow, and so forth. Each section would introduce examples from all relevant languages. The other potential organizing principle is to present individual languages, more or less in full, and then to derive principles from them.

This book steers a middle course. I have divided it into chapters, each of which deals primarily with one of the subjects mentioned above. Most chapters include an extended example from a particular language to set the stage. This section may introduce language-specific features not directly relevant to the subject of the chapter. The chapter then introduces related features from other languages.

Because this book covers both central and unusual topics, the instructor of a course using the book should pick and choose whatever topics are of personal interest. In general, the latter parts of chapters delve into stranger and more novel variants of material presented earlier. The book is intended for a one semester course, but it is about 30 percent too long to cover fully in one semester. It is not necessary to cover every chapter, nor to cover every section of a chapter. Only Chapter 1 and the first seven sections of Chapter 3 are critical for understanding the other chapters. Some instructors will want to cover Chapter 4 before the discussion of ML in Chapter 3. Many instructors will decide to omit dataflow (Chapter 6). Others will wish to omit denotational semantics (in Chapter 10).

I have not described complete languages, and I may have failed to mention your favorite language. I have selected representative programming languages that display particular programming paradigms or language features clearly. These languages are not all generally available or even widely known. The appendix lists all the languages I have mentioned and gives you some pointers to the literature and to implementations and documentation available on the Internet through anonymous ftp (file-transfer protocol).

The exercises at the end of each chapter serve two purposes. First, they allow students to test their understanding of the subjects presented in the text by working exercises directly related to the material. More importantly, they push students beyond the confines of the material presented to consider new situations and to evaluate new proposals. Subjects that are only hinted at in the text are developed more thoroughly in this latter type of exercise.

In order to create an appearance of uniformity, I have chosen to modify the syntax of presented languages (in cases where the syntax is not the crucial issue), so that language-specific syntax does not obscure the other points that I am trying to make. For examples that do not depend on any particular language, I have invented what I hope will be clear notation. It is derived largely from Ada and some of its predecessors. This notation allows me to standardize the syntactic form of language, so that the syntax does not obscure the subject at hand. It is largely irrelevant whether a particular language uses begin and end or { and } . On the other hand, in those cases where I delve deeply into a language in current use (like ML, LISP, Prolog, Smalltalk, and C++), I have preserved the actual language. Where reserved words appear, I have placed them in bold monospace. Other program excerpts are in monospace font. I have also numbered examples so that instructors can refer to parts of them by line number. Each technical term that is introduced in the text is printed in boldface the first time it appears. All boldface entries are collected and defined in the glossary. I have tried to use a consistent nomenclature throughout the book.

In order to relieve the formality common in textbooks, I have chosen to write this book as a conversation between me, in the first singular person, and you, in the second person. When I say we, I mean you and me together. I hope you don't mind.

Several supplemental items are available to assist the instructor in using this text. Answers to the exercises are available from the publisher (ISBN: 0-201-49835-9) in a disk-based format. The figures from the text (in Adobe Acrobat format), an Adobe Acrobat reader, and the entire text of this book are available from the following site:

ftp://ftp.aw.com/cseng/authors/finkel/apld

Please check the readme file for updates and changes. The complete text of this book is intended for on-screen viewing free of charge; use of this material in any other format is subject to a fee.

There are other good books on programming language design. I can particularly recommend the text by Pratt Pratt 96 for elementary material and the text by Louden Louden 93 for advanced material. Other good books include those by Sebesta Sebesta 93 and Sethi Sethi 89. I owe a debt of gratitude to the many people who helped me write this book. Much of the underlying text is modified from course notes written by Charles N. Fischer of the University of Wisconsin-Madison. Students in my classes have submitted papers which I have used in preparing examples and text; these include the following:

C++

Feng Luo 1992

Mike Rogers 1992

Dataflow

Chinya Ravishankar 1981

Godel

James Gary 1992

Lynx

Michael Scott 1985

Mathematics languages

Mary Sue Powers 1994

Miranda

Manish Gupta 1992

Post

Chinya Ravishankar 1981

Rao Surapaneni 1992

CLP

William Ralenkotter 1994

Russell

Rick Simkin 1981

K. Lakshman 1992

Manish Gupta 1992

Smalltalk/C++

Jonathan Edwards 1992

Jonathan Edwards read an early draft of the text carefully and made many helpful suggestions. Michael Scott assisted me in improving Chapter 7 on concurrency. Arcot Rajasekar provided important feedback on Chapter 8 on logic programming. My editor, J. Carter Shanklin, and the reviewers he selected, made a world of difference in the presentation and coverage of the book. These reviewers were David Stotts (University of North Carolina at Chapel Hill), Spiro Michaylov (Ohio State University), Michael G. Murphy (Southern College of Technology), Barbara Ann Greim (University of North Carolina at Wilmington), Charles Elkan (University of California, San Diego), Henry Ruston (Polytechnic University), and L. David Umbaugh (University of Texas at Arlington). The University of Kentucky provided sabbatical funding to allow me to pursue this project, and Metropolitan College in Kuala Lumpur, Malaysia, provided computer facilities that allowed me to work on it. This book was prepared on the Linux version of the Unix operating system. Linux is the result of work by Linus Torvalds and countless others, primarily at the Free Software Foundation, who have provided an immense suite of programs I have used, including text editors, document formatters and previewers, spelling checkers, and revision control packages. I would have been lost without them. Finally, I would like to thank my wife, Beth L. Goldstein, for her support and patience, and my daughter, Penina, and son, Asher, for being wonderful.

Raphael A. Finkel
University of Kentucky

Table of Contents

Preface.


1. Programming Languages as Software Tools.

Evaluating Programming Languages.

Background Material on Programming Languages.

Variables, Data Types, Literals, and Expressions.

Control Constructs.

Procedures and Parameter Passing.

Block Structure.

Runtime Store Organization.

Final Comments.

Exercises.

2. Control Structures.

Exception Handling.

Coroutines.

Coroutines in Simula.

Coroutines in CLU.

Embedding CLU Iterators in C.

Coroutines in Icon.

Continuations: Io.

Power Loops.

Final Comments.

Exercises.

3. Types.

Dynamic-Typed Languages.

Strong Typing.

Type Equivalence.

Dimensions.

Abstract Data Types.

Labels, Procedures, and Types as First-Class Values.

ML.

Expressions.

Global Declarations.

Local Declarations.

Lists.

Functions and Patterns.

Polymorphic Types.

Type Inference.

Higher-Order Functions.

ML Types.

Constructed Types.

Miranda.

Russell.

Dynamic Typing in Statically Typed Languages.

Final Comments.

Exercises.

4. Functional Programming.

LISP.

Function Syntax.

Forms.

Programmer-Defined Functions.

Scope Rules.

Programming.

Closures and Deep Binding.

Identifier Lookup.

The Kernel of a LISP Interpreter.

Run-time List Evaluation.

Lazy Evaluation.

Speculative Evaluation.

Strengths and Weaknesses of LISP.

FP.

Definition of an FP Environment.

Reduction Semantics.

Persistence in Functional Languages.

Limitations of Functional Languages.

Lambda Calculus.

Exercises.

5. Object-Oriented Programming.

Definitions.

A Short Example.

Simula.

Smalltalk.

Assignment and Messages.

Blocks.

Classes and Methods.

Superclasses and Subclasses.

Implementation of Smalltalk.

Subtle Features.

C++.

The Consequences of Static Binding.

Sample Classes.

Final Comments.

Exercises.

6. Dataflow.

Dataflow Computers.

Val.

Sisal.

Post.

Data Types.

Programs.

Synchrony Control.

Guardians.

Speculative Computation.

Final Comments.

Exercises.

7. Concurrent Programming.

Starting Multiple Threads.

Cooperation by Means of Shared Variables.

Join.

Semaphores.

Mutexes.

Conditional Critical Regions.

Monitors.

Crowd Monitors.

Event Counts and Sequencers.

Barriers.

Performance Issues.

Transactions: Argus.

Cooperation by Procedure Call.

Rendezvous.

Remote Procedure Call (RPC).

Remote Evaluation (REV).

Cooperation by Messages.

CSP.

Lynx.

Linda.

SR.

Object-Oriented Programming.

Data-Parallel Programming.

Final Comments.

Exercises.

8. Logic Programming.

Prolog.

Terms, Predicates, and Queries.

Separating Logic and Control.

Axiomatic Data Types.

List Processing.

Difference Lists.

Arithmetic.

Termination Issues.

Resolution Proof Techniques.

Control Aspects.

1An Example of Control Programming.

1Negation.

1Other Evaluation Orders.

1Constraint-Logic Programming (CLP).

1Metaprogramming.

Go .. del.

Program Structure.

Types.

Logic Programming.

Conditionals.

Control.

Final Comments.

Exercises.

9. Aggregates.

Strings.

Literals and Simple Operations.

Representation.

Pattern Matching.

Associative Arrays.

Substrings as First-Class Values.

SNOBOL.

Icon.

Homoiconic Use of Strings: Tcl.

Arrays: APL.

Operators and Meta-operators.

An APL Evaluator.

Incremental Evaluation.

Database Languages.

Data Types.

Control Structures.

Modifying Data.

SQL.

Symbolic Mathematics.

Final Comments.

Exercises.

10. Formal Syntax and Semantics.

Syntax.

Axiomatic Semantics.

Axioms.

A Simple Proof.

Weakest Preconditions.

Denotational Semantics.

Domain Definitions.

Product Domains.

Disjoint-Union Domains.

Function Domains.

Domain Equations.

Nonrecursive Definitions.

Recursive Definitions.

Expressions.

Identifiers.

Environments.

Variables.

Conditional and Iterative Statements.

Procedures.

Functions.

Recursive Routines.

Modeddng Memory and Files.

Blocks and Scoping.

Parameters.

Continuations.

Statement Continuations.

Declaration Continuations.

Procedures, Functions, and Parameters.

Flow of Control.

Summary of Syntactic and Semantic Domains and Semantic Functions.

Final Comments.

Exercises.

Languages Mentioned.


Glossary.


References.


Index. 0805311912T04062001

Preface

This book stems in part from courses taught at the University of Kentucky and at the University of Wisconsin-Madison on programming language design. There are many good books that deal with the subject at an undergraduate level, but there are few that are suitable for a one semester graduate-level course. This book is my attempt to fill that gap.

The goal of this course, and hence of this book, is to expose first-year graduate students to a wide range of programming language paradigms and issues, so that they can understand the literature on programming languages and even conduct research in this field. It should improve the students' appreciation of the art of designing programming languages and, to a limited degree, their skill in programming.

This book does not focus on any one language, or even on a few languages; it mentions, at least in passing, over seventy languages, including well-known ones (Algol, Pascal, C, C++, LISP, Ada, FORTRAN), important but less known ones (ML, SR, Modula-3, SNOBOL), significant research languages (CLU, Alphard, Linda), and little-known languages with important concepts (Io, Go .. del). Several languages are discussed in some depth, primarily to reinforce particular programming paradigms. ML and LISP demonstrate functional programming, Smalltalk and C++ demonstrate object-oriented programming, and Prolog demonstrates logic programming.

Students are expected to have taken an undergraduate course in programming languages before using this book. The first chapter includes a review of much of the material on imperative programming languages that would be covered in such a course. This review makes the book self-contained, and also makes it accessible to advanced undergraduate students.

Most textbooks on programming languages cover the well-trodden areas of the field. In contrast, this book tries to go beyond the standard territory, making brief forays into regions that are under current research or that have been proposed and even rejected in the past. There are many fascinating constructs that appear in very few, if any, production programming languages. Some (like power loops) should most likely not be included in a programming language. Others (like Io continuations) are so strange that it is not clear how to program with them. Some (APL arrays) show alternative ways to structure languages. These unusual ideas are important even though they do not pass the test of current usage, because they elucidate important aspects of programming language design, and they allow students to evaluate novel concepts.

Certain themes flow through the entire book. One is the interplay between what can be done at compile time and what must be deferred to runtime. Actions performed at compile time make for more efficient and less error-prone execution. Decisions deferred until runtime lead to greater flexibility. Another theme is how patterns and pattern matching play a large role in many ways in programming languages. Pattern matching is immediately important for string manipulation, but it is also critical in steering logic programming, helpful for extracting data from structures in ML, and for associating caller and callee in CSP. A third theme is the quest for uniformity. It is very much like the mathematical urge to generalize. It can be seen in polymorphism, which generalizes the concept of type, and in overloading, which begins by unifying operators and functions and then unifies disparate functions under one roof. It can be seen in the homoiconic forms of LISP, in which program and data are both presented in the same uniform way.

Two organizing principles suggest themselves for a book on programming languages. The first is to deal separately with such issues as syntax, types, encapsulation, parallelism, object-oriented programming, pattern matching, dataflow, and so forth. Each section would introduce examples from all relevant languages. The other potential organizing principle is to present individual languages, more or less in full, and then to derive principles from them.

This book steers a middle course. I have divided it into chapters, each of which deals primarily with one of the subjects mentioned above. Most chapters include an extended example from a particular language to set the stage. This section may introduce language-specific features not directly relevant to the subject of the chapter. The chapter then introduces related features from other languages.

Because this book covers both central and unusual topics, the instructor of a course using the book should pick and choose whatever topics are of personal interest. In general, the latter parts of chapters delve into stranger and more novel variants of material presented earlier. The book is intended for a one semester course, but it is about 30 percent too long to cover fully in one semester. It is not necessary to cover every chapter, nor to cover every section of a chapter. Only Chapter 1 and the first seven sections of Chapter 3 are critical for understanding the other chapters. Some instructors will want to cover Chapter 4 before the discussion of ML in Chapter 3. Many instructors will decide to omit dataflow (Chapter 6). Others will wish to omit denotational semantics (in Chapter 10).

I have not described complete languages, and I may have failed to mention your favorite language. I have selected representative programming languages that display particular programming paradigms or language features clearly. These languages are not all generally available or even widely known. The appendix lists all the languages I have mentioned and gives you some pointers to the literature and to implementations and documentation available on the Internet through anonymous ftp (file-transfer protocol).

The exercises at the end of each chapter serve two purposes. First, they allow students to test their understanding of the subjects presented in the text by working exercises directly related to the material. More importantly, they push students beyond the confines of the material presented to consider new situations and to evaluate new proposals. Subjects that are only hinted at in the text are developed more thoroughly in this latter type of exercise.

In order to create an appearance of uniformity, I have chosen to modify the syntax of presented languages (in cases where the syntax is not the crucial issue), so that language-specific syntax does not obscure the other points that I am trying to make. For examples that do not depend on any particular language, I have invented what I hope will be clear notation. It is derived largely from Ada and some of its predecessors. This notation allows me to standardize the syntactic form of language, so that the syntax does not obscure the subject at hand. It is largely irrelevant whether a particular language uses begin and end or { and } . On the other hand, in those cases where I delve deeply into a language in current use (like ML, LISP, Prolog, Smalltalk, and C++), I have preserved the actual language. Where reserved words appear, I have placed them in bold monospace. Other program excerpts are in monospace font. I have also numbered examples so that instructors can refer to parts of them by line number. Each technical term that is introduced in the text is printed in boldface the first time it appears. All boldface entries are collected and defined in the glossary. I have tried to use a consistent nomenclature throughout the book.

In order to relieve the formality common in textbooks, I have chosen to write this book as a conversation between me, in the first singular person, and you, in the second person. When I say we, I mean you and me together. I hope you don't mind.

Several supplemental items are available to assist the instructor in using this text. Answers to the exercises are available from the publisher (ISBN: 0-201-49835-9) in a disk-based format. The figures from the text (in Adobe Acrobat format), an Adobe Acrobat reader, and the entire text of this book are available from the following site:

ftp://ftp.aw.com/cseng/authors/finkel/apld

Please check the readme file for updates and changes. The complete text of this book is intended for on-screen viewing free of charge; use of this material in any other format is subject to a fee.

There are other good books on programming language design. I can particularly recommend the text by Pratt Pratt 96 for elementary material and the text by Louden Louden 93 for advanced material. Other good books include those by Sebesta Sebesta 93 and Sethi Sethi 89. I owe a debt of gratitude to the many people who helped me write this book. Much of the underlying text is modified from course notes written by Charles N. Fischer of the University of Wisconsin-Madison. Students in my classes have submitted papers which I have used in preparing examples and text; these include the following:

C++

Feng Luo 1992

Mike Rogers 1992

Dataflow

Chinya Ravishankar 1981

Godel

James Gary 1992

Lynx

Michael Scott 1985

Mathematics languages

Mary Sue Powers 1994

Miranda

Manish Gupta 1992

Post

Chinya Ravishankar 1981

Rao Surapaneni 1992

CLP

William Ralenkotter 1994

Russell

Rick Simkin 1981

K. Lakshman 1992

Manish Gupta 1992

Smalltalk/C++

Jonathan Edwards 1992

Jonathan Edwards read an early draft of the text carefully and made many helpful suggestions. Michael Scott assisted me in improving Chapter 7 on concurrency. Arcot Rajasekar provided important feedback on Chapter 8 on logic programming. My editor, J. Carter Shanklin, and the reviewers he selected, made a world of difference in the presentation and coverage of the book. These reviewers were David Stotts (University of North Carolina at Chapel Hill), Spiro Michaylov (Ohio State University), Michael G. Murphy (Southern College of Technology), Barbara Ann Greim (University of North Carolina at Wilmington), Charles Elkan (University of California, San Diego), Henry Ruston (Polytechnic University), and L. David Umbaugh (University of Texas at Arlington). The University of Kentucky provided sabbatical funding to allow me to pursue this project, and Metropolitan College in Kuala Lumpur, Malaysia, provided computer facilities that allowed me to work on it. This book was prepared on the Linux version of the Unix operating system. Linux is the result of work by Linus Torvalds and countless others, primarily at the Free Software Foundation, who have provided an immense suite of programs I have used, including text editors, document formatters and previewers, spelling checkers, and revision control packages. I would have been lost without them. Finally, I would like to thank my wife, Beth L. Goldstein, for her support and patience, and my daughter, Penina, and son, Asher, for being wonderful.

Raphael A. Finkel
University of Kentucky

0805311912P04062001