تعبير S

الموسوعة الحرة
بنية بيانات شجرية تمثل التعبير S(* 2 (+ 3 4))

في برمجة الحاسوب ، يُعرف التعبير الرمزي (أو التعبير S ، ويُختصر إلى sexpr أو sexp ) بأنه تعبير يُستخدم في ترميز مُشابه لتمثيل بيانات القوائم المتداخلة ( ذات البنية الشجرية ). وقد طُوّرت التعبيرات الرمزية (S-expressions) خصيصًا للغة البرمجة Lisp ، التي تستخدمها في كلٍ من شفرة المصدر والبيانات.

صفات

في الصيغة المعتادة للغة ليسب، يُعرَّف التعبير S بشكل كلاسيكي [ 1 ] على النحو التالي:

  1. ذرة من الشكل x ، أو
  2. تعبير من الشكل ( x.y ) حيث x و y تعبيرات S.​

يعكس هذا التعريف تمثيل لغة ليسب للقائمة كسلسلة من "الخلايا"، كل منها عبارة عن زوج مرتب . في القوائم البسيطة، يشير y إلى الخلية التالية (إن وجدت)، مُشكلاً بذلك قائمة . تعني العبارة التكرارية في التعريف أن كلاً من هذا التمثيل وصيغة S-expression يمكنهما تمثيل أي شجرة ثنائية . مع ذلك، يمكن لهذا التمثيل من حيث المبدأ أن يسمح بالمراجع الدائرية ، وفي هذه الحالة لا يكون الهيكل شجرة على الإطلاق، بل رسمًا بيانيًا دوريًا ، ولا يمكن تمثيله بصيغة S-expression الكلاسيكية إلا إذا تم توفير اتفاقية للمراجع المتبادلة، على غرار المفاتيح الخارجية في SQL ، و SGML / XML IDREFs، وما إلى ذلك. توفر لهجات ليسب الحديثة، مثل Common Lisp [ 2 ] و Scheme [ 3 ]، مثل هذه الصيغة عبر تسميات البيانات ، التي يمكن من خلالها تمييز الكائنات، والتي يمكن أن تتكرر في أماكن أخرى، مما يشير إلى بنية مشتركة وليست مكررة، مما يُمكّن القارئ أو الطابعة من اكتشاف الدورات، وبالتالي تشغيل تقييمها أو عرضها دون تكرار لا نهائي.

#n=(xy . #n#)

يختلف تعريف الذرة حسب السياق؛ في التعريف الأصلي لجون مكارثي ، [ 1 ] كان من المفترض أن هناك "مجموعة لا نهائية من الرموز الذرية المميزة " ممثلة على أنها "سلاسل من الأحرف اللاتينية الكبيرة والأرقام مع فراغات مضمنة مفردة" (مجموعة فرعية من سلسلة الأحرف والقيم العددية ).

تسمح معظم تدوينات التعبيرات النصية الحديثة بسلاسل نصية مُقتبسة أكثر عمومية (على سبيل المثال، تضمين علامات الترقيم أو رموز يونيكود كاملة )، وتستخدم تدوينًا مختصرًا لتمثيل القوائم التي تحتوي على أكثر من عنصرين، بحيث

(xyz)

يرمز إلى

(x . (y . (z . NIL)))

NILهو كائن نهاية القائمة الخاص (يكتب بشكل بديل ()، وهو التمثيل الوحيد في Scheme [ 4 ] ).

في عائلة لغات البرمجة Lisp، تُستخدم تعابير S لتمثيل كلٍ من شفرة المصدر والبيانات. وتُستخدم أيضًا في لغات مشتقة من Lisp مثل DSSSL ، وكعلامات ترميز في بروتوكولات الاتصال مثل IMAP و CBCL لجون مكارثي . كما تُستخدم كتمثيل نصي لـ WebAssembly . تختلف تفاصيل بناء الجملة وأنواع البيانات المدعومة بين اللغات المختلفة، ولكن السمة الأكثر شيوعًا بينها هي استخدام تعابير S ورمز البادئة.

أنواع البيانات وبنية الجملة

