6. 간단한 언어 만들어보기 - 2

Procedures를 추가해보자

P → E // 프로그램은 표현식으로 구성된다.

E → n // 표현식은 다음 중 하나일 수 있다.

    | x // 변수 생성 가능

    | E + E // 덧셈 가능

    | E - E // 뺄셈 가능

    | (E) // 괄호 가능

    | iszero E // 간단한 함수 (0인지 확인)

    | if E then E else E // 조건문 가능

    | let x = E in E // 지역 변수에 표현식 할당

    | read // 입력

 

5강에서, 우리는 위 Syntax를 만들었었다.

우리는 이제 여기에 아래 두 개를 추가할 것이다.

 

| proc x E

| E E

 

proc x E는 인자 x를 받아 E를 실행하는 함수를 정의한다.

E E는 함수를 호출하는데 사용될 것이다.

 

 

Free/Bound Variables of Procedures

바인딩된 변수란, 선언된 변수를 뜻한다. 다시 말해 let 표현식 내에서 연결되어 형식 매개변수로 등장한 변수이다.

자유 변수란, 정의 내에서 형식 매개변수로 등장하지 않았고 외부에서 정의되지 않았으며 let 구문으로 바인딩되지 않은 경우이다.

 

예를 몇 가지 들어보자.

proc (y) (x+y) : y는 바인딩된 변수이지만, x는 자유 변수이다.

proc (x) (let y = 1 in x + y + z) : x, y는 바인딩된 변수지만, z는 자유 변수이다.

proc (x) (proc (y) (x+y)) : x, y 모두 바인딩된 변수이다.

 

 

Static vs Dynamic Scoping

정적 스코핑과 다이나믹 스코핑은 함수가 호출되는 시점에 쓰이는 개념이다.

let x = 1
  in let f = proc (y) (x+y)
   in let x = 2
      in let g = proc (y) (x+y)
        in (f 1) + (g 1)

x = 1의 지역에서 f 함수가 정의되었고, f 함수의 지역에서 새롭게 x = 2가 되었다.

이 때, 맨 아랫줄 (f 1)은 2일까 3일까?

 

Static Scoping의 경우 함수가 정의된 시점에서 평가한다. 따라서 x = 1으로 평가하고, (f 1)은 2가 된다.

Dynamic Scoping은 함수를 호출한 시점에서 평가한다. 따라서 x = 2으로 평가하고, (f 1)은 3이 된다.

 

대부분의 현대 언어는 정적 스코핑을 사용한다. 그 이유는 프로그램을 이해하고 추론하는 것이 훨씬 간단하기 때문이다. 정적 스코핑에서는 코드를 보며 변수가 어떻게 해석될지 알 수 있고 바인딩된 변수의 이름을 바꾸더라도 프로그램의 의미가 변경되지 않는다.

 

 

Semantics of Procedures: Static Scoping

먼저 도메인은 다음과 같이 수정한다.

 

Val = Z + Bool + Procedure

Procedure = Var * E * Env

Env = Var → Val

 

프로시저 값은 클로저라 부른다. 프로시저는 생성될 때의 환경을 닫힌 상태로 포함한다. 즉, 프로시저 내부에서 사용되는 자유 변수는 그 프로시저가 생성된 환경의 매핑을 사용해 값이 결정된다.

 

환경 p에서 proc x E는 매개변수 x, 본문 E, 현재 환경 p를 포함하는 클로저로 평가된다.

 

