Structure and Interpretation 2

Question 1

What have we done so far?

Answer 1

We have used primitive arithmetic operations, we have combined these operations, and we have abstracted these composite operations by defining them as compound procedures.

Question 2

How can we define a procedure in terms of evolution?

Answer 2

A procedure is a pattern for the “local evolution” of a process. It specifies how each stage of a process is built upon the previous stage. We would like to be able to make statements about the overall, or “global” behavior of a process whose local evolution has been specified by a procedure.

Question 3

Where does the word “local” come from?

Answer 3

From the Latin “Locus” meaning place.

Question 4

In general, the number of steps required by a tree-recursive process will be proportional to ____.

Answer 4

The number of nodes in the tree.

Question 5

In general, the space required by a tree-recursive process will be proportional to _____.

Answer 5

the maximum depth of the tree

Question 6

A programming language uses an evaluation strategy to determine ____.

Answer 6

when to evaluate the argument or arguments of a function call and what kind of value to pass to the function.

Question 7

Delaying evaluation of procedure arguments until the last possible moment (e.g. until they are required by a________) is called lazy evaluation.

Answer 7

primitive operation

Question 8

What is a higher order procedure?

Answer 8

A procedure that produces a procedure as its value.

Question 9

In an applicative order language _____ when the procedure is applied.

Answer 9

all the arguments are evaluated

Question 10

In a normal order language, ____ until the argument values are needed.

Answer 10

evaluations of procedure arguments are delayed

Question 11

What two things does the call mechanism involve?

Answer 11

The parameter passing mechanism

The replacement of the call to the function by the body of the function called (without the header)

Question 12

Applicative order evaluates subexpressions _____.

Answer 12

when, i.e. just before, the procedure is applied.

Question 13

Normal order evaluates subexpressions as they are, without evaluation, and proceeds with the evaluation only when ____.

Answer 13

the corresponding formal parameter is actually itself to be evaluated.

Question 14

evaluate all arguments, then apply operator

Answer 14

applicative order evaluation

Question 15

pass unevaluated expressions to function, evaluate only when needed for primitive operation

Answer 15

normal order evaluation

Question 16

evaluate completely all subexpressions before we apply the current procedure

Answer 16

applicative order evaluation

Question 17

expand all the defined procedures into their bodies until everything is expressed in terms of primitive operations and self-evaluating values

Answer 17

normal order evaluation

Question 18

“fully expand and then reduce”

Answer 18

normal order

Question 19

“evaluate the arguments and then apply”

Answer 19

applicative order

Question 20

The key to understanding complex ideas is ____.

Answer 20

knowing what to ignore

Question 21

What is peano arithmetic?

Answer 21

Adding by incrementing and decrementing

Question 22

A linear recursion is proportional to _____ in time and space.

Answer 22

the order of x

Question 23

Iteration is a system that has ______.

Answer 23

all of its state in explicit variables.

Question 24

In recursion, the deferred procedures have ____.

Answer 24

implicit, hidden variables