Categorical Foundations for CuTe Layouts

文章标题：CuTe Layout 的范畴论基础
作者/机构：Colfax Research

A1 主要贡献

核心问题

在现代计算，尤其是在 GPU 编程中，性能严重依赖于多维数据在内存中的存储和访问方式。尽管图像、视频和机器学习中的张量本质上是多维的，但计算机内存根本上是一维的。这意味着在加载、存储或操作数据时，需要将多维逻辑坐标映射到一维物理坐标。这种映射称为 Layout（布局），对于正确高效地读写内存至关重要。此外，在 GPU 的 SIMT 执行模型中，布局用于描述和操作数据上的线程分区，这对于优化内存访问模式和正确调用专用硬件指令（如张量核心指令）非常重要。

简单的行主序（row-major）和列主序（column-major）布局虽然常用，但不足以满足所有高性能计算的需求，例如矩阵乘法中常见的分块（tiling）计算。为了系统地管理分块操作，可以使用更复杂的布局，如交错布局（interleaved layout）。NVIDIA 的 CUTLASS 库提出，这些复杂的辅助布局可以通过一些基本操作（如逻辑除法、逻辑乘积、补集和组合）从更简单的布局中系统地推导出来。然而，这些操作的定义和构造相当微妙，例如，布局的组合 B ◦ A 仅在 A 和 B 满足某些可除性约束时才有效，这使得理解和使用这些操作变得不直观。

研究目标与创新点

本文的主要思想是，通过将注意力限制在易处理布局（tractable layouts）上，可以为处理布局开发一个直观且强大的数学框架。易处理布局的条目满足一个简单的可除性条件，并且涵盖了实践中遇到的大多数布局，例如行主序、列主序、紧凑布局、投影和扩张（dilation）等。

本文的核心创新点是利用范畴论来描述布局及其操作。作者将易处理布局表示为一个范畴中的态射（morphism）图。具体来说，本文定义了一个名为 Nest 的范畴，其对象是正整数的嵌套元组，其态射 f : S → T 对应于表示布局的图。如果 L 是一个易处理布局，则存在一个本质上唯一的 Nest-态射 f 来编码 L。本文的主要贡献总结如下：

• 定理 A (对应关系)：证明了易处理布局与 Nest 范畴中特定态射之间存在一一对应关系。
  

  

  
  例如，行主序、列主序和分块布局可以由以下图表示：
  

  

• 定理 B (组合)：证明了 Nest 范畴中的态射组合与布局的组合操作是兼容的。
  

  

  
  态射的组合通过拼接图来直观表示：
  

  

• 定理 C (合并)：证明了 Nest 范畴中态射的合并（coalesce）操作（通过折叠相邻箭头实现）与布局的合并操作是兼容的。
  

  

  
  合并操作示例：
  

  

• 定理 D (补集)：证明了 Nest 范畴中态射的补集（complement）操作（包含未被态射 f 命中的条目）与布局的补集操作是兼容的。
  

  

  
  补集操作示例：
  

  

• 定理 E (逻辑除法)：定义了 Nest-态射的可除性及逻辑除法操作，并证明其与布局的逻辑除法兼容。
  

  

  
  逻辑除法示例：
  

  

• 定理 F (逻辑乘积)：定义了 Nest-态射的乘积可容许性（product admissibility）及逻辑乘积操作，并证明其与布局的逻辑乘积兼容。
  

  

  
  逻辑乘积示例：
  

  

• 组合算法：提出了一种用于计算易处理布局 A 和 B 组合 B ◦ A 的算法。该算法的基本思想是将 A 和 B 表示为 Nest-态射 f 和 g，组合这些态射形成 g ◦ f，然后提取其编码的布局来获得 Layout(g ◦ f)。

• 实现：提供了一个 Python 实现（tract 模块），展示了该范畴论构造，并通过测试证明了其与 CUTLASS 的行为一致。

实现与环境

本文提供了一个范畴论框架的 Python 实现，形式为一个名为 tract 的模块，并展示了其与 NVIDIA 的 CuTe DSL（本文中称为 cute）的兼容性。该实现可在 https://github.com/ColfaxResearch/layout-categories 找到。

