SNU 4190.210 프로그래밍 원리 (Principles of Programming) Part III Prof. Kwangkeun Yi
차례 1 값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 2 프로그램의이해 : 환경과메모리 (environment & memory)
다음 1 값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 2 프로그램의이해 : 환경과메모리 (environment & memory)
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 양쪽프로그래밍방식에능숙해야 값 : 변하지않는다 (value, immutable)
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 양쪽프로그래밍방식에능숙해야 값 : 변하지않는다 (value, immutable) (+ 2 1) 는 3을의미 ; 2가변해서 3이되는것이아님.
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 양쪽프로그래밍방식에능숙해야 값 : 변하지않는다 (value, immutable) (+ 2 1) 는 3을의미 ; 2가변해서 3이되는것이아님. (add-element 1 S) 는 S {1} 인집합을의미. S에 1 이첨가된, 변화된 S를의미하지않음.
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 양쪽프로그래밍방식에능숙해야 값 : 변하지않는다 (value, immutable) (+ 2 1) 는 3을의미 ; 2가변해서 3이되는것이아님. (add-element 1 S) 는 S {1} 인집합을의미. S에 1 이첨가된, 변화된 S를의미하지않음. 지금까지의프로그래밍방식 ( 상위의. 수리논술방식 )
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 물건 : 상태가변한다 (state, mutable)
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 물건 : 상태가변한다 (state, mutable) (add-element S 1) 는집합 S가변해서 1 이첨가된새로운집합이됨.
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 물건 : 상태가변한다 (state, mutable) (add-element S 1) 는집합 S가변해서 1 이첨가된새로운집합이됨. 물건의상태를변화시키는, 이런프로그램이필요한경우도많다. ( 예 : 1-데이타 n-구현을돕던 함수 테이블 )
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 물건 : 상태가변한다 (state, mutable) (add-element S 1) 는집합 S가변해서 1 이첨가된 새로운집합이됨. 물건의상태를변화시키는, 이런프로그램이필요한 경우도많다. ( 예 : 1-데이타 n-구현을돕던 함수 테이블 ) 변하므로, 순서가중요.
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 물건 : 상태가변한다 (state, mutable) (add-element S 1) 는집합 S가변해서 1 이첨가된 새로운집합이됨. 물건의상태를변화시키는, 이런프로그램이필요한 경우도많다. ( 예 : 1-데이타 n-구현을돕던 함수 테이블 ) 변하므로, 순서가중요. 물건의상태를변화시키는명령형프로그래밍방식
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 예 : (append l r) 함수 값중심 (value, immutable): l 과 r 은변하지않음. (define (append l r) (cond ((null? l) r) ((null? r) l) (else (cons (car l) (append (cdr l) r))) )) 물건중심 (state, mutable): l 이변해서 l@r 이됨. (define (append l r) (cond ((null? ((null? r) l) l) (begin (change l r) l)) (else (begin (change (cdr l) (append (cdr l) r)) l)) ))
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 프로그래밍언어들은대개 두가지방식을모두구사할수있는방안을제공 단, 기본으로지원하는방식이있고, 원한다면다른방식도가능 Scheme: 값중심 > 물건중심 ML: 값중심 > 물건중심 Java: 물건중심 > 값중심 C: 물건중심 > 값중심 따라서, 데이타속구현에서두방식중하나를 선택해야
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 데이타속구현을두방식중하나로선택. 겉 (interface) 으로드러나는기획의차이 empty : stk vs unit stk push : stk elmt stk vs stk elmt unit is-empty? : stk bool vs stk bool pop : stk elmt stk vs stk elmt
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 데이타속구현을두방식중하나로선택. 속구현의차이
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 데이타속구현을두방식중하나로선택. 속구현의차이 applicative style (define empty ()) (define (push s x) (cons x s)) (define is-empty? null?) (define (pop s) (if (is-empty? s) (error) s))
값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 데이타속구현을두방식중하나로선택. 속구현의차이 applicative style (define empty ()) (define (push s x) (cons x s)) (define is-empty? null?) (define (pop s) (if (is-empty? s) (error) s)) imperative style (define empty (cons 0 0)) (define (push s x) (let ((cell (cons x nil))) (begin (set-cdr! cell (cdr s)) (set-cdr! s cell)) )) (define (is-empty? s) (= 0 (cdr s))) (define (pop s) (if (is-empty? s) (error) (let ((top (cadr s))) (begin (set-cdr! s (cddr s)) (cons top s)) )))
값중심프로그래밍 (applicative programming) 원 리 값은변하지않는것 함수는값을받아새로운값을만든다 값들은변하지않으므로최대한공유하도록구현될수있다 See: 기계에서구현되는 (append l r), (add-element S 1) ( 예 : S = {0, 2, 3, 4, 5, 6})
물건중심프로그래밍 (imperative programming) 원리 물건은그상태가변하는것 함수는물건을받아기존의물건을변화시킬수있다 물건은변하므로공유하도록구현되면혼동스러울수있다 See: 기계에서구현되는 (append l r), (add-element S 8) 변하는중간에사용되므로, 순서가중요
값중심과물건중심구현의비용비교 S = {0, 2, 3, 4, 5, 6} 구현 : 이진탐색가지구조 (binary search tree) 다음함수의구현 : (add-element S 9)
값중심과물건중심구현의비용비교 다음함수의구현 : (add-element S 9)
값중심과물건중심구현의비용비교 다음함수의구현 : (add-element S 9) 변화시키면서 (imperative style)
값중심과물건중심구현의비용비교 다음함수의구현 : (add-element S 9) 변화시키면서 (imperative style) 변화없이 (applicative style)
값중심과물건중심구현의비용비교 원소를넣는경우 변화된새것만유지하면되는경우 time space imperative O(log N) O(1) applicative O(log N) O(1) 옛것과새것모두유지해야하는경우 time space imperative O(N) O(N) applicative O(log N) O(log N)
다음 1 값중심 vs 물건중심프로그래밍 (applicative vs imperative programming) 2 프로그램의이해 : 환경과메모리 (environment & memory)
환경과메모리 (environment & memory) 프로그램실행을이해하는데필요한두개의실체
환경과메모리 (environment & memory) 프로그램실행을이해하는데필요한두개의실체 환경 : 프로그램에서정의된이름들과그대상의목록표 환경은여럿 : 프로그램의어디를실행하냐에따라다른환경이사용됨 유효범위에따라변화하는이름의대상을파악하는데필요
환경과메모리 (environment & memory) 프로그램실행을이해하는데필요한두개의실체 환경 : 프로그램에서정의된이름들과그대상의목록표 환경은여럿 : 프로그램의어디를실행하냐에따라다른환경이사용됨 유효범위에따라변화하는이름의대상을파악하는데필요 메모리 : 이름이지칭하는그대상 ( 값이나물건 ) 을 구현하는공간 메모리는하나 : 메모리는프로그램시작때부터 끝날때까지하나 실행중에변화하는물건을이해하는데필요. 구현된 공간에서물건들이변화.
환경과메모리 (environment & memory)
환경 (environment) 환경은이름들이무엇을지칭하는지를알려주는 테이블 이름과그대상의쌍 (binding) 들의테이블 모든프로그램식의실행은주어진환경아래에서진행된다 환경은프로그램식을바라보는안경 (+ x y) 의실행결과는? 다른환경에서다른실행결과를냄
환경 (environment) 관리 환경만들기 : 이름이지어지면 환경참조하기 : 이름이나타나면 환경폐기하기 : 유효범위가끝나면
새로운환경이도입되는경우 이름짓는경우 (binding, declaration, definition) 식에서이름짓기 E ::= 예전것들 (let ((x E) + ) E) x의정의 (letrec ((x E) + ) E) x의재귀정의 (E E) 함수호출시함수인자가 프로그램에서이름짓기 P ::= E 계산식 (define x E) E 이름정의후계산식
메모리의물건을변화시키는경우 변화시키는명령문 (mutation, imperative operations) Scheme: set!, set-car!, set-cdr! OCaml: 지정문 (:=) Java, C, C++ 등 : 모든지정문 (=)
함수와환경 함수 = 함수텍스트정의와함수가정의될때의환경
함수와환경 함수 = 함수텍스트정의와함수가정의될때의환경 (let ((y 1)) (let ((udd (lambda (x) (+ x y)))) (let ((y 10)) (udd 8))))
환경모델이해하기
환경모델이해하기 (define x 1)
환경모델이해하기 (define x 1) (set! x (+ x 1))
환경모델이해하기 (define x 1) (set! x (+ x 1)) (* (let ((x (+ x 2))) (+ x 3)) x)
환경모델이해하기 (define x 1) (set! x (+ x 1)) (* (let ((x (+ x 2))) (+ x 3)) x) (define f (lambda (n) (+ n x)))
환경모델이해하기 (define x 1) (set! x (+ x 1)) (* (let ((x (+ x 2))) (+ x 3)) x) (define f (lambda (n) (+ n x))) (f 10)
환경모델이해하기 (define x 1) (set! x (+ x 1)) (* (let ((x (+ x 2))) (+ x 3)) x) (define f (lambda (n) (+ n x))) (f 10) (let ((x 100)) (f 10))
환경모델이해하기 (define (make-counter n) (lambda () (begin (set! n (+ n 1)) n) )) (define tic1 (make-counter 0))
환경모델이해하기 (define (make-counter n) (lambda () (begin (set! n (+ n 1)) n) )) (define tic1 (make-counter 0)) (tic1) (tic1)
환경모델이해하기 (define (make-counter n) (lambda () (begin (set! n (+ n 1)) n) )) (define tic1 (make-counter 0)) (tic1) (tic1) (define tic2 (make-counter 0))
환경모델이해하기 (define (make-counter n) (lambda () (begin (set! n (+ n 1)) n) )) (define tic1 (make-counter 0)) (tic1) (tic1) (define tic2 (make-counter 0)) (tic2)
환경모델이해하기 (define (make-counter n) (lambda () (begin (set! n (+ n 1)) n) )) (define tic1 (make-counter 0)) (tic1) (tic1) (define tic2 (make-counter 0)) (tic2) (tic1)
환경모델이해하기 (define (make-withraw balance) (lambda (amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "insufficient fund" ))) (define withdraw (make-withdraw 100)) (withdraw 10) (withdraw 20)
환경모델로이해하기 (define empty (cons () ())) (define (push s x) (let ((cell (cons x ()))) (begin (set-cdr! cell (cdr s)) (set-cdr! s cell))
환경모델로이해하기 (define empty (cons () ())) (define (push s x) (let ((cell (cons x ()))) (begin (set-cdr! cell (cdr s)) (set-cdr! s cell)) (define stk empty) (push stk 1) (push stk 2)