프로그래밍 클로저 - ChoDragon9/posts GitHub Wiki

4장 데이터를 시퀀스로 다루기

  • 클로저는 모든 자료구조를 시퀀스(Seq)라는 하나의 추상으로 다룰 수 있다.
    • 시퀀스란 논리적 리스트다.
      • 논리적이라는 단어를 붙인 이유는 시퀀스가 Lisp의 Cons같은 리스트의 '내부구현'과 직접 관계가 없기 때문이다.
  • 시퀀스는 리스트에 한정되지 않고 어디에서나 사용될 수 있는 추상이다.

4.1 모든 것은 시퀀스

시퀀스는 세 가지 기본적인 특성을 가진다.

  1. 시퀀스의 첫번째 원소를 얻어낼 수 있다.

    • first <seq>: first는 인자가 nil이거나 비어 있으면 nil을 반환한다.

  2. 첫번째 원소를 제외한 나머지를 얻어 낼 수 있어야 한다.

    • rest <seq>: 남은 원소가 없는 경우, rest는 nil이 아니라 빈 시퀀스를 반환한다.

  3. 기존 시퀀스의 앞에 원소를 추가해서 새로운 시퀀스를 만들 수 있다.

    • cons <elem> <seq>

클로저의 맵과 집합에서는 고정적 방문 순서라는 특성이 있다. 반문순서가 무작위로 결정되는 것이 아니라 그 순서가 언제나 동일하다는 것이다.

4.2 시퀀스 라이브러리 사용하기

시퀀스 생성
  • range <start?> <end> <step?>
  • repeat <n> <x>: x는 n만큼 반복한다.
  • iterate <f> <x>: x에서 시작해서 그 값에 함수 f를 적용해 다음값을 만들어 나가는 일을 무한히 반복한다.
시퀀스 필터링
  • filter <pred> <coll>
  • take-while <pred> <coll>: 서술식을 컬렉션의 각 원소에 적용해서 거짓이 나타나기 전 까지의 원소로만 이루어진 시퀀스를 반환한다.
  • drop-while <pred> <coll>: 참으로 만드는 원소를 제거하고 나머지를 반환한다.
시퀀스 서술식
  • every? <pred> <coll>
  • some <pred> <coll>
시퀀스 변환
  • map <f> <coll>
  • reduce <f> <coll>
  • sort <comp?> <coll>
  • sort-by <fn> <comp?> <coll>

5장 함수형 프로그래밍

5.1 함수형 프로그래밍의 개념

순수함수
  • 함수형 프로그램은 순수함수로 이루어져 있다.
  • 순수함수란, 부수효과가 전혀없는 함수를 말한다.
  • 인자에만 의존해서 결과가 만들어지고 반환값으로만 외부세계에 영향을 준다.
영속적 자료구조
  • 변경 불가능 데이터는 클로저의 함수형 프로그래밍과 병형 프로그래밍 방식에 중요하다.
  • 모든 데이터가 변경 불가능이라면, 데이터를 갱신한다는 것은 곧 기존 데이터에 변화가 가해진 새로운 데이터를 생성한다는 뜻
  • 클로저의 자료구조는 영속적이다.
    • 영속적이라는 단어의 의미는 갱신되기 전의 데이터와 후의 데이터가 변경되지 않는 부분을 그대로 공유하는 효율적인 접근 방식을 취한다는 것이다.
지연평가와 재귀

[2.5 흐름제어 > loop/recur을 이용한 반복] 꼬리 재취 최적화를 제공하지 않지만 recur로 최적화 능력을 갖췄다.

함수형 프로그램은 재귀와 지연 평가를 매우 많이 사용한다. 재귀란, 함수가 그 자신을 직접 또는 간접으로 호출하는 것을 말한다. 지연 평가란, 말 그대로 그 표현식을 평가한 결과가 꼭 필요해질 때까지 평가를 미루는 것이다. 지연된 표현식을 평가한다는 것은 그 표현식을 실행하는 것이다.

클로저에서 함수와 표현식에 대해서는 기본적으로 평가가 지연되지 않는다. 하지만 시퀀스에 대해서는 평가를 지연한다. 시퀀스를 다루는 것이 클로저 프로그래밍의 많은 부분을 차지하기 때문에, 지연된 연산의 이점을 충분히 누릴 수 있다.

