[프로그래밍 클로저] 5장 함수형 프로그래밍

함수형 프로그래밍의 개념

• 함수형 프로그래밍은 코드를 작성하고 읽고 테스트하고 재사용하기 쉽게 만들어준다.

순수 함수

• 함수는 인자 값에 항상 같은 값을 준다.
• 함수는 함수 안에서 side effect가 없다. (I/O도 없고 전역 변수나 인자를 변경하지도 않는다.)

영속적 자료구조

• 변경 불가능한 데이터는 스레드 안정성을 보장한다.
• 오해하지 말아야할것은 함수형 언어가 병행성의 근본적인 문제를 해결해 주지는 않는다. 다만 코딩하는 사람에게 제약을 조금 더 주어 변경을 남발하게 못하게 할 뿐이다.
• 클로저에서 함수는 변경 불가능한 자료를 다루기 때문에 함수의 결과가 새로운 값을 리턴한다.
• 내부적으로는 공유 데이터를 사용하기 때문에 중복 데이터에 대한 성능 문제는 발생하지 않는다.

  (def a '(1 2)')
  -> (1 2)
  (def b (cons 0 a))
  -> (0 1 2)
  ; 사실 a의 첫번째 원소인 1과 b의 두번째 원소인 1은 메모리상 같은 데이터이다.

지연 평가와 재귀

• 지연된 표현식을 평가한다는 것은 그 표현식을 실행한다는 의미이다.
• 순수함수가 아니라면 지연된 시퀀스를 사용수 없다. 생성 시점과 실행 시점의 값이 달라 질 수 있기 때문이다.

참조 투명성

• 참조 투명성이란? 함수의 호출 결과와 함수를 언제든 바꿔 쓸수 있다는 말이다.
• 순수 함수는 참조 투명성을 가진다.
• 참조 투명성을 가지는 함수는 메모이제이션 기법을 사용하거나 다른 실행 환경에서 실행되어도 상관이 없다.

함수형 프로그래밍의 이점

• 재사용이 쉽고 조합이 쉽다

여섯가지 원칙

• 직접 재귀를 사용하지 말자. 자바는 꼬리 최적화가 되지 않는다.
• recur을 사용하자. 작은 규모의 시퀀스를 만들 때 좋다.
• 큰 규모의 시퀀스는 지연 시퀀스로 만든다.
• 지연 시퀀스를 만들때는 필요한 부분 외에 다른 부분이 평가되지 않도록 주의 한다.
• *시퀀스 라이브러리를 사용하자. recur, 지연 시퀀스를 만들기전에 시퀀스 라이브러리가 있다면 최대한 활용한다.
• *쪼개서 정복한다.

어떻게 연산을 지연시킬까 (lester)

• 재귀적 정의

  • 기저(basis): 만들어 내려는 시퀀스 가운데 추론이 필요 없는 매우 명백한 원소
  • 귀납규칙: 기저를 바탕으로 추가적 원소를 만들어 내는 데 필요한 규칙

• 재귀적 정의를 실행되는 코드로 바꾸는 방법

  • 기본적 재귀
  • 꼬리 재귀
  • 지연 시퀀스: 값이 정말로 필요해질 때 계산하는 방법
    • 가장 적합한 경우가 많다.

  ; 피보나치 수열
  ; 나쁜 아이디어
  (defn stack-consuming-fibo [n]
    (cond
      (= n 0) 0 ; 기저
      (= n 1) 1 ; 기저
      :else (+ (stack-consuming-fibo (- n 1)) ; 귀납
               (stack-consuming-fibo (- n 2)))))
  
  (stack-consuming-fibo 9)
  -> 9
  
  (stack-consuming-fibo 1000000)
  -> java.lang.StackOverflowError
  
  ; n에 비례해서 스택 프레임을 성성하기 때문에  

• 꼬리 재귀

  • 함수형 프로그램이 스택을 잡아먹는 문제를 해결할 수 있다.
  • 자신을 호출하는 부분이 함수 정의의 마지막인 반환 값 부분에 와야 한다는 점이 다르다.

  (defn tail-fibo [n]
    (letfn [(fib
             [current next n]
             (if (zero? n)
               current
               (fib next (+ current next) (dec n))))]
      (fib 0 1 n)))
  ; letfn 지역 함수를 바인딩
  
  (tail-fibo 9)
  -> 34
  
  (tail-fibo 1000000)
  -> java.lang.StackOverflowError
  ; 자바 가상 머신의 문제

