什么是Lincoln？

Lincoln被开发成一个新的编程环境，包括一个简单的IR，一个简单的解释器，以及后来的一些高级语言层。

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

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

Lincoln具有简单的操作语义：状态转换是确定的，并且总是O(1)。然而它也具有原生的指称语义。在Lincoln中，值不是像图灵机中的简单符号。它们是带有意义和内部状态的黑色盒子。

特点

• 极简主义：最少的内置操作（Jmp，Ret，Call），最少的内置类型（闭包类型）。
• 简单的解释：完整的解释器大约是1000行Rust代码，包括完整的类型定义，这要归功于极简主义设计。

此外，与其他编程平台不同，Lincoln不寻找大的“std”库。相反，每个Lincoln程序都应该是一个隔离的、抽象的构建块，依赖于外界提供基本操作。它只保证，只要外部提供的部分完成了它们的任务，Lincoln程序就会执行它应该执行的操作。

概念

上下文

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

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

值

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

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

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

• 外部类型。Lincoln不理解这些类型，因此尝试丢弃或执行它们将导致错误。它们只能由外部代码生成和消费。

排列

当要执行一个后续操作时，我们使用排列来重新排序值。我们使用Fisher和Yates算法（但不是随机生成数字，而是指定数字）将排列映射到一组数字，然后将这些数字映射到一个单一的数字。

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

指令集

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

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

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

代码引用

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

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

构建和运行程序

在控制台运行以下代码

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”是一组外部函数，用于将纯Lincoln中定义的数字数据类型转换为和转换。

还提供了一套其他外部函数，即“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)

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

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

进一步计划

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

生命周期？借用检查器？

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

先前的艺术

不用说，林肯是介于图灵机和Lambda演算之间的一种东西。

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

联系我！

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

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

或者如果您不介意它公开，只需提出一个问题。