영문 위키피디아 번역

(번역) Idempotence

다움위키 2024. 2. 20. 16:53
Original article: w:Idempotence

 

거듭-상등(Idempotence) (UK: /ˌɪdɛmˈpoʊtəns/, US: /ˌaɪdəm-/)는 수학(mathematics) 및 컴퓨터 과학(computer science)에서 특정 연산(operations)의 속성이며 그것에 의하여 그것은 초기 적용을 지나서 결과를 변경없이 여러 번 적용될 수 있습니다. 거듭상등의 개념은 추상적 대수학(abstract algebra) (특히, 투영기(projector) 및 닫힘 연산자(closure operator)의 이론에서)과 함수형 프로그래밍(functional programming) (이것에서 참조 투명성(referential transparency)의 속성에 연결됨)에서 여러 곳에서 발생합니다.

그 용어는 양의 정수 거듭제곱이 올려졌을 때 불변으로 남는 대수학의 원소의 문맥에서 벤저민 퍼스(Benjamin Peirce)에 의해 도입되었고, 말-그대로 idem + potence (같은 + 거듭제곱)으로부터 "같은 거듭제곱(을 가지는 양)"을 의미합니다.

Definition

마그마(magma) (M, •)의 원소 x는 만약 다음이면 거듭-상등이라고 말합니다:

\(\quad x \cdot x = x\)

만약 모든 원소가 •에 관해 거듭-상등이면, •는 거듭-상등이라고 불립니다. 공식 ∀x, x • x = x는 •에 대해 거듭-상등 법칙이라고 불립니다.

Examples

Idempotent functions

함수 합성(function composition) ∘을 갖는 집합 E에서 자체로의 함수(functions)의 모노이드 \((E^E, \circ)\)에서, 거듭-상등 원소는 f ∘ f = f를 만족하는, 다른 말로 E에서 모든 x에 대해, f(f(x)) = f(x) (E에서 각각의 원소는 f의 고정된 점(fixed point)임)을 만족하는 함수 f: E → E입니다. 예를 들어:

  • 정수 x의 절댓값(absolute value) abs(x)는 다음 이유에 대해 거듭-상등 함수입니다: abs(abs(x)) = abs(x)는 각 정수 x에 대해 참입니다. 이것은 abs ∘ abs = abs가 유지됨을 의미합니다. 즉, abs는 함수 합성에 관한 모든 (정수에서 정수로의) 함수의 집합에서 거듭-상등 원소입니다. 그러므로, abs는 거듭-상등 함수의 위의 정의를 만족시킵니다.

다른 예제는 다음을 포함합니다:

만약 집합 E가 n 원소를 가지면, 우리는 그것을 f 아래에서 k 선택된 고정된 점과 n − k 비-고정된 점으로 분할하면, \(k^{n-k}\)가 다른 거듭-상등 함수의 숫자입니다. 따라서, 모든 가능한 분할을 고려할 때,

\(\quad\displaystyle \sum_{k=0}^n {n \choose k} k^{n-k}\)

은 집합에서 가능한 거듭-상등 함수의 전체 숫자입니다. n = 0, 1, 2, 3, 4, 5, 6, 7, 8, …에 대해 위의 합에 의해 주어질 때 거듭-상등 함수의 숫자의 정수 수열(integer sequence)은 1, 1, 3, 10, 41, 196, 1057, 6322, 41393, … (OEIS에서 수열 A000248)로 시작합니다.

거듭-상등인 것의 속성과 그렇지 않은 것의 속성이 함수 합성 아래에서 보존됩니다. 전자에 대해 예제로서, f(x) = x 모드(mod) 3 및 g(x) = max(x, 5)은 둘 다 거듭-상등이지만, 비록 g ∘ f가 그런 것으로 발생할지라도, f ∘ g는 그렇지 않습니다. 후자에 대해 예제로서, 부울 도메인에서 부정 함수 ¬는 거듭-상등이 아니지만, ¬ ∘ ¬는 그렇습니다. 비슷하게, 실수의 단항 부정 −( )은 거듭-상등이 아니지만, −( ) ∘ −( )는 그렇습니다.

Computer science meaning

컴퓨터 과학(computer science)에서, 용어 idempotence는 그것이 적용되는 문맥에 따라 다른 의미를 가질 수 있습니다:

이것은 많은 상황에서 매우 유용한 속성인데, 왜냐하면 연산이 비-의도된 효과를 초래함없이 필요한 만큼 반복하거나 다시-시도될 수 있기 때문입니다. 비-거듭상등 연산과 함께, 알고리듬은 연산이 이미 수행되었는지 여부를 추적해야 할 수 있습니다.

Computer science examples

데이터베이스(database)에서 고객의 이름과 주소를 찾는 함수는 전형적으로 거듭-상등인데, 왜냐하면 이것이 데이터베이스를 변경하는 원인이 되어서는 안되기 때문입니다. 비슷하게, 고객의 주소를 XYZ로 변경하는 것은 전형적으로 거듭-상등인데, 왜냐하면 최종 주소는 XYZ를 제출한 횟수에 관계없이 같을 것이기 때문입니다. 어쨌든, 고객에 대해 장바구니에 주문을 넣는 것은 전형적으로 거듭-상등이 아닌데, 왜냐하면 전화를 여러 번 실행하면 여러 주문이 이루어지기 때문입니다. 주문의 취소는 거듭-상등인데, 왜냐하면 얼마나 많은 요청이 있더라도 취소된 상태를 유지하기 때문입니다.

