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


  1. Favicon of http://shurain.egloos.com BlogIcon 슈레인

    | 2008.04.30 03:17 | PERMALINK | EDIT | REPLY |

    memorization이 아니라 memoization입니다. 기억하다의 memorize가 아니라 to be remembered의 memorandum에서 온 말입니다.

  2. Favicon of https://skyul.tistory.com BlogIcon 서광열 lambda

    | 2008.04.30 03:23 신고 | PERMALINK | EDIT |

    수정했습니다. 계속 memoization이란 단어로 읽어왔는데, 별 생각없이 memorization으로 기억하고 있었군요^^;

  3. Favicon of http://www.grayger.com/pw/ BlogIcon grayger

    | 2008.05.01 00:29 | PERMALINK | EDIT | REPLY |

    배경지식이 부족해서 잘 이해가 안가는데요^^; 이 방법이 python이나 다른 언어에도 적용될 수 있나요?

  4. Favicon of http://skyul.tistory.com BlogIcon 서광열

    | 2008.05.01 11:54 | PERMALINK | EDIT |

    네. 함수를 인자로 받아서 리턴할 수 있는 파이썬에서는 쉽게 되고, 자바에서도 커맨드 패턴 등으로 해볼 수 있을 겁니다.

  5. Favicon of http://dejavus.tistory.com BlogIcon Dejavus

    | 2008.05.14 17:33 | PERMALINK | EDIT | REPLY |

    앗 이것은 알고리즘 시간에 배운 그것!
    다이나믹 알고리즘 돌릴때 이렇게 하면
    속도가 상당히 빨라졌던 걸로 기억합니다.

  6. Favicon of http://azurespace.tistory.com BlogIcon Azurespace

    | 2008.12.20 13:44 | PERMALINK | EDIT |

    반복문을 이용한 일반적인 상향식 다이나믹 프로그래밍이 가능한 경우, memoization은 성능면에서 약간 떨어지는 편입니다.

Write your message and submit

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"을 이야기했는데 그 말이 딱 맞아떨어지는 부분입니다. 프로그래밍 언어를 추상화시켜서 내부 구현을 모르도록 만들어놨지만 결국 제대로 사용하려면 내부 구현을 상당 부분 알아야 한다는 것이죠.


Write your message and submit

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)

Write your message and submit

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



  1. Favicon of http://writely.tistory.com BlogIcon hey

    | 2008.04.29 10:52 | PERMALINK | EDIT | REPLY |

    전 절대라는 말이 왜 이렇게 기분 좋죠? ^^;

  2. Favicon of http://www.hoogle.kr BlogIcon hoogle

    | 2008.04.29 16:41 신고 | PERMALINK | EDIT | REPLY |

    이런 방식으로 죽을 수 있네요... 지금 ocaml로 프로그래밍을 하고 있답니다.

  3. Favicon of https://skyul.tistory.com BlogIcon 서광열 lambda

    | 2008.04.29 21:03 신고 | PERMALINK | EDIT |

    오. OCaml로 어떤 종류의 프로그램을 작성하시나요? 대외비?^^;;

  4. Favicon of http://www.hoogle.kr BlogIcon hoogle

    | 2008.04.30 00:40 신고 | PERMALINK | EDIT | REPLY |

    음... 꼭 대외비라고 할 수는 없습니다만... C 프로그램에서 Buffer overflow를 자동으로 찾아내주는 분석기를 만들고 있습니다.

    프로그램 분석에서는 ocaml이 제일 좋은 언어라고 생각하니깐요...

    서광열님의 블로그에서 재미나는 글들을 잘 읽고 있습니다 :)

  5. Favicon of https://skyul.tistory.com BlogIcon 서광열 lambda

    | 2008.04.30 00:43 신고 | PERMALINK | EDIT |

    Static Analysis 하시나 보네요. Airac처럼 Abstract Interpretation을 사용한 방식인가요?

  6. Favicon of http://www.hoogle.kr BlogIcon hoogle

    | 2008.04.30 15:21 신고 | PERMALINK | EDIT | REPLY |

    airac을 알고 계시네요... :)
    말씀히산 AI방식으로 하는 것이 맞습니다.

    그리고 제가 그 연구실을 나왔습니다.
    앞으로 다시 그 연구실에 들어가서 박사를 할 계획입니다...

  7. Favicon of https://skyul.tistory.com BlogIcon 서광열 lambda

    | 2008.04.30 16:38 신고 | PERMALINK | EDIT |

    와^^ 저도 한 때 static analysis에 관심을 많이 가졌습니다. 학부 때 졸업 과제 연구도 Java에서 static하게 null pointer exception 찾는 쪽으로 했었고.

    UMD 교환 학생 갔을 때, Jeff Foster 교수 Program Analysis(http://www.cs.umd.edu/class/fall2007/cmsc631/) 과목 청강했었는데 매력을 느껴서 이 분야로 전공하면 어떨까라는 생각도 했었거든요.

    지금은 타임 시스템이나 프로그래밍 언어를 잘 만들어서 처음부터 버퍼 오버플로우 같은 문제가 안 생기게 잘해보자는 접근법 쪽으로 바뀌긴 했지만요.

    나중에 박사가시면 잘 부탁드립니다 (__)

  8. Favicon of http://www.grayger.com/pw/ BlogIcon grayger

    | 2008.05.01 00:34 | PERMALINK | EDIT | REPLY |

    UMD면 Findbugs를 만든 Pugh 교수가 있는 대학교.. 그 학교 CS분야가 static analysis로 유명하나봐요? 혹시 Pugh도 봤나요?

  9. 서광열

    | 2008.05.01 00:58 | PERMALINK | EDIT |

    Bill Pugh 교수님한테 Concurrency 관련 수업을 들었습니다. 수업 중간에 FindBugs 프로젝트를 적극 활용하도록 독려하더군요. UMD가 Static Analysis가 강한 학교인지는 모르겠으나 Bill Pugh, Jeff Foster, Michael Hicks 교수님들이 그쪽으로 논문을 부지런히 내시더군요. 그 때 프로그램 언어 쪽으로만 수업을 듣다보니 세 분 모두에게 수업을 듣는 영광을 누렸습니다.

  10. Favicon of http://blog.naver.com/charsyam BlogIcon CharSyam

    | 2008.05.22 11:09 | PERMALINK | EDIT | REPLY |

    웬지 느낌이 C++ 에서 private 나 const 를 선언한 변수를

    강제 형변환 한다거나(const), 메모리 주소에서 위치를 계산해서

    값을 바꾸는거와 같은 느낌입니다. ^^

Write your message and submit
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는 어떤 모듈이나 클래스 인스턴스의 메소드 자동 완성하기가 힘듭니다.


  1. Favicon of http://infitable.com BlogIcon 선엽

    | 2008.12.23 13:02 | PERMALINK | EDIT | REPLY |

    좋은글 잘보고 갑니다 많은 유용한 정보가 있네요 자주 들러보면 개발자로서 안목을 넓힐수 있는 블로그? 라고 생각드네요 ^^

  2. BlogIcon Connection

    | 2012.09.27 19:24 | PERMALINK | EDIT | REPLY |

    굉장 블로그. 당신의 기사를 읽는 즐겼다. 이건 정말 나에게 좋은 읽기입니다. 내가 즐겨 찾기가 있고 난 새로운 기사를 읽고 기대하고 있습니다. 좋은 일을 계속!

Write your message and submit

까멜레오 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로 코드를 작성하면서 조금씩 추가해 나가려고 생각하고 있습니다.



Write your message and submit