SICP - Notes - Chapter I

Here are some general notes regarding the first chapter of the book sicp that I think are worth remembering. For each note the page is given. I hope it is useful to some of you.

• Book: Structure and Interpretation of Computer Languages.

• Chapter: I, Building Abstraction with Procedures.

Here is a list of the notes contained in this file:

Page: 23

Underlying our approach to this subject is our conviction that computer science is not a science and that its significance has little to do with computers. The computer revolution is a revolution in the way we think and in the way we express what we think.

The essence of this change is the emergence of what might best be called procedural epistemology, the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects.

Mathematics provide a framework for dealing precisely with notions of "what is". Computation provides a framework for dealing precisely with notions of "how to".

Page: 29

Computational processes are abtract beings that inhabit computers. They cannot be seen or touched, and they are not composed of matter at all. However, they are very real, and they can perform intellectual work. They can answer questions, and they can affect the world in various ways. In a way, a computational process is much like a sorcerer's idea of a spirit.

As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes using symbolic expressions in arcane and esoteric programming languages that prescribe the tasks we want our proceses to perform.

Page: 31

Lisp was inveted in the late 1950s as a formalism for reasoning about the use of certain kinds of logical expression, called recursion equations, as a model for computation. The language was conceived by John McCarthy and is based on his paper "Recursive Functions of Symbolic Expressions and Their Computation By Machine".

A Lisp interpreter is a machine that carries out processes described in the Lisp language.

Lisp, whose name is an acryonym for LIst Processing, was designed to provide symbolic manipulating capabilities for attacking programming problems such as the symbolic differentiation and integration of algebraic expressions. It evolved informally in an experimental manner in response to users' needs and to pragmatic implementation considerations. By now Lisp is a family of dialects, which, while sharing most of the original features, may differ from one another in significant ways. The dialect of Lisp used in this book is called Scheme.

Lisp was choosen because it possesses unique features that make it an excellent medium for studying important programming constructs and data sructures and for relating them to the linguistic features that support them. The most isgnificant of these features is the fact that Lisp descriptions of processes, called procedures can themselves be represented and manipulated as Lisp data. The ability to represent procedures as data makes Lisp an excellent language for writing programs that must manipulate other programs as data, such as the interpreters and compilers that support computer languages.

A powerful programming language is more than just a means for instructing a computer to perform tasks. The language also serves as a framework within which we organize our ideas about processes.

When we describe a language, we should pay particular attention to the means that the language provides for combining simple ideas to form more complex ideas. Every powerful language has three mechanisms for this:

• primitive expressions, which represent the simplest entities the language is concerned with,

• means of combination, by which compound elements are built from simples ones, and

• means of abstraction, by which compound elements can e named and manipulated as units.

In programming, we deal with two kinds of elements: procedures and data. Informally data is "stuff" that we want to manipulate, and procedures are descriptions of the rules for manipulating the data. Later we will discover that procedures and really data are not so different.

Page: 14

The environment plays a great role in determining the meaning of the symbols in expressions.

In an interactive language such as Lisp, it is meaningless to speak of the value of an expression such as (+ x 1) without specifying any information about the environment that would provide a meaning for the symbol x and even for the symbol + .

The general notion of the environment as providing a context in which evaluation takes place will play an important role in our understanding of program execution.

Page: 38

A programming language should provide means for using names to refer to computational objects. We say that the name identifies a variable whose value is the object.

The possibility of associating values with symbols and later retrieving them means that the interpreter must maintain some sort of memory that keeps track of name-object pairs. This memory is called the global environment. A computation may involve a number of different environments.

Page: 46

The process followed by the interpreter to evaluate a combination whose operator names a compound procedure is similar for the case where the operator names a primitive procedure. For compound procedures the application process is as follows:

To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

The proess we have just described is called the substitution model for procedure application. This model determines the "meaning" of the procedure application (at least for this chapter). It's important however to keep in mind that:

• The purpose of the substitution is to help us think about procedure application, not to provide a description of how the interpreter really works. In practice the "substitution" is accomplished by using a local environment for the formal parameters.

