Structure And Interpretation Flashcards
Can Lisp processes become data?
Yes. Lisp descriptions of processes, called procedures, can themselves be represented and manipulated as Lisp data.
What is the ethical definition of formalism?
A doctrine stating that acts are right or wrong of themselves regardless of consequences.
What is the mathematical definition of formalism?
A doctrine that mathematics, including the logic used in proofs, can be based on the formal manipulation of symbols without regard to their meaning.
In what year was Lisp invented?
1958
What active language is older than Lisp?
Fortran, specified in 1957
Who conceived of Lisp?
John McCarthy in his paper “Recursive Functions of Symbolic Expressions and Their Computation by Machine.”
What is a Lisp interpreter?
It is a machine that carries out processes described in the Lisp language.
A powerful programming language is a means for instructing a computer to perform tasks, and what else?
The language also serves as a framework within which we organize our ideas about processes.
Describe the three ways in which powerful computer languages turn simple ideas into complex ideas.
- 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.
What are the two elements with which programming deals?
Procedures
Data
Define Evaluate
To find the value of
One kind of primitive expression you might type is a number. What, precisely, is happening when you type a number?
More precisely, the expression that you type consists of the numerals that represent the number in base 10.
(+ 3 4)
Describe what, precisely, this is?
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.
How do expressions become combinations?
Combinations are formed by delimiting a list of expressions within parentheses in order to denote procedure application.
How is a combination evaluated?
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.
Define Delimit
To officially set or state the limits of something.
What is the difference between a parameter and an argument?
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.
What is one good reason for prefix notation?
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)
Define “pretty printing” as it pertains to Lisp
A convention in which each long combination is written so that the operands are aligned vertically.
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?
We say that the name identifies a variable whose value is the object.
What is Lisp’s simplest means of abstraction?
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.
How are complex programs constructed?
Complex programs are constructed by building, step by step, computational objects of increasing complexity.
What follows from the possibility of associating values with symbols and later retrieving them?
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).
How are primitive cases dealt with when evaluating an expression?
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.)
What role does the environment play in a Lisp program?
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 +).
Do the rules for evaluations apply to Lisp definitions?
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.
What are exceptions to the general rule for evaluations called?
Special Forms
What is the general rule for evaluations?
To evaluate a combination, do the following:
- Evaluate the subexpressions of the combination.
- 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).
Is Lisp syntax complicated?
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.
What is a Lisp procedure definition?
A powerful abstraction technique by which a compound operation can be given a name and then referred to as a unit.
(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.
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.
What is the difference between applicative-order evaluation and normal-order evaluation?
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.
What is the special form for case analysis in Lisp?
Cond
Describe the general form of “cond”
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.
How are case analysis with “cond” evaluated?
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.
Define predicate
The word predicate is used for procedures that return true or false, as well as for expressions that evaluate to true or false.
Define Else
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.
Define the special form “if”
A restricted type of conditional that can be used when there are precisely two cases in the case analysis.
How is an if expression evaluated?
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.
Which of the three logical operators “and”, “or” and “not” are special forms?
“And” and “or” are special forms, not procedures, because the subexpressions are not necessarily all evaluated. Not is an ordinary procedure.
