نموذج الممثل وتاريخ حسابات العمليات

📅 آخر تحديث: ٢٢ يوليو ٢٠٢٦
✍️ نُشر في: ٢٢ يوليو ٢٠٢٦
الموسوعة الحرة

يشترك نموذج الفاعل وحسابات العملية في تاريخ مثير للاهتمام وتطور مشترك.

الأعمال المبكرة

يُعد نموذج الممثل، الذي نُشر لأول مرة عام 1973، [ 1 ] نموذجًا رياضيًا للحوسبة المتزامنة . ويتعامل نموذج الممثل مع "الممثلين" باعتبارهم العناصر الأساسية الشاملة للحوسبة الرقمية المتزامنة: فاستجابةً لرسالة يتلقاها، يمكن للممثل اتخاذ قرارات محلية، وإنشاء المزيد من الممثلين، وإرسال المزيد من الرسائل، وتحديد كيفية الاستجابة للرسالة التالية التي يتلقاها.

على عكس النهج السابق القائم على تركيب العمليات المتسلسلة، تم تطوير نموذج الممثل كنموذج متزامن بطبيعته. في نموذج الممثل، كانت التسلسلية حالة خاصة مشتقة من الحساب المتزامن كما هو موضح في نظرية نموذج الممثل .

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

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

قام ميلنر لاحقًا بإزالة بعض هذه القيود في عمله على حساب باي (انظر قسم ميلنر وآخرون أدناه).

كان نشر توني هوار في عام 1978 للعمليات التسلسلية الأصلية مختلفًا عن نموذج الممثل الذي ينص على ما يلي: [ 3 ]

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

اختلفت نسخة عام 1978 من CSP عن نموذج الممثل في الجوانب التالية [Clinger 1981]:

  • كانت بدائيات التزامن في CSP هي الإدخال والإخراج والأوامر المحمية والتركيب المتوازي، بينما يعتمد نموذج الممثل على المراسلة أحادية الاتجاه غير المتزامنة.
  • كانت الوحدة الأساسية للتنفيذ عملية متسلسلة على عكس نموذج الممثل الذي كان فيه التنفيذ متزامنًا بشكل أساسي.
  • كانت العمليات ذات بنية اتصال ثابتة، بينما كانت الجهات الفاعلة ذات بنية اتصال متغيرة ديناميكيًا. وتُعدّ البنية الثابتة إشكالية لأنها تحول دون القدرة على التكيف الديناميكي مع الظروف المتغيرة.
  • كانت العمليات مُهيكلة هرميًا باستخدام التركيب المتوازي، بينما سمح نموذج الممثلون بإنشاء تنفيذ غير هرمي باستخدام المستقبلات [بيكر وهيويت، 1977]. يُعد التركيب المتوازي الهرمي إشكاليًا لأنه يحول دون إمكانية إنشاء عملية تستمر بعد انتهاء عمر مُنشئها. كما أن تمرير الرسائل هو الآلية الأساسية لتوليد التوازي في نموذج الممثلون؛ فإرسال المزيد من الرسائل يُولّد إمكانية المزيد من التوازي.
  • كان الاتصال متزامنًا بينما كان اتصال الممثلين غير متزامن. يُعدّ الاتصال المتزامن إشكاليًا لأنه يتطلب من العملية انتظار عمليات متعددة.
  • كان التواصل بين العمليات، بينما في نموذج الممثل يكون التواصل في اتجاه واحد إلى الممثلين.
  • تتألف هياكل البيانات في النموذج من الأرقام والسلاسل النصية والمصفوفات، بينما في نموذج الممثل، كانت هياكل البيانات عبارة عن ممثلين. ويُعدّ حصر هياكل البيانات في الأرقام والسلاسل النصية والمصفوفات إشكاليًا لأنه يمنع إنشاء هياكل بيانات قابلة للبرمجة.
  • تحتوي الرسائل على أرقام ونصوص، بينما في نموذج الممثل، يمكن أن تتضمن الرسائل عناوين الممثلين. يُعدّ عدم السماح بالعناوين في الرسائل إشكالية لأنه يُعيق مرونة التواصل، إذ لا توجد طريقة لتزويد عملية أخرى بالقدرة على التواصل مع عملية معروفة مسبقًا.
  • لقد تعمد نموذج CSP أن يكون ذا حتمية محدودة [فرانسز، هوار، ليمان، ودي رويفر 1979]، بينما كان نموذج الممثل ذا حتمية غير محدودة . وقد أقنع ديكسترا [1976] هوار بأنه لا يمكن تنفيذ لغة برمجة ذات حتمية غير محدودة.