지연 평가를 이용하는 기법은 사실 순수 함수 사용을 전재로 깔고 있다. 순수 함수를 사용하면, 그 함수를 지금 호출하든 나중에 호출하든 결과에 차이가 없기 때문에 평가를 지연할 수 있다.

참조투명성
  • 함수 호출 자체를 함수의 결과로 치환해도 프로그램의 행동에 영향을 미치지 않는 함수
  • 참조 투명성 덕분에 가능한 것들은 이렇다.
    • 지연성이 가능하다.
    • 메모이제이션이 가능하다.
    • 병행성을 저절로 확보하게 된다.
여섯 가지 원칙

클로저는 함수형 프로그래밍의 학문적인 순수함과 자바 가상 머신에서 실행되어야 한다는 현실 사이에서 균형 잡힌 접근 방법을 취하고 있다. 다음에 설명하는 여섯 가지 원칙이 클로저 스타일의 함수형 프로그래밍을 익히는 첫걸음을 떼도록 도와줄 것이다.

  1. 직접 재귀를 사용하는 것을 피하자. 자바 가상 머신이 꼬리 재귀 최적화를 하지 못하기 때문에, 직접 재귀를 사용하면 순식간에 스택을 소모하게 된다.
  2. 그 대신 recur를 사용하자. 클로저는 recur에 대한 호출을 최적화하는 능력을 갖추었다. recur는 무한이 아닌, 작은 규모의 시퀀스를 만들 때 사용하는 것이 좋다.
  3. 반면에 규모가 큰 시퀀스를 만들어 낼 일이 있다면, 지연 시퀀스로 만들자. 이러면, 이 시퀀스를 사용하는 사람이 실제로 필요한 부분에 대한 연산 비용만 지불할 수 있다.
  4. 지연 시퀀스에서 실제로 필요한 부분 외까지 평가하지 않도록 주의를 기울이자.
  5. 시퀀스 라이브러리를 이용하자. recur나 지연 평가와 관련된 API 없이도 원하는 코드를 작성할 수 있는 경우가 많다.
  6. 쪼개서 정복하자. 간단해 보이는 문제라도 더 작은 구성 요소로 쪼개면 시퀀스 라이브러리 같은 범용적이고 재사용 가능한 코드로 문제를 해결할 수 있다.

5.2 어떤게 연산을 지연시킬까

재귀적인 정의는 두 부분으로 이루어진다.

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

이 절의 목표는 재귀적 정의를 실행되는 코드로 바꾸는 것이다. 사실 방법은 여러 가지다.

  • 기본적 재귀: 함수가 자기 자신을 호출하게 한 뒤 적절한 조작을 가해, 귀납에 해당하는 과정을 만들어 내는 방법이다.
  • 꼬리 재귀: 함수가 함수 정의의 마지막 부분에서 자기 자신을 호출하는 것외에 다른 조작을 가하지 않는 재귀의 형태이다. 꼬리 재귀 형태로 코드를 작성하면, 꼬리 재귀 최적화로 불리는 성능 최적화가 가능해진다.
  • 지연 시퀀스: 실제로 재귀 과정을 실행하기보다, 지연 시퀀스를 이용해 값이 정말로 필요해질 때 계산하는 방법도 있다.

이 가준데 적절한 방법을 선택하는 것이 중요하다. 재귀적 정의를 제대로 구현하지 못하면, 모든 스택을 소모하고 실패하거나, 또는 모든 힙(Heap)을 소모하고 실패하거나, 아니면 둘 다를 일으키는 최악의 코드가 나올 수 있다. 클로저에서는, 지연된 평가를 이용하는 세 번째 방법이 가정 적합한 경우가 많다.

피보나치 수열

지금 나열한 접근 방법들을 적용해 피보나치 수열을 구해 보자.

- 기저: F(0), 0번째 피보나치 수는 0이다. F(1), 첫 번째 피보나치 수는 1이다.
- 귀납 규칙: n > 1이면, F(n)은 F(n - 1) + F(n - 2)과 같다.
기본적 재귀
(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); 34

