Programming Bottom-Up

원문 : http://www.paulgraham.com/progbot.html

Programming Bottom-Up

1993

원문 : http://www.paulgraham.com/progbot.html

It's a long-standing principle of programming style that the functional elements of a program should not be too large. If some component of a program grows beyond the stage where it's readily comprehensible, it becomes a mass of complexity which conceals errors as easily as a big city conceals fugitives. Such software will be hard to read, hard to test, and hard to debug.

프로그램에서 기능 요소가 지나치게 커지지 않도록 하는 방식은 오랜동안 프로그램의 원칙이었다. 프로그램의 특정 요소가 쉽게 읽혀지는 범위를 넘어 커진다면, 마치 대도시에 도망자가 쉽게 숨는 것처럼 오류를 포함하게되는 복잡한 덩어리가 되고 만다. 이런 소프트웨어는 읽기 어렵고, 테스트가 곤란하며, 디버깅이 힘들어진다.

In accordance with this principle, a large program must be divided into pieces, and the larger the program, the more it must be divided. How do you divide a program? The traditional approach is called top-down design: you say "the purpose of the program is to do these seven things, so I divide it into seven major subroutines. The first subroutine has to do these four things, so it in turn will have four of its own subroutines," and so on. This process continues until the whole program has the right level of granularity-- each part large enough to do something substantial, but small enough to be understood as a single unit.

이 원칙을 적용하면, 거대한 프로그램을 작은 조각으로 나누어져야하며, 프로그램이 커질 수록, 더 많이 나누어야한다. 어떻게 프로그램을 나누는가? 전통적인 접근은 탑다운 디자인이라고 한다. "프로그램의 목적은 이들 7가지 일을 하는 것으로, 나는 이를 7가지 주요 부분으로 나누었다. 첫번째 부분은 이들 4가지 일을 함으로, 다시 이를 4개의 작은 부분으로 나눈다"라는 식이다. 이런 절차는 전체 프로그램이 적당한 수준의 조각이 될때까지 행하며, 각각의 부분이 주요한 일을 할정도의 크기이기는 하지만, 단일한 유닛으로 이해가능할 정도까지 한다.

Experienced Lisp programmers divide up their programs differently. As well as top-down design, they follow a principle which could be called bottom-up design-- changing the language to suit the problem. In Lisp, you don't just write your program down toward the language, you also build the language up toward your program. As you're writing a program you may think "I wish Lisp had such-and-such an operator." So you go and write it. Afterward you realize that using the new operator would simplify the design of another part of the program, and so on. Language and program evolve together. Like the border between two warring states, the boundary between language and program is drawn and redrawn, until eventually it comes to rest along the mountains and rivers, the natural frontiers of your problem. In the end your program will look as if the language had been designed for it. And when language and program fit one another well, you end up with code which is clear, small, and efficient.

경 험많은 리스프 프로그래머는 자신의 프로그램을 다른 식으로 분해한다. 탑다운 디자인과 함께, 버텀업(bottom-up) 디자인이라는 원칙을 따른다. 프로그램을 문제에 맞게끔 변형하는 것이다. 리스프에서, 언어를 통해서 프로그램을 짜는 것 뿐 아니라, 언어자체를 프로그램에 맞추어 만들어나간다. 프로그램을 만들어나가면서, "리스프로 어런 이런 연산자가 필요해"라고 생각할 수 있다. 그러면, 이것을 작성해 나간다. 이후 새로운 연산자를 사용하는 것이, 프로그램의 다른 부분을 간결하게 하는 것임을 알게 된다. 마치 두 전선의 경계처럼, 언어와 프로그램의 경계는 서로 오고 가면서, 이따금 강과 산, 또다른 자연적인 경계에 막혀 쉬기도 한다. 종국에는 프로그램은 해당 문제를 위해 디자인된 언어처럼 보인다. 언어와 프로그램이 서로 잘 맞아떨어지므로, 분명하고, 작고, 효율적인 코드의 작성으로 작업은 끝나게 된다.

It's worth emphasizing that bottom-up design doesn't mean just writing the same program in a different order. When you work bottom-up, you usually end up with a different program. Instead of a single, monolithic program, you will get a larger language with more abstract operators, and a smaller program written in it. Instead of a lintel, you'll get an arch.

