Structure and Interpretation of Computer Programs
Yüklə 2,71 Mb. Pdf görüntüsü
|
11 To define f and
g using
lambda we would write (define f (lambda (x y . z) <body>)) (define g (lambda w <body>)) 12 Scheme standardly provides a map procedure that is more general than the one described here. This more general map
takes a procedure of n arguments, together with n lists, and applies the procedure to all the first elements of the lists, all the second elements of the lists, and so on, returning a list of the results. For example: (map + (list 1 2 3) (list 40 50 60) (list 700 800 900)) (741 852 963) (map (lambda (x y) (+ x (* 2 y))) (list 1 2 3) (list 4 5 6)) (9 12 15) 13 The order of the first two clauses in the cond matters, since the empty list satisfies null? and
also is not a pair. 14 This is, in fact, precisely the fringe procedure from exercise 2.28. Here we’ve renamed it to emphasize that it is part of a family of general sequence-manipulation procedures. 15 Richard Waters (1979) developed a program that automatically analyzes traditional Fortran programs, viewing them in terms of maps, filters, and accumulations. He found that fully 90 percent of the code in the Fortran Scientific Subroutine Package fits neatly into this paradigm. One of the reasons for the success of Lisp as a programming language is that lists provide a standard medium for expressing ordered collections so that they can be manipulated using higher-order operations. The programming language APL owes much of its power and appeal to a similar choice. In APL all data are represented as arrays, and there is a universal and convenient set of generic operators for all sorts of array operations. 16 According to Knuth (1981), this rule was formulated by W. G. Horner early in the nineteenth century, but the method was actually used by Newton over a hundred years earlier. Horner’s rule evaluates the polynomial using fewer additions and multiplications than does the straightforward method of first computing a
x n , then adding a n-1 x n-1 , and so on. In fact, it is possible to prove that any algorithm for evaluating arbitrary polynomials must use at least as many additions and multiplications as does Horner’s rule, and thus Horner’s rule is an optimal algorithm for polynomial evaluation. This was proved (for the number of additions) by A. M. Ostrowski in a 1954 paper that essentially founded the modern study of optimal algorithms. The analogous statement for multiplications was proved by V. Y. Pan in 1966. The book by Borodin and Munro (1975) provides an overview of these and other results about optimal algorithms. 17 This definition uses the extended version of map described in footnote 12. 18 This approach to nested mappings was shown to us by David Turner, whose languages KRC and Miranda provide elegant formalisms for dealing with these constructs. The examples in this section (see also exercise 2.42) are adapted from Turner 1981. In section 3.5.3, we’ll see how this approach generalizes to infinite sequences.
19 We’re representing a pair here as a list of two elements rather than as a Lisp pair. Thus, the ‘‘pair’’ (i,j) is represented as (list i j) , not (cons i j) . 20 The set S - x is the set of all elements of S, excluding x. 21 Semicolons in Scheme code are used to introduce comments. Everything from the semicolon to the end of the line is ignored by the interpreter. In this book we don’t use many comments; we try to make our programs self-documenting by using descriptive names. 22 The picture language is based on the language Peter Henderson created to construct images like M.C. Escher’s ‘‘Square Limit’’ woodcut (see Henderson 1982). The woodcut incorporates a repeated scaled pattern, similar to the arrangements drawn using the square-limit procedure in this section. 23 William Barton Rogers (1804-1882) was the founder and first president of MIT. A geologist and talented teacher, he taught at William and Mary College and at the University of Virginia. In 1859 he moved to Boston, where he had more time for research, worked on a plan for establishing a ‘‘polytechnic institute,’’ and served as Massachusetts’s first State Inspector of Gas Meters. When MIT was established in 1861, Rogers was elected its first president. Rogers espoused an ideal of ‘‘useful learning’’ that was different from the university education of the time, with its overemphasis on the classics, which, as he wrote, ‘‘stand in the way of the broader, higher and more practical instruction and discipline of the natural and social sciences.’’ This education was likewise to be different from narrow trade-school education. In Rogers’s words: The world-enforced distinction between the practical and the scientific worker is utterly futile, and the whole experience of modern times has demonstrated its utter worthlessness. Rogers served as president of MIT until 1870, when he resigned due to ill health. In 1878 the second president of MIT, John Runkle, resigned under the pressure of a financial crisis brought on by the Panic of 1873 and strain of fighting off attempts by Harvard to take over MIT. Rogers returned to hold the office of president until 1881. Rogers collapsed and died while addressing MIT’s graduating class at the commencement exercises of 1882. Runkle quoted Rogers’s last words in a memorial address delivered that same year: ‘‘As I stand here today and see what the Institute is, ...
I call to mind the beginnings of science. I remember one hundred and fifty years ago Stephen Hales published a pamphlet on the subject of illuminating gas, in which he stated that his researches had demonstrated that 128 grains of bituminous coal -- ’’ ‘‘Bituminous coal,’’ these were his last words on earth. Here he bent forward, as if consulting some notes on the table before him, then slowly regaining an erect position, threw up his hands, and was translated from the scene of his earthly labors and triumphs to ‘‘the tomorrow of death,’’ where the mysteries of life are solved, and the disembodied spirit finds unending satisfaction in contemplating the new and still unfathomable mysteries of the infinite future. In the words of Francis A. Walker (MIT’s third president): All his life he had borne himself most faithfully and heroically, and he died as so good a knight would surely have wished, in harness, at his post, and in the very part and act of public duty. Yüklə 2,71 Mb. Dostları ilə paylaş:
|