• 제출방법 : 작성한 프로젝트를 ‘{학번}’라는 이름으로 저장한 후 압축하여 Uclass 과제 게시판에 업로드해주세요. 채점은 스크립트로 자동으로 이루어지기에 폴더 이름이 잘못되어서 채점되지 못하면 0점을 받게 됩니다.
  • 예시: 학번이 202448015인 학생은 다음과 같은 프로젝트를 202448015.zip으로 압축해서 제출해야 합니다.

    202448015
    ├── dune-project
    ├── src
    │   ├── ast.ml
    │   ├── dune
    │   ├── interpreter.ml
    │   ├── lexer.mll
    │   └── parser.mly
    └── test
        ├── dune
        └── main.ml 
  

• 제출기한 : 5월 22일 목요일 11:59pm

과제 진행 시 어려운 점이 있으면 Ed Discussion 게시판을 이용해 질문하세요. 게시판을 통해 하기 어려운 질문이라면 아래 TA 이메일을 통해 문의하시기 바랍니다.

• TA 이메일: seongminkim16@gmail.com

이번 과제에서는 함수를 정의하고 호출할 수 있게 언어를 확장합니다. 과제로는 재귀함수를 구현하게 됩니다.

함수의 정의와 호출

지금까지의 언어에 함수를 정의하고 호출 할 수 있는 기능을 추가하자.

fun x -> e는 x를 인자로 받아서 e의 계산 결과를 반환하는 익명 함수를 정의한다. 이때, x를 형식 인자(formal parameter), e를 함수의 몸통식(body expression)이라 한다. 인자 x의 값은 몸통식에서만 사용할 수 있다.

e1 e2에서 e1은 호출할 함수를 계산하는 식이고, e2는 함수의 인자를 계산하는 식이다. e2의 값을 실제 인자(actual parameter)라고 한다.

prog ::= e
e ::= x
    | i
    | b
    | e1 bop e2
    | if e1 then e2 else e3
    | let x = e1 in e2
    | fun x -> e
    | e1 e2
bop ::= + | - | * | / | <=
x ::= <identifiers>
i ::= <integers>
b ::= true | false

이 언어로 표현 가능한 것들은 다음과 같다.

fun x -> (x + 1)
fun x -> (let y = x + 1 in if y <= 0 then x else y)
fun x -> (fun y -> (x + y))
fun f -> (f 1)
let f = fun x -> (x + 1) in (f 2)
let f = fun x -> (x + 1) in (f (f 2))
(fun f -> (f (f 2))) (fun x -> (x + 1))

이처럼 함수를 이름에 바인딩할 수 있고, 다른 함수의 인자로 넘길 수 있으며, 다른 함수의 결괏값으로 반환할 수 있을 때, 우리는 함수가 일등 시민(first-class citizen)이라고 하며 언어가 고차함수(higher-order function)를 지원한다고 한다.

한 가지 흥미로운 점은 let x = e1 in e2와 (fun x -> e2) e1은 동일하다는 것이다. 두 표현식 모두 x를 대신해 e1의 값을 사용하여 e2를 계산한다. 이렇게 let 표현식과 같이 다른 구문으로 표현 가능하지만 프로그램 작성의 편의를 위해 추가된 구문을 설탕 구조(syntactic sugar)라고 한다.

함수의 정의와 호출 구현 (hw5_dynamic)

함수를 정의할 수 있는 키워드인 fun과 ->을 lexer에 추가한다. (lexer.mll)

  | "fun" { FUN }
  | "->" { ARROW }

parser는 우선순위(precedence)와 결합성(associativity)을 명확하게 표현하기 위해 계층 구조로 변경한다. (parser.mly)

/* 코드 생략 */

%token FUN
%token ARROW

/* 코드 생략 */

prog:
  | expr; EOF { $1 }
;

expr:
  | LET; ID; EQUALS; expr; IN; expr { Let ($2, $4, $6) }
  | IF; expr; THEN; expr; ELSE; expr { If ($2, $4, $6) }
  **| FUN; ID; ARROW; expr { Fun ($2, $4) }**
  | comp_expr { $1 }
;

comp_expr:
  | comp_expr; LEQ; arith_expr { Binop (Leq, $1, $3) }
  | arith_expr { $1 }
;

arith_expr:
  | arith_expr; PLUS; term { Binop (Add, $1, $3) }
  | arith_expr; MINUS; term { Binop (Sub, $1, $3) }
  | term { $1 }
;

term:
  | term; TIMES; app_expr { Binop (Mult, $1, $3) }
  | term; DIV; app_expr { Binop (Div, $1, $3) }
  | app_expr { $1 }
;

app_expr:
  | app_expr; atom { App ($1, $2) }
  | atom { $1 }
