Stellvertretend für dynamische Typisierung in C

StackOverflow https://stackoverflow.com/questions/1485505

  •  18-09-2019
  •  | 
  •  

Frage

Ich schreibe eine dynamisch typisierte Sprache. Derzeit sind meine Objekte auf diese Weise dargestellt werden: 

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

Das Ziel ist es, dass ich in der Lage sein, alles soll um als struct Object* passiert und entdecken dann die Art des Objekts durch das class Attribut zu vergleichen. Um zum Beispiel eine ganze Zahl für die Verwendung werfen würde ich einfach Folgendes tun (unter der Annahme, dass integer vom Typ struct Class*): 

struct Object* foo = bar();

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

Das Problem ist, dass, soweit ich weiß, der C-Standard keine Versprechungen, wie Strukturen gespeichert macht. Auf meiner Plattform funktioniert dies. Aber auf einer anderen Plattform struct String könnte speichern value vor class und wenn ich foo->class in der oben zugegriffen würde ich tatsächlich zugreifen foo->value, was natürlich schlecht. Portabilität ist ein großes Ziel hier.

Es gibt Alternativen zu diesem Ansatz: 

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

Das Problem hierbei ist, dass die Union so viel Platz wie die Größe der größten Sache verbraucht, die in der Union gespeichert werden können. Da einige meiner Typen oft so groß wie meine anderen Typen sind, würde dies bedeuten, dass meine kleine Typen (int) würde so viel Platz wie meine große Typen (map) aufnehmen, die eine nicht akzeptable Kompromiss ist. 

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

Dies schafft eine Ebene der Umleitung, die Dinge verlangsamen wird. Geschwindigkeit ist ein Ziel hier.

Die letzte Alternative ist, um void*s zu passieren und die Interna der Struktur selbst zu verwalten. Um zum Beispiel der Typenprüfung zu implementieren oben erwähnt: 

void* foo = bar();

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

Das gibt mir alles, was ich (Portabilität, verschiedene Größen für verschiedene Arten, etc.) will aber mindestens zwei Nachteile:

  1. Hideous, fehleranfällig C. Der obige Code nur berechnet ein Einmann-Offset; es wird viel schlimmer mit Typen komplexer als ganze Zahlen bekommen. Vielleicht kann ich diese ein wenig lindern Makros, aber das wird ganz gleich, was schmerzhaft sein.
  2. Da es kein struct ist, der das Objekt darstellt, ich habe nicht die Möglichkeit, Stapelzuordnungen (zumindest ohne meinen eigenen Stack auf dem Heap Implementierung).

Im Grunde ist meine Frage, wie kann ich bekommen, was ich für sie, ohne bezahlen will? Gibt es eine Möglichkeit tragbar zu sein, hat die Varianz in der Größe für die verschiedenen Arten, nicht-Umleitung verwenden, und halten Sie meinen Code recht?

EDIT: Dies ist die beste Antwort, die ich je für eine SO Frage erhalten. eine Antwort Wahl war hart. SO nur erlaubt mir eine Antwort zu wählen, so dass ich den einen entschied, die mich zu meiner Lösung führen, aber Sie erhielten alle upvotes.

War es hilfreich?

Lösung

