목차
📁 Function(함수)
Function(함수)란 특정 동작을 수행하는 코드를 하나로 묶어 활용하는 코드뭉치를 말한다.
예를 들면 다음과 같은 함수가 있다.
- printf 함수 : 문자열을 화면에 출력한다.
- read_line 함수 : 사용자의 입력을 받아 문자열로 반환한다.
수학의 "함수"에서 기원했지만, 프로그램의 함수에는 side-effect(부작용)이 존재한다.
예를 들면 함수에 같은 값을 전달해도 다른 값을 반환할 수 있다.
수학에서는 f라는 함수에 1이라는 값을 아무리 많이 전달해도 항상 같은 값이 나오지만,
프로그램에서는 f라는 함수에 1이라는 값을 전달할 때마다 결과값이 바뀔 수 있다.
📁 First-order function(일차원 함수) vs Higher-order function(고차원 함수)
📌 First-order function이란 함수를 인자로 전달받지도, 반환하지도 않는 함수를 말한다.
함수를 변수와 다르게 특별 취급하며, 함수의 이름과 변수의 이름을 명확하게 구분한다.
함수와 변수의 사용처가 명확하게 다르므로, 별도의 메모리 공간에 함수와 변수를 따로 저장한다.
즉 이를 구현할때는 Store 외에 함수를 저장할 별도의 메모리가 필요하고, 아래에서는 Fstore로 명명하였다.
함수를 2등 시민 취급한다는 의미로, Second-class function라고도 한다.
대부분의 imperative language(non-functional language)는 first-order function을 지원한다.
📌 Higher-order function이란 함수를 인자로 받거나 반환하는 함수를 말한다.
함수와 변수를 별도로 구분하지 않고 동일하게 취급한다는 의미로 First-class function이라고도 한다.
대부분의 Functional langauge는 higher-order function을 지원한다.
밑에서 구현할 F1VAE 언어에서는 first-order function을 지원한다.
즉 High-order function을 지원하지 않는다는 말과 같다.
📁 Extension of VAE : F1VAE
해당 포스팅에서는 VAE에 함수를 추가한 F1VAE(First-order Function and VAE)를 정의한다.
F1VAE 언어는 다음과 같이 정의된다. (언어가 정의된다는 표현이 맞나?)
F1VAE 언어의 예시는 다음과 같다.
🔎 Concrete syntax
F1VAE는 하나의 함수 정의와 하나의 표현식으로 이루어진 프로그램이다
number, var는 VAE와 동일하다.
prog는 F1VAE의 프로그램을 말한다.
decl은 하나의 인자를 받는 함수의 정의를 말한다.
var(expr)는 함수 호출을 말한다.
🔎 Abstract syntax
d e는 아래 트리를 나타내는 축약코드이다.
def x x = e는 아래 트리를 나타내는 축약코드이다.
x(e)는 아래 트리를 나타내는 축약코드이다.
🔎 OCaml 구현
type expr = Num of int
| Id of string
| Add of expr * expr
| Sub of expr * expr
| LetIn of string * expr * expr
| Call of string * expr
type fundef = FunDef of string * string * expr
type prog = Prog of fundef * expr
📁 F1VAE의 Abstract memory(추상 메모리) for functions
📌 Λ는 하나의 추상메모리를 말한다.
F1VAE 언어를 위해서는 함수 정의를 저장할 추상메모리가 필요하고, Fstore라고 정의한다.
📌 Fstore는 함수이름 x를 받아 파라미터와 함수몸체의 쌍 (x, e)를 반환하는 함수 추상메모리의 집합이다.
즉 Λ는 Fstore의 원소가 된다.
함수 추상메모리는 함수이름을 key로, 파라미터와 함수몸체의 쌍을 value로 하는 map과 같다고 볼 수 있다.
함수 추상메모리 사용을 위해 아래 두개의 보조함수 정의가 필요하다.
📌 Λ(x): 함수 추상메모리 Λ에서 함수이름 x의 값을 찾아 반환한다.
📌 Λ [x1 ↦ (x2, e)]: 함수 추상메모리 Λ에 함수이름 x1의 값을 (x2, e)로 업데이트한 새로운 함수 추상메모리를 반환한다.
🔎 Ocaml로 Abstract memory for functions 구현
예를 들면 다음과 같이 추상메모리에 함수가 들어간다.
📁 F1VAE의 Semantic relations
F1VAE의 확장된 syntax 지원을 위해 다음과 같은 semantic relation 추가 및 확장이 필요하다.
📁 F1VAE의 Semantics
x(e)에 대한 Semantics는 접근 방법에 따라 두가지로 나뉠 수 있다.
1. Substitution
함수 호출 시, 함수몸체의 파라미터 변수를 전달된 인자로 치환한 후 계산하는 방법이다.
Expression e에서 x bound occurrence를 모두 n으로 치환하라는 의미로 다음과 같이 표시한다.
다음과 같이 계산될 수 있다.
substitution 접근법을 사용하면 다음과 같이 코드가 진행된다.
def f x = x + 1 endef (* Λ = [f ↦ (x, x+1)] *)
let y = 3 in (* 𝜎 = [y ↦ 3] *)
let z = 4 in (* 𝜎 = [y ↦ 3, z ↦ 4]*)
f(z - y) (* (x + 1)[1/x] ⇒ 1 +Z 1 ⇒ 2 *)
위 방법으로 정의되는 x(e)의 Semantics는 다음과 같다.
2. Using Store
함수 호출 시, 추상메모리에 파라미터 변수와 인자의 매핑을 추가한 후 함수 몸체를 계산하는 방법이다.
using store 접근법을 사용하면 다음과 같이 코드가 진행된다.
def f x = x + 1 endef (* Λ = [f ↦ (x, x+1)] *)
let y = 3 in (* 𝜎 = [y ↦ 3] *)
let z = 4 in (* 𝜎 = [y ↦ 3, z ↦ 4]*)
f(z - y) (* Λ, [x ↦ 1] ⊢ x + 1 ⇓E 1 +Z 1 ⇒ 2 *)
위 방법으로 정의되는 x(e)의 Semantics는 다음과 같다.
📁 F1VAE의 Formal Semantics
substitution 접근법을 이용한 x(e)의 formal semantics이다.
using store 접근법을 이용한 x(e)의 formal semantics이다.
📁 Lexical Scope vs. Dynamic Scope
identifier와 관련하여 두 가지 형태의 scope 정책이 있다.
Lexical Scope(Static Scope)
identifier의 scope가 컴파일시점에 정의된다.
identifier들의 binding-bound 관계가 프로그램의 구조에 따라 결정되기 때문에 프로그램 개발 시 identifier의 binding-bound 관계 계산이 용이하며, early-binding이라고도 부른다.
대부분의 프로그래밍 언어가 Lexical scope 정책을 사용한다.
예시는 다음과 같다.
substitution을 사용하면 다음과 같이 formal semantics가 표현된다.
store를 사용하면 다음과 같이 formal semantics가 표현된다.
Dynamic Scope
identifier scope가 실행시점에 정의된다.
identifier들의 binding-bound 관계가 실행시점의 메모리에 따라 결정되며, late-binding이라고도 부른다.
dynamic scope 정책을 사용하여 프로그래밍을 하면 프로그램의 자유도가 높아진다.
예시는 다음과 같다.
substitution을 사용하면 다음과 같이 formal semantics가 표현된다.
store를 사용하면 다음과 같이 formal semantics가 표현된다.
📁 Extension of F1VAE : Multiple functions support
Concrete Syntax
Abstract Syntax
Overline은 "0 이상"을 의미
Semantics
