if는 위로, for는 아래로: 관용 패턴과 그 대수, 그리고 한계

조건 분기는 호출자에, 반복문은 배치 처리 함수 내부에배치하면 제어 흐름을 중앙화하고 핵심 처리 로직을 단순화할 수 있음- 호출자가
None

을 처리하고 함수가Option<Walrus>

대신, 입력 타입이 사전 조건을 드러내며 내부에서 고려할 상태가 줄어듦Walrus

를 받게 하면 - 데이터베이스의
선택/투영 조기 실행과벡터화 실행도 유사한 구조를 가짐: 조인 입력을 줄이고, 행마다 지불하던 호출 비용을 배치 단위로 나눔 filter

를map

앞으로 옮길 때는술어도 함께 변환해야 하며, 실제 계산 절감은 변환된 술어p. f

를 저렴한 입력 술어로 단순화할 수 있을 때 가능함대수적 법칙과 적용 조건이 변환의 정당성을 결정함: 루프 불변 조건만 반복문 밖으로 꺼낼 수 있으며, 반복을 배치 함수 안으로 옮기는 일은 동치성보다 비용 구조에 초점이 있음

조건은 호출자에, 반복은 배치 함수 안에

• TigerBeetle의 Tiger Style은 큰 함수를 분리할 때
  제어 흐름을 부모 함수에 중앙화하고, 분기가 없는 로직을 보조 함수로 옮기도록 권장함- 부모 함수가
  switch

/if

를 담당하고 나머지 함수는 제어 흐름을 신경 쓰지 않도록 책임을 나눔

• 부모 함수가
• matklad의 글에서 조건을 위로 올리는 예는
  frobnicate(walrus: Option<Walrus>)

의None

처리를호출자로 이동하는 것임- 핵심 함수는 일반
Walrus

만 받으므로 타입이 사전 조건을 명시하고 입력 상태 공간이 좁아짐 - 핵심은 하류로 흐르는 데이터의 양이 아니라
판단을 어디에서 수행하느냐에 있음

• 핵심 함수는 일반
• 반복을 아래로 내리는 방식은 호출자가
  frobnicate(walrus)

를 반복 호출하는 대신를 호출하고, 그 안에 반복문을 두는 것임frobnicate_batch(walruses)

• 필터링이나 데이터 축소 이후 반복을 수행하면 불필요한 계산을 줄일 수 있음

• 핵심 반복문에서 분기를 없애면
  벡터화의 후보가 됨

• 두 변환을 결합하면 호출자가
  Vec<Option<Walrus>>

에서None

을 버리고 값을 꺼내를 만든 뒤 배치 함수에 전달함Vec<Walrus>

into_iter().filter_map(|w| w).collect()

로 입력을 정리하면frobnicate_batch(&walruses)

는None

을 고려할 필요가 없음

데이터베이스: 선택/투영은 일찍, 조인은 나중에

• 쿼리 최적화에서도
  선택과 투영을 먼저 실행하고 조인처럼 데이터를 결합하거나 확장하는 연산을 뒤로 미루는 원리가 나타남- 다만 쿼리 계획 트리는 잎이 테이블 스캔이고 루트가 결과를 생성하므로, 데이터는 아래에서 위로 흐름
• 따라서 데이터베이스의
  술어 푸시다운은 실행 시점을 앞당긴다는 뜻으로, 여기서 조건을 “위로” 옮긴다는 표현과 방향 용어가 반대임

투영은 필요한 열만 남겨 데이터의 폭을 줄이고,선택은WHERE

조건으로 불필요한 행을 걸러냄- 두 연산을 계획 트리에서 조인 아래로 옮기면 이후 연산으로 전달하는 데이터가 줄어듦

• 비용이 큰 조인은 쿼리 의미가 허용하는 범위에서 최대한 작은 입력을 처리하게 됨

• 반복문을 아래로 내리는 것에 대응하는 또 다른 사례는
  Volcano 방식에서 벡터화/배치 실행으로의 전환임- Volcano 방식은 행 단위로 처리하며 튜플마다 가상
  next()

를 통해 연산자를 호출함 - 배치 실행은 약 1,000개 튜플 묶음마다 연산자를 한 번 호출하고 내부에서 밀집된 반복문을 실행함

• 호출 오버헤드와 호출마다 필요한 판단 비용을
  배치당 한 번지불하며, 내부 반복문은 분기가 적고 캐시 친화적임

• Volcano 방식은 행 단위로 처리하며 튜플마다 가상

범주론: 부분대상으로 입력 제한하기

• 집합의 범주에서 술어
  p : A -> Bool

을 만족하는 원소는 부분집합를 이룸{a ∈ A | p a}

• 이 부분집합과 포함 사상
  {a | p a} ↪ A

가 함께**부분대상(subobject)**을 정의함 - 포함 사상은 단사 사상(monomorphism)이며, 집합의 범주에서는 단사 함수에 해당함

