1.1 The Elements of Programming
強力なプログラミング言語は、コンピュータに仕事を命令するだけのものではない。言語は、processについて考える際のフレームワークを与えてくれる。ゆえに、言語について語る時、その言語がどのように単純なアイデアを組み合わせて複雑なアイデアを作り出すか、に注目する必要がある。すべての強力な言語は、これを達成する為に、3つのメカニズムを持つ:
• primitive expressions:言語の最もシンプルな要素
• means of combination:単純なものから合成された要素を作り出す
• means of abstraction:合成要素に名前を付け、ユニットとして扱う
プログラミングでは、proceduresとdataの、2つの要素を扱う(後で、この2つにはそれほど違いがないことがわかる)。簡単に言えば、dataとは我々が操作したい「もの」、proceduresとはdataを操作する方法を記述したもの。ゆえに、すべての強力なプログラミング言語は、primitive dataとprimitive proceduresを記述し、proceduresとdataを合成し抽象化する手段を持つ必要がある。
この章では、proceduresを作るルールに焦点を絞るため、シンプルな数値データだけを扱う。後の章で、同じルールが、compound dataを操作するproceduresを作るのにも適用できることを見る。
----------
Primitive Elements - primitive procedures, primitive data
Means of Combination - compound procedures, compound data
Means of Abstraction - named compound procedures, named compound data
procedures - recipes
Lisp uses prefix notation
combination: (+ 3 4 5)
operator: +
operands: 3 4 5
eg. (+ 3 (* 4 5) 6)
Lisp has special forms
abstraction: (define a (+ 5 5))
eg. (* a a) -> 625
name general idea: (define (square x) (* x x))
eg. (square 10) -> 100
another way: (define square (lambda (x) (* x x)))
lambda is a Lisp's way saying make a procedure
actually, (define (square x) (* x x)) is a syntactic sugar of (define square (lambda (x) (* x x)))
(define (average x y) (/ (+ x y) 2))
(define (mean-square x y) (average (square x) (square y)))
case analysis:
abs(x) = -x for x<0, 0 for x=0, x for x>0
(define (abs x)
(cond ((< x 0) (- x)) ((= x 0) 0) ((> x 0) x)))
(< x 0) is a predicate: evaluate to true or false.
if operator - takes only one argument, like (- x), it means negate.
(define (abs x)
(if (< x 0) (- x) x))
To find an approximation to sqrt(x) - Newton's method
- make a guess G
- improve the guess by averaging G and X/G
- keep improving the guess until it is good enough
- use 1 as an initial guess
(define (try guess x)
(if (good-enough? guess x)
guess
(try (improve guess x) x)))
(define (sqrt x) (try 1 x))
(define (improve guess x) (average guess (/ x guess)))
(define (good-enough? guess x) (< (abs (- (square guess) x)) .001))
(sqrt 2)
(try 1 2)
(try (improve 1 2) 2)
(try (average 1 (/ 2 1)) 2)
(try 1.5 2)
...
1.41421568
recursive procedures - recursive definition
black-box abstraction - block structure:
(define (sqrt x)
(define (improve guess)
(average guess (/ x guess)))
(define (good-enough? guess)
(< (abs (- (square guess) x))
.001))
(define (try guess)
(if (good-enough? guess)
guess
(try (improve guess))))
(try 1))
applicative-order vs. normal-order
- applicative-order: evaluate everything, apply, then return
- normal-order: evaluate everything into their primitive forms, then apply and return
variable scope
lexical scoping