Search Results for 'OCaml'

6 POSTS

  1. 2008.04.30 Memoization 6
  2. 2008.04.29 OCaml 프로그램 최적화
  3. 2008.04.29 GODI
  4. 2008.04.29 OCaml 죽이기 10
  5. 2008.04.28 명시적 정적 타이핑(typing)의 종말 2
  6. 2008.04.28 까멜레오 OCaml 지원.

Memoization

Posted 2008. 4. 30. 01:51
순수(pure) 함수, 다른 말로 참조 투명한(referential transparent) 함수는 수학적인 함수와 마찬가지로 같은 인자를 넣으면 언제나 같은 값을 돌려줌을 보장하는 함수입니다. 간단한 예로, OCaml로 작성된 다음 피보나치 수열 함수(fib)는 참조 투명한 함수입니다.

let rec fib = function
    0 | 1 as i -> i
    | i -> fib (i - 1) + fib (i - 2)


위 fib 함수는 비효율적으로 작성되어 있기 때문에 무척 느립니다. 이런 순수 함수를 최적화하는 방법으로 알고리즘 자체를 꼬리 호출(tail recursion)하도록 변경하거나 더 나은 알고리즘을 찾는 방법 등도 있겠지만, 함수를 그대로 두고 메모리 공간을 희생해서 속도를 향상하는 최적화 방법으로 기억(memoization)이 있습니다.

다음 memo 함수는 Developing Applications With Objective Caml에서 발췌한 예입니다.

