什么是Lincoln？

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

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

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

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

特性

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

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

概念

上下文

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

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

值

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

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

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

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

排列

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

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

指令集

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

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

每个代码条目都有一个名称。

代码引用

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

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

构建和运行程序

在控制台中运行以下命令：

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 的高级语言表示上面的事实示例，它看起来会像：

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)

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

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

进一步计划

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

生命周期？借用检查器？

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

前人智慧

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

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

联系我！

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

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

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