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

1. التوليد التلقائي للبرامج

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

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

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

يتم ضبط النظام إلى مجال الموضوع من خلال تطوير التسلسل الهرمي المناسب لتوليد الفئات.

مثال على برنامج نصي يولد كود للفئة "معالجة المتجهات (الحد الأدنى ، الحد الأقصى ، الوسط الحسابي)":

<? if ($Stage == stInit) { $argumentID = $Arg["ID"][0]; $argumentSize = $Arg["Size"][0]; $resultID = GetNextMail("result" . $this->ID); if ($this->Op == "Min") { echo " " . $resultID . " = 1E300;\n"; } else if ($this->Op == "Max") { echo " " . $resultID . " = -1E300;\n"; } elseif ($this->Op == "Avr") { echo " " . $resultID . " = 0.0;\n"; } ?> for (i = 0; i < <? echo $argumentSize; ?>; i++) <? if ($this->Op == "Min") { ?> if (<? echo $argumentID . "[i] < " . $resultID; ?>) <? echo $resultID . " = " . $argumentID . "[i];\n"; } else if ($this->Op == "Max") { ?> if (<? echo $argumentID . "[i] > " . $resultID; ?>) <? echo $resultID . " = " . $argumentID . "[i];\n"; } elseif ($this->Op == "Avr") { echo " " . $resultID . " += " . $argumentID . "[i];\n"; } if ($this->Op == "Avr") { echo " " . $resultID . " /= " . $argumentSize . ";\n"; } } ?> 

هذا مخطط غير معقد نسبياً يعمل. يسمح النظام الذي ينفذ مخطط التوليد (PGEN ++) ، على سبيل المثال ، بإنشاء برامج حاسمة في المجالات التالية:

أ) عمليات نمذجة انتشار التلوث ؛
ب) حل بعض المشاكل الكينماتيكا لمعالجات الروبوت البسيطة ؛
ج) برامج تدريبية بسيطة للعمل مع بيانات المتجه (ابحث عن الحد الأدنى والحد الأقصى والمتوسط ​​الحسابي) ؛
د) تطوير الاختبارات لنظام الاختبار النفسي PROFTEST.

فيما يلي مثال على البيان الأولي للمشكلة (برنامج بسيط لمعالجة بيانات المتجه) في شكل مخطط تخطيطي:



وهذه نتيجة إنشاء البرنامج :

2. المشكلة العكسية: إعادة صياغة بيان المشكلة (النموذج الأولي) وفق البرنامج المولد. التحقق من البرامج المولدة

بادئ ذي بدء ، لماذا من الضروري حل مثل هذه المشكلة. التطبيق المباشر ، وأعتقد أن التطبيق الأكثر وضوحًا هو التحقق من البرامج التي يتم إنشاؤها تلقائيًا. إذا كان لدينا النموذج A ، وقمنا ببناء البرنامج P عليه ، والذي تم منه إعادة بناء النموذج B ، فمن المرجح أن يكون البرنامج صحيحًا إذا تزامن النموذجان A و B.

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

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

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

3. واجهة اللغة الطبيعية لنظام توليد البرامج

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

أ) بيان المشكلة مكتوب بلغة طبيعية مبسطة ؛
ب) يتم حل المشكلة العكسية - يتم استخراج بيان رسمي من عبارة اللغة الطبيعية (شبكة من عناصر العناصر في مجال الموضوع) ؛
ج) يتم إطلاق النظام لإنشاء برنامج وفقًا للبيان الرسمي الذي تم الحصول عليه.

