Chapter 1)

프로시저를 써서 요약하는 법

---

1. 계산 프로세스(computational process)란?

컴퓨터 속에 있는 것이며, 데이터(data)라고 하는것을 조작하면서 어떤 일을 한다.
프로세스(process)는 사람이 만든 규칙에 따라 움직이고, 이 규칙을 가리켜 프로그램이라 한다.
계산 프로세스란, 마법사가 넋을 불러내려 할 때 머릿속에 떠올리는 생각과 엇비슷하여, 보거나 만지지는 못하지만 없다고 무시할 수 없는 그 무엇이다.(잉?)

2.  프로그램 짤 때 바탕이 되는 것

프로그램 짜기에 좋은 언어는 그저 컴퓨터에 할 일을 지시하는 수단만이 아니다. 프로그래밍 언어는 프로세스에 대한 사람의 생각을 짜임새 있게 담아내는 그릇이기도 하다.

그러므로 언어를 설명할 때에는 다른 무엇보다 단순한 생각을 모아 복잡한 생각을 엮어내는 수단에 무게를 두어야 한다. 좋은 프로그래밍 언어라면 아래와 같은 일을 할 수 있는 세 가지 표현 방식을 갖추고 있다.

---

• 기본 식(Primitive expression) - 언어에서 가장 단순한 것을 나타낸다.
• 엮어내는 수단(means of combination) - 간단한 것을 모아 복잡한 것(compound element)으로 만든다.
• 요약하는 수단(means of abstraction) - 복잡한 것에 이름을 붙여 하나로 다룰 수 있게끔 간추린다.

---

프로그램을 짤 때 우리는 프로시저(procedure)와 데이터(data)라는 두 가지를 쓴다. 쉽게 말해서, 데이터란 프로시저에서 쓰려는 '물건'이고, 프로시저란 데이터를 처리하는 '규칙'을 적은 것이다. 그래서 좋은 프로그래밍 언어에는 기본 데이터(primitive data)와 기본 프로시저(primitive procedure)를 나타내고, 프로시저들과 데이터들을 엮어서 더 복잡한 것을 만들고, 이를 간단하게 요약하는 수단이 반드시 있어야 한다. 

식(expression)

(+ 137 349)    (- 1000 334)     (* 5 99)     (/ 10 5)
    486              666               495           2

여러 식을 괄호로 묶어 리스트(list)를 만들고 프로시저 적용(procedure application)을 뜻하도록 엮어 놓은 식은 엮은식(combination)이라고 한다.

lisp에서는 전위 표기법(prefix notation)을 사용한다. 맨 왼쪽에 있는 식은 연산자(operator)가 되고, 나머지 식은 피연산자(operand)가 된다. 엮은식을 계산한 값은 인자(argument)에 프로시저를 적용하여 얻는다.
prefix notation을 사용하면 인자가 많아져도 따로 문법을 만들 필요 없이 쓰던 그대로 쓸 수 있다는 점이다.

(+ 21 35 12 7)          (* 25 4 12)
    75                         1200

식(combination)을 괄호로 묶어 놓았으니, 인자가 많아졌다고 해서 헷갈릴 게 없다.
식 속에 다시 식을 너허서 식을 여러 겹으로 엮어 늘리기가 쉽다는 점이다.
(+ (* 3 5) (- 10 6))
   19

(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))와 같이 식을 길게 늘어쓰게 되면 알아보기 어려워 실수로 계산을 틀리기 쉽다.
(물론 인터프리터는 아무문제 없이 동작한다.)

그러므로 같은 식을 쓰더라도 아래처럼 정리해서 적으면 알아보기 쉽다. 이와 같이 식을 깊이 겹쳐 써야 할 떄 인자를 중심으로 줄을 맞추고 알맞게 들여 쓰는 방식을 가지런히 쓰기(pretty-printing)라고 한다.
(가독성을 높이기 위함 이러한 기능은 대부분의 편집기에서 지원이 된다.)
(+ (* 3
       (+ (* 2 4)
           (+ 3 5)))
    (+ (- 10 7)
        6))

식이 아무리 복잡해도, 실행기가 하는 일은 언제나 같다. 식을 읽어 드리고 값을 구한 다  음에 그 값을 찍는다. 이를 가리켜 보통, 읽고 셈하고 찍는 일을 되풀이(read-eval-print-loop)한다고 한다. 언어 실행기는 계산한 값을 보여 달라고 따로 청하지 않아도 알아서 셈한 값을 찍어 준다는 사실을 알아두자.

 

