7. 명시적 참조 & 암시적 참조

Syntax & Semantics

Syntax : 메모리 위치 생성 및 사용 (변수 선언, 할당 참조 등)

신텍스는 프로그래밍 언어에서 메모리 위치 생성 및 사용하는 방법을 정의한다. 이를 통해 변수나 데이터 구조를 저장하고 조작할 수 있다.

 

Semantics: 메모리 상태 조작 (특정 변수에 값 할당 시, 메모리 위치에 새로운 값 저장)

시맨틱스는 프로그램이 실행될 때 메모리의 상태가 어떻게 변하는지를 정의한다. 변수에 값을 할당하거나 변수 값을 변경하는 작업을 포함한다.

 

언어의 상태를 추가함으로써 메모리의 상태를 동적으로 변화시킬 수 있고, 단순한 값 계산 외로도 다양한 부수 효과를 처리할 수 있다.

 

let counter = 0
in let f = proc (x) (let counter = counter + 1
                     in x)
   in let a = (f (f 1))
in counter

 

f 함수의 호출 횟수를 세기 위해 위와 같은 프로그램을 작성할 수 있다.

그러나 여기서 counter의 바인딩은 local로 되어 있다. 즉, 각 함수 호출마다 새로운 counter가 생성되고 함수 호출이 끝나면 사라지기에 실제로 counter 값을 증가시키진 못한다. 따라서 f 함수 내부에서 바인딩된 counter가 아닌 외부 변수 counter를 함수 내에서 변경시켜야 한다.

 

프로그래밍 언어는 참조(references)를 명시적(explicitly) 또는 암시적(implicitly)으로 지원한다.

 

명시적 참조(Explicit References)

명시적 참조를 지원하는 언어는 메모리 할당, 참조 해제, 메모리 셀 변경을 명확하게 처리한다. OCaml, F#과 같은 언어에서 그렇다. 사용자는 메모리 관리에 대한 제어권을 가진다.

 

암시적 참조(Implicit References)

암시적 참조를 지원하는 언어는 참조를 내장된 형태로 처리하며 사용자는 참조를 명시적으로 다루지 않는다.  C와 java와 같은 언어에서 그렇다. 참조와 관련된 작업은 언어 자체가 관리한다.

 

 

Explicit References

Syntax

P → E

E → ...

    | ref E  # 새로운 메모리 위치 할당, E의 값을 그 위치에 저장한 후 그 위치를 반환

    | ! E  # E가 참조하는 위치의 내용 반환

    | E1 := E2  # E1이 참조하는 위치의 내용을 E2의 값으로 변경

    | E1; E2  # E1을 실행한 후 E2를 실행하여 그 효과를 누적

Example

let counter = ref 0
in let f = proc (x) (counter := !counter + 1; !counter)
   in let a = (f 0)
      in let b = (f 0)
in (a - b)

→ counter는 0을 저장하는 새로운 메모리 위치 생성 및 참조

→ f는 입력 x를 받아 counter 값을 증가시키고 그 값을 반환
→ a는 1이 되고 b는 2가 되며 최종적으로 -1이 된다.

 

let f = proc (x) (let counter = ref 0
                  in (counter := !counter + 1; !counter))
   in let a = (f 0)
      in let b = (f 0)
in (a - b)

→ 위 예제와 달리 f 함수 내에서 counter를 0으로 바인딩한다.

→ 따라서 f 0은 항상 1이 되어 최종적으로 0이 된다.

 

let x = ref (ref 0)
in (!x := 11; !(!x))

→ x에는 ref 0을 참조하는 새로운 참조가 담긴다. 이는 let y = ref 0; let x = ref y와 같다.

→ !x는 x가 참조하는 위치의 값을 11로 변경한다.

→ 최종적으로 !(!x)는 11이 된다.

 

Semantics

Val = Z + Bool + Procedure + Loc

Procedure = Var × E × Env

p ∈ Env = Var → Val

σ ∈ Mem = Loc → Val

 

p, σ ⊢ E ⇒ v, σ'

환경 p, 초기 메모리 상태 σ에서 표현식 E를 적용하면,

표현식의 결과 값 v와 표현식 평가 후의 메모리 상태 σ'가 된다.

 

기존 Semantics는 이에 맞춰서 변화한다.

 

예를 들어 p, σ ⊢ n ⇒ n, σ의 경우 환경 p와 메모리 상태 σ에서 표현식 n은, 결과 값 n과 기존 메모리 상태 σ가 된다.

또 p, σ ⊢ x ⇒ p(x), σ 는 결과 값 p(x)와 기존 메모리 상태 σ가 된다.

위 두 경우에서는 단순히 참조를 수행하여 메모리 상태가 변하지 않는다.

 

 

그러나, 위 경우에서는 E1 + E2를 수행하기 위하여 표현식 E1과 E2를 계산한 값을 환경에 저장해두어야 한다.

따라서 σ1 에서 n1을 저장한 메모리가 담기고, σ2에서 n1과 n2가 담긴 메모리가 담기고, 그 위에서 n1 + n2를 연산한다.

 

위는 변화된 전체 Semantics이다. 

 

이번엔 새롭게 추가된 Semantics를 알아보자.

ref E에 대한 Semantics이다. ref E를 수행하기 위해 먼저 표현식 E를 수행한다.

표현식 E의 결과 v, 그를 담고 있는 새로운 메모리 상태 σ1를 구하고,