وتعمل هذه الدائرة أيضًا. تم تطوير مثال لنفس حالة برامج التدريب البسيطة للعمل مع بيانات المتجه.

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

 @versions(Programmatical) @global_unique(PROCESS,infinity):- (\s*for\s*\(i\s*\=\s*0\;\s*i\s*\<\s*(\d+)->{N}\;\s*i\+\+\)\s*\{\\n\s*printf\(\"(\w+)->{VECTOR} \[\%i\]\s*\=\s*\"\,\s*i\)\;\\n\s*scanf\(\"\%lf\"\,\s*\&(\w+)==>{VECTOR}\[i\]\)\;\\n\s*\}\\n)| (\s*printf\(\"(\w+)->{SCALAR}\s*\=\s*\"\)\;\\n\s*scanf\(\"\%lf\"\,\s*\&(\w+)==>{SCALAR}\)\;\\n). @versions(Russian) @nearest(db_vvedem,2,"db_vvedem.csv"). @fast(db_var,"db_var.csv"). @global_unique(PROCESS,infinity):- (()->{VAR}([--]+)?=>{db_vvedem($)}\s+((\s+\s+)?)->{KEYB} ([--]+)?=>{db_var($,$VAR)}\s+(\w+)->{ID}((\s+\s+)?)!=>{KEYB}\s*\.). @versions(Russian) handle:-xpath('PROCESS','//ID/text()',[VText]), xpath('PROCESS','//VAR/text()',['0']), simple_vector(_,VText,_), global_id(GID),assertz(simple_act(GID,in,VText,'')),!. handle:-xpath('PROCESS','//ID/text()',[SText]), xpath('PROCESS','//VAR/text()',['1']), global_id(GID),assertz(simple_act(GID,in,SText,'')),!. @versions(Programmatical) handle:-xpath('PROCESS','//VECTOR/text()',[VText]), xpath('PROCESS','//N/text()',[NText]), simple_vector(_,VText,NText), global_id(GID),assertz(simple_act(GID,in,VText,'')),!. handle:-xpath('PROCESS','//SCALAR/text()',[SText]), simple_scalar(_,SText), global_id(GID),assertz(simple_act(GID,in,SText,'')),!. @versions(Programmatical,Russian) @goal:- handle,!. @done:- clear_db. 

مثال على بيان مشكلة باللغة الروسية:

  .   max.   min.   V  10 .   V  .    V      min.     V      max.   min  .   max  .   V  .      . 

ونموذج المشكلة التي حصل عليها النظام من وصف اللغة الطبيعية أعلاه :

4. تطبيقات أخرى للمشكلة العكسية

عند حل المشكلة العكسية ، لا شيء يمنعنا من التفكير في حالة عدم التعرف على برنامج معين فحسب ، ولكن التعرف عليه "مع التحسين" أو معالجة (شخصية اعتباطية) أخرى. على وجه الخصوص ، كان من الممكن تطوير "موازٍ تلقائي" لبرنامج معترف به مكتوب في C. يقوم بإجراء تحليل ثابت وديناميكي جزئيًا للشفرة المعترف بها ويدرج توجيهات موازية من ملحق Cilk / Cilk ++ إليه. يتم تنفيذ مهمة التحسين هذه من خلال التعرف على الأساليب (على GNU Prolog).

مثال على برنامج حوسبة C تمت معالجته بواسطة موازٍ (أدخل تعليمات cilk_spawn و cilk_sync):

 #include <stdio.h> #include <math.h> #include <omp.h> #define PI 3.14159265358 #define NX 100 #define NY 100 #define MaxT 0.001 #define h 0.01 #define tau 0.00001 #define cilk_spawn _Cilk_spawn #define cilk_sync _Cilk_sync void F( double x, double y, double t, double * val ){ double r = sqrt(x*x + y*y); double result = 0.0; int i; for ( i = 0; i < 300; i++ ) result += exp(-r*t)*sin(0.1*i*r + 0.5*PI); *val = result; } int main( ){ double f[NY][NX] = {0.0}; double v[NY][NX] = {0.0}; double v1[NY][NX] = {0.0}; double t; int x, y; double start = omp_get_wtime(); for ( t = 0.0; t < MaxT; t += tau ) { for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) cilk_spawn F(x*h, y*h, t, &f[y][x]); for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) { cilk_sync; v1[y][x] = v[y][x] + tau*((v[y-1][x]+v[y+1][x]+v[y][x-1]+v[y][x+1]-4.0*v[y][x])/h/h - f[y][x]); } for ( y = 1; y < NY-1; y++ ) for ( x = 1; x < NX-1; x++ ) v[y][x] = v1[y][x]; } for ( y = 0; y < NY; y++ ) { for ( x = 0; x < NX; x++ ) printf("%lf ", v[y][x]); printf("\n"); } printf("Total time = %lf\n", omp_get_wtime() - start); return 0; } 

5. القليل من الخيال. التحقق من البرامج التعسفية وتحديدها برمز مصدر مغلق

هنا نتحدث عن البرامج التعسفية التي كتبها مبرمج و / أو برامج إنشاء نظام لا يوجد لها ببساطة كود مصدر. فليطلب التحقق من الأداء الصحيح لهذا البرنامج ، أو حتى لفهم ما يقوم به. في هذه الحالة ، يمكن استخدام نسخة أو أخرى من ما يسمى "الطبقة الفوقية" - مكون افتراضي لنظام التشغيل يتتبع التسلسل الكامل للبرنامج (وظائف الاستدعاء ، وتعديل البيانات في الذاكرة ، وما إلى ذلك) ويبني نموذجًا تقريبيًا لمنطقه في شكل يعادل عمل البرنامج بأي لغة برمجة. ثم يبقى حل المشكلة العكسية لمثل هذا البرنامج - لاستعادة نموذج (أو نماذج) أولية محتملة تسمح على الأقل بتقييم صحة أو فهم الغرض من البرنامج. تم تطوير النموذج الأولي لمثل هذه "طبقة metaslayer" من قبل المؤلف لحالة برامج C / C ++ ؛ لم يكن هناك الكثير ممكنا ، ولكن عمل شيء ما. ربما في يوم من الأيام سيرغب شخص ما في أداء مثل هذا العمل بالكامل.

6. الخلاصة

آمل أن أكون قد تمكنت من إثبات أن التوليد التلقائي للبرامج وحل المشكلة العكسية ليست مشاكل أكاديمية بحتة ، ولكنها شيء مفيد ولها نتائج عملية مباشرة. في الوقت نفسه ، لا تتظاهر القرارات المقدمة هنا بأنها كاملة وواضحة ، لكنها تُطبَّق وتتظاهر بدعة جديدة.