Substitution(치환)에 관하여

치환은 어떤 코드에서 변수를 다른 값으로 바꾸는 과정을 얘기한다.

 

일단 다음과 같이 정하고 시작하자

x : 나중에 바꿀 식별자

5 : 이 값으로 바꿀거임

(+ x x) : 식별자가 들어있는 코드, x와 x를 더한다. 

근데 이 표현식에서 x를 5로 바꾸는 과정이 필요한데.. 이제 알아보자

 

다음 코드를 살펴보자

{with {x 5} {+ 10 y}}

이 코드가 x를 5로 치환하려고 하는 코드다.

근데 문제는 이 표현식 안에 x가 없다!

+ 10 y라는 표현식에는 x가 들어있지 않기 때문에 치환할 게 없는 상황이다.

잘못된 코드라는 거다..

 

다음 코드를 살펴보자

{with {x 5} {+ x {with {x 3} 10}}}

바깥쪽에서 x는 5로 치환되고 있다. 즉, + x 부분의 x는 5로 바뀐다.

근데 안쪽 {with {x 3} 10} 부분을 보면, 이 안에서는 x가 3으로 다시 정의되고 있다.

이 부분 안에서는 바깥의 x 치환이 영향을 주지 않기 때문에 안의 x는 5가 아니라 3으로 치환된다.

근데 안에서는 x가 3으로 재정의가 되지만 사용되지는 않기 때문에 10이 반환되므로 5+10 = 15가 도출된다.

이건 후에 나오는 스코프라는 개념과 연결된다.

 

이를 보면 더 이해하기 쉽다.

with {x 5} {+ x 5}

Binding Instance(그 변수가 어디서 값이 결정되는지 알려주는 거)에 따르면 with 구문에서 첫 번째 자리 {x 5}가 나오면, 여기서 x는 5로 바인딩된다.

리고 그 아래쪽 표현식인 {+ x 5}에서는 그 바인딩된 값을 사용하기 때문에 + 5 5로 바뀐다.

위의 코드에서도 보다시피 이미 x는 5로 바뀐 상황에서 3으로 치환하려고 해서 오류가 난거다.

그래서 중요한 건, 바인딩이 어디서 일어나는지를 잘 알아야 치환을 정확하게 할 수 있다는 거다.

 

이제 치환을 더 깊게 이해하기 위해 Scope라는 용어를 알아보자

Scope는 어떤 변수가 바인딩된 값이 적용되는 프로그램 코드의 영역이다.

예를 들어, {with {x 5} {+ x x}}에서 x는 5로 바인딩되었고, 그 바인딩이 적용되는 스코프는 {+ x x} 부분이다.

그래서 이 코드에서 두 개의 x는 전부 5로 바뀐다.

다음 예를 알아보자면, {with {x 5} {+ x {with {x 3} x}}}를 보자.

바깥쪽 x는 5로 바인딩되지만 내부 스코프에서는 x가 3이기 때문에 바깥쪽은 5, 안쪽은 3이 된다.

여기서는 스코프가 겹치지 않는다는 게 중요하다.

바깥쪽 x의 값이 안쪽 x에 영향을 주지 않으니 주의하자.

여기서 바인딩된 값이 적용되는 범위(스코프) 안에 있는 식별자(변수)를 Bound Instance라고 한다.

아까 {with {x 5} {+ x {with {x 3} 10}}} 이 코드에서 보다시피.. 바인딩된 인스턴스는 치환할 때 보호된다.

{with {x 5} {+ x {with {x 3} x}}} 다음과 같은 코드의 경우 결과는 

{with {x 5} {+ 5 {with {x 3} 3}}} 

이렇게 된다는 것이다.

이런 결과를 계산할 수 있어야 한다. 답은 8이다.

 

 

이제 Free Identifier를 알아보자

Free Identifier는 어떤 바인딩 인스턴스의 스코프 안에 포함되지 않을 때, 즉 그 변수에 대한 바인딩이 없을 때 Free Identifier라고 부른다.

쉽게 말해서, 어떤 값으로도 연결되지 않은 변수다.

예시 코드를 살펴보자

{with {x 5} {+ x {with {y 3} x}}}

바깥 x는 5로 바인딩되고 안쪽 y는 3으로 바인딩된다. 

근데 이제 {with {y 3} x}에서 x를 살펴보면.. 바인딩된 인스턴스가 없다. 바깥쪽 with {x 5}는 안쪽으로 영향을 미치지 않기 때문에, 이 x는 바인딩되지 않은 자유 인스턴스라고 할 수 있다.. 그래서 치환해보면,

{with {x 5} {+ 5 {with {y 3} 5}}}

이렇게 되기 때문에 10이 나온다.

 

 

이제 Substitution의 예를 살펴보자

{with {x 5} {+ x {with {y x} x}}}

다음과 같은 코드가 있다고 해보자

{with {x 5} {+ 5 {with {5 5} 5}}}

답은 10이 나오는데

with {y 5} 5는 결국 y가 5든 뭐든 상관없고, 뒤에 있는 숫자 그냥 5를 그대로 반환하기 때문이다.

 

다음 예시를 살펴보자

{with {x 5} {+ x {with {x {+ x 1}} x}}}

이와 같은 경우는

바깥 x는 5가 되고 안의 x는 6으로 재정의되는 것을 보여준다.

그렇기 때문에 결과는 11이 된다.

 

