목차
📁 First-class Functions
First-class function와 second-class function의 차이점은 아래 포스팅에서 자세히 설명한다.
first-class function은 함수를 "값"으로 취급하기 때문에 다음과 같은 행동이 가능하다.
- 함수를 변수에 저장할 수 있다.
- 함수를 함수의 인자로 전달할 수 있다.
- 함수를 반환할 수 있다.
Functional language는 기본적으로 first-class function(high-order function)을 지원한다.
📁 Extension of VAE : FVAE 1
해당 포스팅에서는 VAE에 함수를 추가하여 확장한 FVAE(First-class Function and VAE)를 정의한다.
FVAE 언어는 다음과 같이 정의된다.
지금 구현할 FVAE 1에서는 anonymous function(이름없는 함수)만 지원하며, 아래 FVAE 2에서 이름있는 함수를 다룬다.
(fun x -> x + 1)
anonymous function을 변수와 binding함으로써 이름부여와 동일한 효과를 줄 수 있다.
let f = (fun x -> x + 1) in ...
이름없는 함수와 비교를 위해 작성하자면, 위 코드의 이름있는 함수 형태는 다음과 같이 나타낼 수 있다.
let f x = x + 1 in ...
📁 FVAE의 Concrete syntax
FVAE는 하나의 표현식으로 이루어진 프로그램이다.
가장 상단의 expr은 이를 의미한다.
# (fun var -> expr)는 anonymous function을 생성하는 concrete syntax이다.
var는 파라미터를, expr는 함수몸체를 말한다.
# expr expr는 함수호출, 즉 함수를 적용하는 concrete syntax이다.
함수형 프로그래밍에서는 funciton call(함수호출) 대신 function application(함수적용)이라고 말한다.
예를 들어 다음과 같은 코드가 있다고 하자.
1. let f = (fun x -> x - 1) in f 3
2. let f = (fun x -> x + y) in (f 2) 3
3. let f = (fun x y -> x + y) in f 2 31번은 f를 3에 적용(apply)했다고 말하고,
2번은 (f 2)를 3에 적용(apply)했다고 말하고,
3번은 f를 2에 적용한 것을 3에 적용했다고 말하면되나?
📁 FVAE 1의 Abstract syntax
빨간 글씨가 FVAE 1에 새로 추가된 Abstract syntax이다.
𝜆x.e
lambda abstraction(람다 추상화)를 의미하는 abstract syntax이다.
람다 추상화란, λ 람다 기호와 함께 무언가를 함수로 정의하는 것을 말한다.
이때 𝜆x.e는 파라미터 x를 받아 함수 몸체인 e라는 expression으로 치환하는 익명의 함수를 뜻한다.
즉 x는 binding occurrence이고, scope는 e이다.
예를 들어 왼쪽과 같은 함수를 람다 추상화하면 오른쪽과 같이 표현할 수 있다.
f(x) = x + 1 -> λx.x+1
𝜆x.e는 아래 트리를 나타내는 축약코드이다.
x가 Var 집합에 속하는 원소이고, e가 Expr 집합에 속하는 원소일 때
위와 같은 트리가 Expr 집합에 속함을 의미한다.
e1 e2
function application(함수 적용)을 의미하는 abstract syntax이다.
e1는 함수로 계산되는 expression이고,
e2는 인자이다.
e1 e2는 아래 트리를 나타내는 축약코드이다.
e1과 e2가 Var 집합에 속할 경우, 위와 같은 트리가 Expr 집합에 속함을 의미한다.
🔎 OCaml 구현
위 Abstract syntax를 다음과 같이 expr 타입으로 구현할 수 있다.
type expr =
| Num of int
| Id of string
| Add of expr * expr
| Sub of expr * expr
| LetIn of string * expr * expr
| App of expr * expr
| Lambda of string * expr
📁 Value Domain in FVAE
FVAE는 first-class function을 지원하므로, 함수고 "값"이기 때문에 "값"의 확장이 요구된다.
기존의 AE, VAE, F1VAE는 함수가 없었거나, 함수를 "값"으로 보지 않았기 때문에 Value Domain은 정수만으로 충분했다.
FVAE의 Value Domain은 위와 같이 수정된다.
Closure란 모든 함수 "값"의 집합을 말한다.
- Var : 파라미터(인자)
- Expr : 함수 몸체
- Store : 함수가 정의된 시점의 추상메모리
이때 Store는 lexical scope 지원을 위해 필요하다.
Domain Composition
FVAE의 경우와 같이 domain의 확장이 필요할때 기존 domain들의 합을 통해 새로운 domain을 정의할 수 있는데, 이 작업을 domain composition이라고 한다.
A와 B는 기존의 domain, C는 두 domain의 합으로 새로 정의된 domain이다.
이때 domain은 집합이므로, 두 도메인의 합은 집합간의 union(합집합)으로 정의할 수 있다.
즉 FVAE의 새 Value Domain도 union(합집합)으로 표현할 수 있다.
이때 값의 원소는 v,
정수의 원소는 n으로 표기하며,
Closure의 원소는 < 𝜆x.e, σ > 와 같이 표기한다.
𝜆x.e의 x는 Var(파라미터) , e는 Expr (함수몸체), σ는 가상메모리를 의미한다.
🔎 OCaml 구현
type value = NumV of int
| ClosureV of string * expr * Store.t
📁 Store in FVAE
Value Domain의 변경에 따라, 값을 저장하는 추상메모리의 변경도 요구된다.
VAE와, F1VAE의 Value Domain은 정수뿐이었으므로, Store 집합은 변수를 받아 정수를 반환하면 됐었다.
하지만 FVAE의 Value Domain에 Closure가 추가되었으므로,
추상메모리 집합 Store는 변수 Var를 받아 Value 자체를 반환하도록 수정하면 된다.
🔎 OCaml 변환
type value = NumV of int
type t = (string * value) list기존의 Store와 Value는 이와 같이 구현되었고, 이를 FVAE에서 Value Domain의 확장에 맞추어 아래와 같이 수정할 수 있다.
type t = (string * value) list
and value = NumV of int
| ClosureV of string * Ast.t * ttype t가 Store를 구현한 부분인데, 해당 부분에서 직접적으로 바뀐 부분은 없다.
여전히 string값인 변수, value값인 내용의 튜플로 구성되는 리스트이다.
하지만 value domain이 바뀌면서 Closure로 value 자체에서 store를 저장해야하는 일이 생겼고, 이를 위해 type t와 value를 and로 묶어 서로를 참조할 수 있도록 구현하였다.
Caution : Circular dependency
위에서 type간의 상호참조를 and 키워드로 구현할 수 있었지만,
파일간의 상호참조는 엄격하게 금지되어있다.
예를 들어 file A에서 file B를 참조하고, file B에서 file A를 참조하고자 한다고 하자.
이처럼 서로 다른 파일간 상호 참조를 하게 되면 circular dependency(순환 참조)가 발생하며,
file A를 컴파일하려면 file B가 필요한데 file B를 컴파일하려면 file A가 필요한 상황이 되므로 컴파일이 불가능해진다.
이와 같은 주의사항때문에 FVAE에서 Store를 구현한 type t와 Value를 구현한 type value를 다른 파일에 따로 구현하지 않고, 하나의 파일 안에 and 키워드로 상호참조함으로써 Circular dependency가 발생하지 않도록 한다.
📁 FVAE의 Semantics
# semantic relation
# Semantics
1. Substitution
2. Store
# Formal Semantics
1. Substitution
2. Store
📁 Example of FVAE 1
(fun y -> y + 1)
(* < 𝜆y.y + 1, [ ] > *)
(fun y -> y + 1) 2
(* < 𝜆y.y + 1, [ ] >⇒ [ ] ⊢ 2 + 1 ⇓E 3 *)
let x = (fun y -> y + 1) in
x 2
(* [x ↦→< 𝜆y.y + 1, [ ] >] ⊢ x 2 ⇓E 3 *)
let foo = (fun x -> x + 1) in
(* 𝜎 = [foo ↦→< 𝜆x.x + 1, [ ] >] *)
let bar = (fun x -> x - 1) in
(* 𝜎 = [foo ↦→< 𝜆x.x + 1, [ ] >, bar ↦→< 𝜆x.x − 1, [foo ↦→< 𝜆x.x + 1, [ ] >] >] *)
foo (bar 3)
(* foo (bar 3) ⇒ foo (< 𝜆x.x − 1, [foo ↦→< 𝜆x.x + 1, [ ] >] > 3) ⇒ foo 2 ⇒ < 𝜆x.x + 1, [ ] > 2 ⇒ 3 *)
let foo = (fun x -> x + 1) in
(* 𝜎 = [foo ↦→< 𝜆x.x + 1, [ ] >] *)
let bar = (fun x -> foo x) in
(* 𝜎 = [foo ↦→< 𝜆x.x + 1, [ ] >, bar ↦→< 𝜆x.foo x, [foo ↦→< 𝜆x.x + 1, [ ] >] >] *)
foo (bar 3)
(* foo (bar 3) ⇒ foo (< 𝜆x.foo x, [foo ↦→< 𝜆x.x + 1, [ ] >] > 3) ⇒ foo (< 𝜆x.x + 1, [ ] > 3) * ⇒ foo 4 ⇒ < 𝜆x.x + 1, [ ] > 4 ⇒ 5 *
let foo = (fun x -> x + 1) in
(* 𝜎 = [foo ↦→< 𝜆x.x + 1, [ ] >] *)
let bar = (fun x -> x 1) in
(* 𝜎 = [foo ↦→< 𝜆x.x + 1, [ ] >, bar ↦→< 𝜆x.x 1, [foo ↦→< 𝜆x.x + 1, [ ] >] >] *)
bar foo
(* bar foo ⇒ < 𝜆x.x 1, [foo ↦→< 𝜆x.x + 1, [ ] >] > foo
* ⇒ < 𝜆x.x 1, [foo ↦→< 𝜆x.x + 1, [ ] >] > < 𝜆x.x + 1, [ ] > ⇒ < 𝜆x.x + 1, [ ] > 1 ⇒ 2 *)
let foo = (fun x -> (fun y -> y + x)) in
(* 𝜎 = [foo ↦→< 𝜆x.𝜆y.y + x, [ ] >] *)
foo 2 3
(* foo 2 3 ⇒ < 𝜆x.𝜆y.y + x, [ ] > 2 3 ⇒ < 𝜆y.y + 2, [ ] > 3 ⇒ 5 *)
(* foo 2 3 ⇒ < 𝜆x.𝜆y.y + x, [ ] > 2 3 ⇒ < 𝜆y.y + x, [x ↦→ 2] > 3 ⇒ 5 *)
📁 Lexical scope vs. Dynamic scope
Lexical Scope
let x = 0 in
(* 𝜎 = [x ↦→ 0] *)
let f = (fun y -> y + x) in
(* 𝜎 = [x ↦→ 0, f ↦→< 𝜆y.y + x, [x ↦→ 0] >] *)
let x = 99 in
(* 𝜎 = [x ↦→ 99, f ↦→< 𝜆y.y + x, [x ↦→ 0] >] *)
f 1
(* f 1 ⇒ < 𝜆y.y + x, [x ↦→ 0] > 1
* ⇒ [x ↦→ 0] ⊢ 1 + x ⇓E 1 *)
(* f 1 ⇒ < 𝜆y.y + x, [x ↦→ 0] > 1
* ⇒ [x ↦→ 0, y ↦→ 1] ⊢ y + x ⇓E 1 *)
Dynamic Scope
let x = 0 in
(* 𝜎 = [x ↦→ 0] *)
let f = (fun y -> y + x) in
(* 𝜎 = [x ↦→ 0, f ↦→< 𝜆y.y + x, [x ↦→ 0] >] *)
let x = 99 in
(* 𝜎 = [x ↦→ 99, f ↦→< 𝜆y.y + x, [x ↦→ 0] >] *)
f 1
(* f 1 ⇒ < 𝜆y.y + x, [x ↦→ 0] > 1
* ⇒ [x ↦→ 99, f ↦→< 𝜆y.y + x, [x ↦→ 0] >] ⊢ 1 + x ⇓E 100 *)
(* f 1 ⇒ < 𝜆y.y + x, [x ↦→ 0] > 1
* ⇒ [x ↦→ 99, f ↦→< 𝜆y.y + x, [x ↦→ 0] >] ⊢ y + x ⇓E 100 *)
📁 Extension of VAE : FVAE 2 (Named function support)
위에서 정의한 FVAE1을 더욱 확장하여 FVAE가 이름있는함수을 지원하도록 할 수 있다.
해당 확장은 Syntactic sugar를 지원하므로 concrete syntax와 parser의 수정만 진행된다.
Concrete Syntax
let var1 var2 = expr1 in expr2는 이름있는 함수를 정의하는 concrete syntax이다.
- var1 : 함수 이름
- var2 : 파라미터(인자)
- expr1 : 함수몸체
- expr2 : 함수 정의 후 실행할 expression(함수의 scope)
Parser
위에서 정의한 Concrete syntax를 pasing하면 위와 같은 abstract syntax가 되도록 parser를 수정한다.
이때 파싱의 결과로 나온 abstract syntax는 기존 FVAE의 abstract syntax 중 위 syntax의 형태와 같다.
즉 syntactic sugar로 정의되었으므로 abstract syntax에는 변화가 없다.
parse("let foo x = x + 1 in foo 3")
= let foo = (𝜆x. x + 1) in foo 3새 parser를 사용한 예시는 이와 같다.
📁 Extension of VAE : FVAE 3 (Multiple parameters support)
위에서 정의한 FVAE2를 더욱 확장하여 FVAE가 다수의 인자를 받는 함수를 정의할 수 있도록 할 수 있다.
해당 확장은 Syntactic sugar를 지원하므로 concrete syntax와 parser의 수정만 진행된다.
Concrete Syntax
(fun var_list -> expr)는 다수의 인자를 받는 함수를 정의하는 concrete syntax이다.
- var_list : 파라미터(인자)의 나열
- expr : 함수몸체
Parser
위에서 정의한 Concrete syntax를 pasing하면 위와 같은 abstract syntax가 되도록 parser를 수정한다.
이때 파싱의 결과로 나온 abstract syntax는 기존 FVAE의 abstract syntax 중 위 syntax의 형태와 같다.
즉 syntactic sugar로 정의되었으므로 abstract syntax에는 변화가 없다.
parse("(fun x y -> x + y) 1 3")
= (𝜆x.𝜆y.x + y) 1 3새 parser를 사용한 예시는 이와 같다.
