재귀와 비종료가 질의 언어에 들어올 때 평가 순서가 의미론, 종료성, 최적화에 어떤 긴장을 만드는지, 그리고 가능한 세 가지 방향을 살펴본다.
2026년 6월
지난달 나는 FLOPS에서 유한 함수형 프로그래밍, 즉 ‘λFS’에 관한 발표를 했다. 이것은 함수형 프로그래밍과 Datalog 또는 SQL 스타일의 관계형 프로그래밍을 결합하려는 나의 최신 시도이며(이전 시도: Datafun), 덤으로 텐서 대수도 포함한다. 왜 안 되겠는가?
λFS에서 관계 R은 함수로 취급된다. 즉, _x_가 R에 속할 때 그리고 그럴 때에만 R(x) = true이고, 그렇지 않으면 false이다. 이 함수는 오직 유한하게 많은 입력 _x_에 대해서만 R(x) = true라는 의미에서 유한 하다. 이 입력들이 그 지지집합 이다.논문에서는 함수가 유한한 지지집합을 갖도록 보장하는 타입 시스템을 제시한다. 런타임에서는 유한한 불 함수는 그 지지집합을 해시 테이블이나 균형 트리(데이터베이스의 테이블과 같은 것)에 표로 저장하여 표현한다.
이것은 불 값을 넘어 ‘기본값’을 갖는 임의의 공역으로 일반화된다. 함수의 지지집합은 출력이 기본값이 아닌 입력들이다. 예를 들어, 기본값이 false인 불 값이나, 기본값이 0인 정수가 있다. 그러면 유한 함수는 키가 함수의 지지집합인 키-값 테이블로 표현할 수 있다. 다른 모든 키는 암묵적으로 기본값에 대응된다. 불이 아닌 유한 맵은 집계의 결과로 자연스럽게 나타나며, 텐서 대수는 본질적으로 불이 아닌(대개 실수값인) 유한 맵에 대한 관계 대수이다.
발표에서 나는 재귀가 λFS의 미래 과제라고 언급했다. 당연히 누군가가—아마 Atsushi Igarashi였던 것 같다—어려움이 무엇인지 물었다. 가장 큰 어려움은 재귀가 비종료를 허용한다는 점이다. 비종료의 의미론은 보통 도메인 이론을 사용한다. 그런데 이것은 최근 수십 년 동안 유행에서 멀어졌고, 그 결과 나는 깊이 공부해 본 적이 없어서 다소 위압적으로 느낀다.1
더구나 비종료나 어떤 효과든 개입하는 순간, 평가 순서라는 문제가 생긴다. 비형식 람다 계산법에서도 평가가 합류적이지만, 이름에 의한 호출과 값에 의한 호출은 서로 다른 프로그램에서 종료한다. 더 나쁜 점은 관계형 언어에서 ‘평가 순서’는 함수형 언어에서보다 더 넓은 의미를 가진다는 것이다. 다음 예를 보자.
GivenR,S : nat => bool입력 테이블
andtest : nat -> bool블랙박스 술어
letQ(x) := R(x) and test(x) and S(x)질의
여기서 =>는 테이블로 표현되는 유한 함수를 뜻하고, ->는 절차나 클로저로 표현되는 임의의 함수를 뜻한다. 관계적으로 생각하면, 질의 Q는 블랙박스 술어 test로 걸러진 테이블 R과 S의 교집합이다.
중심 질문은 이것이다. 이 질의를 어떤 순서로 평가하는가? 왼쪽에서 오른쪽으로 갈 수도 있다. R의 각 x에 대해, test(x)가 통과하면 x가 S에 있는지 확인한다. Python으로 쓰면 다음과 같다.
[x for x in R if test(x) if x in S]
또는 test가 비쌀 수 있지만 테이블에서 항목을 조회하는 것은 싸다는 점을 감안해, test를 호출하기 전에 x가 S에 있는지 먼저 확인할 수도 있다.
[x for x in R if x in S if test(x)]
그리고 S가 R보다 훨씬 작다는 것을 우연히 알고 있다면, R 대신 S를 순회함으로써 많은 시간을 절약할 수 있다.
[x for x in S if x in R if test(x)]
표준적인 관계형 철학에서는 평가 순서를 질의 계획기가 결정하는 구현 세부사항으로 본다. 그러나 이 순서는 Q의 종료 여부에 영향을 줄 수 있다. 서로 다른 순서가 test를 서로 다른 인자에 대해 호출하기 때문이다. 인위적인 예를 들면 다음과 같다.
R := {"hello", "world"}
S := {"hello", "alice"}
test(x) := x == "hello" or loop-forever()
Q(x) := R(x) and test(x) and S(x)
왼쪽에서 오른쪽으로 실행하면 test("hello")를 호출하고, 이것은 성공한 뒤 test("world")를 호출하는데, 이것은 영원히 반복된다. 하지만 test를 호출하기 전에 R과 S를 교집합하면, 우리는 "hello"만 검사하게 되므로 종료한다.
나는 이 문제를 λFS로 표현했지만, 사용자 정의 함수를 지원하는 모든 SQL 또는 Datalog 엔진에서 발생하며, 전형적인 DB와 PL의 가정 사이의 긴장을 드러낸다.
DB 질의 엔진은 성능 최적화를 위해 실행 전략을 선택할 수 있다.
PL 우리는 프로그램의 동작에 대해 합성적으로 추론할 수 있다. 특히 종료성이나 실행 시간에 대해서.
λFS는 DB와 PL을 잇는 다리가 되려 하지만, 어색한 중간 지점에 걸려 버린다. 나는 어느 한 관점을 다른 하나보다 우선해야 하거나, 아니면 이 바늘귀를 통과할 방법을 찾아야 한다. 아직 무엇이 최선인지 모르겠다. 대신 여기서는 앞으로 나아갈 세 방향, 즉 재귀를 가진 λFS(또는 비종료 함수를 가진 Datalog)에 대한 가능한 의미론의 세 가지 개요를 제시하겠다.
구현하기 가장 단순한 전략은 의미론도 가장 직관적이다. 왼쪽에서 오른쪽으로 평가하는 것이다. 이것은 가장 전형적인 PL 접근이다. 질의 계획을 피하고 그 책임을 전적으로 프로그래머의 손에 맡긴다. 그 결과 질의의 실행 시간을 예측하고 추론하기 쉬워진다. 내가 Finite Choice Logic Programming을 작업하던 중 친구 Rob Simmons가 내게 지적해 준 바와 같다. 이것은 대체로 FCLP의 구현인 Dusa의 비용 모델이기도 하다.
이 접근에서는 _n_개의 항으로 이루어진 논리곱이 최대 _n_개의 중첩 루프로 바뀐다. 예를 들어 R(x) and S(y)는 2개의 루프가 된다.
for x in R:
for y in S:
yield (x,y)
R(x) and S(x)처럼 S(x)의 변수들이 이미 완전히 구체화된 질의에서는 루프 대신 검사를 생성한다.
for x in R:
if x not in S: continue
yield x
논리곱의 변수들 중 일부만 구체화된 경우에는 인덱스가 필요하다. 예를 들어 R(x,y) and S(y,z)를 실행하려면 S를 y로 인덱싱하고 싶다.
for x,y in R:
for z in S_index[y]: -- 적절한 S_index가 있다고 가정
yield (x,y,z)
이러한 인덱스가 있고 모든 논리곱 항이 유한 맵의 적용이라면, 비용 모델은 단순하다. 접두 발화 횟수를 세면 된다. 즉, 논리곱의 각 접두사에 대해, 그 자유 변수를 만족시키는 할당의 수를 센다. 따라서 R(x,y) and S(y,z)에 대해서는 다음 둘을 더한다.
R(x,y)를 만족하는 x,y 튜플의 개수.R(x,y) and S(y,z)를 만족하는 x,y,z 튜플의 개수.그렇다면 test(x) 같은 블랙박스 술어는 어떨까? 이런 항에 대해서는 다음이 필요하다.
모든 인자가 앞선 논리곱 항들에 의해 구체화되어 있어야 한다. 그래야 거기에 도달했을 때 구체적인 값을 갖는다.
앞선 논리곱 항들이 발화할 때마다 test(x)를 평가하는 비용을 더한다. 이것은 전체 x 값의 개수를 초과할 수 있다. 예를 들어 R(x) and S(y) and test(x)는 각 x,y 쌍에 대해 한 번씩 test(x)를 호출한다.
이것은 종료성에 관한 원래 질문에도 바로 답을 준다. 우리는 술어를 정확히 그 술어보다 앞선 논리곱 항들을 만족하는 값들에 대해서만 실행한다. 완전히 우연하게도, 이 왼쪽에서 오른쪽 구체화 요구사항은 유한 함수형 프로그래밍 논문에 있는 타입 시스템과 정확히 일치한다. 나는 원래 이것을 타입 시스템의 약점으로 여겼지만, 왼쪽에서 오른쪽 실행 전략을 택하면 완전히 타당해진다.
나는 이 접근의 단순성과 예측 가능성을 좋아하며, 성능에 대한 책임을 프로그래머에게 지우는 방식으로 ‘정면 돌파’한다는 점도 마음에 든다(물론 이것은 분명 단점이기도 하다). 불행히도 몇몇 질의, 즉 순환적 질의에 대해서는 이것만으로는 만족스러운 성능을 달성하는 것이 불가능하다. 예를 들어 삼각형 질의 edge(x,y) and edge(y,z) and edge(x,z)가 그렇다.2
우리는 R(x) and test(x) and S(x)에 대해 그럴듯한 세 가지 평가 순서를 보았다. 굳이 하나로 제한할 필요가 있을까? 전형적인 DB 접근은 평가 순서를 명시하지 않음으로써 질의 계획기나 최적화기에 가능한 한 많은 재량을 주는 것이다. 이는 우리가 test를 정확히 어떤 값들에 대해 호출할지는 말할 수 없지만, 그 집합의 상한과 하한은 줄 수 있음을 뜻한다. 마찬가지로 프로그램의 종료성도 예/아니오의 문제가 아니라 예/아니오/어쩌면의 문제가 된다.
다시 예시 R(x) and test(x) and S(x)로 돌아가 보자. 우리는 어떤 x 값도 없이 test를 호출할 수는 없다. 우리가 가진 유일한 원천은 R과 S다. 따라서 어떤 질의 실행이든 test를 호출하는 값들은 많아야 R 또는 S에 있는 값들이고, 적어도 둘 다에 있는 값들이다. test(x)가 모든 에 대해 종료한다면 질의는 종료한다. test(x)가 어떤 에 대해 발산한다면 질의는 발산한다. 그 밖의 경우에는 어느 쪽이든 될 수 있다. 하지만 종료하는 모든 실행은 같은 결과를 내야 한다.
불행히도 나는 이 비결정성을 합성적인 방식으로 어떻게 명세해야 할지 모르겠다. 의미론에는 전형적으로 연산적 의미론과 지시적 의미론이라는 두 가지 접근이 있다.
연산적으로는, 바텀업 논리 프로그래밍에 대응하는 의미론을 어떻게 줄지조차 확신이 없다. 하물며 평가 순서의 변이를 포착하는 것은 더 어렵다. 특히 λFS에서는 유한 λ가 어떻게 평가되는가? 일반적인 절차적 λ는 인자에 적용될 때까지 축약을 기다리지만, 유한 함수의 핵심은 바로 그렇게 하지 않는다는 데 있다. 그것들은 데이터베이스 질의처럼 즉시 표로 계산된다. 그러나 이런 동작을 작은 단계 연산 의미론으로 포착하는 방법은 분명하지 않다. (Datafun에는 연산 의미론이 있기는 하지만, 그것은 모나드 내포를 사용하기 때문이고, 이 방식은 왼쪽에서 오른쪽 평가에 고정된다. 바로 내가 벗어나고 싶은 것이다!)
지시적으로는, 자연스러운 전진 방향은 유한 함수형 프로그래밍 논문에 개요가 제시된 지시적 의미론에 도메인 이론과 어떤 형태의 비결정성을 덧붙이는 것일 것이다. 불행히도 나는 아직 비결정성의 도메인 이론(powerdomain)에 충분히 익숙하지 않아서 이것을 어떻게 작동시켜야 할지 모르겠다.
여기에 적절한 접근을 안다고 생각하거나, 함께 작업해 보고 싶다면 이메일(qnrxunery@tznvy.pbz, rot13)로 연락해 주기 바란다.
케이크를 가지면서도 먹을 수 있다면 어떨까? 지금까지 나는 test(x)를 실행했을 때 그것이 발산하면 질의도 발산한다고 가정했다. 평가 순서가 중요한 이유는 이것이 어떤 x에 대해 test를 호출하는지를 바꾸기 때문이다. 우리가 조금 덜 순차적 으로 생각할 수 있다면 이 가정을 버릴 수 있다.
⊥가 발산을 나타낸다고 하자. and의 전형적인 구현은 순차적이다. 왼쪽 인자를 먼저 살피고, 그것이 false를 내면 단락 평가한다.
false and x = false -- 단락 평가; x를 평가하지 않음
true and x = x
⊥ and x = ⊥ -- x를 평가할 차례까지 가지 못한다.
이것은 보기 좋지 않다. 논리곱은 대칭적인데, 이 and는 왼쪽 편향적이다. 연속성을 유지하면서 대칭성을 복원해 보자.
false and x = false -- x를 더 평가할 필요가 없음
true and x = x
x and false = false -- x를 더 평가할 필요가 없음
x and true = x
나는 이것을 Plotkin의 parallel or에 비유하여 ‘병렬 and’라고 부른다.3 순차적 and는 항상 왼쪽 인자를 완전히 평가하지만, 병렬 and는 두 인자를 동시에 평가하고, 어느 하나가 false를 내거나 둘 다 true를 낼 때 종료한다. 이것은 놀랍게도 λFS에 결정성을 되돌려 준다. 앞의 예를 다시 보자.
R := {"hello", "world"}
S := {"hello", "alice"}
test x := (x == "hello") or loop-forever()
Q(x) := R(x) and test(x) and S(x)
왼쪽에서 오른쪽 실행은 test("world") and S("world") = ⊥ and false를 평가한다. 순차적 and에서는 이것이 발산하지만, 병렬 and에서는 단순히 false이다. R을 먼저 순회하든, S를 먼저 순회하든, 아니면 그 교집합을 먼저 순회하든 상관없이, 우리는 같은 직관적으로 올바른 답을 얻는다. 즉 Q = {"hello"}이다.
불행히도 병렬 and를 효율적으로 구현하는 방법은 분명하지 않다. 하지만 완전히 불가능해 보이지는 않는다. 예를 들어 miniKanren의 탐색 전략은 parallel-or의 구현과 비슷하며, Will Byrd에게 들은 바로는 Andorra Prolog도 병렬 and에 유사한 형태의 논리곱을 지원했다고 한다. 나 자신도 miniKanren 2025에 낸 논문에서 최악 경우 최적 조인의 구현을 위해 반복자 인터페이스를 사용한 공정 논리곱에 대해 다룬 적이 있다. 그래서 나는 이 문제가 해결 가능하리라고 의심한다. 하지만 그럴 가치가 있을까?4
일을 더 복잡하게 만드는 것은 재귀에 두 가지 서로 다른 종류가 있다는 점이다. (a) 재귀적 함수 는 지연적으로 계산된다. 함수 본문은 함수 적용이 요구될 때까지 평가되지 않는다. 그리고 (b) 재귀적 관계 (λFS에서는 유한 함수)는 바텀업 관계형 프로그래밍에서 고정점에 도달할 때까지 반복하여 eager하게 계산된다(빈 관계에서 시작해 정의를 반복 적용하고 안정화될 때까지 계속한다). 하지만 두 번째는 아마 첫 번째로 정의할 수 있을 것이다. 재귀만으로도 반복을 정의하기에 충분하다.↩
구체적으로, 어떤 큰 _n_에 대해 edge = {(1, x) : x ∈ [1..n]} ∪ {(x, 1) : x ∈ [1..n]} 라고 하자. 그러면 삼각형들(우리 질의의 답들)은 x, y, z 중 적어도 둘이 1이고 나머지 하나는 [1..n]의 아무 값이나 되는 그런 삼중쌍들이다. 따라서 그 개수는 3 n − 2 ∈ Θ(n)개이다. 하지만 접두사 edge(x,y) and edge(y,z)를 만족하는 삼중쌍은 Θ(n 2)개이다. 따라서 왼쪽에서 오른쪽 평가는 선형 개수의 결과를 찾기 위해 이차 작업을 수행한다. 더 일반적으로, 왼쪽에서 오른쪽 평가는 left-deep 이진 조인 계획에 대응하며, 순환적 질의에 대해서는 이진 조인 계획이 점근적으로 비효율적일 수 있다는 것이 알려져 있다. 순환적 질의는 최악 경우 최적 조인이 필요하다.↩
‘parallel or’는 Gordon Plotkin의 LCF Considered as a Programming Language(1977)에서 시작된 것으로 알고 있지만, 나는 이 강의 노트가 더 접근하기 쉬운 입문 자료라고 생각한다. 64쪽, §8.1, “Failure of full abstraction”을 보라.↩
또한 Meven Lennon-Bertrand와의 이 mastodon 토론도 보라. 그는 불 값에 대한 parallel or/and와 공정한 논리 프로그래밍의 논리합/논리곱 사이의 내 비유가 타당한지 매우 합리적으로 의문을 제기한다.↩