软件配置：
* 核心库：NVIDIA 的 CuTe DSL (cute)。
* 本文实现：一个名为 tract 的 Python 模块，实现了本文提出的范畴论框架。
* 功能：tract 模块提供了与 cute 中布局操作相对应的范畴论操作，并能在两者之间进行转换。

功能对齐展示：
* 元组构造：展示了如何在 Python 中构造简单元组和嵌套元组。
* Layout 与态射构造：
* 在 cute 中使用 cute.make_layout(shape=S, stride=D) 构造布局。
* 在 tract 中使用 tract.make_morphism(domain=S, codomain=T, map_=alpha) 构造嵌套元组态射。
* 布局与态射之间的翻译：
* tract.is_tractable(L)：检查 cute 布局 L 是否是易处理的。
* tract.compute_morphism(L)：将一个易处理的 cute 布局 L 转换为其标准表示的 tract 态射 fL。
* tract.compute_layout(f)：将一个 tract 态射 f 转换为其编码的 cute 布局 Lf。
* 核心操作的兼容性：通过并列代码示例，展示了 cute 和 tract 在以下核心操作上行为的一致性：
1. 组合 (Composition)：cute.composition(B, A) 对应 tract.compose(f, g)。
2. 合并 (Coalesce)：cute.coalesce(A) 对应 tract.coalesce(f)，包括相对合并。
3. 补集 (Complement)：cute.complement(A, N) 对应 tract.complement(f)。
4. 逻辑除法 (Logical Division)：cute.logical_divide(A, B) 对应 tract.logical_divide(f, g)。
5. 逻辑乘积 (Logical Product)：cute.logical_product(A, B) 对应 tract.logical_product(f, g)。

本文没有传统的数值实验，其“实验结果”体现在通过代码示例，系统地验证了其提出的范畴论框架（tract 模块）与现有高性能库（cute）在所有核心布局代数操作上的行为是一致的，从而证明了该框架的正确性和实用性。

A3 背景知识：布局及其代数

扁平布局 (Flat Layouts)

本节研究扁平布局，这是布局的一个重要子类，其中 shape 和 stride 都是元组，而非更一般的嵌套元组。

元组

• 元组定义：若 V 为一个集合，一个 V 中的元组是一个有限有序列表 X = (x1, ..., xm)，其中每个 xi ∈ V。元组 X 的长度为 len(X) = m。本文主要关注整数元组。整数元组 X 的大小为其所有元素的乘积，即 size(X) = Πxi。

• 元组示例：元组 X = (64, 32) 的长度为2，大小为2048。

• 元组拼接：两个元组 X = (x1, ..., xm) 和 Y = (y1, ..., yn) 的拼接记为 X ⋆ Y = (x1, ..., xm, y1, ..., yn)。

• 元组拼接是自由结合幺半群：对于集合 V，(Tuple(V), ⋆, ()) 是 V 上的自由结合幺半群，其幺半群乘积是拼接，单位元是空元组 ()。

• 元组的可除性：若存在整数元组 X'' 使得 X = X' ⋆ X''，则称整数元组 X' 整除 X。

• 元组的置换：若 X = (x1, ..., xm) 是一个元组，σ ∈ Σm 是一个置换，则 Xσ = (xσ(1), ..., xσ(m)) 表示 X 按 σ 进行置換。

• 坐标范围表示法：对于正整数 n，[0, n) 表示 {0, ..., n-1}。对于正整数元组 S = (s1, ..., sm)，[0, S) 表示所有满足 0 ≤ xi < si 的元组 (x1, ..., xm) 的集合。

基本定义

• 扁平布局定义：一个扁平布局是一个对 L = S : D，由一个正整数元组 S = (s1, ..., sm)（称为 L 的 shape）和一个非负整数元组 D = (d1, ..., dm)（称为 L 的 stride）组成。shape(L) 和 stride(L) 具有相同的长度。
  

  

  
  布局 L = (3, 5) : (2, 10) 可视化如下，其中单元格 (i, j) 的标签值为 φL(i, j) = 2i + 10j。
  

  

