Representando tipagem dinâmica em C

Question

Eu estou escrevendo uma linguagem dinamicamente digitado. Atualmente, meus objetos são representados da seguinte maneira:

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

O objetivo é que eu deveria ser capaz de passar tudo ao seu redor como um struct Object* e, em seguida, descobrir o tipo do objeto, comparando o atributo class. Por exemplo, para lançar um inteiro para uso eu simplesmente fazer o seguinte (assumir que integer é do tipo struct Class*):

struct Object* foo = bar();

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

O problema é que, tanto quanto eu sei, o padrão C não faz promessas sobre como estruturas são armazenados. Em minha plataforma isso funciona. Mas em outro struct String plataforma pode armazenar value antes class e quando eu acessada foo->class na foo->value acima eu seria realmente o acesso, que é obviamente ruim. A portabilidade é um grande objetivo aqui.

Existem alternativas para essa abordagem:

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

O problema aqui é que a união usa tanto espaço como o tamanho do maior coisa que pode ser armazenado na união. Tendo em conta que alguns dos meus tipos são muitas vezes tão grande quanto meus outros tipos, isso significaria que os meus pequenos tipos (int) iria ocupar tanto espaço quanto meus grandes tipos (map), que é uma compensação inaceitável.

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

Isso cria um nível de redirecionamento que irá retardar as coisas. A velocidade é um objetivo aqui.

A última alternativa é passar em torno void*s e gerenciar os internos da estrutura de mim mesmo. Por exemplo, para implementar o ensaio do tipo mencionado acima:

void* foo = bar();

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

Isso me dá tudo que eu quero (portabilidade, tamanhos diferentes para diferentes tipos, etc.), mas tem pelo menos duas desvantagens:

1. Hideous, propenso a erros C. O código acima só calcula um deslocamento single-membro; ele vai ficar muito pior com os tipos mais complexos do que os inteiros. Eu poderia ser capaz de aliviar esta um pouco usando macros, mas isso vai ser doloroso não importa o que.
2. Como não há struct que representa o objeto, eu não tenho a opção de alocações de pilha (pelo menos sem implementar a minha própria pilha na pilha).

Basicamente, a minha pergunta é, como posso conseguir o que quero sem pagar por isso? Existe uma maneira para ser portátil, tem variação em tamanho para diferentes tipos, não usar o redirecionamento, e manter meu código bonita?

EDIT: Esta é a melhor resposta que eu já recebidos para uma pergunta SO. Escolhendo uma resposta foi difícil. Assim, só me permite escolher uma resposta assim que eu escolhi o que me levar a minha solução, mas todos receberam upvotes.

Answer 1

Veja Python PEP 3123 ( http://www.python.org/dev/ peps / PEP-3123 / ) para Python como resolve este problema utilizando uma solução padrão C. O pitão pode ser directamente aplicada no seu problema. Essencialmente, você quer fazer isso:

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

Você pode lançar com segurança Integer* para Object* e Object* para Integer* se você sabe que seu objeto é um inteiro.

Answer 2

C lhe dá garantias suficientes de que a sua primeira abordagem irá funcionar. A única modificação que você precisa fazer é que, a fim de tornar o ponteiro aliasing OK, você deve ter um union no escopo que contém todos os structs que você está lançando entre:

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

(Você não precisa nunca uso a união para qualquer coisa - ele só tem que estar no escopo)

Eu acredito que a parte relevante do padrão é o seguinte:

[# 5] Com uma exceção, se o valor de um membro de um objeto de união é utilizado quando a loja mais recente para o objectivo era um membro diferente, o comportamento é definido pela implementação. Uma garantia especial é feita em ordem para simplificar o uso dos sindicatos: Se um união contém várias estruturas que partilhar uma sequência inicial comum (ver abaixo), e se o objeto união atualmente contém um destes estruturas, é permitido para inspecionar a parte inicial comum de qualquer um deles em qualquer lugar que uma declaração do Tipo concluída da união é visível. Duas estruturas partilham uma comum sequência inicial se correspondendo membros têm tipos compatíveis (e, para campos de bit, as mesmas larguras) para uma sequência de uma ou mais inicial membros.

(Isto não diretamente dizer que é OK, mas acredito que ele faz garantia de que se dois structs ter uma seqüência intial comum e são colocados em uma união juntos, eles vão ser definidos na memória da mesma forma - é certamente sido idiomática C por um longo tempo para assumir isso, de qualquer maneira)

.

Answer 3

Secção 6.2.5 da ISO 9899: 1999 (o padrão C99) diz:

Um tipo de estrutura descreve um conjunto não vazio sequencialmente atribuídos de objectos membros (e, em certas circunstâncias, uma matriz incompleto), cada um dos quais tem um nome especificado e opcionalmente tipo possivelmente distinta.

Seção 6.7.2.1 também diz:

Como discutido em 6.2.5, uma estrutura é de um tipo que consiste de uma sequência de membros, cujo armazenamento é alocado numa sequência ordenada, e uma união é um tipo que consiste de uma sequência de membros, cujos sobreposição de armazenamento.

[...]

Dentro de um objeto de estrutura, os membros não-bit-campo e as unidades em que campos de bit residem têm endereços que o aumento na ordem em que elas são declaradas. Um ponteiro para uma estrutura objeto, adequadamente convertido, pontos ao seu membro inicial (ou se este membro é um campo de bits, em seguida, para a unidade na qual reside), e vice-versa. Pode haver sem nome preenchimento dentro de um objeto de estrutura, mas não em seu início.

Isto garante que você precisa.

Na pergunta você diz:

O problema é que, tanto quanto eu sei, o padrão C não faz promessas sobre como estruturas são armazenados. Em minha plataforma isso funciona.

Isto irá funcionar em todas as plataformas. Isso também significa que a sua primeira alternativa - o que você está usando -. É seguro o suficiente

Mas em outra plataforma struct string Integer pode armazenar o valor antes da aula e quando eu acessei foo-> classe no foo-> valor acima de eu realmente estar acessando, que é obviamente ruim. A portabilidade é um grande objetivo aqui.

No compilador compatível é permitido fazer isso. [ Eu substituí Cordas por Integer supondo que você estava referindo-se ao primeiro conjunto de declarações. Numa análise mais aprofundada, você pode estar se referindo à estrutura com uma união incorporado. O compilador ainda não é permitido class reordenar e value. ]

Answer 4

Existem 3 principais abordagens para a implementação de tipos dinâmicos e qual é o melhor depende da situação.

1) C-estilo herança: A primeira é mostrada na resposta de Josh Haberman. Nós criar uma hierarquia de tipo usando a herança clássica 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; };