حسابات العمليات ونموذج الممثل

ميلنر وآخرون

في محاضرته عن تورينج، [ 4 ] لاحظ ميلنر ما يلي:

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

في عام 2003، استذكر كين كان في رسالة حول حساب التفاضل والتكامل باي :

يعتمد حساب باي على التواصل المتزامن (التواصل المباشر). قبل حوالي 25 عامًا، تناولت العشاء مع كارل هيويت وروبن ميلنر (مبتكري نظام CCS وحساب باي الشهيرين)، وكانا يتناقشان حول أساسيات التواصل المتزامن وغير المتزامن. استخدم كارل تشبيه مكتب البريد، بينما استخدم روبن تشبيه الهاتف. وسرعان ما أقر كلاهما بإمكانية تطبيق أحدهما في الآخر.

هوار وآخرون.

قام كلٌّ من توني هوار ، وستيفن بروكس ، وإيه دبليو روسكو بتطوير نظرية CSP وصقلها إلى شكلها الحديث. [ 5 ] وقد تأثر النهج المُتَّبع في تطوير النسخة النظرية من CSP بشكل كبير بعمل روبن ميلنر في حساب أنظمة الاتصال (CCS)، والعكس صحيح. وعلى مرّ السنين، جرى تبادلٌ مثمرٌ للأفكار بين الباحثين العاملين في كلٍّ من CSP وCCS.

هيويت وآخرون

طوّر ويل كلينجر [1981] أول نموذج دلالي للممثلين في الحوسبة المتزامنة، والذي جسّد عدم الحتمية غير المحدودة . وأظهر بيل كورنفيلد وكارل هيويت [1981] أن نموذج الممثلين قادر على استيعاب التزامن واسع النطاق. طوّر آغا الممثلين كنموذج أساسي للحوسبة المتزامنة. وقد تأثر عمله في تمثيل تجريد الممثلين وتركيبهم، وفي تطوير دلالات تشغيلية للممثلين استنادًا إلى أشجار الاتصالات غير المتزامنة، بشكل واضح بعمل ميلنر في حساب أنظمة الاتصال (CCS) [ 6 ] ، بالإضافة إلى عمل كلينجر.

مزيد من التطور المشترك

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

مع ذلك، توجد تطورات مشتركة مثيرة للاهتمام بين نموذج الفاعل وحساب العمليات. ناقش مونتاناري وتالكوت [ 7 ] مدى توافق نموذج الفاعل مع حساب باي. وبيّن سانجيورجي ووالكر كيف يمكن نمذجة عمل نموذج الفاعل، الذي يتعامل مع هياكل التحكم كأنماط لتمرير الرسائل [ 8 ] ، باستخدام حساب باي.

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

انظر أيضاً

