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 Pascal, C, C++, or Java. The first edition of the book has been used at Arizona State University and many other universities around the world since its publication in 2003.

The most important addition to the second edition is 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 and potential to become a dominating programming paradigm in the near future. All major computing companies, including HP, IBM, Intel, Microsoft, Oracle, SAP, Sun Microsystems, have moved into this new paradigm and are using the new paradigm to produce software and even hardware systems. The needs of the skill in SOA programming increase as the deployments of SOA applications increases. The new paradigm has not only the importance in the programming practice, not also contribution to the concepts and principles in programming theory. In fact, SOA programming applies a higher level of abstraction, which requires less technical details for building large software applications. The authors of the 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 the text a new component to choose from, which adds flexibility for different courses to select different contents.

Furthermore, the existing chapters and sections in the first edition have been significantly improved, thanks to the feedbacks from the instructors who adopted the text and students who used the text in the past three years. Following new sections are added into the existing chapters,

2.5.5  Stack                                      

2.7     Recursive structures

3.5     Exception handling

4.6.6  Compare and contrast imperative and functional programming paradigms

5.8     Additional topics in Prolog

Following sections are revised significantly in the second edition:

2.4.5  Enumeration type

2.5.4  Linked list using dynamic memory allocation

2.5.6  File and file operations

2.6     Functions and parameter passing

2.8     Modular design

A.2    Computer architectures and assembly programming

The second edition of the text consists of six chapters. A half-semester course (25 to 30 lecture hours) can teach two to three chapters and a full semester course can teach four to five chanters of choice from the text. Chapter 3 (C++) is closely related to chapter 2. If chapter 3 is selected as a component, chapter 2, or a part of chapter 2, should be selected too. Other chapters are relatively independent 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).

Please contact the authors for instructional support at <text.cse240@asu.edu>. Available materials include lecture slides in PowerPoint format, sample tests, and the solutions to assignments and tests.

Yinong Chen

Wei-Tek Tsai

Table of Contents

Preface (Second Edition) ix
Preface (First Edition) 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 4
1.2 Structures of programming languages 7
1.2.1 Lexical structure 8
1.2.2 Syntactic structure 8
1.2.3 Contextual structure 8
1.2.4 Semantic structure 9
*1.2.5 BNF notation 9
1.2.6 Syntax graph 11
1.3 Data types and type checking 12
1.3.1 Data types and type equivalence 12
1.3.2 Type checking and type conversion 13
1.3.3 Orthogonality 14
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 21
1.5.1 Program development process 21
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++ 36
2.1 Getting started with C/C++ 37
2.1.1 Write your first C/C++ program 37
2.1.2 Basic input and output functions 38
2.1.3 Formatted input and output functions 39
2.2 Control structures in C/C++ 41
2.2.1 Operators and the order of evaluation 41
2.2.2 Basic selection structures (if-then-else and the conditional expression) 42
2.2.3 Multiple selection structure (switch) 43
2.2.4 Iteration structures (while, do-while and for) 46
2.3 Data and basic data types in C/C++ 48
2.3.1 Declaration of variables and functions 48
2.3.2 Scope rule 49
2.3.3 Basic data types 51
2.4 Complex types 53
2.4.1 Array 53
2.4.2 Pointer 56
2.4.3 String 59
2.4.4 Constants 65
2.4.5 Enumeration type 67
2.5 Compound data types 70
2.5.1 Structure types 70
2.5.2 Union 71
2.5.3 Array of structures using static memory allocation 72
2.5.4 Linked list using dynamic memory allocation 75
2.5.5 Stack 79
2.5.6 Files, standard input/output files, and file operations 82
2.6 Functions and parameter passing 90
2.7 Recursive structures 94
2.7.1 Loop structures versus recursive structures 95
2.7.2 The fantastic four abstract approach of writing recursive functions 96
2.7.3 Case study 1: the Tower of Hanoi 97
2.7.4 Case study 2: sorting an array 100
2.8 Modular design 103
2.9 Summary 105
2.10 Homework, programming exercises, and projects 105

Chapter 3 The Object-Oriented Programming Language, C++ 124
3.1 A long program example: a queue and a priority queue written in C++ 125
3.2 Class definition and composition 128
3.2.1 Class definition 128
3.2.2 Scope resolution operator 129
3.2.3 Objects from a class 130
3.2.4 Definition of constructor and destructor 130
3.3 Memory management and garbage collection 131
3.3.1 Static: global variables and static local variables 132
3.3.2 Runtime stack for local variables 133
3.3.3 Heap: dynamic memory allocation 136
3.3.4 Scope and garbage collection 136
3.4 Inheritance 140
3.4.1 Class containment and inheritance 140
3.4.2 Inheritance and hierarchy 143
3.4.3 Inheritance and polymorphism 158
3.4.4 Polymorphism and type checking 160
3.4.5 Polymorphism and late binding 161
3.5 Exception Handling 161
3.6 Summary 165
3.7 Homework, programming exercises, and projects 165