• 列主序与行主序布局：对于布局 L = (s1, ..., sm) : (d1, ..., dm)，如果 di = s1 · · · si-1 对每个 1 ≤ i ≤ m 成立，则称 L 是列主序的。如果 di = si+1 · · · sm 对每个 1 ≤ i ≤ m 成立，则称 L 是行主序的。
  例如，(4, 8) : (1, 4) 是列主序，而 (4, 8) : (8, 1) 是行主序。

• 扁平布局的属性：对于布局 L = (s1, ..., sm) : (d1, ..., dm)：

  • 秩 (rank)：rank(L) = m。
  • 大小 (size)：size(L) = s1 · · · sm。
  • 余大小 (cosize)：cosize(L) = Σ(si - 1)di + 1。
  • 模态 (mode)：第 i 个模态是 modei(L) = si : di。

• 坐标函数：对于扁平布局 L = S : D，其坐标函数 φL: [0, S) → Z 定义为 φL(x1, ..., xm) = Σ xi · di。该函数可因子化为 φcosize(L)L : [0, S) → [0, cosize(L))。

• Colexicographical 同构：对于正整数元组 S = (s1, ..., sm)，colexicographical 同构 colexS: [0, S) → [0, size(S)) 是一个映射，其逆映射 colex-1S 将一个整数 x ∈ [0, size(S)) 映射到一个元组 (x0, ..., xm-1)。

• 布局函数：对于扁平布局 L，其布局函数 ΦL 是坐标函数 φL 与 colex-1S 的复合：ΦL = φL ◦ colex-1S。ΦL 将一个一维索引 x ∈ [0, size(L)) 映射到一个一维物理偏移量。
  布局函数 ΦL 同样可以因子化为 Φcosize(L)L : [0, size(L)) → [0, cosize(L))。

• 列主序布局的布局函数：对于列主序布局 L，其布局函数 Φcosize(L)L 是 [0, size(L)) 上的恒等映射。

• 布局函数非唯一性：存在不同的布局 A != B 具有相同的布局函数 ΦA = ΦB。例如 A = (2, 1, 3) : (5, 100, 10) 和 B = (2, 3) : (5, 10)。

基本操作

限制 (Restrictions)

• 限制定义：对于扁平布局 L = (s1, ..., sm) : (d1, ..., dm) 和子集 I ⊂ <m>，L 对 I 的限制 L|I 是一个扁平布局，其 shape 和 stride 分别由 L 中索引在 I 内的元素构成。

压缩 (Squeeze)

• 压缩操作：对于一个扁平布局 L，squeeze(L) 操作移除所有 si = 1 的模态 si : di。这等价于将 L 限制到所有 si != 1 的索引集合上。

• 压缩不改变布局函数：对于任意扁平布局 L，size(squeeze(L)) = size(L)，cosize(squeeze(L)) = cosize(L)，且 Φsqueeze(L) = ΦL。

过滤零 (Filter zeros)

• 过滤零操作：该操作移除所有 di = 0 的模态 si : di。

置换 (Permute)

• 置换操作：对于秩为 m 的扁平布局 L = S : D 和置换 σ ∈ Σm，Lσ = Sσ : Dσ。

排序 (Sort)

• 排序定义：首先定义整数对 s:d 上的线性序：s1:d1 ⪯ s2:d2 当且仅当 d1 < d2 或 d1=d2 且 s1 ≤ s2。一个扁平布局 L 如果其模态 modei(L) 按此顺序非递减排列，则称其为已排序的。

• 排序与布局函数：如果布局函数 ΦL 是非递减的，则 L 是已排序的。反之不成立。

• 排序构造：对于任意扁平布局 L，可以找到一个置换 σ，使得 sort(L) = Lσ 是已排序的。

• 排序的影响：排序操作通常会改变布局函数，即 Φsort(L) != ΦL，但二者的值域（image）保持不变。

拼接 (Concatenate)