توجد العديد من صيغ التعبير S، التي تدعم مجموعة متنوعة من الصيغ المختلفة لأنواع البيانات المختلفة. وأكثرها شيوعًا هي:

  • القوائم والأزواج :(1 () (2 . 3) (4))
  • الرموز :with-hyphen?@!$|a symbol with spaces|
  • السلاسل النصية :"Hello, world!"
  • الأعداد الصحيحة :-9876543210
  • الأرقام العشرية :-0.06.283186.022e23

غالباً ما يتم استخدام الحرف #كبادئة لامتدادات بناء الجملة، على سبيل المثال #x10للأعداد الصحيحة السداسية عشرية، أو #\Cللأحرف.

الاستخدامات

الاستخدام في لغة ليسب

عند تمثيل الشيفرة المصدرية في لغة ليسب، يكون العنصر الأول من التعبير S عادةً اسم عامل أو دالة، وتُعامل العناصر المتبقية كوسائط. يُطلق على هذا "التدوين البادئ" أو " التدوين البولندي ". على سبيل المثال، يُكتب التعبير المنطقي4 == (2 + 2) بلغة C ، ويُمثَّل كما هو (= 4 (+ 2 2))في تدوين ليسب البادئ القائم على التعبير S.

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

يتم تنفيذ الحالة المتكررة لتعريف التعبيرات S تقليديًا باستخدام خلايا cons .

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

يمكن كتابة القوائم المتداخلة على شكل تعابير S: ((milk juice) (honey marmalade))هي تعبير S ثنائي العناصر، وعناصرها أيضًا تعبيرات S ثنائية العناصر. يُعدّ استخدام المسافات البيضاء في لغة Lisp (وفي هذه المقالة) شائعًا. عادةً ما تُستخدم فواصل الأسطر (أحرف السطر الجديد) كفواصل. هذه قواعد نحوية بسيطة خالية من السياق لمجموعة فرعية صغيرة من اللغة الإنجليزية مكتوبة على شكل تعبير S، [ 5 ] حيث S = جملة، NP = عبارة اسمية، VP = عبارة فعلية، V = فعل.

((( S ) ( NP VP )) (( VP ) ( V )) (( VP ) ( V NP )) (( V ) توفي ) (( V ) موظف ) (( NP ) ممرضات ) (( NP ) مرضى ) (( NP ) مركز طبي ) (( NP ) "دكتور تشان" ))

يمكن كتابة كود البرنامج باستخدام تعابير S، وعادةً ما يتم ذلك باستخدام تدوين البادئة. مثال في لغة Common Lisp :

( defun factorial ( x ) ( if ( zerop x ) 1 ( * x ( factorial ( - x 1 )))))

يمكن قراءة تعابير S في لغة Lisp باستخدام الدالة READ. تقرأ هذه الدالة التمثيل النصي لتعبير S وتعيد بيانات Lisp. يمكن استخدام الدالة PRINT لإخراج تعبير S. بعد ذلك، يمكن قراءة الناتج باستخدام الدالة READ، عندما يكون لجميع عناصر البيانات المطبوعة تمثيل قابل للقراءة. توفر Lisp تمثيلات قابلة للقراءة للأرقام، والسلاسل النصية، والرموز، والقوائم، والعديد من أنواع البيانات الأخرى. يمكن تنسيق كود البرنامج كتعابير S منسقة باستخدام الدالة PPRINT (ملاحظة: PPRINT اختصارًا لـ pretty -print).

برامج لغة ليسب هي تعبيرات S صالحة، ولكن ليس كل تعبير S برنامج ليسب صالح. (1.0 + 3.1)التعبير S صالح، ولكنه ليس برنامج ليسب صالحًا، لأن ليسب تستخدم تدوين البادئة، والعدد العشري (هنا 1.0) غير صالح كعملية (العنصر الأول من التعبير).

إن التعبير S الذي يسبقه علامة اقتباس واحدة، كما في 'x، هو اختصار نحوي للتعبير S المقتبس ، في هذه الحالة (quote x).

استخدامات أخرى

تُستخدم تعابير S أيضًا لتنسيق نص WebAssembly .

العلاقة بـ XML

