참조 투명성

3. 정의

어떤 표현식이 프로그램 내의 어떤 위치에서든 그 값으로 대체될 수 있다면, 그 표현식은 참조 상 투명하다고 한다. 이는 표현식의 평가가 문맥에 의존하지 않고 독립적으로 이루어진다는 것을 의미한다.^[4]

형식 언어에서는 대체 가능성과 관련된 참조 투명성, 명확성, 전개 가능성과 같은 속성들이 정의된다.^[4]
참조 투명성:

• 위치 $p$가 표현식 $e$에서 ''순수 참조적''이라는 것은, 모든 표현식 $e_1$, $e_2$에 대해 $e_1 = e_2$가 $e[e_1/p] = e[e_2/p]$를 의미할 때 정의된다. 즉, 위치는 동일성의 대체 가능성을 따르는 경우에만 표현식에서 순수 참조적이다. $\epsilon$는 모든 표현식에서 순수 참조적이다.
• 연산자 $\Omega$가 위치 $i$에서 ''참조 투명''하다는 것은, 모든 위치 $p$ 및 표현식 $e_1, \dots, e_n$에 대해, $p$가 $e_i$에서 순수 참조적이면 $i.p$가 $e \equiv <\Omega e_1 \dots e_i \dots e_n>$에서 순수 참조적임을 의미할 때 정의된다. 그렇지 않으면 $\Omega$는 위치 $i$에서 ''참조 불투명''하다.
• 연산자가 ''참조 투명''하다는 것은 모든 위치에서 참조 투명하다는 것으로 정의된다. 그렇지 않으면 ''참조 불투명''하다.
• 형식 언어가 ''참조 투명''하다는 것은 모든 연산자가 참조 투명하다는 것으로 정의된다. 그렇지 않으면 ''참조 불투명''하다.

• 형식 언어는 해당 범위 내에서 변수의 모든 발생이 동일한 값을 나타내는 경우 ''확정적''으로 정의된다.

• 형식 언어는 모든 표현식이 β-감소 가능할 때 ''전개 가능''하다고 정의된다.

• 이 세 가지 속성은 서로 독립적이다.
• 명확성은 결정적 언어에서만 전개 가능성을 함의한다.
• 비결정적 언어는 명확성과 전개 가능성을 동시에 가질 수 없다.

4. 예제와 반증

표현식과 관련된 모든 함수가 순수 함수라면, 그 표현식은 참조 상 투명하다. 순수하지 않은 함수라도 그 값이 무시되거나 부작용이 사소하다면 표현식에 포함될 수 있다.

예를 들어, 산술 연산은 참조 상 투명하다. $5\; \backslash times\; 5$는 $25$로 대체할 수 있다. 수학적 관점에서 모든 함수는 참조 상 투명하다. $\backslash sin(x)$는 특정 $x$에 대해 항상 같은 결과를 반환하므로 투명하다.

반면 할당은 투명하지 않다. 예를 들어 C에서 $x\; =\; x\; +\; 1$은 변수 $x$에 할당되는 값을 변경한다. $x$의 초기값이 10이라면, 이 표현식을 두 번 평가하면 각각 $11$과 $12$가 된다. $x\; =\; x\; +\; 1$을 $11$이나 $12$로 대체하면 프로그램의 의미가 달라지므로, 이 표현식은 참조 상 투명하지 않다. 그러나 `int plusone(int x) { return x + 1; }`과 같은 함수 호출은 $x$를 변경하지 않고 부작용이 없으므로 투명하다.

`today()`는 투명하지 않다. "Jan 1, 2001"로 대체하면 내일은 같은 값이 아니기 때문이다. 이는 상태(날짜)에 의존하기 때문이다.

하스켈처럼 부작용이 없는 언어에서는 모든 값 $x$에 대해 $f(x)\; =\; f(x)$이므로, 같은 것을 같은 것으로 대체할 수 있다. 부작용이 있는 언어에서는 이것이 불가능하다.

C 언어로 작성된 두 함수를 비교하면, 하나는 참조 투명하고(rt) 다른 하나는 참조 불투명하다(rq).

```c

int globalValue = 0;

int rq(int x)

{

globalValue++;

return x + globalValue;

}

int rt(int x)

{

return x + 1;

}

```

`rt`는 `x = y`일 때 `rt(x) = rt(y)`이므로 참조 투명하다. 예를 들어 `rt(6) = 7`, `rt(4) = 5`이다. 그러나 `rq`는 수정 가능한 전역 변수를 사용하므로 이에 대해 말할 수 없다.

`rq`의 참조 불투명성은 프로그램 추론을 어렵게 한다. 예를 들어 다음 구문을 보자.

`integer p = rq(x) + rq(y) * (rq(x) - rq(x));`

`rq(x)`가 매번 다른 값을 가질 수 있으므로, 이를 단순화하여 `rq(x)`로 만들 수 없다. `rq`는 전역 변수에 의존하기 때문에 `x - x = 0`과 같은 수학적 항등식이 유지되지 않는다.

5. 명령형 프로그래밍과의 대조

명령형 프로그래밍에서 표현식의 대체는 프로그램 실행의 특정 시점에서만 유효할 수 있다. 이러한 시퀀스 포인트의 정의와 순서는 명령형 프로그래밍의 이론적 기초이며 명령형 프로그래밍 언어 시맨틱의 일부이다.^[1]

