在《黎明邮报》的最后一篇基础文章中，我正式定义了非类型（单堆栈）连接演算（UCC），演示了布尔数和自然数的编码，并提供了一种基于UCC的玩具编程语言。在这篇文章中，我将对非类型化多级级联演算（UMCC）做同样的事情，它通过任意数量的任意命名堆栈来增强UCC。这些额外的堆栈减轻了UCC中与堆栈洗牌相关的许多痛苦。它们还提供了一些其他好处，我们将在本文中开始介绍，并在未来的文章中进一步探讨。
如果您在本文或相关玩具编程语言中发现任何错误或遗漏，如果您能通知我，我将不胜感激。我很乐意给出任何更正或建议的归属。
UMCC的语法通过引入堆栈上下文的概念扩展了UCC的语法，我们用（s）表示堆栈上下文∣ |e | e | s∣ e），其中s是堆栈标识符，e是表达式：
表达式e=i∣ [e]引用∣ e 1 e 2。作曲∣ （s）∣ e）在哪里∉ S（e）堆栈上下文\begin{array}{l}\text{Expressions}&；e&；=&；i&&；\文本{injective}\\\\&&|&；[e] &&；\文本{quote}\\\\&&|&；e_1~e_2~~e_n&&；\文本{compose}\\\\&&|&；（东南）及；\文本{where}~s\notin\mathbb{s}（e）&；\文本{stack context}\\\结束{array}表达式 E = ∣ ∣ ∣ i[e]e 1 E2 ... 伊恩 （s）∣ （e） 在哪里∈ / S（e） 内部引用组合堆栈上下文
S（i）={S（[e]）={S（e1e2…en）=S（e1）⋃ S（E2）⋃ . . . ⋃ S（e n）S（（S）∣ e））={s}⋃ S（e）\begin{array}{l}\mathbb{S}（i）&；=&\{\}\\\mathbb{S}（[e]）&；=&\{\\\\mathbb{S}（e_1~e_2~…~e_n）&；=&；\mathbb{S}（e_1）\bigcup\mathbb{S}（e_2）\bigcup。。。\bigcup\mathbb{S}（e_n）\\\mathbb{S}（（S|e））&；=&\{s\}\bigcup\mathbb{s}（e）\\\end{array}s（i）s（[e]）s（e1） E2 ... 伊恩 ) S（（S）∣ （e） = = = = {}{}S（e1） ) S（E2） ) ... S（e）n ) {s}s（e）
s∉ S（e）S\notin\mathbb{S}（e）S∈ / S（e）限制本质上意味着嵌套的、不带引号的堆栈上下文必须具有不相交的堆栈标识符。在这篇文章的后面，我们将看看∉ S（e）S\notin\mathbb{S}（e）S∈ / 将该演算作为编程语言实现时，可以有效地解除S（e）限制。
该演算的语义由表达式对值多个堆栈的影响定义，这些值多个堆栈本质上是从堆栈标识符到值堆栈的映射：
Values v=[e]引用的表达式值堆栈⟨ s∣ 五、⟩ = ⟨ s∣ ⟩ 空栈∣ ⟨ s∣ V V⟩ 将v推到堆栈s值多个堆栈v=vϵ空多个堆栈∣ 五、⟨ s∣ 五、⟩ 添加堆栈s\begin{array}{l}\text{Values}&；v&；=&；[e] &；\text{quoted expression}\text{Value Stacks}&；\布拉克特{s|V}&；=&；\布拉克特{s|}；\文本{empty stack}~s\\&&|&；\布拉克特{s|V~V}&；\text{push}~v~\text{on stack}~s\text{Value multistack}&；\mathbb{V}&；=&；\mathbb{V}\epsilon&；\文本{empty multistack}\\\\&&|&；\mathbb{V}\braket{s|V}&；\文本{add stack}~s\\\end{array}值堆栈值多个堆栈 五、⟨ s∣ 五、⟩ 五、 = = ∣ = ∣ [e]⟨ s∣ ⟩ ⟨ s∣ V V⟩ Vϵ 五、⟨ s∣ 五、⟩ 引用表达式空堆栈s将v推到堆栈s空多堆栈添加堆栈s
与UCC相比，在UMCC中，我们用push\text{push}push和pop\text{pop}pop来替换swap\text{swap}swap内在函数，它们在堆栈之间移动值。因此，在UMCC中有七个内在的连接术语，push\text{push}push、pop\text{pop}pop、clone\text{clone}clone、drop\text{drop}drop、quote\text{quote}quote、compose\text{compose}compose和apply\text{apply}apply，由以下小步语义定义：
五、⟨ s∣ V V⟩ ⟨ s′∣ V'V'⟩ （s′）∣ （s）∣ 推）⟶ 五、⟨ s∣ V′⟩ ⟨ s′∣ V′⟩ 五、⟨ s∣ V V⟩ ⟨ s′∣ V'V'⟩ （s′）∣ （s）∣ 流行音乐）⟶ 五、⟨ s∣ 五、⟩ ⟨ s′∣ V′V′V⟩ 五、⟨ s∣ V V⟩ （s′）∣ （s）∣ 克隆）⟶ 五、⟨ s∣ V V V⟩ 五、⟨ s∣ V V⟩ （s′）∣ （s）∣ 下降）⟶ 五、⟨ s∣ 五、⟩ 五、⟨ s∣ V V⟩ （s′）∣ （s）∣ 引用）⟶ 五、⟨ s∣ V[V]⟩ 五、⟨ s∣ V[e1…en][e1′…en′]⟩ （s′）∣ （s）∣ 作曲）⟶ 五、⟨ s∣ V[e1…e1′…enn′]⟩ 五、⟨ s∣ V[e]⟩ （s′）∣ （s）∣ （适用）⟶ 五、⟨ s∣ 五、⟩ （s′）∣ （s）∣ e））\begin{array}{l}\mathbb{V}\braket{s|V~V}\braket{s'；|V'；~V'；}&；（s'；|（s | \text{push}））和；\longrightarrow&；\mathbb{V}\braket{s|V~V~V'；}\布拉克特{s'；|V'；}\\\mathbb{V}\braket{s|V~V}\braket{s'；|V'；~V'；}&；（s'；|（s | \text{pop}））和；\longrightarrow&；\mathbb{V}\braket{s|V}\braket{s'；|V'；~V'；~V}\\\ mathbb{V}\braket{s | V~V}&；（s'；|（s | \text{clone}））&；\longrightarrow&；\mathbb{V}\braket{s|V~V~V}\\\ mathbb{V}\braket{s|V~V}&；（s'；|（s | \text{drop}））&；\longrightarrow&；\mathbb{V}\braket{s|V}\\\ mathbb{V}\braket{s|V~V}&；（s'；|（s | \text{quote}）和；\longrightarrow&；\mathbb{V}\braket{s|V~[V]}\\\ mathbb{V}\braket{s|V~[e|u 1~~~e#n]~[e'；#u 1~~~e'；#n]&；（s'；|（s | \text{compose}））和；\longrightarrow&；\mathbb{V}\braket{s|V~[e|1~~~e|n~e'；_1~~~e'；#n]\\\\ mathbb{V}\braket{s|V~[e]}&；（s'；|（s | \text{apply}））&；\longrightarrow&；\mathbb{V}\braket{s|V}（s'；|（s|e））\\\end{array}V⟨ s∣ V V⟩ ⟨ s′∣ V'V'⟩ 五、⟨ s∣ V V⟩ ⟨ s′∣ V'V'⟩ 五、⟨ s∣ V V⟩ 五、⟨ s∣ V V⟩ 五、⟨ s∣ V V⟩ 五、⟨ s∣ V[e 1 ... 伊恩 ] [e1′” ... e n′的 ] ⟩ 五、⟨ s∣ V[e]⟩ （s′）∣ （s）∣ 推（s′）∣ （s）∣ （流行音乐）∣ （s）∣ 克隆（s′）∣ （s）∣ 下降（s′）∣ （s）∣ （引语）∣ （s）∣ 组合（s′）∣ （s）∣ （适用） ⟶ ⟶ ⟶ ⟶ ⟶ ⟶ ⟶ 五、⟨ s∣ V′⟩ ⟨ s′∣ V′⟩ 五、⟨ s∣ 五、⟩ ⟨ s′∣ V′V′V⟩ 五、⟨ s∣ V V V⟩ 五、⟨ s∣ 五、⟩ 五、⟨ s∣ V[V]⟩ 五、⟨ s∣ V[e 1 ... 伊恩 e1′ ... e n′的 ] ⟩ 五、⟨ s∣ 五、⟩ （s′）∣ （s）∣ （e）
五、⟨ s∣ 五、⟩ （s′）∣ （s）∣ [e]））⟶ 五、⟨ s∣ V[e]⟩ \开始{array}{l}\mathbb{V}\braket{s|V}&；（s'；|（s |[e]））&；\longrightarrow&；\mathbb{V}\braket{s|V~[e]}\\\ end{array}V⟨ s∣ 五、⟩ （s′）∣ （s）∣ [e]）） ⟶ 五、⟨ s∣ V[e]⟩
ve1e2。eN=（（ve1）e2）en）\begin{array}{l}\mathbb{V}~e_1~e_2~~e_n&；=&；（（（\mathbb{V}~e_1）~e_2）~.）~e_n）\\\end{array}V e 1 E2 ... 伊恩 = （（（V）e 1） ) E2 ) ... ) 伊恩 )
与UCC相比，为了减少所有有效的UMCC表达式，还需要三条额外的规则。首先，堆栈上下文分布在组合的子表达式上：
（s）∣ e 1 e 2。e（n）⟷ （s）∣ e 1）（s）∣ e 2）。（s）∣ 开始{array}{l}（s|e_1~e_2~…~e_n）&；\longleftrightarrow&；（s|e_1）～（s|e_2）～~（s | e_n）\\\end{array}（s）∣ e 1 E2 ... 伊恩 ) ⟷ （s）∣ e 1 ) （s）∣ E2 ) ... （s）∣ 伊恩 )
其次，当两个以上的堆栈上下文直接嵌套时，最外层的上下文是冗余的，可以删除：
（s′）∣ （s′）∣ （s）∣ （e）⟶ （s′）∣ （s）∣ e））\begin{array}{l}（s'；'；|（s'；|（s | e））&；\longrightarrow&；（s'；|（s|e））\\\end{array}（s′）∣ （s′）∣ （s）∣ （e） ⟶ （s′）∣ （s）∣ （e）
（s′）∣ ) ) ⟶ （s′）∣ ) ⟶ . \开始{array}{l}（s'；（s|）和；\longrightarrow&；（s'；|）和；\longrightarrow&\\\结束{array}（s′）∣ )) ⟶ （s′）∣ ) ⟶ .
这就完成了UMCC的操作语义。通过使用堆栈上下文扩展UCC、减少它们的一些新规则，以及在堆栈之间移动值的两个新内部函数，我们得到了一个级联演算，它仍然非常小和简单，同时对于编写有用的程序来说更实用。正如我在介绍Dawn（第1部分）中开始描述的那样，与其他级联语言相比，Multistack减轻了堆栈洗牌的痛苦，显著提高了可读性和可写性，同时保留了级联语言的积极方面。此外，正如我们将在本文后面开始看到的，多级连接语言还有其他有趣的特性，比如全局变量，但没有全局变量通常带来的缺点。
我们可以通过翻译任何UCC表达式来将UCC嵌入到UMCC中 , 在相应的UMCC表达式中，eum C=（s′）∣ （s）∣ e U C C）e_{UMCC}=（s'；|（s|e_{UCC}））e U MCC = （s′）∣ （s）∣ e U CC )), 通过定义swap\text{swap}交换项。要定义swap\text{swap}swap，我们只需要选择两个新的堆栈标识符，例如s1 s_1 s1 s1'_1s1′ , 将最上面的两个值按在上面，然后按交换顺序将其弹出：
互换=（s1）∣ 推（s1′）∣ 推（s1）∣ pop）（s1′）∣ pop）\qquad\text{swap}=（s|1 | \text{push}）（s'；|1 | \text{push}）（s|u 1 | \text{pop}）（s'；|1 | \text{pop}）swap=（s1 ∣ 推（s1′） ∣ 推（s1） ∣ pop）（s1′） ∣ （流行音乐）
在将UMCC作为编程语言实现时，我们希望用用户定义的术语扩展核心演算。不幸的是∉ S（e）S\notin\mathbb{S}（e）S∈ / S（e）对堆栈上下文的限制提出了一个我们必须解决的问题。如果用户定义了一个包含堆栈标识符的术语，则遵循∉ S（e）S\notin\mathbb{S}（e）S∈ / S（e）限制将阻止在任何其他S堆栈上下文中使用该术语，这是一个不受欢迎的限制。但是，如果我们忽略这个限制而不做任何其他更改，那么这个术语的行为就会有所不同，这取决于它是否在s的堆栈上下文中使用，这可能会导致相当大的混乱。
幸运的是，我们可以通过让解释器/编译器在对外部堆栈上下文进行阴影处理时自动重命名未引用的堆栈标识符来轻松解决这个问题。我们将此转换称为堆栈标识符去阴影。有两种情况需要去阴影，第一种是在评估apply\text{apply}apply内在时，第二种是在评估（即扩展）用户定义的术语时。为了让用户即使在术语定义包含无引号的阴影堆栈标识符时也可以内联术语定义，我们还可以在定义新术语以及开始减少解释器的read-eval-print循环（REPL）中的新表达式时应用去阴影。如果在这四种情况下都使用，去阴影可以有效地提升阴影∉ S（e）S\notin\mathbb{S}（e）S∈ / 完全是S（e）限制。
就像UCC一样，为了测试和验证本文中的所有内容，我为一种基于这种演算的玩具编程语言实现了一个解释器UMCCI。toy编程语言使用用户定义的术语扩展了核心演算，这些术语可以直接或相互递归，并使用堆栈标识符去阴影来提升∉ S（e）S\notin\mathbb{S}（e）S∈ / S（e）限制，如上所述。此外，为了简化样板文件，当在没有任何堆栈上下文的情况下计算表达式时，解释器会自动将表达式包装在默认堆栈上下文中。
解释器可以在浏览器中试用，源代码可以在Github上获得。本文中描述的大多数术语都是预定义的，但任何术语都可以由用户重新定义。示例会话将在本文的其余部分显示。
接下来，我们将看看如何在这个微积分中执行一些计算，就像我们在UCC中所做的那样。这个演算仍然不包括任何内置的数据类型，所以我们仍然将数据类型编码为带引号的表达式。虽然我们可以使用与UCC中相同的布尔和自然数编码，但我们将使用更通用、更系统的编码，我们将利用多个堆栈来改进人体工程学。特别是，我们将从非类型化lambda演算中任意（包括递归）代数数据类型（ADT）的Scott编码中获得灵感，并将相同的概念应用于UMCC。首先，我们将正式定义编码，然后我们将看几个例子，包括布尔数和自然数。
Scott编码背后的基本思想是将代数数据类型的每个变量编码为一个高阶项，该项同时充当构造函数和析构函数（也称为消除器）。当应用于变量的输入数据时，构造函数返回该输入数据的闭包。然后，当该闭包应用于每个可能变量的case表达式时，它仅将编码变量的case表达式应用于闭合的over数据。所以闭包充当析构函数。在非类型化lambda演算中，析构函数按特定顺序应用于case表达式。类似地，在UCC中，我们将按特定顺序将带引号的大小写表达式放在堆栈顶部，然后应用析构函数。在UMCC中，我们将把带引号的大小写表达式放在特定堆栈的顶部，然后应用析构函数。
形式上，设D是一个具有N个构造函数的代数数据类型，{C i}i=1 N\{C_i\}{i=1}^N{C i } i=1N , 这样构造函数ci_{i}ci 有arity A i_{i}A i吗 . 构造函数ci_{i}ci的编码 数据类型D的
C i=quote A i[C i′]组合\qquad C_i=\text{quote}{A_i}~[C'；_i]~\text{compose}C i = 引用我的话 [ci′的 ] 谱写
C i′=（案例1）∣ 放下）。（案例一）− 1.∣ （第一种情况）∣ （pop）（案例1+1）∣ 放下）。（案例N）∣ 下拉）应用\qquad C和#39_i=（\text{case\}C_1 | \text{drop}）。。。（\text{case\}C{i-1}| \text{drop}）（\text{case\}C_i | \text{pop}）（\text{case\}C{i+1}| \text{drop}）。。。（\text{case\\}C|N | \text{drop}）~\text{apply}ci′ = （案例1） ∣ 放下）。。。（案例一）− 1. ∣ （第一种情况） ∣ （pop）（案例1+1） ∣ 放下）。。。（案例N） ∣ 放弃）申请
其中quote n\text{quote}{n}quote n 接受n个输入并返回一个包含所有输入的单引号：
五、⟨ s∣ v1。v n⟩ （s′）∣ （s）∣ 引用（n））⇓ 五、⟨ s∣ V[v1…vn]⟩ \qquad\mathbb{V}\braket{s|V~V|1…V|n}（s'；|（s | \text{quote}n））\Downarrow\mathbb{V}\braket{s|V~[V|1…V|n]}V⟨ s∣ v1 ... v n ⟩ （s′）∣ （s）∣ 引用n )) ⇓ 五、⟨ s∣ V[v1 ... v n ] ⟩
引用n>；1=（s n）∣ 推）。（s 1）∣ 推（s1）∣ 引用流行音乐）。（s）n∣ quote pop）组合n\qquad\text{quote}{n>；1}=（s_n | \text{push}）。。。（s|1 | \text{push}）~（s|1 | \text{quote}~\text{pop}）。。。（s|n | \text{quote}~\text{pop}）~\text{compose}n quote n>；1. = （s）n ∣ 推）。。。（s 1） ∣ 推（s1） ∣ 引用流行音乐）。。。（s）n ∣ 引用流行语
其中compose n\text{compose}n compose n 由n个引号组成，定义与UCC上的前一篇文章相同。
要分解以这种方式编码的ADT，请在每个case堆栈的顶部放置一个带引号的case表达式，然后应用析构函数：
（案例1）∣ [e 1]）。（案例N）∣ [en]）应用\qquad（\text{case\}C_1 |[e_1]）。。。（\text{case\}C|N |[e_N]）~\text{apply}（case_c1 ∣ [e 1 ]) ... （案例N） ∣ [e N ]) 申请
正如我们将在下面的示例中看到的，解构非常类似于ML家族语言中的简单穷举模式匹配。最终，Dawn将包括更多符合人体工程学的模式匹配形式，如递归和多值匹配。在未来的帖子中，我们将研究这种符合人体工程学的模式匹配形式，并推导出如何将它们降低到UMCC中可用的有限破坏形式。
在UCC上的最后一篇文章中，我们将布尔值编码为引用的高阶项，当应用时，它们接受两个值，一个用于false case，一个用于true case，删除不匹配的case值，并保留匹配的case值。在这里，我们的布尔编码将接受两个带引号的大小写表达式，一个用于假大小写，一个用于真大小写，删除不匹配的带引号的大小写表达式，保留并应用匹配的带引号的大小写表达式。结果是，应用布尔值类似于在ML家族语言（如Haskell）中对布尔值进行简单的穷举模式匹配。因此，以下Haskell和UMCC定义是等效的：
数据Bool=False | Truenot a=False的情况a->；正确-正确->；Falseor a b=情况b为False->；错误案例a->；假-真->；正确-正确->；True和a b=情况b为False->；假-真->；错误案例a->；假-真->；符合事实的
{term False=quote0[_False]compose}{term True=quote0[_真]compose}{term _False=（case | False | pop）（case | True | drop）apply}{term(case | False | drop)_
......