Chapter 4 The Functional Programming Language, Scheme 174
4.1 From imperative programming to functional programming 175
4.2 Prefix notation 177
4.3 Basic Scheme terminology 180
4.4 Basic Scheme data types and functions 183
4.4.1 Number 183
4.4.2 Boolean 184
4.4.3 Character 185
4.4.4 String 186
4.4.5 Symbol 187
4.4.6 Pair 187
4.4.7 List 189
4.4.8 Quotes 190
4.4.9 Definition of procedure and procedure type 191
4.4.10 Input/output and non-functional features 192
*4.5 Lambda-calculus 195
4.5.1 Lambda-expressions 195
4.5.2 -procedure and parameter scope 196
4.5.3 Reduction rules 196
4.6 Define your Scheme procedures and macros 198
4.6.1 Unnamed procedures 198
4.6.2 Named procedures 199
4.6.3 Scopes of variables and procedures 199
4.6.4 Let-form and unnamed procedure 201
4.6.5 Macros 202
4.6.6 Compare and Contrast Imperative and Functional Programming Paradigms 203
4.7 Recursive procedures 206
4.8 Define recursive procedures on data types 208
4.8.1 Number manipulations 208
4.8.2 Character and string manipulations 211
4.8.3 List manipulations 212
4.9 Higher order functions 213
4.9.1 Mapping 214
4.9.2 Filtering 215
4.10 Summary 216
4.11 Homework, programming exercises, and projects 217

Chapter 5 The Logic Programming Language, Prolog 226
5.1 A first look at Prolog 226
5.1.1 Brief background 226
5.1.2 Arity Prolog 227
5.1.3 A Prolog program 227
5.1.4 Putting Prolog to work by querying the database 229
5.2 Rules, structured data and the scope of variables 232
5.2.1 Rules and how they work 232
5.2.2 Structures 236
5.2.3 The scope of Prolog variables 239
5.3 Operators and functions 239
5.3.1 Operators 240
5.3.2 Arithmetic 241
5.3.3 Using the operators 243
5.4 Recursion and recursive rules 245
5.4.1 Recursion as a generalization of non-recursive rules 246
5.4.2 Suggestions for writing recursive rule sets 249
5.4.3 Finding factorial values 250
5.4.4 The Towers of Hanoi 251
5.5 Lists 253
5.5.1 Referencing lists 253
5.5.2 Examining the elements of a list 255
5.5.3 Forming new lists 259
5.5.4 Other list predicates 261
5.6 Input and output 261
5.6.1 Reading and writing 265
5.6.2 Database manipulation predicates 267
5.6.3 Input and output examples 268
5.6.4 File I/O 271
5.7 Program control and program design 272
5.7.1 Control program execution 273
5.7.2 Programming suggestions 278
5.8 Additional topics 279
5.8.1 Representing Prolog lists in pairs and writing recursive rules on lists 279
5.8.2 Flow control structures: cut and repeat 280
5.8.3 The Prolog execution model 285
5.9 Summary 287
5.10 Homework, programming exercises, and projects 288

Chapter 6 Fundamentals of Service-Oriented Computing Paradigm 296
6.1 Introduction to C# 296
6.1.1 Comparison between C++ and C# 296
6.1.2 Namespaces and the using directive 297
6.1.3 The queue example in C# 298
6.1.4 Class and object in C# 300
6.1.5 Parameters: passing by reference with ref & out 301
6.1.6 Base classes and constructors 302
6.1.7 Constructor, destructor, and garbage collection 302
6.1.8 Pointers in C# 303
6.1.9 C# unified type system 304
6.1.10 Further topics in C# 305
6.2 Service-oriented computing paradigm 305
6.2.1 Basic concepts and terminologies 306
6.2.2 Web services development 307
6.2.3 Service-oriented system engineering 309
6.2.4 Web services and enabling technologies 310
6.3 Service providers: programming Web services in C# and .Net 312
6.3.1 Creating a Web service project 313
6.3.2 Writing the service agent 314
6.3.3 Launch and access your Web services 315
6.3.4 Automatically generating WSDL file 318
6.4 Publishing and searching Web services using UDDI 320
6.5 Building application using ASP.Net 324
6.5.1 Creating a windows application project in ASP.Net 324
6.5.2 Creating and composing a Web application based on remote Web services 326
*6.6 Advanced topics in service-oriented software development 330
6.6.1 Simple model multiple analyses versus multiple models multiple analyses 330
6.6.2 Infrastructure embedded development framework 332
6.7 Homework, programming exercises, and projects 334

Appendix A Basic Computer Architectures and Assembly Language Programming 340
A.1 Basic computer components and computer architectures 340
A.2 Computer architectures and assembly programming 341
A.3 Subroutines and local variables on stack 347

Appendix B Programming Environments Supporting C, C++, Scheme, and Prolog 349
B.1 Introduction to Unix commands 349
B.2 Programming environments supporting C, C++, and C# programming 352
B.2.1 Getting started with GNU GCC under Unix operating system 352
B.2.2 Getting started with Visual Studio .Net 2005 under MS Windows operating system 353
B.2.3 Download C, C++, and C# programming development tools and environments 354
B.3 Programming environments supporting Scheme programming 354
B.3.1 Getting started with DrScheme 354
B.3.2 Download DrScheme programming environment 356
B.4 Programming environments supporting Prolog programming 356
B.4.1 Getting started with GNU Prolog 356
B.4.2 Download Prolog programming development tools 357

Appendix C ASCII Character Table 359
References 362
Index 365