• The substitution model not the only model of how interpreter really works. It is actually the simplest, and it breaks down when introducing procedures with "mutable data". Later the substitution model will be replaced with a more complicated model of procedure application.

Page: 46

The "fully expand and then reduce" evaluation method is known as normal-order evaluation, in contract to the "evaluate the arguments and then apply" method that the interpreter actually uses, which is called the applicative-order evaluation.

It can be shown that for procedure applications that can be modelled using substitution and that yield legitimate values, normal-order and applicative-order evaluation produce the same value.

Lisp uses applicative-order evaluation for main two reasons:

• It is more efficient as it tends to avoids having to evaluate the same expression multiple times.

• Normal-order evaluation becoems much more complicate to deal with for procedures that cannot be modelled by substitution.

  In any case, normal-order evaluation can be an extremely valuable tool.

Page: 56

There is an important difference between mathematical functions and computer procedures. Procedures must be effective. For example, we can define the square-root function as

\[\sqrt{x} := y: \,\,\, y \geq 0 \land y^2 = x\]

We can use this definition to recognize wheter one number is the square root of another, but we can't use it to actually find the square root of a given number.

The contrast between function and procedure is a reflection of the general distinction between describing properties of things and describing how to do things. This is sometimes referred to as the distinction between the following two types of knowledge

• Declarative knowledge: which deals with declarative (what is) descriptions.

• Imperative knowledge: which deals with imperative (how to) descriptions.

Declarative and imperative descriptions are intimately related.

There is a large amount of research aimed at establishing techniques for proving that programs are correct. Much of the technical difficulty in this context has to do with negotiating the transition between imperative statements (from which programs are constructed) and declarative statements (which can be used to deduce things).

There is also work done in the design of very high level language, in which one programs in terms of declarative statements. The idea is to make interpreters sophisticated enough so that, given "what is", knowledge specified by the programmer, they can generate "how to" knowledge automatically. This cannot be done in general, but some progress has been made.

Page: 65

A bound variable is the name given to a formal parameter of a procedure. We say that the procedure definition binds its formal parameters. The meaning of a procedure definition is unchanged if a bound variable is consistently renamed throughout the definition. The set of expression for which a binding defines a name is called the scope of that name. In a procedural definition, the bound variables declared as the formal parameters of the procedure have the body of the procedure as their scope.

If a variable is not bound, we say that it is free. The meaning of a procedure is not independent of the names of its free variable. The meaning of the prodecure depends on the meaning of the free variables in the currently active working environment.

Lexical scoping dictates that free variables in a procedure are taken to refer to bindings made by enclosing procedure definitions; that is, they are looked up in the environment in which the procedure was defined.

Page: 72

A recursive process is a process characterized by a chain of deferred operations. Carrying out this process requires that the interpreter keep tracks of the operations to be performed later on.

An iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate.

Page: 73

When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers to the procedure itself.

When instead we describe a process as following a pattern that is linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written.

Page: 88

In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithm.

One of the things we should demand from a powerful programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly. Procedures provide this ability, and this is why all but the most primitive programming languages include mechanisms for defining procedures.

Often the same programming pattern will be used with a number of different procedures. To express such patterns as concepts, we will need to construct procedures that can accept procedures as arguments or return procedures as values. Procedures that manipulate procedures are called high-order procedures.

Page: 105

Mathematicians have identified an abstraction known as the summation of a series, and the following "sigma notation" was invented

\[\sum\limits_{n = a}^b f(n) = f(a) + ... + f(b)\]

The power of sigma notation is that it allows mathematician to deal with the concept of summation itself rather than only with particular sums. This allows one to formulate general results about sums that are independent of the particular series being summed.

In general programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the "rights and privileges" of first-class elements are:

• They may be named by varables;

• They may be passed as arguments to procedures;

• They may be returned as the results of procedures;

• They may be included in data structures.

Lisp, unlike other common programming languages, awards procedures full first-class status. This poses challenges for efficient implementation, but the resulting gain in expressive power is enormous.