;

atom:
  | INT { Int $1 }
  | ID { Var $1 }
  | TRUE { Bool true }
  | FALSE { Bool false }
  | LPAREN; expr; RPAREN { $2 }
;

%%

함수와 호출을 나타내는 AST 노드도 정의해준다. (ast.ml)

  | Fun of string * expr
  | App of expr * expr

함수는 값이기에 value type에 새롭게 함수를 등록해준다. (interpreter.ml)

  | Fun of var * expr

최종적으로 eval function에 함수의 정의와 호출 부분을 처리해준다.

1. 함수의 정의라면 expression type을 value type으로 바꾼다.
2. 함수의 호출이라면 먼저 현재 환경으로 e1을 계산한다. 이제 실제 인자인 e2를 현재 환경으로 계산한 뒤에 이 값을 형식 인자에 바인딩한 환경으로 몸통식 e를 계산한다.

  | Fun (x, e) -> Fun (x, e)
  | App (e1, e2) -> begin
      match eval env e1 with
        | Fun (x, e) -> let v2 = eval env e2 in eval (extend_env (x, v2) env) e
        | _ -> failwith "First argument of application must be a function"
    end

이때 다음과 같은 식은 제대로 처리가 되지 않는데,

utop ### interpret "fun x -> x + 1 2";;
- : value =
Fun ("x",
 HW5.Ast.Binop (HW5.Ast.Add, HW5.Ast.Var "x",
  HW5.Ast.App (HW5.Ast.Int 1, HW5.Ast.Int 2)))

이는 OCaml에서도 마찬가지다.

utop ### fun x -> x + 1 2;;
Error: This expression has type int
       This is not a function; it cannot be applied.

이는 괄호를 추가하여 해결 가능하다.

utop ### interpret "(fun x -> x + 1) 2";;
- : value = Int 3

이제 다음의 계산 결과를 보자.

utop ### interpret "let x = 1 in let f = fun y -> (x + y) in let x = 2 in let g = fun y -> (x + y) in (f 1) + (g 1)";;
- : value = Int 6

결과가 6이라는 점은 이해하기 어렵다. OCaml에서 이 값은 5로 계산된다.

utop ### let x = 1 in let f = fun y -> (x + y) in let x = 2 in let g = fun y -> (x + y) in (f 1) + (g 1);;
- : int = 5

이 이유를 알기 위해 자유 변수라는 개념을 소개한다.

자유 변수

프로그램에 등장하는 변수들은 자유 변수(free variable)와 묶인 변수(bound variable)로 구분됩니다. 자유 변수란 주어진 식에서 정의를 찾을 수 없는 변수입니다. 즉, 값을 어디서 가져와야 하는지 식 자체만으로는 알 수 없습니다. 그렇기에 자유 변수의 값은 환경에서 가져와야 합니다. 반면에 주어진 식에서 정의를 찾을 수 있는 변수는 묶인 변수라고 합니다.

표현식 E에 등장하는 자유 변수들의 집합을 FV(E)라고 하며, 이는 귀납적으로 정의됩니다.

식 E에 등장하는 모든 변수들의 집합을 VAR(E)라고 할 때, 묶인 변수들의 집합은 VAR(E) \ FV(E)로 정의됩니다.

다음 식에서 자유 변수를 계산해 봅시다.

let g = fun y -> (x + y) in (f 1) + (g 1)

1. fun y -> (x + y)

   → 내부 식 x + y의 자유 변수는 {x, y}

   → 함수는 y를 바인딩하므로, FV(fun y -> (x + y)) = {x}

2. f 1

   → 함수 f가 어디서도 정의되지 않았으므로 자유 변수 {f}

3. g 1

   → 함수 g가 어디서도 정의되지 않았으므로 자유 변수 {g}

4. 전체 식

   → let g = ... in ... 구조에 따라 ${x} \cup ({f, g} \setminus {g})$

최종적으로 자유 변수는 f와 x가 됩니다.

함수의 의미는 이러한 자유 변수의 값을 해석하는 방식에 따라 달라집니다. 자유 변수의 값을 그 함수가 정의되는 시점에서의 환경으로 해석하는 것을 정적 유효 범위(static scope)라 합니다. 반면, 자유 변수의 값을 함수가 호출되는 시점에서의 환경으로 해석하면 이를 동적 유효 범위(dynamic scope)라 합니다.

동적 유효 범위와 달리 정적 유효 범위는 프로그램을 실행하지 않고도 모든 변수의 유효범위를 알 수 있기에 많은 언어에서 채택됩니다. 실제로 Emacs LISP, LaTeX과 같은 언어들을 제외하고는 대부분이 정적 유효 범위를 기본으로 사용합니다.

