مطابقة النمط

هذا المقال هو عن pattern matching in functional programming. إذا كنت تريد الاستخدامات الأخرى، انظر string matching و pattern recognition.
لمعلومات عن the use of variable matching criteria in defining abstract patterns to match، انظر regular expression.

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

غالباً ما يتم وصف أنماط التسلسل (على سبيل المثال ، سلسلة نصية) باستخدام تعبير منتظم ومطابقتها باستخدام تقنيات مثل المراجعة.

تُستخدم أنماط الشجرة في بعض لغات البرمجة كأداة عامة لمعالجة البيانات بناءً على هيكلها، على سبيل المثال C#[1] F#،[2] هسكل، إم‌إل، رَست،[3] سكالا،[4] سويفت[5] ولغة الرياضيات الرمزية ماثماتيكا التي لها صيغة خاصة للتعبير عن الأنماط الشجرية و بناء اللغة لـ التنفيذ الشرطي واسترجاع القيمة على أساسها.

غالباً ما يكون من الممكن إعطاء أنماط بديلة يتم تجربتها واحداً تلو الآخر، مما ينتج عنه بناء البرمجة الشرطية. تتضمن مطابقة الأنماط أحياناً دعماً لـ الحماية.[بحاجة لمصدر]

تعتمد الخوارزميات التحليل غالباً على مطابقة النمط لتحويل السلاسل إلى شجرة التركيب.[6][7]

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

تاريخ

كانت برامج الحاسب هي الأولى التي استخدمت مطابقة الأنماط هي برامج تحرير النصوص.[بحاجة لمصدر]في مختبرات بل، وسع كن تومسن البحث عن ميزات لـ محرر QED واستبدالها لقبول التعبيرات المنتظمة. تشمل لغات البرمجة الأولية مع تركيبات مطابقة الأنماط SNOBOL من عام 1962، ولغة Refal السوفياتية من عام 1968 مع مطابقة الأنماط القائمة على الأشجار، ساسل من 1976 إن‌پي‌إل من عام 1977، و KRC من عام 1981. لغة برمجة أخرى مع ميزات مطابقة الأنماط القائمة على الأشجار كانت ملحق فريد مك‌بريد لـ ليسپ، في عام 1970.[8]

انظر أيضاً: تعبير منتظم § History


الأنماط البسيطة

أبسط نمط في مطابقة النمط هو قيمة صريحة أو متغير. على سبيل المثال، ضع في اعتبارك تعريف دالة بسيط في صيغة هسكل (لا تكون پارامترات الدالة بين قوسين ولكنها مفصولة بمسافات، = ليست تعييناً ولكنها تعريف): 

f 0 = 1

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

f n = n * f (n-1)