مراجع

  1. ↑ كارل هيويت، بيتر بيشوب وريتشارد ستيجر. نموذج الممثل المعياري العالمي للذكاء الاصطناعي IJCAI 1973.
  2. ↑ روبن ميلنر. العمليات: نموذج رياضي لوكلاء الحوسبة في ندوة المنطق 1973.
  3. ↑ كار هوار . عمليات الاتصال التسلسلي . مجلة الاتصالات والإدارة. أغسطس 1978.
  4. ↑ روبن ميلنر : عناصر التفاعل: محاضرة جائزة تورينج ، اتصالات ACM، المجلد 36، العدد 1، الصفحات 78-89، يناير 1993. ( DOI ).
  5. ↑ إس دي بروكس، سي إيه آر هوار، و دبليو روسكو. نظرية العمليات المتسلسلة المتصلة JACM 1984.
  6. ↑ غول آغا (1985). الممثلون: نموذج للحوسبة المتزامنة في الأنظمة الموزعة (أطروحة دكتوراه). جامعة ميشيغان. hdl : 1721.1/6952 .
  7. ↑ أوجو مونتاناري وكارولين تالكوت. هل يمكن للممثلين والوكلاء من نوع باي أن يعيشوا معًا؟ ملاحظات إلكترونية في علوم الحاسوب النظرية. 1998.
  8. ↑ كارل هيويت. النظر إلى هياكل التحكم كأنماط لتمرير الرسائل. مجلة الذكاء الاصطناعي. يونيو 1977.
  9. ^ ماورو جاسباري. جيانلويجي زافاتارو (مايو 1997). جبر الفاعلين (تقرير فني). جامعة بولونيا. يو بي إل سي إس-97-4.
  10. ^ م. جاسباري. جي زافاتارو (1999). “جبر الممثلين”. في باولو سيانكاريني؛ أليساندرو فانتيشي؛ روبرت جورييري (محرران). الطرق الرسمية للأنظمة القائمة على الكائنات المفتوحة . نيويورك: سبرينغر ساينس + بزنس ميديا.
  11. ↑ غول آغا ؛ براسانا ثاتي (2004). "نظرية جبرية للممثلين وتطبيقها على لغة بسيطة قائمة على الكائنات" (ملف PDF) . من البرمجة الكائنية إلى إدارة الوظائف (كتاب تذكاري لدال) LNCS 2635. مؤرشف من الأصل (ملف PDF) بتاريخ 20 أبريل 2004. تم الاطلاع عليه بتاريخ 15 يناير 2008 .

