تطبیق الگو

در علوم کامپیوتر، تطبیق الگو چک کردن دنباله‌ای از نشانه‌ها به منظور حضور ترکیباتی از برخی الگو هاست. در مقایسه با شناسایی الگو، الگوی منطبق همیشه باید کاملاً همان الگوی مقایسه شده باشد. الگوها عموماً به شکل رشته یا ساختار درخت هستند. کاربردهای تطبیق الگو شامل یافتن یک الگوی نشانه در یک توالی (در صورت وجود) و نمایش آن در خروجی، نمایش برخی از اجزای الگوی همسان در خروجی، و جایگزین کردن الگوی تطبیق با برخی رشته‌های دیگر است. (به عنوان مثال جستجو و جایگزینی)

الگوهای رشته‌ای (مانند متنی از رشته‌ها) معمولاً با استفاده از عبارت باقاعده و تکنیک‌ها مانند عقب‌گرد تشریح می‌شوند.

ساختارهای درختی در برخی زبان‌های برنامه‌نویسی به عنوان یک ابزار کلی برای انجام فر آیند روی داده‌ها بر اساس ساختارشان، مانند … استفاده شده‌اند و زبان سمبولیک ریاضی به نام متمتیکا سینتکس مخصوص خود، برای نمایش الگوهای درختی و ساختار زبانی برای اجرای شرطی و بازیابی ارزش بر اساس آن است. به منظور تأمین سادگی و کارایی، این الگوهای درخت فاقد برخی از ویژگی‌هایی است که در عبارات منظم در دسترس هستند.

معمولاً می‌توان الگوهای پیشنهادی که تک به تک امتحان شده، تا یک ساختار برنامه‌نویسی شرطی قوی را به دست دهد، پیشنهاد داده شود.

تاریخچه

اولین برنامه‌های کامپیوتری که از تطبیق الگو استفاده کردند، ویرایش‌گر‌های متن هستند. در آزمایشگاه‌های بل، کن تامسون برای پوشش عبارت باقاعده ویژگی‌های جستجو و جایگذاری در QED‌ها را گسترش دادند. زبان‌های برنامه‌نویسی اولیه با ساختار تطبیق الگو شامل زبان اسنوبول در سال ۱۹۶۲، SASL در سال ۱۹۷۶، NPL در ۱۹۷۷، و KRC در ۱۹۸۱. زبان‌های برنامه‌نویسی اولیه که تطبیق الگوی مبتنی بر درخت داشتند، گسترش لیسپ توسط Fred McBride، در سال ۱۹۷۰ هستند.

الگوهای اولیه

ساده‌ترین الگو در تطبیق الگو یک متغیر یا مقدار صریح است. به عنوان مثال، یک تابع Haskell با سینتکس ساده را فرض کنید (پارامترهای تابع در پرانتز نمی‌آیند، = به معنای مساوی نیست، بلکه به معنی تعریف است):

 f 0 = 1

در اینجا، ۰ یک الگو ی تک مقداری است. اکنون، هروقت ۰ به عنوان ورودی به f داده شود، الگو مطابقت می‌کند و تابع ۱ برمی‌گرداند. با هر ورودی دیگری، تابع کار نمی‌کند. برای اینکه سینتکس الگوهای پیشنهادی دیگر را در تعریف تابع پشتیبانی کند، می‌توانیم تعریف را به این صورت گسترش دهیم:

 f n = n * f (n-1)

در اینجا، اولین n یک الگوی تک مقداری است، که قطعاً هر مقداری در آن صدق می‌کند. در، الگوها به ترتیب امتحان می‌شوند بنابراین اولین تعریف حتماً برای صفر صدق می‌کند، همان‌طور که برای بقیه ورودی‌ها تابع به ازای هر ورودی، (n * f (n-1 را برمیگردند. الگوی کلمات (معمولاً به شکل _ نوشته می‌شوند) نیز ساده است: مانند نام متغیر، که با هر مقداری تطبیق می‌کند، اما هر مقداری را به هر اسمی اضافه نمی‌کند.

الگوهای درختی

الگوهای پیچیدهٔ بیشتری می‌توانند از الگوهای اولیهٔ بخش قبل ساخته شوند، معمولاً همان‌طور که مقادیر از ترکیب مقادیر دیگر به‌دست می‌آیند. تفاوت در اینجاست که برای کلمات و متغیرها، یک الگو به یک تک مقدار ساخته نمی‌شود، اما با گروهی از مقادیر که ترکیبی از المان‌های صریح اند و المان‌هایی که اجازهٔ تمایز با ساختار الگو را دارند، مطابقت می‌کنند.

در Haskell، خطی که در ادامه آمده‌است یک نوع دادهٔ جبری را تعریف می‌کند Color که یک سازندهٔ یکتای داده دارد ColorConstructor که یک رشته و یک عدد را پوشش می‌دهد.

 data Color = ColorConstructor Integer String

سازنده راسی در درخت است و عدد و رشته برگ‌های روی شاخه‌ها هستند.

وقتی می‌خواهیم بنویسیم functions که یک نوع داده انتزاعی از Color بسازیم، می‌خواهیم تابع‌ها را در interface با نوع داده‌ها بنویسیم، و بنابراین می‌خواهیم مقداری از نوع داده را از داده بیرون بکشیم، به عنوان مثال، فقط بخش عددی یا فقط بخش رشته‌ای از Color.

اگر یک متغیر را که از نوع color است را بدهیم، چگونه می‌توانیم داده را از این متغیر بیرون بکشیم؟ به عنوان مثال برای یک تابع برای گرفتن قسمت عددی Color، می‌توانیم یک الگوی سادهٔ درخت استفاده کنیم و بنویسیم:

 integerPart (ColorConstructor theInteger _) = theInteger

همین‌طور داریم:

 stringPart (ColorConstructor _ theString) = theString

ایجاد این تابع می‌تواند توسط سینتکس ضبط شدهٔ داده، اتوماتیک انجام شود.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «pattern matching». در دانشنامهٔ ویکی‌پدیای انگلیسی.