바 텀업 디자인은 같은 문제를 다른 방식으로 푸는 것에 국한되지 않는 다는 점에서 효과적이다. 바텀업을 하면서, 다른 프로그램으로 끝맺게 된다. 단일하고, 통합된 프로그램 대신에, 더 추상적인 연산자와, 그것으로 작성된 작은 프로그램을 가지는 좀 더 큰 언어를 가지게 된다. 교각대신에 아치를 가지게 된다.

In typical code, once you abstract out the parts which are merely bookkeeping, what's left is much shorter; the higher you build up the language, the less distance you will have to travel from the top down to it. This brings several advantages:

특정한 코드에서는, 도서관리와 같은 것을 추상화한다면, 남은 것은 더 작아진다. 언어를 좀 더 고차원적으로 구성해갈 수록, 위와 아래를 오고 가는 일은 더 적어진다. 이는 상당한 이점을 가진다.

   1. By making the language do more of the work, bottom-up design yields programs which are smaller and more agile. A shorter program doesn't have to be divided into so many components, and fewer components means programs which are easier to read or modify. Fewer components also means fewer connections between components, and thus less chance for errors there. As industrial designers strive to reduce the number of moving parts in a machine, experienced Lisp programmers use bottom-up design to reduce the size and complexity of their programs.

   1. 언어가 더 많은 일을 할 수 있도록 함으로써, 바텀업 디자인은 프로그램이 좀 더 작고, 민첩해질 수 있도록 한다. 더 짧은 프로그램은 많은 부분으로는 나뉘어지지않기 때문에, 더 적은 부분은 쉽게 읽히거나 수정하기 쉬워짐을 의미한다. 더 적은 부분은 또한, 부품간에 더 적은 연결을 의미함으로, 에러의 발생 가능성도 줄여준다. 산업 디자이너들이 기계에서 움직이는 부품의 수를 줄이는 것처럼, 숙련된 리스프 프로그래머는 바텀업 디자인을 사용해서, 프로그램의 크기와 복잡성을 줄인다.

   2. Bottom-up design promotes code re-use. When you write two or more programs, many of the utilities you wrote for the first program will also be useful in the succeeding ones. Once you've acquired a large substrate of utilities, writing a new program can take only a fraction of the effort it would require if you had to start with raw Lisp.

   2. 바텀업 디자인은 코드 재사용성을 늘린다. 두개 혹인 그 이상의 프로그램을 작성한다면, 처음 프로그램에서 작성한 많은 유용한 유틸리티가 이어지는 프로그램에서도 유용하게 상요될 수 있다. 많인 수의 도구를 얻게된다면, 새로운 프로그램을 작성할 때, 아주 작은 노력만 필요하다.

   3. Bottom-up design makes programs easier to read. An instance of this type of abstraction asks the reader to understand a general-purpose operator; an instance of functional abstraction asks the reader to understand a special-purpose subroutine. [1]
   
   3. 바텀업 디자인을 통해서 프로그램은 더 읽기 편해진다. 추상화된 형의 인스탄스를 읽는 사람은 일반적인 연산자로 이해한다. 추상화된 함수의 인스탄스는 전용 목적의 서브루틴으로 이해한다.

   4. Because it causes you always to be on the lookout for patterns in your code, working bottom-up helps to clarify your ideas about the design of your program. If two distant components of a program are similar in form, you'll be led to notice the similarity and perhaps to redesign the program in a simpler way.

   4. 코드의 패턴을 늘 지켜보도록 하기때문에, 바텀업으로 일하는 것은 프로그램을 디자인하는 생각을 더 명확하게 한다. 프로그램중 두개의 요소가 유사한 형태라면, 이 유사성을 발견하고, 프로그램을 더 간단한 방식으로 재디자인하도록 할 수 있다.

Bottom-up design is possible to a certain degree in languages other than Lisp. Whenever you see library functions, bottom-up design is happening. However, Lisp gives you much broader powers in this department, and augmenting the language plays a proportionately larger role in Lisp style-- so much so that Lisp is not just a different language, but a whole different way of programming.

바텀업 디자인은 리스프 이외에도 많은 언어에서 어느 정도 가능하다. 라이브러리 함수등에서도 바텀업 디자인은 발견할 수 있다. 그렇지만 리스프는 이른 분야에서는 더 많은 강력함을 보이며, 리스프 스타일로 더 다양한 역할을 가능케 한다. 리스프는 다른 언어일 분 아니라, 프로그램을 함는 완전히 다른 방식이다.

