Box 데이터 구조

1. Box 데이터 구조란?

Box는 하나의 값을 저장할 수 있는 뮤터블 데이터 구조로, 저장된 값을 수정할 수 있어 함수형 언어에서 상태 변화를 관리할 수 있는 기초 구조가 된다. Box는 특정 값을 초기화한 후 필요할 때 값을 수정할 수 있으며, 이를 통해 뮤터블 데이터 구조의 역할을 할 수 있다.

2. BFAE 문법: Box 기능 추가

Box 기능을 기존 FAE(Functional Arithmetic Expressions) 언어에 추가한 BFAE(Basic FAE + Box) 문법은 다음과 같다:

• {newbox <Expr>}: 새 Box를 생성하고 초기화할 수 있다.
• {setbox <Expr> <Expr>}: Box에 저장된 값을 변경할 수 있다.
• {openbox <Expr>}: Box에 저장된 값을 추출하여 반환할 수 있다.
• {seqn <Expr> <Expr>}: 두 표현식을 순차적으로 실행하여 첫 번째 표현식의 상태 변화가 두 번째 표현식에 반영되게 할 수 있다.

BFAE 문법에서 Box는 단일 값 컨테이너로, Scala에서는 BoxV(var container: ExprValue) 형태로 표현할 수 있으며, Box의 값은 Newbox, Setbox, Openbox 등의 연산을 통해 관리된다.

3. Box 연산자 구현

Box의 각 연산자는 Box 상태를 관리하며, 해석기에서 상태 변화를 반영하도록 구현할 수 있다.

• newbox 연산자: newbox는 새로운 Box를 생성하고 초기값을 설정할 수 있다. 이 연산자는 malloc을 통해 할당된 메모리 주소에 초기값을 저장하며, 이후 Store에 이 상태가 반영되게 한다. 예를 들어 {newbox 5}는 5라는 값을 저장한 Box를 생성할 수 있다.
• openbox 연산자: openbox는 특정 Box에 저장된 값을 반환할 수 있다. 해석기에서는 storeLookup 함수를 통해 openbox가 참조하는 메모리 주소의 값을 가져와 Box의 현재 상태를 확인할 수 있다.
• setbox 연산자: setbox는 특정 Box의 값을 변경할 수 있다. malloc을 통해 메모리 주소에 새로운 값을 저장하고 Store를 업데이트하여 변경된 상태를 반영할 수 있다.
• seqn 연산자: seqn 연산자는 두 개의 표현식을 순차적으로 실행하여 첫 번째 표현식의 상태 변화가 두 번째 표현식에 영향을 주도록 할 수 있다. 해석기에서 interpTwo 함수를 사용하여 첫 번째 표현식의 결과와 상태를 두 번째 표현식에 전달함으로써 상태 변경을 반영할 수 있다.

4. BFAE 확장 구문

기존 Num, Add, Sub, Id, Fun, App 등의 구문에 Newbox, Setbox, Openbox, Seqn을 추가하여 BFAE에서 뮤터블 상태를 관리할 수 있도록 할 수 있다. 이를 통해 Box의 생성과 상태 변경이 프로그램 실행 중 정확히 반영될 수 있다.

5. Box 상태 관리: DefrdSub와 Store

Box의 상태를 효과적으로 추적하기 위해 DefrdSub와 Store라는 두 개의 캐시를 사용할 수 있다:

• DefrdSub: 변수 이름을 메모리 주소와 연결하여 Box의 위치를 추적하는 캐시 역할을 한다.
• Store: 메모리 주소와 값을 연결하는 캐시로서, Box의 상태 변화를 저장하고 관리할 수 있다.

Store는 두 가지 형태로 구현할 수 있다:

• MtSto: 비어 있는 Store를 나타낸다.
• ASto(address, value, rest): 메모리 주소와 값, 그리고 다음 상태를 포함하는 Store 형태이다.

예를 들어, ASto(1, NumV(10), MtSto)는 주소 1에 값 10을 저장하고, 이후 상태는 MtSto로 나타내어 Box가 메모리에 저장된 상태를 보여줄 수 있다. 이처럼 Box의 상태는 메모리 주소를 통해 관리되며, malloc 함수를 사용해 Store 내 고유 주소를 할당한다.

