البرمجة الموجهة نحو المكدس

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

البرمجة الموجهة نحو المكدس هي نموذج برمجي يعتمد على مكدس واحد أو أكثر لمعالجة البيانات و/أو تمرير المعاملات. تتطلب بنيات البرمجة في لغات البرمجة الأخرى تعديلًا لاستخدامها في نظام موجه نحو المكدس. [ 1 ] تعمل معظم لغات البرمجة الموجهة نحو المكدس بنظام التدوين اللاحق أو التدوين البولندي العكسي : حيث تُدرج وسائط أو معاملات الأمر قبل الأمر نفسه. على سبيل المثال، يُكتب التدوين اللاحق بدلًا2 3 multiply من التدوين السابق أو البولنديmultiply 2 3 ، أو التدوين الوسطي . تتوافق لغات البرمجة Forth و Factor و RPL و PostScript ولغة تصميم BibTeX [ 2 ] والعديد من لغات التجميع مع هذا النموذج.2 multiply 3

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

الخوارزميات القائمة على المكدس

تُعدّ لغة PostScript مثالاً على لغة برمجة تعتمد على بنية المكدس اللاحقة. مثال على تعبير في هذه اللغة هو 2 3 mul(حيث يُمثّل 'mul' أمر عملية الضرب). يتطلب حساب هذا التعبير فهم كيفية عمل بنية المكدس.

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

خذ طبقًا 2وضعه على الرزمة، ثم خذ طبقًا آخر 3وضعه على الرزمة. بعد ذلك، خذ mulالطبق. هذه تعليمات للتنفيذ. ثم، خذ الطبقين العلويين من الرزمة، واضرب قيمتيهما ( 2و 3)، واكتب النتيجة ( 6) على طبق جديد. تخلص من الطبقين القديمين ( 2و 3) والطبق mul، وضع الطبق الجديد على الرزمة. عندما لا يتبقى أي أطباق على الناقل، ستظهر نتيجة العملية الحسابية ( 6) على الطبق الموجود أعلى الرزمة.

هذه عملية حسابية بسيطة للغاية. ماذا لو احتجنا إلى عملية حسابية أكثر تعقيدًا، مثل ؟ إذا كُتبت أولًا بصيغة لاحقة، أي ، فيمكن إجراء العملية الحسابية بنفس الطريقة تمامًا والحصول على النتيجة الصحيحة. تُوضح خطوات العملية الحسابية في الجدول أدناه. يُظهر كل عمود عنصر إدخال (اللوحة في نهاية الناقل)، ومحتويات الرزمة بعد معالجة هذا الإدخال.(2 + 3) × 11 + 12 3 add 11 mul 1 add

مدخل23يضيف11مول1يضيف
كومة23 2511 5551 5556

بعد معالجة جميع المدخلات، تحتوي المكدسة على 56، وهو الجواب.

من هذا، يمكن استنتاج ما يلي: لغة البرمجة القائمة على المكدس لا تملك إلا طريقة واحدة للتعامل مع البيانات، وهي سحب جزء من البيانات من أعلى المكدس (عملية تُسمى pop ping)، وإعادة البيانات إلى أعلى المكدس (عملية تُسمى push ing). أي تعبير يمكن كتابته بالطريقة التقليدية ، أو بلغة برمجة أخرى، يمكن كتابته بصيغة لاحقة (أو سابقة) وبالتالي يكون قابلاً للتفسير بواسطة لغة موجهة نحو المكدس.

التلاعب بالمكدس

بما أن المكدس هو الوسيلة الأساسية لمعالجة البيانات في لغات البرمجة الموجهة نحو المكدس، فإن هذه اللغات غالبًا ما توفر أنواعًا من عوامل معالجة المكدس. من بين هذه العوامل الشائعة: `<b>` dupلتكرار العنصر الموجود أعلى المكدس، exchو`<b swap>` لتبديل العناصر في أعلى المكدس (حيث يصبح الأول ثانيًا والثاني أولًا)، rollو`<b>` لتبديل العناصر بشكل دوري في المكدس أو في جزء منه، popو`<b drop>` لحذف العنصر الموجود أعلى المكدس (حيث يكون `<b>` ضمنيًا)، وغيرها. تُعد هذه العوامل أساسية في دراسة الإجراءات.

مخططات تأثير التراكم

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

(قبل -- بعد )

على سبيل المثال، يتم وصف عوامل تشغيل مكدس Forth الأساسية:

dup ( a -- aa ) drop ( a -- ) swap ( ab -- ba ) over ( ab -- aba ) rot ( abc -- bca )

الوظيفة fibالموضحة أدناه هي:

fib( n -- n' )

It is equivalent to preconditions and postconditions in Hoare logic. Both comments may also be referenced as assertions, though not necessarily in the context of Stack-based languages.

PostScript stacks

PostScript and some other stack languages have other separate stacks for other purposes.

Variables and dictionaries

The evaluation of different expressions has already been analysed. The implementation of variables is important for any programming language, but for stack-oriented languages, it is of special concern, as there is only one way to interact with data.

The way variables are implemented in stack-oriented languages such as PostScript usually involves a separate, specialized stack which holds dictionaries of key-value pairs. To create a variable, a key (the variable name) must be created first, with which a value is then associated. In PostScript, a name data object is prefixed with a /, so /x is a name data object which can be associated with, for example, the number 42. The define command is def, so

/x 42 def

associates with the name x with the number 42 in the dictionary atop the stack. A difference exists between /x and x – the former is a data object representing a name, and x stands for what is defined under /x.

Procedures

A procedure in a stack-based programming language is treated as a data object in its own right. In PostScript, procedures are denoted between { and }.

For example, in PostScript syntax,

{ dup mul }

represents an anonymous procedure to duplicate what is on the top of the stack and then multiply the result – a squaring procedure.

Since procedures are treated as simple data objects, names with procedures can be defined. When they are retrieved, they are executed directly.

Dictionaries provide a means of controlling scoping, as well as storing definitions.

Since data objects are stored in the top-most dictionary, an unexpected ability arises naturally: when looking up a definition from a dictionary, the topmost dictionary is checked, then the next, and so on. If a procedure is defined that has the same name as another already defined in a different dictionary, the local one will be called.

Anatomy of some typical procedures

Procedures often take arguments. They are handled by the procedure in a very specific way, different from that of other programming languages.

To examine a Fibonacci number program in PostScript:

/fib { dup dup 1 eq exch 0 eq or not { dup 1 sub fib exch 2 sub fib add } if } def

يُستخدم تعريف تكراري على المكدس. تأخذ دالة أعداد فيبوناتشي وسيطًا واحدًا. أولًا، يتم اختباره لمعرفة ما إذا كان يساوي 1 أو 0.

تحليل كل خطوة من الخطوات الرئيسية للبرنامج، مع مراعاة بنية المكدس، بافتراض حساب ما يلي fib(4) :

 عدد الأكوام: 4 مكرر المكدس: 4 4 مكرر المكدس: 4 4 4 1 مكافئ المكدس: 4 4 خطأ صرافة المكدس: 4 خطأ 4 0 مكافئ المكدس: 4 خطأ خطأ أو المكدس: 4 خطأ لا المكدس: 4 صحيح

بما أن التعبير يُقيّم إلى صحيح، يتم تقييم الإجراء الداخلي.

 عدد الأكوام: 4 مكرر المكدس: 4 4 1 فرعي المكدس: 4 3 فيبوناتشي
(استدعاء متكرر هنا)
 المكدس: 4 F(3) صرافة المكدس: F(3) 4 2 فرعي المكدس: F(3) 2 فيبوناتشي
(استدعاء متكرر هنا)
 المكدس: F(3) F(2) يضيف المكدس: F(3)+F(2)

وهي النتيجة المتوقعة.

لا تستخدم هذه العملية متغيرات مُسماة، بل تعتمد كليًا على المكدس. يمكن إنشاء متغيرات مُسماة باستخدام /a exch defالبنية. على سبيل المثال،{/n exch def n n mul}

هي عملية تربيع بمتغير مُسمى n. بافتراض أن /sq {/n exch def n n mul} defو 3 sqيتم استدعاء ، يتم تحليل العملية sqبالطريقة التالية:

 المكدس: 3 /ن صرافة المكدس: /n 3 تعريف المكدس: فارغ (تم تعريفه) ن المكدس: 3 ن المكدس: 3 3 مول المكدس: 9

وهي النتيجة المتوقعة.

التحكم والتدفق

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

2 3 gt { (2 أكبر من 3) = } { (2 ليس أكبر من 3) = } ifelse

يؤدي وظيفة مماثلة تقريبًا في لغة C:

إذا كان ( 2 > 3 ) { اطبع ( "2 أكبر من ثلاثة \n " ); } وإلا { اطبع ( "2 ليس أكبر من ثلاثة \n " ); }

تتشابه عمليات التكرار وغيرها من البنى.

تحليل نموذج اللغة

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

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

انظر أيضاً

مراجع

  1. ↑ لورفيج، ت. (2015). نماذج البرمجة القائمة على المكدس. مفاهيم لغات البرمجة - CoPL'15، 33.
  2. ↑ أورين باتاشنيك، تصميم أنماط BibTeX (ملف PDF)