위의 구현에서는 함수의 몸통식을 계산할 때, 현재 환경으로 그대로 사용했습니다. 그렇기에 동적 유효 범위를 가지게 됩니다. 그렇기에 정적 유효 범위를 가지는 OCaml과는 다른 결과가 나온 것입니다. 이제 정적 유효 범위를 구현해 봅시다.

정적 유효 범위 구현 (hw5_static)

정적 유효 범위를 지원하기 위해서는 함수가 정의되었을 당시의 환경이 필요하다. 그렇기에 함수의 값을 다음과 같이 정의한다. (interpreter.ml)

    | Fun of var * expr * env

이렇게 정의한 함수값을 클로저(closure)라고 한다. 이는 함수를 호출하기 위해 필요한 모든 정보를 담고 있는 값이라는 뜻이다.

이제 value의 정의에 env의 정보가 필요하고 env의 정의에 value가 필요하니 이둘을 상호적으로 정의해준다.

type value =
    | Int of int
    | Bool of bool
    | Fun of var * expr * env
and env = (var * value) list

이렇게 함수가 정의되었을 때의 환경을 얻어내었다면, 이를 함수 몸통식을 계산할 때 활용하면 된다.

  | Fun (x, e) -> Fun (x, e, env)
  | App (e1, e2) -> begin
        match eval env e1 with
            | Fun (x, e, fun_env) -> let v2 = eval env e2 in eval (extend_env (x, v2) fun_env) e
            | _ -> failwith "First argument of application must be a function"
    end

utop ### interpret "let x = 1 in let f = fun y -> (x + y) in let x = 2 in let g = fun y -> (x + y) in (f 1) + (g 1)";;
- : value = Int 5

추가로 다음의 코드도 정상적으로 작동한다. 이 코드는 동적 스코프에서는 동작하지 않는다.

utop ### interpret "let f = fun x -> (fun y -> (x + y)) in ((f 3) 4)";;
- : value = Int 7

재귀 함수 (hw5_static)

다음의 프로그램을 생각해보자. 재귀 함수를 의도한 것이지만 정적 유효 범위에서는 작동하지 않는다.

utop ### interpret "let f = fun x -> if x <= 0 then 1 else x * f (x - 1) in f 5";;
Exception: Failure "f is not found".

let으로 f를 정의한 직후의 환경은 다음과 같다.

이 환경에서 함수 호출 f 5를 실행하면 먼저 환경에서 f에 대한 정보를 가져온다. 이때, f가 정의되었던 환경은 $\emptyset$이다. 이제 형식 인자에 5를 바인딩하고 환경을 ${x \rightarrow 5}$로 업데이트한다. 이제 이 환경으로 함수의 몸통식을 계산한다. 하지만, 이때, f에 대한 정보는 환경에 존재하지 않는다. 따라서 현재 언어에서는 재귀 함수를 사용할 수 없다.

이를 해결하기 위해 다음과 같이 문법을 확장한다.

prog ::= e
e ::= x
    | i
    | b
    | e1 bop e2
    | if e1 then e2 else e3
    | let x = e1 in e2
    | fun x -> e
    **| let rec f x = e1 in e2**
    | e1 e2
bop ::= + | - | * | / | <=
x ::= <identifiers>
i ::= <integers>
b ::= true | false

let rec f x = e1 in e2의 형태는 let rec f = fun x → e1 in e2의 구문 설탕 형태이다.

이를 통해 다음과 같은 식을 계산할 수 있다.

utop ### interpret "let rec f x = if x <= 0 then 1 else x * f (x - 1) in f 5";;
- : value = Int 120

Letrec이라는 새로운 value 타입을 정의한다. 이 타입은 함수 이름, 형식 인자 이름, 몸통식, 함수가 정의된 환경을 저장한다.

  | Letrec of var * var * expr * env

이제 환경에 재귀 함수 이름, 형식 인자 이름, 몸통식, 환경을 포함하여 in 뒤의 표현식을 계산한다.

  | Letrec (f, x, e1, e2) -> let rec_val = Letrec (f, x, e1, env) in let new_env = extend_env (f, rec_val) env in eval new_e

과제 (hw5_static)

interpreter.ml을 수정하여 재귀함수 호출을 구현해주세요.

주의: interpreter.ml을 제외하고는 수정하실 수 없습니다.

  | App (e1, e2) ->
      let v1 = eval env e1 in
      let v2 = eval env e2 in
      match v1 with
      | Fun (x, e, fun_env) -> eval (extend_env (x, v2) fun_env) e
      | Letrec (f, x, e, fun_env) ->

      (*
	     코드를 채워주세요.
      *)

      | _ -> failwith "First argument of application must be a function"