Substitution의 연기

with {x 1} { with {y 2} { + 100 {+ 99 {+ 98 ... {+ y x}...}
만약에 이런 연산을 하려고 하면

이 계산을 위해 모든 표현을 순차적으로 찾아가며 x, y값을 대입하게 된다.

중간에 x나 y가 더 자주 등장하면 그때마다 각각의 값을 대입해야 한다.

이 방법은 식이 복잡하고 변수의 등장 횟수가 많아질수록 반복적으로 대입 작업을 해야 하기 때문에 매우 비효율적이다.

이는 보통 O(nm)의 시간 복잡도를 가진다.

n은 변수의 개수

m은 식의 개수다.

 

다만, 대입을 연기하는 경우(Deferring Substitution)을 이용하면 이 시간을 단축할 수 있다.

처음에는 x에 1을 넣는다는 걸 기억하고 값을 바로 대입하지 않고 대입 리스트에 추가한다.

예를 들어, 대입 리스트는 [(x, 1)]가 된다.

그 다음 y에 2를 넣을 때도 바로 대입하지 않고, 역시 리스트에 추가한다. 

이제 리스트는 [(y, 2), (x, 1)]가 된다.

이제 본격적으로 계산할 때, + y x를 만나게 되는데, 이때 대입 리스트를 사용해서 필요한 값을 찾아 계산한다.

대입 리스트의 최신 값을 사용하기 때문에, y는 2, x는 1로 대체할 수 있다.

따라서 + y x는 + 2 1 이 된다.

중요한 점은, 모든 대입을 한 번에 최종적으로 처리하므로, 변수들이 여러 번 등장하더라도 각각의 값들을 일일이 찾는 과정이 줄어들어 훨씬 효율적으로 계산할 수 있다.

시간 복잡도는 O(m)이 된다.

 

그러면, 

with {x 1} 
  { with {y 2} 
    { with {x 4} 
      { + y x } } }

이처럼 도중에 바인딩 되면 대입 연기의 경우 어떻게 처리해야 할까?

바로 대입 리스트의 맨 앞에 새로운 값을 추가한다.

[x = 4, y = 2, x = 1] 이런 리스트가 만들어진다.

대입을 연기하는 방식에서는 대입 리스트를 최신으로 유지하고 가장 최근에 추가된 값을 사용해서 계산을 진행하기 때문에 이렇게 하면 x는 4로 바뀌게 된다.

이렇게 하면 변수의 값이 여러 번 바뀌어도 항상 올바른 최신 값을 사용할 수 있다.

 

{with {x 1} {+ {with {x 2} x} x}}

다음과 같은 식이 인터프리터로 들어가게 되면

{+ {with {x 2} x} x} 이렇게 바뀌고 [] 안에 x = 1이 들어가게 된다. 즉, [x = 1]

그리고 위의 식이 또 인터프리터로 들어가게 되면

{with {x 2} x}와 x로 나뉘어 들어가게 된다.

왜냐면 case문에서 with 구문과 그냥 일반 ID case로 나뉘어 들어가기 때문

{with {x 2} x}는 [x = 2, x = 1]이 되어 x가 2가 될 것이고

x는 그냥 [x = 1]을 이용하여 1이 될거다.

결론적으로 계산을 하게 되면 2+1=3 이 되는거다.

 

 

 

---

 

이제 대입을 연기하는 방식을 코드로 표현해보자

 

변경된 함수를 정의하자

Change
; interp : Expr -> number
to
; interp : Expr DefrdSub -> number

 

이렇게 해서 대입을 연기한 후 나중에 필요할 때 값을 가져올 수 있도록 만든다.

 

trait DefrdSub
case object MtSub extends DefrdSub
case class ASub(name: Id, value: Int, saved: DefrdSub) extends DefrdSub

 

MtSub는 빈 대입 리스트를 나타낸다. 

ASub는 대입 리스트에 실제로 대입된 값을 저장하는 객체다.

saved는 이전의 대입 리스트로  이를 통해 대입이 체인 형태로 연결되어 관리된다.

 

다음은 예시 인스턴스다

ASub(Id("x"), 1,
  ASub(Id("y"), 4, ASub(Id("x"), 2, MtSub)))

마지막 MtSub는 더 이상 이전 대입이 없음을 나타낸다.

 

 

// interp : Expr DefrdSub -> number

def interp(expr: Expr, ds: DefrdSub): Int = expr match {
  case Num(n) => n
  case Add(l, r) => interp(l, ds) + interp(r, ds)
  case Sub(l, r) => interp(l, ds) - interp(r, ds)
  case With(i, v, e) => interp(e, ASub(i, interp(v, ds), ds))
  case Id(s) => lookup(Id(s), ds)
}

 

// lookup: Id DefrdSub -> number

def lookup(name: Id, ds: DefrdSub): Int = ds match {
  case MtSub => throw new SimpleException(s"Free Identifier: $name")
  case ASub(i, v, saved) => if (i == name) v else lookup(name, saved)
}

 

기존에는 With 표현식을 만날 때마다 변수를 대입하고 그걸 다시 계산하는 과정이 필요했다.

대입이 여러 번 일어날 때마다, subst 함수로 모든 표현식을 일일이 수정하기 때문에 비효율적일 수 있다.

근데 이제는 대입을 즉시 수행하지 않고 필요할 때만 리스트에서 값을 가져올 수 있다.

ASub(i, interp(v, ds), ds)를 사용해서 대입 리스트에 새로운 값(i = v)을 추가하고 기존의 대입 리스트(ds)도 함께 저장한다.

그리고 변수를 만났을 때는 lookup 함수를 사용해서 대입 리스트에서 해당 변수의 값을 찾는다.

 

lookup 함수는 변수의 값과 대입 리스트를 받아서 그 변수의 값을 반환한다.

대입 리스트가 비어 있는 경우(MtSub), 즉 대입된 값이 없는 경우에는 예외를 던져서 오류를 발생시킨다.

대입 리스트에 값이 있는 경우(ASub), 만약 현재 변수 이름(i)이 찾고자 하는 변수 이름(name)과 같다면, 그 값을 반환한다.

그렇지 않다면, 대입 리스트의 다음 부분(saved)을 계속 탐색한다.

이 lookup 함수는 대입 리스트에서 가장 최신의 값을 찾기 위해 리스트를 앞에서부터 차례로 탐색하는 방식이다.

이를 통해 대입을 연기하면서 필요한 시점에 최신의 대입 값을 확인할 수 있다.

 

---

 

이제 함수 호출과 그에 따른 대입을 연기하는 과정에 대해 알아보자

 

{deffun {f x} {+ 1 x}}

 

다음과 같이 함수가 호출되었다고 하자

 

interp(parse ("{with {y 2} {f 10}}"), [])

 

이렇게 인터프리터에 들어왔다면,

 

interp(parse ("{f 10}"), [y = 2])

이렇게 y가 바인딩되고 대괄호에 y = 2가 기억된다.

이제 함수 본문을 해석할 차례다.

interp(parse ("{+ 1 x}"), [...])

이때 대입 리스트에는 x = 10만 추가된다.

기존에 있던 y = 2는 함수 본문 해석에 영향을 주지 않는다.

대입 리스트는 함수 호출 시 그 호출과 관련된 값만 사용하기 때문이다.

따라서 기존의 대입 리스트를 무시하고, 현재 함수 호출에 필요한 값인 x만 사용하게 된다.

즉, 이전에 정의된 다른 변수(y = 2)는 함수 본문을 해석할 때 참조되지 않으며, 오직 함수 매개변수(x = 10)만 대입 리스트에 존재한다.

 

다만.. 만약 이렇게 함수가 정의되었다면..

{deffun {f x} {+ y x}}

interp(parse ("{with {y 2} {f 10}}"), [])
이렇게 사용하려고 하면.. 어떻게 될까

 

interp(parse ("{f 10}"), [y = 2])

이렇게 될테고

함수 본문을 해석하기 위해 들어가서

interp(parse ("{+ y x}"), [x = 10])

이렇게 될텐데

이러면 기존에 있던 대입 리스트가 무시되어 y값은 증발한다. ㅋㅋㅋ

이러면 문제가 발생한다.. "free var: y"

이 문제는 함수 호출 시 기존 대입 리스트를 확장하지 않고 덮어쓰는 방식 때문에 발생했다.

 

함수 호출 시 대입 리스트를 관리하는 방법에서 변수의 스코프가 굉장히 중요한 역할을 한다.

함수에서 사용되는 변수들이 외부의 값에 어떻게 접근하고 관리되는지는 프로그램의 정확성과 예측 가능성에 큰 영향을 미치기 때문이다.

 

정적 스코프는 코드가 명확하게 어디서 어떤 변수를 참조하는지를 알 수 있게 해줘서, 코드의 예측 가능성을 높여준다.

동적 스코프는 프로그램의 실행 상태에 따라 변수 값을 바꿀 수 있기 때문에, 동적으로 값을 조절해야 할 때 유용하지만, 코드의 예측 가능성을 떨어뜨릴 수 있다.

 

다음은 함수 호출까지 포함한 인터프리터의 코드다.

 

// interp : Expr list-of-FunDef DefrdSub -> number

def interp(expr: Expr, funDefs: List[FunDef], ds: DefrdSub): Int = expr match {
  case Num(n) => n
  case Add(l, r) => interp(l, funDefs, ds) + interp(r, funDefs, ds)
  case Sub(l, r) => interp(l, funDefs, ds) - interp(r, funDefs, ds)
  case With(i, v, e) => interp(e, funDefs, ASub(i, interp(v, funDefs, ds), ds))
  case Id(s) => lookup(Id(s), ds)
  case App(ftn, arg) =>
    val FunDef(_, argName, body) = lookupFunDef(ftn, funDefs)
    interp(body, funDefs, ASub(argName, interp(arg, funDefs, ds), MtSub))
}

 

여기서 App에 있는 MtSub는 대입 리스트의 시작을 나타내며, 이는 새로운 함수 호출 시 새로운 대입 환경을 시작한다는 것을 의미한다.