모든 계산 모델은 '정적 단일 할당'에 도달

포엠입니다.

TL;DR

정적 단일 대입 형식을 「루프까지」확장하면 매우 강력해졌어!

정적 단일 할당이란?

자세한 설명은 Wikipedia에 양보합니다. JavaScript로 말하면 모든 것이 const로 표현되는 것 같습니다.

그런데 이 정적 단일 대입, 이대로는 부분적인 최적화에 이용되는 정도일 뿐입니다만, 이것을 루프까지 확장해, 모든 프로그램을 표현할 수 있으면 매우 좋은 것은 아닐까. 라는 것이 본고의 내용입니다.

아래의 의사 코드를 참조하세요.

sum = 0
for x in xs {
  sum = sum + x
}

이것은 sum 변수를 덮어 쓰면서 루프를 돌리는 일반적인 절차 언어의 코드입니다.

이에 대해, sum 를 덧쓰기하지 않는 다음의 의사 코드를 생각합니다.

for sum from 0; x in xs {
  sum = last sum + x
}

last sum 부분에 주목하십시오. 여기서 last sum는 이전 루프의 동명 변수를 나타냅니다. sum 에는 한 번의 루프로 한 번밖에 대입할 수 없습니다. 각 루프의 sum 는 어디까지나 다른 변수이며, last 를 사용해 다른 (전의) 루프에서의 값을 참조할 수 있습니다.

이제 맑고 정적 단일 할당 규칙 "각 변수가 한 번만 할당됨"을 지키면서 루프까지 확장 할 수있었습니다.

어떻게 기쁜지

앞의 sum 예제에서는 각 루프가 이전 루프의 계산 결과를 기다리지 않으면 이 루프에서 계산할 수 없다는 것이 명확하게 나타났습니다. 그림으로 하면 이런 형태입니다.



한편, 이전 루프의 계산 결과에 의존하지 않는 것도 명확하게 나타낼 수 있습니다.

for x in xs {
  y = x * 2
}

last 연산자를 사용하지 않으므로 각 루프는 완전히 독립적으로 계산할 수 있습니다.


기쁜 것은 병렬화를 하기 쉬운 점입니다 (예를 들어, SIMD 명령 와 같은). 이 속성은 루프에만 국한되지 않습니다. 다음 의사 코드를 생각해 봅시다.

a = 2 * 2
b = 3 * 3
c = a + b

c 를 구하려면 a 와 b 가 필요하지만 a 와 b 는 서로 독립적으로 계산할 수 있습니다. 즉, 병렬로 실행할 수 있습니다.

이것은 위에서 설명한 간단한 계산뿐만 아니라 매우 무거운 계산에서도 마찬가지입니다. I/O 등 긴 대기가 발생하는 처리를.

정적 단일 할당의 본래 목적이 그렇듯이 이 형식에 따라 프로그램을 작성하면 다양한 최적화의 이점을 얻을 수 있습니다.

필자는 이 정적 단일 대입 형식의 확장이야말로 다양한 계산 모델 중에서 가장 적절하게 추상화된 형태가 아닐까 생각하고 있습니다.

졸린 문장입니다만, 이상이 이번에 쓰고 싶었던 포엠이 됩니다. 당연히 현명한 독자의 분들에게는 츳코미 커녕이 다수 있다고 생각합니다. 부디 코멘트란에서 논의를 나누지 않겠습니까? 언제까지 기다리고 있습니다.