mlochbaum/Singeli 来源: https://github.com/mlochbaum/Singeli

Singeli 介绍:

Singeli 作为解释器 | Singeli 作为编译器
-> Purity 和 Ford 编写一个 min 过滤器
Singeli 是一种领域特定语言，用于构建高性能算法（包括 SIMD (https://en.wikipedia.org/wiki/SIMD)），它通过灵活的抽象来封装与单个指令相对应的代码。它在 BQN (https://mlochbaum.github.io/BQN) 中实现，前端生成中间表示 (IR)，后端将其转换为 C 语言（IR 设计简单，因此支持 LLVM 或机器码等其他后端无需太多工作）。凭借在 CBQN (https://github.com/dzaima/CBQN/tree/master/src/singeli/src) 中投入生产的约 5k 行代码，我认为 Singeli 已可称为可用之列！另请参见 SingeliSort (https://github.com/mlochbaum/SingeliSort) 和 1brc (https://github.com/dzaima/1brc)。
核心语言现在应该是稳定的（且过往的破坏性变更都附带了大约 6 个月的弃用期）。标准包含文件对于舒适的编程很重要，但在某些领域（特别是更复杂的 SIMD 指令）还不够完善。但如果有更好的设计方案出现，我们可能会引入新的包含文件，而不是进行重大的破坏性变更。
要编译 input.singeli：

$ singeli input.singeli [-o output.c]

选项请参见 $ singeli -h 或此部分。要将 singeli 作为可执行文件运行，请确保 CBQN (https://github.com/dzaima/CBQN) 作为 bqn 安装在您的可执行文件路径中，或调用为 /path/to/bqn singeli ...。
调试编译错误很容易，因为它们带有解析或堆栈跟踪（如果没有，那就是 bug——请报告），且 show{} 可以在编译时打印任何你想要的内容。在运行时，include 'debug/printf' 提供的 lprintf{} 会打印你传递给它的内容，并且生成的 C 代码相当冗长，但它嵌入了源函数和变量名，可以帮助你定位。
在工具方面，交互式 Singeli 操场 (https://github.com/dzaima/singeliPlayground) 是一个不错的工具，可以让你在不经历尴尬的编译-调试循环的情况下让代码的部分功能运行起来，而 singeli-lsp (https://codeberg.org/dzaima/singeli-lsp) 提供了带有解析和名称解析的高级编辑功能。
Singeli 的早期设计讨论发生在 topanswers.xyz (https://topanswers.xyz/apl?q=1623)；现在它在 BQN 论坛 (https://mlochbaum.github.io/BQN/community/forums.html)。

语言概述

Singeli 主要是一种元编程语言。其目的是在 CPU 指令周围构建抽象，以创建大量专用代码。源代码倾向于在编译时执行复杂操作，以生成在运行时执行相对简单操作的程序，因此最好将你的思维围绕编译时发生的事情。
抽象的主要工具是生成器。用 {参数} 编写，生成器执行与 C 宏、C++ 模板或泛型类似的任务，但提供了更多灵活性。它们在编译期间展开，并构成一种图灵完备的语言。生成器使用词法作用域并允许递归调用。
这是一个调用另一个生成器的示例：

def gen{func, arg} = func{arg, arg + 1}  

实际上，+ 也是一个生成器（如果它被定义了的话）。Singeli 的操作符不是内置的；相反，用户将每个操作符声明为生成器的中缀或前缀语法。例如，include/skin/cop.singeli 中的这行将 + 定义为一个左结合、优先级为 30 的中缀操作符（可以有一个中缀和一个前缀定义）：

oper + __add infix left 30  

生成器可以通过额外的定义进行扩展。每个定义在其适用域上覆盖之前的定义，这意味着应用生成器时，会向后搜索当前作用域中所有可见的定义，直到找到合适的。上面的 gen 适用于任意两个参数，但可以使用类型和条件来缩小定义范围：

def gen{x:T, n, n, S if 'number'==kind{n} and T<=S} = { cast{S, x} + n }  

这里，x 必须是一个带类型的值，且类型为 T，两个 n 参数必须匹配。并且 if 后面的条件必须成立。否则，会尝试之前的定义，如果没有剩余定义则会出错。
这里的最终目标是定义函数供其他程序使用。函数在顶层使用 fn 关键字和括号语法声明，可能带有类似生成器的参数。类型使用 value:type 语法而不是 type value。

fn demo{T}(a:T, len:u64) : void = { while (len > 0) { a = a + 1 len = len - 1 } }  

这里你可以看到，要在运行时执行的代码以命令式风格编写。提供了 if、else 和 while 控制结构。语句由换行符或分号分隔；这两个字符是等效的。
如果可能，迭代应使用 for-each 循环进行。在 SIMD 编程中，这些循环非常重要，并且有多种变体，考虑了向量化和循环展开。因此，Singeli 不提供单一的 for 循环结构，而是提供一种用于定义循环的通用机制。
定义看起来像这样：

def for{vars,begin,end,iter} = { i:u64 = begin while (i < end) { iter{i, vars} ++i } }  

虽然这个循环本身是一个普通生成器（允许其他循环调用它），但使用特殊语法在变量和代码块上调用它。这是一个有两个指针的例子：

@for (src,dst over i from 0 to len) { src = 1 + dst }  

在循环外，这些变量是指针，在循环内，它们是个别值。正是 iter 生成器执行此转换，使用给定的索引 i 索引 vars 中的每个指针。每个变量跟踪其值是否在循环内被设置，如果是这种情况则写入内存。

生成器

生成器本质上是一个编译时函数，它接受称为参数的值并返回结果。创建生成器有几种方式：

# 匿名生成器，立即调用  
def a_sq = ({x} => x*x){a}  
# 带有两个用例的命名生成器  
def min{a, b} = a  
def min{a, b if b < a} = b  

生成器定义的结构是 name{params} = body。body 可以是单个表达式，或者是由 {} 包围的多个表达式组成的块。
命名生成器是语句而不是表达式：def name{params} = body。name 后面可以跟多个参数列表，定义一个嵌套生成器。这种形式也允许多个定义。当调用生成器时，会从最后一个开始扫描这些定义，找到适用于参数的那个。也就是说，应用生成器时，它会测试参数是否满足其所有条件，如果匹配则运行，否则调用上一个定义。
有时以相同的方式扩展多个生成器很有用；请参见 extend 了解此用例。
函数也可以有生成器参数。这种情况在函数部分讨论。

参数匹配

生成器定义仅在其指定的参数列表与给定的参数匹配时才被使用，从而允许多个定义有效。
除了名称之外，参数列表可以包含隐式和显式约束，例如：

• 参数数量
• 同名的两个参数必须匹配
• par:typ 参数必须是一个带类型的值
• 显式条件 if cond 必须成立（结果为 1）
  完整的匹配和解构系统在 def 下描述。
  整个参数列表的匹配方式与元组相同。这也意味着（最多）一个参数槽可以是变长的，如果用前导 ... 标记。这个“收集”参数对应任意数量的输入，并定义为这些值的元组。例如，def tup{...t} = t 是内置 tup 的一个可能实现，它返回所有参数的元组。

展开语法

调用生成器时，任何参数槽前都可以加上 ...，将其从元组展开为多个参数。例如，gen{a, ...tup{b, c}, d} 展开为 gen{a, b, c, d}。
任何表达式都可以跟随：虽然 ... 不是操作符，但它的优先级被视为无限低。

部分应用

生成器可以通过在调用语法中使用 . 代替一个或多个参数来部分应用。这不会调用生成器，而是创建一个新的生成器，其参数用于那些 . 位置。例如，gen{., 5, .} 是一个有两个参数的生成器，当调用 {a, b} 时，结果是 gen{a, 5, b}。
一个参数槽也可以用 ... 替换，而无需任何后续表达式。这代表任意数量的参数，因此例如当用一个或多个值调用 gen{., 5, ...} 时，第一个用于 .，其余的传递到末尾 ... 所在的位置。

值的类型

生成器是一种值——也就是说，在编译时是一等公民。像大多数值一样，它在运行时不存在。希望它已经完成了需要做的事情！
事实上，它是更复杂的值类型之一。以下是完整列表：

数字字面量

number = repeat* ( scientific | base )
scientific = digit+ ( "." digit+ )? "e" "-"? digit+
base = ( "0x" | digit+ "b" ) ( digit | letter )+
repeat = digit+ ( "r" | "d" | "w" )

Singeli 中的数字以数字开头，但也可以包含字母、小数点 . 和内部的 -；开头的 - 不被解析为数字的一部分，而是作为单独的操作符。数字字面量中的字母不区分大小写，可以包含下划线，下划线会被忽略。
支持典型的科学计数法，如 45 或 1.3e-12。
整数十六进制字面量可以用 x 书写，如 0xf3cc0，但 b 可以用于更通用的进制。b 前的 2 到 36 之间的十进制数给出进制，如 2b110101 或 32b0jbm1。与十六进制一样，数字 9 后跟 a。
一个额外的前缀允许指定数字的重复。这会按书写的顺序重复尾数数字（包括前导 0），保持进制和指数不变。最低位数字始终相对于小数点保持其位置。可以指定多个前缀作为文档形式；它们必须具有相同的含义。

• r：重复完整的数字序列，3r12 表示 121212
• d：重复到指定的数字，5r123 表示 23123（从最低位数字开始）
• w：重复到指定位宽，10w0x4f 表示 0x34f（进制必须是 2 的幂）

定义

def 语句，语法为 def target = value，进行编译时定义。以这种方式定义的值在其作用域内是常量（遵循词法作用域规则），例外情况是，如果它是生成器，则仍然可以通过生成器定义语句（def target{params} = ...）进行扩展。更准确地说，定义在编译时保持不变。
如果它是一个寄存器，它将始终引用同一个寄存器，但该寄存器在运行时可以是可变的，允许其值自由更改为相同类型的另一个值。
使用 def 制作的每个可变寄存器副本都将反映这些更改，并且对其进行赋值会更改其值。

匹配

定义的目标可以是普通名称，但也允许其他形式，用于解构元组和类型，以及添加条件。其中一些对于生成器参数比 def 更有用，实际上，操作符 = 和 == 在 def 目标的顶层是不允许的。
这些是简单目标：

• 名称如 param 匹配任何值
• _ 匹配任何值但不分配名称
• 数字或符号字面量仅匹配该值
• (expr)，其中表达式 expr 在求值时必须匹配参数

这些是复合目标：

• a=b 独立匹配目标 a 和 b
• a==b 等同于 a=(b)
• a:T 匹配类型为 T 的带类型值 a
• *T 匹配指针类型
• [k]T 匹配向量类型
• {a,b,...} 匹配元组或元组类型

每个操作符（=、==、:、*、[k]）都是右结合的，也就是说，左侧只能是简单目标或元组，而右侧延伸到表达式末尾。例如，a:P=*V=[k]T 分组为 a:(P=(*(V=[k]T)))，以匹配类型为 P、*V 和 *[k]T 的变量 a。
此外，任何目标后面都可以跟一个条件，如 if a < 5。这里 if 必须在任何操作符之后，但它可以出现在元组匹配器的任何组件中，或者在向量类型匹配器的括号部分 [k] 中。
元组包含零个或多个目标（即使没有目标也可以有一个 if 条件），并且只匹配相同长度的元组或元组类型。然而，它也可以包含一个“收集”的变长槽，用前导 ... 表示，匹配零个或多个值——因此允许的总值数量是非收集目标的数量或更多。这些值被视为一个元组。所以目标 {...a} 与 a 相同，除了它要求匹配的值是元组，并且如果它碰巧是一个元组类型，它将被转换为类型元组。
一个最终的隐式条件是，任何出现多次的名称必须分配给匹配的值，因此 {a,a} 匹配 tup{3,3} 但不匹配 tup{3,4}。这不适用于占位符 _，因此 {_,_} 匹配任一元组。
带括号的表达式和条件可以自由使用目标中其他任何地方的名称。这是通过在所有其他匹配要求检查完毕且名称已定义后对它们进行求值来实现的。因此 {a if show{b>a}, b, b} 是一个完全正常的目标，并且 show 仅在两个 b 值都匹配的情况下显示。
if 条件的位置完全不影响其含义，除了条件的相对顺序控制它们的求值顺序。
注意 a:T 中的类型也是一个目标！像 a:[8]i16 这样的目标将同时分配给 a 和 i16。要指定 e