• 拼接定义：两个扁平布局 L1 = S1 : D1 和 L2 = S2 : D2 的拼接是 L1 ⋆ L2 = (S1 ⋆ S2) : (D1 ⋆ D2)。

• 拼接布局的布局函数：拼接布局 L1 ⋆ ... ⋆ Lk 的布局函数可以通过其各部分 Li 的布局函数来确定，具体来说，其坐标函数 φ 是各部分坐标函数 φLi 的和，其布局函数 Φ 则是通过 colex 同构将各 ΦLi 组合起来。

• 拼接布局的属性：拼接布局的秩、大小和余大小分别是各部分对应属性的和、积与和。

扁平合并 (Flat coalesce)

• 合并布局定义：一个扁平布局 L = (s1, ..., sm) : (d1, ..., dm) 被称为已合并的（coalesced），如果：1. 对所有 i，si != 1；2. 对所有 1 ≤ i < m，sidi != di+1。

• 合并操作：对于任意扁平布局 L，可以构造一个已合并的扁平布局 coal♭(L)，其与 L 具有相同的布局函数。该构造通过迭代地合并满足 di+1 = sidi 的相邻模态 (si, si+1) : (di, di+1) 为 (sisi+1) : (di)，并移除所有 si=1 的模态来实现。

• 合并的性质：coal♭(L) 是已合并的，并且 Φcoal♭(L) = ΦL。

• 布局函数等价性：两个扁平布局 A 和 B 具有相同的布局函数 ΦA = ΦB，当且仅当 coal♭(A) = coal♭(B)。

• 合并的唯一性：coal♭(L) 是具有 ΦL 的布局函数且秩最小的唯一扁平布局。

紧凑扁平布局 (Compact flat layouts)

• 紧凑布局定义：一个扁平布局 L 如果其布局函数 Φcosize(L)L 是一个同构（即双射），则称其为紧凑的。

• 紧凑布局的例子：所有列主序和行主序布局都是紧凑的。

• 紧凑布局的充要条件：一个扁平布局 L 是紧凑的，当且仅当存在一个置换 σ，使得 squeeze(L)σ 是列主序的。

• 紧凑性的等价条件：L 是紧凑的，当且仅当 coal♭(L)、squeeze(L) 或 sort(L) 是紧凑的。

补集 (Complements)

• 补集定义：如果拼接布局 L ⋆ L' 是紧凑的，则称扁平布局 L' 是 L 的一个补集。

• 补集的存在性：一个布局 L 要有补集，其布局函数 ΦL 必须是单射的，但这还不够。

• 补集非唯一性：补集不是唯一的。

• 可补性 (Complementable)：一个已排序的扁平布局 L = (s1, ..., sm) : (d1, ..., dm) 被称为可补的，如果对所有 1 ≤ i < m，sidi 整除 di+1。

• 可补性与补集存在性：一个扁平布局 L 存在补集 L'，当且仅当 sort(squeeze(L)) 是可补的。

• 标准补集构造：对于一个可补的布局 L，可以构造一个标准补集 comp♭(L)。

