Joy 非正式教程

# Joy 非正式教程 来源：https://www.kevinalbrecht.com/code/joy-mirror/j01tut.html 您所在位置：Joy 非正式教程 (https://www.kevinalbrecht.com/code/joy-mirror/j01tut.html) Joy 非正式教程返回至编程语言 Joy 主页 (http://www.latrobe.edu.au/philosophy/phimvt/joy.html)*作者：Manfred von Thun*2003 年 2 月修订 本修订版包含对 John Cowan (2001) 扩展的引用。 *摘要：*Joy 是一种函数式编程语言，它不基于函数对参数的应用，而是基于函数的组合。它不使用 lambda 抽象表达式，而是使用引号表达式（quotation of expressions）。大量的所谓组合子（combinators）用于执行引号解除（dequotation），它们起到高阶函数的作用。其中一些组合子可用于消除递归定义。用 Joy 编写的程序紧凑，通常看起来就像后缀记法。编写程序并对其进行推理变得容易，因为在 Joy 中没有实际参数对形式参数的替换。 本教程描述了 Joy 语言的基本特性，这些特性在所有实现中很可能是一致的。 *关键词：*函数式编程、高阶函数、函数组合、组合子、消除递归定义、无变量记法 --- ## 引言 虽然 Joy 的理论很有趣，但本教程尽可能避免理论。本文的其余部分组织如下：本引言部分以对语言一些显著特征的极简短概述继续。接下来的两节介绍基本数据类型及其操作。之后一节回到 Joy 的核心特性：程序的引号及其与组合子的一同使用。在关于定义的简短一节之后，下一节继续讨论组合子，特别是那些可以消除递归定义需求的组合子。在最后一节，通过几个短程序和一个较大程序来演示 Joy 中聚合数据的编程。 要相加两个整数（例如 2 和 3）并输出它们的和，您可以输入程序： `` 2 3 + `` 这是普通的后缀记法，是 1920 年代波兰逻辑学家首次使用的一种记法的反转形式。其优点在于，在复杂表达式中无需括号。内部工作原理如下：第一个数字将整数 2 压入堆栈。第二个数字将整数 3 压入其顶部。然后加法操作符将这两个整数弹出堆栈，并压入它们的和 5。系统读取像上面这样的输入，并在它们以句点 `"."` 结束时执行，像这样： `` 2 3 + . `` 在默认模式下，无需显式的输出指令，因此数字 `5` 会被写入输出文件（通常是屏幕）。因此，在默认模式下，终止的 `"."` 可被视为指令，用于写入堆栈顶部元素。为了简便，下面的内容中将不再显示终止句点。除了整数，当前版本的 Joy（由 John Cowan 扩展）还包含实数或“浮点数”。浮点数的算术运算与整数类似。下面示例为两个数的乘法： `` 2.34 5.67 * `` 并将它们的乘积 `13.2678` 留在堆栈顶部。（因此，要在终端上查看结果，上述行必须以句点终止。）要计算整数的平方，只需将其自身相乘。要计算两个整数之和的平方，需将和自身相乘。最好在不重复计算和的情况下完成。以下是一个计算 2 和 3 之和平方的程序： `` 2 3 + dup * `` 计算完 2 和 3 的和后，堆栈中只有整数 5。然后 `dup` 操作符将 5 的另一个副本压入堆栈。然后乘法操作符将两个整数替换为它们的乘积，即 5 的平方。平方结果输出为 25。除了 `dup` 操作符，还有其他几个用于重新排列堆栈顶部的操作符。`pop` 操作符移除顶部元素，`swap` 操作符交换顶部两个元素。这与真正的后缀记法不同，因为堆栈操作符只有在存在堆栈的情况下才有意义。这种记法也用于一些袖珍计算器、Unix 工具 dc、排版语言 Postscript 和通用语言 Forth。Billy Tanksley 建议称之为串联记法（concatenative notation）。这种记法的理论本身就是一个话题，但本教程不会涉及。 一个*列表*（list）由方括号括起来的整数构成。就像整数可以相加和进行其他操作一样，列表也可以通过各种方式进行操作。以下示例将两个列表*连接*起来： `` [1 2 3] [4 5 6 7] concat `` 首先将两个列表压入堆栈。然后 `concat` 操作符将它们弹出堆栈，并将列表 `[1 2 3 4 5 6 7]` 压入堆栈。在那里可以进一步操作，或将其写入输出文件。 列表的元素不必都是同一类型，元素本身也可以是列表。以下示例使用了一个包含一个整数、两个浮点数和一个包含三个整数的列表的列表。 `` [ 3.14 42 [1 2 3] 0.003 ] dup concat `` `dup` 操作符将在堆栈顶部压入一个列表副本，然后将这两个列表连接成一个。 Joy 大量使用了*组合子*（combinators）。它们类似于操作符，期望堆栈顶部有特定内容。但与操作符不同的是，它们会执行堆栈顶部的内容，而该内容必须是程序的*引号*（quotation），用方括号括起来。其中一个组合子是用于将一个列表的元素通过函数映射到另一个列表的 `map` 组合子。考虑以下程序： `` [1 2 3 4] [dup *] map `` 它首先将整数列表压入堆栈，然后将引号程序压入堆栈。接着 `map` 组合子移除列表和引号，并通过将程序应用于给定列表的每个成员来构造另一个列表。结果是将列表 `[1 4 9 16]` 留在堆栈顶部。 在*定义*新函数时，不使用形式参数，因此没有实际参数对形式参数的替换。经过以下定义： `` square == dup * `` 符号 `square` 就可以代替 `dup *` 使用。定义出现在如下所示的块中： `` DEFINE square == dup * ; cube == dup dup * * . `` 如示例所示，定义模式由保留字 `DEFINE` 启动，直到句点结束。各个定义之间用分号分隔。在库中，使用 `LIBRA` 代替 `DEFINE`。在本文的其余部分，将不再显示启动符、分隔符和终止符。 与其他编程语言一样，定义可以是递归的，例如阶乘函数的定义。该定义使用了某种递归模式，该模式在其他地方也很有用。在 Joy 中，有一个用于*原始递归*（primitive recursion）的组合子，它内置了这种模式，从而无需定义。`primrec` 组合子除了一个数据参数外，还期望两个引号程序。对于整数数据参数，其工作方式如下：如果数据参数为零，则第一个引号必须产生要返回的值。如果数据参数为正，则第二个引号必须将数据参数与将函数应用于其前驱的结果结合起来。对于阶乘函数，所需的引号程序非常简单： `` [1] [*] primrec `` 递归地计算阶乘。不需要任何定义。例如，以下程序计算 `5` 的阶乘： `` 5 [1] [*] primrec `` 它首先将数字 `5` 压入堆栈，然后压入两个短引号程序。此时堆栈包含三个元素。然后执行 `primrec` 组合子。它弹出两个引号并保存到别处。然后 `primrec` 测试堆栈顶部元素（最初是 `5`）是否等于零。如果是，则弹出它并执行其中一个引号 `[1]`，该引号将 `1` 留在堆栈上作为结果。否则，它将一个减一的副本压入堆栈顶部并递归。在从递归返回的路上，它使用另一个引号 `[*]` 将现在堆栈顶部的阶乘与堆栈上的第二个元素相乘。当所有操作完成后，堆栈包含 `120`，即 `5` 的阶乘。 从这个程序可以看出，递归定义的通常分支结构已内建于组合子中。`primrec` 组合子可以与许多其他引号参数一起使用，以计算完全不同的函数。它也可以用于整数以外的数据类型。 Joy 还有许多其他组合子，可用于计算许多函数，而无需用户给出递归或非递归定义。一些组合子比 `primrec` 更具数据特异性，而另一些则通用得多。 ## 整数、浮点数、字符和真值 Joy 的数据类型分为简单类型和聚合类型。*简单*类型包括整数、浮点数（或实数）、字符和真值。聚合类型包括集合、字符串和列表。任何类型的字面量都会将该类型的值压入堆栈。它们可以通过通用堆栈操作（如 `dup`、`pop`、`swap` 等）进行操作，也可以通过特定于其类型的操作符进行操作。本节介绍简单类型的字面量和操作符。 *整数*就是整数。该类型的字面量以十进制记法书写。提供以下二元运算： `` + - * / rem `` 前四个具有通常含义，最后一个为除法后的余数运算符。操作符写在操作数之后。二元操作符从堆栈顶部移除两个值，并用结果替换它们。例如，程序 `` 20 3 4 + * 6 - 100 rem `` 计算结果为 34，此值留在堆栈顶部。还有一些特定于整数的一元操作符，如 `abs`（取绝对值）和 `signum`（根据参数为负、零或正分别返回 `-1`、`0` 或 `+1`）。 除了正整数和负整数（或整数）外，Joy 还有浮点数或“浮点数”。该类型的字面量以小数点及小数点后至少一位数字书写。可选地，最后一位数字后可以跟 'E' 或 'e' 以及正或负的指数。以下是一些示例： `` 3.14 314.0 3.14E5 3.14e-5 `` 最后两个等价于 314000.0 和 0.0000314。大多数整数操作符同样适用于浮点数。John Cowan 的扩展还提供了大量用于浮点数的函数，但这超出了本教程的范围。 *字符*是字母、数字、标点符号，实际上是任何可打印字符或少数空白字符。类型为字符的字面量写作一个单引号后跟字符本身。字符类型的值被视为类似小整数。这意味着可以将其他数字加到它们上面，例如 32 可用于将大写字母转换为小写字母。有两个定义在字符和整数上的一元操作符：`pred` 取前驱，`succ` 取后继。例如， `` 'A 32 + succ succ `` 计算结果为 `'c`，即第三个小写字母。 *真值*类型在某些语言中称为*布尔型*。以下是两个字面量、一元否定操作符和两个二元操作符（合取与析取）： `` true false not and or `` 例如，程序`` false true false not and not or `` 计算结果为 `false`。 整数和字符类型的值可以使用以下*关系操作符*进行比较： `` = < > != <= >= `` `!=` 操作符返回 `=` 操作符的否定结果。其他操作符具有通常含义。与所有操作符一样，它们采用后缀记法。结果总是真值。例如， `` 'A 'E < 2 3 + 15 3 / = and `` 计算结果为 `true`。 ## 集合、字符串和列表 *聚合*类型包括无序类型的集合以及有序类型的字符串和列表。聚合可以构建、组合、拆解以及测试成员关系。本节介绍聚合类型的字面量和操作符。 *集合*是零个或多个小整数的无序集合。类型为集合的字面量写在大括号内；空集合写作一对空的大括号。对于集合字面量，元素的顺序无关紧要，重复也无效。合取与析取操作符也定义在集合上。例如，以下两个等价程序： `` {1 3 5 7} {2 4 6 8} or {} or {3 4 5 6 7 8 9 10} and {3 7 5 1} {2 4 6 8} or {} or {3 4 5 6 7 8 9 10 10} and `` 计算结果为 `{3 4 5 6 7 8}`。否定操作符 `not` 相对于最大可表示集合（在大多数实现中最多有 32 个成员：从 `0` 到 `31`）取补集。 *字符串*是零个或多个字符的有序序列。类型为字符串的字面量写作双引号内；空字符串写作两个相邻的双引号，中间没有任何内容：`""`。请注意，这与仅包含空格的字符串 `" "` 不同。两个字符串可以连接，字符串也可以反转。例如， `` "dooG" reverse " morning" " " concat concat "world" concat `` 计算结果为 `"Good morning world"`。 对于许多操作符，实现可以选择将其作为原语，或者在库中定义。除了执行速度外，对用户来说，哪种选择没有区别。在当前实现中，`reverse` 操作符是在库中定义的。 *列表*是零个或多个任意类型值的有序序列。类型为列表的字面量写作方括号内；空列表写作一对空的括号。列表可以包含列表作为成员，因此列表类型是一种递归数据类型。 聚合类型的值（即集合、字符串和列表）可以通过 `cons` 操作符添加新成员来从现有值构建。这是一个二元操作符，其第一个参数必须是可能的新成员，第二个参数必须是聚合。对于集合，如果新成员尚未存在则添加；对于字符串和列表，新成员添加在最前面。以下是一些示例。左侧的程序计算结果为右侧的字面量。 `` 5 3 {2 1} cons cons 3 swap cons {1 2 3 5} 'E 'C "AB" cons cons 'C swap cons "CECAB" 5 [6] [1 2] cons cons 'A swap cons ['A 5 [6] 1 2] `` 如示例所示，`cons` 操作符最适用于向已在堆栈中且位于聚合下方的聚合添加元素。要添加刚刚压入的新元素，需要先将新元素和聚合进行 `swap` 交换，然后再将新元素 `cons` 入聚合。为方便起见，Joy 还有另一个操作符 `swons`，它首先执行 `swap`，然后执行 `cons`。 `cons` 和 `swons` 操作符构建聚合值，而两个一元操作符 `first` 和 `rest` 则拆解它们。两者仅适用于非空聚合值。对于