[프로그래밍 언어/Racket] Thunks, Laziness, Streams, Memoization -컴도리돌이

2020/05/21 - [컴퓨터 전공 공부/프로그래밍언어론] - [프로그래밍 언어/Racket] Racket introduction - 컴도리돌이 -(1)

2020/05/28 - [컴퓨터 전공 공부/프로그래밍언어론] - [프로그래밍 언어/Racket] Thunks, Laziness, Streams, Memoization -컴도리돌이-(2)

2020/06/04 - [컴퓨터 전공 공부/프로그래밍언어론] - [프로그래밍언어/Racket] Macros - 컴도리돌이-(3)

2020/06/11 - [컴퓨터 전공 공부/프로그래밍언어론] - [프로그래밍 언어/Racket] Datatype-Style Programming with Lists or Structs and more - 컴도리돌이-(4)

---

 

Thunks 

 

매개변수를 받지 않는 함수를 Thunking이라 부른다. 

불필요한 계산이나 반복되는 and/or 계산에 의해 생긴 지연(delaying)에서 효과적으로 사용된다.

thunk는 불필요한 계산에서 생기는 비용을 skip 해준다. 하지만 하나 이상의 thunk을 사용하는 것은 바람직한 선택이 아니다.

 

(lambda () e)

 

<example>

(define (my-if-bad x y z)
	(if x y z))
    
(define (fact-bad n)
	(my-if-bad (= n 0) 1 (* n (fact-bad (- n 1))))) 


;thunking을 안해주면 무한루프에 빠진다.


(define (my-if x y z)
	(if x (y) (z)))
    
(define (fact n)
	(my-if (= n 0) (lambda() 1) (lambda() (* n (fact (- n 1)))))) 

(define (f th)
	(if (…) 0 (… (th) …))) ;Great


(define (f th)
		(… (if (…) 0 (… (th) …))
		(if (…) 0 (… (th) …))
		…
		(if (…) 0 (… (th) …)))) ;worse

---

 

Streams

 

일반적으로 stream은 일련의 연속성을 갖는 흐름이라 생각하면 된다.

(음성, 영상, 등의 작은 조각들이 하나의 줄기를 이루며 전송되는 데이터 열이라 생각하면 된다. )

 

 

Using streams

 

racket에서는 pair과 thunks를 사용하여 streams을 표현을 한다.

 

'(next-answer . next-thunk)
; s라는 stream이 주어졌을 때 , 사용자는 리스트에 있는 어느 수를 받을 수 있다.

;First : ( car (s))
;Second : ( car ((cdr (s))))
;Third : (car ((cdr ((cdr ())))))



(define (number-until stream tester)
  (letrec ([f (lambda (stream ans)
                (let ([pr (stream)])
                  (if (tester (car pr))
                      ans
                      (f (cdr pr) (+ ans 1)))))])
    (f stream 1)))

 

Making streams

 

Recursion으로 하나의 thunk 오른쪽에 next thunk을 만들 수 있다.

 

(define ones (lambda () (cons 1 ones)))

(define nats
  (letrec ([f (lambda (x)
                (cons x (lambda () (f (+ x 1)))))])
    (lambda () (f 1))))
    
(define powers-of-two
  (letrec ([f (lambda (x)
                (cons x (lambda () (f (* x 2)))))])
    (lambda () (f 2))))

 

#test case

>(ones)
#'(1 . #<procedure:ones>)

>(define two-and-higher (cdr (nats)))

>(two-and-higher)
#'(2 . #<procedure>)

>((cdr (two-and-higher)))
#'(3 . #<procedure>)

---

Memoization

 

캐시 공유를 사용하는 모든 호출에 대해 수정 가능한 캐시가 필요한다.

 

<example>

(define (fib1 x)
  (if (or (= x 1) (= x 2)
          1
          (+ (fib1 (- x 1))
             (fib1 (- x 2)))))
             
             
(define (fib2 x)
  (letrec ([f (lambda (acc1 acc2 y)
                (if (= y x)
                    (+ acc1 acc2)
                    (f (+ acc1 acc2) acc1 (+ y 1))))])
    (if (or (= x 1) (= x 2))
        1
        (f 1 1 3))))
        
(define (fib3 x)
  (letrec ([memo null] #;memo=(4 . 3) (3 . 2) (1 . 1) (2 . 1))
           [f (lambda (x)
                (let ([ans (assoc x memo)])
                  (if ans (cdr ans)
                      (let ([new-ans (if (or (= x 1) (= x 2))
                                         1
                                         (+ (f (- x 1)) (f (- x 1))))])
                        (begin
                          (set! memo (cons (cons x new-ans) memo))
                          new-ans)))))])
    (f x)))
    
    
#>(fib3 100)
#316912650057057350374175801344

 

assoc 함수는 해당 x 값을 가진 memo를 선택한다.

#assoc example

#>(assoc 10 '( (11 . "11") (10 . "10")))
#'(10 ."10")