Erlang VM (BEAM) 是如何构建列表的？

Question

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

1> [1, 2].

据我了解，在 vm 中，此列表将表示为单链表。

Erlang 运行时是如何创建这个结构的？例如，它是不是这样构造的：

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

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

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

Answer 1

Erlang VM 实现 BEAM 使用的技术可以追溯到 60 年代或 70 年代初的第一个 Lisp 实现。它有时被称为标记指针或类型指针。（Tags) This technique does not store type of a target in a target object (lists CONS in this case) but in the pointer itself or save a scalar value in the place where is usually a pointer. It allows save a quite good amount of memory especially in dynamically typed languages as LISP or Erlang. (It was interesting in old days when memory was very expensive and become important again nowadays when CPU become much faster than memory and cache miss/hit determines a speed of algorithms.) As a drawback, it also leads to a little bit confusing code. The whole part which deals with list construction starts at 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))

只会调用 checked 或 unchecked 版本的 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)，地址是 compressed 和 tagged （参见 _unchecked_make_list）。希望以上描述对您有所帮助。

Erlang VM (BEAM) 是如何构建列表的？

How is a list constructed by the Erlang VM (BEAM)?

erlang