It's true that this style of development is better suited to programs which can be written by small groups. However, at the same time, it extends the limits of what can be done by a small group. In The Mythical Man-Month, Frederick Brooks proposed that the productivity of a group of programmers does not grow linearly with its size. As the size of the group increases, the productivity of individual programmers goes down. The experience of Lisp programming suggests a more cheerful way to phrase this law: as the size of the group decreases, the productivity of individual programmers goes up. A small group wins, relatively speaking, simply because it's smaller. When a small group also takes advantage of the techniques that Lisp makes possible, it can win outright.

이런 스타일의 개발은 작은 그룹에서 행해질 때 더 효과적임은 분명하다. 그러나, 동시에, 작은 그룹이 할 수 있는 한계를 확장시킨다. 고전적인 맨-먼스에 따른 프레데릭의 책에서는 한 그룹의 프로그래머의 효율성은 크기에 비례하지 않는다. 그룹의 크기가 증가할 수록, 개개인의 효율성은 낮아진다. 리스프 프로그램의 경험상 이 법칙을 좀 더 즐겁게 바꿀 수 있다. 그룹의 크기가 감소함에 따라, 개개인의 효율성은 급증한다. 작은 그룹이 승리하는 이유는 더 작기 때문이다. 작은 그룹이 리스프가 가능한 기법의 이득을 받는다면, 승리는 더욱 자명해진다.

PCL Ch3. save-db load-db 변경하기

환경은 CLISP + emacs + slime

CLISP은 유니코드를 지원한다. 유니코드를 지원하게 하기위해서는