Siehe Python PEP 3123 ( http://www.python.org/dev/ Pep / pep-3123 / ), wie Python, dieses Problem unter Verwendung von Standard C. Der Python-Lösung löst direkt auf Ihr Problem angewandt werden kann. Im Grunde wollen Sie dies tun: 

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

Sie können sicher werfen Integer* Object* und Object* Integer*, wenn Sie wissen, dass Ihr Objekt ist eine ganze Zahl.

Andere Tipps

C gibt Ihnen ausreichend garantiert, dass Ihr ersten Ansatz funktioniert. Die einzige Änderung, die Sie machen müssen, ist, dass, um den Zeiger Aliasing OK zu machen, können Sie einen union in Umfang haben müssen, die alle der structs enthält, die Sie werfen zwischen: 

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

(Sie müssen nicht immer auf verwenden die Vereinigung für alles - es muss nur in Umfang sein)

Ich glaube, dass der relevante Teil des Standards ist dies:

  

[# 5] Mit einer Ausnahme, wenn der Wert   ein Mitglied einer Vereinigung Objekt wird verwendet,   wenn der letzte Laden des   Aufgabe war es zu einem anderen Element, das   Verhalten ist die Implementierung definiert.   Eine besondere Garantie wird gemacht, um   die Verwendung von Gewerkschaften zu vereinfachen: Wenn ein   Vereinigung enthält mehrere Strukturen, die   teilen sich eine gemeinsame Anfangsfolge (siehe   unten), und wenn die Vereinigung Objekt   Derzeit enthält eine davon   Strukturen, ist es erlaubt, zu inspizieren   der gemeinsame Anfangsteil eines von ihnen   überall, dass eine Erklärung der   abgeschlossene Art der Vereinigung ist   sichtbar. Zwei Strukturen eine gemeinsame   Anfangsfolge, wenn entsprechende   Mitglieder haben kompatible Typen (und,   für Bit-Felder, die gleichen Breiten) für eine   Sequenz von einem oder mehreren Anfängen   Mitglieder.

(Dies gilt nicht direkt sagen, es ist in Ordnung, aber ich glaube, dass es keine Garantie, dass, wenn zwei structs eine gemeinsame intial Sequenz aufweisen und in einer Vereinigung zusammengefügt, werden sie verlegt werden im Speicher die gleiche Art und Weise - gewesen, es ist sicherlich idiomatische C für eine lange Zeit, dies zu übernehmen, jedenfalls)

.

Abschnitt 6.2.5 von ISO 9899: 1999 (der C99-Standard) sagt:

  

A-Strukturtyp beschreibt einen sequentiell zugeordneten nicht-leeren Satz von Elementobjekte (und unter bestimmten Umständen eine unvollständige Array), von denen jede eine gegebenenfalls angegebenen Namen und möglicherweise unterschiedlichen Typs.

Abschnitt 6.7.2.1 auch sagt:

  

Wie in 6.2.5 beschrieben, ist eine Struktur mit einer Art von einer Folge von Elementen besteht, deren Speicherung in einer geordneten Folge zugeordnet ist, und eine Vereinigung ist eine Art, bestehend aus einer Folge von Elementen, deren Lagerung überlappen.

     

[...]

     

Innerhalb eines Strukturobjekts, die Nicht-Bit-Feld Elemente und die Einheiten, in denen Bit-Felder   haben residieren-Adressen, die in der Reihenfolge zu erhöhen, in der sie deklariert ist. Ein Zeiger auf eine   Strukturobjekt, in geeigneter Weise umgewandelt, weist auf sein Ausgangselement (oder, wenn das Element eine   Bit-Feld, dann an die Einheit, in der er sich befindet), und umgekehrt. Es kann nicht namentlich sein   Polsterung in einem Strukturobjekt, aber nicht am Anfang.

Dies garantiert, was Sie brauchen.

In der Frage, die Sie sagen:

  

Das Problem ist, dass, soweit ich weiß, der C-Standard keine Versprechungen, wie Strukturen gespeichert macht. Auf meiner Plattform funktioniert dies.

Dies wird auf allen Plattformen funktionieren. Es bedeutet auch, dass Ihre erste Alternative - was Sie derzeit verwenden -. Sicher genug ist,

  

Aber auf einer anderen Plattform-Struktur String Integer könnte Wert speichern, bevor Klasse und wenn ich foo- zugegriffen> Klasse in der oben würde ich tatsächlich zugreifen foo-> Wert, der offensichtlich schlecht ist. Portabilität ist ein großes Ziel hier.

Nein konformer Compiler erlaubt, das zu tun. [ I ersetzt String nach Integer vorausgesetzt, Sie auf den ersten Satz von Erklärungen beziehen wurden. Bei näherer Betrachtung meinen Sie mit einer eingebetteten Vereinigung der Struktur könnten worden. Der Compiler noch nicht class und value neu zu ordnen erlaubt. ]

Es gibt drei wichtige Ansätze für die Implementierung dynamischer Typen und welche man am besten auf die Situation abhängig ist.

1) C-Stil Vererbung: Die erste ist in Josh Haberman Antwort gezeigt. Wir schaffen eine Art Hierarchie klassische C-Stil Vererbung: 

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

Funktionen mit dynamisch typisierten Argumente erhalten sie als Object*, überprüfen Sie die class Mitglied und warf als angemessen. Die Kosten für den Typ ist zwei Zeiger Hopfen zu überprüfen. Die Kosten für den zugrunde liegenden Wert zu erhalten, ist ein Zeiger Hop. In Ansätzen wie diese, werden Objekte typischerweise auf dem Heap zugewiesen, da die Größe von Objekten bei der Kompilierung unbekannt ist. Da die meisten `malloc Implementierungen ein Minimum von 32 Bytes zu einer Zeit zuteilen, kleine Objekte, die eine erhebliche Menge an Speicher mit diesem Ansatz verschwenden kann.

2) Stichwort Vereinigung: Wir können die „kurze String-Optimierung“ / „kleines Objekt Optimierung“, um eine Dereferenzierungsebene entfernen für den Zugriff auf kleine Objekte mit: 

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

Funktionen mit dynamisch typisierten Argumenten erhalten sie als Object, überprüfen Sie das class Mitglied, und gegebenenfalls die Union lesen. Die Kosten für die Art zu überprüfen, ist ein Zeiger Hop. Wenn der Typ eine der speziellen kleinen Typen ist, wird es direkt in der Union gespeichert werden, und es gibt keine indirection den Wert abzurufen. Andernfalls wird ein Zeiger Hop erforderlich, um den Wert abzurufen. Dieser Ansatz kann manchmal vermeiden Objekte auf dem Heap zugewiesen werden. Obwohl die genaue Größe eines Objekts noch nicht zum Zeitpunkt der Kompilierung bekannt ist, wissen wir nun die Größe und Ausrichtung (unsere union) benötigt, um kleine Objekte aufzunehmen.

In diesen ersten zwei Lösungen, wenn wir alle möglichen Arten zum Zeitpunkt der Kompilierung bekannt ist, können wir die Art mit einem Integer-Typ anstelle eines Zeigers kodieren und Typprüfung indirection durch einen Zeiger Hop reduzieren.

3) Nan-Boxen. Schließlich gibt es nan-Box, wo jedes Objekt-Handle ist nur 64 Bits 

double object;

Jeder Wert auf einen Nicht-NaN double entspricht, wird verstanden einfach ein double sein. Alles anderes Objekt-Handles ist ein NaN. Es gibt tatsächlich große Schwaden von Bitwerten von doppelter Genauigkeit Schwimmer, die in den üblicherweise verwendeten IEEE-754-Standard-Gleitkomma NaN entsprechen. Im Raum von NaNs verwenden wir ein paar Bits Typen und die verbleibenden Bits für Daten zu markieren. Durch die Nutzung der Tatsache, dass die meisten 64-Bit-Rechner eigentlich nur einen 48-Bit-Adressraum, können wir sogar Stash Zeiger in NaNs. Diese Methode verursacht keine Indirektion oder zusätzliche Speicher zu verwenden, sondern schränkt unsere kleine Objekttypen, ist umständlich, und in der Theorie ist nicht tragbar C.

  

Das Problem ist, dass, soweit ich weiß, der C-Standard keine Versprechungen, wie Strukturen gespeichert macht. Auf meiner Plattform funktioniert dies. Aber auf einer anderen Plattform struct String könnte speichern value vor class und wenn ich foo->class in der oben zugegriffen würde ich tatsächlich zugreifen foo->value, was natürlich schlecht. Portabilität ist ein großes Ziel hier.

Ich glaube, Sie hier falsch. Erstens, weil Ihr struct String keinen value Mitglied. Zweitens, weil ich glaube, C hat das Layout im Speicher der struct-Mitglieder garantieren. Deshalb sind die folgenden Größen: 

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

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

Wenn C keine Garantien gemacht, dann wäre Compiler wahrscheinlich diese beiden optimieren die gleiche Größe zu sein. Aber es garantiert die interne Layout Ihrer structs, so dass die natürlichen Regeln Ausrichtung treten in und machen die zweite größer als die erste.

Ich schätze die pedantisch Probleme mit dieser Frage und Antworten angehoben, aber ich wollte nur erwähnen, dass CPython Ähnliche Tricks verwendet hat „mehr oder weniger für immer“ und es ist seit Jahrzehnten in einer Vielzahl von C-Compiler arbeiten. Insbesondere finden Sie unter object.h , Makros wie PyObject_HEAD, structs wie PyObject: alle Arten von Python-Objekten (unten an der C-API-Ebene) werden immer Zeiger auf sie immer hin und her zu / von PyObject* ohne Schaden getan werfen. Es ist schon eine Weile her, seit ich das letzte Mal Meer Anwalt mit einem ISO-C-Standard, auf den Punkt gespielt, die ich (!) Keine Kopie zur Hand haben, aber ich glaube, dass es einige Einschränkungen gibt, die sollte diese keep machen funktioniert, wie es seit fast 20 Jahren ...

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top