هنا، أول n هو نمط متغير واحد، والذي سيتطابق تماماً مع أي وسيطة وربطه بالاسم n ليتم استخدامه في بقية التعريف. في هسكل (على عكس هوپ على الأقل، تتم تجربة الأنماط بالترتيب بحيث يظل التعريف الأول سارياً في الحالة المحددة جداً للإدخال 0، بينما تُرجع الدالة n * f (n-1) لأي وسيطة أخرى حيث تكون n هي الوسيطة.

نمط أحرف البدل (غالباً ما يُكتب كـ _) بسيط أيضاً: مثل اسم المتغير، فإنه يطابق أي قيمة، لكنه لا يربط القيمة بأي اسم. تم تطوير خوارزميات لـ أحرف البدل المطابقة في حالات مطابقة السلسلة البسيطة في عدد من التكرارية والأصناف غير التكرارية.[9]

أنماط الشجرة

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

يصف نمط الشجرة جزءاً من شجرة بالبدء بالعقدة وتحديد بعض الفروع والعقد وترك بعضها غير محدد بنمط متغير أو حرف بدل. قد يكون من المفيد التفكير في شجرة النحو المجردة للغة البرمجة و نوع البيانات الجبرية.

في هسكل، يحدد السطر التالي نوع البيانات الجبرية Color الذي يحتوي على مُنشئ بيانات واحد ColorConstructor الذي يلتف بعدد صحيح وسلسلة. 

data Color = ColorConstructor Integer String

المُنشئ هو عقدة في شجرة ويكون العدد الصحيح والسلسلة أوراقاً في فروع.

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

إذا مررنا متغيراً من النوع Color، فكيف يمكننا إخراج البيانات من هذا المتغير؟ على سبيل المثال، للحصول على دالة للحصول على الجزء الصحيح من Color، يمكننا استخدام نمط شجرة بسيط وكتابة: 

integerPart (ColorConstructor theInteger _) = theInteger

أيضاً: 

stringPart (ColorConstructor _ theString) = theString

يمكن أتمتة إنشاء هذه الدوال من خلال بناء جملة بيانات سجل هسكل.

يوضح مثال أوكَمل الذي يعرّف شجرة حمراء - سوداء ودالة لإعادة توازنها بعد إدراج عنصر يوضح كيفية المطابقة في بنية أكثر تعقيداً تم إنشاؤها بواسطة نوع بيانات متكرر. 

type color = Red | Black
type 'a tree = Empty | Tree of color * 'a tree * 'a * 'a tree

let rebalance t = match t with
    | Tree (Black, Tree (Red, Tree (Red, a, x, b), y, c), z, d)
    | Tree (Black, Tree (Red, a, x, Tree (Red, b, y, c)), z, d)                                  
    | Tree (Black, a, x, Tree (Red, Tree (Red, b, y, c), z, d))
    | Tree (Black, a, x, Tree (Red, b, y, Tree (Red, c, z, d)))
        ->  Tree (Red, Tree (Black, a, x, b), y, Tree (Black, c, z, d))
    | _ -> t (* the 'catch-all' case if no previous pattern matches *)

ترشيح البيانات مع الأنماط

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

[A x|A x <- [A 1, B 1, A 2, B 2]]

بتقييم 

[A 1, A 2]

مطابقة الأنماط في الرياضيات

في الرياضيات، الهيكل الوحيد الموجود هو الشجرة، والتي يتم ملؤها بالرموز. في صيغة هسكل المستخدمة حتى الآن، يمكن تعريف هذا على أنه 

data SymbolTree = Symbol String [SymbolTree]

يمكن أن تبدو الشجرة كمثال بعد ذلك 

Symbol "a" [Symbol "b" [], Symbol "c" [] ]

في الصيغة التقليدية الأكثر ملاءمة، تتم كتابة الرموز كما هي ويتم تمثيل مستويات الشجرة باستخدام []، بحيث تكون a[b,c] على سبيل المثال شجرة بها الأصل، وb وc كتوابع. يتضمن النمط في الرياضيات وضع "_" في مواضع في تلك الشجرة. على سبيل المثال، النمط 

A[_]

سيطابق عناصر مثل A[1], A[2] أو بشكل عام A[x] حيث يمثل x أي كيان. في هذه الحالة، A هو العنصر الملموس ، بينما يشير _ إلى قطعة الشجرة التي يمكن تنويعها. يربط الرمز المُضاف مسبقًا إلى _ المطابقة مع اسم المتغير هذا بينما يقيد الرمز الملحق بـ _ التطابقات مع عقد ذلك الرمز. لاحظ أنه حتى الفراغات نفسها يتم تمثيلها داخلياً على أنها Blank[] لـ _ و Blank[x] لـ _x.

تقوم دالة الرياضيات Cases بترشيح عناصر الوسيط الأول التي تطابق النمط الموجود في الوسيط الثاني:[10] 

Cases[{a[1], b[1], a[2], b[2]}, a[_] ]

بتقييم 

{a[1], a[2]}

تنطبق مطابقة الأنماط على هيكل التعبيرات. في المثال أدناه، 

Cases[ {a[b], a[b, c], a[b[c], d], a[b[c], d[e]], a[b[c], d, e]}, a[b[_], _] ]

معيداً 

{a[b[c],d], a[b[c],d[e]]}

لأن هذه العناصر فقط هي التي ستطابق النمط a[b[_],_] أعلاه.

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

fib[0|1]:=1
fib[n_]:= fib[n-1] + fib[n-2]

بعد ذلك، يمكننا طرح السؤال: بالنظر إلى fib[3]، ما هو تسلسل استدعاءات فيبوناتشي التكرارية؟ 

Trace[fib[3], fib[_]]

معيداً بنية تمثل تكرارات النمط fib[_] في البنية الحسابية: 

{fib[3],{fib[2],{fib[1]},{fib[0]}},{fib[1]}}

البرمجة التصريحية

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

على سبيل المثال، يمكن استخدام دالة الرياضيات Compile لعمل إصدارات أكثر كفاءة من الكود. في المثال التالي لا تهم التفاصيل بشكل خاص؛ ما يهم هو أن التعبير الفرعي Compile يقوم بتوجيه Compile أن التعبيرات ذات الشكل com[_] يمكن افتراض أنها أعداد صحيحة لأغراض التجميع: 

com[i_] := Binomial[2i, i]
Compile[{x, {i, _Integer}}, x^com[i], {{com[_],  Integer}}]

تعمل علب البريد في إرلانگ بهذه الطريقة أيضاً.

يتعلق توافق كيري–هاورد بين البراهين والبرامج بمطابقة النمط بنمط- إم‌إل مع تحليل الحالات و الإثبات بالإسهاب.

مطابقة النمط والسلاسل

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

ومع ذلك، من الممكن إجراء قليل من مطابقات نمط السلسلة ضمن نفس الإطار الذي تمت مناقشته في هذه المقالة.

أنماط الشجرة للسلاسل

في الرياضيات، يتم تمثيل السلاسل كأشجار أصل سلسلة تعبيرات StringExpression وجميع الأحرف بالترتيب كتوابع للأصل. وبالتالي، لمطابقة "أي كمية من الأحرف اللاحقة"، يلزم وجود حرف بدل جديد ___ على عكس _ الذي يطابق حرفاً واحداً فقط.

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

[] -- an empty list
x:xs -- an element x constructed on a list xs

وبالتالي فإن بنية القائمة التي تحتوي على بعض العناصر هي element:list. عند مطابقة النمط، نؤكد أن جزءاً معيناً من البيانات يساوي نمطاً معيناً. على سبيل المثال، في الدالة: 

head (element:list) = element

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

في المثال، ليس لدينا أي استخدام لـ list، لذلك يمكننا تجاهلها، وبالتالي كتابة الدالة: 

head (element:_) = element

يتم التعبير عن تحويل الرياضياتي المكافئ 

head[element, ]:=element

مثال على أنماط السلسلة

في الرياضيات، على سبيل المثال، 

StringExpression["a",_]

سيطابق سلسلة مكونة من حرفين وتبدأ بحرف "a".

نفس النمط في هسكل: 

['a', _]

يمكن تقديم الكيانات الرمزية لتمثيل العديد من الفئات المختلفة للميزات ذات الصلة بسلسلة. على سبيل المثال، 

StringExpression[LetterCharacter, DigitCharacter]

سيطابق سلسلة تتكون من حرف أولاً، ثم رقم.

في هاسكل، يمكن استخدام الحماية لتحقيق نفس المطابقات: 

[letter, digit] | isAlpha letter && isDigit digit

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

SNOBOL

المقالة الرئيسية: SNOBOL

SNOBOL (StriNg Oriented and symBOlic Language) لغة السلسلة الموجهة والرمزية وهي عبارة عن لغة برمجة حاسوبية تم تطويرها بين عامي 1962 و 1967 في مختبرات بل آي‌تي آند تي بواسطة ديڤد جاي. فاربر ، رالف إي. گريسوولد و إيڤان پي. پولونسكي.

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

تم تدريس SNOBOL على نطاق واسع في جامعات أمريكية أكبر في أواخر الستينيات وأوائل السبعينيات، واستخدم على نطاق واسع في السبعينيات والثمانينيات كلغة لمعالجة النص في العلوم الإنسانية.

منذ إنشاء SNOBOL، جعلت اللغات الأحدث مثل آوك و پرل من تعديل السلسلة عن طريق التعبيرات المنتظمة أمراً شائعاً. ومع ذلك، فإن أنماط SNOBOL4 تشتمل على قواعد BNF النحوية، والتي تعادل قواعد خالية من السياق أكثر قوة من التعبيرات المنتظمة.[11]


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

انظر أيضاً

المراجع

  1. ^ "Pattern Matching - C# Guide".
  2. ^ "Pattern Matching - F# Guide".
  3. ^ "Pattern Syntax - The Rust Programming language".
  4. ^ "Pattern Matching". Scala Documentation. Retrieved 2021-01-17.
  5. ^ "Patterns — The Swift Programming Language (Swift 5.1)".
  6. ^ Warth, Alessandro, and Ian Piumarta. "OMeta: an object-oriented language for pattern matching." Proceedings of the 2007 symposium on Dynamic languages. ACM, 2007.
  7. ^ Knuth, Donald E., James H. Morris, Jr, and Vaughan R. Pratt. "Fast pattern matching in strings." SIAM journal on computing 6.2 (1977): 323-350.
  8. ^ "Archived copy". Archived from the original on 2007-02-03. Retrieved 2007-04-14.{{cite web}}: CS1 maint: archived copy as title (link)
  9. ^ Cantatore, Alessandro (2003). "Wildcard matching algorithms".
  10. ^ "Cases—Wolfram Language Documentation". reference.wolfram.com. Retrieved 2020-11-17.
  11. ^ Gimpel, J. F. 1973. A theory of discrete patterns and their implementation in SNOBOL4. Commun. ACM 16, 2 (Feb. 1973), 91–100. DOI=http://doi.acm.org/10.1145/361952.361960.

وصلات خارجية

 هناك كتاب ، Haskell، في معرفة الكتب.


مشاع المعرفة فيه ميديا متعلقة بموضوع [[commons: Category:مطابقة النمط

| مطابقة النمط

]].

قالب:Strings

الكلمات الدالة:
تمّ الاسترجاع من "https://www.marefa.org/w/index.php?title=مطابقة_النمط&oldid=2294661"