<blockquote>(setq slime-net-coding-system 'utf-8-unix)</blockquote>

라인을 .emacs 에 넣어두어야한다.

우선 여기까지 되었으면 with-open-file 에서 각 stream에 encoding을 정의해주어야한다.
몇가지 예제 파일을 찾다가 Common Lisp Cookbook 에서 힌트를 찾았다.
:external-format을 설정해주면 모든 문제가 일단 OK
아래는 변경한 save-db, load-db이다.

(defun save-db (filename)
  (with-open-file (out filename
                       :external-format (ext:make-encoding :charset 'charset:utf-8 :line-terminator :unix)
                      
                       :direction :output
                       :if-exists :supersede)
    (with-standard-io-syntax (print *db* out))))

(defun load-db (filename)
  (with-open-file (in filename
                      :external-format (ext:make-encoding :charset 'charset:utf-8 :line-terminator :unix))
    (with-standard-io-syntax
      (setf *db* (read in)))))

이상으로 문제는 완료..
이제 유니코드를 사용해도 정상적으로 출력이 된다. 핵심은 역시 (ext: ... ) 부분..

PCL ch4.함수의 정의

* 함수 정의하는 형태

<blockquote>(defun name (parameters)
    "Optional document string"
    bodyform)
</blockquote>

* 파라미터 리스트 : 함수에 전달되는 인자를 받을 변수를 정의한다.
- 필수 파라미터 : 변수 이름의 리스트
- 옵션 파라미터

<blockquote>(defun foo (a b &optional c) ... )<br /></blockquote>

• a, b 두 인자는 필수 파라미터이다. 따라서 먼저 두 변수에 값이 할당된다.
• 이후에도 남은 값이 있다면 그때 c에 할당된다.

- 디폴트 값 넘기기
옵션 파라미터에 디폴트 값을 넣고 싶다면 다음과 같이 사용한다.

<blockquote>(defun foo (a b &optional (c 10)) ... )</blockquote>

만약 주어진 옵션 파라미터에 값이 등록되었는지를 알고 싶다면 "-supplied-p" 변수를 이용할 수 있다. 해당하는 변수가 등록되었다면 T, 그렇지 않다면 NIL 이다.

<blockquote>(defun foo (a b &optional (c 0 c-supplied-p)) <br />     (list a b c c-supplied-p))</blockquote>

- Rest 파라미터 : 여러 개의 인수를 받고자할 때 사용한다.

<blockquote>(defun foo (a b &rest c) ... )</blockquote>

- Keyword 파라미터 : 어떤 인수가 어떤 변수로 매핑될지 일일이 정하고 싶다면 사용한다. 또한 &optional 에서 처럼 기본값과 등록되었는지 확인하는 변수 모두 사용이 가능하다.

<blockquote>(defun foo (&keyword a b (c 0) (d 0 d-supplied-p)) (list a b c d d-supplied-p)) </blockquote>

해당하는 값을 등록하고 싶다면 :a :b 식으로 :을 변수명 앞에 붙여 값을 가져올 수 있다.

* Return 값 강제하기

- RETURN-FROM, BLOCK
BLOCK으로 해당 블록의 이름을 정한 후 RETURN-FROM을 이용해 해당 블록에서 탈출한다. 기본적으로 함수정의안에서는 함수 이름자체가 하나의 블록으로 취급된다.

<blockquote>(defun foo (n)<br />  (dotimes (i 10)<br />    (dotimes (j 10)<br />      (when (> (* i j) n)<br />        (return-from foo (list i j))))))</blockquote>

* 고차 함수 (Higher-order function)

- LAMBDA, FUNCALL, APPLY

일반적으로 함수를 사용한다는 것은 다음과 같다.

<blockquote>(foo 1 2 3) == (funcall #'foo 1 2 3) </blockquote>

이때 #'는 해당하는 함수를 찾아오는 함수이다. 일종의 함수 포인터 연산이라고 생각해도 되겠다. (Scheme과는 달리 LISP은 변수공간과 함수 공간이 구분되어있다.)

apply는 funcall과 유사하지만 개별 인자들을 일일이 가져오는 형식이 아니고, 리스트 자체를 받아오는 경우에 사용한다.

lambda는 이름없는 함수를 만들 수 있다.

<blockquote>(funcall #'(lambda (x y) (+ x y)) 3 5) ==> 8</blockquote>

연습문제 4.6

(define (let? exp)
  (tagged-list? exp 'let))

(define (let-body exp)
  (caddr exp))

(define (let-vars exp)
  (let ((var-exp-list (cadr exp)))
    (map car var-exp-list)))

(define (let-exps exp)
  (let ((var-exp-list (cadr exp)))
    (map cadr var-exp-list)))

(define (let->combination exp)
  (cons 
   (make-lambda (let-vars exp)
                (let-body exp))
   (let-exps exp)))

연습문제 4.4

<blockquote>(define (eval-and exp env)
  (if (null? exp)
      #t
      (let ((test (car exp)))
        (if (eval test)
            (eval-and (cdr exp) env)
            #f))))

(define (eval-or exp env)
  (if (null? exp)
      #f
      (let ((test (car exp)))
        (if (eval test)
            #t
            (eval-or (cdr exp) env)))))

(define (and? exp)
  (tagged-list? exp 'and))

(define (or? exp)
  (tagged-list? exp 'or))
</blockquote>

좀 아리까리함..

연습문제 4.3

(define eval-table (make-table))
(define get (eval-table 'lookup-proc))
(define put (eval-table 'insert-proc!))

(define (eval-quoted exp env)
  (text-of-quotation exp))

(define (eval-set exp env)
  (eval-assignment exp env))
(define (eval-define exp env)
  (eval-definition exp env))
(define (eval-if. exp env)
  (eval-if exp env))
(define (eval-lambda exp env)
  (make-procedure (lambda-parameters exp)
                  (lambda-body exp)
                  env))
(define (eval-begin exp env)
  (eval-sequence (begin-actions exp) env))
(define (eval-cond exp env)
 (eval (cond->if exp) env))
(put 'quote eval-quoted)
(put 'set eval-set)
(put 'define eval-definition)
(put 'if eval-if.)
(put 'lambda eval-lambda)
(put 'begin eval-begin)
(put 'cond eval-cond)


(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((get (car exp))
         ((get (car exp)) exp env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) evn)))
        (else
         (error "Unknown expression type -- EVAL" exp))))

연습문제 4.2

a. 프로시저 적용이 우선되게될 때 (define x 3)를 예로 들어 보자.
이 경우 eval은 (define x 3)를 define 정의 식이 아니라, 일반 프로시저로 인식하게 된다.
따라서 define이라는 프로시저에 (x 3) 을 넣어 해당하는 결과를 수행하도록 식을 평가하게된다. 따라서, application이 무리하게 먼저 실행되면 심각한 문제가 발생하게된다.

b. 굳이 application을 call을 사용해서 수행하고 싶다면 다음과 같이 변경한다.

<blockquote>
(define (application? exp) (tagged-list? exp 'call))
(define (operator exp) (cadr exp))
(define (operands exp) (cddr exp))</blockquote>

연습문제 4.1

(define (list-of-values exps env)
  (if (no-operands? exps)
      '()
      (let ((left-values (eval (first-operands exps))))
        (let ((right-values (list-of-values (rest-operands exps))))
          (cons left-values right-values)))))

오른쪽부터 셈하도록 하려면 left-values와 right-values의 위치를 바꿔주면 된다.