[UPL] Recursion

 

 

 

함수 몸체에서 자기자신을 직접 호출하는것도 재귀인자기가 부른 함수가 자기를 호출하는것도 재귀라고 할 수 있다. (간접 재귀)

 

조건 분기문을 추가한 언어인 CFVAE에서는 함수 몸체에서 함수 자신을 호출할 때 아직 자신이 정의되지 않은 상태라 저장소에 들어오지 않았고, 따라서 Recursion이 불가능하다. 

 

OCaml처럼 Concrete Syntax에 rec키워드를 추가해 rec가 붙어있으면 재귀호출이 가능한 함수, 붙어있지 않으면 재귀호출이 불가능한 함수로 구분해서 구현할 수 있는 RCFVAE 언어를 정의해보자.

 

 

 

일단 Concrete Syntax 먼저.. 

함수를 선언할 때 rec 키워드를 붙일 수 있도록 하자. 

 

기존 함수 정의를 사용할 때, expr1에서 var는 free identifier였지만

rec를 붙여서 함수를 정의할 때는 expr1에서 var은 expr1의 계산 결과인 clousure이다.

 

rec 유무에 따라 scope가 달라지도록 구현하자. 

 

함수 정의를 만나면 그 시점의 메모리를 캡쳐하고, 함수 호출을 만나면 메모리를 가져와서 몸체를 계산하기에 기존 함수 정의에서는 재귀가 불가능했다. 

 

 

 

 

 

Abstract Syntax는 위와 같이 정의된다. x 는 변수명 e1은 몸체 e2는 결과 

재귀함수를 정의하는거니까.. e1의 계산결과로 클로저가 나와야 한다. (아니면 오류 뱉어야 함)

 

 

 

일단 e1을 평가했을때 클로저가 나오는지 확인하고, 재귀 호출이 가능하도록 하기 위해 변수 x에 e1의 평가 결과인 클로저를 바인딩한 새로운 저장소 시그마2를 만들어둠.

이 시그마2를 가지고 e2의 본문을 평가한다. 새로 만들어 둔 저장소인 시그마2는 e2를 평가할 때만 사용된다. 

 

let f = fun x -> x + 1 in
f 3

let rec f = fun x -> if x = 0 then 1 else x * f(x - 1) in
f 3

 

 

rec이 안 붙은 함수에서 f 는 fun x -> x + 1 클로저로 바인딩됐는데, 클로저 내부에는 정의될 당시의 환경만 가지고 있으니 이 환경에는 f 가 없어서 재귀호출이 불가능.

 

rec을 붙이면 f 를 먼저 환경으로 등록하고 fun x ~ 를 평가함. 

즉, 클로저는 f를 포함하고 있으니 재귀 호출이 가능하다.

 

 

