如何由erlang vm构建一个列表？

Question

当我在erlang中创建一个列表时,例如在erlang shell中:

1> [1, 2].

据我所知,在vm中,这个列表将被表示为单链表.

这个结构是如何由erlang运行时创建的？例如,它构造如下:

1. 在内存中创建一个结构来保存一个终止列表的列表
2. 在内存中创建一个结构来保存项目'2',以及对空列表的引用.
3. 在内存中创建一个结构来保存项目'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 实现。它有时被称为标记或类型化指针。（标签）此技术不会将目标类型存储在目标对象中（在本例中列出 CONS），而是存储在指针本身中，或者在通常是指针的位置保存标量值。它可以节省大量内存，尤其是在 LISP 或 Erlang 等动态类型语言中。（这在过去很有趣，当时内存非常昂贵，现在当 CPU 变得比内存快得多并且缓存未命中/命中决定算法的速度时，它再次变得重要。）作为一个缺点，它也会导致一些令人困惑的代码。处理列表构造的整个部分从erl_term.h 的第 216 行开始。你可以注意到有宏

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

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

_ET_DECLARE_CHECKED(Eterm,make_list,const Eterm*)

当用ET_DEBUG. （查看更多详细信息。） 宏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）。我希望这个描述对您有所帮助。