什么是林肯？

林肯被开发成一个新的编程环境，包括一个简单的中间表示（IR）、一个简单的解释器和以后的一些高级语言层。

IR也设计成适合作为许多其他编程语言的目标形式，尽管这些语言的语义通常相当不同。

在计算机科学中，林肯位于两个其他简单模型之间：图灵机和λ演算。图灵机具有简单的操作语义，但缺乏指称语义，这意味着您需要正式描述“状态”和带符号的纸带上的符号的含义，机器的定义无法告诉您任何关于它的事情。另一方面，λ演算具有丰富的指称语义，但难以定义操作语义——单个替换可以是任意复杂的，而归约的顺序是不确定的。

林肯具有简单的操作语义：状态转换是确定的，并且始终是O(1)。然而，它也有本地的指称语义。在林肯中，值不是像图灵机中的简单符号。它们是可以携带意义和内部状态的黑色盒子。

特性

• 极简主义：最小化的内置操作（Jmp、Ret、Call），最小化的内置类型（闭包类型）。
• 简单的解释：完整的解释器大约有1000行Rust代码，包括完整的类型定义，这得益于极简的设计。

此外，与其他编程平台不同，林肯并不寻求一个大型的“std”库。相反，每个林肯程序都应该是一个隔离的、抽象的构建块，它依赖于外部世界提供基本操作。它只保证，只要外部提供者履行了他们的职责，林肯程序就会做它应该做的事情。

概念

上下文

上下文是一组值。在上下文上的基本操作包括：将上下文分成两部分，或将两个上下文合并为一个，或从上下文中取出一个值，或使用排列来重新排列值。这两种操作都应该是O(1)操作。

如何表示上下文由解释器决定。在这个演示解释器中，我们将其表示为向量，但它可以是CPU的寄存器集合、一块内存、网站的cookie，或任何其他东西。

值

上下文中的值可以分为两类

• 闭包。这是林肯唯一的“内置”类型。它们可以在林肯内部创建和执行（使用）。它非常丰富，能够表示其他语言中熟悉的各种类型，包括

  • 元组或积类型
  • 枚举或求和类型
  • 交集类型或具有多个消费方法的对象

• 外部类型。林肯不了解这些类型，因此尝试删除或执行它们将导致错误。它们只能由外部代码生成和消费。

排列

当一个延续即将执行时，我们使用排列来重新排序值。我们使用费舍尔-耶茨算法（但不是随机生成数字，而是指定数字）将排列映射到一组数字，然后将这些数字映射到一个单独的数字。

解释器的实现需要支持至少6个变量，因为这正是8位整数可以表示的排列数量。

指令集

程序包含一组代码条目，或指令。有3种不同的代码条目

• 跳转。在当前上下文中执行排列后，跳转到另一个条目或外部函数。它必须指定要跳转到的位置。
• 调用。在当前上下文中使用部分当前上下文和一个条目组或外部函数创建一个值。然后跳转到另一个条目或外部函数。它必须指定要调用的条目，然后指定返回的位置。
• 返回。从上下文中取出一个值，然后在指定的变体上使用当前上下文的其余部分执行该值。如果该值是闭包，这意味着将使用指定的条目组的变体，并且捕获的值将与当前上下文合并。

每个代码条目都由一个名称引用。

代码引用

在讨论代码条目中的“另一个条目或外部函数”时，我指的是代码引用。代码引用指向以下之一

• 条目。一个代码条目。
• 外部。程序中定义的“外部”函数。
• 外部函数。外部世界可以提供的“外部”函数，但不在程序中定义。
• 终止。指示执行已完成。

构建和运行程序

在控制台运行以下内容

git clone https://github.com/earthengine/lincoln
cargo run

程序将显示一个提示

Lincoln> 

现在你可以运行一些命令，例如

entry: call entry1 1 from
entry1: jmp count #!ba
set export entry

你可以使用保存命令将你的工作保存到json文件

save myprogram.json

或重新加载它

load myprogram.json

然后你可以通过以下方式编译程序

compile bint

其中“bint”是一组外部函数，用于将纯林肯中定义的数字数据类型转换为其对应的类型。

还提供了一组其他外部函数，即“fact”，它使用执行器的本地数据类型。

要运行程序，请使用

run entry 0 10

并得到类似的结果

Result(1/1): 10

示例

给出了两个示例程序

bint.json

这是如何定义可复制本地数据类型的一个演示。要运行，请使用以下命令

load bint.json
compile bint
run test_copy 0 "10usize"

目前只支持“usize”类型，它通常是系统中的64位无符号整数。

运行此命令应得到以下结果

Result(1/2): 10
Result(2/2): 10

fact.json

这是如何定义完全依赖于外部世界提供所需函数的算法的一个演示。

要运行，请使用以下命令

load fact.json
compile fact
run fact 0 "10usize"

你期望得到以下结果

Result(1/1): 3628800

未来开发

林肯的简约设计意味着当前的IR（中间表示）可能会像现在一样冻结。一些想法

• 可复制类型 - 由外部条目提供 - "复制"条目始终可以复制值。此外，如果它捕获的所有变量都是可复制的，则可以有一个"可复制"闭包：它只是一个额外的闭包变体，它会复制其捕获的变量。
• 可丢弃类型 - 与可复制类型相同。它们可以是外部类型，或者是一个不执行任何操作的额外变体。

高级语言的建议

如果我们用类似于Haskell的高级语言表示上面提到的fact示例，它看起来会是这样

extern zero
extern one
extern copy_int
extern eq
extern drop_int
extern minus
extern mul

fact c n := -- a definition of `fact`, takes variable `c` and `n`
    f =     -- an assignment, which is always lazy
        call c n := fact c n -- a definition of a variant "call"
        drop c := c          -- another variant "drop"
    zero -> z                -- an invocation, result are in `z`
    one -> o                 -- `zero` and `one` are external
    copy_int n -> n1 n2      -- `copy_int` is external
    eq n1 z                  -- Without the arrow, the group of variants simple values only
        equals :=
            drop_int n2 ->       -- `drop_int` is external
            f.drop ->        -- call the `drop` variant of f
            c o              -- the final statement
        not_equal := 
            copy_int n2 -> n1 n2
            minus n1 o -> n    -- minus is external
            c = _ n :=         -- Assign a closure to `c`
                mul n n2 -> n  -- mul is external
                c n
            f.call c n         -- call the `call` variant of f (recursion)

上面的示例展示了基本思想

• 所有变量都必须定义一次，并且只使用一次
• 内部作用域可以遮蔽外部作用域中的同一变量。在这种情况下，外部变量不会被捕获，因此仍然有效，并且必须在其他地方使用。
• 赋值是惰性的，调用是急切的。两者都可以用来定义变量。
• 赋值的右侧是一个闭包。闭包的第一个变体可以是未命名的。

进一步计划

上述语言不是静态类型，但我们应该能够为其提供一个类型系统。

生命周期？借用检查器？

如果我们谈论未来的静态类型语言，是的，它们将被考虑。否则，想象一个像上述那样在运行时检查的动态类型语言并不困难。

已有技术

无需再次提及，林肯（Lincoln）是图灵机与λ演算之间的某种东西。

还有一个类似的想法，例如B Geron的继续演算。我的系统与之不同，因为它具有线性性：B Geron的系统允许自由复制和丢弃项，而我的系统则不允许。

联系我！

如果您对这个项目感兴趣，请通过以下方式与我联系

• https://www.linkedin.com/in/zhiyu-ren-51a48620/

如果您不想将其公开，只需提出问题即可。