참조 투명도
Referential transparency
참조 투명성과 참조 불투명성은 컴퓨터 프로그램의 일부분 특성이다. 프로그램의 동작을 바꾸지 않고 그에 상응하는 값(및 그 반대)으로 대체할 수 있는 표현은 참조적으로 투명하다고 한다.[1] 이를 위해서는 표현식이 순수해야 하며, 즉 표현값이 동일한 입력에 대해 동일해야 하며 그 평가에는 부작용이 없어야 한다. 참조적으로 투명하지 않은 표현을 참조적으로 불투명하다고 한다.
수학에서 모든 함수 적용은 수학 함수를 구성하는 것의 정의에 의해 참조적으로 투명하다. 그러나 잘못된 함축적 의미를 피하기 위해 절차와 방법을 사용하는 프로그래밍에서는 항상 이러한 경우가 아니다. 기능 프로그래밍에서는 참조적으로 투명한 기능만 고려한다. 일부 프로그래밍 언어는 참조 투명성을 보장하는 수단을 제공한다. 일부 기능 프로그래밍 언어는 모든 기능에 대해 참조 투명성을 강제한다.
참조 투명성의 중요성은 프로그래머와 컴파일러가 프로그램 행동에 대해 다시 쓰기 시스템으로 추론할 수 있도록 한다는 것이다. 이것은 정확성 증명, 알고리즘의 단순화, 코드를 깨지 않고 수정하는 것을 돕거나, 메모화, 일반적인 하위표현 제거, 게으른 평가 또는 병렬화를 통해 코드를 최적화하는 데 도움이 될 수 있다.
역사
이 개념은 알프레드 노스 화이트헤드와 버트란드 러셀의 프린키니아 마티카(1910–13)에서 유래한 것으로 보인다.[2] 그것은 윌러드 반 오르만 콰인(Willard Van Orman Quine)에 의해 분석철학에서 채택되었다. Word and Object(1960년)의 §30에서 Quine은 다음과 같은 정의를 내린다.
격납건물 φ의 모드는 단수 t의 발생이 용어나 문장 t(t)에서 순수하게 참조될 때마다 포함된 용어 φ(ψ)(t)에서도 순수하게 참조되는 경우 참조 투명하다.
이 용어는 프로그래밍 언어의 변수에 대한 논의에서 크리스토퍼 스트레이치의 강의 노트인 프로그래밍 언어의 기본 개념에 현대 컴퓨터 과학 용어에 등장했다. 강의 노트에는 서지학에서 Quine의 말과 사물이 언급되어 있다.
예제 및 counterexample
표현에 관련된 모든 함수가 순수한 함수라면 표현은 참조적으로 투명하다.
일부 소스에서 입력을 반환하는 함수를 고려하십시오. 유사 코드에서 이 함수에 대한 호출은 GetInput(Source) 어디에 Source 특정 디스크 파일, 키보드 등을 식별할 수 있다. 동일한 값을 가진 경우에도 Source, 연속적인 반환 값은 다를 것이다. 그러므로 함수 GetInput() 결정론적이거나 참조적으로 투명하지 않다.
보다 미묘한 예로는 자유 변수를 갖는 함수의 예를 들 수 있는데, 즉 매개변수로 명시적으로 전달되지 않는 일부 입력에 의존한다. 그런 다음 글로벌 변수, 현재 실행 환경의 변수(동적 바인딩의 경우) 또는 폐쇄의 변수(정적 바인딩의 경우)와 같은 비로컬 변수에 대한 이름 바인딩 규칙에 따라 해결된다. 매개변수로 전달된 값을 변경하지 않고 이 변수를 변경할 수 있으므로 매개변수가 동일하더라도 기능에 대한 후속 호출의 결과는 다를 수 있다. 그러나 순수한 기능 프로그래밍에서는 파괴적 할당이 허용되지 않으므로 자유 변수가 값에 정적으로 바인딩되어 있는 경우에는 정적 바인딩과 불변성으로 인해 비 로컬 변수와 그 값이 각각 변경될 수 없기 때문에 함수는 여전히 참조적으로 투명하다.
산술 연산은 참조적으로 투명하다. 5 * 5 으로 대체될 수 있다. 25예를 들어. 사실 수학적 의미에서의 모든 함수는 참조적으로 투명하다. 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 == y 그때 f(x) == f(y)이것은 구별할 수 없는 동일성으로도 알려진 재산이다. 그러한 속성은 부작용이 있는 언어의 경우 일반적으로 유지될 필요가 없다. 그렇더라도 그러한 주장을 유형별 사용자 정의 동등성은 포함하지 않고, 시스템이 시험한 용어의 동일성인 이른바 판단적 평등으로 제한하는 것이 중요하다. 예를 들어, 다음과 같다. B f(A x) 그리고 유형 A 예를 들어, 모든 용어를 동등하게 만드는 것과 같은 평등의 개념을 무시했다. 그러면 평등의 개념을 가질 수 있다. x == y 그럼에도 불구하고 f(x) != f(y)이것은 Haskell과 같은 시스템이 사용자 정의 동등성 관계를 가진 형식에 정의된 기능이 그 동등성에 대해 잘 정의되어 있는지 검증하지 않기 때문이다. 따라서 참조 투명성은 동등성 관계가 없는 유형으로 제한된다. 참조 투명성을 사용자 정의 동등성 관계까지 확장하는 것은 예를 들어 Martin-Lof ID 유형으로 수행할 수 있지만, 아그다, Coq 또는 Idris와 같이 의존적으로 입력된 시스템이 필요하다.
명령형 프로그래밍과 대비
표현식을 그 값으로 대체하는 것이 프로그램 실행의 특정 지점에서만 유효하다면 그 표현은 참조적으로 투명하지 않다. 이러한 시퀀스 포인트의 정의와 순서는 명령 프로그래밍의 이론적 토대가 되며 명령 프로그래밍 언어의 의미론적 일부가 된다.
그러나 참조적으로 투명한 표현은 언제든지 평가할 수 있기 때문에 시퀀스 포인트를 정의하거나 평가 순서에 대한 보증을 전혀 할 필요가 없다. 이러한 고려 없이 수행되는 프로그래밍을 순기능 프로그래밍이라고 한다.
참조 투명 스타일로 코드를 작성할 때의 한 가지 장점은 지능형 컴파일러를 사용할 경우 정적 코드 분석이 더 쉽고 코드 개선 변환이 자동으로 가능하다는 것이다. 예를 들어, C에서 프로그래밍할 때, 프로그램의 결과를 변경하지 않고 기능 호출을 루프 외부로 이동시킬 수 있더라도, 루프 내부에 고가의 함수에 대한 호출을 포함하는 것에 대한 성능 벌칙이 있다. 프로그래머는 소스코드 가독성을 희생시키면서 통화의 수동 코드 동작을 수행하도록 강요될 것이다. 그러나 컴파일러가 함수 호출이 참조적으로 투명하다고 판단할 수 있는 경우, 이 변환을 자동으로 수행할 수 있다.
참조 투명성을 강제하는 언어의 주요 단점은 단계별 명령형 프로그래밍 스타일에 자연스럽게 맞는 운영 표현을 보다 어색하고 간결하지 않게 만든다는 것이다. 그러한 언어들은 종종 명확한 조항 문법이나 모노드와 같은 언어의 순기능적 품질을 유지하면서 이러한 작업을 쉽게 하기 위한 메커니즘을 포함한다.
다른 예
예를 들어, 두 가지 기능을 사용하자. 하나는 참조적으로 투명하고 다른 하나는 참조적으로 불투명하다.
인트로 g = 0; 인트로 rt(인트로 x) { 돌아오다 x + 1; } 인트로 로(인트로 x) { g++; 돌아오다 x + g; } 함수 rt 참조적으로 투명하다. 즉, 다음과 같은 경우 x == y 그때 rt(x) == rt(y)예를 들어, rt(6) = 7그러나, 우리는 그런 말을 할 수 없다. ro 왜냐하면 수정하는 글로벌 변수를 사용하기 때문이다.
참조 불투명도 ro 프로그램에 대한 추론을 더 어렵게 만든다. 예를 들어, 다음과 같은 문장에 대해 추론하고 싶다고 하자.
인트로 i = 로(x) + 로(y) * (로(x) - 로(x)); 이 진술을 단순화하여 다음과 같은 목적을 달성하고자 할 수 있다.
인트로 i = 로(x) + 로(y) * 0; 인트로 i = 로(x) + 0; 인트로 i = 로(x); 하지만, 이것은 효과가 없을 것이다. ro 의 각 발생 때문에 ro(x) 다른 값으로 평가하다 다음 반환 값 ro 전달되지 않고 각 통화에 대해 수정되는 글로벌 값을 기반으로 함 rox - x = 0과 같은 수학 정체성이 더 이상 유지되지 않는다는 뜻이다.
그러한 수학적 정체성은 다음과 같은 참조적으로 투명한 함수를 지탱할 것이다. rt.
그러나 보다 정교한 분석을 사용하여 다음과 같은 문구를 단순화할 수 있다.
인트로 tmp = g; 인트로 i = x + tmp + 1 + (y + tmp + 2) * (x + tmp + 3 - (x + tmp + 4)); g = g + 4; 인트로 tmp = g; 인트로 i = x + tmp + 1 + (y + tmp + 2) * (x + tmp + 3 - x - tmp - 4)); g = g + 4; 인트로 tmp = g; 인트로 i = x + tmp + 1 + (y + tmp + 2) * (-1); g = g + 4; 인트로 tmp = g; 인트로 i = x + tmp + 1 - y - tmp - 2; g = g + 4; 인트로 i = x - y - 1; g = g + 4; 이것은 더 많은 단계를 필요로 하고 컴파일러 최적화에 불가능한 코드에 대한 어느 정도의 통찰력을 필요로 한다.
그러므로 참조 투명성은 우리의 코드에 대해 추론할 수 있게 해주며, 이는 보다 강력한 프로그램으로 이어질 것이며, 테스트를 통해 우리가 찾기를 기대할 수 없었던 버그를 발견할 수 있는 가능성, 그리고 최적화의 기회를 볼 수 있는 가능성을 가능하게 한다.
참고 항목
참조
- ^ John C. Mitchell (2002). Concepts in Programming Languages. Cambridge University Press. p. 78.
- ^ Alfred North Whitehead; Bertrand Russell (1927). Principia Mathematica. 1 (2nd ed.). Cambridge University Press. 여기: p.665. Quine에 따르면, 그 용어는 거기서 유래되었다.
- Søndergaard, Harald; Sestoft, Peter (1990). "Referential transparency, definiteness and unfoldability" (PDF). Acta Informatica. 27 (6): 505–517. doi:10.1007/bf00277387. S2CID 15806063.
- Davie, Antony (1992). An Introduction to Functional Programming Systems Using Haskell. New York: Cambridge University Press. p. 290. ISBN 0-521-27724-8.
