Представление динамической типизации в C

https://stackoverflow.com/questions/1485505

18-09-2019
|

Вопрос

Я пишу динамически типизированный язык.В настоящее время мои объекты представлены следующим образом:

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; };

Цель состоит в том, чтобы я мог передавать все как 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();

Это дает мне все, что я хочу (мобильность, разные размеры для разных типов и т. д.), но имеет как минимум два недостатка:

Отвратительный, склонный к ошибкам C.Приведенный выше код вычисляет только смещение одного элемента;с типами, более сложными, чем целые числа, будет намного хуже.Возможно, мне удастся немного облегчить это с помощью макросов, но это все равно будет болезненно.
Поскольку нет struct который представляет объект, у меня нет возможности выделения стека (по крайней мере, без реализации моего собственного стека в куче).

По сути, мой вопрос: как я могу получить то, что хочу, не заплатив за это?Есть ли способ обеспечить переносимость, иметь различия в размерах для разных типов, не использовать перенаправление и сохранить красивый код?

РЕДАКТИРОВАТЬ:Это лучший ответ, который я когда-либо получал на вопрос SO.Выбрать ответ было сложно.ТАК позволяет мне выбрать только один ответ, поэтому я выбрал тот, который привел меня к моему решению, но вы все получили голоса «за».

Решение

См. Python PEP 3123 (http://www.python.org/dev/peps/pep-3123/) о том, как Python решает эту проблему с помощью стандарта C.Решение 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* к Integer* если вы знаете, что ваш объект является целым числом.

Другие советы

C дает вам достаточные гарантии того, что ваш первый подход будет работать.Единственное изменение, которое вам нужно сделать, это то, что для корректного использования псевдонимов указателя у вас должен быть union в области видимости, которая содержит все structs, которые вы выполняете между:

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

(Вам не нужно когда-либо использовать объединение для чего угодно — оно просто должно быть в области видимости)

Я считаю, что соответствующая часть стандарта такова:

#5] за одним исключением, если значение объекта Union используется, когда самый последний магазин для объекта был для другого участника, поведение определяется внедрением.Одна специальная гарантия сделана для упрощения использования профсоюзов:Если профсоюз содержит несколько структур, которые имеют общую начальную последовательность (см. Ниже), и если объект Union в настоящее время содержит одну из этих структур, разрешено осмотреть общую начальную часть любой из них в любом месте, что объявление за завершенным типом Союза видны.Две структуры разделяют общую начальную последовательность, если соответствующие элементы имеют совместимые типы (и, для битовых полей, одинаковую ширину) для последовательности одного или нескольких начальных элементов.

(Это не напрямую говорю, что все в порядке, но я считаю, что это гарантирует, что если двое structимеют общую начальную последовательность и объединяются вместе, они будут располагаться в памяти одинаково - в любом случае, в течение долгого времени это было идиоматическим языком C).

Раздел 6.2.5 ISO 9899:1999 (стандарт C99) гласит:

Тип структуры описывает последовательно выделенный непустой набор объектов-членов (и, в определенных обстоятельствах, неполный массив), каждый из которых имеет необязательно указанное имя и, возможно, отдельный тип.

В разделе 6.7.2.1 также говорится:

Как обсуждалось в 6.2.5, структура — это тип, состоящий из последовательности элементов, память которых распределяется в упорядоченной последовательности, а объединение — это тип, состоящий из последовательности элементов, хранилища которых перекрываются.

[...]

В пределах объекта структуры, небиточные элементы и подразделения, в которых проживают битовые поля, имеют адреса, которые увеличиваются в порядке, в котором они объявлены.Указатель на объект структуры, который соответственно преобразован, указывает на своего начального элемента (или, если этот член является бит-полем, то на единицу, в котором он находится), и наоборот.В пределах объекта структуры может быть неназванная прокладка, но не в его начале.

Это гарантирует то, что вам нужно.

В вопросе вы говорите:

Проблема в том, что, насколько мне известно, стандарт C не дает никаких обещаний относительно того, как хранятся структуры.На моей платформе это работает.

Это будет работать на всех платформах.Это также означает, что ваша первая альтернатива — то, что вы используете сейчас — достаточно безопасна.

Но на другой платформе ~~Нить~~Integer может хранить значение перед классом, и когда я обращался к foo->class в приведенном выше примере, я фактически получал доступ к foo->value, что явно плохо.Мобильность здесь является большой целью.

Ни один совместимый компилятор не может этого сделать.[Я заменил String на Integer, предполагая, что вы имеете в виду первый набор объявлений.При ближайшем рассмотрении вы, возможно, имели в виду структуру со встроенным объединением.Компилятору по-прежнему не разрешено переупорядочивать class и value.]

Существует три основных подхода к реализации динамических типов, и какой из них лучше, зависит от ситуации.

1) Наследование в стиле C: Первый показан в ответе Джоша Хабермана.Мы создаем иерархию типов, используя классическое наследование в стиле 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) Нан-бокс: Наконец, есть нанбокс, где каждый дескриптор объекта имеет длину всего 64 бита.

double object;

Любое значение, соответствующее не-NaN double понимается просто как double.Все остальные дескрипторы объектов имеют значение NaN.На самом деле существуют большие диапазоны битовых значений чисел с плавающей запятой двойной точности, которые соответствуют NaN в широко используемом стандарте с плавающей запятой IEEE-754.В пространстве NaN мы используем несколько битов для обозначения типов, а остальные биты — для данных.Воспользовавшись тем фактом, что большинство 64-битных машин на самом деле имеют только 48-битное адресное пространство, мы можем даже хранить указатели в NaN.Этот метод не требует косвенного обращения или дополнительного использования памяти, но ограничивает типы наших небольших объектов, неудобен и теоретически не переносим на C.

Проблема в том, что, насколько мне известно, стандарт 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 не давал никаких гарантий, то компиляторы, вероятно, оптимизировали бы оба файла до одинакового размера.Но это гарантирует внутреннюю компоновку ваших структур, поэтому вступают в силу естественные правила выравнивания и делают вторую структуру больше первой.

Я ценю педантичность вопросов, поднятых этим вопросом и ответами, но я просто хотел упомянуть, что CPython использовал подобные приемы «более или менее всегда» и десятилетиями работал в огромном разнообразии компиляторов C.В частности, см. объект.h, макросы типа PyObject_HEAD, такие структуры, как PyObject:все виды объектов Python (на уровне API C) получают указатели на них, которые постоянно перебрасываются туда и обратно в/из PyObject* без какого-либо вреда.Прошло много времени с тех пор, как я в последний раз играл в морского юриста по стандарту ISO C, до такой степени, что у меня нет под рукой копии (!), но я верю, что здесь есть некоторые ограничения, которые должен пусть это продолжает работать так, как работает уже почти 20 лет...

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow