PLT_7

bells!·2024년 11월 7일

PLT

목록 보기
7/7

Mutable Data Structure

  • 해당 개념이 나오게 된 배경
    : 함수형 프로그래밍은 일반적으로 불변 데이터를 선언함(val). 그런데 저런 불변 데이터를 가변 데이터화할 수 있다는 것에서 의의가 있음. 이에 PLT에서 해당 개념을 배우는 것임.

Scala에서 var나 mutable한 컬렉션을 제공하는 것도 이런 이유입니다. 기본적으로는 불변성을 지키는 FP 원칙을 따르되, 필요할 때는 mutable한 구조로 전환할 수 있는 유연성을 제공하는 것이죠. 이를 통해 함수형 프로그래밍의 이점을 유지하면서도, 상태 변화를 효과적으로 처리할 수 있습니다.

그래서 목표가?
변수를 지원하기 위해선 값의 변화를 허용해야 하고, 이를 위해 mutable data structure인 box를 구현한다!

Mutable Data Structure는 값을 변경할 수 있는 데이터 구조를 의미합니다. 즉, 생성된 후에도 데이터 구조의 내부 값이나 상태를 수정할 수 있습니다. 이는 값을 한 번 설정하면 변경할 수 없는 immutable data structure와 대비되는 개념입니다.

Mutable Data Structure의 필요성
프로그래밍에서 상태를 저장하고, 필요할 때 그 상태를 업데이트하는 것이 중요할 때가 많습니다. 특히 변수를 지원하고 프로그램의 상태를 관리하기 위해서는 이러한 mutable data structure가 필요합니다.

Scala에서의 Mutable Data Structure
Scala는 기본적으로 불변(immutable) 데이터 구조를 선호하지만, 변경 가능한(mutable) 데이터 구조도 제공합니다. 예를 들어, var 키워드로 선언된 변수는 값이 변경될 수 있는 반면, val 키워드로 선언된 변수는 불변으로 유지됩니다. 또한, scala.collection.mutable 패키지에는 변경 가능한 컬렉션들이 포함되어 있어 필요할 때 mutable한 데이터 구조를 사용할 수 있습니다.

Scala에서 간단한 Mutable Data Structure 구현 예시: Box
PLT에서 'box'는 값을 감싸고 그 값을 변경할 수 있는 구조로, 상태 변화의 예로 자주 사용됩니다.

class Box(var value: Int) {
  def set(newValue: Int): Unit = {
    value = newValue
  }

  def get: Int = value
}

// 사용 예시
val myBox = new Box(10)  // Box를 10으로 초기화
println(myBox.get)       // 10 출력
myBox.set(20)            // Box의 값을 20으로 변경
println(myBox.get)       // 20 출력

위 코드에서 Box는 value라는 변수를 가지고 있으며, 이 변수는 set 메서드를 통해 변경할 수 있습니다. 따라서 myBox 객체의 값은 초기에는 10이었지만, set 메서드 호출을 통해 20으로 바뀌었습니다.

mutable data structure가 중요한 이유
이런 구조는 프로그램에서 변경 가능한 상태를 구현하는 데 필수적입니다. PLT에서는 이러한 mutable 구조를 통해 변수, 할당, 상태 변화 등을 다룰 수 있으며, 이는 프로그래밍 언어의 기본적인 동작 방식을 이해하는 데 중요합니다.

순수 함수 설명 및 조건
1. 순수 함수 (Pure Function): 입력이 동일하면 항상 동일한 출력을 반환해야 합니다.
2. 부작용 없음 (No Side Effects): 함수 실행 중 외부 상태를 변경하지 않아야 합니다.
추가) 자바의 class와 box의 비슷한 점 : set/get으로 처리를 하는 것이 비슷..!

  • Box를 AE에 추가해보기 (BFAE = FUNCTION + AE + BOXES)
<Expr> ::= <num>
                    | {+ <Expr> <Expr>}
                    | {- <Expr> <Expr>}
                    | <id>
                    | {fun {<id>} <Expr>}
                    | {<Expr> <Expr>}
                    | {newbox <Expr>}
                    | {setbox <Expr> <Expr>}
                    | {openbox <Expr>}
                    | {seqn <Expr> <Expr>}

seqn : seqn에 포함된 { } 내부의 것이 순차적으로 실행되도록 한다. (이전 줄의 변화가 다음 줄의 변화에 영향을 미친다.)

scala에서 구현하려면..?

// 이걸로 충분? Nope! 추가 논리 필요함.
case Seqn(e1, e2) => 
		interp(e1, ds)
		interp(e2, ds)
        
// 이렇게 하면? -> 동적인 것처럼 작동 가능!
{with {a {newbox 1}}
    {with {f {fun {x} {+ x {openbox a}}}}
        {seqn
            {setbox a 2} // update 'a' like an assumption that 'ds' could be updated.
            {f 5}}}}

따라서.. 목표는..! 밑의 코드처럼 동작하도록 만드는 거! 