ref E를 수행한 결과는 E를 저장한 위치인 l, 새로운 메모리 상태는 [l ↦ v]σ1가 된다.

이 때, l은 σ1에 포함되어 있어선 안된다. 현재 사용되지 않는 위치여야 한다.

* l ↦ v는 위치 l이 값 v를 가리킨다는 뜻이다.

 

!E에 대한 Semantics이다. 표현식 E의 결과인 위치 l과 메모리 상태 σ1에 대하여,

σ1(l)이 결과가 되고 메모리 상태는 σ1 된다.

 

E1 := E2에 대한 Semantics이다.

E1의 결과는 바뀔 메모리 위치 l, 이 때의 메모리 상태 σ1이 된다.

E2의 결과는 변경할 값 v, 이 때의 메모리 상태 σ2가 된다.

E1 := E2의 결과는 변경된 값 v, 그리고 메모리 상태는 E1의 주소 l이 가리키는 값이 E2의 결과 v가 되도록 한다.

 

E1; E2에 대한 Semantics이다.

E1은 기존 상태인 p, σ0에서 실행되어 v1, σ1이 된다.

E2는 E1의 실행된 이후 상태인 p, σ1에서 실행되어 v2, σ2가 된다. 이 값이 E1; E2의 결과이다.

 

 

Exercise

letrec f(x) = E in E 라는 새로운 재귀 Syntax를 추가해보자.

 

p, σ0 ⊢ letrec f(x) = E1 in E2 ⇒ v, σ1에서,

E1은 프로시저 본문이고 E2는 본문을 사용하는 표현식이다.

 

재귀 환경을 설정하여 f를 재귀적으로 참조할 수 있게 하고 E2를 평가해야 한다.

p[f ↦ (x, E1, p)] 은 환경 p에 f를 추가하고, f는 (x, E1, p)를 가리킨다.

 

따라서, Semantics rules는 아래와 같다.

 

[f ↦ (x, E1, p)]p, σ0 ⊢ E2 ⇒ v, σ1

---------------------------------------

p, σ0 ⊢ letrec f(x) = E1 in E2 ⇒ v, σ1

 

 

Implicit Refrences

Syntax

P → E

E → ...

    | x := E  # x의 값을 E의 값으로 변경

    | E1; E2  # E1을 실행한 후 E2를 실행하여 그 효과를 누적

 

Semantics

Val = Z + Bool + Procedure + Loc

Procedure = Var × E × Env

p ∈ Env = Var → Loc

σ ∈ Mem = Loc → Val

기존 환경은 변수(Var)가 값(Val)을 가지고 있었다. 여기서는 변수가 주소(Loc)를 가진다.

따라서 변수의 값을 구하기 위해선 σ(p(x))를 수행해야 한다.

 

 

Explicit References와의 차이가 있는 시맨틱스만 알아보자.

 

p, σ ⊢ x ⇒ σ(p(x)), σ 

위에서 이야기했듯, p에서 x는 주소를 가지기에 메모리에서 값을 꺼내온다.

 

Explicit References이기 때문에 let x에서 메모리를 할당한다.

E1의 결과 v1, σ1에 대하여 환경에는 [x ↦ l]을 추가, σ1에는 [l ↦ v1]을 추가한다.

이 때, l은 σ1의 도메인에 포함되지 않은 새로운 값이여야 한다.

 

x의 값을 변경할 때는 p(x)로 주소를 구하여 값을 지정한다.

 

함수를 호출할 때는

p, σ0 ⊢ E1 ⇒ (x, E, p'), σ1,

p, σ0 ⊢ E2 ⇒ v, σ2 에 대하여,

[x ↦ l]p', [l ↦ v]σ2⊢v', σ3 이 되고, 이게 결과가 된다.

 

Call-By-Reference

지금까지는 Call-by-Value를 사용해왔다. 즉 형식 매개변수는 실제 매개변수의 값을 포함하는 새로운 위치를 참조한다.

Call-By-Reference를 위해서는 새로운 syntax와 semantics를 추가해야한다.

E → ...

    | E <y>

함수를 호출할 때 x에 새로운 주소를 부여하는 것이 아닌, 매개변수 y의 주소를 부여한다.

 

이 때, 변수 별칭(Variable Aliasing)으로 인해 동일한 메모리 위치를 참조하는 여러 변수가 있는 상황이 있을 수 있다. 예를 들어, f(x)가 함수 f(y)를 반환할 때, (f <y>) <y> 를 호출할 때 이와 같은 상황이 생긴다. 이는 프로그램의 동작을 예측하기 어렵게 만든다.

 

 

Lazy Evaluation

지연 평가는 매개변수의 평가를 실제로 필요할 때까지 지연시키는 기법이다. (즉시 평가- Eager Evaluation은 프로시저가 호출되기 전에 매개변수를 완전히 평가한다)

let p = proc (x) (1)
  in (p (2 * 3))

위와 같은 구문이 있을 때, p(2*3) 호출 단계에서 2*3은 아직 평가하지 않는다.

p(x)는 x의 값과 상관없이 1을 반환하므로 2*3은 끝까지 평가되지 않는다.

 

직접 평가와 지연 평가의 특징을 비교해보자.

즉시 평가	지연 평가
공간 효율적	시간 효율적
비종료 회피 불가	비종료 회피 가능
평가 순서를 이해하기 쉬움	평가 순서를 이해하기 어려움
부작용을 예측하기 쉬움	부작용을 예측하기 어려움