As funções com argumentos tipagem dinâmica recebê-los como Object*, inspecionar o membro class, e elenco, conforme apropriado. O custo para verificar o tipo é dois saltos ponteiro. O custo para obter o valor subjacente é um hop ponteiro. Em abordagens como este, os objetos são normalmente alocados na pilha uma vez que o tamanho dos objetos é desconhecido em tempo de compilação. Como a maioria dos `implementações malloc alocar um mínimo de 32 bytes de cada vez, pequenos objetos podem perder uma quantidade significativa de memória com esta abordagem.

2) união Tagged: Nós podemos remover um nível de engano para acessar pequenos objetos usando a "otimização corda curta" / "pequena otimização objeto":

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

As funções com argumentos tipagem dinâmica recebê-los como Object, inspecionar o membro class, e ler a união conforme o caso. O custo para verificar o tipo é um hop ponteiro. Se o tipo é uma das pequenas tipos especiais, ele é armazenado diretamente na união, e não há engano para recuperar o valor. Caso contrário, um hop ponteiro é necessário para recuperar o valor. Esta abordagem pode, por vezes, evitar a alocação de objetos na pilha. Embora o tamanho exato de um objeto ainda não é conhecido em tempo de compilação, agora sabemos o tamanho e alinhamento (nosso union) necessária para acomodar pequenos objetos.

Nestas duas primeiras soluções, se sabemos todos os tipos possíveis em tempo de compilação, que pode codificar o tipo usando um tipo inteiro em vez de um ponteiro e reduzir tipo indireto de verificação por um hop ponteiro.

3) Nan-boxing:. Finalmente, há nan-boxing onde cada objeto identificador é de apenas 64 bits

double object;

Qualquer valor correspondente a um double não-NaN é entendido como sendo simplesmente uma double. Todas as outras alças do objeto são um NaN. Na verdade, existem grandes áreas de valores de precisão dupla bit flutua que correspondem a NaN no IEEE-754 padrão de ponto flutuante comumente usado. No espaço de Nans, usamos alguns bits para tipos de etiquetas e os restantes bits para dados. Tirando proveito do fato de que a maioria das máquinas de 64 bits na verdade só tem um espaço de endereçamento de 48 bits, podemos até ponteiros Stash em NaNs. Este método não incorre engano ou extra de uso de memória, mas restringe nossos tipos de objetos pequenos, é estranho, e em teoria não é portátil C.

Answer 5

O problema é que, tanto quanto eu sei, o padrão C não faz promessas sobre como estruturas são armazenados. Em minha plataforma isso funciona. Mas em outro struct String plataforma pode armazenar value antes class e quando eu acessada foo->class na foo->value acima eu seria realmente o acesso, que é obviamente ruim. A portabilidade é um grande objetivo aqui.

Eu acredito que você está errado aqui. Em primeiro lugar, porque o seu struct String não tem um membro value. Em segundo lugar, porque acredito C faz garantir o layout em memória dos membros da sua estrutura. É por isso que a seguir são de tamanhos diferentes:

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

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

Se C feita nenhuma garantia, em seguida, compiladores provavelmente otimizar tanto daqueles a ser do mesmo tamanho. Mas ele garante o layout interno das suas estruturas, de modo que as regras alinhamento natural chutar e fazer a segunda maior do que o primeiro.

Answer 6

Eu aprecio as questões pedantes levantadas por esta pergunta e respostas, mas eu só queria mencionar que CPython usou truques semelhantes "mais ou menos para sempre" e que tem trabalhado durante décadas através de uma enorme variedade de compiladores C. Especificamente, consulte object.h , macros como PyObject_HEAD, estruturas como PyObject: todos os tipos de objetos Python (para baixo no nível API C) estão recebendo ponteiros para eles para sempre expressos e para trás de / para PyObject* com nenhum dano feito. Tem sido um advogado tempo desde a última vez que jogou mar com um C padrão ISO, a tal ponto que eu não tenho uma cópia acessível (!), Mas eu acredito que existem algumas restrições lá que deve fazer este continuar trabalhando, pois tem por quase 20 anos ...