14

我正在编写一种动态类型的语言。目前,我的对象以这种方式表示:

struct Class { struct Class* class; struct Object* (*get)(struct Object*,struct Object*); };
struct Integer { struct Class* class; int value; };
struct Object { struct Class* class; };
struct String { struct Class* class; size_t length; char* characters; };

目标是我应该能够将所有内容作为 a 传递struct Object*,然后通过比较class属性来发现对象的类型。例如,要转换一个整数以供使用,我只需执行以下操作(假设它integer的类型为struct Class*):

struct Object* foo = bar();

// increment foo
if(foo->class == integer)
    ((struct Integer*)foo)->value++;
else
    handleTypeError();

问题是,据我所知,C 标准没有承诺如何存储结构。在我的平台上,这有效。但是在另一个平台上struct String可能会存储value之前class和当我foo->class在上面访问时,我实际上会访问foo->value,这显然很糟糕。可移植性是这里的一个大目标。

这种方法有替代方案:

struct Object
{
    struct Class* class;
    union Value
    {
        struct Class c;
        int i;
        struct String s;
    } value;
};

这里的问题是联合使用的空间与可以存储在联合中的最大事物的大小一样多。鉴于我的某些类型比其他类型大很多倍,这意味着我的小类型 ( int) 将占用与我的大类型 ( map) 一样多的空间,这是一个不可接受的权衡。

struct Object
{
    struct Class* class;
    void* value;
};

这会产生一定程度的重定向,从而减慢速度。速度是这里的目标。

最后一种选择是传递void*s 并自己管理结构的内部。例如,要实现上面提到的类型测试:

void* foo = bar();

// increment foo
if(*((struct Class*) foo) == integer)
    (*((int*)(foo + sizeof(struct Class*))))++;
else
    handleTypeError();

这给了我想要的一切(便携性、不同类型的不同尺寸等),但至少有两个缺点:

  1. 丑陋,容易出错 C. 上面的代码只计算了单个成员的偏移量;对于比整数更复杂的类型,情况会变得更糟。我也许可以使用宏来缓解这个问题,但无论如何这都会很痛苦。
  2. 由于没有struct代表对象,我没有堆栈分配的选项(至少没有在堆上实现我自己的堆栈)。

基本上,我的问题是,我怎样才能在不付钱的情况下得到我想要的东西?有没有一种方法可以移植,不同类型的大小有差异,不使用重定向,并保持我的代码漂亮?

编辑:这是我收到的关于 SO 问题的最佳回复。选择答案很困难。所以只允许我选择一个答案,所以我选择了一个能引导我找到解决方案的答案,但你们都收到了赞成票。

4

6 回答 6

7

C 为您提供了足够的保证,即您的第一种方法将起作用。您需要进行的唯一修改是,为了使指针别名正常,您必须有一个union包含struct您正在转换的所有 s 的范围内:

union allow_aliasing {
    struct Class class;
    struct Object object;
    struct Integer integer;
    struct String string;
};

(您不需要联合用于任何事情 - 它只需要在范围内)

我相信标准的相关部分是这样的:

