هل هناك أي نموذج رياضي أو نظرية وراء لغات البرمجة؟ [مغلق

Question

تعتمد RDBMS على الجبر العلائقي وكذلك نموذج CODD. هل لدينا شيء مشابه لتلك اللغات أو OOP؟

Answer 1

هل لدينا [نموذج أساسي] للغات البرمجة؟

السماوات ، نعم. ولأن هناك كثير لغات البرمجة ، هناك نماذج متعددة للاختيار من بينها. الأكثر أهمية أولا:

• الكنيسة حساب Lambda Untyped هو نموذج للحساب قوي مثل آلة تورينج (لا أكثر ولا أقل). تتمثل "فرضية تورث الكنيسة" الشهيرة في أن هذين النموذجين المكافئين يمثلان النموذج الأكثر عمومية للحساب الذي نعرفه كيفية تنفيذه. حساب حساب Lambda بسيط للغاية ؛ في مجملها اللغة

  e ::= x | e1 e2 | \x.e
  

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

  حساب حساب Lambda عام لدرجة أنه يمكنك أخذها في عدة اتجاهات.

  • إذا كنت ترغب في استخدام جميع القواعد المتاحة ، فيمكنك كتابة أدوات متخصصة مثل المقيمين الجزئيين وأجزاء من المجمعين.

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

  • إذا كنت تتجنب تقليل أي تعبير فرعي تحت Lambda ، وإذا كنت تصر أيضًا على تقليل كل وسيطة إلى نموذج عادي قبل تطبيق وظيفة ، فستكون لديك نموذج من حريص لغة وظيفية مثل F#أو LISP أو CAML الموضوعي أو المخطط أو ML القياسي.

• هناك أيضا العديد من النكهات مطبوع Lambda Calculi ، والتي يتم تجميعها الأكثر شهرة تحت الاسم النظام و, ، التي اكتشفتها جيرارد (بالمنطق) بشكل مستقل (في علوم الكمبيوتر). يعد System F نموذجًا ممتازًا لللغات مثل CLU و Haskell و ML ، والتي هي متعددة الأشكال ولكن لديها فحص نوع الترجمة. اكتشف Hindley (في المنطق) و Milner (في علوم الكمبيوتر) شكلًا مقيدًا للنظام F (الذي يطلق عليه الآن نظام Hindley-Milner) مما يجعل من الممكن استنتاج تعبيرات النظام F من بعض تعبيرات غير نمط حساب التفاضل والتكامل لامدا. طور داماس وميلنر خوارزمية تفعل هذا الاستدلال ، والذي يستخدم في ML القياسي وتم تعميمه بلغات أخرى.

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

• هناك عائلة كاملة من النماذج تعتمد على الآلات التجريدية. هنا لا يوجد نموذج فردي بقدر ما هو تقنية. يمكنك تحديد لغة باستخدام آلة الحالة وتحديد التحولات على الجهاز. يشمل هذا التعريف كل شيء بدءًا من آلات Turing إلى آلات Von Neumann إلى أنظمة الكتابة المدى ، ولكن بشكل عام تم تصميم الجهاز المجردة ليكون "أقرب إلى اللغة". تصميم هذه الآلات ، وأعمال إثبات النظريات عنها ، تأتي تحت عنوان الدلالات التشغيلية.

ماذا عن البرمجة الموجهة للكائن؟

أنا لست متعلمًا جيدًا كما يجب أن أكون حول النماذج المجردة المستخدمة في OOP. ترتبط النماذج الأكثر دراية بها ارتباطًا وثيقًا باستراتيجيات التنفيذ. إذا أردت التحقيق في هذا المجال ، فسوف أبدأ مع دلالات ويليام كوك الدلالية لـ Smalltalk. (SmallTalk كلغة بسيطة للغاية ، وبسيطة تقريبًا مثل حساب التفاضل والتكامل Lambda ، لذلك يجعل دراسة حالة جيدة لنمذجة اللغات الأكثر تعقيدًا للكائنات.)

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

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

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

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

آمل أن يمنحك هذا الاقتباس فكرة عن نكهة العمل.

Answer 2

يعتمد Lisp على حساب التفاضل والتكامل Lambda ، وهو مصدر إلهام لمعظم ما نراه في اللغات الحديثة اليوم.

آلات Von-Neumann هي أساس أجهزة الكمبيوتر الحديثة ، والتي تمت برمجتها لأول مرة بلغة التجميع ، ثم في مترجم الصيغة. ثم تم تطبيق النظرية اللغوية الرسمية لـ Grammars الخالية من السياق ، وتشعر على بناء جملة جميع اللغات الحديثة.

تحتوي نظرية القابلية للحساب (الأوتوماتا الرسمية) على هرات من أنواع الآلة التي توازي التسلسل الهرمي للنحو الرسمي ، على سبيل المثال ، العظم المعتاد = الدعامة المحدودة ، الخالية من السياق = pushdown-automaton ، grammar-grammar-context-grammar = آلة تورينج.

هناك أيضًا نظرية المعلومات ، من نوعين ، شانون و Kolmogorov ، والتي يمكن تطبيقها على الحوسبة.

هناك نماذج أقل شهرة للحوسبة ، مثل نظرية الوظائف المتكررة ، والآلة السجلات ، وما بعد الآلات.

ولا تنسى المسند السطحي في أشكاله المختلفة.

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

Answer 3

ترث اللغات الوظيفية مثل Lisp مفاهيمها الأساسية من "Lambda Alculs" للكنيسة (مقال ويكيبيديا هنا). يعتبر

Answer 4

قد يكون مفهوم واحد آلة تورينج.

Answer 5

إذا درست لغات البرمجة (على سبيل المثال: في جامعة) ، فهناك الكثير من النظرية ، وليس القليل من الرياضيات.

الأمثلة هي:

• آلات الدولة المحدودة
• lanugages الرسمية (و سياق القواعد الحرة مثل BNF المستخدمة لوصفها)
• بناء ال طاولات محلل LRISH

Answer 6

أقرب تشبيه يمكنني التفكير فيه هو Gurevich Evolving Algebras ، في الوقت الحاضر ، أكثر معروفة تحت اسم "آلات الحالة المجردة Gurevich" (GASM).

كنت آمل منذ فترة طويلة أن أرى المزيد من التطبيقات الحقيقية للنظرية عندما انضم Gurevich إلى Microsoft ، لكن يبدو أن القليل منها سيصدر. يمكنك التحقق من صفحة ASML على موقع Microsoft.

النقطة الجيدة حول GASM هي أنها تشبه عن كثب الرمز الزائفة حتى لو تم تحديد الدلالي بشكل رسمي. هذا يعني أنه يمكن للممارسين فهمهم بسهولة.

بعد كل شيء ، أعتقد أن جزءًا من نجاح الجبر العلائقي هو أنه الأساس الرسمي للمفاهيم التي يمكن إمساكها بسهولة ، وهي الجداول ، والمفاتيح الأجنبية ، والوصول ، إلخ.

أعتقد أننا بحاجة إلى شيء مشابه للمكونات الديناميكية لنظام البرمجيات.

Answer 7

هناك العديد من الأبعاد لمعالجة سؤالك ، وتناثر في الإجابات.

بادئ ذي بدء ، لوصف بناء جملة اللغة وتحديد كيف سيعمل المحلل ، نستخدم القواعد النحوية الخالية من السياق.

ثم تحتاج إلى تعيين معاني إلى بناء الجملة. الدلالات الرسمية تأتي في متناول يدي. اللاعبون الرئيسيون هم الدلالات التشغيلية ، والدلالات الدلالية ، والدلالات البديهية.

لاستبعاد البرامج السيئة لديك نظام النوع.

في النهاية ، يمكن أن تقل جميع برامج الكمبيوتر إلى (أو تجميع ، إذا كنت كذلك) نماذج حساب بسيطة للغاية. يتم تعيين البرامج الضرورية بسهولة أكبر لآلات تورينج ، ويتم تعيين البرامج الوظيفية إلى حساب التفاضل والتكامل Lambda.

إذا كنت تتعلم كل هذه الأشياء بنفسك ، فإنني أوصي بشدة http://www.uni-koblenz.de/~laemmel/paradigms0910/, ، لأن المحاضرات مسجلة على الفيديو ووضعها على الإنترنت.

Answer 8

ال قسم التاريخ من ويكيبيديا البرمجة الشيئية يمكن أن يكون التنوير.

Answer 9

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

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

Answer 10

لا يوجد نموذج رياضي لـ OOP.

الجبر العلائقي في النموذج الرياضي لـ SQL. تم إنشاؤه BT EF CODD. كان CJ Date أيضًا عازفًا معروفًا ساعد في هذه النظرية. الفكرة كلها هي أنه يمكنك القيام بكل عملية كعملية محددة ، مما يؤثر على الكثير من القيم في نفس الوقت. هذا بالطبع يعني أنه يجب إخبار محرك قاعدة البيانات بما يجب الخروج منه ، وأن قاعدة البيانات قادرة على تحسين استعلامك.

انتقد كل من CODD والتاريخ SQL لأنهم شاركوا في النظرية ، لكنهما لم يشاركوا في إنشاء SQL.

شاهد هذا الفيديو: http://player.oreilly.com/videos/9781491908853؟toc_id=182164

هناك الكثير من المعلومات من تاريخ كريس. أتذكر أن هذا التاريخ انتقد لغة برمجة SQL باعتبارها لغة فظيعة ، لكن لا يمكنني العثور على الورقة.

كان نقد TEH في الأساس أن معظم اللغات تسمح بكتابة التعبيرات وتعيين المتغيرات لتلك التعبيرات ، ولكن SQL لا.

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

وفقًا للعم بوب ، لن تكون هناك حاجة إلى قواعد البيانات عندما يكون لدى كل شخص SSD ، لأن بنية SSDs تعني أن الوصول سريع مثل ذاكرة الوصول العشوائي. لذلك يمكنك الحصول على كل الأشياء الخاصة بك في ذاكرة الوصول العشوائي.

https://www.youtube.com/watch؟feature=player_detailpage&v=t86v3n4osh#t=3287

المشكلة الوحيدة في التخلص من SQL هي أنك ستنتهي بدون لغة استعلام لقاعدة البيانات.

لذا نعم ولا ، تم استخدام الجبر العلائقي كمصدر إلهام لـ SQL ، لكن SQL ليس في الحقيقة تطبيق الجبر العلائقي.

في حالة lisp ، الأمور مختلفة. كانت الفكرة الرئيسية هي أن تنفيذ وظيفة eval في LISP يمكن أن تنفذ اللغة بأكملها. هذا هو أول تطبيق LISP هو نصف صفحة فقط من التعليمات البرمجية.

http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equations-of-software/

للضحك قليلا: https://www.youtube.com/watch؟v=hzf3htukk8u

أهمية البرمجة الوظيفية كلها تعود إلى وظائف الكاري والمكالمات البطيئة. ولا تنسى البيئات والإغلاق أبدًا. و Reduce MAP. كل هذا يعني أننا سنرمز باللغات الوظيفية خلال 20 عامًا.

الآن العودة إلى OOP ، لا يوجد إضفاء الطابع الرسمي على OOP.

ومن المثير للاهتمام ، أن لغة OO الثانية التي تم إنشاؤها على الإطلاق ، SmallTalk ، لها أشياء فقط ، أو لا تحتوي على بدايات أو أي شيء من هذا القبيل. والمبدع ، آلان كاي ، تم إنشاء كتل صريحة للعمل تمامًا كوظائف LISP.

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

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

https://www.youtube.com/watch؟feature=player_detailpage&v=o6l6xendd_k#t=250

المشكلة الرئيسية في ذلك هي أن الوظائف غير موجودة بشكل مستقل عن الأشياء في OOP ، ولكن في نظرية الفئة التي يقومون بها. وبالتالي فهي غير متوافقة. يمكنك تطوير لغة جديدة للتعبير عن نظرية الفئة.

اللغة النظرية التجريبية التي تم إنشاؤها صراحة لمحاولة إضفاء الطابع الرسمي على OOP هي Z. Z مشتقة من الشكلية المتطلبات.

محاولة أخرى هي شكلية لوكا كارديلي:

Javahttp://lucacardelli.name/papers/primobjimp.pdf Javahttp://lucacardelli.name/papers/primobj1storder.a4.pdf Javahttp://lucacardelli.name/papers/primobjsemlics.a4.pdf

أنا غير قادر على قراءة هذا التدوين وفهمه. يبدو أنه تمرين عديمة الفائدة ، لأنه على حد علمي ، لم ينفذ أحد على الإطلاق بالطريقة التي تم بها تنفيذ حساب التفاضل والتكامل Lamba في LISP.

Answer 11

كما اعلم، قواعد رسمية يستخدم لوصف بناء الجملة.