| Ast.RLetIn (str, e1, e2) -> 
		begin
			match (interp e1 s) with
			| Store.ClosureV (str', e, s') ->
				let s_cleaned = List.remove_assoc str s' in
				let rec s'' = (str, Store.ClosureV (str', e, s'')) :: s_cleaned in
				interp e2 s''
			| _ -> failwith (Format.asprintf "Not a function: %a" Ast.pp e1)
		end

 

 

OCaml로 해당 내용을 구현할 때는 이런식으로.. s'' 을 도입해서 처리하자. 

그냥 하려고 하면 let rec 오른쪽에 Store.add 함수호출이 나올 수 없다고 오류뜸.

 

let rec sum = (fun x -> 
	if x < 1 then 0
	else x + (sum (x - 1)))
in
sum 10

 

 

이 함수를 실행하면 무한 재귀로 스택이 터지는데.. 

저 구문은 (x < 1) 0 (x + sum(x-1)) 이렇게 Church Boolean 스타일로 변환된다.

함수 application 하려면 인자를 계산해야 하니, x에 0이 들어오더라도 sum(-1)을 호출하게 돼 sum(-1)이 호출되고.. 연쇄적으로 계속 재귀를 타며 스택이 터진다. 

 

인자를 미리 계산하지 않고 필요할 때만 계산해보자. - Lazy Evalutaion. Call by name, Call by need
x와 y를 받아서 x만 반환하는 경우 y는 사용되지 않으니 아예 계산하지 않으니 계산하지 않아도 된다. 

 

let add x y = x + y
in
add (1+2) (3+4)

 

Lazy Evaluation에서 (1+2) 와 (3+4) 는 그대로 넘어가고, 필요할 때 해당 부분을 만들어내서 3과 7을 만들어낸다.

Lazy든 Eager는 결과는 같아야 하는데..

 

Pure Functional Language에서는 Side Effect가 없으니 결과가 같음이 보장되지만, Imperative Language에서는 Statement가 메모리를 변경할 수 있으니 Lazy Evalutaion과 Eager Evaluation의 결과가 다를 수 있다. 

 

함수 호출 시 사용되는 값을 추상메모리에 저장할 때 인자를 계산하지 말고 얼려서 추상메모리에 반영하자. 

 

 

 

기존 Value 도메인을 확장해야 한다. 

Freezed 도메인을 추가해 표현식을 얼려서 전달할 수 있도록 수정하자.

 

얼려서 전달할 때 얼리는 시점의 메모리도 함께 얼려줘야 한다.

#e, 시그마#

 

 

변수를 만났을 때 Freeze된 값을 녹여서 사용한다. 값이 얼어있지 않으면 그대로.. 얼어있다면 녹여서.. 

 

인자로 넘길 때 안쓰는 요소들이 많다면 당연히 Freeze해서 전달하는게 합리적인데

(λx x x x x x x x x) e1 이런식으로 함수를 사용할 때는 e1을 매번 다시 계산하게 되니 Lazy Evalutaion방식의 성능이 매우 떨어진다.

 

그래서 Lazy Evaluation을 사용하는 언어는 Memoization을 사용해 한 번 녹였던 값을 기억해서 계속 사용한다.

 

 

 

---

 

 

 

Concrete Syntax에 let rec 키워드만 추가하고 Abstract Syntax까지 확장하는 대신 Syntatic Sugar로 Recursion을 처리해보자.

Fixpoint Combinator가 사용된다.

 

// Concrete Syntax
let rec f = fun n -> if n = 0 then 1 else n * f (n - 1) in f 3

// Desugaring
let f = fix (fun f -> fun n -> if n = 0 then 1 else n * f (n - 1)) in f 3

 

 

 

 

fix는 함수를 인자로 받아 함수의 fixpoint를 반환하는 함수이다. fix 는 fixpoint를 찾아주는 역할. 

fixpoint는 f(x) = x 를 만족하는 x를 의미한다.

 

함수에 따라 fixpoint가 없을 수도 있고, 함수마다 다른 fixpoint를 가지게 된다. 

당연히 fixpoint가 여러 개인 함수가 있을 수도 있고.. 

 

여러 번 합성해도 fixpoint는 동일하다. f(f(x)) = x / f(f(f(f(x)))) = x / fix f = f (fix f)

 

 

 

let rec sum x = if x < 1 then 0 else x + sum (x - 1) 하고 싶은건 이건데, lec rec를 사용할 수 없으니 fix를 사용하자.

재귀를 못 쓰니까 F 로 바꿔서 정의하는 것. fix F = F (fix F) 에서 재귀를 정의한다. 

 

하나씩 쭉 따라가면 뭐.. 인자가 두 개 이상인 함수에서는 커링을 적용해서 똑같은 방식으로 진행한다. 

 

F는 내가 직접 쓰는 재귀 함수의 본체, fix로 묶어서 진짜 재귀로 변환한다. 

즉, F는 함수를 인자로 받는 함수로 이걸 재귀처럼 사용하는 sum 본체를 돌려주는 함수라고 생각하면 됨.. 

 

fix f = f ( fix f) 로 넘기는 f 는 재귀함수가 아니여야 하고, fix는 재귀를 만들어주는 함수라고 생각.

즉, f는 아직 자신을 호출하지 않고 자신처럼 행동하는 외부 함수를 매개변수로 받는다. 

fix f 는 구현하려는 재귀함수의 Desugaring된 형태.