6. Box 상태 관리 예제

• Box 생성 및 값 변경: {with {b {newbox 7}} {seqn {setbox b 10} {openbox b}}} 예제에서는 Box를 생성하여 7로 초기화한 뒤, setbox로 값을 10으로 변경하고 openbox로 이 값을 확인할 수 있다. 이 과정에서 Box의 상태가 변경된 것을 확인할 수 있다.
• 연산 중 상태 변경: {with {b {newbox 0}} {seqn {setbox b {+ 1 {openbox b}}} {openbox b}}}는 setbox로 값을 변경하고, 이후 openbox를 통해 변경된 값을 반환한다.

7. Box와 함수 호출에서의 상태 관리

Box는 함수 호출 간에도 상태가 유지될 수 있도록 설계되었다.

• 예를 들어, {with {a {newbox 1}} {with {f {fun {x} {+ x {openbox a}}}} {seqn {setbox a 2} {f 5}}}} 예제에서는 newbox로 1을 초기화하고, setbox로 값을 2로 변경한 후 함수 f에서 openbox를 통해 변경된 값을 참조하여 최종 결과에 반영할 수 있다.
• App 연산자를 사용한 함수 호출에서 Box의 메모리 주소가 전달되며, ClosureV 타입을 통해 파라미터가 Box의 주소를 참조하도록 설정하여 함수 내에서도 Box 상태가 유지되게 할 수 있다.

8. Box 상태 관리를 위한 비상태적 접근

Box는 상태를 직접 가지지 않고, 메모리 주소와 Store를 통해 상태를 간접적으로 관리할 수 있다. 이를 통해 Box는 함수형 프로그래밍의 비상태적 특성을 유지하면서도 상태 변화를 효과적으로 추적할 수 있다.

 

DefrdSub와 Store를 쉽게 이해하기 위해 각각을 일상적인 비유로 설명해보겠다.

1. DefrdSub: 주소록

DefrdSub는 변수가 실제 데이터가 저장된 메모리 주소를 가리키는 역할을 한다. 이를 주소록에 비유할 수 있다.

• 비유: DefrdSub를 우리가 흔히 쓰는 주소록이라고 생각해자. 주소록에는 사람 이름과 그 사람이 사는 집 주소가 저장되어 있다. 그런데 주소록에는 사람의 주소(집 위치)만 있을 뿐, 실제 사람이 거주하는 집의 내부 모습이나 상태(예: 방 안에 있는 가구나 물건)는 직접 알 수 없다.
• DefrdSub의 역할: 마찬가지로, DefrdSub는 변수 이름을 메모리 주소와 연결해 주는 “주소록” 역할을 한다. 예를 들어, 변수를 a라고 하면, DefrdSub는 이 a라는 변수가 실제로 어느 메모리 위치(주소)에 데이터를 저장하고 있는지 알려준다.

2. Store: 창고

Store는 메모리 주소와 그 주소에 저장된 실제 값을 연결한다. 이를 창고에 비유할 수 있다.

• 비유: Store를 창고라고 생각해보자. 창고 안에는 많은 물건이 칸마다 저장되어 있는데, 각 칸마다 고유한 번호가 있다. 창고에서 물건을 찾을 때는 물건 이름이 아니라 번호를 통해 찾아간다. 창고 관리자는 이 번호를 바탕으로 창고의 특정 위치에서 물건을 꺼내거나 교체할 수 있다.
• Store의 역할: Store는 메모리 주소(창고의 각 칸 번호)와 그에 해당하는 값을 연결해 주는 “창고” 역할을 한다. 즉, DefrdSub가 알려준 주소를 바탕으로 Store에 가면 그 주소에 저장된 실제 값(데이터)을 확인하거나 변경할 수 있다.

이렇게 DefrdSub와 Store는 서로 협력하여 프로그램이 실행되는 동안 변수 이름을 통해 데이터에 접근하고, 데이터를 업데이트할 수 있도록 도와준다.