[#5] 除了一个例外,如果联合对象的成员的值在对象的最近存储是不同成员时使用,则行为是实现定义的。一个特殊的保证是为了简化联合的使用:如果联合包含多个共享一个公共初始序列的结构(见下文),并且如果联合对象当前包含这些结构之一,则允许检查公共它们中的任何一个的初始部分,在任何地方都可以看到已完成联合类型的声明。如果对应的成员对于一个或多个初始成员的序列具有兼容的类型(并且对于位域,具有相同的宽度),则两个结构共享一个共同的初始序列。

(这并没有直接说没关系,但我相信它确实保证如果两个structs 有一个共同的初始序列并一起放入一个联合中,它们将以相同的方式排列在内存中 - 这当然是惯用的C 很长时间来假设这个,反正)。

于 2009-09-28T05:13:32.077 回答
7

有关 Python 如何使用标准 C 解决此问题,请参阅 Python PEP 3123 ( http://www.python.org/dev/peps/pep-3123/)。Python解决方案可以直接应用于您的问题。基本上你想这样做:

struct Object { struct Class* class; };
struct Integer { struct Object object; int value; };
struct String { struct Object object; size_t length; char* characters; };

如果您知道您的对象是整数,则可以安全地Integer*转换为Object*Object*to 。Integer*

于 2009-09-28T07:18:12.030 回答
3

ISO 9899:1999(C99 标准)的第 6.2.5 节说:

结构类型描述了一个顺序分配的非空成员对象集(在某些情况下,一个不完整的数组),每个对象都有一个可选的指定名称和可能的不同类型。

第 6.7.2.1 节还说:

如 6.2.5 所述,结构是由一系列成员组成的类型,其存储按有序顺序分配,联合是由一系列成员存储重叠的类型。

[...]

在结构对象中,非位域成员和位域所在的单元的地址按声明顺序递增。一个指向结构对象的指针,经过适当的转换,指向它的初始成员(或者如果该成员是位域,则指向它所在的单元),反之亦然。结构对象中可能有未命名的填充,但不是在其开头。

这保证了您所需要的。

在你说的问题中:

问题是,据我所知,C 标准没有承诺如何存储结构。在我的平台上,这有效。

这将适用于所有平台。这也意味着您的第一个替代方案 - 您当前正在使用的 - 足够安全。

但是在另一个平台上,struct String Integer 可能会在 class 之前存储 value,当我在上面访问 foo->class 时,我实际上会访问 foo->value,这显然很糟糕。可移植性是这里的一个大目标。

不允许任何兼容的编译器这样做。[假设您指的是第一组声明,我将 String 替换为 Integer 。仔细检查后,您可能指的是具有嵌入式联合的结构。编译器仍然不允许重新排序classvalue. ]

于 2009-09-28T06:10:14.383 回答
3

实现动态类型有 3 种主要方法,哪一种最好取决于具体情况。

1)C风格的继承:第一个显示在Josh Haberman的回答中。我们使用经典的 C 风格继承创建类型层次结构:

struct Object { struct Class* class; };
struct Integer { struct Object object; int value; };
struct String { struct Object object; size_t length; char* characters; };

具有动态类型参数的函数将它们接收为Object*,检查class成员,并酌情进行强制转换。检查类型的成本是两个指针跃点。获取基础值的成本是一个指针跳。在像这样的方法中,对象通常在堆上分配,因为在编译时对象的大小是未知的。由于大多数 `malloc 实现一次至少分配 32 个字节,因此使用这种方法小对象可能会浪费大量内存。

2) 标记联合:我们可以使用“短字符串优化”/“小对象优化”删除访问小对象的间接级别:

struct Object {
    struct Class* class;
    union {
        // fundamental C types or other small types of interest
        bool as_bool;
        int as_int;
        // [...]
        // object pointer for large types (or actual pointer values)
        void* as_ptr;
    };
};

具有动态类型参数的函数将它们接收为Object,检查class成员,并酌情读取联合。检查类型的成本是一个指针跳。如果类型是特殊的小类型之一,则直接存储在联合中,没有间接取值。否则,需要一跳指针来检索该值。这种方法有时可以避免在堆上分配对象。尽管在编译时仍然不知道对象的确切大小,但我们现在知道union容纳小对象所需的大小和对齐方式(我们的)。

在前两种解决方案中,如果我们在编译时知道所有可能的类型,我们可以使用整数类型而不是指针对类型进行编码,并将类型检查间接减少一个指针跳。

3) Nan-boxing:最后是nan-boxing,每个对象句柄只有64位。

double object;

任何对应于非 NaN 的值double都被理解为简单的 a double。所有其他对象句柄都是 NaN。在常用的 IEEE-754 浮点标准中,实际上存在大量对应于 NaN 的双精度浮点数位值。在 NaN 空间中,我们使用一些位来标记类型,其余位用于数据。利用大多数 64 位机器实际上只有 48 位地址空间这一事实,我们甚至可以将指针存储在 NaN 中。这种方法不会产生间接或额外的内存使用,但会限制我们的小对象类型,很尴尬,而且理论上不可移植 C。

于 2016-11-20T20:54:54.460 回答
2

问题是,据我所知,C 标准没有承诺如何存储结构。在我的平台上,这有效。但是在另一个平台上struct String可能会存储value之前class和当我foo->class在上面访问时,我实际上会访问foo->value,这显然很糟糕。可移植性是这里的一个大目标。

我相信你在这里错了。首先,因为你struct String没有value会员。其次,因为我相信 C确实保证了结构成员的内存布局。这就是为什么以下是不同大小的原因:

struct {
    short a;
    char  b;
    char  c;
}

struct {
    char  a;
    short b;
    char  c;
}

如果 C 不做任何保证,那么编译器可能会将两者优化为相同的大小。但它保证了结构的内部布局,因此自然对齐规则开始起作用并使第二个大于第一个。

于 2009-09-28T05:16:22.943 回答
2

我很欣赏这个问题和答案提出的迂腐问题,但我只想提一下,CPython“或多或少地永远”使用了类似的技巧,并且它已经在各种各样的 C 编译器中工作了几十年。具体来说,请参见object.h、宏之类PyObject_HEAD的 、结构之类PyObject的:各种 Python 对象(在 C API 级别)正在获取指向它们的指针,它们永远来回转换,PyObject*而不会造成任何伤害。自从我上次使用 ISO C 标准玩海上律师以来已经有一段时间了,以至于我手边没有副本(!),但我确实相信那里有一些限制应该让它继续工作已经将近20年...

于 2009-09-28T05:27:18.617 回答