skx/slisp

来源：https://github.com/skx/slisp

slisp

本仓库包含 slisp，一个编译器，它读取 Lisp 程序作为输入，并生成面向 Linux/AMD64 的独立汇编表示。

该项目的命名源于“简单 Lisp”（Simple Lisp）或“Steve 的 Lisp”，任君选择。

Lisp 传统上是交互式的，并提供 REPL，但拥有编译版本仍然很有用，并且仍然允许大多数常见 Lisp 程序执行。

快速链接：

• INTRODUCTION.md
  • 各功能的简要高层概述。
• PRIMITIVES.md
  • 所有可用函数和特殊形式的详细列表。

示例

    ;; 阶乘。耶。
    (defun fact (n)
      (if (<= n 1) 1 (* n (fact (- n 1)))))

    ;; 入口点
    (defun main ()
      (println "显示一些阶乘：")
      (println (fact 4))
      (println (fact 5))
      (println (fact 9))
      (println (fact 10))

      ;; 退出码 - 如果你喜欢，可以用 "(exit 3)"
      0)

在 test/ 目录下有多个示例，包括：

• factorial.lisp
• fibonacci.lisp
• fizzbuzz.lisp

example.lisp 包含其他杂项代码片段，最后 brainfuck.lisp 包含一个实用/可用的 brainfuck 解释器。

需要注意的是，除非在命令行中添加 -stdlib=false，否则我们会为所有用户程序预置一个标准库函数。该库本身也是功能的一个有用参考/演示：

• stdlib.slisp —— 我们的标准库，用 slisp 自身编写。
  • 包含一个良好的 print 定义，能适当处理已知类型。
  • 包含 map、length 以及其他通用函数。

特性

• 支持绑定、函数、整数、字符串、lambda、列表等。
  • lambda 支持闭包。
  • 通过 int?、cons? 等函数进行运行时类型检测。
• 一个粗糙但就绪的 bump 分配器，用于堆分配的 cons 单元。
• 数学运算：
  • +、-、*、/ 和 %。
• 比较运算：
  • =、<、<=、>=、>，以及用于反转结果的 !。
• 特殊形式
  • (cond ..)
  • (defun ..)
  • (do ..)
  • (if ..)
  • (lambda ..)
  • (let ..)
  • (list ..)
  • (set! ..)

你可以在 PRIMITIVES.md 中查看我们所有原语的完整列表及其详细说明——包括内置特殊形式，以及标准库中那些用汇编或 slisp 自身实现的部分。

反特性：

• 无垃圾回收。
• 无宏。
  • 添加宏并非不可能，但如果没有 quote、quasiquote 等，工作量会很大。
• 无 quote。
  • 只有在你能够调用 eval 时才有用，而作为一个编译器？这不容易实现。

用法

构建编译器：

go build .

用它来编译并链接一个程序：

./slisp example.lisp  > example.s
nasm -f elf64 example.s
ld -o example example.o

最后执行你的程序：

./example

专业提示 如果你运行：

make clean all

当前目录下的所有 *.lisp 文件都会被编译。这样就避免了手动重定向、汇编或链接。不过，仅运行 “make clean example” 也会执行 example.lisp 文件，这样更简洁。

测试

test/ 目录下有一些功能测试程序，它们编译固定程序并将其输出与已知正确结果进行比较。你可以通过执行以下命令来运行这些测试：

cd test && make test

在顶层目录运行 make clean 将移除测试产物和编译后的程序。

除了功能测试，还有对内部实现包的 Go 语言测试，这些测试可以以标准方式执行：

$ go test ./...
ok      github.com/skx/slisp	0.004s
ok      github.com/skx/slisp/compiler	0.009s
ok      github.com/skx/slisp/env	(cached)
ok      github.com/skx/slisp/lexer	0.008s
ok      github.com/skx/slisp/parser	0.006s

此外，还支持 Go 提供的模糊测试。你可以通过执行以下命令运行五分钟的模糊测试（删除 -fuzztime=300s 可以无限运行，删除 -parallel=1 可以同时运行多个实例）：

$ go test -fuzztime=300s -parallel=1 -fuzz=FuzzProject -v

动机

我花了几周时间为我自制语言 s-lang (https://github.com/skx/s-lang) 编写了一个编译器。最初该语言只使用整数，后来我添加了浮点数/字符串/指针，并在值的低位中使用了适当的类型标记。

我发现处理类型和语法开销有点复杂，并且有点把自己逼入了死角——我编写了一个相当完整的标准库，包含文件 I/O、getenv 和其他功能。

然而，添加更多类型和动态功能感觉过于复杂，因为这将涉及大量重写我之前完成的工作：编译器、标准库以及两者之间的接口。

于是这个仓库诞生了：

• 实现一个编译器。
• 从一开始就具有正确的类型系统。使用宏来提高可读性并最大限度地减少出错的可能性。
• 使用广为人知的 SysV ABI，而不是我自制的替代方案。
• 使用 Lisp，因为它的语法很容易解析。
  • 我以前曾为其编写过解释器，所以虽有挑战，但相对友好。

这个编译器已经比 s-lang 更“真实”和“可用”，尽管它在质量、标准库、测试用例和创意方面有所欠缺。不过归根结底，两者都是玩具，都是为我的个人学习而存在的。