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. Most parts of the contents presented in the text have 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 Department at Arizona State University. Being 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 experiences 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.
By 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 is organized into five chapters and three appendices. Chapter one discusses the programming paradigms, principles, and common aspects of programming languages. Chapter two uses C as the example of the imperative programming paradigm to teach how to write imperative programs. It is assumed that the students have basic understanding of a high-level programming language such as Pascal, C, C++, or Java. Chapter three extends the discussion and programming from C to C++. The chapter focuses on the main features of object-oriented programming paradigms, including class composition, inheritance, dynamic memory allocation and deallocation, late binding, polymorphism, and class hierarchy. Chapters four and five take a major paradigm shift to teach functional and logic programming, respectively. Students are not required to have any knowledge in functional and logic programming to learn from these two chapters. Assignments, programming exercises, and projects are given at the end of each chapter. The three appendices provide supplementary materials to the main text. In Appendix A, the basic computer architecture and assembly language programming are introduced. If students do not have basic computer science background, the material should be covered in the class. Appendix B first introduces 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. Appendix C gives the ASCII code table that is referred in various parts of the text. In the main text, the sections with an asterisk mark are optional and can be skipped if time does not permit to cover all the material. Chapters four and five are self-contained and can be taught independently, or in a different order.
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 used in this text. Thomas Boyd, Joe DeLibero, and Renee Turban of Arizona State University reviewed the final draft of the text and made constructive suggestions and useful comments. My teaching assistants Ibraz Mohammed, Jianchun Fan, Harish Bashettihalli, and Rajanikanth Mitta, helped me in the past few years prepare the assignments and programming exercises.
Raynette Brodie,
the student consultant for Microsoft at Arizona State University, contributed
the section "From C++ to C#" and the C# related materials in other sections.
Peter Hallam, C# developer at Microsoft, made very useful comments on C#
related topics. The major part of chapter five, sections 5.1 through 5.7, was reprinted (arranged by the publisher) from Tom Hankins and Thom Luce's book Prolog Minimanual.
I also would like to thank the editoral team, Jay Hays, Billee Jo Hefel, and Lynne Rogers at Kendall/Hunt Publishing. Jay pushed me into the position to write the text, Billee Jo checked my progress constantly that made me finally meet the deadline, and Lynne completed the production process.
The text was written while I was carrying out a full university workload. I am thankful to my family, Wei, George, and Jane. 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 <text.cse240@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
Table of Contents Preface
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 6
1.2.1 Lexical Structure 6
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 10
1.3.1 Data Types and Type Equivalence 11
1.3.2 Type Checking and Type Conversion 11
1.3.3 Orthogonality 12
1.4 Program Processing and Preprocessing 14
1.4.1 Interpretation and Compilation 15
1.4.2 Preprocessing: Macro and Inlining 16
*1.5 Program Development 19
1.5.1 Program Development Process 20
1.5.2 Program Testing 20
1.5.3 Correctness Proof 23
1.6 Summary 25
1.7 Homework and Programming Exercises 27
The Imperative Programming Languages, C/C++ 37
2.1 Getting Started with C/C++ 38
2.1.1 Write Your First C/C++ Program 38
2.1.2 Basic Input and Output Functions 39
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 42
2.2.2 Basic Selection Structures (if-then-else and the conditional expression) 43
2.2.3 Multiple Selection Structure (switch) 44
2.2.4 Iteration Structures (while, do-while and for) 47
2.3 Data and Basic Data Types in C/C++ 48
2.3.1 Declaration of Variables and Functions 49
2.3.2 Scope Rule 50
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 58
2.4.4 Constants 64
2.4.5 Enumeration Type 65
2.5 Compound Data Types 68
2.5.1 Structure Types 68
2.5.2 Union 69
2.5.3 Collection of Structures Using Static Memory Allocation 70
2.5.4 Collection of Structures Using Dynamic Memory Allocation 73
2.5.5 File and File Operations 76
2.6 Functions and Parameter Passing 81
2.7 Modular Design 84
2.8 Summary 85
2.9 Homework, Programming Exercises, and Projects 87
The Object-Oriented Programming Language, C++ 109
3.1 A Long Program Example: A Queue and a Priority Queue Written in C++ 110
3.2 Class Definition and Composition 113
3.2.1 Class Definition 113
3.2.2 Scope Resolution Operator 114
3.2.3 Objects From a Class 114
3.2.4 Definition of Constructor and Destructor 115
3.3 Memory Management and Garbage Collection 116
3.3.1 Static: Global Variables and Static Local Variables 117
3.3.2 Runtime Stack for Local Variables 118
3.3.3 Heap: Dynamic Memory Allocation 120
3.3.4 Scope and Garbage Collection 120
3.4 Inheritance 124
3.4.1 Class Containment and Inheritance 124
3.4.2 Inheritance and Hierarchy 127
3.4.3 Inheritance and Polymorphism 142
3.4.4 Polymorphism and Type Checking 144
3.4.5 Polymorphism and Late Binding 144
*3.5 From C++ to C# 145
3.5.1 Namespaces and The Using Directive 145
3.5.2 The Queue Example in C# 146
3.5.3 Class and Object in C# 147
3.5.4 Parameters: Passing by Reference with ref & out 148
3.5.5 Base Classes and Constructors 149
3.5.6 Constructor, Destructor, and Garbage Collection 149
3.5.7 Pointers in C# 150
3.5.8 C# Unified Type System 151
3.5.9 Further Topics in C# 152
3.6 Summary 153
3.7 Homework, Programming Exercises, and Projects 155
The Functional Programming Language, Scheme 161
4.1 From Imperative Programming to Functional Programming 162
4.2 Prefix Notation 164
4.3 Basic Scheme Terminology 167
4.4 Basic Scheme Data Types and Functions 169
4.4.1 Number 169
4.4.2 Boolean 170
4.4.3 Character 171
4.4.4 String 172
4.4.5 Symbol 173
4.4.6 Pair 173
4.4.7 List 174
4.4.8 Quotes 175
4.4.9 Definition of Procedure and Procedure Type 176
4.4.10 Input/Output and Non-functional Features 178
*4.5 Lambda-Calculus 180
4.5.1 Lambda l-Expressions 181
4.5.2 l-procedure and Parameter Scope 181
4.5.3 Reduction Rules 182
4.6 Define your Scheme Procedures and Macros 183
4.6.1 Unnamed Procedures 183
4.6.2 Named Procedures 184
4.6.3 Scopes of Variables and Procedures 184
4.6.4 Let-form and Unnamed Procedure 186
4.6.5 Macros 187
4.7 Structure of Recursive Procedures 188
4.7.1 Control Structure of Recursive Procedures 188
4.7.2 Simple Steps of Writing Recursive Procedures 190
4.7.3 Case Study: Solving Hanoi Tower Problem 191
4.8 Define Recursive Procedures on Data Types 194
4.8.1 Number Manipulations 194
4.8.2 Character and String Manipulations 197
4.8.3 List Manipulations 198
4.9 Higher Order Functions 199
4.9.1 Mapping 199
4.9.2 Filtering 201
4.10 Summary 202
4.11 Homework, Programming Exercises, and Projects 203
The Logic Programming Language, Prolog 219
5.1 A First Look at Prolog 219
5.1.1 Brief Background 219
5.1.2 Arity Prolog 220
5.1.3 A Prolog Program 220
5.1.4 Putting Prolog to Work by Querying the Database 222
5.2 Rules, Structured Data and The Scope of Variables 225
5.2.1 Rules and How They Work 225
5.2.2 Structures 228
5.2.3 The Scope of Prolog Variables 231
5.3 Operators and Functions 231
5.3.1 Operators 232
5.3.2 Arithmetic 234
5.3.3 Using the Operators 235
5.4 Recursion and Recursive Rules 238
5.4.1 Recursion as a Generalization of Non-Recursive Rules 239
5.4.2 Suggestions for Writing Recursive Rule Sets 242
5.4.3 Finding Factorial Values 242
5.4.4 The Towers of Hanoi 244
5.5 Lists 245
5.5.1 Referencing Lists 245
5.5.2 Examining The Elements of a List 248
5.5.3 Forming New Lists 251
5.5.4 Other List Predicates 253
5.6 Input and Output 254
5.6.1 Reading and Writing 258
5.6.2 Database Manipulation Predicates 260
5.6.3 Input and Output Examples 261
5.6.4 File I/O 263
5.7 Program Control and Program Design 264
5.7.1 Control Program Execution 265
5.7.2 Programming Suggestions 269
5.8 Homework, Programming Exercises, and Projects 271
Appendix A Basic Computer Architectures and Assembly Language Programming 281
A.1 Basic Computer Components and Computer Architectures 281
A.2 Computer Architectures and Assembly Programming 282
A.3 Subroutines and Local Variables on Stack 286
Appendix B Programming Environments Supporting C, C++, Scheme, and Prolog
B.1 Introduction to Unix Commands 289
B.2 Programming Environments Supporting C, C++, and C# Programming 292
B.2.1 Getting Started with GNU GCC under Unix Operating System 292
B.2.2 Getting Started with Visual Studio C++ under MS Windows Operating System 293
B.2.3 Getting Started with Visual Studio .Net under MS Windows Operating System
B.2.4 Download C, C++, and C# Programming Development Tools 294
B.3 Programming Environments Supporting Scheme Programming 294
B.3.1 Getting Started with DrScheme 294
B.3.2 Download DrScheme Programming Environment 295
B.4 Programming Environments Supporting Prolog Programming 295
B.4.1 Getting Started with GNU Prolog 295
B.4.2 Download Prolog Programming Development Tools 296
Appendix C ASCII Character Table 299
References 303
Index 305
