OCaml로 문제 풀이하기

OCaml 소개

OCaml은 Objective Caml입니다. CAML은 Categorical and Abstract ML입니다. ML은 Machine Language입니다. 즉 Caml은 기계 언어를 카테고리적이고 추상적으로 다루기 위해 고안된 언어이고, OCaml은 그러한 Caml에 OOP적인 요소를 부가한 것입니다.

OCaml로 문제 풀이: 2769번 논리식 비교

2769번 문제: 논리식 비교는 두 boolean expression을 받아 식이 동치인지 아닌지 검증하는 문제입니다. 입력이 일종의 언어이기 때문에 OCaml로 풀어보기에 적절한 문제라고 생각합니다. 문제를 풀기 위해서, 일반적인 프로그래밍 언어와 비슷하게 lexing/parsing을 거칠 수 있고, 모든 경우에 대해 식을 평가하여 문제를 해결할 수 있을 것입니다. OCaml은 lexer와 parser를 간단하게 만들 수 있도록 ocamllexocamlyacc라는 toolchain을 제공합니다.

type.ml

OCaml의 lexer/parser 문법은 간단합니다. 다만 parser가 OCaml object를 생성해야 하는데, 이 문제에서는 기존의 object로는 생성하기 힘든 을 다루고 있습니다. 따라서 type을 선언하는 부분을 따로 만들 필요가 있습니다.

type bool_expr =
| EAnd of bool_expr * bool_expr
| EOr  of bool_expr * bool_expr
| EXor of bool_expr * bool_expr
| ENot of bool_expr
| EVar of int

OCaml의 type 정의는 재귀적으로 만들 수 있고, sum type과 product type을 간단하게 만들 수 있습니다.

parser.mly

OCaml은 lexing 후 parser의 token을 만들어내는 형태입니다. 따라서 parser를 먼저 만드는 것이 좋습니다.

%{
  open Type

  let pv = Hashtbl.create 20

  let var_cnt = ref 0
  let retrieve c = try Hashtbl.find pv c with Not_found -> (
    let lvcnt = !var_cnt in
    let _ : unit = Hashtbl.add pv c lvcnt in
    let _ : unit = var_cnt := lvcnt + 1 in
    lvcnt
  )

  let clean () = let _ : unit = var_cnt := 0 in Hashtbl.reset pv
  let _ : unit = clean ()
%}

%token <int> NUM
%token <char> NAME
%token EOF
%token BOPEN BCLOSE AND OR NOT XOR

%left OR
%left XOR
%left AND
%right NOT

%start parser_main
%type <int * bool_expr * bool_expr> parser_main

%%
parser_main:
| init expr expr EOF { (!var_cnt, $2, $3) }
;
init:
| { clean () }
expr:
| expr OR expr  { EOr  ($1, $3) }
| expr AND expr { EAnd ($1, $3) }
| expr XOR expr { EXor ($1, $3) }
| NOT expr { ENot $2 }
| BOPEN expr BCLOSE { $2 }
| NAME { EVar (retrieve $1) }
;

parser는 OCaml 문법을 지원하기 때문에, 단순히 object를 만드는 것뿐만 아니라 처리까지 일부/전부 담당할 수 있습니다. %{...%} 부분에 보조적인 함수를 선언합니다. 여기에서는 (추후 a-z의 문자 하나가 들어갈) NAME의 alpha conversion을 parser에서 시행하고 있습니다.

좋은 점은 shift/reduce conflict(이 이름이 익숙하지 않다면, precedence/priority와 associativity)를 알아서 해결해 준다는 것입니다. 다음의 네 줄이 그 선언입니다:

%left OR
%left XOR
%left AND
%right NOT

위에 있을수록 낮은 precedence입니다. 이름에서 유추할 수 있는 방향으로 알아서 shift 혹은 reduce해 줍니다.

ocamlyacc는 모종의 이유로 가장 깊은 곳부터 parsing을 시작합니다. 재귀적인 구조인 경우 끝에서부터 parsing을 한다고 생각하시면 됩니다. 따라서 초기화를 하기가 약간 까다롭습니다. 위 코드에서처럼 init와 같은 rule을 새로 만들거나, 맨 처음에 한 번 초기화한 뒤 처리가 다 끝난 후 다음 parsing을 위해 초기화하는 방법 등으로 해결할 수 있습니다.

lexer.mll

lexer의 문법은 정말 간단합니다.

{
  open Parser
}

rule lexing_token = parse
| ' ' { lexing_token lexbuf }
| '(' { BOPEN }
| ')' { BCLOSE }
| '&' { AND }
| '|' { OR }
| '~' { NOT }
| '^' { XOR }
| ['a' - 'z'] as s { NAME s }
| eof { EOF }

lexer는 변형된 regex를 사용해서 코드를 lexing합니다. {...} 안에 OCaml 코드가 들어가는 것은 parser와 비슷합니다. open Parser는 parser의 내용을 그대로 가져오는 줄인데, parser에서 만들어 놓은 token을 사용하기 위해서 넣었습니다.

