프로그램 식 조합 방법 <expr> ::= <constant> | <name>

Presentation on theme: "프로그램 식 조합 방법 <expr> ::= <constant> | <name>"— Presentation transcript:

1 프로그램 식 조합 방법 <expr> ::= <constant> | <name>
| (<expr> <expr>*) | … <constant> ::= <number> | + | - | … | <string> | stringlength | … | <bool> | and | or | … Notation: <a> = a라는 구조물 … = 기타등등 더 있다 <a>+ = a라는 구조물이 1개 이상 <a>* = a라는 구조물이 0개 이상

2 속내용감추기 = 이름짓기 (define <name> <expr>)

3 조건식 (if <expr> <expr> <expr>)
rule of evaluation: 첫번째 식 계산; #t 이면 두번째 식 계산, #f 이면 세번째 식 계산. (if (= x y) (+ x x) (square y))

4 조건식 혹은 설탕구조로 (cond (<expr> <expr>)+)
(cond (<expr> <expr>)+ (else <e>)) 설탕구조 syntactic sugar라고 한다 지금있는 것 가지고 표현할 수 있는 문법구조 새로운 것을 할 수 있는 것은 아니다. 달콤하기만. 영양가 없슴 그 설탕은 이렇게 녹는다 (cond (<e1> <e1’>) (<e2> <e2’>) (else <e3’>)) = (if <e1> <e1’> (if <e2> <e2’> <e3’>) )

5 <expr> ::= <constant>
| <name> | (<expr> <expr>*) | (if <expr> <expr> <expr>) | (cond (<expr> <expr>)+ ) | (cond (<expr> <expr>)+ (else <expr>) ) | …

6 함수에 이름짓기 abstraction by functions/procedures
똑 같이 반복되는 일들이 있으면 하나의 함수로 요약하자 함수의 인자들에 이름을 붙이고 그 이름을 가지고 하는일을 표현: parameterization x+1, x*x, 2*x + y 그 함수를 다양한 인자값에 적용할 수 있다 그 함수에 이름을 붙이고, 그 함수대신에 그 이름으로!

7 함수식 만들기 함수식 만드는 방법 = 변수에 이름 붙이기 + 변수가지고 할일 정의하기
(lambda (<name>*) <expr>) x+1 은 (lambda (x) (+ x 1)) 2*x+y는 (lambda (x y) (+ (* 2 x) y)) 3 은 (lambda () 3) 혹은 (lambda (x) 3) 함수에 이름붙이기 (define <name> <expr>) (define succ (lambda (x) (+ x 1))) 아니면, 보기좋도록 (설탕구조로) (define (<name> <name>*) <expr>) (define (succ x) (+ x 1)) (define (formula x y) (+ (* 2 x) y))

8 <expr> ::= <constant>
| <name> | (<expr> <expr>*) | (if <expr> <expr> <expr>) | (lambda (<name>*) <expr>) | … <special-form> ::= (define <name> <expr>) | (define (<name> <name>*) <expr>)

9 함수식은 함수값을 계산한다 Lambda-Exprs Evaluate to Functions/Procedures
(lambda (x) (+ x 1)) evaluates to a function/procedure that increments parameter is x, to do is (+ x 1) (lambda (x y) (+ x y)) evaluates to a function/procedure that adds parameters are x and y, to do is (+ x y) (lambda (x y z) (+ (* x y) z)) evaluats to a function/procedure that does multiply and add parameters are x and y and z, to do is (+ (* x y) z)

10 함수식에 이름붙이기 (define succ (lambda (x) (+ x 1)))
(define formula (lambda (x y) (+ (* 2 x) y))) (define mong (lambda () ( ))) 혹은 (define (succ x) (+ x 1)) (define (formula x y) (+ (* 2 x) y)) (define (mong) ( ))

11 함수의 사용: 함수값의 적용 function application 계산법
(<expr> <expr>*) ((lambda (x) (+ x 1)) 1) (succ 1) 함수의 몸통이 정한 일(to do)를 진행 함수의 인자이름들이 계산된 인자값을 뜻한다고 정의된 환경에서 함수의 몸통을 계산

12 함수값의 적용 적극적인 계산법 eager evaluation
(succ (+ 7 8)) succ을 계산; 함수값이 나옴: param x, todo (+ x 1); (+ 7 8)를 계산; 15가 나옴; param x가 15라고 정의하고 todo (+ x 1)를 실행; x를 계산; 15가 나옴; … 16이 나옴; 결과값은 16.

13 참고: 또다른 계산법 소극적인 계산법 lazy evaluation
(succ (+ 7 8)) succ을 계산; 함수값이 나옴: param x, todo (+ x 1); (+ 7 8)를 계산하지 말고 todo의 x 자리에 껴넣고; (+ (+ 7 8) 1)를 계산; 16이 나옴; 결과값은 16.

14 적극적 vs 소극적인 eager eval vs lazy eval
한번만 계산 반복해서 계산 불필요한 계산 필요한 것만 계산 두가지 계산법은 서로 비교 불가능 Scheme은 적극적인 계산법 선택

15 함수는 인자의 이름과 상관없이 같은 것은 같다 (define (add1 x) (+ x 1))
(define (add1 y) (+ y 1)) 같은 일을 하는 함수지만 내부가 다르게 정의될 수 있다 (define (add1 x) (+ (- x 1) 2))