• recur를 이용한 자체 재귀

  • 자바 가상 머신에서도 최적화할 수 있는 한 가지 특수한 경우

  (defn recur-fibo [n]
    (letfn [(fib
             [current next n]
             (if (zero? n)
               current
               (recur next (+ current next) (dec n))))]
      (fib 0 1 n)))
  
  (recur-fibo 9)
  -> 34
  
  (recur-fibo 1000000)
  -> 195 ...
  

  ; letfn 지역 함수를 바인딩

• 지연 시퀀스

  • lazy-seq 매크로

  (lazy-seq & body)
  ; body 부분이 꼭 필요할 때만 실행되게 만든다.
  ; 이후에 일어날 호출에 대비해 결과를 캐싱하는 기능도 갖추고 있다.
  
  (defn lazy-seq-fibo
    ([]
      (concat [0 1] (lazy-seq-fibo 0 1)))
    ([a b]
      (let [n (+ a b)]
        (lazy-seq
          (cons n (lazy-seq-fibo b n))))))
  
  (take 10 (lazy-seq-fibo))
  -> (0 1 1 2 3 5 8 13 21 34)
  
  (rem (nth (lazy-seq-fibo) 1000000) 1000)
  -> 난 error
  
  (take 5 (iterate (fn [[a b]] [b (+ a b)]) [0 1]))
  -> ([0 1] [1 1] [1 2] [2 3] [3 5])
  
  (defn fibo []
    (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
  ; 가장 짧고도 간단하다. 그러나 난 안된다...
  ; 피보나치 수열은 무한 수열이기 때문에 세 번째 원칙에 따라 지연 시퀀스로 구현하는 것이 맞을테고, 다섯 번째 원칙을 따라 기존 시퀀스 함수로 구현할 수 있는지 살펴보는게 좋을 것이다.
  ; 위는 와닿지 않음...
  

• 시퀀스의 실현

  • 실현(realization)될 때, 즉 시퀀스의 일부가 메모리에서 실제로 생성될 때만 자원을 소모한다.

  (def lots-o-fibs (take 100000000 (fibo)))
  -> #'user/lots-o-fibs
  
  (nth lots-o-fibs 100)
  -> 안해봄... 내 repl에서 될리 없음... 이상한 숫자들...
  
  ; 주의할 것
  ; REPL은 평가를 지연하지 않는다.
  
  ; 이렇게 하지 말 것!
  (take 10000000 (fibo))
  
  (set! *print-length* 10)
  -> 10
  
  (take 100000000 (fibo))
  -> (0 1 1 2 3 5 8 13 21 34 ...)
  

• 머리를 쓰지 않기

  ; 컬렉션의 헤드를 참조하는 코드 (이렇게 하지 말 것!)
  (def head-fibo (lazy-cat [0 1] (map + head-fibo (rest head-fibo))))
  
  (take 10 head-fibo)
  -> (0 1 1 2 3 5 8 13 21 34)
  
  (nth head-fibo 1000000)
  -> java.lang.OutOfMemoryError: Java heap space
  ; 문제는 최상위 var인 head-fibo가 컬렉션의 헤드를 참조한다는 것이다.
  ; 지연 시퀀스를 다룰 때는 머리(head)를 안 쓰는 것도 좋은 방법이다.

더욱 게을러지기 (lester)

• 게으름을 피워보자.

  • 기존 시퀀스 함수를 이용함으로써 문제를 해결할 수 있는 경우가 많다.

  [:h :t :t :h :h :h]
  
  (defn count-heads-pairs [coll]
    (loop [cnt 0 coll coll]
      (if (empty? coll)
        cnt
        (recur (if (= :h (first coll) (second coll))
                  (inc cnt)
                  cnt)
                (rest coll))))) 
  (count-heads-pairs [:h :h :h :t :h])
  -> 2
  (count-heads-pairs [:h :t :h :t :h])
  -> 0
  ; 동작하기는 하지만, 바람직한 코드라고 할 수는 없다.
  
  ; 쓸데없이 복잡한 버전, 나은 방식을 뒤에 소개할 것...
  (defn by-pairs [coll]
    (let [take-pair (fn [c]
                       (when (next c) (take 2 c)))]
      (lazy-seq
        (when-let [pair (seq (take-pair coll))]
          (cons pair (by-pairs (rest coll)))))))
  
  (by-pairs [:h :t :t :h :h :h])
  -> ((:h :t) (:t :t) (:t :h) (:h :h) (:h :h))
  
  (defn count-heads-pairs [coll]
    (count (filter (fn [pair] (every? #(= :h %) pair))
                   (by-pairs coll))))
  ; recur를 이용한 기존의 구현보다 훨씬 읽기 쉬울뿐더러,
  ; 인접한 앞면의 쌍을 세고 있다는 것을 명확하게 표현한다.
  
  (partition 2 [:h :t :t :h :h :h])
  -> ((:h :t) (:t :h) (:h :h))
  
  ; partition이 by-pairs와 같은 결과를 내게 하려면,
  ; size에는 2을 step에는 1을 넘기면 된다.
  (partition 2 1 [:h :t :t :h :h :h])
  -> ((:h :t) (:t :t) (:t :h) (:h :h) (:h :h))
  
  (by-pairs [:h :t :t :h :h :h])
  -> ((:h :t) (:t :t) (:t :h) (:h :h) (:h :h))
  
  ; 모두 앞면으로 이루어진 쌍을 세기 위해 사용한 count와 filter 부분 역시 개선 가능하다.
  ; count와 filter는 함께 사용되는 경우가 많기 때문에 둘을 묶어서...
  (use '[clojure.countrib.def :only (defvar)])
  (defvar count-if (comp count filter) "Count items matching a filter")
  
  (count-if odd? [1 2 3 4 5])
  -> 3
  
  (defn
    count-runs
    "Count runs of length n where pred is true in coll."
    [n pred coll]
    (count-if #(every? pred %) (partition n 1 coll)))
  
  (count-runs 2 #(= % :h) [:h :t :t :h :h :h])
  -> 2
  
  (count-runs 2 #(= % :t) [:h :t :t :h :h :h])
  -> 1
  
  (count-runs 3 #(= % :h) [:h :t :t :h :h :h])
  -> 1
  
  (defvar count-heads-pairs (partial count-runs 2 #(= % :h))
    "Count runs of length two that are both heads")
  ; partial을 이용해서 새로운 버전의 count-heads-pairs를 만들고 있다.
  
  (partial count-runs 1 #(= % :h))
  ; 위 코드는 다음 코드의, 좀더 효과적인 표현이다.
  (fn [coll] (count-runs 1 #(= % :h) coll))
  
  ; partial을 이용한 함수의 부분 적용은 커링(currying)과 유사하지만...

• 여러 가지 모습의 def

  • 모두 특수 구문 def의 래퍼
  • defn-는 defn과 유사하지만 private 함수

• 커링과 부분 적용

  • 함수를 커리하게 되면 원래 함수에서 인자 하나가 고정된 새로운 함수를 얻는다.

  ; 모조 커리
  (defn faux-curry [& args] (apply partial partial args))
  
  ; 커리의 용도 중 하나가 부분 적용이다.
  
  ; partial을 사용한 부분 적용
  (def add-3 (partial + 3))
  (add-3 7)
  -> 10
  
  ; faux-curry를 사용한 부분 적용
  (def add-3 ((faux-curry +) 3))
  (add-3 7)
  -> 10
  
  ; 커링은 부분 적용을 수행하는 과정일 뿐이다.
  ; faux-curry는 진짜 커리라고 할 수는 없는데...
  
  ; 모조 커리
  ((faux-curry true?) (= 1 1))
  -> #<... 임의의 함수 이름 ...>
  
  ; 진짜 커리라면 이런 결과가 나온다.
  ((curry true?) (= 1 1))
  -> true
  
  ; 클로저에 커리가 없어도 큰 문제가 되지 않는다.
  ; 커리를 통해 얻고자 하는 것은 partial을 통해서도 달성할 수 있기 때문이다.
  ; 부분 적용(partial application)과 커링(currying)이라는 말을 혼용한다.

다시 재귀로 (joony)

• 클로저는 함수형 프로그래밍의 이상과 자바 가상 머신의 한계 사이에서 적절한 균형을 유지함
  • 예: loop, recur를 이용한 명시적 꼬리 최적화 (TCO)
  • 서로 다른 두 세계이므로 타협도 필요, 타협점이 중요한 순간에 발목을 잡진 않을까?

상호재귀

• my-odd?와 my-even?이 서로를 호출하기 때문에 각 함수 정의 전에 둘에 해당하는 var선언이 필요
  • (declare &names) declare는 이름들을 인자로 받아, 각각의 이름을 def로 선언해주는 매크로

(declare my-odd? my-even?)

(defn my-odd? [n]
  (if (= n 0)
    false
    (my-even? (dec n))))

(defn my-even? [n]
  (if (= n 0)
    true
    (my-odd? (dec n))))

(map my-even? (range 10))
=> (true false true false true false true false true false)

(map my-odd? (range 10))
=> (false true false true false true false true false true)

• my-odd?와 my-even?은 인자 크기에 비혜해 스택을 소모하기 때문에, 큰 값을 넣으면 제대로 작동하지 않음

(my-even? (* 1000 1000 1000))
=> java.lang.StackOverflowError: null

• 앞서 recur를 도입하게 만든 문제와 비슷. but 여기서는 recur로 문제를 해결하지 못하는데, recur를 상호 재귀에 적용할 수 없기 떄문.

• odd/even을 재귀 '없이' 효율적으로 구현하는 것도 가능. 클로저는 bit-and를 이용해 odd?와 even?을 구현한다.

(defn even? [n] (zero? (bit-and n 1)))

(defn odd? [n] (not? (even? n)))

• 재귀에 관련한 문제는 사실 이 예제들처럼 간단하지도 않고, 효과적인 해결책이 없을 수 도 있다. 이럴 땐 다음 접근법으로 알아보도록 하자.
  • 상호재귀를 재귀로 바꾸기
  • 트랩폴린을 이용한 상호 재귀
  • 재귀를 평가지연으로 바꾸기
  • 메모이제이션을 이용해 재귀 호출을 줄이기

상호 재귀를 재귀로 바꾸기

좀더 추상화 할 수 있는 함수를 이용하는 방법

(defn parity [n]
  (loop [n n par 0]
    (if (= n 0)
      par
      (recur (dec n) (- 1 par)))))

(map parity (range 10))
-> (0 1 0 1 0 1 0 1 0 1)

(defn my-even? [n]
  (= 0 (parity n)))

(defn my-odd? [n]
  (= 1 (parity n)))

트램폴린을 이용한 상호 재귀

• 상호 재귀를 최적화 하는 한가지 기법 함수를 구현하는 사람이 recur를 이용해 재귀를 선언하는 대신 함수를 호출하는 쪽에서 recur를 통해 재귀적으로 함수를 호출할 수 있게함.

• 인자로는 주어진 함수를 호출하고 그 함수를 호출한 결과 반환되는 함수를 다시호출 하는 방식으로 반복해서 호출

• (trampoline f & partial-args)

  • f: 상호재귀적인 함수 중 하나
  • partial-args : 그함 수의 인자

(trampoline list)
-> ()

(trampoline + 1 2)
-> 3

trampoline이 인자로 받은 함수를 호출한 결과가 함수라면, recur를 이용해 그 함수를 다시 호출한다.

(defn trampoline-fibo [n]
  (let [fib (fn fib [f-2 f-1 current]
              (let [f (+ f-2 f-1)]
                    (if (= n current)
                      f
                      #(fib f-1 f (inc current)))))]
    (cond
     (= n 0) 0
     (= n 1) 10
     :else (fib 0 1 2))))

(trampoline-fibo 9)
(trampoline trampoline-fibo 9)
(rem(trampoline trampoline-fibo 1000)10)


(declare my-odd? my-even?)
(defn my-odd? [n]
  (if (= n 0)
    false
    #(my-even? (dec n))))

(defn my-even? [n]
  (if (= n 0)
    true
    #(my-odd? (dec n))))

    (trampoline my-even? 1000000)
->true

(my-even? 1000000)
-> #<user$my_even_QMARK_$fn__702 user$my_even_QMARK_$fn__702@14fd5dbb>

재귀를 평가 지연으로 바꾸기

• 재귀를 제거하거나 최적화하는 기법 가운데 가장 많이 쓰이는 것이 '평가지연'

• replace는 심벌과 심벌의 리스트를 포함하는 s-list자료구조를 처리하는 함수.

  • s-list, oldsym, newsym을 인자로 받아 s-list에 나타나는 모든 oldsym을 newsym으로 치환한다.

(replace '((a b) (((b g r) (f r)) c (d e)) b) 'b 'a)
-> ((a a) (((a g r) (f r)) c (d e)) a)
; 이건 클로저 함수가 아닝가봉가? 여튼 안돌아감..

• 다음 코드는 replace의 스킴 구현을 클로저로 옮겨온 것
• replace함수와 이름 충돌이 생기지 않게 이름을 replace-symbol로 바꾼 것 외에는 거의 같음
  • replace-symbol과 replace-symbol-expression이 서로를 호출하기 때문에 굉장히 많은 s-list를 넘기면 스택을 날려버림. (예는 deeply-nested)
  • deeply-nested: bottm이라는 원소 하나를 많은 괄호로 둘러싼 리스트 생성
  • replace-symbol했을 때 괄호 깊이가 깊으면, 스택 날림

; 스킴버전을 그대로 번역한 코드, 실제로 이렇게 사용하지는 말 것

(declare replace-symbol replace-symbol-expression)

(defn replace-symbol [coll oldsym newsym]
  (if (empty? coll)
    ()
    (cons (replace-symbol-expression
           (first coll) oldsym newsym)
          (replace-symbol
           (rest coll) oldsym newsym))))

(defn replace-symbol-expression [symbol-expr oldsym newsym]
  (if (symbol? symbol-expr)
    (if (= symbol-expr oldsym)
      newsym
      symbol-expr)
    (replace-symbol symbol-expr oldsym newsym)))

; 다음은 스택을 날려버리는 문제의 예를 위한 함수

(defn deeply-nested [n]
  (loop [n n
         result '(bottom)]
    (if (= n 0)
      result
      (recur (dec n) (list result)))))

(deeply-nested 5)
-> ((((((bottom))))))

(deeply-nested 25)
-> ((((((((((((((((((((((((((bottom))))))))))))))))))))))))))

(set! *print-level* 25) ; 특수 변수, 어느 이상 안쪽내용은 표시하지 않게.

(deeply-nested 0)

(replace-symbol (deeply-nested 5) 'bottom 'deepest)
-> ((((((deepest))))))

(replace-symbol (deeply-nested 10000) 'bottom 'deepest)
-> StackOverflowError   clojure.core/empty? (core.clj:5706)

• 위 경우, Replace-symbol의 모든 재귀적 호출이 cons안에서 이루어지므로, 재귀를 없애려면 단지 이부분을 lazy-seq로 감싸기만 하면 된다.
• 괄호 깊어도 잘 처리할 수 있음

(defn- coll-or-scalar [x & _] (if (coll? x) :collection :scalar))
(defmulti replace-symbol coll-or-scalr)
(defmethod replace-symbol :collection [coll oldsym newsym]
  (lazy-seq
   (when (seq coll)
     (cons (replace-symbol (first coll) oldsym newsym)
           (replace-symbol (rest coll) oldsym newsym)))))

(defmethod replace-symbol :scalar [obj oldsym newsym]
  if (= obj oldsym newsym obj))

(replace-symbol (deeply-nested 100) 'bottom 'deepest)

• lazy-seq는 재귀를 제거하고 괄호가 많은 리스트의 경우에 스택이 모두 소모되지 않게 막아준다.

• 참고

  • multimethod : 심벌가 리스트 각각에 대해 함수를 작성한 이전코드와 달리, 심벌과 리스트를 모두 처리할 수 있게함. if구문 써서 코드를 작성할 필요 없어서 분기 줄어들고, 가독성 높임.

메모이제이션을 이용해 재귀 호출을 줄이기

• n이커질 수록 느려지는 것에 대해, 캐싱을 통해 속도를 높임
• 캐싱해 놓은 결과를 바로 반환
• 메모이제이션 캐시가 만들어지고 나면, 캐시된 값의 계산을 요청했을 떄 값이 거의 즉각 리턴됨.

;F(0) = 1, M(0) = 0
;F(n) = n -M(F(n-1)), n >0
;M(n) = n -F(M(n-1)), n >0

(declare m f)

(defn m [n]
  (if (zero? n)
    0
    (- n (f (m (dec n))))))

(defn f [n]
  (if (zero? n)
    1
    (- n (m (f (dec n))))))


(m 250)
-> 155

(time (m 250))
-> "Elapsed time: 77840.393 msecs"
   155

;memoize함수를 이용해,m과 f가 메모이제이션을 수행하도록 하는 예

(def m (memoize m))
(def f (memoize f))
(time (m 250))
-> 바로 안됨;;

• 메모이제이션으로 충분하지 않을 수 있음 / 메모이제이션 캐시가 생성이 안되면 안되니까.
• 캐시가 생성 안되었을때 m,f에 큰수를 인자로 넘기면 캐시가 만들어지지 못한채 스택이 날아감
  • 이 때는 함수대신 시퀀스를 만들어서 사용할 수 있음.
  • 앞쪽 부터 차례로 모든 결과가 캐시되도록 만들 수 있음.
  • m과 f를 모든 수에 맵핑시켜 m-seq와 f-seq를 만들기

(def m-seq (map m (iterate inc 0)))
(def f-seq (map f (iterate inc 0)))

(nth m-seq 250)
-> 155;완전 빠르게 나옴

(time (nth m-seq 10000))
-> "Elapsed time: 41.732 msecs"
    6180

---

정리

• 문제를 표현하는 자연스러운 방법이 상호 재귀 함수라면 이것을 택한다.
• 재귀적 과정에서 이미 계산한 결과를 다시 계산하는 것을 막기 위해서 메모이제이션을 사용한다.
• 필요한 값들이 미리 캐시되도록 시퀀스를 사용한다.
• 단점은 모든 결과를 캐시하기 때문에 heap을 소모한다는 것.