Erlang VM（BEAM）如何构造列表？ [英] How is a list constructed by the Erlang VM (BEAM)?
问题描述
当我在Erlang中创建列表时，例如在Erlang shell中：
When I create a list in Erlang, such as in the Erlang shell:
1> [1, 2].
据我了解，在vm中，此列表将表示为单链接列表。
From what I understand, in the vm this list will be represented as a singly linked list.
Erlang运行时如何创建此结构？例如，是否构造了这样的东西：
How is this structure created by the Erlang runtime? For example, is it constructed something like this:
- 在内存中创建一个结构来保存一个终止列表的列表
- 在内存中创建一个结构来保存项 2，并引用空列表。
- 在内存中创建一个结构来保存项 1 ，以及对项目'2'的引用。
我正确地认为以下c和erlang代码是工作完成了吗？
Am I correct in thinking the following c and erlang code is where the bulk of the work is done?
- > 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
- 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 ，但是我还没有找到实现...
erl_term.h contains a macro make_list but I haven't been able to find the implementation yet...
推荐答案
Erlang VM实施BEAM使用的技术可以追溯到60年代或70年代初的第一个Lisp实施。有时称为标记或类型化指针。 （标签）技术不会将目标的类型存储在目标对象中（在这种情况下为CONS），而是存储在指针本身中，或者将标量值保存在通常为指针的位置。它可以节省大量内存，尤其是在使用LISP或Erlang等动态类型的语言时。 （在过去，内存非常昂贵，而如今，当CPU变得比内存快得多并且缓存未命中/命中率决定了算法的速度时，重新变得很重要，这是很有趣的。）作为缺点，它还导致代码有些混乱。整个列表构建部分始于 erl_term.h 的第216行。您可以注意到有一个宏
The Erlang VM implementation BEAM uses a technique which dates back to first Lisp implementations back to the 60s or early 70s. It is sometimes referred as tagged or typed pointers. (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. You can note there is macro
#define _unchecked_make_list(x) ((Uint) COMPRESS_POINTER(x) + TAG_PRIMARY_LIST)
这是您要查找的宏。这是您的 make_list 。该行
which is macro you are looking for. It is your make_list. The line
_ET_DECLARE_CHECKED(Eterm,make_list,const Eterm*)
使用 ET_DEBUG 进行编译时，将对其进行检查。 （请参见更多详细信息。）宏 make_list
Would make a checked version of it when compiled with ET_DEBUG. (See more details.) Macro make_list
#define make_list(x) _ET_APPLY(make_list,(x))
只需调用已检查或 unchecked 版本的 make_list 。真正构造列表的宏是
would just call the checked or unchecked version of make_list. The macros which really constructing list are
#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 ），其地址是压缩的和 tagged （请参见 _unchecked_make_list ）。希望此说明对您有所帮助。
The list cell structure is simply two consecutive Uint values on the heap (hp) which address is compressed and tagged (See _unchecked_make_list). I hope this description helps you.
这篇关于Erlang VM（BEAM）如何构造列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
