Structure And Interpretation Of Programs
Some notes from my reading of Harold Abelson’s EXCELLENT lecture in the famous MIT course Structure and Interpretation of Computer Programs.
The subject matter … involves us with three foci of phenomena: the human mind, collections of computer programs, and the computer. Every computer program is a model, hatched in the mind, of a real or mental process. ese processes, arising from human experience and thought, are huge in number, intricate in detail, and at any time only partially understood. ey are modeled to our permanent satisfaction rarely by our computer programs. Thus even though our programs are carefully handcraed discrete collections ofsymbols, mosaics of interlocking functions, they continually evolve: we change them as our perception of the model deepens, enlarges, generalizes until the model ultimately aains a metastable place within still another model with which we struggle. e source of the exhilaration associated with computer programming is the continual unfolding within the mind and on the computer of mechanisms expressed as programs and the explosion of perception they generate. If art interprets our dreams, the computer executes them in the guise of programs! (xii-xiv, Structure and Interpretation of Computer Programs)
Computer Science is Not About Computers
Many people think that computer science is all about computers. They think that it’s about programming, hardware, and software. But this is not really true. Computer science is actually about problem solving. It’s about finding ways to solve problems using computers.
In the same way that geometry is not really about surveying instruments, computer science is not really about computers. Geometry is about the properties of space and shapes. It’s about finding ways to measure and describe these properties. Computer science is about the properties of computation. It’s about finding ways to solve problems using computers.
The tools of computer science are computers. But the essence of computer science is problem solving. It’s about using the power of computers to solve problems that would be difficult or impossible to solve by hand.
This is why computer science is such a powerful tool. It can be used to solve problems in a wide variety of fields, from science to engineering to business. And as computers become more powerful, the possibilities for computer science become even greater. If you’re interested in problem solving, then computer science is the field for you. It’s a field that’s constantly evolving, and it’s a field that offers endless possibilities.
Knowledge domains
In computer science, there are two main types of knowledge: declarative and imperative. Declarative knowledge is knowledge about what is true. It makes statements of fact that can be used to reason about things. For example, the statement “the square root of 16 is 4” is a declarative statement.
Imperative knowledge, on the other hand, is knowledge about how to do something. It describes a specific sequence of steps that can be used to achieve a goal. For example, the statement “to find the square root of a number, you can use the Babylonian method” is an imperative statement.
Declarative knowledge is often expressed in the form of axioms, which are statements that are assumed to be true. Imperative knowledge is often expressed in the form of algorithms, which are step-by-step procedures for solving problems.
Computer science is concerned with both declarative and imperative knowledge. Declarative knowledge is used to represent the structure of data and the relationships between different pieces of data. Imperative knowledge is used to describe how to manipulate data and solve problems.
Algorithms and Procedures
In computer science, we focus on imperative knowledge. This is knowledge about how to do something. It describes a specific sequence of steps that can be used to achieve a goal.
An algorithm is a step-by-step procedure for solving a problem. It is a precise description of what to do in order to get the desired result. Algorithms are often used in computer programs to automate tasks.
A procedure is a type of algorithm that is specifically designed to be used by computers. Procedures are typically written in a programming language, which is a language that computers can understand.
The Difference Between Declarative and Imperative Knowledge
Declarative knowledge is knowledge about what is true. It makes statements of fact that can be used to reason about things. For example, the statement “the square root of 16 is 4” is a declarative statement.
Imperative knowledge, on the other hand, is knowledge about how to do something. It describes a specific sequence of steps that can be used to achieve a goal. For example, the statement “to find the square root of a number, you can use the Babylonian method” is an imperative statement.
The main difference between declarative and imperative knowledge is that declarative knowledge is about what is true, while imperative knowledge is about how to do something.
Why We Care About Imperative Knowledge
We care about imperative knowledge because it allows us to give computers instructions on how to solve problems. Computers are machines that can only follow instructions, so we need to give them instructions in a way that they can understand.
Algorithms are a way of expressing imperative knowledge in a way that computers can understand. By writing algorithms, we can give computers instructions on how to solve a wide variety of problems.
The Importance of Procedures
Procedures are an important type of algorithm because they are specifically designed to be used by computers. Procedures are typically written in a programming language, which is a language that computers can understand.
This makes procedures a very convenient way to give computers instructions. We can simply write the procedure in a programming language, and then the computer can follow the instructions to solve the problem.
Procedures and Processes
A procedure is a step-by-step description of how to do something. It is a recipe for achieving a goal.
A process is the actual sequence of steps that are carried out by a computer when it is executing a procedure.
When we want to get the computer to actually compute a value, we will evaluate an expression that applies a procedure to some values. The process is the sequence of steps that the computer takes to evaluate the expression and produce the desired value.
The focus of this course is on understanding how to control different kinds of processes by describing them with procedures.
How to Control Processes
There are two main ways to control processes:
- Sequential control is the most basic way to control processes. In sequential control, the steps in a process are executed one after the other, in a linear fashion.
- Conditional control allows us to specify that certain steps in a process should only be executed if certain conditions are met. This allows us to create more complex processes that can respond to different situations.
Processes are an essential part of computer programming. They allow us to give computers instructions on how to solve problems. By understanding how to control processes, we can create programs that can perform complex tasks.
The Idea of a Computational Process
A computational process is an abstract being that inhabits computers. It is a sequence of steps that are carried out by the computer to achieve a goal.
The evolution of a process is directed by a pattern of rules called a program. Programs are written by people to tell the computer what to do.
Computational processes are like sorcerer’s spirits. They cannot be seen or touched, but they are very real. They can perform intellectual work, answer questions, and affect the world.
The programs we use to conjure processes are like sorcerer’s spells. They are carefully composed from symbolic expressions in programming languages.
When a computational process is executed on a correctly working computer, it executes the program precisely and accurately. This means that even small errors in programs can have complex and unanticipated consequences.
Learning to program is not as dangerous as learning sorcery, but it still requires care, expertise, and wisdom. A small bug in a computer-aided design program, for example, could lead to the catastrophic collapse of an airplane or a dam.
Master software engineers have the ability to organize programs so that they can be reasonably sure that the resulting processes will perform the tasks intended. They can visualize the behavior of their systems in advance, and they know how to structure programs so that unanticipated problems do not lead to catastrophic consequences.
Well-designed computational systems, like well-designed automobiles or nuclear reactors, are designed in a modular manner, so that the parts can be constructed, replaced, and debugged separately.
Controlling Complexity in Large Systems
Large systems are often complex and difficult to understand. This is because they are made up of many different parts that interact with each other in complex ways.
The language of procedures and processes can help us to control complexity in large systems by providing a way to describe the different parts of the system and how they interact with each other. This allows us to understand the system better and to design solutions that are more likely to be successful.
Examples of Existing Procedures
By abstracting existing procedures to see how they have been used to solve problems. This will help us to understand how the language of procedures and processes can be used in practice. We will also spend some time designing our own procedures to solve problems. This will give us the opportunity to practice using the language of procedures and processes and to see how it can be used to control complexity in large systems.