• N-补集：L' 是 L 的一个 N-补集，如果 L' 是 L 的补集且 size(L) · size(L') = N。

• N-可补性：一个已排序的扁平布局 L 被称为 N-可补的，如果它是可补的，并且 smdm 整除 N。

• N-补集的存在性：L 存在 N-补集，当且仅当 L 是 N-可补的。可以构造一个标准的 N-补集 comp♭(L, N)。

组合 (Composition)

• 组合定义：若扁平布局 R 满足 1. shape(A) = shape(R) 和 2. ΦR = ΦB ◦ Φsize(B)A，则称 R 是 A 和 B 的组合，记为 R = B ◦ A。这要求 cosize(A) ≤ size(B)。
• 组合不总存在于扁平布局中：两个扁平布局的组合结果可能不是一个扁平布局，而是一个嵌套布局。因此，详细讨论推迟到一般布局部分。

扁平除法 (Flat division)

• 扁平除法定义：假设 A 和 B 是扁平布局，且 B 是 size(A)-可补的。A 对 B 的扁平除法定义为 A ⊘♭ B = (comp♭(B, size(A)), B)。

扁平乘积 (Flat products)

• 扁平乘积定义：假设 A 和 B 是扁平布局，且 A 是 size(A)·cosize(B)-可补的。A 和 B 的扁平乘积定义为 A ⊗♭ B = (A, comp♭(A, size(A) · cosize(B))) ◦ B。

易处理的扁平布局 (Tractable flat layouts)

• 易处理布局定义：一个扁平布局 L = sort(L) = (s1, ..., sm) : (d1, ..., dm) 被称为易处理的，如果对每个 1 ≤ i < m，di = 0 或 sidi 整除 di+1。
• 易处理布局的例子：列主序、行主序、紧凑、可补的布局都是易处理的。
• 易处理性的等价条件：L 是易处理的，当且仅当 sort(L) 是易处理的，或 filter(L) 是易处理的，或 filter(L) 是可补的。

嵌套元组 (Nested Tuples)

本节引入嵌套元组，这是定义一般布局所必需的元组泛化。

Profiles

• Profile 定义：一个 Profile P 要么是 ∗，要么是一个由 Profiles (P1, ..., Pr) 组成的元组。

• Profile 的属性：

  • 秩 (rank)：P 的顶层元组的长度。
  • 长度 (length)：P 中 ∗ 的数量。
  • 深度 (depth)：嵌套的层数。

• Profile 的替换 (Substitution)：若 Q 是一个长度为 m 的 Profile，P1, ..., Pm 是一些 Profiles，则 Q-替换 (P1, ..., Pm)Q 是通过将 Q 的第 i 个 ∗ 替换为 Pi 得到的新 Profile。

基本定义

• 嵌套元组定义：一个嵌套元组 X 由一个扁平元组 X♭ (其 flattening) 和一个 Profile prof(X) 组成，且 len(X♭) = len(prof(X))。

• 嵌套元组的属性：其秩、长度、深度、大小等属性由其 Profile 和 flattening 决定。

• 嵌套元组的全等 (Congruent)：如果两个嵌套元组 X1 和 X2 的 Profile 相同，即 prof(X1) = prof(X2)，则称它们是全等的。

替换 (Substitution)

• 嵌套元组的替换：如果 X1, ..., Xm 是嵌套元组，Y 是一个长度为 m 的嵌套元组，则可以定义替换 (X1, ..., Xm)Y，其结果是一个新的嵌套元组，其 flattening 是 X1♭ ⋆ ... ⋆ Xm♭，其 Profile 是 (prof(X1), ..., prof(Xm))prof(Y)。

精化 (Refinement)

• 精化定义：称嵌套元组 X' 精化 X (记为 X' ↠ X)，如果 X 可以通过将 X' 的每个条目替换为某个相同大小的嵌套元组得到。具体地，要么 X = size(X')，要么 rank(X') = rank(X) 且 modei(X') 精化 modei(X)。

• 相对模态 (Relative mode)：如果 X' ↠ X，可以定义 X' 相对于 X 的第 i 个模态 modei(X', X)。X' 可以看作是这些相对模态在其 prof(X) 结构下的替换。

布局 (Layouts)

在介绍了嵌套元组后，本节将布局的概念推广到一般情况。

基本定义

• 布局定义：一个布局是一个对 L = S : D，其中 S 是一个正整数的嵌套元组 (shape)，D 是一个非负整数的嵌套元组 (stride)，且 S 和 D 是全等的。

• 布局的属性：布局的秩、长度、深度、大小和 profile 由其 shape S 决定。

• 布局的扁平化：任何布局 L = S : D 都可以通过 L♭ = S♭ : D♭ 得到一个扁平布局。

• 布局函数：一般布局 L 的布局函数 ΦL 定义为其扁平化布局的布局函数，即 ΦL = ΦL♭。

基本操作

• 扁平化：如上所述，L♭ = S♭ : D♭。
• 拼接：布局 L=S:D 和 L'=S':D' 的拼接是 (L, L') = (S, S') : (D, D')。注意这与扁平布局的拼接 ⋆ 不同。
• P-替换：对于布局 L=S:D 和 profile P (其中 len(P)=rank(L))，可以定义 P-替换 LP。