غالبًا ما تُقارن تعابير S بلغة XML : أحد الفروق الرئيسية هو أن تعابير S لها شكل واحد فقط للاحتواء، وهو الزوج المنقط، بينما يمكن أن تحتوي وسوم XML على سمات بسيطة، أو وسوم أخرى، أو بيانات CDATA ، ولكل منها صيغة مختلفة. فرق آخر هو أن تعابير S لا تُحدد آلية مرجعية، بينما تُوفر XML مفهوم المعرفات الفريدة والمراجع إليها. في حالات الاستخدام البسيطة، تُعد تعابير S أبسط من XML، ولكن في حالات الاستخدام الأكثر تعقيدًا، تحتوي XML على لغة استعلام تُسمى XPath، والتي تستخدمها العديد من الأدوات ومكتبات الطرف الثالث لتبسيط التعامل مع بيانات XML.

التقييس

تتضمن معايير بعض لغات البرمجة المشتقة من لغة ليسب مواصفات لبنية تعبيرات S الخاصة بها. وتشمل هذه اللغات: كومون ليسب (وثيقة معيار ANSI ANSI INCITS 226-1994 (R2004))، وسكيم (R5RS و R6RS [ 6 ] )، و ISLISP .

في مايو 1997، قدّم رون ريفست مسودة إنترنت [ 7 ] للنظر في نشرها كوثيقة RFC . عرّفت المسودة صيغةً مبنيةً على تعابير S في لغة Lisp، ولكنها كانت مُخصصةً لتخزين البيانات وتبادلها للأغراض العامة (على غرار XML ) بدلاً من استخدامها في البرمجة تحديدًا. لم تُعتمد المسودة كوثيقة RFC، ولكن تم الاستشهاد بها واستخدامها لاحقًا في وثائق RFC أخرى (مثل RFC 2693) والعديد من المنشورات الأخرى. [ 8 ] كان الهدف الأصلي من استخدامها في SPKI .

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

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

لم يُعتمد هذا التنسيق على نطاق واسع للاستخدام خارج نطاق SPKI (ومن بين مستخدميه GnuPG وlibgcrypt و Netttle و GNU lsh). توفر صفحة Rivest الإلكترونية الخاصة بتعبيرات S شفرة مصدرية بلغة C لمحلل ومولد (متاحة بموجب ترخيص MIT )، والتي يمكن تعديلها وتضمينها في برامج أخرى. [ 9 ] إضافةً إلى ذلك، لا توجد قيود على تنفيذ هذا التنسيق بشكل مستقل.

انظر أيضاً

مراجع

  1. 1 2 جون مكارثي (1960/2006). الدوال التكرارية للتعبيرات الرمزية. مؤرشف في 2004-02-02 على موقع Wayback Machine . نُشر أصلاً في مجلة Communications of the ACM .
  2. ↑ "Common Lisp HyperSpec: 22.4 - قاموس الطابعة: *PRINT-CIRCLE*" . 2018-12-28.
  3. ↑ "التقرير السابع المنقح حول مخطط لغة الخوارزميات: القسم 2.4: تسميات البيانات" (PDF) . 2013-07-06.
  4. ↑ "تقرير منقح^5 حول لغة البرمجة الخوارزمية " schemers.org .
  5. ↑ جي. غازدار، تش. ميليش، معالجة اللغة الطبيعية في لغة ليسب
  6. ↑ سبيربر، مايكل؛ ديبفيج، آر. كينت؛ فلات، ماثيو؛ فان ستراتن، أنطون؛ فيندلر، روبي؛ ماثيوز، جاكوب (12 أغسطس 2009). "تقرير منقح حول لغة البرمجة الخوارزمية Scheme". مجلة البرمجة الوظيفية . 19 (ملحق 1): 1-301 . CiteSeerX 10.1.1.372.373 . doi : 10.1017/S0956796809990074 . S2CID 267822156 .  
  7. ↑ تعابير S ، مجموعة عمل الشبكة، مسودة إنترنت، تاريخ الانتهاء 4 نوفمبر 1997 - ر. ريفست، 4 مايو 1997 draft-rivest-sexp-00.txt، رونالد ل. ريفست، موقع CSAIL التابع لمعهد ماساتشوستس للتكنولوجيا
  8. ↑ rivest sexp ، بحث في جوجل سكولار
  9. ↑ "SEXP (تعبيرات S)" . people.csail.mit.edu . مؤرشف من الأصل بتاريخ 23-02-2023 . تم الاطلاع عليه بتاريخ 05-05-2023 .