배열과 함수 사이의 대응 관계가 언어 설계에 어떤 매력을 주는지, 그리고 Futhark가 타입·문법·의미 보장 측면에서 왜 이를 완전히 통합하지 않았는지를 살펴본다.
고성능 순수 함수형 데이터 병렬 배열 프로그래밍
2026년 1월 16일 게시
제가 어릴 때 Haskell 배열 문서를 처음 훑어보던 시절, 이 신비한 물건들이 대체 무엇인지에 대한 다음 설명을 보고 웃음이 나왔습니다:
Haskell은 인덱싱 가능한 배열을 제공하는데, 이는 정의역이 정수의 연속 부분집합과 동형(isomorphic)인 함수로 생각할 수 있다.
저는 이것이 흔한 자료구조를 두고 너무 웃길 정도로 난해하며 불필요하게 형식주의적인 설명이라고 생각했습니다. 하지만 이제는 나이가 들고 조금은 현명해졌고, 학계의 상아탑에 단단히 자리 잡은 지금, 이 설명을 보며 오히려 이것이 배열의 본질을 잘 잡아낸 훌륭한 정의라고 생각합니다! 그리고 이 문장이 이렇게 여러 해 동안 제 머릿속에 남아 있었다면, 더 산문적인 어떤 설명보다 훨씬 더 나은 문서였던 게 아닐까—라고 누가 부정할 수 있을까요?
언어 설계자의 입장에서 배열과 함수 사이의 대응 관계는(그것이 유용한 문서화 방식인지와 무관하게, 분명 존재합니다) 매혹적입니다. 왜냐하면 언어를 개선하는 가장 좋은 방법 중 하나가 언어를 더 작게 만드는 것이기 때문입니다. 물론 우리의 목표는 배열과 함수를 표현(representation) 차원에서 통합하는 것이 아닙니다. 실용적인 프로그래밍 언어에서 배열을 어떤 처치 인코딩(Church-encoding)으로 표현하는 것이 좋은 생각이라고 진지하게 주장할 사람은 없을 테니까요. 대신 고려해볼 만한 것은, 문법(syntax)이나 타입 수준에서 배열과 함수를 통합하면 어떤 결과가 생길 수 있는지, 그리고 왜 퓨사크는 결국 그렇게 하지 않았는지입니다.
먼저 참고할 만한 선행 작업이 있습니다. 배열 언어 K는 배열과 함수를 문법적으로 통합하는데, 둘 다 f[x] 표기법으로 인덱싱/적용하기 때문입니다. 하지만 대응 관계는 대체로 여기서 끝입니다. APL 계열 언어로서 K의 프로그래밍은 원소 단위(element-at-a-time) 프로그래밍이 아니라 전체 배열에 대한 벌크(bulk) 연산에 기반하며, 이러한 벌크 연산을 수행하는 연산자들은 함수에는 적용할 수 없습니다. 그리고 물론 K에는 타입 시스템이 없으므로, 그 대응은 순전히 문법적일 뿐입니다.
Dex는 이 채널에서 이전에 다룬 연구용 언어로, 배열-함수 대응 관계를 활용하긴 하지만 주로 개념적 수준에서 둘이 비슷하게 느껴지도록 하는 방식입니다. 출발점으로 Dex에서 a에서 b로 가는 함수는 관례적인 표기 a -> b를 쓰고, 인덱스 타입이 a이고 원소 타입이 b인 배열은 a => b로 씁니다. 여기서 a는 정수의 연속 부분집합과 동형인 타입이어야 하며, 따라서 Dex의 배열 타입은 미리 계산되어 효율적으로 표현된 함수로 진짜로 생각할 수 있습니다. 익명 함수는 \x->e로 쓰고, 배열은 for x.e로 구성합니다. 배열은 명시적 인덱싱을 사용하는 “pointed” 스타일로 변환되며, 이는 함수가 이름 붙은 매개변수로 정의되고 그 매개변수가 다른 함수에 전달되는 방식과 유사합니다.
흔한 함수 연산들 중 상당수는 배열에도 멋진 해석이 가능합니다. 예를 들어 커링/언커링은 배열의 언플래튼(unflattening)/플래튼(flattening)과 동등합니다. (a,b) -> c를 a -> b -> c로 커링하는 것이 사실 (a,b) => c에서 a => b => c로 가는 것과 같다는 점을 생각해 보세요. 부분 적용(partial application)은 어떤 차원을 고정하는 것과 같습니다. 함수의 매개변수 순서를 뒤집는 것은 배열을 전치(transpose)하는 것과 같습니다. 합성(composition)은 어떤 순열 배열(permutation array)을 다른 배열에 적용하는 것과 같습니다. 이런 사고방식이 공통 패턴을 인식하고 다른 방식으로 해석하도록 독려한다는 점이 제게는 매우 흥미롭습니다. 특히 Dex에서는 배열과 함수가 근본적으로 완전히 다른 타입이며, 공통 추상화로 함께 쓰기 위한 기능(예: 둘 모두에 동작하는 transpose 같은 함수)은 거의 제공되지 않습니다. 그럼에도 시사적인 문법과 _느낌_을 통해 프로그래머가 다른 방식으로 생각하도록 유도된다는 점이 흥미롭습니다.
이제 퓨사크에서 배열과 함수의 통합이 어느 정도까지 가능할지 생각해봅시다. 우선 타입 수준에서의 통합은 희망이 없습니다. 효율적인 디펑셔널라이제이션(defunctionalisation)을 가능하게 하려면, 퓨사크는 함수 사용 방식에 제약을 둡니다. 예를 들어 분기(branch)에서 함수를 반환하는 것을 금지합니다. 이런 제약은 배열에는 적용되지 않고(또 적용되면 안 됩니다!), 따라서 통합은 불가능합니다. 또한 퓨사크에서 [n]f64 같은 배열 타입은 크기(그에 따른 유효 인덱스) 를 명시적으로 나타내며, 이는 런타임에조차 추출할 수 있습니다. 함수에는 이런 것이 불가능하며, 가능하게 만들려면 의존 타입(dependent types)에 더 가까이 가야 합니다—물론 그게 어쨌든 좋은 생각일 수도 있지만요.
이제 문법으로 넘어가 봅시다. a[i]를 a i로 바꾸는 것은 크게 어려운 일은 아닐 것입니다. 제겐 낯설어 보이지만, 표기법의 변화는 어떤 것이든 처음엔 낯설어 보이기 마련이니 크게 집착할 문제는 아닙니다. 진짜 도전 과제는 슬라이싱(slicing) 입니다. 퓨사크는 꽤 전통적인 파이썬풍의 배열 슬라이스 표기법 a[i:j]를 지원합니다. 이는 함수 적용 문법과 그렇게 간단히 대응되지는 않습니다. 한 가지 해결책은, 배열을 단일 인덱스가 아니라 전체 인덱스 배열 에 적용할 수 있도록 허용해서 같은 모양(shape)의 배열을 결과로 얻는 것입니다. 즉 적용 a [i, j, k]는 [a[i], a[j], a[k]]와 동등합니다. 퓨사크에는 이미 구간(range)을 구성하는 괜찮은 표기법이 있으므로, 이렇게 하면 슬라이스 a[i:k]를 a(i..<k)로 쓸 수 있습니다(괄호는 순전히 우선순위 때문입니다). 물론 기존의 대괄호 문법을 그대로 두고, i가 배열일 때도 a[i]를 허용하는 방식으로도 가능하겠지요.
연산적 보장(operational guarantees)은 조금 더 다루기 어렵습니다. 현재 슬라이싱은 본질적으로 배열 메타데이터만 조작하는, 사실상 공짜에 가까운 연산임이 보장됩니다. 하지만 임의의 인덱싱 배열로 슬라이스하는 경우에는 이런 보장이 불가능합니다. 인덱스에 표현 가능한 패턴이 없을 수도 있고, 중복이 있을 수도 있으며, 임의의 구멍(hole)이 있을 수도 있습니다—사실상 필터링(filtering)과 확장(expansion)을 완전히 일반화한 것이 됩니다. 컴파일러는 표준 슬라이스에 해당하는 효율적인 경우를 탐지하고 활용하기 위해 상당한 작업을 해야 할 것입니다. 그러나 이런 식으로 프로그래머 의도를 역으로 추론하려는 접근은 퓨사크 철학과는 상충합니다. 우리는 프로그래머가 실제로 명시한 것 을 활용하고 싶지, 그들이 의미했을지도 모르는 것 을 줄 사이에서 읽어내고 싶지는 않습니다.
퓨사크가 이 실험을 하기에 적절한 언어라고는 생각하지 않지만, 배열-함수 대응 관계를 완전히 활용하는 언어가 어떤 모습일지는 보고 싶습니다. 다만 이를 위한 최선의 방법이 타입을 하나만 두는 것이라고는 생각하지 않습니다. 표현 방식을 어떻게 선택하느냐가 성능에 미치는 영향이 너무 극적이어서 컴파일러에만 맡겨두기 어렵기 때문입니다. 대신 저는 배열과 적절한 함수 모두에 대해 동작하는 공유 추상화를 허용하는 언어를 상상합니다. 출발점 하나는 a -> b와 배열 타입 a => b가 둘 다(원소 타입 b를 갖는) Haskell 의미에서의 펑터(functor)라는 관찰입니다. 즉 “펑터적 맵(functorial map)” 연산(fmap)을 지원합니다. 함수의 매개변수 타입이 정수의 연속 부분집합과 동형이라면 스캔과 리덕션 연산도 정의하기 쉽습니다. 그러면 “배열 같은(array-like)” 어떤 것이든 처리하는 함수를 정의하기 시작할 수 있습니다. 또한 AUTOMAP 뒤에 있는 아이디어를 “AUTOFMAP”으로 확장해, 정의역이 같은 함수 f와 g에 대해 f + g 같은 연산을 허용할 수도 있을 것입니다. 이는 일반적인 수학적 관례를 반영합니다. 다른 일들도 가능해집니다—함수에 대한 행렬 곱(matrix multiplication)이 언제 유용할지는 아직 모르겠지만, 누군가 그걸 알아내서 제게 알려줬으면 좋겠습니다.