연습문제 1.2

5+4+(2-(3-(6+4/5))) / 3(6-2)(2-7)

-> (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (-2 7)))

연습문제 1.3
세 숫자를 인자로 받아 그 가운데 큰 숫자 두개를 제곱한 다음, 그 두 값을 덧셈하여 내놓는 프로시저를 정의하라.
(hint: 3가지 숫자 모두 제곱한 뒤 가장 작은수를 빼면 나머지 2개의 큰 숫자가 남는다.)

   (define (square x) (* x x))
   
   (define (maxNum x y z)
     (cond
       ((and (>= x z) (>= y z)) (+ (square x) (square y)))
       ((and (>= y x) (>= z x)) (+ (square y) (square z)))
       ((and (>= x y) (>= z y)) (+ (square x) (square z)))))    
       

연습문제 1.4
엮은식(combination)의 연산자 자리에 복잡한 식(compound expression)이 다시 와도 앞에서 밝힌 규칙에 따라 식의 값을 구할 수 있다. 다음 프로시저에 인자를 주고 어떻게 계산되는지 밝혀 보라.

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

b가 양수가 들어오면 a와 b를 더함
b가 음수가 들어오면 a와 b를 뺌

 

연습문제 1.5
Ben Bitdiddle은 언어 실행기가 인자 먼저 계산법(applicative order evaluation)을 따르는지 아니면 정의대로 계산법(normal-order evaluation)을 따르는지 알아보고 싶어서 아래와 같이 두 프로시저를 정의하였다.

(define (p) (p))

(define (test x y)
   (if (= x 0)
       0
       y))

그런 다음 아래 식의 값을 구해 보았다.
(test 0 (p))

인자 먼저 계산(applicatvie order evaluation)하는 실행기를 쓴다면 어떤 결과를 보게 될까? 정의한 대로 계산(normal-order evaluation)하는 실행기라면 어떤 결과가 나올까? 저마다 왜 그런 답이 나오는지 밝혀 보라. (if 식을 계산하는 규칙은 인자 먼저 하든지 정의대로 하든지 똑같다고 치자. 다시 말해서, 술어의 답, 곧 참이냐 거짓이냐에 따라 두 식 가운데 하남나 골라서 값을 구한다.)

인자 먼저 계산법(applicatvie order evaluation)의 경우 (test 0 (p))을 실행하게 되면
인자를 먼저 계산하게 되어 (define (p) (p))를 호출하게 된다.
p또한 (define (p) (p))이기 때문에 무한루프인 재귀호출(recursive call)이 된다.
결국 스택오버플로우가 발생하게되어 프로그램은 자동으로 종료된다.

반대로 정의대로 계산법(normal-order evaluation)의 경우 먼저 인자를 계산할 필요가 없다.
(if (= x 0)
     0
     y)
의 프로시저를 먼저 실행하게 된다. x의 값이 현재 0이니 결과적으로 0을 리턴하게 된다.

 

연습문제 1.6

Alyssa P. Hacker는 if가 왜 특별한 형태여야 하는지 받아들이기 어려웠다. "그냥 cond를 써서 if를 보통 프로시저처럼 징의하면 안 될까?" 라고 자신에게 되묻곤 했다. Alyssa의 친구 Eva Lu Ator는 그렇게 할 수 있을 거라고 하면서 if 대신 쓸 수 있는 new-if를 다음처럼 만들어 보았다.

(define (new-f predicate then-clause else-clause)
 (cond (predicate then-clause)
 	(else else-clause)))

Eva는 Alyssa에게 이 프로그램이 if처럼 돌아간다는 걸 보여주려고 아래처럼 실험을 하였다.

(new-if (= 2 3) 0 5)
-> 5

(new-if (= 1 1) 0 5)
-> 0

Alyssa는 좋아하며 다음 제곱근 프로그램에서 new-if를 써보았다.

(define (sqrt-iter guess x)
   (new-if (good-enough? guess x)
             guess
             (sqrt-iter (improve guess x)
                          x)))
Alyssa가 새로 만든 프로시저로 제곱근을 구하려 할 때 어떤 일이 일어나는가?

