OCaml

. 설치
http://ropas.kaist.ac.kr/caml/ocaml
-> distribution
-> Native Win32 port based on the Microsoft toolchain (3.08.2)

http://caml.inria.fr/
-> Download
-> Binary distributions for Microsoft Windows
-> Self installer (3.09.0) for the port based on the Microsoft toolchain

Interpreter 사용에는 Visual C++이나 cygwin 등이 필요없고
compiler 사용시에만 필요하다.

Compiler를 쓰기 위해서는 module system을 이해해야 한다.

. ML
Segmentation fault가 없다.

. SML
http://www.smlnj.org/ (미국식) - 요즘 개발 잘 안됨

. Ocaml
Caml + OOP

. Ocaml 문법
;; : 프로그램의 끝
+. : float를 위한 add(strongly typed language라서 integer add와 다르다.)
. _ : int = 1
_ : 변수명 없음
int : type
1 : value
. tuple 만들기 (a,b,c,d)
. tuple 쪼개기 (pattern matching 이용)
. function type : (입력 변수1 타입 -> 입력 변수2 타입 -> ... -> 입력 변수n 타입 -> 출력변수 타입)
. :: : cons operator (int -> int list -> int list)
. @ : list comcatenation operator(int list -> int list -> int list)
. 둘 중 하나로 다른 것을 구현가능하다.
. match e with
| pattern1 -> e1
| pattern2 -> e2
e(expression)이 pattern 1을 만족하면 e1을 수행 아니면 아래를 비교
. program : data type + algorithm

. let
같은 변수명이나 함수명을 다시 정의하면 가장 최근에 정의한 것이
수행된다.

. type 정의
type abc = A|B|C
type pair = PAIR of int * int
. A,B,C,PAIR
data 모양의 이름, 첫 글자는 반드시 대문자이다.
data를 construction할 때 사용한다.
A,B,C처럼 of가 없으면 delimiter, seperator, maker 등으로 쓴다.
ex) let a = A;;

. type abc = A
type abcd = A
let value = A( )
가장 최근에 적은 A가 그 위의 것을 shadow한다.
따라서 value의 type은 abcd이다.

. match e with
| ListEnd ->
| ListNode(1, ListEnd) ->
| ListNode(1, ListNode(x,y)) ->
| ListNode(x, y) ->
| x : 아무거나(named)
| _ : 아무거나(unnamed)

. program의 모든 부분이 strongly typed
. add-one
. run_twice (int->int) -> int -> int
. n! = n * (n-1) if n > 1
= 1 otherwise
. Polymorphism
. List -> 'a | 'a List

. 예제 프로그램
type tree = Leaf | Node of tree * tree;;

type tree = Leaf of int | Node of int * tree * tree;;
(* sum(lt) 대신 sum lt라고 써도 된다. *)
let rec sum t = match t with
| Leaf(x) -> x
| Node(x, lt, rt) -> x + (sum lt) + (sum rt);;

let value t = match t with
| Leaf i -> i
| Node (i, lt, rt) -> i;;

(* depth first search *)
let rec dfs t = match t with
| Leaf i -> print_int i
| Node (i, lt, rt) -> dfs lt; dfs rt; print_int i; ;;

(* tree t에 k라는 원소가 있는 지 본다. *)
let rec mem k t = match t with
| Leaf i -> k = i
| Node (i, lt, rt) -> (k = i) or (mem k lt) or (mem k rt);;
(* k = i은 bool type *)
(* or은 앞 expression 틀렸을 때 수행됨 *)

let mytree = Node(1, Node(2, Leaf 100, Leaf 4), Leaf 5);;
sum mytree;; => 112

(* map : ('a -> 'b) -> 'a list -> 'b list *)
let rec map f alist = match alist with
| [] -> []
| hd::tail -> (f hd)::(map f tail);;

(* alist에 el이라는 원소가 있는 지 본다. *)
let rec mem el alist = match alist with
| [] -> false
| hd::tail -> (hd = el) or (mem el tail);;

let rec gcd n m =
if n = 0
then m
else if n >= m
then gcd (n - m) m
else gcd m n;;

. Mutual recursive function
let rec f x = 블라 (g 블라) 블라
and g y = 블라 (f 블라) 블라

. Mutual recursive type(?)
type t1 = ... | C1 of ... * t2 * ... | ...
and t2 = ... | C2 of ... * t1 * ... | ...

. assignment statement(= side effect 생김)
let x = ref 0;
let _ = print_int !x;
let _ = x:=1;
let _ = print_int !x;

. head and tail
head::tail -> head === car, stack top
head::tail -> tail === cdr, stack pop

. Type
1. let rec gcd (n, m) = (int * int -> int) type
  => gcd (1,2) : OK
  => gcd 1 2 : error               

2. let rec gcd n m = (int -> int -> int) type
  => gcd (1, 2) : error
  => gcd 1 2 : OK

