We all have witnessed the rapid development of computer
science and its applications in many domains, particularly in web-based computing
(Web 2.0), cloud computing, big data processing, and mobile computing. As a
science discipline, the fundamentals of computer science, including programming
language principles and the classic programming languages, are stable and do
not change with the technological innovations. C, C++, Scheme/LISP, and Prolog
belong to the classic programming languages that were developed several decades
ago and are still the most significant programming languages today, both in
theory and in practice. However, the technologies that surround these languages
have been changed and improved, which give these languages new perspectives and
new applications. For example, C++ is extended to generic classes and writing
multithread programs. Functional programming principles are widely used in
database query languages and the new object- and service-oriented programming
languages such as C#.
This text is intended for
computer science and computer engineering students in their sophomore year of
study. It is assumed that students have completed a basic computer science
course and have learned a high-level programming language like C, C++, or Java.
Most of the content presented
in the text has been used in the “Introduction to Programming Languages” course
taught by the author in the School of Computer Science at the University of the
Witwatersrand at Johannesburg, and in the Computer Science and Engineering
programs at Arizona State University. This text is different
from
the existing texts on programming languages that
either focus on teaching programming paradigms, principles, and the language
mechanisms, or focus on language constructs and programming skills. This text
takes a balanced approach on both sides. It teaches four programming languages
representing four major programming paradigms. Programming paradigms,
principles, and language mechanisms are used as the vehicle to facilitate
learning of the four programming languages in a coherent way. The goals of such
a programming course are to make sure that computer science students are
exposed to different programming paradigms and language mechanisms, and obtain
sufficient programming skills and experience in different programming
languages, so that they can quickly use these or similar languages in other
courses.
Although there are many
different programming paradigms, imperative, object-oriented, functional, and
logic programming paradigms are the four major paradigms widely taught in
computer science and computer engineering departments around the world. The
four languages we will study in the text are the imperative C, object-oriented
C++, functional Scheme, and logic Prolog. At the end of the course, students
should understand
·
the language structures at different layers (lexical, syntactic,
contextual, and semantic), the control structures and the execution models of
imperative, object-oriented, functional, and logic programming languages;
·
program processing (compilation versus interpretation) and
preprocessing (macros and inlining);
·
different aspects of a variable, including its type, scope, name,
address, memory location, and value.
More specific features of programming languages and
programming issues are explored in cooperation with the four selected
languages. Students are expected to have understood and be able to
·
write C programs with complex data types, including pointers,
arrays, and generic structures, as well as programs with static and dynamic
memory allocation;
·
apply the object-oriented features such as inheritance and class
hierarchy, polymorphism and typing, overloading, early versus late binding, as
well as the constructors, the destructor and the management of static memory,
stack, and heap in C++;
·
apply the functional programming style of parameter passing and
write Scheme programs requiring multiple functions;
·
apply the logic programming style of parameter passing, write
Prolog facts, rules, and goals, and use multiple rules to solve problems;
·
be able to write programs requiring multiple
subprograms/procedures to solve large programming problems;
·
be able to write recursive subprograms/procedures in imperative,
object-oriented, functional, and logic programming languages.
The text has
been revised
and improved throughout in each of
the new editions.In the second edition, the major
change made was the inclusion of programming in Service-Oriented Architecture
(SOA). Since the publication of the first edition in 2003, SOA programming has
emerged as a new programming paradigm, which has demonstrated its strength to
become a dominating programming paradigm. All major computing companies,
including HP, IBM, Intel, Microsoft, Oracle, SAP, and Sun Microsystems, have
moved into this new paradigm and are using the new paradigm to produce software
and even hardware systems. The need for skill in SOA programming increases as
the deployment of SOA applications increases. This new SOA paradigm is not only
important in the practice of programming, but it also contributes to the
concepts and principles of programming theory. In fact, SOA programming applies
a higher level of abstraction, which requires fewer technical details for
building large software applications. We, the authors of this book, are leading
researchers and educators in SOA programming. The inclusion of the new chapter
on C# and SOA programming makes the text unique, which allows teaching of the
most contemporary programming concepts and practice. The new chapter also gives
professors a new component to choose from, which adds flexibility for them to
select different contents for different courses. As SOA has developed
significantly in the past 10 years, this chapter is also updated in the fourth
edition to include an introduction to Silverlight animation, phone application
development, cloud computing, and big data processing.
In the third edition, we completely
rewrite Chapter 5. We also discuss the modern applications of Prolog in the
semantic
web
(Web 3.0) and its
relationship with the currently used
web
semantic languages RDF (Resource Description Framework) and OWL (Web Ontology
Language). Semantic
web
is considered the
next generation of
web that allows the web
to be browsed and explored by both humans and
computer programs. In the third edition revised print, this chapter is further
expanded with the latest computing technologies in cloud computing and big data
processing.
Since the publication of the
second edition in 2006, the programming environment for Chapter 4, on Scheme,
has been changed from DrScheme to DrRacket. The change does not affect the
examples in the text. They all work in the new DrRacket environment, except
certain notational issues. We have updated Chapter 4 to match the changes made
in DrRacket.
As parallel computing and
multithreading are becoming more and more important in software development,
the third edition adds a new section on parallel computing and multithreading
in C++, in Chapter 3. A MapReduce example is used as a case study for
explaining multithreading in C++. The parallel computing concept is also
emphasized in Chapter 4, where the eager evaluation and higher functions Map
and Reduce are linked to parallel computing.
In the fourth edition, we
added a number of new sections and many examples throughout Chapters 1, 2, 3,
4, 5, and 6 to explain the more difficulty concepts. In Chapter 1, macro
expansion and execution are explained in more detail and the order of
executions are discussed and showed on different programming environments. More
complex
examples
of syntax graphs are
given in Section 1.2. In Chapter 2, structure padding is discussed in Section
2.5. The file operations in Section 2.6 are extended. More recursive examples are
given in Section 2.7. A case study that puts all together is given in a new
section at the end of the chapter. In Chapter 3, a new subsection on memory
leak detection is added in Section 3.3 on memory management. Section 3.4 on
inheritance is extended with a new subsection on type casting. A new section on
C++ file operations is added as Section 3.5. In Chapter 4, the application of
filtering in query languages is added in Section 4.9. In the new editions,
Chapter 5 is further extended to include
web
application and phone application development in C#. It also extends the
discussions to cloud computing and big data processing.
In the fifth edition, changes and revisions are made throughout
the book. In Chapter 2, more data structures are discussed, including doubly
linked list, graphs, and trees. Chapter 3, Object-Oriented Programming Language
C++, is significantly extended to include inheritance, type casting, function
overloading and operator overloading, and C++ file operations. A new section
3.8 Case Study is included to put together all the concepts and programming
mechanisms learned in this chapter. In Appendix B, tutorials on using GNU GCC environment
and Visual Studio environment to edit and debug programs are added.
This edition of the text is
organized into six chapters and three appendices. Chapter 1 discusses the
programming paradigms, principles, and common aspects of programming languages.
Chapter 2 uses C as the example of the imperative programming paradigm to teach
how to write imperative programs. It is assumed that students have a basic
understanding of a high-level programming language such as C, C++, or Java.
Chapter 3 extends the discussion and programming from C to C++. The chapter
focuses on the main features of object-oriented programming paradigms,
including class composition, dynamic memory management and garbage collection,
inheritance, dynamic memory allocation and
deallocation
, late binding, polymorphism, and class hierarchy.
Chapters 4 and 5 take a major paradigm shift to teach functional and logic
programming, respectively. Students are not required to have any knowledge of
functional and logic programming to learn from these two chapters. Chapter 6
gives a brief introduction to C# and service-oriented computing paradigm. A full
discussion of the service-oriented computing paradigm is given in another book
by the authors: Service-Oriented Computing and Web Software Integration.
Assignments, programming exercises, and projects are given at the end of each
chapter.
The sections with an asterisk (*) are optional and can be
skipped if time does not permit covering all the material. Chapters 4 and 5 are
self-contained and can be taught independently, or in a different order.
The three appendices provide
supplementary materials to the main text. In Appendix A, the basic computer
organization and assembly language programming are introduced. If students do
not have a basic computer science background, the material should be covered in
the class. Appendix B starts with basic Unix commands. If the class uses a
Unix-based laboratory environment, students can read the appendix to get
started with Unix. Then the appendix introduces the major programming language
environments that can be used to support teaching the four programming
languages, including GNU GCC/G++ for C and C++, Visual Studio for C and C++,
DrRacket for Scheme, and GNU Prolog. Appendix C gives the ASCII code table that
is referred to in various parts of the text.
The text consists of six
chapters, which can be considered reconfigurable components of a course. A
half-semester course (25–30 lecture hours) can teach from two to three
chapters, and a full semester course can teach four to five chapters of choice
from the text. Chapter 3 (C++) is closely related to Chapter 2. If Chapter 3 is
selected as a component of a course, Chapter 2, or a part of Chapter 2, should
be selected as well. Other chapters are relatively independent of each other
and can be selected freely to compose a course.
For a half-semester course,
sensible course compositions could include: (Chapters 1, 2, 3); (Chapters 2,
3); (Chapters 1, 2, 6); (Chapters 2, 3, 6); (Chapters 1, 4, 5); and (Chapters 4,
5). For a full semester course, sensible course compositions could include:
(chapters 1, 2, 3, 4, 5); (chapters 1, 2, 3, 4, 6); (Chapters 1, 2, 3, 5, 6);
and (Chapters 2, 3, 4, 5, 6).
I wish to thank all those who
have contributed to the materials and to the formation of this text.
Particularly, I would like to thank my colleagues Scott Hazelhurst and Conrad
Mueller of the University of the Witwatersrand, and Richard Whitehouse of
Arizona State University who shared their course materials with me. Parts of
these materials were used in teaching the programming languages course and in
preparing this text. Thomas Boyd, Joe DeLibero, Renee Turban, and Wei-Tek Tsai of
Arizona State University reviewed the drafts of the text and made constructive
suggestions and useful comments. Other instructors using this text have given
me invaluable feedback and improvement suggestions, including Janaka
Balasooriya, Calvin Cheng, Mutsumi Nakamura, and Yalin Wang. My teaching
assistants helped me in the past few years to prepare the assignments and
programming exercises
; particularly, I would
like to thank Ruben Acuna, Raynette Brodie, Justin
Convery, Gennaro De Luca, Garrett Gutierrez, and Kevin Liao.
The text was written and
revised while I was carrying out a full university workload. I am thankful to
my family. I could not imagine that I would be able to complete the task
without their generous support by allowing me to use most of the weekends in
the past year to write the text.
Although I have used the
materials in teaching the programming languages courses at the University of
the Witwatersrand, Johannesburg and at Arizona State University for several
years, the text was put together in a short period of time. There are certainly
many errors of different kinds. I would appreciate it if you could send me any
corrections, comments, or suggestions for improving the text. My email address dedicated
to dealing with the responses to the text is <yinong.chen@asu.edu>.
Instructors who use the text can contact the author for instructional support,
including lecture slides in PowerPoint format and the solutions to the
assignments.
Table of Contents
Table of
Contents
Preface xi
Chapter 1 Basic
Principles of Programming Languages 1
1.1 Introduction2
1.1.1 Programming
concepts and paradigms 2
1.1.2 Program
performance and features of programming languages3
1.1.3 Development
of programming languages 4
1.2 Structures
of programming languages 8
1.2.1 Lexical
structure 8
1.2.2 Syntactic
structure 9
1.2.3 Contextual
structure 9
1.2.4 Semantic
structure 9
1.2.5 BNF notation9
1.2.6 Syntax graph11
1.3 Data types
and type checking 12
1.3.1 Data types
and type equivalence 13
1.3.2 Type
checking and type conversion 13
1.3.3 Orthogonality14
1.4 Program
processing and preprocessing 16
1.4.1 Interpretation
and compilation 16
1.4.2 Preprocessing:
macro and inlining 18
*1.5 Program
development 23
1.5.1 Program
development process 23
1.5.2 Program
testing 24
1.5.3 Correctness
proof 27
1.6 Summary29
1.7 Homework
and programming exercises 31
Chapter 2 The
Imperative Programming Languages, C/C++ 39
2.1 Getting
started with C/C++ 40
2.1.1 Write your
first C/C++ program 40
2.1.2 Basic input
and output functions 41
2.1.3 Formatted
input and output functions 42
2.2 Control
structures in C/C++ 44
2.2.1 Operators
and the order of evaluation 44
2.2.2 Basic
selection structures (if-then-else and the conditional expression)45
2.2.3 Multiple
selection structure (switch) 46
2.2.4 Iteration
structures (while, do-while, and for) 49
2.3 Data and
basic data types in C/C++ 51
2.3.1 Declaration
of variables and functions 51
2.3.2 Scope rule52
2.3.3 Basic data
types 53
2.4 Complex
types 56
2.4.1 Array56
2.4.2 Pointer58
2.4.3 String60
2.4.4 Constants69
2.4.5 Enumeration
type 70
2.5 Compound
data types 73
2.5.1 Structure
types and paddings 73
2.5.2 Union75
2.5.3 Array of
structures using static memory allocation 77
2.5.4 Linked list
using dynamic memory allocation 80
2.5.5 Doubly
linked list 84
2.5.6 Stack86
2.6 Standard
input and output, files, and file operations 89
2.6.1 Basic
concepts of files and file operations 89
2.6.2 File
operations in C 90
2.6.3 Flush
operation in C 95
2.7 Functions
and parameter passing 97
2.8 Recursive
structures and applications 101
2.8.1 Loop
structures versus recursive structures 101
2.8.2 The
fantastic-four abstract approach of writing recursive functions102
2.8.3 Hanoi Towers103
2.8.4 Insertion
sorting 106
2.8.5 Merge sort
algorithm 108
2.8.6 Quick sort
algorithm 110
2.8.7 Tree operations110
2.8.8 Gray code
generation 114
2.9 Modular
design 116
2.10 Case Study:
Putting All Together 118
2.11 Summary125
2.12 Homework,
programming exercises, and projects 127
Chapter 3 The
Object-Oriented Programming Language, C++ 147
3.1 A long program
example: a queue and a priority queue written in C++148
3.2 Class
definition and composition 151
3.2.1 Class
definition 151
3.2.2 Scope
resolution operator 152
3.2.3 Objects from
a class 153
3.2.4 Definition
of constructor and destructor 153
3.3 Memory
management and garbage collection 154
3.3.1 Static:
global variables and static local variables 155
3.3.2 Runtime
stack for local variables 156
3.3.3 Heap:
dynamic memory allocation 159
3.3.4 Scope and
garbage collection 159
3.3.5 Memory leak
detection 164
3.4 Inheritance171
3.4.1 Class
containment and inheritance 171
3.4.2 Inheritance
and virtual function 174
3.4.3 Inheritance
and hierarchy 177
3.4.4 Inheritance
and polymorphism 191
3.4.5 Polymorphism
and type checking 193
3.4.6 Polymorphism
and late binding 194
3.4.7 Type Casting
in C++ 194
3.5 Function
and Operator Overloading 196
3.5.1 Function
overloading 196
3.5.2 Operator
overloading 197
3.6 File
Operations in C++ 203
3.6.1 File objects
and operations in C++ 203
3.6.2 Ignore
operation in C++ 208
3.7 Exception
Handling 209
3.8 Case
Study: Putting All Together 213
3.8.1 Organization
of the program 213
3.8.2 Header files214
3.8.3 Source files216
*3.9 Parallel
computing and multithreading 224
3.9.1 Basic
concepts in parallel computing and multithreading224
3.9.2 Generic
features in C++ 224
3.9.3 Case Study:
Implementing multithreading in C++ 226
3.10 Summary230
3.11 Homework,
programming exercises, and projects 231
Chapter 4 The
Functional Programming Language, Scheme 241
4.1 From
imperative programming to functional programming242
4.2 Prefix
notation 244
4.3 Basic
Scheme terminology 246
4.4 Basic
Scheme data types and functions 249
4.4.1 Number types249
4.4.2 Boolean250
4.4.3 Character251
4.4.4 String252
4.4.5 Symbol252
4.4.6 Pair252
4.4.7 List254
4.4.8 Application
of Quotes 255
4.4.9 Definition
of procedure and procedure type 256
4.4.10 Input/output
and nonfunctional features 258
*4.5 Lambda-calculus260
4.5.1 Lambda-expressions260
4.5.2 -procedure
and parameter scope 261
4.5.3 Reduction
rules 261
4.6 Define
your Scheme procedures and macros 262
4.6.1 Unnamed
procedures 263
4.6.2 Named
procedures 263
4.6.3 Scopes of
variables and procedures 263
4.6.4 Let-form and
unnamed procedures 265
4.6.5 Macros266
4.6.6 Compare and
contrast imperative and functional programming paradigms268
4.7 Recursive
procedures 270
4.8 Define
recursive procedures on data types 272
4.8.1 Number
manipulations 272
4.8.2 Character
and string manipulations 276
4.8.3 List
manipulations 277
4.9 Higher-order
functions 279
4.9.1 Mapping280
4.9.2 Reduction283
4.9.3 Filtering284
4.9.4 Application
of filtering in query languages 286
4.10 Summary287
4.11 Homework,
programming exercises, and projects 289
Chapter 5 The
Logic Programming Language, Prolog 299
5.1 Basic
concepts of logic programming in Prolog 299
5.1.1 Prolog
basics 300
5.1.2 Structures
of Prolog facts, rules, and goals 302
5.2 The Prolog
execution model 303
5.2.1 Unification
of a goal 303
5.2.2 Example of
searching through a database 305
5.3 Arithmetic
operations and database queries 306
5.3.1 Arithmetic
operations and built-in functions 306
5.3.2 Combining
database queries with arithmetic operations 308
5.4 Prolog
functions and recursive rules 310
5.4.1 Parameter
passing in Prolog 310
5.4.2 Factorial
example 311
5.4.3 Fibonacci
numbers example 311
5.4.4 Hanoi Towers312
5.4.5 Graph model
and processing 313
5.4.6 Map
representation and coloring 314
5.5 List and
list manipulation 316
5.5.1 Definition
of pairs and lists 316
5.5.2 Pair
simplification rules 317
5.5.3 List
membership and operations 318
5.5.4 Knapsack
problem 321
5.5.5 Quick sort322
5.6 Flow
control structures 323
5.6.1 Cut324
5.6.2 Fail327
5.6.3 Repeat328
*5.7 Prolog
application in semantic Web 330
5.8 Summary331
5.9 Homework,
programming exercises, and projects 333
Chapter 6 Fundamentals
of the Service-Oriented Computing Paradigm 341
6.1 Introduction
to C# 341
6.1.1 Getting
started with C# and Visual Studio 341
6.1.2 Comparison
between C++ and C# 343
6.1.3 Namespaces
and the using directives 343
6.1.4 The queue
example in C# 345
6.1.5 Class and
object in C# 346
6.1.6 Parameters:
passing by reference with ref&out349
6.1.7 Base classes
and constructors 350
6.1.8 Constructor,
destructor, and garbage collection 350
6.1.9 Pointers in
C# 351
6.1.10 C# unified
type system 352
6.1.11 Further
topics in C# 353
6.2 Service-oriented
computing paradigm 353
6.2.1 Basic
concepts and terminologies 353
6.2.2 Web services
development 355
6.2.3 Service-oriented
system engineering 356
6.2.4 Web services
and enabling technologies 357
6.3 *Service
providers: programming web services in C# 358
6.3.1 Creating a
web service project 359
6.3.2 Writing the
service class 360
6.3.3 Launch and
access your web services 361
6.3.4 Automatically
generating a WSDL file 363
6.4 Publishing
and searching web services using UDDI 365
6.4.1 UDDI file365
6.4.2 ebXML 367
6.4.3 Ad hoc
registry lists 368
6.5 Building
applications using ASP.Net 368
6.5.1 Creating
your own web browser 368
6.5.2 Creating a
Windows application project in ASP.Net 369
6.5.3 Developing a
website application to consume web services 374
6.6 Silverlight
and Phone Applications Development 377
6.6.1 Silverlight
Applications 377
6.6.2 Developing
Windows Phone Apps Using Silverlight 380
6.7 Cloud
computing and big data processing 389
6.7.1 Cloud
computing 389
6.7.2 Big data392
6.8 Summary394
6.9 Homework,
programming exercises, and projects 395
Appendix A Basic
Computer Architectures and Assembly Language Programming401
A.1 Basic
computer components and computer architectures 401
A.2 Computer
architectures and assembly programming 402
A.3 Subroutines
and local variables on stack 407
Appendix B Programming
Environments Supporting C, C++, Scheme, and Prolog409
B.1 Introduction
to operating systems 409
B.2 Introduction
to Unix and C/C++ programming environments 412
B.2.1 Unix and
Linux operating systems 412
B.2.2 Unix shell
and commands 413
B.2.3 Unix system
calls 417
B.2.4 Getting
started with GNU GCC under the Unix operating system419
B.2.5 Debugging
your C/C++ programs in GNC GCC 421
B.2.6 Frequently
used GCC compiler options 424
B.2.7 C/C++
operators 424
B.2.8 Download
programming development environments and tutorials426
B.3 Getting
started with Visual Studio programming environment426
B.3.1 Creating a
C/C++ project in Visual Studio 427
B.3.2 Debugging
your C/C++ programs in Visual Studio 429
B.4 Programming
environments supporting Scheme programming 430
B.4.1 Getting started
with DrRacket 430
B.4.2 Download
DrRacket programming environment 431
B.5 Programming
environments supporting Prolog programming 432
B.5.1 Getting
started with the GNU Prolog environment 432
B.5.2 Getting
started with Prolog programming 433
B.5.3 Download
Prolog programming development tools 435
Appendix C ASCII
Character Table 437
Bibliography 439
Index 443