치환은 다음과 같은 문법으로 작성할 수 있다.

{with {<id> <Expr>} <Expr>}

 

이를 Scala에서 정의하려고 하면

case class With(name: Id, nameExp: Expr, body: Expr) extends Expr:

이렇게 만들 수 있다.

 

이를 파싱하려고 하면 다음과 같이 asset 문을 쓰고 체크할 수 있다.

assert(parse("{with {x 5} {+ 8 2}}") == With(Id("x"), Num(5), Add(Num(8), Num(2))))

콘크리트 Syntax를 추상 Syntax로 바꾸는 과정인거 이제 알 것이다.

 

이를 구현하려고 계획하려면 어떻게 해야할까?

// [contract] subst: Expr Id number -> Expr
// (here, Id is an identifier and number is the value for the identifier)
// [purpose] to substitute second argument with third argument in first argument,
// as per the rules of substitution, the resulting expression contains
// no free instances of the second argument

def subst(expr: Expr, idtf: Id, value: Int): Expr = expr match {
  case Num(num) => expr
  case Add(lhs, rhs) => Add(subst(lhs, idtf, value), subst(rhs, idtf, value))
  case Sub(lhs, rhs) => Sub(subst(lhs, idtf, value), subst(rhs, idtf, value))
  case With(i, v, e) => With(i, subst(v, idtf, value), if (i == idtf) e else subst(e, idtf, value))
  case Id(s) => if (id(s) == idtf) Num(value) else expr
}

함수 안의 내용을 설명해보자면

case Add(lhs, rhs) => Add(subst(lhs, idtf, value), subst(rhs, idtf, value))

이거는 Add(Num(1), Id("x"))에서 x를 10으로 치환하면 Add(Num(1), Num(10))으로 바뀌도록 설계한거다.

 

뺄셈도 마찬가지고

 

case With(i, v, e) => With(i, subst(v, idtf, value), if (i == idtf) e else subst(e, idtf, value))

첫 번째 인자(i)는 with에서 선언한 변수고, 두 번째(v) 는 그 변수에 할당된 값이다. 세 번째(e)는 그 변수를 사용하는 본문이다.

i와 idtf(치환하려는 변수) 가 같은 경우 그 변수는 이미 재정의됐기 때문에 본문(e)에서는 더 이상 치환하지 않는다.

즉, 치환 작업을 하지 않고 e를 그대로 둔다.

i와 idtf가 다를 경우 본문(e)에서 계속해서 치환 작업을 진행하는 식으로 설계한다.

 

case Id(s) => if (id(s) == idtf) Num(value) else expr

이건 변수(Id)일 때다.

만약 현재 변수가 치환하려는 변수(idtf)와 같다면, 그 변수를 값(Num(value))으로 대체한다.

만약 다르다면, 아무런 변화 없이 그 변수를 그대로 반환한다.

 

이런 설계 틀을 짜주고

테스트 케이스들을 몇 개 생각해보자

{with {x 10} 5}와 같은 경우는 5가 나와야 한다.

그러니 assert를 이제 맞춰쓰면

assert(subst(Num(5), Id("x"), 10) == Num(5)) 이렇게 되면 정상이다.

 

{with {x 10} {+ 1 x}}

이 테스트 케이스는 11이 나와야 한다.

assert(subst(Add(Num(1), Id("x")), Id("x"), 10) == Add(Num(1), Num(10)))

이렇게 assert를 작성해주면 될 것 같다.

 

{with {x 10} x}

이거는 그냥 10이고

 

{with {x 10} y}

이거는 그냥 아무것도 아닌 y가 반환돼야하므로

assert(subst(Id("y"), Id("x"), 10) == Id("y"))

이렇게 assert 만들면 된다.

 

이제 치환된 표현식을 계산해주는 함수인 interp함수를 보자

def interp(wae: Expr): Int = wae match {
  case Num(n) => n
  case Add(l, r) => interp(l) + interp(r)
  case Sub(l, r) => interp(l) - interp(r)
  case With(i, v, e) => interp(subst(e, i, interp(v)))
  case Id(s) => throw new SimpleException(s"Free identifier: $s")
}

 

이 함수는 wae 표현식을 실제로 계산해서 숫자로 변환해주는 함수다.

Num을 만나면 숫자를 그대로 반환하고,

Add와 Sub는 각각 좌우의 표현식을 해석해서 더하거나 빼준다.

With 구문에서는 변수 바인딩이 필요할 때 subst 함수를 이용해 본문 e에서 변수를 값으로 대체한 뒤에 그걸 다시 해석한다.

만약 정의되지 않은 변수(Id) 를 만나면, 자유 변수 에러를 발생시킨다.

왜 에러를 발생시키냐면 {with {x 5} {+ x y}} 다음과 같은 코드가 있을 때 y는 자유변수가 된다.

근데 y는 현재 아무 값도 없는데 x랑 더한다는게 비정상적이지 않은가?

이런 이유로 해석기가 이를 처리할 수 없어 에러를 발생시킨다.

 

즉, interp는 주어진 표현식을 계산해서 최종 값을 반환하는 역할을 한다.

 

예시를 보자면

interp(parse("{with {x 5} {+ x x}}"))

이걸 처리하면 {with {x 5} {+ x x}}에서 x를 5로 바인딩하고 subst를 이용해 {+ x x}를 {+ 5 5}로 치환한다.

그런 다음 계산해서 10이라는 답을 내놓는다.