[UPL] 고차원 함수와 일차원 함수

 

 

 

이전에 정의한 언어인 VAE에 함수를 추가해 F1VAE를 정의해보자 (First Order Function and VAE)

 

여기서 함수는 수학에서 가져온 용어지만, 수학과는 다르게 같은 값에 대해 다른 출력이 있을 수 있다. (Side Effect)

Pure Functional Language는 함수에서도 Side Effect가 없지만.. 우선 일반적인 프로그래밍 언어에서는 함수 호출에 대한 Side Effect가 발생할 수 있다. 

 

Higher Order Function - 고차원함수로 함수를 인자로 받거나 반환할 수 있다. (1등 시민)

First Order Function - 일차원함수로 함수를 인자로 받을 수 없고, 반환값으로 사용할 수도 없다. (2등 시민)

 

지금 정의하는 F1VAE는 First Order Function을 지원하고, 함수를 변수와 다르게 특별 취급해 함수의 이름과 변수의 이름을 명확하게 구분한다. (변수를 저장하는 공간과 함수를 저장하는 공간을 나눠서 메모리를 따로 사용)

 

대부분의 Imperative Language는 First Order Function을 지원하고, Functional Language는 Higher Order Function을 지원한다.

 

 

개발자가 사용하는 Concrete Syntaxs는 위와 같이 정의하자. 

decl과 prog 부분을 보면 알 수 있듯, 꼭 하나의 함수를 정의해야 하고 함수의 파라미터는 하나만 가질 수 있다. 

 

 

 

 

당연히.. 구문을 저렇게 작성하더라도 내부적으로는 AST 형태로 표현된다.

 

새로 정의하는 언어에서는 함수를 1급 시민으로 취급하지 않으니 함수를 저장하는 저장소가 변수 저장소와 독립적으로 있어야 한다. 

변수 저장소 Fstore는 함수명을 받아서 파라미터와 인자로 구성된 쌍을 반환한다.

 

 

 

Fstore에서 함수명 x의 값을 찾아서 반환하거나, Fstore의 함수명 x1으로 저장된 값을 (x2, e)로 업데이트한 새로운 Fstore를 반환한다.

 

Concrete Syntax를 새로 정의했으니 Semantics Relation을 확장해보자. 

 

 

 

 

 

1. 프로그램 P는 결과적으로 어떤 정수 N으로 평가됨을 의미하는 관계

2. 특정 정의 d는 함수 스토어 람다로 평가됨을 의미하는 관계 

3. 함수 저장소, 변수 저장소, 표현식은 어떤 정수 N으로 평가됨을 의미하는 관계

 

 

 

 

Semantics의 정의로부터 Inference Rule을 만들어보자.

여기서 함수 호출을 수행할 때는 메모리를 사용하는 방법과 치환을 사용하는 방법 두 가지를 사용할 수 있다. 

 

함수의 몸체를 저장할 때, 함수 저장소는 그대로 사용하지만 변수 저장소는 빈 저장소를 사용함에 주의하자!!!!!

치환하거나 메모리를 사용하거나 인자를 계산할 때는 빈 메모리 상태에서 계산해야 하는데, 이 부분은 Lexical Scope를 유지하기 위해서이다.

 

Lexical Scope

Identifier의 Scope가 컴파일 시점에 정의돼 bind-bound relation이 프로그램의 구조에 따라 결정된다. 

대부분의 프로그래밍 언어가 Lexical Scope를 사용한다.

 

Dynamic Scope 

런타임 시점에 Scope가 정해져 bind-bound relation이 실행시점의 메모리에 따라 결정된다.

pure Lisp, SmallTalk 같은 언어가 해당 Scope를 사용하지만.. 자주 사용되지는 않는다. 

 

프로그래밍 언어는 둘 중 하나의 Scope를 정해서 사용한다. 

함수 몸체를 계산할 때 비어 있는 변수 저장소를 사용할지, 기존에 사용하던 변수 저장소를 사용할지에 따라 Lexical Scope와 Dynamic Scope가 결정된다. 

 

Lexical Scope에서는 Free Identifier인 변수가 Dynamic Scope에서는 제대로 실행될 수 있다. 

 

 

 

 