그러나 참조 투명한 표현식은 임의의 시점에 평가될 수 있으므로, 시퀀스 포인트 정의나 전체적인 평가 순서의 보장은 필요하지 않다. 이러한 것을 고려하지 않는 프로그래밍을 순수 함수형 프로그래밍이라고 부른다.^[1]

참조 투명한 스타일의 코드 작성은 지능적인 컴파일러와 정적 코드 분석을 더 쉽게 하며, 자동으로 더 나은 코드 향상 변형을 가능하게 하는 장점이 있다. 예를 들어, C로 프로그래밍할 때 루프 내에서 비용이 비싼 함수 호출을 포함하는 경우, 함수 호출을 프로그램 결과에 영향 없이 루프 밖으로 빼더라도 성능 페널티가 발생한다. 프로그래머는 소스 코드 가독성을 희생하여 수동으로 코드 모션을 실행해야 할 수 있다. 하지만 컴파일러가 해당 함수 호출이 참조 투명하다는 것을 알 수 있다면, 이러한 변형을 자동으로 수행할 수 있다.^[1]

참조 투명성을 강제하는 언어의 주요 단점은, 연속적인 단계를 갖는 명령형 프로그래밍 스타일에 자연스럽게 맞춰진 연산 표현식을 더 어색하고 덜 간결하게 만든다는 것이다. 그러한 언어들은 명확한 문법과 모나드와 같은 언어의 순수 함수 속성을 유지하면서도, 앞서 말한 작업들을 더 쉽게 만들기 위한 메커니즘을 종종 받아들인다.^[1]

6. 기술적 과제와 해결

참조 상 투명한 표현식은 임의의 시점에 평가될 수 있으므로, 시퀀스 포인트 정의나 전체적인 평가 순서 보장은 필요하지 않다. 이러한 점을 고려하지 않는 프로그래밍을 순수 함수형 프로그래밍이라고 부른다.

참조 상 투명한 스타일의 코드 작성은 지능적인 컴파일러와 정적 코드 분석을 쉽게 하고, 자동으로 더 나은 코드 개선을 가능하게 한다. 예를 들어 C로 프로그래밍할 때, 루프 안에서 비용이 큰 함수를 호출하면 성능 저하가 발생할 수 있다. 이는 함수 호출을 프로그램 결과에 영향을 주지 않고 루프 밖으로 빼는 경우에도 마찬가지다. 프로그래머는 소스 코드 가독성을 희생하여 수동으로 코드를 옮겨야 할 수 있다. 그러나 컴파일러가 해당 함수 호출이 참조 상 투명하다는 것을 알 수 있다면, 이러한 변형을 자동으로 수행할 수 있다.^[1]

참조 투명성을 강제하는 언어의 주요 단점은 연속적인 단계를 가지는 명령형 프로그래밍 스타일에 자연스럽게 맞춰진 연산 표현식을 더 어색하고 덜 간결하게 만든다는 것이다. 그러한 언어들은 명확한 문법과 모나드와 같은, 언어의 순수 함수적 성질을 유지하면서도 앞서 말한 작업들을 더 쉽게 만들기 위한 메커니즘을 도입하기도 한다.^[1]

ML과 같이 기본적으로 함수형을 지향하지만 보조적으로 대입 기능도 갖추어, 식에 상태를 갖게 하는 경우가 종종 있다. Haskell에서는 모나드 형과 구문 설탕을 이용하여 참조 투명성을 유지한 채 절차형적인 표현을 가능하게 한다.^[1] Clean에서는 한 번 참조하면 두 번 다시 참조하지 않는다는 일의성을 그 값의 타입에 부가 속성으로 부여하여, 대입을 이용하면서 참조 투명성을 유지하고, 효율화도 실현하고 있다.^[1] Haskell 2010에서 ST 모나드(State Transformer 모나드)로 결실을 맺었다. 참조 투명성을 만족하는 함수는 인수가 같으면 같은 값을 반환하므로, 대입을 사용해도 그 성질을 만족하고, 다른 계산에도 영향을 미치지 않으면 된다. 이것이 ST 모나드이다.^[1]

6. 1. 대입과 참조 투명성

6. 2. 부작용과 참조 투명성

6. 3. 해결 방안

7. 관련 개념

• 멱등성: 연산을 여러 번 적용해도 결과가 달라지지 않는 성질이다.
• 리스코프 치환 원칙: 객체 지향 프로그래밍에서 하위 타입 객체가 상위 타입 객체를 대체할 수 있어야 한다는 원칙이다.
• 재작성 규칙: 표현식을 동등한 다른 표현식으로 바꾸는 규칙이다.
• 함수형 프로그래밍 언어: 부작용이 없는 순수 함수를 중심으로 하는 프로그래밍 패러다임이다.
• 분산 처리: 여러 컴퓨터에 작업을 분산하여 처리하는 방식이다.
• 메모이제이션: 함수의 결과를 캐싱하여 동일한 입력에 대한 반복 계산을 피하는 기법이다.

참조

_[1] 서적 Word and Object https://archive.org/[...] MIT Press 1960
_[2] 간행물 Fundamental Concepts in Programming Languages 1967
_[3] 서적 Principia Mathematica https://archive.org/[...] Cambridge University Press 1927
_[4] 논문 Referential Transparency, Definiteness and Unfoldability http://www.itu.dk/pe[...] 1990