{with {b {newbox 0}}
   {seqn {setbox b {+ 1 {openbox b}}}   // b를 setbox로 수정
         {openbox b}}}

그런데 이거는 interp 2개 연잉서 짠 코드로는 논리가 부족..! 어떻게 해결 가능할까?

해결법!
두 개의 저장소 (캐시)를 통해 정적 스코프와 동적 변경을 분리해서 관리하려고 합니다. 각 캐시의 역할을 다음과 같이 설정할 수 있습니다:

  1. 정적 스코프용 캐시 (DefrdSub):

  • 정적 스코프에서 변수의 메모리 주소를 추적하기 위한 용도입니다. 이 캐시에는 각 변수가 정의될 때의 메모리 주소를 저장하여, 정적 범위 내에서 해당 변수를 참조할 때 항상 같은 주소를 사용하게 합니다.

  • DefrdSub라는 트레이트를 사용해 정의됩니다:

  • MtSub는 빈 저장소를 의미합니다.

  • ASub(name: Id, address: Int, saved: DefrdSub)는 변수 이름 (name), 메모리 주소 (address), 그리고 이전의 DefrdSub 상태 (saved)를 포함합니다. 이를 통해, 새로운 변수가 추가될 때마다 저장소에 쌓이는 구조입니다.

  1. 동적 변경을 관리하는 캐시 (Store):
  • 이 캐시는 변수의 현재 값을 저장하고 업데이트하기 위한 용도로, 변경 가능한 box 값을 관리합니다.
  • 이 캐시는 프로그램의 실행 중 값이 변경될 때마다 업데이트되어, 동적 스코프처럼 동작할 수 있게 합니다.
  • Store라는 트레이트를 사용해 정의됩니다:
  • MtSto는 빈 저장소를 나타냅니다.
  • ASto(address: Int, value: ExprValue, rest: Store)는 메모리 주소 (address), 해당 주소에 저장된 값 (value), 그리고 이전의 Store 상태 (rest)를 포함합니다. 이 구조로, 동적 변경이 발생할 때마다 새 값을 추가해 이전 상태를 유지할 수 있습니다.

추가설명
DefrdSub는 변수가 정적으로 정의된 위치를 추적하여, 해당 변수의 메모리 주소를 지속적으로 참조할 수 있게 합니다. 즉, f 같은 함수가 정의된 위치에서 접근해야 하는 메모리 주소를 유지합니다.
Store는 실행 중 발생하는 변수의 값 변화를 관리하여, setbox 같은 표현식으로 변수 값이 변경될 때마다 업데이트됩니다.
이 두 캐시를 분리함으로써, 정적 스코프와 동적 변화를 각각 관리하고, 프로그램의 실행 중에 발생하는 값을 업데이트하면서도 정적 스코프의 일관성을 유지할 수 있습니다.

trait Store
case object MtSto extends Store   // 텅 빈 거!
case class ASto (address: Int, value: ExprValue, rest: Store) extends Store    //

해서.. 해결된 최종본은..!

//interp: Expr DefrdSub Store -> ValueStore

trait ExprValue
case class NumV(n: Int) extends ExprValue
case class ClosureV(param: Id, body: Expr, ds: DefrdSub) extends ExprValue
case class BoxV(address: Int) extends ExprValue

// ValueStore가 정적, 동적 데이터를 다 받아줌.
trait ValueStore	
case class vs(value: ExprValue, store: Store) extends ValueStore

그리고 위의 코드를 작성해보면..!

def interp(expr: Expr, defrdSub: DefrdSub, store: Store): (ExprValue, Store) = expr match {
    case Seqn(e1, e2) =>
        val (result1, updatedStore1) = interp(e1, defrdSub, store)   // e1 평가 및 store 업데이트
        val (result2, updatedStore2) = interp(e2, defrdSub, updatedStore1)  // e2 평가에 업데이트된 store 사용
        (result2, updatedStore2)  // 최종 결과와 업데이트된 store 반환
    // 다른 경우들
}

이렇게 result와 updatestore을 둘 다 받아주는 형태!

위의 부분 간단 정리!
We must force the interpreter to return not only the value of each expression but also an updated store that reflects mutations made in the process of computing that value.

이제 이어서 내용을 학습하도록 하겠다..!

위에서는 수정된 값들을 저장하는 것을 위해 tuple를 사용해서 값을 저장했었다. (lexical, dynamic 둘 다!)

// Implementing Boxes with 'var' (State)