거듭-상등 방법 또는 서브루틴의 합성은, 어쨌든, 만약 수열에서 나중 방법이 이전 방법이 의존하는 값을 바꾸면 반드시 거듭-상등일 필요는 없습니다 – 거듭-상등은 합성 아래에서 닫혀있지 않습니다. 예를 들어, 변수의 초기 값이 3이고 변수를 읽고, 그런-다음 그것을 5로 바꾸고, 그런-다음 그것을 다시 읽는 수열이 있다고 가정합니다. 수열의 각 단계는 거듭-상등입니다: 변수를 읽는 단계 둘 다는 이차 효과를 가지지 않고 변수를 5로 바꾸는 것은 실행 횟수에 관계없이 항상 같은 효과를 가집니다. 그럼에도 불구하고, 전체 수열을 한 번 실행하면 출력 (3, 5)가 생성되지만, 그것을 두 번째로 실행하면 출력 (5, 5)이 생성되므로, 수열은 거듭-상등이 아닙니다.

Hypertext Transfer Protocol (HTTP)에서, 거듭-상등과 안전(safety)은 HTTP 동사(HTTP verbs)를 구분하는 주요 속성입니다. 주요 HTTP 동사 중에서, GET, PUT 및 DELETE는 표준에 따라 거듭-상등 방식으로 구현되어야 하지만, POST는 그럴 필요없습니다. GET은 자원을 검색합니다; PUT은 리소스에 컨텐츠를 저장합니다; 그리고 DELETE는 자원을 제거합니다. 위의 예제에서처럼, 데이터를 읽는 것은 보통 이차 효과가 없으므로, 그것은 거듭-상등 (실제로 nullipotent)입니다. 컨텐츠의 주어진 집합을 저장하고 삭제하는 것은, 요청이 해당 리소스를 고유하게 식별하고 나중에 오직 해당 리소스를 다시 식별하는 위치 또는 식별자를 지정하는 한, 각각의 보통 거듭-상등입니다. 고유 식별자를 갖는 PUT 및 DELETE 연산은 각각 값 또는 널(null)-값의 불변 변수에 할당하는 간단한 경우로 감소하고, 같은 이유로 거듭-상등입니다; 마지막 결과는 심지어 응답이 다르더라도 항상 초기 실행의 결과와 같습니다.

저장 또는 삭제에서 고유한 식별 요구-사항의 위반은 전형적으로 거듭-상등의 위반의 원인이 됩니다. 예를 들어, 고유 식별자를 지정없이 주어진 컨텐츠의 집합을 저장 또는 삭제하는 것: 거듭-상등일 필요가 없는 POST 요청은 종종 고유 식별자를 포함하지 않으므로, 식별자의 생성은 수신 시스템에 위임되어 작성되며, 그런-다음 해당하는 새로운 레코드를 생성합니다. 비슷하게, 비-특정 기준과 함께 PUT 및 DELETE 요청은 시스템의 상태에 따라 다른 결과 – 예를 들어, 가장 최근 레코드를 삭제하려는 요청을 초래할 수 있습니다. 각각의 경우에서, 후속 실행은 시스템의 상태를 추가로 수정할 것이므로, 그들은 거듭-상등이 아닙니다.

이벤트 스트림 처리(Event stream processing)에서, 거듭-상등은, 심지어 같은 파일, 이벤트 또는 메시지가 한번보다 많이 수신되더라도, 같은 결과를 생성하기 위한 시스템의 능력을 참조합니다.

부하-저장 아키텍처(load-store architecture)에서, 페이지 오류(page fault)를 일으킬 수 있는 명령어는 거듭-상등입니다. 따라서 만약 페이지 오류가 발생하면, OS는 디스크에서 페이지를 로드할 수 있고 그런-다음 오류-발생된 명령어를 간단히 다시-실행할 수 있습니다. 이러한 명령어가 거듭-상등이 아닌 프로세서에서, 페이지 결함을 다루는 것은 훨씬 더 복잡합니다.

출력을 다시-포맷할 때, 프리티-인쇄(pretty-printing)는 거듭-상등이 있을 것으로 예상됩니다. 다시 말해, 만약 출력이 이미 "pretty"이면, 프리티-프린터에 대해 수행할 작업이 없어야 합니다.

서비스 지향 아키텍처(Service Oriented Architecture, 줄여서 SOA)에서, 전체적으로 거듭-상등의 단계로 구성된 여러-단계 오케스트레이션 과정은 만약 해당 과정의 임의의 일부가 실패하면 주변-효과없이 다시-실행될 수 있습니다.

Applied examples

일상 생활에서 많은 사람들이 접할 수 있는 적용된 예제는 엘리베이터(elevator) 호출 단추와 횡단-보도 단추(crosswalk button)를 포함합니다. 단추를 처음 활성화하면 요청이 만족될 때까지 시스템을 요청 상태로 옮깁니다. 만약 시스템이 활성화 횟수에 기초한 요청을 만족시키는 시간을 조정하도록 설계되지 않은 한, 초기 활성화와 만족시키게 될 요청 사이의 단추의 후속 활성화는 영향을 미치지 않습니다.

See also

Further reading