람다 대수 인자 이름이 같을 때

이 글은 책 The implementation of functional programming languages에서 2.2.2.2 Naming을 읽고 정리한 것이다.

Naming

여러 형식 인자 이름이 같을 때 주의를 해야 한다. 예를 들어 다음과 같은 식이 있다고 하자.

첫 번째 축약에서 안쪽에 있는 $x$를 바꾸지 않았는데, 그 이유는 안쪽에 있는 $x$가 $\lambda x$로 감싸져 있기 때문이다. 안쪽에 있는 $x$는 바깥쪽 $\lambda x$ 추상의 본문(body)에서 자유 변수가 아니다.

람다 추상화 $(\lambda x.E)$에서 정확히 어떤 $x$를 바꿀지 어떻게 알 수 있을까? 방법은 의외로 쉬운데 (아님) 식 $E$에서 자유 변수인 것을 바꾸면 된다. 만약 어떤 변수가 식 $E$에서 자유 변수라면 그 변수는 $\lambda x$ 추상화 $(\lambda x.E)$에서 종속 변수가 된다. 그래서 위 예제에서 바깥쪽 $\lambda x$ 추상화를 적용할 때 먼저 본문을 확인한다.

두 번째 $x$만 자유 변수이므로 인자로 바꿔 쓴다.

이게 바로 본문에서 자유 변수만 바꾸면 된다고 했던 이유이다. 블록으로 구분해서 변수의 범위를 중첩하는 언어에서도 비슷한 규칙을 따른다.

아래는 비슷한 종류의 다른 예시이다.

다시 한번 해보면, 첫 번째 축약에서 안쪽에 있는 $x$는 바깥쪽 $\lambda x$ 추상의 본문에서 자유 변수가 아니기 때문에 안쪽에 있는 $x$는 바꿔 쓰지 않았다.

참고

• https://archive.org/details/implementationof00peyt