Incremental 소개 (2015)

입력이 변경될 때 효율적으로 업데이트될 수 있는 자기 조정 계산 (self-adjusting computations), 즉 *자기 조정 계산 (self-adjusting computations)*을 구축하기 위한 강력한 라이브러리인 Incremental (주석이 잘 달린 mli는 여기에서 확인 가능)의 출시를 발표하게 되어 기쁩니다.

가장 단순하게는, 자기 조정 계산을 고급 스프레드시트라고 생각할 수 있습니다. 스프레드시트에서 각 셀은 단순한 데이터 또는 이 셀의 값이 다른 셀의 값으로부터 어떻게 유도되어야 하는지를 설명하는 방정식을 포함합니다. 이를 총체적으로 보면 그래프 구조의 계산 (graph-structured computation)이 되며, Excel의 핵심적인 최적화 중 하나는 일부 셀이 변경될 때 Excel이 변경된 셀에 의존하는 그래프의 부분만을 재계산한다는 점입니다.

자기 조정 계산 (Self-Adjusting Computation, SAC)을 스프레드시트와 다르게 만드는 것은 그 역동성 (dynamism)입니다. SAC의 계산 그래프 (computational graph) 구조는 입력 데이터의 변화에 대응하여 런타임 (runtime) 중에 변경될 수 있습니다.

이러한 역동성은 상당히 많은 유연성을 제공하며, 이는 다양한 방식으로 사용될 수 있습니다. 몇 가지 예시는 다음과 같습니다.

온라인 조합 알고리즘 (On-line combinatorial algorithms). Incremental은 자기 조정 계산 (이 용어가 여기서 유래되었습니다)에 관한 Umut Acar 외 연구진의 작업에 기반을 두고 있으며, 그들은 주로 다양한 조합 알고리즘의 효율적인 온라인 버전을 구축하는 데 관심이 있었습니다. 많은 경우, 그들은 일괄 처리 (all-at-once) 알고리즘을 상당히 단순한 증분 방식 (incrementalizations)으로 변환함으로써 맞춤형 온라인 알고리즘의 점근적 복잡도 (asymptotic complexity)를 맞출 수 있었습니다.

증분 GUI 구축 (Incremental GUI construction). GUI 애플리케이션을 모델링하는 간단하고 자연스러운 방법 중 하나는 디스플레이를 어떤 더 추상적인 데이터 모델로부터 뷰 (view)를 생성하는 함수로 구조화하는 것입니다.

매 반복마다 처음부터 뷰를 구축하는 함수를 갖는 것은 간단하지만 비용이 지나치게 많이 듭니다. 하지만 이 함수가 증분 계산 (incrementalized computation)을 생성하도록 작성할 수 있다면, 단순하면서도 효율적인 솔루션을 얻게 됩니다. 우리는 여러 UI에서 이 기술을 사용하여 좋은 효과를 거두었습니다.

이는 Elm과 같은 언어에서 GUI를 구축하기 위해 함수형 반응형 프로그래밍 (Functional Reactive Programming, FRP)이 어떻게 사용되는지를 떠올리게 할 수도 있습니다. SAC와 FRP는 서로 다른 의미론 (Semantics)을 가집니다. FRP는 주로 시간과 유사한 계산 (Time-like computations)에 초점을 맞추는 반면, SAC는 주로 DAG 구조의 계산 (DAG-structured computations)을 최적화하는 데 중점을 둡니다. 하지만 두 방식은 특히 구현 수준에서 매우 밀접하게 연관되어 있습니다. FRP와 SAC를 모두 포함하는 더 넓은 개념적 지형에 대한 설명은 여기 제 포스트를 참조하십시오.

설정 가능한 계산 (Configurable computations). 저희의 작업에서 가져온 한 가지 예는 리스크 계산입니다. 포트폴리오의 리스크 척도를 계산하려면 상호 의존적인 모델들의 복잡한 집합으로부터 데이터를 결합해야 합니다. 이러한 각 모델은 시장의 실시간 데이터와 사용자에 의해 결정된 설정 (Configuration) 모두에 의존합니다.

설정 변경은 단순히 계수 (Coefficient)를 미세하게 조정하는 것일 수도 있고, 특정 모델에서 사용되는 요인 (Factor) 목록을 변경하는 것과 같이 계산의 전체적인 구조를 변경하는 것일 수도 있습니다. Incremental을 사용하면 단순한 데이터 변경뿐만 아니라 더 구조적인 설정 변경에 대응하여 하나의 통합된 프레임워크 내에서 효율적으로 업데이트될 수 있는 계산을 구축할 수 있습니다.

Incremental 맛보기

Incremental이 정말 유용한 이유는 대규모의 복잡한 계산을 구축하는 데 도움을 주기 때문이므로, 단 몇 줄의 코드만으로 Incremental이 작동하는 설득력 있는 예시를 보여주기는 어렵습니다. 그럼에도 불구하고, 작은 예시들을 통해 라이브러리가 어떻게 작동하는지 감을 잡을 수는 있습니다.

이를 위해 몇 가지 작은 예시들을 살펴보겠습니다. 시작하기에 앞서, Incremental 펑터 (Functor)를 인스턴스화해야 합니다.

open Core.Std
module Inc = Incremental_lib.Incremental.Make ()

이렇게 생성된 각 인스턴스는 그 자체로 독립적인 계산 세계입니다. Incremental 펑터는 생성적 (Generative)입니다. 즉, 적용될 때마다 새로운 타입을 만들어내므로, 서로 다른 Incremental 세계의 값들이 실수로 섞이는 것을 방지합니다.

