تمثيل الكتابة الديناميكية في ج

Question

أنا أكتب لغة مكتوبة ديناميكيا. حاليا، يتم تمثيل كائناتي بهذه الطريقة:

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();

هذا يعطيني كل ما أريد (إمكانية النقل، أحجام مختلفة لأنواع مختلفة، إلخ) ولكن لديها اثنين من الهبوط على الأقل:

1. البشعة، عرضة للخطأ C. التعليمات البرمجية أعلاه تحسب فقط إزاحة عضو واحد؛ سوف تحصل أسوأ بكثير مع أنواع أكثر تعقيدا من الأعداد الصحيحة. قد أكون قادرا على تخفيف هذا قليلا باستخدام وحدات الماكرو، لكن هذا سيكون مؤلما بغض النظر عن ما.
2. لأنه لا يوجد struct هذا يمثل الكائن، ليس لدي خيار مخصصات المكدس (على الأقل دون تنفيذ مكدساتي على كومة).

في الأساس، سؤالي هو، كيف يمكنني الحصول على ما أريد دون دفع ثمنها؟ هل هناك طريقة لتكون محمولة، لها تباين في الحجم لأنواع مختلفة، وليس استخدام إعادة التوجيه، والحفاظ على رمز بلدي جميلة؟

تحرير: هذا هو أفضل استجابة تلقيتها على الإطلاق للحصول على سؤال حتى الآن. كان اختيار إجابة صعبة. لذلك فقط يسمح لي فقط باختيار إجابة واحدة، لذا اخترت الشخص الذي يقودني إلى حلاي، لكنك تلقيت جميعا upvotes.

Answer 1

انظر بيثون بيب 3123 (http://www.python.org/dev/peps/pep-3123/) لكيفية حل ثعبان هذه المشكلة باستخدام C. يمكن تطبيق حل الثعبان مباشرة على مشكلتك. أساسا تريد القيام بذلك:

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* إذا كنت تعرف أن جسمك صحيح.

Answer 2

ج يمنحك ضمانات كافية أن نهجك الأول سيعمل. التعديل الوحيد الذي تحتاجه لجعله هو أنه من أجل جعل المؤشر يهيمون على مستوى موافق، يجب أن يكون لديك union في نطاق يحتوي على كل من structمن أنك تلتصق بين:

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

(لا تحتاج إلى أي وقت مضى استعمال الاتحاد لأي شيء - يجب أن يكون فقط في نطاق)

أعتقد أن الجزء ذو الصلة من المعيار هو:

# 5] مع استثناء واحد، إذا تم استخدام قيمة عضو في كائن نقابي عندما كان أحدث المتجر إلى الكائن عضوا مختلفا، فإن السلوك محدد بالتنفيذ. يتم إجراء ضمان خاص من أجل تبسيط استخدام النقابات: إذا كان الاتحاد يحتوي على العديد من الهياكل التي تشترك في تسلسل أولي مشترك (انظر أدناه)، وإذا كان كائن النقابة يحتوي حاليا على إحدى هذه الهياكل، فمن المسموح له بفحص المشترك الجزء الأولي من أي منهم في أي مكان أن إعلان النوع المكتمل من الاتحاد مرئي. تشترك هياكلان في تسلسل أولي مشترك إذا كان الأعضاء المقابلين لديهم أنواع متوافقة (وعلى حقول بت أو نفس العرض) للحصول على تسلسل واحد أو أكثر من الأعضاء الأوليين.

(هذا لا مباشرة قل أنه على ما يرام، لكنني أعتقد أنه يضمن ذلك إذا كان اثنان structلدى S تسلسلات مالية مشتركة ويتم وضعها في اتحاد معا، سيتم وضعها في الذاكرة بنفس الطريقة - من المؤكد أنها كانت oriomatic c منذ وقت طويل لنفترض ذلك، على أي حال).

Answer 3

القسم 6.2.5 من ISO 9899: 1999 (معيار C99) يقول:

يصف نوع الهيكل مجموعة غير متأثرة غير متأثرة من الكائنات الأعضاء (وفي ظروف معينة، توجد صفيف غير مكتملة)، لكل منها اسما محددا اختياريا ونوعا متميزا.

القسم 6.7.2.1 يقول أيضا:

كما تمت مناقشته في 6.2.5، فإن الهيكل هو نوع يتكون من سلسلة من الأعضاء، والذي يتم تخصيص تخزينها في تسلسل أمر، والاتحاد هو نوع يتكون من سلسلة من الأعضاء الذين يتداخلون التخزين.

[...]

ضمن كائن هيكل، فإن الأعضاء غير الميدانيين وغير الموجودين والوحدات التي يقيمون بها حقول بتاتين لها عناوين تزيد في الترتيب الذي تم الإعلان عنه فيه. مؤشر إلى كائن هيكل، يتم تحويله بشكل مناسب، يشير إلى عضوه الأولي (أو إذا كان هذا العضو حقل بعض الشيء، إلى الوحدة التي تقع فيها)، والعكس صحيح. قد تكون هناك حشوة لم تسمها داخل كائن هيكل، ولكن ليس في البداية.

هذا يضمن ما تحتاجه.

في السؤال الذي تقوله:

المشكلة هي أنه، بقدر ما أعرف، فإن المعيار C لا يقدم أي وعود حول كيفية تخزين الهياكل. على منصة بلدي هذا يعمل.

هذا سيعمل على جميع المنصات. وهذا يعني أيضا أن البديل الأول الخاص بك - ما تستخدمه حاليا - آمن بما فيه الكفاية.

ولكن على بنية منصة أخرى سلسلةقد يتم تخزين عدد صحيح القيمة قبل الفصل وعندما وصلت إلى فئة FOO-> في ما سبق، سأكون في الواقع الوصول إلى القيمة FOO->، والتي من الواضح أنها سيئة. القدرة هي هدف كبير هنا.

لا يسمح بمجموعة مترجم متوافقة للقيام بذلك. [لقد استبدلت السلسلة عن طريق عدد صحيح على افتراض أنك تشير إلى المجموعة الأولى من الإعلانات. عند الفحص الوثيق، قد تشعر بالإشارة إلى الهيكل بنقطة مضمنة. لا يزال المترجم غير مسموح به لإعادة ترتيبه class و value.]

Answer 4

هناك 3 طرق رئيسية لتنفيذ الأنواع الديناميكية والتي يعتمدها المرء على الوضع.

1) الميراث على غرار C: يظهر أول واحد في إجابة جوش هربمان. نخلق التسلسل الهرمي للنوع باستخدام ميراث نمط C Classic 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 العضو، والذي يلقي حسب الاقتضاء. تكلفة التحقق من النوع هي قفزات مؤشرين. التكلفة للحصول على القيمة الأساسية هي قفزة مؤشر واحد. في أساليب مثل هذا واحد، يتم تخصيص الكائنات عادة على كومة الكومة لأن حجم الكائنات غير معروف في وقت الترجمة. نظرا لأن معظم تطبيقات MALOC تخصيص ما لا يقل عن 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 حيث يكون كل مقبض كائن 64 بت فقط.

