Solution Manual for Concepts of Programming Languages, 12th Edition
Struggling with assignments? Solution Manual for Concepts of Programming Languages, 12th Edition has all the answers you need!
Ava Martinez
Contributor
4.0
60
about 2 months ago
Preview (19 of 60)
Sign in to access the full document!
Instructor’s Solutions Manual
to
Concepts of Programming Languages
Twelfth Edition
R.W. Sebesta
to
Concepts of Programming Languages
Twelfth Edition
R.W. Sebesta
2
Preface
Changes for the Twelfth Edition
he goals, overall structure, and approach of this twelfth edition of
Concepts of Programming Languages remain the same as those of the
eleven earlier editions. The principal goals are to introduce the
fundamental constructs of contemporary programming languages and to
provide the reader with the tools necessary for the critical evaluation of
existing and future programming languages. A secondary goal is to prepare the
reader for the study of compiler design, by providing an in-depth discussion of
programming language structures, presenting a formal method of describing
syntax, and introducing approaches to lexical and syntactic analysis.
The twelfth edition evolved from the eleventh through several different kinds
of changes. To maintain the currency of the material, nearly all of the discussion
of some programming languages, specifically Lua and Objective-C, has been
removed. Material on the newer language, Swift, was added to several chapters.
In addition, a new section on optional types was added to Chapter 6. Material
was added to Section 8.3.4 to describe iterators in Python. In numerous places in
the manuscript small changes were made to correct and/or clarify the discussion.
The Vision
This book describes the fundamental concepts of programming languages by
discussing the design issues of the various language constructs, examining the
design choices for these constructs in some of the most common languages, and
critically comparing design alternatives.
Any serious study of programming languages requires an examination of
some related topics, among which are formal methods of describing the syntax
and semantics of programming languages, which are covered in Chapter 3. Also,
implementation techniques for various language constructs must be considered:
Lexical and syntax analysis are discussed in Chapter 4, and implementation of
T
Preface
Changes for the Twelfth Edition
he goals, overall structure, and approach of this twelfth edition of
Concepts of Programming Languages remain the same as those of the
eleven earlier editions. The principal goals are to introduce the
fundamental constructs of contemporary programming languages and to
provide the reader with the tools necessary for the critical evaluation of
existing and future programming languages. A secondary goal is to prepare the
reader for the study of compiler design, by providing an in-depth discussion of
programming language structures, presenting a formal method of describing
syntax, and introducing approaches to lexical and syntactic analysis.
The twelfth edition evolved from the eleventh through several different kinds
of changes. To maintain the currency of the material, nearly all of the discussion
of some programming languages, specifically Lua and Objective-C, has been
removed. Material on the newer language, Swift, was added to several chapters.
In addition, a new section on optional types was added to Chapter 6. Material
was added to Section 8.3.4 to describe iterators in Python. In numerous places in
the manuscript small changes were made to correct and/or clarify the discussion.
The Vision
This book describes the fundamental concepts of programming languages by
discussing the design issues of the various language constructs, examining the
design choices for these constructs in some of the most common languages, and
critically comparing design alternatives.
Any serious study of programming languages requires an examination of
some related topics, among which are formal methods of describing the syntax
and semantics of programming languages, which are covered in Chapter 3. Also,
implementation techniques for various language constructs must be considered:
Lexical and syntax analysis are discussed in Chapter 4, and implementation of
T
3
subprogram linkage is covered in Chapter 10. Implementation of some other
language constructs is discussed in various other parts of the book.
The following paragraphs outline the contents of the twelfth edition.
Chapter Outlines
Chapter 1 begins with a rationale for studying programming languages. It then
discusses the criteria used for evaluating programming languages and language
constructs. The primary influences on language design, common design trade-
offs, and the basic approaches to implementation are also examined.
Chapter 2 outlines the evolution of the languages that are discussed in this
book. Although no attempt is made to describe any language completely, the
origins, purposes, and contributions of each are discussed. This historical
overview is valuable, because it provides the background necessary to
understanding the practical and theoretical basis for contemporary language
design. It also motivates further study of language design and evaluation. Because
none of the remainder of the book depends on Chapter 2, it can be read on its
own, independent of the other chapters.
Chapter 3 describes the primary formal method for describing the syntax of
programming language—BNF. This is followed by a description of attribute
grammars, which describe both the syntax and static semantics of languages. The
difficult task of semantic description is then explored, including brief
introductions to the three most common methods: operational, denotational, and
axiomatic semantics.
Chapter 4 introduces lexical and syntax analysis. This chapter is targeted to
those Computer Science departments that no longer require a compiler design
course in their curricula. Similar to Chapter 2, this chapter stands alone and can be
studied independently of the rest of the book, except for Chapter 3, on which it
depends.
Chapters 5 through 14 describe in detail the design issues for the primary
constructs of programming languages. In each case, the design choices for several
example languages are presented and evaluated. Specifically, Chapter 5 covers the
many characteristics of variables, Chapter 6 covers data types, and Chapter 7
explains expressions and assignment statements. Chapter 8 describes control
statements, and Chapters 9 and 10 discuss subprograms and their implementation.
Chapter 11 examines data abstraction facilities. Chapter 12 provides an in-depth
subprogram linkage is covered in Chapter 10. Implementation of some other
language constructs is discussed in various other parts of the book.
The following paragraphs outline the contents of the twelfth edition.
Chapter Outlines
Chapter 1 begins with a rationale for studying programming languages. It then
discusses the criteria used for evaluating programming languages and language
constructs. The primary influences on language design, common design trade-
offs, and the basic approaches to implementation are also examined.
Chapter 2 outlines the evolution of the languages that are discussed in this
book. Although no attempt is made to describe any language completely, the
origins, purposes, and contributions of each are discussed. This historical
overview is valuable, because it provides the background necessary to
understanding the practical and theoretical basis for contemporary language
design. It also motivates further study of language design and evaluation. Because
none of the remainder of the book depends on Chapter 2, it can be read on its
own, independent of the other chapters.
Chapter 3 describes the primary formal method for describing the syntax of
programming language—BNF. This is followed by a description of attribute
grammars, which describe both the syntax and static semantics of languages. The
difficult task of semantic description is then explored, including brief
introductions to the three most common methods: operational, denotational, and
axiomatic semantics.
Chapter 4 introduces lexical and syntax analysis. This chapter is targeted to
those Computer Science departments that no longer require a compiler design
course in their curricula. Similar to Chapter 2, this chapter stands alone and can be
studied independently of the rest of the book, except for Chapter 3, on which it
depends.
Chapters 5 through 14 describe in detail the design issues for the primary
constructs of programming languages. In each case, the design choices for several
example languages are presented and evaluated. Specifically, Chapter 5 covers the
many characteristics of variables, Chapter 6 covers data types, and Chapter 7
explains expressions and assignment statements. Chapter 8 describes control
statements, and Chapters 9 and 10 discuss subprograms and their implementation.
Chapter 11 examines data abstraction facilities. Chapter 12 provides an in-depth
Loading page 4...
4
discussion of language features that support object-oriented programming
(inheritance and dynamic method binding), Chapter 13 discusses concurrent
program units, and Chapter 14 is about exception handling, along with a brief
discussion of event handling.
Chapters 15 and 16 describe two of the most important alternative
programming paradigms: functional programming and logic programming.
However, some of the data structures and control constructs of functional
programming languages are discussed in Chapters 6 and 8. Chapter 15 presents an
introduction to Scheme, including descriptions of some of its primitive functions,
special forms, and functional forms, as well as some examples of simple functions
written in Scheme. Brief introductions to ML, Haskell, and F# are given to
illustrate some different directions in functional language design. Chapter 16
introduces logic programming and the logic programming language, Prolog.
To the Instructor
Chapters 1 and 3 are typically covered in detail, and though students find it
interesting and beneficial reading, Chapter 2 receives little lecture time due to the
lack of hard technical content. Because no material in subsequent chapters
depends on Chapter 2, it can be skipped entirely. If a course in compiler design is
required, Chapter 4 is not covered.
Chapters 5 through 9 should be relatively easy for students with extensive
programming experience in C++, Java, or C#. Chapters 10 through 14 are more
challenging and require more detailed lectures.
Chapters 15 and 16 are entirely new to most students at the junior level.
Ideally, language processors for Scheme and Prolog should be available for
students required to learn the material in these chapters. Sufficient material is
included to allow students to dabble with some simple programs.
Undergraduate courses will probably not be able to cover all of the material
in the last two chapters. Graduate courses, however, should be able to completely
discuss the material in those chapters by skipping over some parts of the early
chapters on imperative languages.
discussion of language features that support object-oriented programming
(inheritance and dynamic method binding), Chapter 13 discusses concurrent
program units, and Chapter 14 is about exception handling, along with a brief
discussion of event handling.
Chapters 15 and 16 describe two of the most important alternative
programming paradigms: functional programming and logic programming.
However, some of the data structures and control constructs of functional
programming languages are discussed in Chapters 6 and 8. Chapter 15 presents an
introduction to Scheme, including descriptions of some of its primitive functions,
special forms, and functional forms, as well as some examples of simple functions
written in Scheme. Brief introductions to ML, Haskell, and F# are given to
illustrate some different directions in functional language design. Chapter 16
introduces logic programming and the logic programming language, Prolog.
To the Instructor
Chapters 1 and 3 are typically covered in detail, and though students find it
interesting and beneficial reading, Chapter 2 receives little lecture time due to the
lack of hard technical content. Because no material in subsequent chapters
depends on Chapter 2, it can be skipped entirely. If a course in compiler design is
required, Chapter 4 is not covered.
Chapters 5 through 9 should be relatively easy for students with extensive
programming experience in C++, Java, or C#. Chapters 10 through 14 are more
challenging and require more detailed lectures.
Chapters 15 and 16 are entirely new to most students at the junior level.
Ideally, language processors for Scheme and Prolog should be available for
students required to learn the material in these chapters. Sufficient material is
included to allow students to dabble with some simple programs.
Undergraduate courses will probably not be able to cover all of the material
in the last two chapters. Graduate courses, however, should be able to completely
discuss the material in those chapters by skipping over some parts of the early
chapters on imperative languages.
Loading page 5...
5
Supplemental Materials
The following supplements are available to all readers of this book at
www.pearsonhighered.com/cs-resources/.
• A set of lecture note slides. PowerPoint slides are available for each
chapter in the book.
• All of the figures from the book.
A companion Web site to the book is available at www.pearson.com/cs-
resources/. This site contains mini-manuals (approximately 100-page tutorials) on
a handful of languages.
Solutions to many of the problem sets are available to qualified instructors in
our Instructor Resource Center at www.pearson.com. Please contact your school’s
Pearson Education representative or visit www.pearson.com to register.
Language Processor Availability
Processors for and information about some of the programming languages
discussed in this book can be found at the following Web sites:
C, C++, Fortran, and Ada gcc.gnu.org
C# and F# microsoft.com
Java java.sun.com
Haskell haskell.org
Scheme www.plt-scheme.org/software/drscheme
Perl www.perl.com
Python www.python.org
Ruby www.ruby-lang.org
JavaScript is included in virtually all browsers; PHP is included in virtually all
Web servers.
All this information is also included on the companion Web site.
Supplemental Materials
The following supplements are available to all readers of this book at
www.pearsonhighered.com/cs-resources/.
• A set of lecture note slides. PowerPoint slides are available for each
chapter in the book.
• All of the figures from the book.
A companion Web site to the book is available at www.pearson.com/cs-
resources/. This site contains mini-manuals (approximately 100-page tutorials) on
a handful of languages.
Solutions to many of the problem sets are available to qualified instructors in
our Instructor Resource Center at www.pearson.com. Please contact your school’s
Pearson Education representative or visit www.pearson.com to register.
Language Processor Availability
Processors for and information about some of the programming languages
discussed in this book can be found at the following Web sites:
C, C++, Fortran, and Ada gcc.gnu.org
C# and F# microsoft.com
Java java.sun.com
Haskell haskell.org
Scheme www.plt-scheme.org/software/drscheme
Perl www.perl.com
Python www.python.org
Ruby www.ruby-lang.org
JavaScript is included in virtually all browsers; PHP is included in virtually all
Web servers.
All this information is also included on the companion Web site.
Loading page 6...
6
Acknowledgments
The suggestions from outstanding reviewers contributed greatly to this book’s present form and contents. In
alphabetical order, they are:
Aaron Rababaah University of Maryland at Eastern Shore
Amar Raheja California State Polytechnic University–
Pomona
Amer Diwan University of Colorado
Bob Neufeld Wichita State University
Bruce R. Maxim University of Michigan–Dearborn
Charles Nicholas University of Maryland–Baltimore County
Cristian Videira Lopes University of California–Irvine
Curtis Meadow University of Maine
David E. Goldschmidt
Donald Kraft Louisiana State University
Duane J. Jarc University of Maryland, University College
Euripides Montagne University of Central Florida
Frank J. Mitropoulos Nova Southeastern University
Gloria Melara California State University–Northridge
Hossein Saiedian University of Kansas
I-ping Chu DePaul University
Ian Barland Radford University
K. N. King Georgia State University
Karina Assiter Wentworth Institute of Technology
Mark Llewellyn University of Central Florida
Acknowledgments
The suggestions from outstanding reviewers contributed greatly to this book’s present form and contents. In
alphabetical order, they are:
Aaron Rababaah University of Maryland at Eastern Shore
Amar Raheja California State Polytechnic University–
Pomona
Amer Diwan University of Colorado
Bob Neufeld Wichita State University
Bruce R. Maxim University of Michigan–Dearborn
Charles Nicholas University of Maryland–Baltimore County
Cristian Videira Lopes University of California–Irvine
Curtis Meadow University of Maine
David E. Goldschmidt
Donald Kraft Louisiana State University
Duane J. Jarc University of Maryland, University College
Euripides Montagne University of Central Florida
Frank J. Mitropoulos Nova Southeastern University
Gloria Melara California State University–Northridge
Hossein Saiedian University of Kansas
I-ping Chu DePaul University
Ian Barland Radford University
K. N. King Georgia State University
Karina Assiter Wentworth Institute of Technology
Mark Llewellyn University of Central Florida
Loading page 7...
7
Matthew Michael Burke
Michael Prentice SUNY Buffalo
Nancy Tinkham Rowan University
Neelam Soundarajan Ohio State University
Nigel Gwee Southern University–Baton Rouge
Pamela Cutter Kalamazoo College
Paul M. Jackowitz University of Scranton
Paul Tymann Rochester Institute of Technology
Richard M. Osborne University of Colorado–Denver
Richard Min University of Texas at Dallas
Robert McCloskey University of Scranton
Ryan Stansifer Florida Institute of Technology
Salih Yurttas Texas A&M University
Saverio Perugini University of Dayton
Serita Nelesen Calvin College
Simon H. Lin California State University–Northridge
Stephen Edwards Virginia Tech
Stuart C. Shapiro SUNY Buffalo
Sumanth Yenduri University of Southern Mississippi
Teresa Cole Boise State University
Thomas Turner University of Central Oklahoma
Tim R. Norton University of Colorado–Colorado Springs
Timothy Henry University of Rhode Island
Walter Pharr College of Charleston
Xiangyan Zeng Fort Valley State University
Numerous other people provided input for the previous editions of Concepts
of Programming Languages at various stages of its development. All of their
Matthew Michael Burke
Michael Prentice SUNY Buffalo
Nancy Tinkham Rowan University
Neelam Soundarajan Ohio State University
Nigel Gwee Southern University–Baton Rouge
Pamela Cutter Kalamazoo College
Paul M. Jackowitz University of Scranton
Paul Tymann Rochester Institute of Technology
Richard M. Osborne University of Colorado–Denver
Richard Min University of Texas at Dallas
Robert McCloskey University of Scranton
Ryan Stansifer Florida Institute of Technology
Salih Yurttas Texas A&M University
Saverio Perugini University of Dayton
Serita Nelesen Calvin College
Simon H. Lin California State University–Northridge
Stephen Edwards Virginia Tech
Stuart C. Shapiro SUNY Buffalo
Sumanth Yenduri University of Southern Mississippi
Teresa Cole Boise State University
Thomas Turner University of Central Oklahoma
Tim R. Norton University of Colorado–Colorado Springs
Timothy Henry University of Rhode Island
Walter Pharr College of Charleston
Xiangyan Zeng Fort Valley State University
Numerous other people provided input for the previous editions of Concepts
of Programming Languages at various stages of its development. All of their
Loading page 8...
8
comments were useful and greatly appreciated. In alphabetical order, they are:
Vicki Allan, Henry Bauer, Carter Bays, Manuel E. Bermudez, Peter Brouwer,
Margaret Burnett, Paosheng Chang, Liang Cheng, John Crenshaw, Charles Dana,
Barbara Ann Griem, Mary Lou Haag, John V. Harrison, Eileen Head, Ralph C.
Hilzer, Eric Joanis, Leon Jololian, Hikyoo Koh, Jiang B. Liu, Meiliu Lu, Jon
Mauney, Robert McCoard, Dennis L. Mumaugh, Michael G. Murphy, Andrew
Oldroyd, Young Park, Rebecca Parsons, Steve J. Phelps, Jeffery Popyack, Steven
Rapkin, Hamilton Richard, Tom Sager, Raghvinder Sangwan, Joseph Schell,
Sibylle Schupp, Mary Louise Soffa, Neelam Soundarajan, Ryan Stansifer, Steve
Stevenson, Virginia Teller, Yang Wang, John M. Weiss, Franck Xia, and Salih
Yurnas.
Matt Goldstein, Portfolio Management Specialist; Meghan Jacoby, Portfolio
Management Assistant; Managing Content Producer, Scott Disanno; and Prathiba
Rajagopal, all deserve my gratitude for their efforts to produce the twelfth edition
both quickly and carefully.
About the Author
Robert Sebesta is an Associate Professor Emeritus in the Computer Science
Department at the University of Colorado–Colorado Springs. Professor Sebesta
received a BS in applied mathematics from the University of Colorado in Boulder
and MS and PhD degrees in computer science from Pennsylvania State
University. He taught computer science for more than 40 years..
comments were useful and greatly appreciated. In alphabetical order, they are:
Vicki Allan, Henry Bauer, Carter Bays, Manuel E. Bermudez, Peter Brouwer,
Margaret Burnett, Paosheng Chang, Liang Cheng, John Crenshaw, Charles Dana,
Barbara Ann Griem, Mary Lou Haag, John V. Harrison, Eileen Head, Ralph C.
Hilzer, Eric Joanis, Leon Jololian, Hikyoo Koh, Jiang B. Liu, Meiliu Lu, Jon
Mauney, Robert McCoard, Dennis L. Mumaugh, Michael G. Murphy, Andrew
Oldroyd, Young Park, Rebecca Parsons, Steve J. Phelps, Jeffery Popyack, Steven
Rapkin, Hamilton Richard, Tom Sager, Raghvinder Sangwan, Joseph Schell,
Sibylle Schupp, Mary Louise Soffa, Neelam Soundarajan, Ryan Stansifer, Steve
Stevenson, Virginia Teller, Yang Wang, John M. Weiss, Franck Xia, and Salih
Yurnas.
Matt Goldstein, Portfolio Management Specialist; Meghan Jacoby, Portfolio
Management Assistant; Managing Content Producer, Scott Disanno; and Prathiba
Rajagopal, all deserve my gratitude for their efforts to produce the twelfth edition
both quickly and carefully.
About the Author
Robert Sebesta is an Associate Professor Emeritus in the Computer Science
Department at the University of Colorado–Colorado Springs. Professor Sebesta
received a BS in applied mathematics from the University of Colorado in Boulder
and MS and PhD degrees in computer science from Pennsylvania State
University. He taught computer science for more than 40 years..
Loading page 9...
9
Contents
Chapter 1 Preliminaries 1
1.1 Reasons for Studying Concepts of Programming Languages...................2
1.2 Programming Domains..........................................................................5
1.3 Language Evaluation Criteria.................................................................6
1.4 Influences on Language Design ...........................................................17
1.5 Language Categories ...........................................................................20
1.6 Language Design Trade-Offs ...............................................................21
1.7 Implementation Methods .....................................................................22
1.8 Programming Environments ................................................................29
Summary • Review Questions • Problem Set ...................................................30
Chapter 2 Evolution of the Major Programming Languages 33
2.1 Zuse’s Plankalkül ................................................................................36
2.2 Pseudocodes........................................................................................37
2.3 The IBM 704 and Fortran ....................................................................40
2.4 Functional Programming: Lisp.............................................................45
2.5 The First Step Toward Sophistication: ALGOL 60 ...............................50
2.6 Computerizing Business Records: COBOL ..........................................56
2.7 The Beginnings of Timesharing: Basic.................................................61
Interview: ALAN COOPER—User Design and Language Design................ 64
2.8 Everything for Everybody: PL/I...........................................................66
Contents
Chapter 1 Preliminaries 1
1.1 Reasons for Studying Concepts of Programming Languages...................2
1.2 Programming Domains..........................................................................5
1.3 Language Evaluation Criteria.................................................................6
1.4 Influences on Language Design ...........................................................17
1.5 Language Categories ...........................................................................20
1.6 Language Design Trade-Offs ...............................................................21
1.7 Implementation Methods .....................................................................22
1.8 Programming Environments ................................................................29
Summary • Review Questions • Problem Set ...................................................30
Chapter 2 Evolution of the Major Programming Languages 33
2.1 Zuse’s Plankalkül ................................................................................36
2.2 Pseudocodes........................................................................................37
2.3 The IBM 704 and Fortran ....................................................................40
2.4 Functional Programming: Lisp.............................................................45
2.5 The First Step Toward Sophistication: ALGOL 60 ...............................50
2.6 Computerizing Business Records: COBOL ..........................................56
2.7 The Beginnings of Timesharing: Basic.................................................61
Interview: ALAN COOPER—User Design and Language Design................ 64
2.8 Everything for Everybody: PL/I...........................................................66
Loading page 10...
10
2.9 Two Early Dynamic Languages: APL and SNOBOL............................69
2.10 The Beginnings of Data Abstraction: SIMULA 67 ...............................70
2.11 Orthogonal Design: ALGOL 68...........................................................71
2.12 Some Early Descendants of the ALGOLs.............................................73
2.13 Programming Based on Logic: Prolog..................................................77
2.14 History’s Largest Design Effort: Ada ...................................................79
2.15 Object-Oriented Programming: Smalltalk.............................................83
2.16 Combining Imperative and Object-Oriented Features: C++...................85
2.17 An Imperative-Based Object-Oriented Language: Java.........................88
2.18 Scripting Languages ............................................................................91
2.19 The Flagship .NET Language: C# ........................................................98
2.20 Markup-Programming Hybrid Languages .......................................... 100
Summary • Bibliographic Notes • Review Questions • Problem Set •Programming
Exercises ...................................................................................................... 102
Chapter 3 Describing Syntax and Semantics 109
3.1 Introduction....................................................................................... 110
3.2 The General Problem of Describing Syntax........................................ 111
3.3 Formal Methods of Describing Syntax ............................................... 113
3.4 Attribute Grammars........................................................................... 128
History Note ........................................................................................... 128
3.5 Describing the Meanings of Programs: Dynamic Semantics ............... 134
History Note ........................................................................................... 142
Summary • Bibliographic Notes • Review Questions • Problem Set................ 155
Chapter 4 Lexical and Syntax Analysis 161
4.1 Introduction....................................................................................... 162
4.2 Lexical Analysis................................................................................ 163
2.9 Two Early Dynamic Languages: APL and SNOBOL............................69
2.10 The Beginnings of Data Abstraction: SIMULA 67 ...............................70
2.11 Orthogonal Design: ALGOL 68...........................................................71
2.12 Some Early Descendants of the ALGOLs.............................................73
2.13 Programming Based on Logic: Prolog..................................................77
2.14 History’s Largest Design Effort: Ada ...................................................79
2.15 Object-Oriented Programming: Smalltalk.............................................83
2.16 Combining Imperative and Object-Oriented Features: C++...................85
2.17 An Imperative-Based Object-Oriented Language: Java.........................88
2.18 Scripting Languages ............................................................................91
2.19 The Flagship .NET Language: C# ........................................................98
2.20 Markup-Programming Hybrid Languages .......................................... 100
Summary • Bibliographic Notes • Review Questions • Problem Set •Programming
Exercises ...................................................................................................... 102
Chapter 3 Describing Syntax and Semantics 109
3.1 Introduction....................................................................................... 110
3.2 The General Problem of Describing Syntax........................................ 111
3.3 Formal Methods of Describing Syntax ............................................... 113
3.4 Attribute Grammars........................................................................... 128
History Note ........................................................................................... 128
3.5 Describing the Meanings of Programs: Dynamic Semantics ............... 134
History Note ........................................................................................... 142
Summary • Bibliographic Notes • Review Questions • Problem Set................ 155
Chapter 4 Lexical and Syntax Analysis 161
4.1 Introduction....................................................................................... 162
4.2 Lexical Analysis................................................................................ 163
Loading page 11...
11
4.3 The Parsing Problem ......................................................................... 171
4.4 Recursive-Descent Parsing................................................................. 175
4.5 Bottom-Up Parsing............................................................................ 183
Summary • Review Questions • Problem Set • Programming Exercises.......... 191
Chapter 5 Names, Bindings, and Scopes 197
5.1 Introduction....................................................................................... 198
5.2 Names............................................................................................... 199
History Note ........................................................................................... 199
5.3 Variables........................................................................................... 200
5.4 The Concept of Binding..................................................................... 203
5.5 Scope ................................................................................................ 211
5.6 Scope and Lifetime............................................................................ 222
5.7 Referencing Environments................................................................. 223
5.8 Named Constants............................................................................... 224
Summary • Review Questions • Problem Set •Programming Exercises........... 227
Chapter 6 Data Types 235
6.1 Introduction....................................................................................... 236
6.2 Primitive Data Types ......................................................................... 238
6.3 Character String Types ...................................................................... 242
History Note ........................................................................................... 243
6.4 Enumeration Types............................................................................ 247
6.5 Array Types ...................................................................................... 250
History Note ........................................................................................... 251
History Note ........................................................................................... 251
6.6 Associative Arrays............................................................................. 261
4.3 The Parsing Problem ......................................................................... 171
4.4 Recursive-Descent Parsing................................................................. 175
4.5 Bottom-Up Parsing............................................................................ 183
Summary • Review Questions • Problem Set • Programming Exercises.......... 191
Chapter 5 Names, Bindings, and Scopes 197
5.1 Introduction....................................................................................... 198
5.2 Names............................................................................................... 199
History Note ........................................................................................... 199
5.3 Variables........................................................................................... 200
5.4 The Concept of Binding..................................................................... 203
5.5 Scope ................................................................................................ 211
5.6 Scope and Lifetime............................................................................ 222
5.7 Referencing Environments................................................................. 223
5.8 Named Constants............................................................................... 224
Summary • Review Questions • Problem Set •Programming Exercises........... 227
Chapter 6 Data Types 235
6.1 Introduction....................................................................................... 236
6.2 Primitive Data Types ......................................................................... 238
6.3 Character String Types ...................................................................... 242
History Note ........................................................................................... 243
6.4 Enumeration Types............................................................................ 247
6.5 Array Types ...................................................................................... 250
History Note ........................................................................................... 251
History Note ........................................................................................... 251
6.6 Associative Arrays............................................................................. 261
Loading page 12...
12
6.7 Record Types .................................................................................... 265
6.8 Tuple Types ...................................................................................... 268
6.9 List Types ......................................................................................... 270
6.10 Union Types...................................................................................... 272
6.11 Pointer and Reference Types.............................................................. 275
History Note ........................................................................................... 278
6.12 Optional Types.................................................................................. 287
6.13 Type Checking .................................................................................. 287
6.14 Strong Typing ................................................................................... 288
6.15 Type Equivalence .............................................................................. 289
6.16 Theory and Data Types...................................................................... 293
Summary • Bibliographic Notes • Review Questions • Problem Set •Programming
Exercises ...................................................................................................... 295
Chapter 7 Expressions and Assignment Statements 301
7.1 Introduction....................................................................................... 302
7.2 Arithmetic Expressions...................................................................... 302
7.3 Overloaded Operators........................................................................ 311
7.4 Type Conversions.............................................................................. 313
History Note ........................................................................................... 315
7.5 Relational and Boolean Expressions................................................... 316
History Note ........................................................................................... 316
7.6 Short-Circuit Evaluation .................................................................... 318
7.7 Assignment Statements...................................................................... 319
History Note ........................................................................................... 323
7.8 Mixed-Mode Assignment .................................................................. 324
Summary • Review Questions • Problem Set • Programming Exercises ........... 324
6.7 Record Types .................................................................................... 265
6.8 Tuple Types ...................................................................................... 268
6.9 List Types ......................................................................................... 270
6.10 Union Types...................................................................................... 272
6.11 Pointer and Reference Types.............................................................. 275
History Note ........................................................................................... 278
6.12 Optional Types.................................................................................. 287
6.13 Type Checking .................................................................................. 287
6.14 Strong Typing ................................................................................... 288
6.15 Type Equivalence .............................................................................. 289
6.16 Theory and Data Types...................................................................... 293
Summary • Bibliographic Notes • Review Questions • Problem Set •Programming
Exercises ...................................................................................................... 295
Chapter 7 Expressions and Assignment Statements 301
7.1 Introduction....................................................................................... 302
7.2 Arithmetic Expressions...................................................................... 302
7.3 Overloaded Operators........................................................................ 311
7.4 Type Conversions.............................................................................. 313
History Note ........................................................................................... 315
7.5 Relational and Boolean Expressions................................................... 316
History Note ........................................................................................... 316
7.6 Short-Circuit Evaluation .................................................................... 318
7.7 Assignment Statements...................................................................... 319
History Note ........................................................................................... 323
7.8 Mixed-Mode Assignment .................................................................. 324
Summary • Review Questions • Problem Set • Programming Exercises ........... 324
Loading page 13...
13
Chapter 8 Statement-Level Control Structures 329
8.1 Introduction....................................................................................... 330
8.2 Selection Statements.......................................................................... 332
8.3 Iterative Statements ........................................................................... 343
8.4 Unconditional Branching ................................................................... 355
History Note ........................................................................................... 355
8.5 Guarded Commands .......................................................................... 356
8.6 Conclusions....................................................................................... 358
Summary • Review Questions • Problem Set • Programming Exercises ............ 359
Chapter 9 Subprograms 365
9.1 Introduction....................................................................................... 366
9.2 Fundamentals of Subprograms........................................................... 366
9.3 Design Issues for Subprograms.......................................................... 374
9.4 Local Referencing Environments ....................................................... 375
9.5 Parameter-Passing Methods ............................................................... 377
History Note ........................................................................................... 385
History Note ........................................................................................... 385
9.6 Parameters That Are Subprograms ..................................................... 393
History Note ........................................................................................... 395
9.7 Calling Subprograms Indirectly ......................................................... 395
9.8 Design Issues for Functions ............................................................... 397
9.9 Overloaded Subprograms................................................................... 399
9.10 Generic Subprograms ........................................................................ 400
9.11 User-Defined Overloaded Operators .................................................. 406
9.12 Closures ............................................................................................ 406
9.13 Coroutines......................................................................................... 408
Chapter 8 Statement-Level Control Structures 329
8.1 Introduction....................................................................................... 330
8.2 Selection Statements.......................................................................... 332
8.3 Iterative Statements ........................................................................... 343
8.4 Unconditional Branching ................................................................... 355
History Note ........................................................................................... 355
8.5 Guarded Commands .......................................................................... 356
8.6 Conclusions....................................................................................... 358
Summary • Review Questions • Problem Set • Programming Exercises ............ 359
Chapter 9 Subprograms 365
9.1 Introduction....................................................................................... 366
9.2 Fundamentals of Subprograms........................................................... 366
9.3 Design Issues for Subprograms.......................................................... 374
9.4 Local Referencing Environments ....................................................... 375
9.5 Parameter-Passing Methods ............................................................... 377
History Note ........................................................................................... 385
History Note ........................................................................................... 385
9.6 Parameters That Are Subprograms ..................................................... 393
History Note ........................................................................................... 395
9.7 Calling Subprograms Indirectly ......................................................... 395
9.8 Design Issues for Functions ............................................................... 397
9.9 Overloaded Subprograms................................................................... 399
9.10 Generic Subprograms ........................................................................ 400
9.11 User-Defined Overloaded Operators .................................................. 406
9.12 Closures ............................................................................................ 406
9.13 Coroutines......................................................................................... 408
Loading page 14...
14
Summary • Review Questions • Problem Set • Programming Exercises ............ 411
Chapter 10 Implementing Subprograms 417
10.1 The General Semantics of Calls and Returns ...................................... 418
10.2 Implementing “Simple” Subprograms................................................ 419
10.3 Implementing Subprograms with Stack-Dynamic Local Variables...... 421
10.4 Nested Subprograms.......................................................................... 429
10.5 Blocks............................................................................................... 436
10.6 Implementing Dynamic Scoping........................................................ 437
Summary • Review Questions • Problem Set • Programming Exercises ............ 441
Chapter 11 Abstract Data Types and Encapsulation Constructs 447
11.1 The Concept of Abstraction ............................................................... 448
11.2 Introduction to Data Abstraction ........................................................ 449
11.3 Design Issues for Abstract Data Types ............................................... 452
11.4 Language Examples........................................................................... 453
Interview: BJARNE STROUSTRUP—C++: Its Birth,
Its Ubiquitousness, and Common Criticisms.............................................. 454
11.5 Parameterized Abstract Data Types.................................................... 472
11.6 Encapsulation Constructs................................................................... 476
11.7 Naming Encapsulations ..................................................................... 480
Summary • Review Questions • Problem Set • Programming Exercises ............ 483
Chapter 12 Support for Object-Oriented Programming 489
12.1 Introduction....................................................................................... 490
12.2 Object-Oriented Programming ........................................................... 491
12.3 Design Issues for Object-Oriented Languages .................................... 495
12.4 Support for Object-Oriented Programming in Specific Languages ..... 500
Summary • Review Questions • Problem Set • Programming Exercises ............ 411
Chapter 10 Implementing Subprograms 417
10.1 The General Semantics of Calls and Returns ...................................... 418
10.2 Implementing “Simple” Subprograms................................................ 419
10.3 Implementing Subprograms with Stack-Dynamic Local Variables...... 421
10.4 Nested Subprograms.......................................................................... 429
10.5 Blocks............................................................................................... 436
10.6 Implementing Dynamic Scoping........................................................ 437
Summary • Review Questions • Problem Set • Programming Exercises ............ 441
Chapter 11 Abstract Data Types and Encapsulation Constructs 447
11.1 The Concept of Abstraction ............................................................... 448
11.2 Introduction to Data Abstraction ........................................................ 449
11.3 Design Issues for Abstract Data Types ............................................... 452
11.4 Language Examples........................................................................... 453
Interview: BJARNE STROUSTRUP—C++: Its Birth,
Its Ubiquitousness, and Common Criticisms.............................................. 454
11.5 Parameterized Abstract Data Types.................................................... 472
11.6 Encapsulation Constructs................................................................... 476
11.7 Naming Encapsulations ..................................................................... 480
Summary • Review Questions • Problem Set • Programming Exercises ............ 483
Chapter 12 Support for Object-Oriented Programming 489
12.1 Introduction....................................................................................... 490
12.2 Object-Oriented Programming ........................................................... 491
12.3 Design Issues for Object-Oriented Languages .................................... 495
12.4 Support for Object-Oriented Programming in Specific Languages ..... 500
Loading page 15...
15
Interview: BJARNE STROUSTRUP—On Paradigms and Better
Programming 504
12.5 Implementation of Object-Oriented Constructs................................... 528
12.6 Reflection.......................................................................................... 531
Summary • Review Questions • Problem Set • Programming Exercises ............ 537
Chapter 13 Concurrency 543
13.1 Introduction....................................................................................... 544
13.2 Introduction to Subprogram-Level Concurrency................................. 549
13.3 Semaphores....................................................................................... 554
13.4 Monitors............................................................................................ 559
13.5 Message Passing................................................................................ 561
13.6 Ada Support for Concurrency ............................................................ 562
13.7 Java Threads...................................................................................... 570
13.8 C# Threads........................................................................................ 580
13.9 Concurrency in Functional Languages................................................ 585
13.10 Statement-Level Concurrency............................................................ 588
Summary • Bibliographic Notes • Review Questions • Problem Set • Programming
Exercises....................................................................................................... 590
Chapter 14 Exception Handling and Event Handling 597
14.1 Introduction to Exception Handling ................................................... 598
History Note ........................................................................................... 602
14.2 Exception Handling in C++................................................................ 604
14.3 Exception Handling in Java ............................................................... 608
14.4 Exception Handling in Python and Ruby............................................ 615
14.5 Introduction to Event Handling.......................................................... 618
14.6 Event Handling with Java .................................................................. 619
Interview: BJARNE STROUSTRUP—On Paradigms and Better
Programming 504
12.5 Implementation of Object-Oriented Constructs................................... 528
12.6 Reflection.......................................................................................... 531
Summary • Review Questions • Problem Set • Programming Exercises ............ 537
Chapter 13 Concurrency 543
13.1 Introduction....................................................................................... 544
13.2 Introduction to Subprogram-Level Concurrency................................. 549
13.3 Semaphores....................................................................................... 554
13.4 Monitors............................................................................................ 559
13.5 Message Passing................................................................................ 561
13.6 Ada Support for Concurrency ............................................................ 562
13.7 Java Threads...................................................................................... 570
13.8 C# Threads........................................................................................ 580
13.9 Concurrency in Functional Languages................................................ 585
13.10 Statement-Level Concurrency............................................................ 588
Summary • Bibliographic Notes • Review Questions • Problem Set • Programming
Exercises....................................................................................................... 590
Chapter 14 Exception Handling and Event Handling 597
14.1 Introduction to Exception Handling ................................................... 598
History Note ........................................................................................... 602
14.2 Exception Handling in C++................................................................ 604
14.3 Exception Handling in Java ............................................................... 608
14.4 Exception Handling in Python and Ruby............................................ 615
14.5 Introduction to Event Handling.......................................................... 618
14.6 Event Handling with Java .................................................................. 619
Loading page 16...
16
14.7 Event Handling in C# ........................................................................ 623
Summary • Bibliographic Notes • Review Questions • Problem Set • Programming
Exercises....................................................................................................... 626
Chapter 15 Functional Programming Languages 633
15.1 Introduction....................................................................................... 634
15.2 Mathematical Functions..................................................................... 635
15.3 Fundamentals of Functional Programming Languages........................ 638
15.4 The First Functional Programming Language: Lisp ............................ 639
15.5 An Introduction to Scheme ................................................................ 643
15.6 Common Lisp.................................................................................... 661
15.7 ML.................................................................................................... 663
15.8 Haskell.............................................................................................. 668
15.9 F# ..................................................................................................... 673
15.10 Support for Functional Programming in Primarily Imperative Languages
......................................................................................................... 676
15.11 A Comparison of Functional and Imperative Languages..................... 679
Summary • Bibliographic Notes • Review Questions • Problem Set • Programming
Exercises....................................................................................................... 681
Chapter 16 Logic Programming Languages 689
16.1 Introduction....................................................................................... 690
16.2 A Brief Introduction to Predicate Calculus ......................................... 690
16.3 Predicate Calculus and Proving Theorems.......................................... 694
16.4 An Overview of Logic Programming ................................................. 696
16.5 The Origins of Prolog ........................................................................ 698
16.6 The Basic Elements of Prolog ............................................................ 698
16.7 Deficiencies of Prolog ....................................................................... 713
14.7 Event Handling in C# ........................................................................ 623
Summary • Bibliographic Notes • Review Questions • Problem Set • Programming
Exercises....................................................................................................... 626
Chapter 15 Functional Programming Languages 633
15.1 Introduction....................................................................................... 634
15.2 Mathematical Functions..................................................................... 635
15.3 Fundamentals of Functional Programming Languages........................ 638
15.4 The First Functional Programming Language: Lisp ............................ 639
15.5 An Introduction to Scheme ................................................................ 643
15.6 Common Lisp.................................................................................... 661
15.7 ML.................................................................................................... 663
15.8 Haskell.............................................................................................. 668
15.9 F# ..................................................................................................... 673
15.10 Support for Functional Programming in Primarily Imperative Languages
......................................................................................................... 676
15.11 A Comparison of Functional and Imperative Languages..................... 679
Summary • Bibliographic Notes • Review Questions • Problem Set • Programming
Exercises....................................................................................................... 681
Chapter 16 Logic Programming Languages 689
16.1 Introduction....................................................................................... 690
16.2 A Brief Introduction to Predicate Calculus ......................................... 690
16.3 Predicate Calculus and Proving Theorems.......................................... 694
16.4 An Overview of Logic Programming ................................................. 696
16.5 The Origins of Prolog ........................................................................ 698
16.6 The Basic Elements of Prolog ............................................................ 698
16.7 Deficiencies of Prolog ....................................................................... 713
Loading page 17...
17
16.8 Applications of Logic Programming .................................................. 719
Summary • Bibliographic Notes • Review Questions • Problem Set • Programming
Exercises....................................................................................................... 720
Bibliography .....................................................................................725
Index..................................................................................................737
Answers to Selected Problems
Chapter 1
Problem Set:
3. Some arguments for having a single language for all programming domains are: It
would dramatically cut the costs of programming training and compiler purchase and
maintenance; it would simplify programmer recruiting and justify the development of
numerous language dependent software development aids.
4. Some arguments against having a single language for all programming domains are:
The language would necessarily be huge and complex; compilers would be expensive
and costly to maintain; the language would probably not be very good for any
programming domain, either in compiler efficiency or in the efficiency of the code it
generated. More importantly, it would not be easy to use, because regardless of the
application area, the language would include many unnecessary and confusing features
and constructs (those meant for other application areas). Different users would learn
different subsets, making maintenance difficult.
5. One possibility is wordiness. In some languages, a great deal of text is required for
even simple complete programs. For example, COBOL is a very wordy language. In
Ada, programs require a lot of duplication of declarations. Wordiness is usually
considered a disadvantage, because it slows program creation, takes more file space for
the source programs, and can cause programs to be more difficult to read.
7. The argument for using the right brace to close all compounds is simplicity—a right
brace always terminates a compound. The argument against it is that when you see a right
brace in a program, the location of its matching left brace is not always obvious, in part
because all multiple-statement control constructs end with a right brace.
8. The reasons why a language would distinguish between uppercase and lowercase in its
identifiers are: (1) So that variable identifiers may look different than identifiers that are
names for constants, such as the convention of using uppercase for constant names and
using lowercase for variable names in C, and (2) so that catenated words as names can
have their first letter distinguished, as in TotalWords. (Some think it is better to include
a connector, such as underscore.) The primary reason why a language would not
16.8 Applications of Logic Programming .................................................. 719
Summary • Bibliographic Notes • Review Questions • Problem Set • Programming
Exercises....................................................................................................... 720
Bibliography .....................................................................................725
Index..................................................................................................737
Answers to Selected Problems
Chapter 1
Problem Set:
3. Some arguments for having a single language for all programming domains are: It
would dramatically cut the costs of programming training and compiler purchase and
maintenance; it would simplify programmer recruiting and justify the development of
numerous language dependent software development aids.
4. Some arguments against having a single language for all programming domains are:
The language would necessarily be huge and complex; compilers would be expensive
and costly to maintain; the language would probably not be very good for any
programming domain, either in compiler efficiency or in the efficiency of the code it
generated. More importantly, it would not be easy to use, because regardless of the
application area, the language would include many unnecessary and confusing features
and constructs (those meant for other application areas). Different users would learn
different subsets, making maintenance difficult.
5. One possibility is wordiness. In some languages, a great deal of text is required for
even simple complete programs. For example, COBOL is a very wordy language. In
Ada, programs require a lot of duplication of declarations. Wordiness is usually
considered a disadvantage, because it slows program creation, takes more file space for
the source programs, and can cause programs to be more difficult to read.
7. The argument for using the right brace to close all compounds is simplicity—a right
brace always terminates a compound. The argument against it is that when you see a right
brace in a program, the location of its matching left brace is not always obvious, in part
because all multiple-statement control constructs end with a right brace.
8. The reasons why a language would distinguish between uppercase and lowercase in its
identifiers are: (1) So that variable identifiers may look different than identifiers that are
names for constants, such as the convention of using uppercase for constant names and
using lowercase for variable names in C, and (2) so that catenated words as names can
have their first letter distinguished, as in TotalWords. (Some think it is better to include
a connector, such as underscore.) The primary reason why a language would not
Loading page 18...
18
distinguish between uppercase and lowercase in identifiers is it makes programs less
readable, because words that look very similar are actually completely different, such as
SUM and Sum.
10. One of the main arguments is that regardless of the cost of hardware, it is not free.
Why write a program that executes slower than is necessary. Furthermore, the difference
between a well-written efficient program and one that is poorly written can be a factor of
two or three. In many other fields of endeavor, the difference between a good job and a
poor job may be 10 or 20 percent. In programming, the difference is much greater.
15. The use of type declaration statements for simple scalar variables may have very little
effect on the readability of programs. If a language has no type declarations at all, it may
be an aid to readability, because regardless of where a variable is seen in the program
text, its type can be determined without looking elsewhere. Unfortunately, most
languages that allow implicitly declared variables also include explicit declarations. In a
program in such a language, the declaration of a variable must be found before the reader
can determine the type of that variable when it is used in the program.
18. The main disadvantage of using paired delimiters for comments is that it results in
diminished reliability. It is easy to inadvertently leave off the final delimiter, which
extends the comment to the end of the next comment, effectively removing code from the
program. The advantage of paired delimiters is that you can comment out areas of a
program. The disadvantage of using only beginning delimiters is that they must be
repeated on every line of a block of comments. This can be tedious and therefore error-
prone. The advantage is that you cannot make the mistake of forgetting the closing
delimiter.
Chapter 2
Problem Set:
6. Because of the simple syntax of LISP, few syntax errors occur in LISP programs.
Unmatched parentheses is the most common mistake.
7. The main reason why imperative features were put in LISP was to increase its
execution efficiency.
10. The main motivation for the development of PL/I was to provide a single tool for
computer centers that must support both scientific and commercial applications. IBM
believed that the needs of the two classes of applications were merging, at least to some
degree. They felt that the simplest solution for a provider of systems, both hardware and
software, was to furnish a single hardware system running a single programming
language that served both scientific and commercial applications.
11. IBM was, for the most part, incorrect in its view of the future of the uses of
computers, at least as far as languages are concerned. Commercial applications are
nearly all done in languages that are specifically designed for them. Likewise for
scientific applications. On the other hand, the IBM design of the 360 line of computers
was a great success--it still dominates the area of computers between supercomputers and
minicomputers. Furthermore, 360 series computers and their descendants have been
widely used for both scientific and commercial applications. These applications have
been done, in large part, in Fortran and COBOL.
distinguish between uppercase and lowercase in identifiers is it makes programs less
readable, because words that look very similar are actually completely different, such as
SUM and Sum.
10. One of the main arguments is that regardless of the cost of hardware, it is not free.
Why write a program that executes slower than is necessary. Furthermore, the difference
between a well-written efficient program and one that is poorly written can be a factor of
two or three. In many other fields of endeavor, the difference between a good job and a
poor job may be 10 or 20 percent. In programming, the difference is much greater.
15. The use of type declaration statements for simple scalar variables may have very little
effect on the readability of programs. If a language has no type declarations at all, it may
be an aid to readability, because regardless of where a variable is seen in the program
text, its type can be determined without looking elsewhere. Unfortunately, most
languages that allow implicitly declared variables also include explicit declarations. In a
program in such a language, the declaration of a variable must be found before the reader
can determine the type of that variable when it is used in the program.
18. The main disadvantage of using paired delimiters for comments is that it results in
diminished reliability. It is easy to inadvertently leave off the final delimiter, which
extends the comment to the end of the next comment, effectively removing code from the
program. The advantage of paired delimiters is that you can comment out areas of a
program. The disadvantage of using only beginning delimiters is that they must be
repeated on every line of a block of comments. This can be tedious and therefore error-
prone. The advantage is that you cannot make the mistake of forgetting the closing
delimiter.
Chapter 2
Problem Set:
6. Because of the simple syntax of LISP, few syntax errors occur in LISP programs.
Unmatched parentheses is the most common mistake.
7. The main reason why imperative features were put in LISP was to increase its
execution efficiency.
10. The main motivation for the development of PL/I was to provide a single tool for
computer centers that must support both scientific and commercial applications. IBM
believed that the needs of the two classes of applications were merging, at least to some
degree. They felt that the simplest solution for a provider of systems, both hardware and
software, was to furnish a single hardware system running a single programming
language that served both scientific and commercial applications.
11. IBM was, for the most part, incorrect in its view of the future of the uses of
computers, at least as far as languages are concerned. Commercial applications are
nearly all done in languages that are specifically designed for them. Likewise for
scientific applications. On the other hand, the IBM design of the 360 line of computers
was a great success--it still dominates the area of computers between supercomputers and
minicomputers. Furthermore, 360 series computers and their descendants have been
widely used for both scientific and commercial applications. These applications have
been done, in large part, in Fortran and COBOL.
Loading page 19...
18 more pages available. Scroll down to load them.
Preview Mode
Sign in to access the full document!
100%
Study Now!
XY-Copilot AI
Unlimited Access
Secure Payment
Instant Access
24/7 Support
AI Assistant
Document Details
Subject
Information Technology