16 이름 짓는 대상의 수준이 점점 올라가면서 프로그램의 복잡성을 관리하게 된다.
레벨 1: 기초적인 값에 이름짓기 (define pi 3.14) (define area (* pi (* 10 10))) 레벨 2: 함수/프로시져에 이름짓기 (define add1 …) (define square …) 레벨 3: 이름들의 묶음에 이름짓기 (보따리, “module”, “package”, “class”, “file”, etc.) …

17 프로그램식과 그 타입 프로그램식의 계산결과는 값 타입은 값의 종류 int 1 : 1 string “a” “a” : bool
#f #f : pi 3.14 : real 32.4 real (+ 1 (* pi 10)) :

18 함수식의 타입 (lambda (x) (+ x 1)) : num -> num
(lambda (x y) (+ (* 2 x) y)) : num * num -> num Type표기법: int, real, string, bool, t1 * t2 = t1과 t2의 짝 t1 -> t2 = t1에서 t2로 가는 함수

19 프로그램은 타입이 맞아야 typeful programming
(<expr1> <expr2>) 가 타입이 맞으려면 <expr1> : t1 -> t2 이고 <expr2> : t1 이어야 (+ 1 2)는 타입이 맞다, 왜냐하면 + : int * int -> int 1 : int, 2 : int (add1 1)은 타입이 맞다, 왜냐하면 add1 = (lambda (x) (+ x 1)) : num -> num 1 : int 이고 int는 num이다. (1 2) untypeful

20 프로그램짜기는 각 타입마다 두가지 폼으로 춤추기
프로그램짜기는 각 타입마다 두가지 폼으로 춤추기 그 타입의 값을 만들기, 그리고 사용하기 introduction elimination num 1, 2, -3.0, (+ <expr>+) bool #t, #f (and <expr>+) string “바보” (strlength <expr>) t1 -> t2 (lambda (x) (<expr> <expr>) (+ x 1)

21 이름의 유효범위 scope 이름짓기를 하다보면 이름의 유효범위를 제한하고 싶다
이름을 재사용하고 싶다 지은 이름을 필요이상으로 알리고 싶지 않다 이미 우리는 이름의 유효범위가 제한되는 경우를 목격했다 함수가 적용될 때 일어나는 일을 상기해 보자: 함수의 인자이름들이 계산된 인자값을 뜻한다고 정의된 환경에서 함수의 몸통을 계산 (define (add1 x) (+ x 1)) 인자이름 x의 유효범위는 함수의 몸통이고, 몸통을 벗어나면 그 x는 더 이상 유효하지 않다.

22 이름의 유효범위 제한하기 (lambda (<name>*) <expr>)
(let ((<name> <expr>)+) <expr1>) <name>은 <expr>값의 이름 <name>의 유효범위는 <expr1>으로 제한됨 (let ((x 10) (y 1)) (+ x y))

23 <expr> ::= <constant>
| <name> | (<expr> <expr>*) | (if <expr> <expr> <expr>) | (lambda (<name>*) <expr>) | (let ((<name> <expr>)+) <expr> ) | …

24 이름짓기와 유효범위는 수리 논술의 2000년 전통 Theorem. The intersection of all addition-closed sets is addition-closed. Proof. Let S be the intersection set. Let x and y be elements of S. Because x and y are elements of every addition-closed set, their addition must be included in every addition-closed set hence in S. End.

25 let-expr도 사실은 설탕이란다 = procedure + application
(let ((<name> <expr>)) <expr1>) = ( (lambda (<name>) <expr1>) <expr0>) (let ( (x 8) ) (+ x 1)) = ( (lambda (x) (+ x 1)) 8) (let ((x 8) (y 9)) (+ x y)) = ( (lambda (x y) (+ x y)) 8 9) (let ((x 8) (y x)) (+ x y)) = ( (lambda (x y) (+ x y)) 8 x)

26 define-form도 사실은 거의 설탕이란다
(define <name> <expr>) <expr’> = (let ((<name> <expr>)) <expr’>) 프로그램 = <define-form>* <expr> 은 설탕이다. 녹으면 하나의 <let-expr>이다. (define <name1> <expr1>) (define <name2> <expr2>) <expr> = (let ((<name1> <expr1>)) (let ((<name2> <expr2>)) <expr>)) 따라서 프로그램 = <expr>

27 중첩된 define이라는 설탕이 녹으면 (define <name1>
(define <name2> <expr2>) (define <name3> <expr3>) <expr1>) = (define <name1> (let ((<name2> <expr2>)) (let ((<name3> <expr3>)) <expr1>)))

28 (define (집에가서공부하기 x) (define (집에가기 x) …) (define (공부하기 x) …) (define (다잊자 x) …) (다잊자 (공부하기 (집에가기 x))) )

29 유효범위 구분하기 (let ( (x 1) (y 2) ) (+ (let ( (y (+ x 1)) )
scope of x, y (let ( (x 1) (y 2) ) (+ (let ( (y (+ x 1)) ) (let ( (x (* y 3)) ) (+ x y) ) scope of y scope of x

30 유효범위 구분하기 (define (todofor me) (define (gohome x) (+ me x))
(define (study y) (* (gohome me) y)) (define (forget x) (* 0 (study (gohome x)))) (forget (study (gohome me)) ) (todofor )