1. 환경 p에서 E1이 (x, E, p')로 평가되고, // E1이 함수야?

2. 환경 p에서 E2가 v로 평가되며, // E2를 v로 평가

3. 환경 [x ↦ v]p' 에서 E가 v'로 평가된다면, // p'에 x = v를 추가하고 E를 실행한 결과 v'

4. 환경 p에서 E1 E2는 v'로 평가된다. // v' 반환

 

 

예시 1

[] ⊢ (proc (x) (x)) 1 ⇒ 1 이 평가되는 과정을 알아보자.

(proc (x) (x)) 1는 E E꼴이므로, p ⊢ E1 E2 로 나타낼 수 있다.

p ⊢ E1 ⇒ (x, x, p')이고, p ⊢ E2 ⇒ 1 이다.

따라서 [x ↦ 1]p' ⊢ x ⇒ 1 로 평가된다.

 

예시 2

먼저 환경에 x ↦ 1이 추가된다.

다음으로, f ↦ (y, (x+y), [x ↦ 1])이 추가된다.

그 다음, 환경에 x ↦ 2가 추가된다. (여기 아래부턴 원래 환경 x ↦ 1보다 우선시 접근됨)

이어서 f 3이 호출된다.

p ⊢ f ⇒ (y, (x+y), [x ↦ 1])로 평가되고, p ⊢ 3 ⇒ 3으로 평가된다.

[x ↦ 1, y ↦ 3] ⊢ (x+y) ⇒ 4로 평가되어서 p ⊢ f 3 ⇒  4로 평가된다.

 

 

Semantics of Procedures: Dynamic Scoping

Dynamic Scoping에서는 Procedure = Var * E이다. 즉 현재 환경을 저장하지 않는다.

함수 호출 시점의 환경을 사용한다는 점 빼고는 크게 다르지 않다.

 

 

예시

먼저 환경에 x ↦ 1이 추가된다.

다음으로, f ↦ (y, (x+y))이 추가된다.

그 다음, 환경에 x ↦ 2가 추가된다. (여기 아래부턴 원래 환경 x ↦ 1보다 우선시 접근됨)

이어서 f 3이 호출된다.

p ⊢ f ⇒ (y, (x+y))로 평가되고, p ⊢ 3 ⇒ 3으로 평가된다.

[y ↦ 3]p ⊢ (x+y) ⇒ 5로 평가되어서 p ⊢ f 3 ⇒  5로 평가된다.

 

 

Multiple Argument Procedures

다중 매개변수를 가진 함수는 단일 매개변수를 받는 함수의 연속으로 변환하여 표현할 수 있다.

let f = proc (x) proc (y) (x+y)는, 이는 x를 인자를 받고 또 다른 함수 proc (y) (x+y)를 반환하는 함수 f를 정의한다. 반환된 이 함수는 y를 인자로 받고 x와 y의 합을 계산한다.

((f 3) 4)는 f에 3을 적용하면 3을 x로 갖는 새로운 함수가 반환되고, 이 함수는 4를 인자로 받아 3+4를 계산해 7을 반환한다.

 

 

Recursive Procedures

현재 우리의 언어는 재귀적인 프로시저를 지원하지 않는데, let f = proc (x) (f x) in (f 1)에서, f의 정의를 찾을 수 없기 때문에 평가가 진행되지 못한다.

 

물론 dynamic scoping에서는 함수를 호출한 시점의 환경을 사용하므로 정상적으로 실행된다.

 

Static scoping에서 재귀적인 프로시저를 사용하기 위해서는 letrec 신텍스를 추가해야한다.

letrec f(x) = E in E

 

letrec은 재귀적인 정의가 가능하도록 f를 정의할 때 그 본문 E 안에서 f가 이미 바인딩된 상태라고 가정한다. 이를 통해 f는 자신의 본문 내에서 자기 자신을 호출할 수 있게 된다.

 

 

따라서 재귀를 위해서는 도메인을 다시 추가해야 한다.

Val = Z + Bool + Procedure + RecProcedure

Procedure = Var * E * Env

RecProcedure = Var * Var * E * Env

Env = Var → Val

 

이는 재귀적인 프로시저 정의를 처리한다.

환경 p에서 f(x) = E1 이라는 재귀적 함수가 정의되고, E2가 실행되는 컨텍스트에 있다.

f는 (f, x, E1, p) 클로저로 평가되는 재귀 함수이다. E2를 이 환경에서 평가하면 값 v를 얻는다.

환경 p에서 표현식 E1은 (f, x, E, p')로 평가되고, E2는 v로 평가되며,

[x ↦ v, f ↦ (f,x,E,p')]p' 에서 표현식 E가 v'로 평가된다면,

환경 p에서 E1 E2 는 v'로 평가된다.

 

예시

[] ⊢ letrec f(x) = f x in f 1 를 평가해보자.

letrec f(x)에서, 환경에는 f ↦ (f, x, (f x), []) 가 저장되며 자기 자신을 참조할 수 있도록 한다.

따라서, [ f ↦ (f, x, (f x), []) ]p ⊢ f ⇒  f ↦ (f, x, (f x), [])

이어서, [f ↦ (f, x, (f x), []] ⊢ f 1 ⇒ [f ↦ (f, x, (f x), [], x ↦ 1] f x ⇒ [f ↦ (f, x, (f x), [], x ↦ 1] f x ...

 

Mutually Recursive Procedures

상호 재귀적 프로시저라는 뜻으로, 서로를 참조할 수 있게 한다.

letrec f(x1) = E1 and g(x2) = E2 in E

신텍스에 위와 같은 구문을 추가해야 한다.

두 함수를 and로 이어줌으로 f와 g가 서로를 참조할 수 있도록 정의한다.