Representación de tipado dinámico en C

Question

Escribo un lenguaje de tipado dinámico. Actualmente, mis objetos están representados de esta manera:

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

El objetivo es que debería ser capaz de pasar todo a su alrededor como un struct Object* y luego descubrir el tipo del objeto comparando el atributo class. Por ejemplo, para emitir un número entero para su uso yo simplemente hacer lo siguiente (a suponer que integer es de tipo struct Class*):

struct Object* foo = bar(); 

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

El problema es que, por lo que yo sé, el estándar de C no hace promesas sobre cómo se almacenan las estructuras En mi plataforma, esto funciona. Pero en otra plataforma struct String podría almacenar value antes de class y cuando accedí al foo->class en el cuadro anterior, estaría accediendo a foo->value, lo cual es obviamente malo. La portabilidad es un gran objetivo aquí.

Hay alternativas a este enfoque:

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

El problema aquí es que la unión utiliza tanto espacio como el tamaño de la cosa más grande que se puede almacenar en la unión. Dado que algunos de mis tipos son muchas veces más grandes que mis otros tipos, esto significaría que mis tipos pequeños (int) ocuparían tanto espacio como mis tipos grandes (map), lo cual es una compensación inaceptable.

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

Esto crea un nivel de redirección que ralentizará las cosas. La velocidad es un objetivo aquí.

La última alternativa es pasar alrededor de void* sy gestionar las partes internas de la estructura yo mismo. Por ejemplo, para poner en práctica el ensayo del tipo mencionado anteriormente:

void* foo = bar(); 

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

Esto me da todo lo que quiero (portabilidad, diferentes tamaños para diferentes tipos, etc.) pero tiene al menos dos inconvenientes:

1. horrible , propenso a errores C. El código anterior solo calcula una compensación de un solo miembro; empeorará con tipos más complejos que enteros. Tal vez pueda aliviar esto un poco usando macros, pero esto será doloroso sin importar qué.
2. Dado que no hay struct que represente el objeto, no tengo la opción de asignaciones de pila (al menos sin implementar mi propia pila en el montón).

Básicamente, mi pregunta es, ¿cómo puedo obtener lo que quiero sin tener que pagar por ello? ¿Hay alguna manera de ser portátil, tener una variación en el tamaño para diferentes tipos, no utilizar la redirección, y mantener mi código bonito?

EDITAR: Esta es la mejor respuesta que he recibido para una pregunta ASÍ. Elegir una respuesta fue difícil. SO solo me permite elegir una respuesta, así que elegí la que me condujo a mi solución, pero todos ustedes recibieron votos por contestar.

Answer 1