合并 (Coalesce)

• 合并布局定义：一个布局 L 被称为已合并的，如果其深度为0，或者其深度为1且作为扁平布局是已合并的。
• 合并操作：对于任意布局 L，可以定义 coal(L)，其结果是一个已合并的布局。
• 布局函数等价性：ΦA = ΦB 当且仅当 coal(A) = coal(B)。
• 相对合并：对于布局 L=S:D 和 S 的一个精化 S̄，可以定义相对合并 coal(L, S̄)。

紧凑布局 (Compact layouts)

• 紧凑布局定义：一个布局 L 如果其布局函数 Φcosize(L)L 是一个同构，则称其为紧凑的。
• 等价条件：L 是紧凑的当且仅当 L♭ 是紧凑的或 coal(L) 是紧凑的。

补集 (Complements)

• 补集定义：布局 L' 是 L 的补集，如果拼接布局 (L, L') 是紧凑的。
• 可补性：布局 L 是可补的，当且仅当其扁平化 L♭ 是可补的。
• N-补集：L' 是 L 的 N-补集，如果它是 L 的补集且 size(L) · size(L') = N。

组合 (Composition)

• 组合定义：布局 A 和 B 的组合 B ◦ A 是满足以下条件的唯一布局：1. shape(B◦A) 精化 shape(A)；2. B◦A 在 shape(A) 上是已合并的；3. ΦB◦A = ΦB ◦ Φsize(B)A。
• 组合的存在性：组合可能不存在，或者结果可能是一个非扁平布局，即使输入是扁平的。

逻辑除法 (Logical division)

• 逻辑除法定义：A ⊘ B = (comp(B, size(A)), B) ◦ A，其中 comp(B, size(A)) 是 B 关于 size(A) 的补集。
• 直观解释：逻辑除法允许使用(tile_coord, tile_id) 的形式来索引一个被 B (tile) 剖分的布局 A。
  

  

逻辑乘积 (Logical product)

• 逻辑乘积定义：A ⊗ B = (A, comp(A, size(A) · cosize(B))) ◦ B。
  

  

易处理的布局 (Tractable layouts)

• 易处理布局定义：一个布局 L 被称为易处理的，如果其扁平化 L♭ 是易处理的。

A2 方法细节

Tuple 范畴

本节定义了一个 Tuple 范畴，其对象是正整数元组，其态射称为元组态射。每个元组态射 f : S → T 编码一个扁平布局 Lf。

基本定义

• Fin* 范畴：首先定义 Fin* 范畴，其对象是有限指针集 <m>* = {*, 1, ..., m}，态射是保指针的映射 α: <m>* → <n>* (即 α(*) = *)。

• 易处理映射：Fin* 中的一个指针映射 α 如果对任意 j ∈ <n>，其原像 α⁻¹(j) 为空或单元素集，则称 α 是易处理的 (tractable)。

• Tuple 范畴：Tuple 范畴的对象是正整数元组 S = (s1, ..., sm)。一个态射 f : (s1, ..., sm) → (t1, ..., tn) 由一个易处理的指针映射 α : <m>* → <n>* 指定，并满足条件：如果 1 ≤ i ≤ m 且 α(i) != *，则 si = tα(i)。称 f 位于 α 之上。
  态射 f = (8,8,16,16) --(3,4,1,2)--> (16,16,8,8) 可视化为：
  

  

从元组态射到扁平布局

• 态射到布局的编码：对于元组态射 f : (s1, ..., sm) → (t1, ..., tn)，其编码的扁平布局 Lf 的 shape 是 (s1, ..., sm)，其 stride (d1, ..., dm) 由公式 di = t1 · ... · tα(i)-1 (如果 α(i) != *) 或 di = 0 (如果 α(i) = *) 给出。

• 布局到态射的转换：对于一个易处理的扁平布局 L，可以构造一个标准的元组态射表示 fL，使得 L(fL) = sort(squeeze(filter(L)))。

• 一一对应关系：在非退化 (non-degenerate) 的情况下，标准形式的元组态射与易处理的扁平布局之间存在一一对应关系 (定理 3.1.2.21)。非退化意味着不存在 si=1 且 di!=0 的模态。

示例

• 恒等态射 (Identity morphisms)：idS : S → S 编码了以 S 为 shape 的列主序布局。
• 同构 (Isomorphisms)：同构 f: S → T 编码了紧凑布局。
• 投影 (Projections)：投影态射 p 将 (s1, ..., sm) 投影到其子元组上，其编码的布局 stride 中对应于被投影掉的维度的值为0。
• 扩张 (Dilations)：扩张态射 f 通过在 T 中引入大小为1的元素，对 S 的 stride 进行“膨胀”，实现带填充的加载/存储。

元组态射的实现

• 实现函子 (Realization Functor)：构造了一个实现函子 |·|: Tuple → Set，它将一个元组态射 f 映射到其编码布局 Lf 的布局函数 ΦLf。
• 组合兼容性：该函子证明了 Tuple 范畴中的态射组合与布局组合是兼容的：L(g◦f) = Lg ◦ Lf。

元组态射的操作

• 和 (Sum)：f ⊕ g 是通过拼接 f 和 g 的域和陪域得到的。
• 压缩 (Squeeze)：squeeze(f) 移除域和陪域中所有大小为1的元素。L(squeeze(f)) = squeeze(Lf)。
• 排序 (Sort)：sort(f) 通过预置换 f 的域，使其变为一个已排序的态射。L(sort(f)) = sort(Lf)。
• 合并 (Coalesce)：coal(f) 产生一个已合并的态射。L(coal(f)) = coal(Lf)。
• 拼接 (Concatenate)：对于像不交的 f 和 g，可以定义拼接 f ⋆ g。L(f⋆g) = Lf ⋆ Lg。
• 补集 (Complement)：对于单射 f，可以定义其补集 fc。L(fc) = comp♭(Lf, size(T))。
• 扁平除法 (Flat division)：f ⊘♭ g = (g, gc) ◦ f。L(f ⊘♭ g) = Lf ⊘♭ Lg。
• 扁平乘积 (Flat products)：f ⊗♭ g = (f, f c) ◦ g。L(f ⊗♭ g) = Lf ⊗♭ Lg。

Nest 范畴

本节将 Tuple 范畴推广到 Nest 范畴，其态射编码任意的易处理布局（包括嵌套布局）。

基本定义

• Nest 范畴：Nest 范畴的对象是正整数的嵌套元组。一个态射 f: S → T 由一个元组态射 f♭: S♭ → T♭ 指定，即 HomNest(S, T) = HomTuple(S♭, T♭)。

从嵌套元组态射到布局

• 编码规则：一个嵌套元组态射 f : S → T 编码的布局 Lf，是通过将其扁平化元组态射 f♭ 编码的扁平布局 Lf♭ 赋予 S 的 profile prof(S) 得到的。
• 一一对应关系：标准形式的非退化嵌套元组态射与非退化的易处理布局之间存在一一对应关系 (定理 3.2.2.15)。

嵌套元组态射的操作

• 通用构造：Nest 范畴上的大多数操作（如合并、补集、逻辑除法、逻辑乘积）都是通过将其扁平化，在 Tuple 范畴中执行相应操作，然后再根据需要恢复其嵌套结构来定义的。
• 组合 (Composition)：嵌套元组态射的组合与布局组合是兼容的。Lg◦f = Lg ◦ Lf (定理 3.2.6.21)。
• 合并 (Coalesce)：L(coal(f)) = coal(Lf) (命题 3.2.6.13)。
• 补集 (Complement)：L(fc) = coal(comp(Lf, size(T))) (命题 3.2.6.20)。
• 逻辑除法 (Logical division)：L(f ⊘ g) = Lf ⊘ Lg (命题 3.2.6.26)。
• 逻辑乘积 (Logical product)：L(f ⊗ g) = Lf ⊗ Lg (命题 3.2.6.31)。

