flâneur

Gabriel Galer

0 followers · 262 views

on the atlas — 14

highlights — 70

  • But in the reduction step, where we strip off the car of the list, we must take into account that the car may itself be a tree whose leaves we need to count.
    Structure and Interpretation of Computer Programs
  • Defining scale-list in terms of map suppresses that level of detail and emphasizes that scaling transforms a list of elements to a list of results. The difference between the two definitions is not that the computer is performing a different process (it isn't) but that we think about the process differently.
    Structure and Interpretation of Computer Programs
  • One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter's value will be a list of any remaining arguments.
    Structure and Interpretation of Computer Programs
  • The word nil is a contraction of the Latin word nihil, which means ``nothing.'
    Structure and Interpretation of Computer Programs
  • This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the calculus.
    Structure and Interpretation of Computer Programs
  • The subtle point to notice is that the value returned by (cons x y) is a procedure -- namely the internally defined procedure dispatch, which takes one argument and returns either x or y depending on whether the argument is 0 or 1.
    Structure and Interpretation of Computer Programs
  • This style of programming is often called message passing, and we will be using it as a basic tool in chapter 3 when we address the issues of modeling and simulation.
    Structure and Interpretation of Computer Programs
  • Another approach, introduced by Zilles at MIT, by Goguen, Thatcher, Wagner, and Wright at IBM (see Thatcher, Wagner, and Wright 1978), and by Guttag at Toronto (see Guttag 1977), is called algebraic specification. It regards the ``procedures'' as elements of an abstract algebraic system whose behavior is specified by axioms that correspond to our ``conditions,'' and uses the techniques of abstract algebra to check assertions about data objects.
    Structure and Interpretation of Computer Programs
  • One, pioneered by C. A. R. Hoare (1972), is known as the method of abstract models. It formalizes the ``procedures plus conditions'' specification as outlined in the rational-number example above. Note that the condition on the rational-number representation was stated in terms of facts about integers (equality and division). In general, abstract models define new kinds of data objects in terms of previously defined types of data objects. Assertions about data objects can therefore be checked by reducing them to assertions about previously defined data objects.
    Structure and Interpretation of Computer Programs
  • To continue with our simple example, suppose we are designing a rational-number package and we can't decide initially whether to perform the gcd at construction time or at selection time. The data-abstraction methodology gives us a way to defer that decision without losing the ability to make progress on the rest of the system.
    Structure and Interpretation of Computer Programs
  • The horizontal lines represent abstraction barriers that isolate different ``levels'' of the system. At each level, the barrier separates the programs (above) that use the data abstraction from the programs (below) that implement the data abstraction.
    Structure and Interpretation of Computer Programs
  • To enable us to implement the concrete level of our data abstraction, our language provides a compound structure called a pair, which can be constructed with the primitive procedure cons. This procedure takes two arguments and returns a compound data object that contains the two arguments as parts. Given a pair, we can extract the parts using the primitive procedures car and cdr.
    Structure and Interpretation of Computer Programs
  • In particular, we introduce data-directed programming as a technique that allows individual data representations to be designed in isolation and then combined additively (i.e., without modification).
    Structure and Interpretation of Computer Programs
  • Indeed, we will discover how to form compound data using no special ``data'' operations at all, only procedures. This will further blur the distinction between ``procedure'' and ``data,'' which was already becoming tenuous toward the end of chapter 1.
    Structure and Interpretation of Computer Programs
  • As with compound procedures, the main issue to be addressed is that of abstraction as a technique for coping with complexity, and we will see how data abstraction enables us to erect suitable abstraction barriers between different parts of a program.
    Structure and Interpretation of Computer Programs
  • It would be much better if we could ``glue together'' a numerator and denominator to form a pair -- a compound data object -- that our programs could manipulate in a way that would be consistent with regarding a rational number as a single conceptual unit.
    Structure and Interpretation of Computer Programs
  • The general technique of isolating the parts of a program that deal with how data objects are represented from the parts of a program that deal with how data objects are used is a powerful design methodology called data abstraction.
    Structure and Interpretation of Computer Programs
  • Just as the ability to define procedures enables us to deal with processes at a higher conceptual level than that of the primitive operations of the language, the ability to construct compound data objects enables us to deal with data at a higher conceptual level than that of the primitive data objects of the language.
    Structure and Interpretation of Computer Programs
  • Programs are typically designed to model complex phenomena, and more often than not one must construct computational objects that have several parts in order to model real-world phenomena that have several aspects.
    Structure and Interpretation of Computer Programs
  • The notion of first-class status of programming-language elements is due to the British computer scientist Christopher Strachey
    Structure and Interpretation of Computer Programs
  • As programmers, we should be alert to opportunities to identify the underlying abstractions in our programs and to build upon them and generalize them to create more powerful abstractions. This is not to say that one should always write programs in the most abstract way possible; expert programmers know how to choose the level of abstraction appropriate to their task. But it is important to be able to think in terms of these abstractions, so that we can be ready to apply them in new contexts.
    Structure and Interpretation of Computer Programs
  • In order to implement Newton's method as a procedure, we must first express the idea of derivative. Note that ``derivative,'' like average damping, is something that transforms a function into another function.
    Structure and Interpretation of Computer Programs
  • Notice how this formulation makes explicit the three ideas in the method: fixed-point search, average damping, and the function y x/y.
    Structure and Interpretation of Computer Programs
  • In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for e - 2, where e is the base of the natural logarithms. In this fraction, the Ni are all 1, and the Di are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ....
    Structure and Interpretation of Computer Programs
  • This approach of averaging successive approximations to a solution, a technique we that we call average damping, often aids the convergence of fixed-point searches.
    Structure and Interpretation of Computer Programs
  • Since the interval of uncertainty is reduced by half at each step of the process, the number of steps required grows as (log( L/T)), where L is the length of the original interval and T is the error tolerance (that is, the size of the interval we will consider ``small enough'').
    Structure and Interpretation of Computer Programs
  • Let allows one to bind variables as locally as possible to where they are to be used
    Structure and Interpretation of Computer Programs
  • The variables' values are computed outside the let. This matters when the expressions that provide the values for the local variables depend upon variables having the same names as the local variables themselves.
    Structure and Interpretation of Computer Programs
  • Church developed the calculus to provide a rigorous foundation for studying the notions of function and function application. The calculus has become a basic tool for mathematical investigations of the semantics of programming languages.
    Structure and Interpretation of Computer Programs
  • Simpson's Rule is a more accurate method of numerical integration
    Structure and Interpretation of Computer Programs
  • we would like our language to be powerful enough so that we can write a procedure that expresses the concept of summation itself rather than only procedures that compute particular sums.
    Structure and Interpretation of Computer Programs
  • Indeed, mathematicians long ago identified the abstraction of summation of a series and invented ``sigma notation,''
    Structure and Interpretation of Computer Programs
  • Procedures that manipulate procedures are called higher-order procedures. This section shows how higher-order procedures can serve as powerful abstraction mechanisms, vastly increasing the expressive power of our language.
    Structure and Interpretation of Computer Programs
  • One of the most striking applications of probabilistic prime testing has been to the field of cryptography. Although it is now computationally infeasible to factor an arbitrary 200-digit number, the primality of such a number can be checked in a few seconds with the Fermat test. This fact forms the basis of a technique for constructing ``unbreakable codes'' suggested by Rivest, Shamir, and Adleman (1977). The resulting RSA algorithm has become a widely used technique for enhancing the security of electronic communications.
    Structure and Interpretation of Computer Programs
  • The idea of the algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are precisely the same as the common divisors of b and r. Thus, we can use the equation to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers.
    Structure and Interpretation of Computer Programs
  • In other words, the Fibonacci numbers are produced by applying Tn, the nth power of the transformation T, starting with the pair (1,0). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations Tpq, where Tpq transforms the pair (a,b) according to a bq + aq + ap and b bp + aq. Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tp'q' of the same form, and compute p' and q' in terms of p and q. This gives us an explicit way to square these transformations, and thus we can compute Tn using successive squarin…
    Structure and Interpretation of Computer Programs
  • This algorithm, which is sometimes known as the ``Russian peasant method'' of multiplication, is ancient.
    Structure and Interpretation of Computer Programs
  • 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 algorithms.)
    Structure and Interpretation of Computer Programs
  • Like the design and description of a process, the analysis of a process can be carried out at various levels of abstraction.
    Structure and Interpretation of Computer Programs
  • One approach to coping with redundant computations is to arrange matters so that we automatically construct a table of values as they are computed. Each time we are asked to apply the procedure to some argument, we first look to see if the value is already stored in the table, in which case we avoid performing the redundant computation. This strategy, known as tabulation or memoization, can be implemented in a straightforward way
    Structure and Interpretation of Computer Programs
  • But even in numerical operations, tree-recursive processes can be useful in helping us to understand and design programs. For instance, although the first fib procedure is much less efficient than the second one, it is more straightforward, being little more than a translation into Lisp of the definition of the Fibonacci sequence. To formulate the iterative algorithm required noticing that the computation could be recast as an iteration with three state variables.
    Structure and Interpretation of Computer Programs
  • This second method for computing Fib(n) is a linear iteration. The difference in number of steps required by the two methods -- one linear in n, one growing as fast as Fib(n) itself -- is enormous, even for small inputs.
    Structure and Interpretation of Computer Programs
  • The interpreter itself evaluates expressions using a tree-recursive process.
    Structure and Interpretation of Computer Programs
  • The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive.
    Structure and Interpretation of Computer Programs
  • It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.
    Structure and Interpretation of Computer Programs
  • we will see that any iterative process can be realized ``in hardware'' as a machine that has a fixed set of registers and no auxiliary memory. In contrast, realizing a recursive process requires a machine that uses an auxiliary data structure known as a stack.
    Structure and Interpretation of Computer Programs
  • The contrast between the two processes can be seen in another way. In the iterative case, the program variables provide a complete description of the state of the process at any point. If we stopped the computation between steps, all we would need to do to resume the computation is to supply the interpreter with the values of the three program variables.
    Structure and Interpretation of Computer Programs
  • By contrast, the second process does not grow and shrink. At each step, all we need to keep track of, for any n, are the current values of the variables product, counter, and max-count. We call this an iterative process.
    Structure and Interpretation of Computer Programs
  • The expansion occurs as the process builds up a chain of deferred operations (in this case, a chain of multiplications). The contraction occurs as the operations are actually performed. This type of process, characterized by a chain of deferred operations, is called a recursive process.
    Structure and Interpretation of Computer Programs
  • A procedure is a pattern for the local evolution of a computational process. It specifies how each stage of the process is built upon the previous stage.
    Structure and Interpretation of Computer Programs