الحفاظ على النوع عام بدون en-expansion

Question

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

type ('data, 'context) interpreter = ('data -> 'context -> 'context) list

التحويل البرمجي هو في الأساس عبارة عن رمز رمزي مع خطوة رسم الخرائط النهائية المميزة للتشويش التي تستخدم وصف الخريطة المحددة على النحو التالي:

type ('data, 'context) map = (string * ('data -> 'context -> 'context)) list

الاستخدام المترجم النموذجي يبدو هكذا:

let pocket_calc = 
  let map = [ "add", (fun d c -> c # add d) ;
              "sub", (fun d c -> c # sub d) ;
              "mul", (fun d c -> c # mul d) ]
  in 
  Interpreter.parse map "path/to/file.txt"

let new_context = Interpreter.run pocket_calc data old_context

المشكلة: أريد بلدي pocket_calc مترجم للعمل مع أي فصل يدعم add, sub و mul الطرق والمقابلة data اكتب (يمكن أن يكون أعداد صحيحة لفئة سياق واحدة وأرقام الفاصلة العائمة لآخر).

لكن، pocket_calc يتم تعريفه على أنه قيمة وليس وظيفة ، وبالتالي فإن نظام النوع لا يجعل نوعه عام: في المرة الأولى التي يتم فيها استخدامه ، 'data و 'context ترتبط الأنواع بأنواع أي البيانات والسياق الذي أقدمه أولاً ، ويصبح المترجم غير متوافق إلى الأبد مع أي بيانات أخرى للبيانات والسياق.

يتمثل الحل القابل للتطبيق في ETA-Expand تعريف المترجم المترجم للسماح بأن تكون معلمات نوعها عامة:

let pocket_calc data context = 
  let map = [ "add", (fun d c -> c # add d) ;
              "sub", (fun d c -> c # sub d) ;
              "mul", (fun d c -> c # mul d) ]
  in 
  let interpreter = Interpreter.parse map "path/to/file.txt" in
  Interpreter.run interpreter data context

ومع ذلك ، فإن هذا الحل غير مقبول لعدة أسباب:

• إنه يعيد تجميع المترجم المترجم في كل مرة يطلق عليها ، والتي تحطّم الأداء بشكل كبير. حتى خطوة التعيين (تحويل قائمة الرمز المميز إلى مترجم باستخدام قائمة الخريطة) تسبب تباطؤًا ملحوظًا.

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

• أرغب أحيانًا في إعادة استخدام قائمة خريطة معينة في العديد من المترجمين الفوريين ، سواء كانت من تلقاء نفسها أو عن طريق إعداد تعليمات إضافية (على سبيل المثال ، "div").

الأسئلة: هل هناك أي طريقة لجعل النوع حدودي بخلاف ETA-Expansion؟ ربما بعض الخدعة الذكية التي تنطوي على توقيعات الوحدة النمطية أو الميراث؟ إذا كان هذا مستحيلًا ، هل هناك أي طريقة لتخفيف القضايا الثلاث التي ذكرتها أعلاه لجعل ETA-Expansion حلاً مقبولًا؟ شكرًا لك!

Answer 1

يتمثل الحل القابل للتطبيق في ETA-Expand تعريف المترجم المترجم للسماح بأن تكون معلمات نوعها عامة:

 let pocket_calc data context = 
   let map = [ "add", (fun d c -> c # add d) ;
               "sub", (fun d c -> c # sub d) ;
               "mul", (fun d c -> c # mul d) ]
   in 
   let interpreter = Interpreter.parse map "path/to/file.txt" in
   Interpreter.run interpreter data context

ومع ذلك ، فإن هذا الحل غير مقبول لعدة أسباب:

• إنه يعيد تجميع المترجم المترجم في كل مرة يطلق عليها ، والتي تحطّم الأداء بشكل كبير. حتى خطوة التعيين (تحويل قائمة الرمز المميز إلى مترجم باستخدام قائمة الخريطة) تسبب تباطؤًا ملحوظًا.

يعيد ترجمة المترجم المترجم في كل مرة لأنك تفعل ذلك بشكل خاطئ. الشكل الصحيح هو شيء مثل هذا (ومن الناحية الفنية ، إذا كان التفسير الجزئي لـ Interpreter.run ل interpreter يمكنك القيام ببعض الحسابات ، يجب عليك نقلها من fun جدا).

 let pocket_calc = 
   let map = [ "add", (fun d c -> c # add d) ;
               "sub", (fun d c -> c # sub d) ;
               "mul", (fun d c -> c # mul d) ]
   in 
   let interpreter = Interpreter.parse map "path/to/file.txt" in
   fun data context -> Interpreter.run interpreter data context

Answer 2

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

بافتراض النوع المحدد للكرات البدائية:

type 'a primitives = <
  add : 'a -> 'a;
  mul : 'a -> 'a; 
  sub : 'a -> 'a;
>

يمكنك استخدام تعدد الأشكال من الدرجة الأولى التي توفرها الهياكل والأشياء:

type op = { op : 'a . 'a -> 'a primitives -> 'a }

let map = [ "add", { op = fun d c -> c # add d } ;
            "sub", { op = fun d c -> c # sub d } ;
            "mul", { op = fun d c -> c # mul d } ];;

يمكنك استعادة نوع البيانات المفروضة على البيانات التالية:

 val map : (string * op) list

تعديل: فيما يتعلق بتعليقك حول أنواع العمليات المختلفة ، لست متأكدًا من مستوى المرونة التي تريدها. لا أعتقد أنه يمكنك مزج العمليات عبر بدايات مختلفة في نفس القائمة ، ولا تزال تستفيد من مواصفات كل منها: في أحسن الأحوال ، يمكنك فقط تحويل "عملية الإضافة/الفرعية/MUL" إلى "عملية" على إضافة/ sub/mul/div "(كما نحن متجانسة في نوع البدائي) ، ولكن بالتأكيد ليس كثيرا.

على مستوى أكثر براغماتية ، صحيح أنك ، مع هذا التصميم ، تحتاج إلى نوع "عملية" مختلف لكل نوع بدائي. ومع ذلك ، يمكنك بسهولة إنشاء functor parametriced بواسطة نوع البدائية وإعادة نوع العملية.

لا أعرف كيف يمكن للمرء أن يفضح علاقة فرعية مباشرة بين أنواع بدائية مختلفة. المشكلة هي أن هذا سيحتاج إلى علاقة فرعية على مستوى Functor ، والتي لا أعتقد أن لدينا في CAML. ومع ذلك ، يمكنك استخدام شكل أبسط من النموذج الفرعي الصريح (بدلاً من الصب a :> b, ، استخدم وظيفة a -> b) ، قم ببناء functor الثاني ، Contravariant ، والتي ، التي ، مع إعطاء خريطة من نوع بدائي إلى آخر ، من شأنه أن يبني خريطة من نوع عملية إلى أخرى.

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

التكاليف التفسيرية وتعويضات التشغيل

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

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

أعتقد أنك قد تكون مهتمًا بالمدى الطويل بلغة "معاد" وسيطة تمثل عملياتك: نوع بيانات جبري بسيط للعمليات الحسابية ، التي ستقوم ببنائها من تمثيلك النصفي. لا يزال بإمكانك محاولة بناء عمليات الإغلاق "في وقت مبكر" منه ، على الرغم من أنني لست متأكدًا من أن العروض أفضل بكثير من تفسيرها مباشرة ، إذا كان التمثيل في الذاكرة لائقًا. علاوة على ذلك ، سيكون من الأسهل بكثير توصيل المحللين/المحولات الوسيطة لتحسين عملياتك ، على سبيل المثال الانتقال من نموذج "العمليات الثنائية الترابطية" إلى نموذج "عمليات N" ، والذي يمكن تقييمه بشكل أكثر كفاءة.