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를 간단하게 만들 수 있도록 ocamllex
와 ocamlyacc
라는 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을 사용하기 위해서 넣었습니다.
ocamllex
와 ocamlyacc
에 대한 더욱 자세한 내용은 여기에서 보실 수 있습니다. 끝에 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
첫 두 줄은 ocamlyacc
와 ocamllex
를 이용해 parser.mly
와 lexer.mll
을 실제 OCaml 코드로 바꾸는 것입니다.
다음 두 줄은 parser.mli
에 open Type
을 추가하기 위한 줄입니다. verbose.mli
에는 open Type
과 빈 줄이 있습니다. 이 과정을 거쳐야 하는 이유는, 지금 parser.mly
의 parser_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년 전
코드가 공개가 안되어있네요 ㅠ ㅠ궁금