Sixth Edition
We have witnessed the rapid development of computer science and software engineering, as well as their applications in many, if not all domains of our society, industry, manufactory, commerce, and business, particularly in web-based computing (Web 2.0), semantics web (Web 3.0), cloud computing, big data processing, artificial intelligence, and mobile computing. As a science and engineering discipline, the fundamentals of computer science and software engineering, including programming language principles and the classic programming languages, are stable and do not change with the technological innovations. C, C++, Scheme/LISP, Prolog, and Python 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 include generic classes and writing multithread programs. Functional programming principles are widely used in database query languages, and the newer languages C# and Python are extended from object-oriented programming languages to service-oriented programming languages.
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 at least one high-level programming language like C, C++, Python, or Java.
Most of the content presented in this 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, Johannesburg, and in the School of Computing, Informatics, and Decision Systems Engineering 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 and engineering 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, there are five major paradigms widely taught in computer science and computer engineering schools and in industry around the world: imperative, object-oriented, functional, logic programming, and service-oriented. The six languages we will study in the text are the imperative C, object-oriented C++, functional Scheme, logic Prolog, service-oriented C#, and multi-paradigm Python. 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, logic, and service-oriented programming language;
·
program processing (compilation versus interpretation) and preprocessing (macros and inlining); and
·
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 conjunction with the seven 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, and 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 paradigm 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;
·
apply imperative, object-oriented, and functional paradigms to write Python programs, particularly in the application of dynamic data types, flexible iterative structures, and dynamic list structure;
·
be able to write recursive subprograms/procedures in imperative, object-oriented, functional, and logic programming languages; and
·
be able to write programs requiring multiple subprograms/procedures to solve large programming problems in all the programming languages covered in the text.
The current edition of the text is organized into seven chapters and three appendices. Chapter 1 discusses the programming paradigms, principles, and common aspects of programming languages. Chapter 2 uses C as an example of the imperative programming paradigm to teach how to write imperative programs. Memory maps are emphasized throughout the chapter so students can better understand the data and states stored in memory. It is assumed in this chapter 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 imperative to object-oriented and 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 author: Service-Oriented Computing and System Integration.) Chapter 7 teaches the multi-paradigm programming language of Python. Python has become one of the most popular programming languages today due to its easiness in programming and abundant libraries in application areas, particularly in the area of artificial intelligence. Python supports multiple programming paradigms including imperative, object-oriented, service-oriented, and functional. It is a great example of teaching multiple paradigms in one programming language.
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, 5, 6, and 7 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 operating system concepts and commands. If the class uses a Unix-based laboratory environment, students can read the appendix to get started with Unix. The appendix then 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 seven chapters, which can be considered reconfigurable components of a course. A typical 3-credit hour course (42 lecture hours) will not be able to cover all the chapters and languages in this text. At Arizona State University, CSE220 (Programming for Computer Engineering) for the Computer System Engineering program covers Appendix B on the Unix operating system and GNU C/C++ programming, Chapter 1 on Basic Principles of Programming Languages, Chapter 2 on Imperative Programming Languages C/C++, and Object-Oriented Programming Language C++. CSE240 (Instruction to Programming Languages) for the Computer Science program covers Chapter 1, Chapter 2, Chapter 3, Chapter 4 on Functional Programming Language Scheme, and Chapter 5 on Logic Programming Language Prolog. We also use Chapter 6 on C# and Fundamentals of the Service-Oriented Computing Paradigm and Chapter 7 on Multi-Paradigm Programming Language Python for extracurricular activities, such as honors enrichment projects. Different schools can choose different chapters based on their program needs.
A half-semester course (24–30 lecture hours) could teach two to three chapters and a full semester course could 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); (Chapters 1, 7); (Chapter 1, 7, 5); or (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); (Chapters 1, 2, 3, 4, 7); or (Chapters 1, 2, 3, 5, 7).
This text has been revised and improved throughout in each of the new editions. In the second edition, the inclusion of programming in Service-Oriented Architecture (SOA) was the major change made. Since the publication of the first edition in 2003, SOA programming has emerged as a new programming paradigm and has demonstrated its strength to become a dominating programming paradigm. All major computing companies, including Amazon Web Services (AWS), HP, IBM, Intel, Microsoft, Oracle, and SAP, 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. I, the author of this book, am a leading researcher and educator in SOA programming, with over 100 publications in SOA domain. The inclusion of the new chapter on C# and SOA programming makes the text unique, allowing 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 two decades, 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, Chapter 5 was completely rewritten. 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) are also discussed. 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 was 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. Chapter 4 has been updated to match the changes made in DrRacket.
As parallel computing and multithreading became more and more important in software development, the third edition added a new section on parallel computing and multithreading in C++ in Chapter 3. A MapReduce example was used as a case study for explaining multithreading in C++. The parallel computing concept was also emphasized in Chapter 4, where the eager evaluation and higher functions Map and Reduce are linked to parallel computing.
In the fourth edition, a number of new sections and many examples throughout Chapters 1, 2, 3, 4, 5, and 6 were added for explaining the more difficult concepts. In Chapter 1, macro expansion and execution were explained in more detail and the order of executions were discussed and showed on different programming environments. More complex examples of syntax graphs were given in Section 1.2. In Chapter 2, structure padding was discussed in Section 2.5. The file operations in Section 2.6 were extended. More recursive examples were given in Section 2.7. A case study that puts all this together was given in a new section at the end of the chapter. In Chapter 3, a new subsection on memory leak detection was added in Section 3.3 on memory management. Section 3.4 on inheritance was extended with a new subsection on type casting. A new section on C++ file operations was added as Section 3.5. In Chapter 4, the application of filtering in query languages was added in Section 4.9. In the new editions, Chapter 5 was further extended to include web application in C#. The chapter also extended the discussions to cloud computing and big data processing.
In the fifth edition, changes and revisions were made throughout the book. In Chapter 2, more data structures were discussed, including doubly linked lists, graphs, and trees. Chapter 3, Object-Oriented Programming Language C++, was significantly extended to include inheritance, type casting, function overloading and operator overloading, and C++ file operations. A new section 3.8 Case Study was included to put together all the concepts and programming mechanisms learned in the chapter. In Appendix B, tutorials on using GNU GCC environment and Visual Studio environment to edit and debug programs were added.
In this sixth edition, changes and revisions are made throughout the book. However, the most significant change is the addition of Chapter 7 on Python. This chapter is written following the same style as the previous chapters. It discusses the paradigms first and uses the paradigms to explain the programming features and constructs. Many of the examples and projects in the previous chapters are re-implemented in this chapter in Python, so that this chapter is seamlessly integrated into the book and curriculum requirement. The chapter starts with installing the Python programming environment and very basic examples. Then it discuss all the fundamental issues of the language.
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 constructive 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.
This text was written and revised while I was carrying out a full university workload. I could not imagine that I would have been able to complete the task without the generous support of my family, who allowed me to use most of the weekends in the past year to write this text. For this, I am thankful.
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, this 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
. Instructors who use the text can contact the author for instructional support, including lecture slides in PowerPoint format and the solutions to assignments.
Yinong Chen
September 2019
Table of Contents
Preface xi
Chapter 1 Basic Principles of Programming Languages 1
1.1 Introduction 2
1.1.1 Programming concepts and paradigms 2
1.1.2 Program performance and features of programming languages 3
1.1.3 Development of programming languages 3
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 10
1.2.5 Error types at different levels 10
1.2.6 BNF notation 12
1.2.7 Syntax graph 13
1.3 Data types and type checking 15
1.3.1 Data types and type equivalence 15
1.3.2 Type checking and type conversion 16
1.3.3 Orthogonality 17
1.4 Program processing and preprocessing 19
1.4.1 Interpretation and compilation 19
1.4.2 Preprocessing: macro and inlining 20
*1.5 Program development 26
1.5.1 Program development process 26
1.5.2 Program testing 27
1.5.3 Correctness proof 30
1.6 Summary 32
1.7 Homework and programming exercises 33
Chapter 2 The Imperative Programming Languages, C/C++ 41
2.1 Getting started with C/C++ 42
2.1.1 Write your first C/C++ program 42
2.1.2 Basic input and output functions 43
2.1.3 Formatted input and output functions 45
2.2 Control structures in C/C++ 48
2.2.1 Operators and the order of evaluation 48
2.2.2 Basic selection structures (if-then-else and the conditional expression) 49
2.2.3 Multiple selection structure (switch) 50
2.2.4 Iteration structures (while, do-while, and for) 54
2.3 Data and basic data types in C/C++ 55
2.3.1 Declaration of variables and functions 56
2.3.2 Scope rule 57
2.3.3 Basic data types 58
2.4 Complex types 60
2.4.1 Array 60
2.4.2 Pointer 64
2.4.3 Array and String 67
2.4.4 Constants 76
2.4.5 Enumeration type 78
2.5 Compound data types 80
2.5.1 Structure types and paddings 80
2.5.2 Union 83
2.5.3 Array of structures using static memory allocation 85
2.5.4 Linked list using dynamic memory allocation 87
2.5.5 Doubly linked list 92
2.5.6 Stack 94
2.6 Standard input and output, files, and file operations 96
2.6.1 Basic concepts of files and file operations 96
2.6.2 File operations in C 97
2.6.3 Flush operation in C 105
2.7 Functions and parameter passing 106
2.7.1 Call-by-value 107
2.7.2 Call-by-address 108
2.7.3 Call-by-alias 110
2.7.4 Passing a structure into a function 111
2.7.5 Passing an array into a function 115
2.8 Recursive structures and applications 117
2.8.1 Loop structures versus recursive structures 117
2.8.2 The fantastic-four abstract approach of writing recursive functions 118
2.8.3 Hanoi Towers 120
2.8.4 Insertion sorting 123
2.8.5 Merge sort algorithm 125
2.8.6 Quick sort algorithm 126
2.8.7 Tree operations 127
2.8.8 Gray code generation 131
2.9 Modular design 133
2.10 Case Study: Putting All Together 135
2.11 Summary 142
2.12 Homework, programming exercises, and projects 145
Chapter 3 The Object-Oriented Programming Language, C++ 165
3.1 A long program example: a queue and a priority queue written in C++ 166
3.2 Class definition and composition 169
3.2.1 Class definition 169
3.2.2 Scope resolution operator 171
3.2.3 Objects from a class 172
3.2.4 Definition of constructor and destructor 172
3.3 Memory management and garbage collection 173
3.3.1 Static: global variables and static local variables 174
3.3.2 Runtime stack for local variables 175
3.3.3 Heap: dynamic memory allocation 177
3.3.4 Scope and garbage collection 178
3.3.5 Memory leak detection 183
3.4 Inheritance 190
3.4.1 Class containment and inheritance 190
3.4.2 Inheritance and virtual function 193
3.4.3 Inheritance and hierarchy 196
3.4.4 Inheritance and polymorphism 210
3.4.5 Polymorphism and type checking 212
3.4.6 Polymorphism and late binding 213
3.4.7 Type Casting in C++ 213
3.5 Function and operator overloading 215
3.5.1 Function overloading 215
3.5.2 Operator overloading 216
3.6 File operations in C++ 223
3.6.1 File objects and operations in C++ 223
3.6.2 Ignore operation in C++ 227
3.7 Exception Handling 229
3.8 Case dtudy: putting all together 232
3.8.1 Organization of the program 232
3.8.2 Header files 233
3.8.3 Source files 235
*3.9 Parallel computing and multithreading 243
3.9.1 Basic concepts in parallel computing and multithreading 243
3.9.2 Generic features in C++ 244
3.9.3 Case Study: Implementing multithreading in C++ 245
3.10 Summary 249
3.11 Homework, programming exercises, and projects 251
Chapter 4 The Functional Programming Language, Scheme 261
4.1 From imperative programming to functional programming 262
4.2 Prefix notation 264
4.3 Basic Scheme terminology 266
4.4 Basic Scheme data types and functions 269
4.4.1 Number types 269
4.4.2 Boolean 270
4.4.3 Character 271
4.4.4 String 272
4.4.5 Symbol 272
4.4.6 Pair 272
4.4.7 List 274
4.4.8 Application of Quotes 275
4.4.9 Definition of procedure and procedure type 277
4.4.10 Input/output and nonfunctional features 278
*4.5 Lambda-calculus 280
4.5.1 Lambda-expressions 281
4.5.2 Lambda-procedure and parameter scope 281
4.5.3 Reduction rules 282
4.6 Define your Scheme procedures and macros 283
4.6.1 Unnamed procedures 283
4.6.2 Named procedures 283
4.6.3 Scopes of variables and procedures 284
4.6.4 Let-form and unnamed procedures 286
4.6.5 Macros 287
4.6.6 Compare and contrast imperative and functional programming paradigms 288
4.7 Recursive procedures 291
4.8 Define recursive procedures on data types 293
4.8.1 Number manipulations 293
4.8.2 Character and string manipulations 296
4.8.3 List manipulations 298
4.9 Higher-order functions 300
4.9.1 Mapping 300
4.9.2 Reduction 304
4.9.3 Filtering 304
4.9.4 Application of filtering in query languages 306
4.10 Summary 308
4.11 Homework, programming exercises, and projects 309
Chapter 5 The Logic Programming Language, Prolog 319
5.1 Basic concepts of logic programming in Prolog 319
5.1.1 Prolog basics 320
5.1.2 Structures of Prolog facts, rules, and goals 322
5.2 The Prolog execution model 323
5.2.1 Unification of a goal 324
5.2.2 Example of searching through a database 325
5.3 Arithmetic operations and database queries 326
5.3.1 Arithmetic operations and built-in functions 326
5.3.2 Combining database queries with arithmetic operations 328
5.4 Prolog functions and recursive rules 330
5.4.1 Parameter passing in Prolog 330
5.4.2 Factorial example 331
5.4.3 Fibonacci numbers example 331
5.4.4 Hanoi Towers 332
5.4.5 Graph model and processing 333
5.4.6 Map representation and coloring 334
5.5 List and list manipulation 336
5.5.1 Definition of pairs and lists 336
5.5.2 Pair simplification rules 337
5.5.3 List membership and operations 338
5.5.4 Knapsack problem 341
5.5.5 Quick sort 342
5.6 Flow control structures 344
5.6.1 Cut 344
5.6.2 Fail 347
5.6.3 Repeat 348
*5.7 Prolog application in semantic Web 350
5.8 Summary 351
5.9 Homework, programming exercises, and projects 353
Chapter 6 Fundamentals of the Service-Oriented Computing Paradigm 361
6.1 Programming in C# 361
6.1.1 Getting started with C# and Visual Studio 361
6.1.2 Comparison between C++ and C# 363
6.1.3 Namespaces and the using directives 363
6.1.4 The queue example in C# 365
6.1.5 Class and object in C# 366
6.1.6 Parameters: passing by reference with ref&out 369
6.1.7 Base classes and constructors 370
6.1.8 Constructor, destructor, and garbage collection 370
6.1.9 Pointers in C# 371
6.1.10 C# unified type system 372
6.1.11 Further topics in C# 373
6.2 Service-oriented computing paradigm 373
6.2.1 Basic concepts and terminologies 373
6.2.2 Web services development 375
6.2.3 Service-oriented system engineering 376
6.2.4 Web services and enabling technologies 377
6.3 *Service providers: programming web services in C# 378
6.3.1 Creating a web service project 379
6.3.2 Writing the service class 380
6.3.3 Launch and access your web services 381
6.3.4 Automatically generating a WSDL file 383
6.4 Publishing and searching web services using UDDI 385
6.4.1 UDDI file 385
6.4.2 ebXML 387
6.4.3 Ad hoc registry lists 388
6.5 Building applications using ASP.Net 388
6.5.1 Creating your own web browser 388
6.5.2 Creating a Windows application project in ASP.Net 389
6.5.3 Developing a website application to consume web services 394
6.6 Cloud computing and big data processing 397
6.6.1 Cloud computing 397
6.6.2 Big data 400
6.8 Summary 402
6.9 Homework, programming exercises, and projects 405
Chapter 7 The Multi-Paradigm Programming Language, Python 411
7.1 Introduction to Python 412
7.2 A quick start with Python 413
7.2.1 Install Python and run the first program 413
7.2.2 Install and use Python IDE 414
7.2.3 Python programming in Unix/Linux GNU IDE 415
7.2.4 Python programming in Visual Studio IDE 416
7.3 Python fundamentals 417
7.3.1 Variables, basic types, and functions 417
7.3.2 Control structures: conditional and loop statements 419
7.3.3 Recursive functions 422
7.3.4 Lambda expressions and functions 423
7.3.5 Higher-order functions: map, reduce, and filter 425
7.4 Python complex types and data structures 427
7.4.1 String and character 427
7.4.2 Array and list 431
7.4.3 Two-dimensional list 435
7.4.4 Dictionaries, sets, and tuples 439
7.5 Python class and inheritance 442
7.5.1 Class and object 442
7.5.2 Inheritance and case study 446
7.6 Input, output, and files 459
7.6.1 Input and output 459
7.6.2 File operations 461
7.6.3 Exception handling 462
7.6.4 Case study: putting all together 463
7.7 Summary 471
7.8 Homework and programming exercises 473
Appendix A Basic Computer Architectures and Assembly Language Programming 479
A.1 Basic computer components and computer architectures 479
A.2 Computer architectures and assembly programming 481
A.3 Subroutines and local variables on stack 485
Appendix B Programming Environments Supporting C, C++, Scheme, and Prolog 487
B.1 Introduction to operating systems 487
B.2 Introduction to Unix and GNU C/C++ programming environments 490
B.2.1 Unix and Linux operating systems 490
B.2.2 Unix shell and commands 491
B.2.3 Unix system calls 496
B.2.4 Getting started with GNU GCC under the Unix operating system 499
B.2.5 Debugging your C/C++ programs in GNU GCC 501
B.2.6 Frequently used GCC compiler options 504
B.2.7 C/C++ operators 504
B.2.8 Download programming development environments and tutorials 506
B.3 Getting started with Visual Studio programming environment 506
B.3.1 Creating a C/C++ project in Visual Studio 506
B.3.2 Debugging your C/C++ programs in Visual Studio 509
B.4 Programming environments supporting Scheme programming 510
B.4.1 Getting started with DrRacket 510
B.4.2 Download DrRacket programming environment 511
B.5 Programming environments supporting Prolog programming 512
B.5.1 Getting started with the GNU Prolog environment 512
B.5.2 Getting started with Prolog programming 513
B.5.3 Download Prolog programming development tools 515
Appendix C ASCII Character Table 517
Bibliography 519
Index 523