. Type
[] : list type - 같은 타입의 원소가 몇 개든 들어와도 됨. (다른 타입이 섞일 수 없음, 갯수가 맘대로)
() : tuple type - 원소의 갯수와 type이 정해짐. (다른 타입이 섞일 수 있음. 갯수가 고정)
list는 원소를 ;로 구분하고
tuple은 원소를 ,으로 구분해준다.
[1,2,3]은 [(1,2,3)]으로 해석함.

. Type
let rec eval t = match t with
| INT i -> i
| PLUS (ls, rs) -> (eval ls) + (eval rs)
| MINUS (ls, rs) -> (eval ls) - (eval rs)
| TIMES (ls, rs) -> (eval ls) * (eval rs);;
Characters 17-75:
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
INT _
  .................match t with

=> INT(i) -> i 로 적어야 됨. 괄호를 안치면 이런 에러가 남.

. Polymorphism
. 안전성(sound), 완전성(completeness)
. 안전성과 완전성은 둘 다 달성될 수 없다. trade-off 해야 한다.
. Polymorphism은 completeness를 위해 존재한다.
. completeness를 위해 soundness를 희생
let rec f x =
let _ = (f 1, f "")
in ();;
(ML의 type system이 허용하지 않음, LISP에서는 허용)
. ML => sound, LISP => complete

(* cmp 순으로된 두 list를 merge하기 *)
# let rec merge cmp l1 l2 = match (l1, l2) with
     | ([], lst) -> lst
     | (lst, []) -> lst
     | (h1 :: t1, h2 :: t2) ->
     match (cmp h1 h2, cmp h2 h1) with
     | (true, false) -> h1 :: (merge cmp t1 l2)
     | (false, true) -> h2 :: (merge cmp l1 t2)
     | _ -> h1 :: (merge cmp t1 t2);;
(* cmp match에서 h1 h2, h2 h1을 두개 비교하는 이유 *)
(* cmp에 등호가 들어갈 때나 아무튼 두 원소가 같은 경우 한 번만 적어주기 위함 *)

# let less x y = x < y;;
# merge less [1;3;5] [2;4;8];;

# merge less [1,3,5] [2,4,8];;

(* list의 구분자는 ;임 ,를 쓰면 안됨 *)
(* list를 2개의 list로 split 함 *)
let rec split list = match (list) with
                    | ([]) -> ([], [])
                    | ([x]) -> ([x], [])
                    | (x::y::tail) -> let (p, q) = (split tail) in (x::p, y::q) ;;

# split [1; 2; 3; 4; 5; 6; 7; 8;];;
- : int list * int list = ([1; 3; 5; 7], [2; 4; 6; 8])

(* tail recursive를 이용한 split 구현 *)
(* 속도가 더 빠르다. split하면서 값의 순서가 뒤집혀서 나온다. *)
let split x =
  let rec loop(p, q, r) = match(p, q, r) with
       | (p, q, []) -> (p, q)
       | (p, q, [a]) -> (a::p, q)
       | (p, q, a::b::rest) -> loop(a::p, b::q, rest) in loop([], [], x);;

split([1;2;3;4;5;6;7;8;9;10]);;
- : int list * int list = ([9; 7; 5; 3; 1], [10; 8; 6; 4; 2])

let rec sort less list = match (list) with
   | [] -> [] (* 이것이 없으면 stack overflow가 일어남. *)
   | [a] -> [a] (* 이것이 없으면 stack overflow가 일어남. *)
   | list -> let rec merge (l1, l2) = match (l1, l2) with                    
       | ([], a) -> a                                                        
       | (a, []) -> a                                                        
       | (h1::t1, h2::t2) ->                                                 
           if (less h1 h2) then h1::merge(t1, l2)                            
                           else h2::merge(t2, l1)                            
       and split l = match (l) with                                          
           | [] -> ([], [])                                                  
           | [x] -> ([x], [])                                                
           | (x::y::tail) -> let (p, q) = split tail in (x::p, y::q) in
       let (p, q) = split(list)                                                  
       in merge((sort less p), (sort less q));;

sort less [];;
sort less [1];;
sort less [1;2];;
sort less [2;1];;
sort less [1;2;3];;
sort less [2;1;3];;
sort less [3;2;1];;
sort less [10;9;8;7;6;5;4;3;2;1];;
sort less [1;2;3;4;5;6;7;8;9;10];;

. ML에서 Ocaml로 포팅하기
  . ML은 fun을 쓰지만 Ocaml에서는 let으로 쓰고 fun을 생략
  . Recursive function의 경우 ML은 rec을 안 쓰지만 Ocaml에서는 rec를 쓴다.
  . ML은 그냥 |으로 구분하지만 Ocaml은 match를 쓴다.
  ML은 =을 쓸 때 Ocaml은 ->을 쓴다.
  . ML은 nil, Ocaml은 []