List Data
• list 만드는 방법
– () : t-list
– cons : t * t-list -> t-list
• list 사용하는 방법
– car : t-list -> t
– cdr : t-list -> t-list
– null? : t-list -> bool
List Programming Patterns
• 만들어 올리기
– (define (build from to) …)
• 타고 내려가기
– (define (length lst) …)
• 타고 내려가며 만들어 올리기
– (define (append lst1 lst2) …)
• 접어 모으기
– (define (accumulate lst) …)
• 걸러내기
– (define (filter p lst) …)
Programming On Structured Data
• 데이터의 구조는 데이터를 만드는 방법들 의 조합으로 결정된다 :
– 예 ) 리스트 (1 2 3 4) 는 :
nil,cons,cons,cons,cons 로 구성
• 데이터를 다루는 프로그램은 데이터의 구 조를 따라서 일을 한다
List Data Abstraction
• list 를 만들고 사용하는 방법 (how) 이 무엇 인지 이름으로 감춘다 .
• 외부에서는 그 이름만 사용해서 프로그램한 다 .
• list 만드는 방법
– nil : t-list
– link : t * t-list -> t-list
• list 사용하는 방법
– first : t-list -> t
– rest : t-list -> t-list
– empty? : t-list -> bool
Data Abstraction Concept
nil, link, first, rest, empty?
programs that use list
implementation 1 implementation 2
List Programming Patterns
• 만들어 올리기
– (define (build from to) …)
• 타고 내려가기
– (define (length lst) …)
• 타고 내려가며 만들어 올리기
– (define (append lst1 lst2) …)
• 접어 모으기
– (define (accumulate lst) …)
• 걸러내기
– (define (filter p lst) …)
(define nil ())
(define link cons) (define first car) (define rest cdr)
(define empty? null?)
Implementation of List Data (1)
Implementation of List Data (2)
(define nil ())
(define (link x lst) (lambda (f) (f x lst))) (define (first lst) (lst (lambda (x y) x))) (define (rest lst) (lst (lambda (x y) y))) (define empty? null?)
(first (link 1 nil))
(first (rest (link 1 (link 2 nil))))
Implementation of List Data (3)
(define nil ())
(define (link x lst)
(define (I-am-cons m) (cond ((equal? m ‘f) x) ((equal? m ‘r) lst)
(else (error “unknown message”)) ))
I-am-cons)
(define (first lst) (lst ‘f)) (define (rest lst) (lst ‘r)) (define empty? null?)
Data Abstraction 이 좋은점
• 데이터를 만들고 사용하는 사람은 아래 다섯개만 사용해서 프로그램한다 . t-list 가 어떻게 구현되 었는지 알바 없다 .
– nil: t-list
– link: t * t-list -> t-list – first: t-list -> t
– rest: t-list -> t-list
– empty?: t-list -> bool
• 구현된 속내용을 바꾸어도 프로그램의 다른 부분 은 상관없다 .
• 구현된 속내용을 바꾸고 싶은 경우 위의 다섯개만 바꾸면 된다 .
Data Abstraction 의 좋은점이 깨 질 수 있는 여지
• 혹시 프로그래머가 다음과 같이 프로그램하면 ?
– … (first (cons 1 (link 2 nil)))…
– t-list 가 cons 로 구현되었다면 잘 돌고
– t-list 가 다른방식으로 구현되었다면 안 돈다 .
– t-list 를 cons 에서 새로운 방법으로 구현하게 되면 , 잘 돌던 것이 갑자기 돌지않게된다 .
• 프로그래머가 그렇게 “요약의 경계” (abstraction barrier) 를 넘나들게 하는 것은 좋지않다 .
– 그런 프로그램이 짜지지 않게 하려면 어떻게 해야 할까 ? – 그런 프로그램인지 아닌지 자동으로 확인해 주는 도구가
있다면 ? 필요하지 않을까 ?
Data Abstraction Example 2:
Rational Number Data
• rational number 만드는 방법
– make-rat: int * int -> rat
• rational number 사용하는 방법
– numer: rat -> int
– denom: rat -> int
Rational Number Implementations
(define (make-rat a b) (cons a b)) (define (numer r) (car r))
(define (denom r) (cdr r))
(define (make-rat a b) (cons b a)) (define (numer r) (cdr r))
(define (denom r) (car r)) (define (make-rat a b)
(cons (encrypt a) (encrypt b))) (define (numer r) (decrypt (car r)) (define (denom r) (decrypt (cdr r))