double object;

أي قيمة تتوافق مع غير نان double من المفهوم أن يكون ببساطة double. وبعد جميع مقابض الكائنات الأخرى هي نان. هناك بالفعل مسافات كبيرة من القيم بت العوامات الدقيقة المزدوجة التي تتوافق مع NAN في معيار النقطة العائمة IEEE-754 الشائعة الاستخدام. في مساحة NANS، نستخدم بعض البتات لأنواع العلامات والأجزاء المتبقية للبيانات. من خلال الاستفادة من حقيقة أن معظم الأجهزة 64 بت في الواقع تحتوي فقط على مساحة عنوان 48 بت، يمكننا حتى تخفيف المؤشرات في NANS. تتكبد هذه الطريقة لا تستخدم غير مباشر أو استخدام ذاكرة إضافية ولكنها تقييد أنواع كائناتنا الصغيرة، وهي محرجة، وفي النظرية ليست محمولة C.

Answer 5

المشكلة هي أنه، بقدر ما أعرف، فإن المعيار C لا يقدم أي وعود حول كيفية تخزين الهياكل. على منصة بلدي هذا يعمل. ولكن على منصة أخرى struct String قد تخزن value قبل class وعندما وصلت foo->class في ما سبق أود الوصول إليها foo->value, ، وهذا أمر سيء للغاية. القدرة هي هدف كبير هنا.

أعتقد أنك مخطئ هنا. أولا، لأنك struct String لا يملك value عضو. ثانيا، لأنني أصدق ج هل ضمان التخطيط في ذكرى أعضاء بنية الخاص بك. لهذا السبب فيما يلي أحجام مختلفة:

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

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

إذا لم يرد ج لا ضمانات، فمن المحتمل أن يحسن المغلوون كلاهما بنفس الحجم. لكنه يضمن التخطيط الداخلي لبيتك، وبالتالي فإن قواعد المحاذاة الطبيعية تطرد وجعل المرتبة الثانية أكبر من الأول.

Answer 6

وأنا أقدر القضايا المحددة التي أثارها هذا السؤال والأجوبة، لكنني أردت فقط أن أذكر أن Cpython استخدم حيلا مماثلة "أكثر أو أقل إلى الأبد" وتم عملها منذ عقود عبر مجموعة كبيرة من المحامرة C. على وجه التحديد، انظر كائن, ، وحدات الماكرو مثل PyObject_HEAD, ، هيكل مثل PyObject: جميع أنواع كائنات بيثون (أسفل على مستوى API C) هي الحصول على مؤشرات لهم إلى الأبد يلقيون إلى الأبد وإلى الأبد من / من PyObject* مع عدم وجود ضرر. لقد مر بعض الوقت منذ أن أدى آخر مرة إلى محامي البحر مع معيار ISO C، إلى النقطة التي ليس لدي نسخة مفيدة (!)، لكنني أعتقد أن هناك بعض القيود هناك ذلك ينبغي اجعل هذا يستمر في العمل لأنه يحتوي على ما يقرب من 20 عاما ...