(define (new-if predicate then-clause else-clause)
      (cond (predicate then-clause)
                    (else else-clause))) 
 
 (define (sqrt-iter guess x)
      (new-if (good-enough? guess x)
              guess
                    (sqrt-iter (improve guess x) x)))
  
  (define (improve guess x)
      (average guess (/ x guess)))
  
  (define (average x y)
      (/ (+ x y) 2))
  
  (define (good-enough? guess x)
      (< (abs (- (square guess) x)) 0.001))
  
  (define (square x)
      (* x x))
 
  (define (sqrt x)
      (sqrt-iter 1.0 x))

 (define (sqrt-iter guess x)
      (new-if (good-enough? guess x)
              guess
                    (sqrt-iter (improve guess x) x)))
                    
부분에서 재귀호출이 일어나서 무한루프를 돌게된다..
scheme 에서는 인자 값을 먼저 평가하는 방식을 사용하기 때문이다. (applicative-order evaluation)
(sqrt-iter (improve guess x) x) 반복...
결과적으로 스택오버플로우가 일어나 프로그램이 종료된다.

 

연습문제 1.7

앞서 만든 good-enough?로는 아주 작은 수의 제곱근을 구하지 못한다. 또 컴퓨터에서 수를 셈할 때에는 유효숫자가 딱 정해져 있다는 점 때문에 아주 큰 수의 제곱근을 구하는 데도 알맞지 않다. 아주 작은 수나 큰 수의 제곱근을 구할 때 good-enough?가 올바로 답을 내지 못하는 보기를 들어 이런 문제를 설명해 보라. good-enough?를 만드는 여러 방법 가운데 하나는, 참 값에 더 가까운 값 guess를 구하기 위해 어림잡은 값을 조금씩 고쳐 나가면서 헌 값에 견주어 고친 값이 그다지 나아지지 않을 때까지 계산을 이어가는 것이다. 이 방법에 따라 위에서 만든 제곱근 프로시저를 고쳐 보자. 그렇게 고치고 나니, 아주 작은 수나 큰 수의 제곱근을 구할 때 전보다 잘 돌아가는가?

잉?
컴퓨터로 표현할 수 있는 수가 제한 되어 있기 때문에 이를 해결 하는 문제인건데
어떤식으로 알고리즘을 구성해야 될지?

답을 찾아보니

1.7 문제 응용버전 이였다...

(define (good-enough? guess x) 
  (< (abs (- (improve guess x) guess)) 
     (* guess 0.000000001))) 
  
  기존 guess의 값의 차이가 0.001보다 크게 발생할 경우 무한루프를 빠지게 되었다.
 0.001 값을 바꾸어 주게 되면 해결이 된다.
 (사실 지금도 완벽히 이해하진 못했음)

전체코드

1 (define (new-if predicate then-clause else-clause)
  2         (cond (predicate then-clause)
  3                                   (else else-clause)))
  4 
  5  (define (sqrt-iter guess x)
  6          (if (good-enough? guess x)
  7                                guess
  8                             (sqrt-iter (improve guess x) x)))
  9 
 10   (define (improve guess x)
 11           (average guess (/ x guess)))
 12 
 13   (define (average x y)
 14           (/ (+ x y) 2))
 15 
 16    (define (good-enough? guess x)
 17        (< (abs (-(improve guess x)guess ))
 18                (* guess .0000001)))
 19 
 20   (define (square x)
 21           (* x x))
 22 
 23   (define (sqrt x)
 24           (sqrt-iter 1.0 x))

연습문제 1.8

세제곱근(cube root)을 구하는 뉴튼 법은, x의 세제곱근에 가까운 값을 y라고 할 때 다음 식에 따라 y보다 더 가까운 값을 계산하는 것이다.

x/y*y + 2y / 3

제곱근 프로시저처럼, 이 식을 써서 세제곱근 프로시저를 짜보자. (1.3.4절에서 제곱근과 세제곱근을 간추려, 더 쓰임새가 넓은 뉴튼 방법을 어떻게 표현할 수 있는지 보게 된다.)

연습문제 1.7 응용

1 (define (square x) (* x x))
  2 
  3 (define (cube-root-iter guess prev_guess x)
  4   (if (good-enough? guess prev_guess)
  5     guess
  6     (cube-root-iter (improve guess x) guess x)))
  7 
  8 (define (improve guess x)
  9   (average3 (/ x (square guess)) guess guess))
 10 
 11 (define (average3 x y z)
 12   (/ (+ x y z) 3))
 13 
 14 (define (good-enough? guess prev_guess)
 15   (< (abs (- guess prev_guess)) (abs (* guess 0.001))))
 16 
 17 (define (cube-root x)
 18   (cube-root-iter 1.0 0.0 x))