by Joseph Weizenbaum Since the dawn of the age of computers, people have cursed the difficulty of programming. Over and over again we encounter the suggestion that we should be able to communicate to a computer in natural language what we want it to do. Unfortunately, such advice rests upon a misconception of both the computer and its task. The computer might not be stupid, but it is stubborn. That is, the computer does what all the details of its pro- gram command it to do, i. e. , what the programmer "tells" it to do. And this can be quite different from what the programmer intended. The misun- derstanding with respect to tasks posed to the computer arises from the failure to recognize that such tasks can scarcely be expressed in natural language, if indeed at all. For example, can we practice music, chemistry or mathematics without their respective special symbolic languages? Yet books about computers and programming languages can be written more or less reasonably, even if they are not quite poetic or lyrical. This book can serve as an example of this art and as a model for anyone at- tempting to teach inherently difficult subject matters to others. Klagenfurt, April 1995 Preface Striving to make learning to program easier, this book addresses primarily students beginning a computer science major. For our program examples, we employ a new, elegant programming language, Modula-3.

Table of Contents:
1 What is programming?.- 1.1 An informal introduction.- 1.1.1 Algorithms.- 1.1.2 Switches and Symbols.- 1.1.3 Turing machine.- 1.1.4 Computability.- 1.2 The von Neumann Computer.- 1.3 Rigid thought structures.- 1.4 Programming in the small.- 1.4.1 Software production methods.- 1.4.2 Writing simple programs.- 1.5 Levels of programming.- 1.5.1 Formal and human languages.- 1.5.2 Assembler.- 1.5.3 High-level programming languages.- 1.6 Programming and Computer science.- 1.6.1 The responsibility of Computer scientists.- 2 Metalanguages.- 2.1 Definition of formal languages.- 2.2 Digits and numbers.- 2.3 Names.- 2.4 Arithmetic expressions.- 2.5 Extension for Modula-3 syntax.- 3 The structure of programs.- 3.1 Structuring.- 3.2 Language environment.- 3.3 The statics and dynamics of a program.- 3.3.1 Data and data types.- 3.3.2 Algorithms and procedures.- 3.4 Structure of Modula-3 programs.- 3.4.1 Themodule.- 3.4.2 Hello, world.- 3.4.3 Source code.- 3.4.4 Computing the arithmetic mean.- 3.4.5 SIO interface.- 4 Predefined data types.- 4.1 Integers.- 4.1.1 Range.- 4.1.2 Operations.- 4.2 Logical type.- 4.2.1 Range.- 4.2.2 Operations.- 4.3 Characters.- 4.3.1 Range.- 4.3.2 Operations.- 4.4 Texts.- 4.4.1 Range.- 4.4.2 Operations.- 4.5 Floating-point numbers.- 4.5.1 Range.- 4.5.2 Floating-point literals.- 4.5.3 Operations.- 4.5.4 Input and Output of floating-point numbers.- 5 Statements.- 5.1 The assignment.- 5.2 Structured Statements.- 5.3 Sequence.- 5.4 Branches.- 5.4.1 If statement.- 5.4.2 Case statement.- 5.4.3 Equivalence of If and Case.- 5.5 Loops.- 5.5.1 Whileloop.- 5.5.2 Loop invariants.- 5.5.3 Repeat loop.- 5.5.4 For loop.- 5.5.5 Loop statement.- 5.5.6 Equivalence of the repetition statements.- 6 User-defined simple types.- 6.1 Enumeration.- 6.1.1 Predefined enumerations.- 6.1.2 Range.- 6.1.3 Operations.- 6.2 Subranges.- 6.2.1 Operations.- 6.2.2 Predefined subranges.- 7 Expressions and declarations.- 7.1 Expressions.- 7.1.1 Syntax of expressions.- 7.1.2 Evaluation of expressions.- 7.1.3 Evaluation of logical expressions.- 7.2 Declarations.- 7.2.1 Constant declarations.- 7.2.2 Type declarations.- 7.2.3 Variable declarations.- 7.3 Equivalence of types.- 7.4 Subtypes.- 7.5 Assignment compatibility.- 7.6 Expression compatibility.- 8 Composite static types.- 8.1 Arrays.- 8.1.1 Unidimensional arrays.- 8.1.2 Multidimensional arrays.- 8.1.3 Array constructors.- 8.1.4 Operations on arrays.- 8.1.5 Example: Schedule.- 8.1.6 Linear search in an array.- 8.1.7 Sorting an array.- 8.2 Records.- 8.2.1 Record selectors.- 8.2.2 Record constructors.- 8.2.3 Operations with records.- 8.2.4 With Statement.- 8.2.5 Example: Student data management.- 8.3 Sets.- 8.3.1 Range.- 8.3.2 Set constructors.- 8.3.3 Operations on sets.- 8.3.4 Example: Input of numbers.- 8.4 Comparison of arrays, records and sets.- 8.5 Packed data types.- 9 Structuring algorithms.- 9.1 Block structure.- 9.2 Procedures and functions.- 9.2.1 Procedure declaration.- 9.2.2 Procedure invocation.- 9.3 Modes of parameter passing.- 9.3.1 Value parameter.- 9.3.2 Variable parameters.- 9.3.3 Read-only parameters.- 9.3.4 Information transfer via global variables.- 9.3.5 Comparing the kinds of parameters.- 9.4 Identifying the procedures.- 9.5 Name, type and default value of a parameter.- 9.6 Eval statement.- 9.7 Procedure types.- 9.7.1 Operations with procedures.- 10 Modules.- 10.1 Structure.- 10.1.1 Interface.- 10.1.2 Implementation.- 10.1.3 Compilation units.- 10.2 Using modules.- 10.2.1 Structuring the data space.- 10.2.2 Type creation.- 10.2.3 Creating toolboxes.- 10.3 An example with graphic elements.- 10.4 Modularization.- 11 Dynamic data structures.- 11.1 Dynamism in static data structures.- 11.1.1 Implementation of Stacks as arrays.- 11.1.2 FIFO queues in arrays.- 11.1.3 Example: Rotating shifts.- 11.1.4 Explicit address management with pointers.- 11.1.5 Address management by the System.- 11.2 Dynamic data in Modula-3.- 11.2.1 Allocation and deallocation.- 11.2.2 Operations with references.- 11.2.3 Open (dynamic) arrays.- 11.2.4 Arrays of references.- 11.3 Subtypes.- 11.3.1 Subtype rule for references.- 11.3.2 Subtype rule for arrays.- 11.4 Abstract and encapsulated data types.- 11.4.1 Opaque data types.- 11.4.2 Revelation.- 11.4.3 An abstract and a generic stack.- 11.4.4 Rules for the design of encapsulated data types.- 11.5 Dynamic structures.- 11.5.1 Lists.- 11.5.2 Kinds of lists.- 11.5.3 Singly linked, sorted linear list.- 12 Recursion.- 12.1 Recursive algorithms.- 12.1.1 Fundamentals of recursive programming.- 12.1.2 Using recursion.- 12.1.3 Quicksort.- 12.1.4 The Towers of Hanoi.- 12.1.5 Recursive list management.- 12.2 Recursive data structures.- 12.2.1 Trees.- 12.2.2 Binary trees and search trees.- 12.2.3 Binary search trees.- 12.2.4 Traversing a tree.- 12.2.5 Implementation of the binary search tree.- 13 Objects.- 13.1 Object-oriented modeling.- 13.2 Object-oriented programming.- 13.2.1 Encapsulation.- 13.2.2 Inheritance.- 13.2.3 Polymorphism.- 13.2.4 Dynamic binding.- 13.2.5 Object-oriented applications.- 13.3 Object types in Modula-3.- 13.3.1 Declaration of object types.- 13.3.2 Implementation of objects.- 13.3.3 Implementation of methods.- 13.3.4 Accessing object components.- 13.3.5 Creating objects.- 13.3.6 Subtyping rules for objects.- 13.4 Encapsulation of object types.- 13.4.1 Inheritance.- 13.4.2 Polymorphism and dynamic binding.- 13.4.3 Generalization.- 13.4.4 The tree class hierarchy.- 13.4.5 Subclasses of binary trees.- 14 Persistent data structures.- 14.1 Files.- 14.1.1 Accessing files.- 14.1.2 Access functions.- 14.1.3 Files and main memory.- 14.1.4 File types.- 14.2 Files in Modula-3.- 14.2.1 Input and Output streams.- 14.2.2 Fmt and Scan.- 14.2.3 Simple-IO.- 14.3 Persistent variables.- 14.3.1 Implementation.- 15 Exception handling.- 15.1 Exceptions in a program.- 15.2 Exception handling in Modula-3.- 15.2.1 Exceptions, run-time errors, programming errors.- 15.2.2 Declaration of exceptions.- 15.2.3 Generation of exceptions.- 15.2.4 Exception handling.- 15.2.5 Delegating exceptions.- 15.3 Delaying exception handling.- 15.4 Strategies for exception handling.- 16 Parallel programming.- 16.1 Motivation for parallelism.- 16.2 Parallel programs.- 16.3 Threads in Modula-3.- 16.3.1 Schedulers of Modula-3 environments.- 16.3.2 Creating threads.- 16.4 Shared variables.- 16.4.1 Data-parallel algorithms.- 16.4.2 Critical regions and mutual exclusion.- 16.4.3 Type Mutex and the Lock statement.- 16.4.4 Monitor.- 16.4.5 Semaphores.- 16.5 Message passing.- 16.5.1 Client/server model.- 16.5.2 Synchronous message communication.- 16.5.3 Asynchronous message communication.- 16.5.4 Channels.- A small database.- B Language Definition.- C Library interfaces.- D Modula-3 language environments.