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


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