[PL] Recursion

📁 Recursion

재귀호출이란 함수가 자기자신을 호출하는 것을 말한다.

 

직접호출(direct recursion)이란 함수 몸체에서 자기자신을 호출하는 것을 말한다.

(* direct recursion *)
let rec sum (x : int) : int =
    match x with
        | 0 -> 0
        | _ -> x + (sum (x - 1))

 

 

간접호출(indirect recursion)이란 자기가 부른 함수를 자기가 호출하는 것을 말한다.

(* indirect(mutual) recursion *)
let rec is_even (x : int) : bool =
    if x = 0 then true
    else is_odd (x-1)

and is_odd (x : int) : bool =
    if x = 0 then false
    else is_even (x-1)

 

 

CFVAE에서는 위 코드가 runtime error를 발생시킨다.

함수 몸체에서 호출되는 sum이 Free identifier이기 때문이다.

 

 

 

📁 Extension of CFVAE: RCFVAE

해당 포스팅에서는 CFVAE를 확장하여 재귀함수를 지원하는 RCFVAE(Recursion and CFVAE)를 정의한다.

 

RCFVAE 언어는 다음과 같이 정의된다.

 

 

📁 Concrete Syntax in RCFVAE

RCFVAE는 하나의 표현식으로 이루어진 프로그램이다.

가장 상단의 expr은 이를 의미한다.

 

 

📁 Abstract Syntax in RCFVAE

빨간 글씨가 RCFVAE에 새로 추가된 Abstract syntax이다.

 

 

let rec x = e1 in e2

재귀함수 정의를 의미하는 abstract syntax이다.

 

x는 함수 이름이고,

e1는 재귀함수이고,

e2는 재귀함수 정의 후 실행할 expression이다.

 

 

let rec x = e1 in e2는 아래 트리를 나타내는 축약코드이다.

 

 

 

🔎 OCaml 구현

위 Abstract syntax를 다음과 같이 expr 타입으로 구현할 수 있다.

type expr = Num of int
| Name of string
| Add of expr * expr
| Sub of expr * expr
| LetIn of string * expr * expr
| RLetIn of string * expr * expr
| App of expr * expr
| Lambda of string * expr
| LessThan of expr * expr

 

 

📁 Semantics in RCFVAE

Semantics

 

 

Formal Semantics

 

 

 

📁 Lazy evalution(늦은 계산)

expression을 등장 시점에 바로 계산하지 않고 사용될 때 계산하여 사용하는 방법이다.

 

함수호출에서 lazy evaluation이 적용되면, 함수 호출 시점에서 인자를 계산하는것이 아니라, 함수 몸체에서 사용될 때 계산한다.

이렇게 함수 호출과 관련하여 사용되는 lazy evaluation은 call-by-name, call-by-need라고도 부른다.

 

대부분의 Functional programming language는 lazy evaluation도 지원한다.

 

 

Eager evalution과 반대되는 개념으로, Eager evalution이란 expression을 등장 시점에 바로 계산하는 전형적인 방법이다.

대부분의 프로그래밍언어에서는 Eager evalution 방법으로 함수호출을 수행한다.

 

예를 들어 인자를 먼저 계산하는 것과 같다.