如何用erlang vm构造列表？ [英] how is a list constructured by the erlang vm?

问题描述

当我在erlang中创建列表时，例如在erlang shell中：

  1> [1,2]。 
  

根据我的理解，在vm中，该列表将被表示为单链表。 p>

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

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


2. 在内存中创建一个保存项目'2'的结构，并引用空列表。


3. 在内存中创建一个结构来保存项目'1' ，并提到项目'2'。

我正在思考以下c和erlang代码是大部分工作完成了？

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


• < a href =https://github.com/erlang/otp/blob/maint/erts/emulator/beam/erl_bif_lists.c =nofollow> https://github.com/erlang/otp/blob/ main / 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 但我还没有找到实现...

解决方案

Erlang VM实现BEAM使用这种技术可追溯到60年代或70年代初的第一个Lisp实现。它有时被称为标记或类型的指针。 （标签）此技术不目标对象中的目标对象的存储类型（在这种情况下列出了CONS），但是在指针本身中，或者将标量值保存在通常是指针的位置。它允许保存相当好的内存，特别是在LISP或Erlang的动态类型语言中。 （这是有趣的，当记忆非常昂贵，现在变得重要，当CPU变得比内存快得多，缓存未命中/命中决定了算法的速度。）作为一个缺点，它也导致一点点混乱的代码。处理列表构造的整个部分从行开始216的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 编译时，将会进行检查。 （请参见详细信息）。宏 make_list

  #define make_list ）_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]）$ ​​b $ b  

列表单元格结构只是两个连续的 Uint 值（ hp ），该地址是压缩和标记（见 _unchecked_make_list ）。我希望这个描述可以帮助你。

When I create a list in erlang, such as in the erlang shell:

1> [1, 2].

From what I understand, in the vm this list will be represented as a singly linked list.

How is this structure created by the erlang runtime? For example, is it constructed something like this:

1. create a structure in memory to hold an list that terminates the list
2. create a structure in memory to hold the item '2', and a reference to the empty list.
3. create a structure in memory to hold the item '1', and a reference to item '2'.

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

erl_term.h contains a macro make_list but I haven't been able to find the implementation yet...

解决方案

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)

which is macro you are looking for. It is your make_list. The line

_ET_DECLARE_CHECKED(Eterm,make_list,const Eterm*)

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))

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])

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构造列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！