Consulte Python PEP 3123 (http://www.python.org/dev/peps/pep-3123/) para saber cómo Python resuelve este problema utilizando la norma C. La solución de Python se puede aplicar directamente a su problema.Esencialmente, usted quiere hacer esto:

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

Puedes lanzar con seguridad Integer*-Object* y Object*-Integer* si sabe que su objeto es un número entero.

Answer 2

C le ofrece suficientes garantías de que su primer enfoque funcionará.La única modificación que necesita hacer es que con el fin de hacer que el puntero aliasing OK, debe tener un union en su alcance que contiene todos los struct s que está Conversiones entre:

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

(Usted no lo hace necesita cada vez uso la unión para cualquier cosa - sólo tiene que estar en su alcance)

creo que la parte pertinente de la norma es la siguiente:

[# 5] con una excepción, si el valor de un miembro de un objeto de unión se utiliza cuando el más reciente tienda para el objeto fue a un miembro diferente, el comportamiento es definido por la implementación. Una garantía especial se hace con el fin para simplificar el uso de los sindicatos: Si una unión contiene varias estructuras que comparten una secuencia inicial común (véase más adelante), y si el objeto unión contiene actualmente una de estas estructuras, se permite inspeccionar la parte inicial común de cualquiera de ellos en cualquier lugar que una declaración del tipo completado de la unión es visible. Dos estructuras comparten una secuencia inicial si los miembros correspondientes tienen tipos compatibles (y, para campos de bits, el mismo ancho) para una secuencia de uno o más miembros iniciales .

(Esto no lo hace directamente dicen que está bien, pero yo creo que es garantía de que si dos struct s tienen una secuencia intial común y se ponen en una unión en conjunto, van a estar expuesto en memoria de la misma manera - ciertamente ha sido idiomático C durante mucho tiempo para asumir esto, de todos modos).

Answer 3

El problema es que, hasta donde yo sé, el estándar C no promete cómo se almacenan las estructuras. En mi plataforma, esto funciona. Pero en otra plataforma struct String podría almacenar value antes class y cuando tuve acceso foo->class en lo anterior me gustaría ser en realidad el acceso foo->value, lo que obviamente es mala. La portabilidad es un gran objetivo aquí.

creo que estás equivocado aquí. En primer lugar, debido a que su struct String no tiene un miembro value. En segundo lugar, porque creo C hace garantizar la disposición en memoria de los miembros de su estructura. Es por eso que los siguientes son los tamaños diferentes:

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

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

Si C hace ninguna garantía, entonces probablemente compiladores optimizar ambas cosas a tener el mismo tamaño. Pero garantiza el diseño interno de sus estructuras, por lo que las reglas de alineación natural se activan y hacen que la segunda sea más grande que la primera.

Answer 4

Aprecio los pedantes problemas planteados por esta pregunta y respuestas, pero solo quería mencionar que CPython ha usado trucos similares "más o menos para siempre" y ha estado trabajando durante décadas en una gran variedad de compiladores de C.Específicamente, vea object.h, macros como PyObject_HEAD, estructuras como PyObject: todos los tipos de objetos de Python (abajo en el nivel de API de C) están recibiendo punteros para siempre lanzados hacia y desde PyObject* sin daño alguno. Ha pasado un tiempo desde la última vez que jugué con un abogado de mar con un estándar ISO C, hasta el punto de que no tengo una copia a mano (!), Pero creo que hay algunas restricciones allí que deberían hacer que esto siga funcionando como lo ha hecho durante casi 20 años ...

Answer 5

la sección 6.2.5 de la norma ISO 9899: 1999 (el estándar C99) dice:

un tipo de estructura se describe una forma secuencial asignado conjunto no vacío de objetos miembro (y , en determinadas circunstancias, una matriz incompleta), cada una de las cuales tiene un nombre opcionalmente especificado y posiblemente un tipo distinto.

Sección 6.7.2.1 también dice:

Como se discutió en 6.2.5, una estructura es un tipo que consta de una secuencia de los miembros, cuyo almacenamiento se asigna en una secuencia ordenada, y una unión es un tipo que consiste en una secuencia de miembros cuyo almacenamiento se superpone.

[...]

Dentro de un objeto de estructura, los miembros no-bits de campo y las unidades en que los campos de bits residen tienen direcciones que aumentan en el orden en que se declaran. Un puntero a un objeto de estructura , adecuadamente convertido, apunta a su miembro inicial (o si ese miembro es un campo de bit , luego a la unidad en la que reside), y viceversa. Puede haber un relleno sin nombre dentro de un objeto de estructura, pero no al principio.

Esto garantiza lo que necesita.

En la pregunta que dicen:

El problema es que, por lo que yo sé, el estándar de C no hace promesas sobre cómo se almacenan las estructuras. En mi plataforma, esto funciona.

Esto funcionará en todas las plataformas. También significa que su primera alternativa, lo que está usando actualmente, es lo suficientemente segura.

Pero en otra plataforma struct cadena entero podría almacenar el valor antes de la clase y cuando tuve acceso foo-> clase de lo anterior que en realidad sería accediendo foo-> valor, lo que obviamente es mala. La portabilidad es un gran objetivo aquí.

Ningún compilador compatible puede hacerlo. [Reemplacé Cadena por entero suponiendo que se estaba refiriendo al primer conjunto de declaraciones. En un examen más detallado, es posible que se haya estado refiriendo a la estructura con una unión incrustada. El compilador todavía no puede reordenar class y value.]

Answer 6

Existen 3 enfoques principales para implementar tipos dinámicos y cuál es el mejor depende de la situación.

1) C-style inheritance: El primero se muestra en la respuesta de Josh Haberman. Creamos un tipo de jerarquía utilizando la herencia clásica de estilo C:

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

funciones con argumentos tipos dinámicos ellos reciben como Object*, inspeccionar el miembro de class, y echó en su caso. El costo de verificar el tipo es de dos saltos de puntero. El costo para obtener el valor subyacente es un salto de puntero. En enfoques como este, los objetos normalmente se asignan en el montón ya que el tamaño de los objetos se desconoce en el momento de la compilación. Como la mayoría de las implementaciones `malloc asignan un mínimo de 32 bytes a la vez, los objetos pequeños pueden desperdiciar una cantidad significativa de memoria con este enfoque.

2) unión Etiquetado: podemos quitar un nivel de indirección para acceder a los objetos pequeños utilizando la "optimización de cadena corta"/"optimización objeto pequeño":

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

funciones con tipos dinámicos argumentos los reciben como Object, inspeccione el miembro class y lea la unión según corresponda. El costo para verificar el tipo es un salto de puntero. Si el tipo es uno de los tipos pequeños especiales, se almacena directamente en la unión, y no hay indirección para recuperar el valor. De lo contrario, se requiere un salto de puntero para recuperar el valor. Este enfoque a veces puede evitar la asignación de objetos en el montón. Aunque aún no se conoce el tamaño exacto de un objeto en el momento de la compilación, ahora sabemos el tamaño y la alineación (nuestro union) necesarios para acomodar objetos pequeños.

En estas dos primeras soluciones, si conocemos todos los tipos posibles en tiempo de compilación, podemos codificar el tipo utilizando un tipo entero en lugar de un puntero y reducir la indirección de verificación de tipo mediante un salto de puntero.

3) Nan-boxing: Finalmente, hay nan-boxing donde cada objeto se maneja es de solo 64 bits.

double object; 

Cualquier valor correspondiente a una no-NaN double se entiende que ser simplemente un double. Todos los demás identificadores de objeto son un NaN. En realidad, hay grandes franjas de valores de bit de flotantes de doble precisión que corresponden a NaN en el estándar de punto flotante IEEE-754 comúnmente utilizado. En el espacio de NaNs, utilizamos algunos bits para etiquetar tipos y los bits restantes para datos. Al aprovechar el hecho de que la mayoría de las máquinas de 64 bits solo tienen un espacio de direcciones de 48 bits, incluso podemos almacenar punteros en NaN. Este método no implica indirección ni uso de memoria adicional, pero restringe nuestros pequeños tipos de objetos, es incómodo y, en teoría, no es portátil C.