Structure and Interpretation of Computer Programs

These notes will be evergrowing as I read the book and take the video courses on the MIT Open Courseware site. Feel free to reach out and chat about the book or any of the notes you may find here!

Computational Processes -> Manipulate Data

└> Evolution by a pattern of rules called program

Lisp

Includes new data objects:

• Atoms
• Lists

Procedures are processes that can be represented and manipulated as Lisp data.

The ability to represent procedures as data also makes Lisp and excellent language for writing programs that must manipulate other program's data, such as interpreters and compilers that support computer languages.

Expressions using primitive procedures

Basic math operations using list

Addition

lispCopy
1(+ 137 349)

Subtraction

lispCopy
1(- 1000 334)

Multiplication

lispCopy
1(* 5 99)

Division

lispCopy
1(/ 10 5)

Variables

A critical aspect of a programming language is the means it provides for using names to refer to computational objects. We say that the name identifies a *variable* whose *value* is the object.

In Lisp we can create variables using define.

lispCopy
1(define size 2)

Defining the size variable causes the interpreter to associate the value 2 with the name size. We can then use this variable by name:

lispCopy
1(* 5 size)

The possibility of associating values to variables and using them later means that the interpreter must maintain some memory that keeps track of name-object pairs. This memory is called the global environment.

Combinations

Are expressions formed by delimiting a list of expressions within parentheses. The leftmost element in the list is called the operator and the other elements are called the operands.

Combinations can be evaluated by:

• Evaluating the subexpression in the combination, for example with (* 2 (+ 1 1)) we will evaluate first (+1 1)
• Apply the procedure that is the value of the operator to the operands of the subexpression

The evaluation rule is recursive because we need to evaluate each subexpression in the combination to evaluate the whole combination.

(...) recursion is a very powerful technique for dealing with hierarchical, treelike objects. In fact, the "percolate values upward" form of the evaluation rule is an example of a general kind of process known as *tree accumulation*.

Compound Procedures

We can create a procedure definition, by giving a name to a compound procedure and then referencing it as a unit. For example:

lispCopy
1(define (square x)(* x x))

The general form of a procedure definition is

(define (⟨name⟩ ⟨formal parameters⟩)⟨body⟩)

lispCopy
1(define (sum-of-squares x y)
2  (+ (square x) (square y)))