Fifth 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 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