[UPL] MiniC 구현

 

 

 

Imperative Language는 명령어를 수행할 때 프로그램의 메모리 상태를 변경하는 언어로, Statement를 통해 메모리를 변경한다.

C C++ Java Python 모두 Statement를 사용하는 Imperative Language이다.

 

Functional Language는 함수를 값으로 다루는 언어지만 Statement를 가질 수 있다.

OCaml은 Statement가 없고 Declaration과 Expression만 가진다.

 

Functional Language와 Imperative Language는 서로 대비되는 개념이 아니고, 공존할 수 있다 (JavaScript)

 

Statement안에 Statement가 위치할 수 있다. 

Java C 같은 언어에서는 if 구문이 값을 반환하지 않으니 Statement이고, OCaml에서는 if 구문이 값을 반환하니 Expression이다.

 

간단한 기능을 수행하는 MiniC를 인터프리터 언어로 구현해보자.

 

 

 

 

 

Concrete Syntax / Abstract Syntax에서는 크게 다른 부분이 없다.

변수에 값을 할당하는 assignment, true 브랜치와 false 브랜치를 작성하고.. Value 도메인에 Bool 추가, Bool 도메인에 true, false를 추가하자.

 

p는 program으로 빈 메모리에서 실행하고 변화된 메모리를 반환한다.

s는 statement로 현재 메모리에서 실행하고 변화된 메모리를 반환한다.

e는 expression으로 현재 메모리에서 실행해 계산된 값을 반환한다. 

 

Semantics도 그냥 그대로 작성해 주면 되니까.. 어려울게 없다. 

 

 

 

Statement List를 계산하는 보조 Semantic Relation고 Formal Semantics만 자세하게 살펴보자.

S에 모자가 붙어있으면 Statement List를 의미하고, Statement를 순차적으로 하나씩 계산해서 저장소를 업데이트한다. 

 

&& || 논리 연산 시 대부분의 언어는 Short Circuit Evaluation을 사용해 결과가 정해진 경우 남은 Expression 계산을 건너뛰는데, 이 때Side Effect를 고려해야 한다.

e1 || e2 에서 e2를 계산할 때 메모리를 바꾸게 되면 결과가 아예 달라질 수 있다.

 

// 원본
if (e1 || e2) {
  doSomething();
}

// desugaring
if (e1) {
  doSomething();
} else if (e2) {
  doSomething();
}

 

 

Short Circuit Evaluation을 사용할 때 논리 연산을 if 문을 중첩해서 Desugaring 할 수 있다.  

 

 

 

 

반복문은 while 구문 하나만 사용하고, 다른 구문은 Syntatic Sugar로 처리한다.

expression이 false인 경우 메모리를 그대로 반환하고, true인 경우 statement를 순차적으로 실행한다.

 

while의 Semantics를 정의할 때 while을 사용했지만.. Operational Semantics는 수학처럼 생겼을 뿐이지 수학이 아니다.

기계의 동작을 나타낼 뿐, Compositional 하지 않기에 그대로 사용해도 괜찮다. 

 

 

 

 

---

 

 

 

 

C에서 수행할 수 있는 연산인 포인터 연산을 구현해보자. - Reference, Dereference

&x 연산으로는 변수 x의 메모리 주소를 가져오고, *e 연산으로는 e가 메모리 주소를 의미할 때 해당 주소에 저장된 값을 가져온다.

 

 

 

var = expr 문법은 syntatic sugar로 처리할 수 있다. (*&x = 3 으로 처리할 수 있다)

 

dex x = e : 변수 선언과 초기화를 함께 수행한다.

x = *e : Load Statement

*e1 = e2 : Store Statement

 

변수 - 주소 - 값 이 세 요소의 관계를 잘 설정해보자.

 

컴파일 언어에서는 각 변수가 서로 다른 메모리공간을 사용한다고 가정하면 프로그램을 읽은 후 변수를 주소로 변경한다.

즉, 컴파일 결과인 바이너리에는 변수 관련 정보가 모두 제거되고 주소와 값의 관계만 남게 된다. 

 

 

 

인터프리터 언어에서는 메모리를 2개로 쪼갠다. (추상메모리를 2개 사용)

 

추상메모리1은 변수와 주소 사이의 관계를 정의하고,

 

추상메모리2는 주소와 값 사이의 관계를 정의한다.

 

주소 도메인을 따로 정의했으니 주소 사이의 사칙연산 및 대소비교는 런타임 에러를 뱉는다.

 

 

 

 

 

애초에 주소가 정수로 다뤄진다고 하더라도 주소값끼리의 비교는 유의미한 결과를 도출하지 않아 주소값 사이의 대소비교는 Undefined Behavior로 정의된다.

 

C언어 스펙에서도 주소끼리의 대소비교는 불가능하다고 정의되어 있다. (덧셈, 뺄셈은 가능)

다른 언어에서도 언어의 Spec을 살펴보면 어떤 연산이 Undefined Behavior인지 알 수 있다.

 

어차피 공간을 할당하는건 시스템이고, 시스템이 할당하는 공간은 개발자가 절대 알 수 없으니 Undefined Behavior이다.

 

 

이제 관리해야 하는 메모리가 두 개로 늘었으니 이전에 수행하던 모든 연산은 메모리 하나를 받는 형태에서 메모리 두 개를 받는 형태로 변한다.

 

 

 

 

함수 정의와 호출은 지난번에 구현했던 F1VAE와 유사하다. 

함수를 저장하기 위한 Fstore를 따로 정의하고, 함수 호출은 임시로 사용할 메모리를 만들어 파라미터를 바인딩 해 주면 된다. 

 

함수의 반환 값을 다뤄야 하는데.. 호출된 함수는 반환 값을 특정 메모리 주소에 저장하고, 호출한 함수는 그 특정 메모리 주소에서 값을 가져오는 방식으로 동작한다. (a@ret)

 

지금 이렇게 구현하면 프로그램이 return을 만나더라도 그냥 해당 부분에 값만 세팅해줄 뿐, 다음 라인을 이어서 읽는다.

 

함수 호출 시 지역 변수의 Scope를 고려하자. 반환하는 시그마는 함수 호출 시점의 시그마를 반환해야 한다. 

변수에 선언이 없다면 Scope도 없고, 어디서든 꺼내 쓸 수 있지만, 선언이 생기면 Scope가 생긴다.

 

while 루프를 돌 때도, 몸체를 한 번 돌면 그 안의 변수의 Scope는 사용되지 않는다.

 

변수의 Lifetime이 끝나더라도 만약 그 변수가 가지고 있던 주소를 통해 값으로 접근하는건 가능한데, C에서는 값을 재할당 할 때 값을 overwrite하는 방식으로 값 공간을 활용한다. (!= GC)