Incremental 계산은 항상 그 *변수 (variables)*에서 시작됩니다. 변수에 대한 수정은 입력 데이터의 업데이트를 Incremental에 전달하는 방식입니다.

직육면체의 차원에 대응하는 몇 가지 변수를 작성해 보겠습니다.

module Var = Inc.Var
(* dimensions of a rectangular prism *)
let width_v = Var.create 3.
...

각 변수와 연관된 (사소한) Incremental 계산을 얻기 위해 Var.watch를 사용할 수 있습니다.

let width = Var.watch width_v
let depth = Var.watch depth_v
let height = Var.watch height_v

다음은 직육면체의 밑면적과 부피에 대한 Incremental 계산입니다.

let base_area =
Inc.map2 width depth ~f:( *. )
let volume =
...

Incremental 계산으로부터 정보를 얻기 위해서는, 관찰자 (observer) 노드를 생성함으로써 데이터가 필요한 노드를 명시적으로 표시해야 합니다. 프레임워크는 어떤 노드가 관찰되고 있는지 알고 있기 때문에, 계산의 어느 부분이 결과에 여전히 필요한지를 추적할 수 있습니다.

let base_area_obs = Inc.observe base_area
let volume_obs = Inc.observe volume

계산을 강제로 실행하려면 Inc.stabilize를 명시적으로 호출해야 합니다. 다음은 stabilize를 사용하여 계산을 실행한 다음 관찰자로부터 정보를 가져오는 코드입니다.

let () =
let v = Inc.Observer.value_exn in
let display s =
...

이를 실행하면 다음과 같은 출력을 볼 수 있습니다.

1st stabilize: base area: 25.; volume: 125.
after set height: base area: 25.; volume: 125.
2nd stabilize: base area: 25.; volume: 250.

높이(height)를 설정하는 것만으로는 관찰된 값을 변경하기에 충분하지 않으며, 이를 실현하기 위해서는 안정화(stabilization) 과정이 필요하다는 점에 유의하십시오.

이는 상당히 사소한 계산이며, Incremental화할 내용이 분명 많지는 않습니다. 조금 더 복잡한 것을 시도해 봅시다. 덧셈이나 max와 같은 교환 법칙(commutative) 및 결합 법칙(associative)이 성립하는 연산자를 사용하여, Incremental 배열을 하나로 병합하는 함수를 만들어 보겠습니다.

let rec merge ar ~f =
if Array.length ar <= 1 then ar.(0)
else
...

이것은 의존성 그래프 (dependency graph)로서 이진 트리 (binary tree)를 사용하여 수행되기 때문에, 요소를 업데이트하는 복잡도 (complexity)는 배열의 크기를 n이라고 할 때 log(n)입니다.

우리는 이를 평균을 계산하는 데 사용할 수 있습니다:

let average ar =
let sum = merge ar ~f:(+.) in
Inc.map sum ~f:(fun s -> s /. float (Array.length ar))

이 방식은 작동하지만, 만약 우리의 병합 (merge) 연산에 역연산 (inverse)이 있다면 적어도 성능 측면에서는 더 개선할 수 있습니다. 그 경우, 새로운 값을 더하기 전에 기존 값을 먼저 제거함으로써 원칙적으로 합계 (sum)를 상수 시간 (constant time) 내에 유지할 수 있습니다. Incremental에는 이러한 구조를 활용하기 위한 함수가 있습니다.

let sum ar =
Inc.unordered_array_fold ~f:(+.) ~f_inverse:(-.) ar;;

이제 조금 더 동적인 작업을 해보겠습니다. 구체적으로, 주어진 배열의 접두사 (prefix)에 대한 평균을 계산하고 싶다면 어떻게 될까요? 이를 위해서는 Incremental 계산 내에서 새로운 Incremental 노드들을 생성할 수 있게 해주는 bind 함수를 사용해야 합니다.

let average_of_prefix ar length =
Inc.bind length (fun length ->
average (Array.init length ~f:(fun i -> ar.(i))))

이 함수의 타입은 float Inc.t array -> int Inc.t -> float Inc.t이며, 따라서 접두사의 길이는 Incremental 계산의 완전한 구성 요소가 됩니다. 결과적으로, 이 계산의 의존성 구조 (dependency structure)는 동적으로 변합니다. 예를 들어, length의 값이 7이라면, 계산은 오직 length와 배열의 처음 7개 요소에만 의존하게 됩니다.

이 내용이 Incremental이 무엇인지에 대해 충분한 감을 잡고, 여러분에게 어디에 유용할지 고민을 시작하는 데 도움이 되기를 바랍니다. Incremental의 오버헤드 (overhead)가 결코 작지 않다는 점에 유의하십시오. 제 노트북에서는 단일 노드 (node)를 실행하는 데 약 30ns 정도가 소요되는데, 이는 예를 들어 숫자들을 단순히 합산하는 것보다 훨씬 더 많은 시간입니다. Incremental은 단일 노드에 투입되는 계산량이 해당 오버헤드에 비해 크거나, 계산을 다시 수행해야 하는 서브 그래프 (sub-graph)에 비해 계산 그래프 (computational graph)가 클 때 유용해지는 경향이 있습니다. 저희의 경험에 따르면, 이 분야에는 Incremental로부터 이득을 얻을 수 있는 수많은 응용 사례가 존재합니다.