ocamllexocamlyacc에 대한 더욱 자세한 내용은 여기에서 보실 수 있습니다. 끝에 desk calculator를 만드는데, 여기서는 parser에 OCaml 코드를 넣어 실제로 계산까지 시행합니다.

main.ml

그러나 이 코드의 경우 parser가 처리까지 하지 않으므로, 주 코드가 필요합니다.

open Type
open Parser
open Lexer

exception SuccessfulExit

let my_for : int -> int -> int -> (int -> 'a) -> 'a list = fun st ed step func ->
  let rec inner st l =
    if st >= ed then List.rev l else (
      let v = func st in
      inner (st+step) (v::l)
    )
  in
  inner st []

let evaluate : bool_expr -> (int -> bool) -> bool = fun e f ->
  let rec inner e = match e with
  | EAnd (e1, e2) -> (inner e1) && (inner e2)
  | EOr  (e1, e2) -> (inner e1) || (inner e2)
  | EXor (e1, e2) ->
    let v1 = inner e1 in
    let v2 = inner e2 in
    ((not v1) && v2) || (v1 && (not v2))
  | ENot e' -> not (inner e')
  | EVar n -> (f n)
  in
  inner e

let main () =
  let n = int_of_string (read_line ()) in
  let rec iter c = (
    if c <= n then (
      let s = read_line () in
      let lexbuf = Lexing.from_string s in
      let (vn, e1, e2) = parser_main lexing_token lexbuf in
      let res = List.for_all (
        fun n ->
        let v1 = evaluate e1 (fun m -> (n land (1 lsl m)) = 0) in
        let v2 = evaluate e2 (fun m -> (n land (1 lsl m)) = 0) in
        v1 = v2
      ) (my_for 0 (1 lsl vn) 1 (fun n -> n)) in
      let _ = Printf.printf "Data set %d: %s\n" c (if res then "Equivalent" else "Different") in
      iter (c + 1)
    ) else ()
  ) in
  iter 1

let _ = main ()

평범한 OCaml 코드입니다. 빠른 문제 풀이를 위한 imperative feature를 흉내내기 위해 my_for와 같은 함수가 있습니다.

관습적으로 lexer/parser는 open하지 않고 Parser.parser_main Lexer.lexing_token lexbuf와 같이 사용합니다. 그렇지만 여기에서는 open을 사용해야 하는 중요한 이유가 있습니다.

컴파일 / 실행 / 제출

컴파일은 다음과 같은 순서로 하면 됩니다.

ocamlyacc parser.mly
ocamllex lexer.mll
cat verbose.mli parser.mli > parser2.mli
mv parser2.mli parser.mli
ocamlc -c type.ml
ocamlc -c parser.mli
ocamlc -c lexer.ml
ocamlc -c parser.ml
ocamlc -c main.ml
ocamlc type.cmo parser.cmo lexer.cmo main.cmo -o run

첫 두 줄은 ocamlyaccocamllex를 이용해 parser.mlylexer.mll을 실제 OCaml 코드로 바꾸는 것입니다.

다음 두 줄은 parser.mliopen Type을 추가하기 위한 줄입니다. verbose.mli에는 open Type과 빈 줄이 있습니다. 이 과정을 거쳐야 하는 이유는, 지금 parser.mlyparser_main의 type이 int * Type.bool_expr * Type.bool_expr로 되어 있기 때문입니다. 안타깝게도, ocamlyacc%{...%}에 들어가 있는 내용을 자동으로 추론해서 적어 주지 않습니다.

그 다음은 순서대로 컴파일 후 링크하는 과정입니다. 실행은 링크 후 ./run으로 할 수 있습니다.

그러나 우리에게는 중요한 문제가 남아 있습니다. 백준에는 파일 4개를 이름을 붙여 제출할 수 없습니다. 이 문제를 해결하기 위해서 우리는 의도적으로 .mli 파일을 만들지 않았습니다. 따라서 모든 .ml 파일의 dependency graph가 DAG를 이룹니다. 위상 정렬한 후에 순서대로 한 파일에 몰아서 써 주기만 하면 됩니다.

cat type.ml parser.ml lexer.ml main.ml > one.ml

one.ml에는 local open이 남아 있습니다. 우리가 lexer/parser를 사용할 때 open을 사용한 이유가 여기에 있습니다. open을 사용하지 않으면, 하나로 합친 파일에서 해당하는 부분을 찾아서 없애기가 번거롭습니다. 이 경우에는 파일을 열고, ^\s*open (Type|Lexer|Parser)을 찾은 뒤 모두 없애면 됩니다.

이렇게 해서 만든 파일은 454줄, 17,069 byte입니다. 이렇게 해서 맞은 제 코드는 여기에서 볼 수 있습니다.


댓글 (3개) 댓글 쓰기


cushionbadak 5년 전

잘 읽었습니다!


sgchoi5 5년 전

수고하셨어요.. 이런 걸 읽다보면 C/C++/JAVA/PYTHON 같은게 얼마나 쓰기 편한지... 매우 감사해지네요..


cpuu 5년 전

코드가 공개가 안되어있네요 ㅠ ㅠ궁금