Concrete Syntax에서 decl_list와 var_list를 도입해서.. 

F1VAE 언어를 여러 함수를 정의할 수 있고, 함수의 파라미터도 여러개 받을 수 있도록 확장해보자. 

 

 

 

Inference Rule은 이렇게 나오는데...

일단 이 규칙으로는 인자와 파라미터의 개수가 정확히 일치하는 경우만 함수를 호출할 수 있다. 

파이썬, 자바스크립트에서는 인자와 파라미터의 개수가 일치하지 않아도 함수를 호출할 수 있고, 부족한 인자는 기본값으로 사용하도록 설정할 수 있는데.. 이런 부분도 모두 인터프리터 수준에서 직접 구현된다. 

 

 

 

---

 

 

 

First Class Function을 지원하는 언어에서는 함수명과 변수명이 구별되지 않고, 앞서 언급한 것 처럼 함수가 값으로 활용돼 변수에 저장하거나, 함수의 인자로 전달하거나, 반환값으로 활용될 수 있다. 

 

이번에는 VAE 언어를 확장해 1급 시민 함수를 지원하는 FVAE 언어를 정의해보자. 

 

 

 

 

표현식에서 함수가 추가됐다. 파라미터를 인자로 받아 몸체와 리턴값으로 구성된 표현식을 반환한다. (이름이 없는 함수임에 주의 lambda)

 

 

 

 

 

lambda abstraction에서 x는 파라미터, e는 함수 몸체를 의미한다. (x는 binding occurrence, x는 e에서만 사용된다)

이제는 함수도 값으로 처리되기에.. Value 도메인도 정수와 Closure를 포함할 수 있도록 확장해야 한다. 

 

 

type value = 
	| NumV of int
	| ClosureV of string * Ast.expr * t
and t = (string * value) list

 

 

value 타입을 정의하려면 t타입이 있어야 하고, t타입을 정의하려면 value 타입이 있어야 하는데.. 이러면 순환 참조 오류가 발생한다.

OCaml에서는 and 키워드를 사용해 순환 참조 문제를 우회한다. 

 

모듈을 제공하는 언어에서는 서로 다른 모듈 간 상호참조가 불가능하다.

모듈별로 컴파일해서 수정한 부분만 다시 컴파일 할 수 있다는 장점이 있지만.. 컴파일의 순서가 정해진다. 

 

B가 A를 참조한다면 A를 먼저 컴파일하고 B를 나중에 컴파일 해야 한다. 

 

 

 

Semantics를 바탕으로.. Inference Rule을 정의하면 위와 같이 도출된다. 

 

함수형 언어는 lambda abstraction과 function application으로 대부분의 문법을 표현할 수 있다.

사용성을 위해 여러 Syntatic Sugar를 지원하고, 덕분에 Semantics와 Interpreter를 간결하게 표현할 수 있다. 

 

Concrete Syntax와 Parser를 수정해야 하지만.. Abstract Syntax / Semantics는 수정하지 않아도 된다.

Syntatic Sugar로 이름 있는 함수를 정의하거나, 여러 파라미터를 받는 함수를 정의할 수 있다. (Curried function)

 

자바에서도 함수형 언어 패러다임을 일부 지원하는데.. 

정말 함수를 1급 시민 객체로 취급하는건 아니고, 함수를 객체로 다룬다.

즉, 약속을 해 둔 것.. 객체를 넘기면 특정 함수를 호출해준다고.. (C++ Functor)

 

() -> 화살표 함수로 람다식을 작성하는데, 이 부분은 Syntatic Sugar로 실제로 ByteCode 수준에서는 lambda가 존재하지 않는다.

화살표 함수를 사용하면 내부적으로 Functional Interface의 구현체로 변환된다.

 

 

 

 

그냥 요점만 기억하자.. 

<λx.e σ> 는 클로저의 원소로 익명 함수를 의미하고.. Inference Rule에서 가져다가 사용한다.

Syntatic Sugar로 파라미터 여러 개를 받는 함수를 정의할 수 있고

fun x y -> x + y | let f = fun x -> (fun y -> x + y) | λx. (λy. x + y) 로 해석된다.