// interp : Expr DefrdSub -> Expr-Value
def interp(expr: Expr, ds: DefrdSub): ExprValue = expr match {
    …
	case Newbox(val_expr) => BoxV(interp(val_expr, ds))
	case Setbox(box_expr, val_expr) => interp(box_expr, ds) match {
    	case ev@BoxV(container) => ev.container = interp(val_expr, ds)
    	ev.container // For return type matching
}
	case Openbox(box_expr) => interp(box_expr, ds) match {
    	case ev@BoxV(container) => ev.container
}


// But this doesn't explain anything about boxes!
// We want to implement box operations from scratch!

practice!
1. 7 => vs(NumV(7), MtStore)
2. {+ 7 6} => vs(NumV(13), MtStore)
3. {with {b {newbox 7}}
{seqn {setbox b 10}
{openbox b}}}

=>vs(NumV(10),ASto(1,NumV(10),ASto(2,BoxV(1),ASto(1,NumV(7),MtSto))))

설명)
1. box에 할당할 캐시 생성
code) ASto(1,NumV(7),MtSto) : 1위치에 NumV(7)을 저장, 이때 store cache는 비워진 상태 그대로..!

  1. box에 값 할당하기
    code) ASto(2,BoxV(1),ASto(1,NumV(7),MtSto)) : 2 위치에 BoxV(1) 저장. 이때, BoxV(1)에는 Asto(1, NumV(7), MtSto) 가 들어가.

  2. box에 할당한 값을 새로운 값으로 update(set)하기 :: 이렇게 되는 이유가 seqn 때문에, 이전 변경이 사후에 영향을 주기 때문에 그런 거!
    code) Asto(1,NumV(10), ASto(2,BoxV(1),ASto(1,NumV(7),MtSto)))

  3. 결국저장할 값은 10..!
    vs(NumV(10), Asto(1,NumV(10), ASto(2,BoxV(1),ASto(1,NumV(7),MtSto))))

3번을 풀기 위한 개념


1. 정적 스코프용 캐시 (DefrdSub):

  • DefrdSub라는 트레이트를 사용해 정의됩니다:
  • MtSub는 빈 저장소를 의미합니다.
  • ASub(name: Id, address: Int, saved: DefrdSub)는 변수 이름 (name), 메모리 주소 (address), 그리고 이전의 DefrdSub 상태 (saved)를 포함합니다. 이를 통해, 새로운 변수가 추가될 때마다 저장소에 쌓이는 구조입니다.
  1. 동적 변경을 관리하는 캐시 (Store):
  • Store라는 트레이트를 사용해 정의됩니다:
  • MtSto는 빈 저장소를 나타냅니다.
  • ASto(address: Int, value: ExprValue, rest: Store)는 메모리 주소 (address), 해당 주소에 저장된 값 (value), 그리고 이전의 Store 상태 (rest)를 포함합니다. 이 구조로, 동적 변경이 발생할 때마다 새 값을 추가해 이전 상태를 유지할 수 있습니다.

trait Store
case object MtSto extends Store
case class ASto (address: Int, value: ExprValue, rest: Store) extends Store
위의 개념 중 ASto를 적용한 게 밑의 거!
Binding id → address to box(ExprValue) → address to value(ExprValue) → value

state 빼고 box 구현해보기.

//interp: Expr DefrdSub Store -> ValueStore

trait ExprValue
case class NumV(n: Int) extends ExprValue
case class ClosureV(param: Id, body: Expr, ds: DefrdSub) extends ExprValue
case class BoxV(address: Int) extends ExprValue

trait ValueStore
case class vs(value: ExprValue, store: Store) extends ValueStore

위 코드가 기본 꼴이고, 이걸 수정하여 코드를 만들겠음.

//interp: Expr DefrdSub Store -> ValueStore
def interp(expr: Expr, ds: DefrdSub, st: Store): ValueStore = expr match {
    case Num(n) => vs(NumV(n), st)
    case Add(l, r) => interp(l, ds, st) match {
	case vs(l_value, l_store) => interp(r, ds, l_store) match {
  	case vs(r_value, r_store) => vs(numAdd(l_value, r_value), r_store)
	}
  }
    …

설명!
interp(l, ds, st): 좌항 l을 정적 환경 ds와 저장소 st를 기반으로 평가합니다.
interp(r, ds, l_store): 우항 r을 정적 환경 ds와 좌항 평가 후의 Store (l_store)를 기반으로 평가합니다.

Q)Add 연산의 최종 반환에서 l_store가 아닌 r_store를 사용하는 이유?
1. 평가 순서에 따른 최신 상태 유지:

  • l_store는 좌항 평가 후의 저장소 상태이지만, 우항 r을 평가하는 동안 l_store가 r_store로 업데이트됩니다.
  • 따라서, Add의 최종 결과에서는 최신 저장소 상태인 r_store를 사용해야 합니다.
  1. 동적 상태 업데이트:
  • 좌항과 우항 평가 중에 Store가 변할 수 있습니다. 만약 Add 표현식이 setbox와 같은 변이 연산을 포함하는 경우, r_store가 l_store보다 최신 상태를 반영하게 됩니다.
  • l_store를 사용하면 우항 평가의 변경 사항이 반영되지 않을 수 있으므로, r_store를 사용하여 최종 상태를 일관되게 유지하는 것이 중요합니다.
profile
bells!
bell!
이전 포스트

PLT_6

0개의 댓글