증분 계산 그래프는 바뀐 부분만 다시 계산한다

##

Yabu는 함수 정의를 바꿀 때 코드 재생성, 재컴파일, 타입 검사를 대화형 속도로 처리하기 위해 증분 계산 그래프를 활용한다. 이 글은 Salsa를 바탕으로 한 계산 캐시와 무효화 방식이 어떻게 작동하는지 설명한다.

Yabu 작업의 일부로 이 방식을 익혔다. Yabu에서는 재컴파일, 코드 재생성, 타입 검사를 대화형 속도로 해야 한다. 구현은 Salsa를 기반으로 한다.

알고리즘에는 크게 두 가지 요소가 있다. 입력은 바뀔 수 있고 외부에서 발생하는 변화의 유일한 원천이다. 시스템은 입력을 설정한 뒤 계산을 수행한다. 계산은 입력이나 다른 계산만을 사용하는 순수 함수다. 계산 결과는 메모이제이션되며, 레드-그린 워크(red-green walk)를 통해 무효화된다.

Yabu에서 입력의 예로 함수 정의를 들 수 있다. 이미지를 만든 뒤 함수를 다시 정의한다고 하자. 함수의 소스 문자열이 입력이 되고, 여기에서 여러 순수 계산이 파생된다. 예를 들어 parse 계산은 소스 입력에 의존해 추상 구문 트리(AST)를 반환한다. 순수 함수이므로 입력이 바뀌지 않았다면 다시 파싱하지 않고 캐시된 AST를 반환할 수 있다.

(defun some-func ((a int) (b int)) int (+ a b))

(define-computation parse (source) (yabu:parse source))

계산을 조합하면 일반 함수 호출과 비슷해 보이지만, 각 계산은 내부적으로 어떤 계산을 호출하는지 추적한다. 이렇게 실행 중 의존 그래프가 만들어지고, 나중에 입력이 바뀌었을 때 어떤 계산을 무효화할지 판단하는 데 사용된다.

(define-computation compile (source) (let* ((typecheck-result (typecheck source))) (if (errorp typecheck-result) typecheck-result (yabu:compile ast))))

이 compile 함수는 Yabu에서 올바른 컴파일 함수가 아니다. 이 예에서는 해당 함수가 나머지 함수들을 고려해 타입 검사를 통과하는지만 확인하고, 나머지 함수들이 이 함수를 고려해 타입 검사를 통과하는지는 확인하지 않는다. 스테이징 시스템과 관련된 일부 복잡한 부분도 생략했다. 실제 알고리즘은 Yabu Incremental Typesystem에서 확인할 수 있다.

여기서 parse, typecheck, compile은 모두 계산이다. 실행 중 그래프에서 compile(source)는 typecheck에 의존하고, typecheck는 parse와 AST가 호출하는 모든 함수의 type-signature 계산에 의존할 수 있다.

compile(source) ----. | v parse(source) <------ typecheck(ast) | .------------------------+------------------------. v v v type-signature(f_1) type-signature(f_2) ... type-signature(f_N)

f_1의 타입 시그니처가 바뀌면 이 함수의 타입 검사 결과는 자동으로 무효화된다. 이런 무효화가 있어야 Yabu의 타입 검사기가 큰 프로그램에서도 대화형 사용에 적합한 속도를 낼 수 있다.

각 메모이제이션 항목에는 반환값, 메모이제이션이 마지막으로 유효하다고 확인된 리비전인 verified-at, 값이 마지막으로 바뀐 리비전인 changed-at, 그리고 의존성 목록이 저장된다. 예를 들어 위의 compile은 typecheck(source)에 의존한다. typecheck(source)는 parse(source)와 type-signature(f_1)..type-signature(f_N) 등에 의존한다. 각 의존성에 대해서도 해당 계산이 의존했을 당시의 changed-at 리비전을 추적한다.

some-func를 다시 정의한 뒤 (compile "<source>")를 호출하는 경우를 보자. 새 소스이므로 캐시가 없어 계산 함수를 실행한다. typecheck 역시 새 소스에 대한 항목이 없으므로 실행되고, 이는 아직 항목이 없는 parse에 의존한다. 그 결과 다음 메모이제이션 항목이 만들어진다.

(:key '(parse source) :return <ast> :verified-at :R7 :changed-at :R7 :dependency-list '((:input source)))

그다음 (-> (int int) int)인 +의 type-signature를 확인한다. 표준 라이브러리 항목이므로 세션 시작 때 :verified-at과 :changed-at이 R1로 설정돼 있다. R1은 R7보다 앞선 리비전이므로 이 항목이 오래됐을 수 있어 의존성을 확인해야 한다. (type-signature +)는 +의 소스에 의존하고, 그 소스의 리비전도 R1이다. 메모이제이션 항목과 의존성의 리비전이 같으므로 최신 상태로 판단하고, (type-signature +)의 :verified-at을 현재 리비전인 R7로 갱신한다.

타입 검사가 통과하면 결과도 메모이제이션하고 다음과 같은 항목을 만든다.

(:key '(typecheck source) :return <pass|fail> :verified-at :R7 :changed-at :R7 :dependency-list '((parse source) (type-signature +))')

계산을 최신 상태로 판단하는 조건은 :verified-at이 현재 리비전과 같거나, 의존성이 입력이고 그 :changed-at이 현재 리비전보다 이전인 경우다.

의존성 그래프를 따라 입력에 도달하거나, 해당 리비전에서 이미 하위 그래프를 검증한 곳에 이를 때까지 확인해야 한다. 그래프를 거슬러 올라오면서 :verified-at을 현재 리비전으로 갱신하면, 같은 리비전에서 해당 계산을 다시 확인할 때 하위 그래프 검사를 건너뛸 수 있다.

다음에 같은 소스를 대상으로 typecheck를 다시 계산하면 그래프를 따라가 입력에 도달해 변경 여부를 확인한다. 입력이 바뀌지 않았다면 계산 트리를 거슬러 올라오며 검증 리비전을 갱신하고, 타입 검사와 컴파일을 모두 건너뛴다.

— marce coll, 2026-04-23