Introduction to Computer Science

✍ Scribed by Alan J. Perlis

• Publisher: Harper & Row
• Year: 1975
• Tongue: English
• Leaves: 408
• Category: Library

✦ Synopsis

Programming has become a highly useful skill. Many students choose a first course in computer science merely to acquire the ability to use a programming language. However, programming involves much more than language skill. We do not program the content of ordinary human discourse; we program methods of solving problems, and we express these programs in logical and symbolic form. We do so because there is no other way to get computing machines to execute the programs. Thus, language skill is necessary but not sufficient for mastering the use of computers. Precise expression of symbolic concepts stated in a programming language is required. Although the arsenal of mathematical theory used in this book does not go beyond high-school level mathematics, students must develop a willingness to absorb notations and to express relations in symbolic form.

Learning a language is important. However, the choice of language is less important. In acquiring a competence in one language, students must see that they are developing the ability to acquire competence in computer languages in general. Learning about language, programming, and the computer should make us aware of the shifting and shadowy boundaries between them. Technology dictates how this boundary shifts; education prepares us for the eventuality of the shift.

A university course in computer science has several goals which this book attempts to achieve:

1. To give students practice in expressing problem-solving methods in the form of executable computer programs.

2. To give students an appreciation of the computer: its logical simplicity, its ingenious structural complexity, and its awesome potential.

3. To give students experience in the use of programming languages.

4. To give students an appreciation of programming systems, not so much as they are encountered during use of the computer, but as they are shaped and built for the students’ own purposes.

5. To give students some contact with the emerging theory of computation.

Some readers may question the use of Algol60 and APL as the programming languages in this text. Certainly they are neither the most popular nor the most advanced. They are, however, enormously influential in shaping trends, and an understanding of them makes the more popular and newer languages simpler to understand and master.

For most college students this text aims to support their first and only course in computer science. Computers play a part in all of our lives. Education reveals that the computer’s role is shaped by people and not by the machine itself. In all probability, computers ultimately will become as common-place as the ubiquitous electric motor. This is as it should be. In our world the computer is a basic tool that we reach for at progressively earlier stages, in our search for solutions to our pressing societal, scientific, and personal problems. Thus, it is my conviction that an introduction to computer science must be significantly more than mere drill in the use of a popular programming language.

✦ Table of Contents

Cover
Half title
Imprint
Contents
Preface
1 ALGORITHMS
Introduction
Algorithms
Representation of Algorithms
Two Paradigms of Programming: Backtracking and Recursion
Recursion
Summary
References
Problems
2 STANDARD FORMS
Introduction
Linearization of a Flowchart
Simplification
Arithmetization 1
Arithmetization 2
Computer Arithmetic
Computer-Instruction Repertoire in Register Terms
Microprogramming and Instruction Execution
Logical-Element Description
History of Electronic Computers
The Invention and Improvement of Equipment
The Enlargement of Function
The Growth of an Industry
References
Problems
3 LANGUAGES
Introduction
The Properties of Programming Languages
Grammar FCI
Grammar FC2
Grammar FC3
Grammar FCP1
Grammar FCP2
Algol60
Grammar BEX
Notes
Algol60: Scope and Context
Algol60: Procedures
How Does One Learn a Programming Language?
FORTRAN
The APL Language
APL Operators
APL Procedures
A Brief Survey of Programming Languages
COBOL: Common Business-Oriented Language
FORTRAN: Formula-Translation Language
BASIC: Beginners’ All-Purpose Symbolic Instruction Code
Algol60: Algorithmic Language
PL/I: “Programming Language I”
Algol68
SNOBOL
LISP
APL: A Programming Language
Assembly Language
References
Problems
Algol60 Problems
APL Exercises
General Programs in Which Algol60 or apL May Be Used
BNF Problems
4 DATA STRUCTURES
Introduction
Strings
Trees and List Structures
Applications of Trees
Queues
Searching Linear Lists
Sorting: An Application of Trees
Summary and References
Problems
5 SYSTEMS
Overview
The APL System
An Example: The Markov Algorithm Translator
Error-Processing
Summary and References
Problems
6 THEORY
Noncomputable Functions
Program Correctness
Termination of Algorithms
Summary and References
Problems
Index