[컴파일러] Assignment 0. Your First Functional Programming

경희대학교 허선영 교수님의 컴파일러 수업을 기반으로 정리한 글입니다.

 

OCaml(Objective Caml)

• Functional Programming Language: 함수의 구성 & 추가로 프로그램이 설계되는 Functional Programming 방식을 사용하는 언어
• Functional programming language에서 function은 인자로서 전달되고, 자료구조에 저장되고, function calls의 결과로 반환된다.
•  OCaml은 정적 타입 언어 -> 변수와 함수의 타입이 Compile time에 결정됨
• 한 번 변수를 바인딩하면 변경 불가 
  • x = x + 1 형태로 변경 불가
  • 값을 바꾸고 싶으면 새롭게 리바인딩해야함 let x = x + 1

Syntax

- Data Types 

- Operators

- Functions

- Other Syntax

 

Opam

• Opam: package manager of OCaml(like pip for Python)
• https://ocaml.org/docs/installing-ocaml

Installing OCaml · OCaml Documentation

 

eval $(opam env) -> dune 명령어 실행 전 실행

Task 1: Basic Functions

(* CSE322 Compiler Assignment 0 - Task 1 *)

exception NotImplemented

(* 1. Basic Recursion *)

(* sum n: calculate 1 + 2 + ... + n *)
let rec sum n = match n with
  | 0 -> 0
  | n -> n + sum (n-1)

(* fac n: calculate 1 * 2 * ... * n *)
let rec fac n = match n with
  | 0 -> 1
  | n -> n * fac (n-1)

(* fib n: return the n-th fibonacci number *)
let rec fib n = match n with
  | 0 -> 0
  | 1 -> 1
  | n -> fib(n-1) + fib(n-2)

(* pow (x, y): calculate x to the power of y *)
let rec pow (x, y) = 
  if y = 0 then 1
  else x * pow(x, y - 1)
  

(* gcd (x, y): find the great common divisor of x and y *)
let rec gcd (x, y) = 
  if y = 0 then x
  else gcd(y, x mod y)

(* palindrome s: return true if s is a palindrome *)
let rec palindrome s = 
  let n = String.length s in
  if n <= 1 then true
  else if (String.sub s 0 1) <> (String.sub s (n-1) 1) then false
  else palindrome(String.sub s 1 (n-2))

(* 2. List *)

(* max l: return the maximum value in l *)
let rec max l = match l with
  | [] -> 0
  | [x] -> x
  | hd::tl -> if hd > max tl then hd else max tl

(* exist l x: check if x exists in l *)
let rec exist l x = match l with
  | [] -> false
  | hd::tl -> if hd = x then true else exist tl x

(* count l x: count the number of x in l *)
let rec count l x = match l with
  | [] -> 0
  | hd::tl -> if hd = x then 1 + count tl x else count tl x

(* reverse l: return the reversed l *)
let rec reverse l = match l with
  | [] -> []
  | hd::tl -> reverse tl @ [ hd ]

(* find l x: return the index of the first x in l
*                   -1 if x does not exist in l *)
let rec find l x = match l with 
  | [] -> -1
  | hd::tl -> if hd = x then 0  (* 첫 번째 x를 찾으면 재귀 stop *)
              else 
                let index = find tl x in
                if index = -1 then -1
                else index + 1

(* findr l x: return the index of the last x in l
*                    -1 if x does not exist in l *)
let rec findr l x =   match l with
| [] -> -1  
| hd::tl -> 
    let result = findr tl x in  
    if result != -1 then result + 1  (* find의 경우와 달리 재귀함수가 마지막 깊이까지 탐색 *)
    else if hd = x then 0 
    else -1

 

Task 2: Binary Tree

(* CSE322 Compiler Assignment 0 - Task 2 *)

exception NotImplemented

type 'a tree = Leaf of 'a | Node of 'a tree * 'a * 'a tree

(* sum t: return the sum of all values *)
let rec sum t = match t with
  | Leaf x -> x
  | Node (t1,x,t2) -> (sum t1) + x + (sum t2)

(* exist t n: return true if n exists in a tree *)
let rec exist t n = match t with
  | Leaf x -> x = n (* base case *)
  | Node (t1, x, t2) -> (exist t1 n) || x = n || (exist t2 n)

(* count t n: count n in a tree *)
let rec count t n = match t with
  | Leaf x -> if x = n then 1 else 0
  | Node (t1, x, t2) -> if x = n then (count t1 n) + 1 + (count t2 n) 
                        else (count t1 n) + (count t2 n)

(* inorder t: return the list of values using inorder tree traversal *)
let rec inorder t = match t with
  | Leaf x -> [ x ]
  | Node (t1, x, t2) -> inorder t1 @ [ x ] @ inorder t2

(* depth t: return the depth of a tree*)
let rec depth t = match t with
  | Leaf x -> 0
  | Node (t1, x, t2) -> 
      let depth1 = (depth t1) + 1 in
      let depth2 = (depth t2) + 1 in
      if depth1 >= depth2 then depth1 else depth2

(* max t: return the maximum value in a tree*)
let rec max t = match t with
  | Leaf x -> x
  | Node(t1, x, t2) -> 
    let max1 = max t1 in
    let max2 = max t2 in
    if max1 > max2 then
      if x > max1 then x else max1
    else
      if x > max2 then x else max2