• 각 원소를 자기 자신으로 보내므로 서로 다른 입력은 서로 다른 출력으로 이어짐

• 이 부분집합과 포함 사상

• 조건을 위로 옮기기 전에는 피호출 함수가 임의의
  A

를 받아if p(a)

를 실행하지만, 옮긴 뒤에는호출자가 검사하고 피호출 함수는 조건을 만족하는 부분집합만 입력받음- 모든 입력이 이미 검사를 통과했으므로 내부
if

가 필요 없어짐 - 코드에서는
Option<Walrus>

대신Walrus

를 받는 식으로타입에 입력 제한을 기록함

• 모든 입력이 이미 검사를 통과했으므로 내부
• 범주론에서
  로 볼 수 있음Option<Walrus>

는 쌍대곱(coproduct)1 + Walrus

• 이 타입을 받아 분기하는 함수는 쌍대곱의 보편 성질에 따라 각 성분에 대응하는 두 함수와 같음
• 조건을 위로 올리면 이 두 역할을 분리하여 호출자는
  1

, 즉 값이 없는 경우를 처리하고 핵심 함수는Walrus

성분만 담당함

filter와 map: 순서를 바꾸는 정확한 법칙

“map 전에 filter”를 무조건 적용할 수는 없음

filter p (map f xs)

에서p

는f

의 출력인B

를 검사하므로 타입이B -> Bool

임 -
map f (filter p xs)

에서p

는 입력인A

를 검사하므로 타입이A -> Bool

임 -
두 식을 연결하는 올바른 법칙은

임filter p . map f == map f . filter (p . f)

이 법칙은

**매개변수성(parametricity)**에서 따르며,filter

를Maybe

를 거치는 연산으로 분해하면 관계가 드러남keep :: (a -> Bool) -> a -> Maybe a keep p x = if p x then Just x else Nothing filter p = catMaybes . map (keep p)

:filter p

자체는 자연 변환이 아님p

가 원소 타입을 고정하므로 자연성 사각형을 구성할 수 없음 -
반면

는 자연 변환이며,catMaybes :: [Maybe a] -> [a]

map g . catMaybes == catMaybes . map (fmap g)

가 성립함 -
keep p . f == fmap f . keep (p . f)

와을 이용하면 다음과 같이 변환할 수 있음catMaybes

의 자연성filter p . map f == catMaybes . map (keep p) . map f == catMaybes . map (keep p . f) == catMaybes . map (fmap f . keep (p . f)) == catMaybes . map (fmap f) . map (keep (p . f)) == map f . catMaybes . map (keep (p . f)) == map f . filter (p . f)

동치인 변환이 반드시 더 저렴하지는 않음

하므로, 올바른 변환이라고 해서 자동으로 비용이 줄지는 않음filter (p . f)

도 검사할 때 모든 원소에f

를 계산- 비용 절감은
할 수 있을 때 발생함p . f

를 입력에 대한 저렴한 술어q

로 단순화- 일반적으로
p

가 검사하는 값의 부분을f

가 변경하지 않는 경우에 가능함 - 이때
filter p . map f == map f . filter q

가 성립하고,f

는 필터를 통과한 원소에만 실행됨

• 일반적으로
• 양쪽 모두
  O(n) 단일 순회이며, 절약하는 것은 어차피 버릴 원소에 대한f

호출임

적용 조건과 비용 구조의 한계

반복문 밖으로 조건을 꺼내는 변환은 조건이 루프 불변일 때 유효함- 원소별 조건은 반복문 자체를 벗어날 수 없으며, 경계로 옮긴 뒤
Option<Walrus>

대신Walrus

처럼 타입에 검사 결과를 기록할 수 있음

• 원소별 조건은 반복문 자체를 벗어날 수 없으며, 경계로 옮긴 뒤
  선택을 조인 아래로 내리는 변환은 술어가 조인 한쪽의 열만 참조할 때 유효함필터를 매핑 앞으로 옮기는 변환에는p

를p . f

로 바꾸는 법칙이 필요하며, 계산 절감에는 이를 저렴한 입력 술어로 단순화할 수 있다는 추가 조건이 필요함대수는 어떤 재작성이 적법한지 결정함filter

/map

사례에서는catMaybes

의 자연성이 변환의 정당성을 뒷받침하며 코드 전체 구조를 추론할 수 있게 함- 이런 일반 원리는 코드베이스나 시스템의 구조를 개선하는 데 도움을 주지만, 구성 요소 전반에서 필요한 조건이 유지되어야 함

반복을 아래로 내리는 일은 동치성보다 비용의 문제임- 함수의 형태를
A -> B

에서[A] -> [B]

로 바꿔 초기 설정 비용을 배치당 한 번 지불하도록 함

• 함수의 형태를