Structure And Interpretation

Question 1

Can Lisp processes become data?

Answer 1

Yes. Lisp descriptions of processes, called procedures, can themselves be represented and manipulated as Lisp data.

Question 2

What is the ethical definition of formalism?

Answer 2

A doctrine stating that acts are right or wrong of themselves regardless of consequences.

Question 3

What is the mathematical definition of formalism?

Answer 3

A doctrine that mathematics, including the logic used in proofs, can be based on the formal manipulation of symbols without regard to their meaning.

Question 4

In what year was Lisp invented?

Answer 4

1958

Question 5

What active language is older than Lisp?

Answer 5

Fortran, specified in 1957

Question 6

Who conceived of Lisp?

Answer 6

John McCarthy in his paper “Recursive Functions of Symbolic Expressions and Their Computation by Machine.”

Question 7

What is a Lisp interpreter?

Answer 7

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

Question 8

A powerful programming language is a means for instructing a computer to perform tasks, and what else?

Answer 8

The language also serves as a framework within which we organize our ideas about processes.

Question 9

Describe the three ways in which powerful computer languages turn simple ideas into complex ideas.

Answer 9

1. Primitive expressions, which represent the simplest entities the language is concerned with. 2. means of combination, by which compound elements are built from simpler ones, and 3. means of abstraction, by which compound elements can be named and manipulated as units.

Question 10

What are the two elements with which programming deals?

Answer 10

Procedures

Data

Question 11

Define Evaluate

Answer 11

To find the value of

Question 12

One kind of primitive expression you might type is a number. What, precisely, is happening when you type a number?

Answer 12

More precisely, the expression that you type consists of the numerals that represent the number in base 10.

Question 13

(+ 3 4)

Describe what, precisely, this is?

Answer 13

Expressions representing numbers may be combined with an expression representing a primitive procedure (such as + or *) to form a compound expression that represents the application of the procedure to those numbers.

Question 14

How do expressions become combinations?

Answer 14

Combinations are formed by delimiting a list of expressions within parentheses in order to denote procedure application.

Question 15

How is a combination evaluated?

Answer 15

The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands.

Question 16

Define Delimit

Answer 16

To officially set or state the limits of something.

Question 17

What is the difference between a parameter and an argument?

Answer 17

The term parameter (sometimes called formal parameter) is often used to refer to the variable as found in the function definition, while argument (sometimes called actual parameter) refers to the actual value passed.

Question 18

What is one good reason for prefix notation?

Answer 18

Prefix notation has several advantages. One of them is that it can accommodate procedures that may take an arbitrary number of arguments:
(+ 32 33 33 32 23 233 233 3322 323 … n)

Question 19

Define “pretty printing” as it pertains to Lisp

Answer 19

A convention in which each long combination is written so that the operands are aligned vertically.

Question 20

A critical aspect of a programming language is the means it provides for using names to refer to computational objects. How do we describe this?

Answer 20

We say that the name identifies a variable whose value is the object.

Question 21

What is Lisp’s simplest means of abstraction?

Answer 21

Define is our language’s simplest means of abstraction, for it allows us to use simple names to refer to the results of compound operations.

Question 22

How are complex programs constructed?

Answer 22

Complex programs are constructed by building, step by step, computational objects of increasing complexity.

Question 23

What follows from the possibility of associating values with symbols and later retrieving them?

Answer 23

It should be clear that 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 the name-object pairs. This memory is called the environment (more precisely the global environment, since we will see later that a computation may involve a number of different environments).

Question 24

How are primitive cases dealt with when evaluating an expression?

Answer 24

We take care of the primitive cases by stipulating that:

the values of numerals are the numbers that they name,

the values of built-in operators are the machine instruction sequences that carry out the corresponding operations, and

the values of other names are the objects associated with those names in the environment.

(The second is a special case of the third, where built-in operators themselves are objects associated with names.)

Question 25

What role does the environment play in a Lisp program?

Answer 25

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 (or even for the symbol +).

Question 26

Do the rules for evaluations apply to Lisp definitions?

Answer 26

No, (define x 3) is not a combination. Evaluating (define x 3) does not apply define to two arguments, one of which is the value of the symbol x and the other of which is 3, since the purpose of the define is precisely to associate x with a value. The purpose of the define is precisely to associate x with a value.

Question 27

What are exceptions to the general rule for evaluations called?

Answer 27

Special Forms

Question 28

What is the general rule for evaluations?

Answer 28

To evaluate a combination, do the following:

1. Evaluate the subexpressions of the combination.
2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

Question 29

Is Lisp syntax complicated?

Answer 29

In comparison with most other programming languages, Lisp has a very simple syntax; that is, the evaluation rule for expressions can be described by a simple general rule together with specialized rules for a small number of special forms.

Question 30

What is a Lisp procedure definition?

Answer 30

A powerful abstraction technique by which a compound operation can be given a name and then referred to as a unit.

Question 31

(define (square x) (* x x))

We have here a compound procedure, which has been given the name square. The procedure represents the operation of multiplying something by itself. The thing to be multiplied is given a local name, x, which plays the same role that a pronoun plays in natural language. Evaluating the definition creates this compound procedure and associates it with the name square.

Answer 31

Observe that there are two different operations being combined here: we are creating the procedure, and we are giving it the name square. It is possible, indeed important, to be able to separate these two notions – to create procedures without naming them, and to give names to procedures that have already been created.

Question 32

What is the difference between applicative-order evaluation and normal-order evaluation?

Answer 32

In applicative-order evaluation, the interpreter first evaluates the operator and operands and then applies the resulting procedure to the resulting arguments.

Normal-order evaluation would not evaluate the operands until their values were needed. Instead it would first substitute operand expressions for parameters until it obtained an expression involving only primitive operators, and would then perform the evaluation.

Question 33

What is the special form for case analysis in Lisp?

Answer 33

Cond

Question 34

Describe the general form of “cond”

Answer 34

The symbol cond is followed by parenthesized pairs of expressions called clauses. The first expression in each pair is a predicate – that is, an expression whose value is interpreted as either true or false.

Question 35

How are case analysis with “cond” evaluated?

Answer 35

The predicates are evaluated one at a time to see whether they are true or false. This process continues until a predicate is found whose value is true, in which case the interpreter returns the value of the corresponding consequent expression of the clause as the value of the conditional expression. If none of the predicates are found to be true, the value of the cond is undefined.

Question 36

Define predicate

Answer 36

The word predicate is used for procedures that return true or false, as well as for expressions that evaluate to true or false.

Question 37

Define Else

Answer 37

Else is a special symbol that can be used in place of the a predicate in the final clause of a cond. This causes the cond to return as its value the value of the corresponding whenever all previous clauses have been bypassed. In fact, any expression that always evaluates to a true value could be used as the predicate here.

Question 38

Define the special form “if”

Answer 38

A restricted type of conditional that can be used when there are precisely two cases in the case analysis.

Question 39

How is an if expression evaluated?

Answer 39

To evaluate an if expression, the interpreter starts by evaluating the part of the expression. If the evaluates to a true value, the interpreter then evaluates the and returns its value. Otherwise it evaluates the and returns its value.

Question 40

Which of the three logical operators “and”, “or” and “not” are special forms?

Answer 40

“And” and “or” are special forms, not procedures, because the subexpressions are not necessarily all evaluated. Not is an ordinary procedure.