Fourth Edition
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 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
have been revised and improved throughout the entire text in each of 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 example 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.
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 the 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 de-allocation, 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 teaching the programming languages course
and in preparing this text. Thomas Boyd, Joe DeLibero, and Renee Turban 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, and Mutsumi Nakamura. My teaching assistants helped me in the past
few years to prepare the assignments and programming exercises, particularly, I
could like to thank Ruben Acuna, Raynette Brodie, Gennaro De Luca, and Garrett
Gutierrez.
The text
was written 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.
Yinong
Chen and Wei-Tek Tsai
May 2015
Table of Contents
Preface
x
Chapter 1
Basic Principles of Programming
Languages.
1
1.1
Introduction.
1
1.1.1
Programming concepts and paradigms
1
1.1.2
Program performance and features of
programming languages
3
1.1.3
Development of programming
languages
4
1.2
Structures of programming languages.
7
1.2.1
Lexical structure
7
1.2.2
Syntactic structure
7
1.2.3
Contextual structure
7
1.2.4
Semantic structure
8
1.2.5
BNF notation
8
1.2.6
Syntax graph
10
1.3
Data types and type checking.
11
1.3.1
Data types and type equivalence
11
1.3.2
Type checking and type conversion
12
1.3.3
Orthogonality
13
1.4
Program processing and preprocessing.
15
1.4.1
Interpretation and compilation
15
1.4.2
Preprocessing: macro and inlining
16
*1.5
Program development
21
1.5.1
Program development process
22
1.5.2
Program testing
22
1.5.3
Correctness proof
26
1.6
Summary.
28
1.7
Homework and programming exercises.
29
Chapter 2
The Imperative Programming
Languages, C/C++.
35
2.1
Getting started with C/C++.
36
2.1.1
Write your first C/C++ program
36
2.1.2
Basic input and output functions
37
2.1.3
Formatted input and output
functions
37
2.2
Control structures in C/C++.
39
2.2.1
Operators and the order of
evaluation
40
2.2.2
Basic selection structures
(if-then-else and the conditional expression)
40
2.2.3
Multiple selection structure
(switch)
42
2.2.4
Iteration structures (while,
do-while, and for)
45
2.3
Data and basic data types in C/C++.
47
2.3.1
Declaration of variables and
functions
47
2.3.2
Scope rule
48
2.3.3
Basic data types
49
2.4
Complex types.
52
2.4.1
Array
52
2.4.2
Pointer
54
2.4.3
String
57
2.4.4
Constants
65
2.4.5
Enumeration type
66
2.5
Compound data types.
69
2.5.1
Structure types and size of
structure variable
69
2.5.2
Union
71
2.5.3
Array of structures using static
memory allocation
73
2.5.4
Linked list using dynamic memory
allocation
76
2.5.5
Stack
80
2.6
Standard input and output, files, and file
operations.
83
2.6.1
Basic concepts of files and file
operations
83
2.6.2
File operations in C
84
2.6.3
Flush operation in C
88
2.7
Functions and parameter passing.
90
2.8
Recursive structures and applications.
94
2.8.1
Loop structures versus recursive structures
94
2.8.2
The fantastic-four abstract
approach of writing recursive functions
95
2.8.3
Hanoi Towers
96
2.8.4
A simple recursive sorting
algorithm
99
2.8.5
Merge sort algorithm
101
2.8.6
Quick sort algorithm
102
2.8.7
Gray code generation
103
2.9
Modular design.
105
2.10
Case Study: Putting All Together
107
2.11
Summary.
114
2.12
Homework, programming exercises, and projects.
117
Chapter 3
The Object-Oriented Programming
Language, C++.
137
3.1
A long program example: a queue and a
priority queue written in C++.
138
3.2
Class definition and composition.
141
3.2.1
Class definition
141
3.2.2
Scope resolution operator
142
3.2.3
Objects from a class
143
3.2.4
Definition of constructor and
destructor
143
3.3
Memory management and garbage collection.
144
3.3.1
Static: global variables and static
local variables
145
3.3.2
Runtime stack for local variables
146
3.3.3
Heap: dynamic memory allocation
149
3.3.4
Scope and garbage collection
149
3.3.5
Memory leak detection
154
3.4
Inheritance.
161
3.4.1
Class containment and inheritance
161
3.4.2
Inheritance and hierarchy
164
3.4.3
Inheritance and polymorphism
178
3.4.4
Polymorphism and type checking
180
3.4.5
Polymorphism and late binding
181
3.4.6
Type Casting in C++
181
3.5
File Operations in C++.
183
3.5.1
File objects and operations in C++
183
3.5.2
Ignore operation in C++
186
3.6
Exception Handling.
187
*3.7
Parallel computing and multithreading.
191
3.7.1
Basic concepts in parallel
computing and multithreading
191
3.7.2
Generic features in C++
191
3.7.3
Case Study: Implementing
multithreading in C++
193
3.8
Summary.
196
3.9
Homework, programming exercises, and
projects.
199
Chapter 4
The Functional Programming
Language, Scheme.
209
4.1
From imperative programming to functional
programming.
210
4.2
Prefix notation.
212
4.3
Basic Scheme terminology.
214
4.4
Basic Scheme data types and functions.
217
4.4.1
Number types
217
4.4.2
Boolean
218
4.4.3
Character
219
4.4.4
String
220
4.4.5
Symbol
220
4.4.6
Pair
221
4.4.7
List
222
4.4.8
Application of Quotes
223
4.4.9
Definition of procedure and
procedure type
225
4.4.10
Input/output and nonfunctional features
226
*4.5
Lambda-calculus.
228
4.5.1
Lambda-expressions
228
4.5.2
l-procedure and parameter scope
229
4.5.3
Reduction rules
229
4.6
Define your Scheme procedures and macros.
231
4.6.1
Unnamed procedures
231
4.6.2
Named procedures
231
4.6.3
Scopes of variables and procedures
231
4.6.4
Let-form and unnamed procedures
233
4.6.5
Macros
234
4.6.6
Compare and contrast imperative and
functional programming paradigms
236
4.7
Recursive procedures.
238
4.8
Define recursive procedures on data types.
240
4.8.1
Number manipulations
240
4.8.2
Character and string manipulations
243
4.8.3
List manipulations
244
4.9
Higher-order functions.
246
4.9.1
Mapping
247
4.9.2
Reduction
248
4.9.3
Filtering
249
4.9.4
Application of filtering in query
languages
251
4.10
Summary.
252
4.11
Homework, programming exercises, and projects.
253
Chapter 5
The Logic Programming Language,
Prolog.
263
5.1
Basic concepts of logic programming in
Prolog.
263
5.1.1
Prolog basics
264
5.1.2
Structures of Prolog facts, rules,
and goals
266
5.2
The Prolog execution model
267
5.2.1
Unification of a goal
267
5.2.2
Example of searching through a
database
269
5.3
Arithmetic operations and database queries.
270
5.3.1
Arithmetic operations and built-in
functions
270
5.3.2
Combining database queries with
arithmetic operations
272
5.4
Prolog functions and recursive rules.
274
5.4.1
Parameter passing in Prolog
274
5.4.2
Factorial example
274
5.4.3
Fibonacci numbers example
275
5.4.4
Hanoi Towers
276
5.4.5
Graph model and processing
276
5.4.6
Map representation and coloring
278
5.5
List and list manipulation.
279
5.5.1
Definition of pairs and lists
279
5.5.2
Pair simplification rules
280
5.5.3
List membership and operations
281
5.5.4
Knapsack problem
284
5.5.5
Quick sort
285
5.6
Flow control structures.
287
5.6.1
Cut
287
5.6.2
Fail
290
5.6.3
Repeat
291
*5.7
Prolog application in semantic Web.
293
5.8
Summary.
294
5.9
Homework, programming exercises, and
projects.
297
Chapter 6
Fundamentals of the
Service-Oriented Computing Paradigm..
305
6.1
Introduction to C#.
305
6.1.1
Getting started with C# and Visual
Studio
305
6.1.2
Comparison between C++ and C#
307
6.1.3
Namespaces and the using directives
307
6.1.4
The queue example in C#
309
6.1.5
Class and object in C#
310
6.1.6
Parameters: passing by reference
with
ref&out
313
6.1.7
Base classes and constructors
314
6.1.8
Constructor, destructor, and
garbage collection
314
6.1.9
Pointers in C#
315
6.1.10
C# unified type system
316
6.1.11
Further topics in C#
317
6.2
Service-oriented computing paradigm..
317
6.2.1
Basic concepts and terminologies
318
6.2.2
Web services development
319
6.2.3
Service-oriented system engineering
320
6.2.4
Web services and enabling
technologies
321
6.3
*Service providers: programming Web
services in C#.
323
6.3.1
Creating a Web service project
324
6.3.2
Writing the service class
324
6.3.3
Launch and access your Web services
325
6.3.4
Automatically generating a WSDL
file
328
6.4
Publishing and searching Web services
using UDDI
329
6.4.1
UDDI file
329
6.4.2
ebXML
331
6.4.3
Ad hoc registry lists
332
6.5
Building applications using ASP.Net
332
6.5.1
Creating your own Web browser
333
6.5.2
Creating a Windows application
project in ASP.Net
334
6.5.3
Developing a Web site application
to consume Web services
339
6.6
Silverlight and Phone Applications
Development
342
6.6.1
Silverlight Applications
342
6.6.2
Developing Windows Phone Apps Using
Silverlight
345
6.7
Cloud computing and big data processing.
353
6.7.1
Cloud computing
353
6.7.2
Big data
356
6.8
Summary.
358
6.9
Homework, programming exercises, and
projects.
359
Appendix A
Basic Computer Architectures and
Assembly Language Programming.
365
A.1
Basic computer components and computer
architectures.
365
A.2
Computer architectures and assembly programming.
367
A.3
Subroutines and local variables on stack.
371
Appendix B
Programming Environments Supporting C, C++,
Scheme, and Prolog.
373
B.1
Introduction to Unix commands.
373
B.2
Programming environments supporting C, C++, and
C# programming.
377
B.2.1
Getting started with GNU GCC under the Unix operating system
377
B.2.2
Getting started with Visual Studio under the MS Windows operating system
377
B.2.3
Download C, C++, and C# programming development tools and environments
378
B.3
Programming environments supporting Scheme
programming.
378
B.3.1
Getting started with DrRacket
378
B.3.2
Download DrRacket programming environment
379
B.4
Programming environments supporting Prolog
programming.
380
B.4.1
Getting started with the GNU Prolog environment
380
B.4.2
Getting started with Prolog programming
381
B.4.3
Download Prolog programming development tools
383
Appendix C
ASCII Character Table.
385
Bibliography
389
Index
393