للمزيد من القراءة

  • إدسكار ديكسترا. منهج البرمجة. برنتيس هول . 1976.
  • كارل هيويت وآخرون. استقراء الممثل والتقييم الميتا، سجل مؤتمر ACM حول مبادئ لغات البرمجة، يناير 1974.
  • كارل هيويت، وآخرون. الدلالات السلوكية لبنية التحكم غير العودية، وقائع Colloque sur la Programmation، أبريل 1974.
  • إيرين غريف وكارل هيويت. دلالات الممثل في برنامج PLANNER-73، وقائع ندوة ACM حول مبادئ لغات البرمجة. يناير 1975.
  • إيرين غريف. دلالات العمليات المتوازية المتصلة. أطروحة دكتوراه في قسم الهندسة الكهربائية وعلوم الحاسوب بمعهد ماساتشوستس للتكنولوجيا. أغسطس 1975.
  • كارل هيويت وهنري بيكر، الممثلون والوظائف المستمرة، وقائع مؤتمر IFIP العملي حول الوصف الرسمي لمفاهيم البرمجة. 1-5 أغسطس 1977.
  • كارل هيويت وهنري بيكر قوانين الاتصال بين العمليات المتوازية IFIP-77، أغسطس 1977.
  • هنري بيكر وكارل هيويت، " التجميع التدريجي للنفايات في العمليات"، وقائع ندوة لغات برمجة الذكاء الاصطناعي. إشعارات SIGPLAN 12، أغسطس 1977.
  • أكي يونيزاوا، تقنيات تحديد المواصفات والتحقق للبرامج المتوازية القائمة على دلالات تمرير الرسائل، أطروحة دكتوراه في قسم الهندسة الكهربائية وعلوم الحاسوب بمعهد ماساتشوستس للتكنولوجيا، ديسمبر 1977.
  • هنري بيكر . أنظمة الممثلين للحوسبة في الوقت الحقيقي. أطروحة دكتوراه في قسم الهندسة الكهربائية وعلوم الحاسوب بمعهد ماساتشوستس للتكنولوجيا. يناير 1978.
  • جورج ميلن وروبن ميلنر . العمليات المتزامنة وبنيتها النحوية . مجلة الجمعية الآلية للآلات. أبريل 1979.
  • نسيم فرانسيز ، سي إيه آر هوار ، دانيال ليمان، وويليم دي رويفر. دلالات عدم الحتمية، والتزامن، والاتصال. مجلة علوم الحاسوب والأنظمة. ديسمبر 1979.
  • نانسي لينش ومايكل فيشر. حول وصف سلوك الأنظمة الموزعة في دلالات الحوسبة المتزامنة. سبرينغر-فيرلاغ. 1979.
  • ويل كلينجر. أسس دلالات الفاعلين. أطروحة دكتوراه في الرياضيات من معهد ماساتشوستس للتكنولوجيا. يونيو 1981.
  • جيه إيه بيرجسترا وجيه دبليو كلوب. جبر العمليات للاتصال المتزامن. المعلومات والتحكم. 1984.
  • إيك بيست . السلوك المتزامن: التسلسلات والعمليات والمسلمات. محاضرات في علوم الحاسوب المجلد 197 1984.
  • لوكا كارديلي. نموذج تنفيذي للاتصالات المتزامنة . ندوة حول التزامن. سلسلة محاضرات في علوم الحاسوب 197. سبرينغر-فيرلاغ. 1985
  • روبن ميلنر، يواكيم بارو، وديفيد ووكر. حساب التفاضل والتكامل للعمليات المتنقلة. قسم علوم الحاسوب، جامعة إدنبرة. التقارير ECS-LFCS-89-85 وECS-LFCS-89-86. يونيو 1989. نُقّحت في سبتمبر وأكتوبر 1990 على التوالي.
  • روبن ميلنر. حساب باي متعدد الحدود: دليل تعليمي. جامعة إدنبرة. تقرير LFCS رقم ECS-LFCS-91-180. 1991.
  • كوهي هوندا وماريو توكورو. حساب التفاضل والتكامل كائن للاتصالات غير المتزامنة ECOOP 91.
  • بنيامين بيرس، ديدييه ريمي، وديفيد تيرنر. لغة برمجة عالية الرتبة ذات أنواع بيانات محددة، تعتمد على حساب باي. ورشة عمل حول نظرية الأنواع وتطبيقها على أنظمة الحاسوب. جامعة كيوتو. يوليو 1993.
  • سيدريك فورنيه وجورج غونتييه . الآلة الكيميائية المجردة الانعكاسية وحساب الوصل POPL 1996.
  • سيدريك فورنيه، وجورج جونتييه، وجان جاك ليفي، ولوك مارانجيه، وديدييه ريمي. حساب التفاضل والتكامل لوكلاء الهاتف المحمول CONCUR 1996.
  • جيرار بودول. حساب باي بأسلوب مباشر ، POPL 1997
  • تاتسورو سيكيجوتشي وأكينوري يونيزاوا . حساب التفاضل والتكامل مع رمز التنقل FMOODS 1997.
  • لوكا كارديلي وأندرو د. جوردون . البيئات المتنقلة: أسس علوم البرمجيات والهياكل الحسابية، موريس نيفات (محرر)، سلسلة محاضرات في علوم الحاسوب، المجلد 1378، سبرينغر، 1998.
  • روبن ميلنر. أنظمة الاتصالات والأنظمة المتنقلة: حساب باي، مطبعة جامعة كامبريدج. 1999.
  • جيه سي إم بايتن. تاريخ موجز لجبر العمليات. علوم الحاسوب النظرية. 2005. (الرابط صالح اعتبارًا من 2015_26_5_0004)
  • JCM Baeten, T. Basten, and MA Reniers. Algebra of Communicating Processes Cambridge University Press. 2005.
  • هي جيفنغ وكار هوار. ربط نظريات التزامن. جامعة الأمم المتحدة، المعهد الدولي لتكنولوجيا البرمجيات، تقرير رقم 328، يوليو 2005.
  • لوكا أسيتو وأندرو د. جوردون (محرران). حسابات العمليات الجبرية: الخمسة والعشرون عامًا الأولى وما بعدها من جبر العمليات. بيرتينورو، فورلي، إيطاليا، 1-5 أغسطس 2005.
  • كارل هيويت. ما هو الالتزام؟ الالتزام المادي والتنظيمي والاجتماعي . COIN@AAMAS. 27 أبريل 2006ب.
  • كارل هيويت (2007أ) ما هو الالتزام؟ المادي والتنظيمي والاجتماعي (مراجعة) بابلو نورييغا وآخرون محررون. LNAI 4386. سبرينغر-فيرلاغ. 2007.
  • كارل هيويت (2007ب) الحوسبة التنظيمية واسعة النطاق تتطلب التناقض غير الطبقي والانعكاس COIN@AAMAS'07.