재귀적 정의 때문에, 1보다 큰 n에 대해서 stack-consuming-fibo를 호출할 때마다 stack-consuming-fibo에 대한 호출이 두 개씩 더 생겨나게 된다. 자바 가상 머신 수준에서 이런 호출은 메서드에 대한 호출이기 때문에, 스택 프레임이 계속 쌓이게 된다.

꼬리 재귀

함수형 프로그램이 스택을 잡아먹는 문제는 꼬리 재귀를 사용해서 해결할 수 있다. 꼬리 재귀 함수 역시 재귀적 정의를 사용하긴 하지만, 자신을 호출하는 부분이 함수 정의의 마지막인 반환 값 부분에 와야 한다는 점이 다르다. 이런 식으로 함수를 정의하면, 재귀적 정의를 반복문 형태로 바꿔 스택을 소모하지 않게 만드는 꼬리 재귀 최적화가 가능해진다.

(defn tail-fibo [n]
    (letfn [(fib
            [current next n]
            (if (zero? n)
                current
                (fib next (+ current next) (dec n))))]
    (fib 0 1 n)))

leffn은 let과 비슷하지만 지역 함수를 바인딩한다는 점이 다르다. letfn에서 선언된 함수는 자기 자신을 부를 수 있고 letfn 블록 내에 정의된 다른 함수를 호출할 수 도 있다.

  • 세 번째 줄을 보면 fib는 current 피보나치 수, next 피보나치 수, 그리고 결과를 내기까지 남은 단계의 숫자인 n 등 세 개의 인자를 같는다.
  • 다섯째 줄은 더 수행할 단계가 남아 있지 않으면 현재의 피보나치 수를 반환하라는 뜻이다.
  • 여섯째 줄은 남아 있는 단계의 수를 하나 줄이면서 계산을 계속하라는 의미다.
  • 일곱째 줄은 기본 값인 0과 1, 그리고 몇 번째 피보나치 수를 계산할지 나타내는 n을 가지고 연산을 시작하고 있다.

하지만 꼬리 재귀 함수인데도 큰 n에 대해서는 여전히 값을 구하는 데 실패한다. 문제는 자바 가상 머신에 있다. 하스켈 등 함수형 언어에서는 꼬리 재귀 최적화가 가능한 반면에 자바 가상 머신은 함수형 언어를 위해 설계된 것이 아니기 때문에, 가상 머신에서 직접 돌아가는 어떤 언어도 자동적인 꼬리 재귀 최적화를 수행하지 못한다.

recur를 이용한 자체 재귀

클로저에서 꼬리 재귀 함수는 recur를 이용하는 자체 제귀 함수로 고쳐쓸 수 있다. 일곱째 줄에서 fib 대시 recur를 호출하는 점이다. 스택을 소모하지 않기 때문에, 큰 n에 대한 피보나치 수도 느리긴 하지만 계산해 낸다.

(defn recur-fibo [n]
    (letfn [(fib
            [current next n]
            (if (zero? n)
                current
                (recur next (+ current next) (dec n))))]
    (fib 0 1 n)))
지연 시퀀스

지연 시퀀스는 lazy-seq라는 매크로를 이용해 만든다.

(lazy-seq & body)

lazy-seq는 그 body 부분이 꼭 필요할 때만 실행되게 만든다. 즉, 직접 또는 간접적으로 지연 시퀀스에 대해 seq 함수가 호출될 때만 body 부분이 실행된다고 보면된다. lazy-seq는 이후에 일어날 호출에 대비해 결과를 캐싱하는 기능도 갖추고 있다.

5.4 다시 제귀로

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

메모이제이션이란, 함수가 예전에 계산한 결과를 캐싱하여 공간을 소모하는 대신에 계산 속도를 빠르게 만드는 기법을 말한다. 메모이제이션을 수행하는 함수를 호출하며 인자를 넘기면, 그 함수는 예전에도 그와 같은 인자를 받아서 값을 반환한 적이 있는 지 검사한다. 넘겨받은 인자가 함수가 가진 맵(map)에 키로 존재한다면, 함수는 연산을 수행하는 대신 캐싱해 놓은 결과를 바로 반환한다. 클로저의 memoize 함수를 이용해서 메모이제이션을 수행하도록 만들 수 있다.

⚠️ **GitHub.com Fallback** ⚠️