[PL] Identifier, Memory Address

1. Identifier이란

Identifier이란, 프로그램의 요소를 나타내는 '이름'이다.

Function name, variable name, parameter name, field name, class name 등 ..

Letter, underscore, digit으로 구성된다.
각 언어마다 naming rule이 다르며, c언어의 경우 digit으로 시작할 수 없다.

🔔 Example

let _ = f 0
let f x = 
  let y = 1 in
  x + y
let _ = f 1
let _ = x - z

위 예시에는 f, x, y, z이 identifiers이다.

f는 함수 identifier
y는 변수 identifier
x는 파라미터 identifier
z는 free identifier

2. Identifier 정의 및 접근

identifier는 프로그램에서 여러 번 나타날 수 있다.
identifier을 정의할 때 = 'biding occurence'
identifier에 접근(사용)할 때 = 'bound occurence'
위 경우 모두 아닌 경우 = 'free identifier'

3. 범위 (Scope)

🌱 Identifier는 scope을 가지고 있다.

즉 Identifier는 scope에 대해서 binding-bound relationship을 가진다.

🌱 scope = binding occurence identifier가 bound되는 영역

-> Identifier의 생애주기
-> Identifier에 대한 접근가능성을 결정한다.

🌱 Out of Scope = Free Identifier이다.

Identifier를 out of scope에서 접근하면, 그것은 Free Identifier이다.

위 예시에서,
f의 scope = 5 ~ 6 (다른 scope에서 사용 불가. 함수 바디 내부에서는 f 사용 불가이므로 3, 4는 아니다)
x의 scope = 3 ~ 4 (함수 body 내에서만 사용 가능)
y의 scope = 4 (let - in expression이므로)

line 6에서의 x는 앞서 정의된 x의 scope이 아니기 때문에 free identifier이다.

🌱 재귀함수의 경우 scope가 바뀐다.

f 함수가 재귀함수라면 함수 바디 내에서도 사용 가능하므로 3, 4, 5, 6 라인에서 모두 접근할 수 있게 된다 ❗❗

4. Shadowing

🌱 같은 identifier는 범위 내에서 binding occurence로 다시 나타날 수 있다.

즉, 같은 이름의 identifier을 같은 scope 내에서 정의할 수 있다.

🌱 가장 내부에 있는 binding occrurence identifier는 bound occrurence identifier에 참조된다.

즉 innermost binding occurence identifier는 outer binding occurence를 숨긴다.

이를 'shadowing', 'variable shadowing'이라고 한다.

🔔 Example

라인 4의 x는 라인 1의 x를 'shadow'한다. 라인 1의 scope 내에서 라인 4의 x가 같은 identifier로 정의되었기 때문이다.
따라서 innermost x인 라인 4의 x가 1의 x를 숨기게 된다.

라인 7의 x는 라인 4의 x가 아니라 1의 x이다. 왜냐하면 라인 4의 x의 scope이 아니기 때문!

5. Memory Address

🌱 variable 값을 저장하기 위한 abstract memory를 정의한다.

기존처럼 그저 1+3, 4-2 등의 expression이 아니라 '변수'를 정의한 것이기 때문에, 변수를 추후 다시 사용하기 위해서는 그 값을 저장해야 한다. 이를 위해 store이 필요하다.

🌱 Store이란, 변수 x를 받아서 정수 n을 리턴하는 함수들의 집합이다.

Abstract Memory인 store는 함수로서, 변수를 입력하면 해당 값을 리턴한다.

Store : var -> z

σ는 Store의 한 요소이다.
σ ∈ Store

🌱 Abstract Memory를 이용하기 위해 두개의 helper 함수를 정의하자.

1) σ(x) : abstract memory σ로부터, 변수 x를 찾고 그 값을 리턴한다. (getter 함수)
2) σ[x↦n] : abstract memory σ로부터, 변수 x의 값을 n으로 업데이트하고, 새로운 abstract memory를 리턴한다. (setter 함수)

ocaml에서는 어떻게 abstract memory를 만들 수 있을까?

store = 변수 이름, 변수 값 리스트
위와 같이 [("x", 3)]으로 udpate할 수 있다.