什么是Lincoln？

Lincoln是为了成为一个新的编程环境而开发的，包括简单的IR、简单的解释器和后来的一些高级语言层。

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

在计算机科学中，Lincoln位于两个其他简单模型之间：图灵机和λ演算。图灵机具有简单的操作语义，但缺乏指称语义，这意味着您需要正式描述一个“状态”和一条带符号的带子代表什么，机器的定义不能告诉您任何关于它的信息。另一方面，λ演算具有完整的指称语义，但很难定义操作语义——一个单一的替换可以是任意复杂的，且约简的顺序是不确定的。

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

特性

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

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

概念

上下文

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

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

值

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

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

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

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

排列

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

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

指令集

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

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

每个代码条目都通过名称引用。

代码引用

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

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

构建和运行程序

在控制台中运行以下内容

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

程序将显示一个提示

Lincoln> 

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

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

您可以使用save命令将您的作品保存到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)

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

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

进一步计划

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

生命周期？借用检查器？

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

相关艺术

不用说，林肯介于图灵机和 Lambda 演算之间。

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

联系我！

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

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

或者如果你不介意它是公开的，只需提出一个问题即可。