计算

本章阐述了如何使用 Tuple 和 Nest 范畴的框架来计算易处理布局的组合、逻辑除法和逻辑乘积。核心是解决一个常见问题：在 cute 中可组合的布局 A 和 B，其标准表示 f 和 g 在 Nest 范畴中可能因为陪域和域不匹配而无法直接组合。

组合

• 核心挑战：标准表示 fA: S → T 和 gB: U → V，当 T != U 时不可组合。

• 解决方案：互精化 (Mutual Refinements)：

  • 互精化定义：对元组 (T, U) 的一个互精化是一对新的嵌套元组 (T', U')，使得 T' 精化 T，U' 精化 U，且 T' 整除 U'。
  • 转换态射：利用互精化，可以将原始态射 f: S → T 和 g: U → V 转换为新的可组合态射 f': S' → T' 和 g': T' → U'。这是通过拉回 (pullback) 和前推 (pushforward) 操作实现的。
    

    

  • 保持布局函数不变：这个转换过程保证了 Φ(Lf) = Φ(Lf') 和 Φ(Lg) = Φ(Lg')。

• 组合算法 (Algorithm 4.1.2)：

  1. 输入：易处理布局 A 和 B。
  2. 获取标准表示：计算 A 和 coal(B) 的标准表示 f: S → T 和 g: U → V。
  3. 计算互精化：使用算法 4.1.1 计算 (T, U) 的一个互精化 (T', U')。如果不存在，则无法组合。
  4. 转换态射：使用构造 4.1.2.1 将 f 和 g 转换为可组合的 f': S' → T' 和 g': T' → U'。
  5. 组合新态射：计算 g' ◦ f'。
  6. 编码为布局：计算 C = L(g'◦f')。
  7. 返回弱组合：C 是 A 和 B 的一个弱组合 (weak composite)。最终的组合是 B ◦ A = coal(C, shape(A))。

A6 附录

A.1 范畴是什么？

• 基本概念：范畴是抽象化态射及其组合的数学对象。它由对象、态射、组合规则和恒等态射组成。
• 范畴的组成：
  1. 对象 (Objects)：一个对象的集合。
  2. 态射 (Morphisms)：对象之间的“箭头”，每个态射 f: X → Y 有一个域 X 和一个陪域 Y。
  3. 组合规则 (Composition rule)：对于 f: X → Y 和 g: Y → Z，存在一个复合态射 g ◦ f : X → Z。组合必须是结合的，即 h ◦ (g ◦ f) = (h ◦ g) ◦ f。
  4. 恒等态射 (Identity morphisms)：每个对象 X 都有一个恒等态射 idX : X → X，满足 f ◦ idX = f 和 idY ◦ f = f。
• 示例：
  • Set 范畴：对象是集合，态射是函数。
  • Vect 范畴：对象是向量空间 Rn，态射是矩阵，组合是矩阵乘法。
  • Div 范畴：对象是正整数，若 a 整除 b，则存在一个唯一的态射 a → b。
• 同构 (Isomorphism)：范畴中的一个态射 f: X → Y 如果存在一个逆态射 f⁻¹: Y → X 使得 f⁻¹ ◦ f = idX 且 f ◦ f⁻¹ = idY，则称 f 为一个同构。

A.2 函子是什么？

• 定义：函子 F: C → D 是范畴 C 和 D 之间的一种映射，它将 C 中的对象映射到 D 中的对象，将 C 中的态射映射到 D 中的态射，并保持组合规则和恒等态射。
• 函子的性质：
  1. 保持组合：F(g ◦ f) = F(g) ◦ F(f)。
  2. 保持恒等：F(idX) = id(FX)。

引用文献

【1, Saunders Mac Lane. Categories for the Working Mathematician. 2nd ed. Vol. 5. Graduate Texts in Mathematics. Springer, 1998. isbn: 978-0-387-98403-0.】在附录 A.1 中被引用，作为对范畴论更高级概念的推荐读物。