erlang - Erlang VM (BEAM) 是如何构造列表的？

Question

当我在 Erlang 中创建列表时，例如在 Erlang shell 中:

1> [1, 2].

据我了解，在虚拟机中，这个列表将被表示为一个单链表。

这个结构是如何由 Erlang 运行时创建的？例如，它是否构造了这样的东西:

在内存中创建一个结构来保存一个终止列表的列表

在内存中创建一个结构来保存项目“2”，以及对空列表的引用。

在内存中创建一个结构来保存项目“1”和对项目“2”的引用。

我认为以下 c 和 erlang 代码是完成大部分工作的地方是否正确？

https://github.com/erlang/otp/blob/maint/lib/stdlib/src/lists.erl

https://github.com/erlang/otp/blob/maint/erts/emulator/beam/erl_bif_lists.c

https://github.com/erlang/otp/blob/maint/erts/emulator/beam/erl_term.h

https://github.com/erlang/otp/blob/maint/erts/emulator/beam/erl_term.c

erl_term.h包含一个宏 make_list但我还没有找到实现...

Answer 1

Erlang VM 实现 BEAM 使用的技术可以追溯到 60 年代或 70 年代初的第一个 Lisp 实现。它有时被称为标记或类型指针。 ( Tags ) 此技术不将目标类型存储在目标对象中(在这种情况下列出 CONS)，而是在指针本身中或在通常是指针的位置保存标量值。它可以节省大量内存，尤其是在 LISP 或 Erlang 等动态类型语言中。 (过去很有趣，当时内存非常昂贵，现在当 CPU 变得比内存快得多并且缓存未命中/命中决定了算法的速度时，它又变得重要了。)作为一个缺点，它也会导致代码有点困惑。整个处理列表构建的部分从line 216 of erl_term.h开始。 .你可以注意到有宏

#define _unchecked_make_list(x) ((Uint) COMPRESS_POINTER(x) + TAG_PRIMARY_LIST)

这是您正在寻找的宏。这是您的 make_list .线

_ET_DECLARE_CHECKED(Eterm,make_list,const Eterm*)

使用 ET_DEBUG 编译时会生成它的检查版本. (见 more details。)宏 make_list

#define make_list(x)        _ET_APPLY(make_list,(x))

只会调用 make_list 的选中或未选中版本.真正构建列表的宏是

#define CONS(hp, car, cdr) \
        (CAR(hp)=(car), CDR(hp)=(cdr), make_list(hp))

#define CAR(x)  ((x)[0])
#define CDR(x)  ((x)[1])

列表单元格结构只是两个连续的 Uint堆上的值( hp )，该地址被压缩和标记(参见 _unchecked_make_list )。我希望这个描述对你有帮助。