let memo f =
        let table = ref [] in
        let rec find_or_apply entries x =
            match entries with
                (x', y) :: _ when x' = x -> y
            | _ :: entries -> find_or_apply entries x
            | [] ->
                    let y = f x in
                    table := (x, y) :: !table;
                    y
        in
        (fun x -> find_or_apply !table x)

이 함수의 타입은

val memo : ('a -> 'b) -> ('a -> 'b)


로 원래 함수와 동일한 타입의 함수를 리턴합니다. 코드를 살펴보면 table을 두고 계산 결과를 저장해서 한 번 f(e) 값이 불리면 두 번째 불리는 f(e)는 새로 계산하지 않고 저장된 값을 쓰게 됩니다. 일종의 동적 프로그래밍(dynamic programming) 기법입니다.

기억(memorization)이 가능한 이유는 함수가 참조 투명하기 때문입니다. 매번 호출할 때마다 값이 바뀌는 함수라면 이전 함수의 결과를 저장해뒀다가 재활용하는 것이 불가능하기 때문입니다.

어느 정도 속도 향상이 있었는지 측정하기 위해서 시간을 재는 함수를 다음과 같이 만들어 봅니다.


let time f x =
    let start = Sys.time () in
    let y = f x in
    let finish = Sys.time () in
    Printf.printf "Elapsed time: %f seconds\n" (finish -. start);
    y
;;

OCaml은 함수 언어고 a + b라고 해서 a를 b보다 먼저 연산(evaluation)한다는 보장이 없습니다. IO의 경우는 순서가 중요하기 때문에, IO의 순서를 정하기 위해서 위와 같이 let 구문을 연달아 늘어 놓는 방법을 많이 씁니다. 앞서 let이 새로운 스코프(lexical scope)을 만들기 때문에 순서가 보장되게 됩니다.

let memo_fib = memo fib;;

time memo_fib 35;;
time memo_fib 35;;


fib를 memo로 감싸서 memo_fib 함수를 정의한 다음에 2번 불러보면 두 번째는 이미 계산된 저장 값을 가져 오기 때문에 매우 빠르게 계산됨을 확인할 수 있습니다.

Elapsed time: 2.579000 seconds
Elapsed time: 0.000000 seconds


OCaml 프로그램 최적화

Posted 2008. 4. 29. 20:45
프로그래밍 언어를 공부를 단계별로 나눈다면

(1) 프로그래밍 언어의 문법를 파악
(2) 프로그래밍 언어의 의미(semantics)를 이해
(3) 프로그래밍 언어 커뮤니티가 사용하는 관례와 용법 파악
(4) 프로그래밍 언어 내부 구현(컴파일러, 인터프리터) 지식을 활용한 최적화 코드 작성

정도의 순서로 진행될 것입니다. OCaml은 일반적으로 상당히 빠른 머신 코드로 컴파일될 수 있다고 알려져 있지만 OCaml 컴파일러가 어떤 최적화 기법을 사용하는지 알면 더욱 더 효율적인 코드를 짤 수 있을 것입니다. 

예를 들어, 다중 인자를 받는 OCaml 함수를 정의할 때 두 가지 방법을 사용할 수 있습니다. OCaml QnA의 Making code run fast라는 글에서 인용했습니다.

fun x y z -> ...


fun (x, y, z) -> ...


첫 번째는 커리(curried) 형태이고, 두 번째는 언커리(uncurried) 함수로 여러 인자를 하나의 튜플로 만든 형태입니다. 

개발자가 느끼기에 두 코드가 하는 일은 거의 동일하지만 OCaml 컴파일러 입장에서 봤을 때는 달라지는 부분이 생깁니다. OCaml 바이트코드 컴파일러(ocamlc)의 경우, 커리 함수는 힙(heap) 할당 없이 스택에 변수를 넘겨서 함수 호출을 수행함을 보장합니다. 반대로 언커리 함수는 힙에 튜플을 만들어서 넘깁니다. 호출된 함수 안에서는 다시 튜플에서 각각의 원소를 꺼내 와야 하기 때문에 커리 함수에 비해 속도가 느려집니다.

그런데 반드시 이렇게 되어야만 하는 것도 아닙니다. 네이티브 컴파일러(ocamlopt)는 두 경우 모두 힙에 할당하지 않고 레지스터를 이용해 파라미터를 전달하기 때문에 두 함수는 성능 차가 없어집니다.

또 하나의 예로, 대부분의 Lisp이나 ML 컴파일러는 부동소수점 계산이 느립니다. 가비지 콜렉션, 다형성/타입 추상화 등 때문에 부동소수를 힙에 할당하고 포인터를 저장하는 방식으로 구현된 경우가 많기 때문입니다. float 두 개 더하려면 포인터를 2개 읽어서 float를 가져와 더한 다음에 그 결과를 다시 포인터가 가리키는 주소에 저장해야 하기 때문에 속도가 느려질 수밖에 없습니다.

컴파일러가 부동소수점을 언박싱(unboxing)하는 최적화를 하면 이 문제를 완화시킬 수 있습니다. 다만 컴파일러가 모든 케이스를 자동으로 언박싱할 수 없기 때문에 몇 가지 트릭을 사용하게 되고, 이런 트릭을 모르는 개발자는 속도가 느린 프로그램을 작성할 수밖에 없게 되는 것이죠.

예전에 조엘(Joel) 아저씨가 "The Law of Leaky Abstraction"을 이야기했는데 그 말이 딱 맞아떨어지는 부분입니다. 프로그래밍 언어를 추상화시켜서 내부 구현을 모르도록 만들어놨지만 결국 제대로 사용하려면 내부 구현을 상당 부분 알아야 한다는 것이죠.


GODI

Posted 2008. 4. 29. 20:02
OCaml의 라이브러리(표준 라이브러리 제외)는 GODI 프로젝트를 통해 관리되고 있습니다. GODI 툴 체인(godi_console)을 사용하면 OCaml 라이브러리를 쉽게 설치/제거할 수 있습니다. GODI 라이브러리 목록은 camlcity.org 홈페이지에 링크되어 있는데,  생각보다 별로 많지 않은 것 같네요. Perl의 CPAN와 비교하면 약간 부끄러울 정도랄까요? godi_console로 확인해보니 164개의 라이브러리가 있군요.

GODI로 설치된 OCaml 라이브러리는 다음과 같이 로딩합니다. 예를 들어, Bitmatch라는 라이브러리 로딩하려면 다음과 같이 합니다.


skyul@skyul-desktop:~$ ocaml
        Objective Caml version 3.10.1
# #use "topfind";;
- : unit = ()
Findlib has been successfully loaded. Additional directives:
  #require "package";;      to load a package
  #list;;                   to list the available packages
  #camlp4o;;                to load camlp4 (standard syntax)
  #camlp4r;;                to load camlp4 (revised syntax)
  #predicates "p,q,...";;   to set these predicates
  Topfind.reset();;         to force that packages will be reloaded
  #thread;;                 to enable threads

- : unit = ()
# #require "Bitmatch";;
No such package: Bitmatch
# #require "bitmatch";;
/opt/godi/lib/ocaml/site-lib/bitmatch: added to search path
/opt/godi/lib/ocaml/site-lib/bitmatch/bitmatch.cma: loaded
# open Bitmatch;;
# Bitmatch.create_bitstring 10;;
- : Bitmatch.bitstring = ("\000\000", 0, 10)

OCaml 죽이기

Posted 2008. 4. 29. 00:57
OCaml 프로그램은 이론적으로 절대 크래시가 날 수 없습니다. 외부 모듈(C로 작성된 코드)를 호출한 경우가 아니면 죽을 수가 없게 타입 시스템 자체가 디자인되었기 때문입니다.

하지만 강한 타이핑(strong typing)하는 언어라도 직렬화(OCaml에서는 Linearization 용어 사용, 자바의 Serialization과 같은 개념)를 지원하면 타입 시스템을 얼마든지 깨먹을 수 있게 됩니다. OCaml은 Marshal 모듈을 사용해 직렬화를 하는데, Marshal 모듈을 이용하면 다음과 같이 'a 타입을 'b 타입으로 강제로 바꾸는 함수(C의 캐스팅)를 작성할 수 있습니다.


# let magic_copy a =
    let s = Marshal.to_string a [Marshal.Closures] in
        Marshal.from_string s 0;;
val magic_copy : 'a -> 'b = <fun>


이렇게 작성한 후에 다음과 같이 int 타입을 float로 강제로 변환한 후에 덧셈을 하면 크래시가 발생하고 프로그램이 죽게 됩니다.

# (magic_copy 2 : float)  +. 4.5;;
Segmentation fault



IBM dW의 Crossing borders: Typing strategies beyond the Java model는 프로그래밍 언어의 타이핑 전략(typing strategies)에 대해서 이야기하고 있습니다. 상당수 개발자들이 프로그래밍 언어의 타이핑 생산성, 유지보수성 등에 상당한 영향을 미친다고 생각하고 있고, 자바 개발자들이 상당수 루비로 갈아탄 것도 이와 무관하지 않아 보입니다.

이 기사의 저자는 자바 타이핑에 대한 대안으로 서로 양극단에 있는 Ruby와 OCaml의 타이핑을 비교하고 있습니다. Ruby는 동적 타이핑을 하는 대표적 언어이고, OCaml은 정적 타이핑의 대표 주자인 ML 계열의 언어입니다.

프로그래밍 언어의 타이핑을 구분하는 방법은 몇 가지가 있는데, 정적/동적 타이핑, 강한(strong)/약한(weak) 타이핑이 일반적인 구분 방법입니다. 여기에 하나 덧붙이자면 명시적/암묵적 타이핑이 있습니다. 명시적 타이핑 언어는 자바나 C#처럼 모든 타입을 개발자가 적어줘야 하는 방식이고, 암묵적 타이핑은 OCaml이나 Haskell처럼 개발자가 일부 타입을 기입하지 않더라도 타입 추론을 통해 컴파일러가 나머지 타입을 찾아내는 방식입니다.

자바가 루비에 비해 생산성이 떨어지는 문제를 동적/정적 타이핑의 문제로만 볼 수 없는 이유는 자바와 OCaml을 비교했을 때 자바 이상으로 강력한 정적 타이핑을 제공하는 OCaml 코드가 자바보다는 루비에 가까운 간결함을 보이기 때문입니다.

근데 하나 분명한 것은 자바는 아니라는 것입니다. 루비도 좋고 OCaml도 좋고 장단점이 있지만 명시적 정적 타이핑하는 자바는 이제 수명이 다하고 있다는 것이 핵심이 아닐까 싶습니다. Spring, AspectJ, Hibernate 등 다양한 자바 기반의 거대 프레임워크가 존재하는 이유는 반대로 생각하면 자바만으로는 일반적인 어플리케이션 개발에 요구되는 메타프로그래밍을 쉽게 할 수 없기 때문입니다.

물론 워낙 개발자가 많은 자바 진영이다 보니 그리 쉽게 망하겠냐는 생각을 하실 수도 있겠지만, 자바를 다른 언어로 대체하려는 움직임은 자바 진영 내부에서 가장 먼저 논의되고 있습니다. 요즘은 JVM에서 동작하는 언어(JVML)에 대한 이야기로 뜨겁습니다. 함수 언어와 객체지향 언어를 결합한 Scala가 신예라면, JVM 용 스크립트 언어인 Groovy, Jruby, Jython 등은 이미 많은 유저를 확보했습니다. 그 외에도, Lisp의 현대판인 Clojure, CLR과 JVM에서 동시에 동작하는 Fan, Scheme JVM 버전인 SISC 등이 그야말로 자바를 따라잡기 위해 노력하고 있는 상황입니다.

자바는 이런 언어의 라이브러리를 구현하기 위한 시스템 언어 정도로 물러서고 어플리케이션 프로그래밍은 자바가 아닌 좀 더 생산성이 높은 언어로 하는 시대가 올지도 모르겠습니다.


사족: 언급된 내용 중에서 제가 동적 타이핑에서 가장 불편하다고 생각하는 점 중에 하나는 IDE 개발 도구 지원입니다. Eclipse를 비롯한 자바 개발 도구는 대부분 자바 소스를 파싱해서 AST 형태로 만든 후 각종 리팩토링(이름 변경 등)을 매우 쉽게 만들어 줍니다. 반대로 Python이나 Ruby IDE는 어떤 모듈이나 클래스 인스턴스의 메소드 자동 완성하기가 힘듭니다.


까멜레오 OCaml 지원.

Posted 2008. 4. 28. 13:48
까멜레오는 주로 Python과 C로 작성되었습니다. UI와 위젯 작성은 파이썬으로 하고, 속도가 생명인 미디어 재생/분석 코드는 C로 작성되어 있습니다.  그런데, 프로젝트를 하다보니 코드를 C로 작성하면 아무래도 작성 시간도 오래 걸리고, 품질도 그리 높지가 않더군요. 특히, 메모리 깨먹는 버그나 멀티쓰레드 관련 버그는 정말 괴롭습니다.

최근에 이런 문제를 돌파해보고자 함수 언어인 OCaml을 까멜레오 구현 언어로 추가하기 위한 작업을 끝마쳤습니다. 특히, 비디오 처리(video processing) 코드를 OCaml로 작성해서 오류를 줄이고 작성 속도도 높여보자는 것이 가장 중요한 취지입니다.

기존 까멜레오 코드가 상당 부분 파이썬으로 코딩되어 있기 때문에 OCaml와 Python을 연결하기 위해 Pycaml 프로젝트를 가져다가 조금 고쳤습니다. OCaml과 Python이 직접 붙는 것은 아니고, Ocaml의 C 인터페이스를 이용해 Python/C API에 붙이는 방식으로 구현되어 있습니다.

아직 기본적인 데이타 타입 변환만 있고, Python의 list, tuple. dict와 OCaml의 list, tuple, assoc list 등을 변환해주는 코드 등이 부족한 상태라 사용이 그리 쉽지는 않은 상태입니다. 이쪽은 OCaml로 코드를 작성하면서 조금씩 추가해 나가려고 생각하고 있습니다.