موضوع مقاله: برنامه‌نویسی تابعی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # برنامه‌نویسی تابعی | مقدمه: در علوم کامپیوتر، برنامه‌نویسی تابعی یک رویکرد برنامه‌نویسی است که در آن برنامه‌ها توسط محاسبه و ترکیب توابع ساخته می‌شوند. | ## بخش 1: برنامه‌نویسی تابعی | برنامه‌نویسی تابعی یک رویکرد برنامه‌نویسی اعلانی است که در آن تعریف توابع درخت‌هایی از عبارت‌ها هستند که هر کدام از این عبارات به جای یک توالی از عبارات دستوری که وضعیت برنامه را تغییر می‌دهند؛ صرفاً یک مقدار برمی‌گردانند. در برنامه‌نویسی تابعی، توابع به عنوان شهروندان درجه یک تلقی می‌شوند، این بدان معنی است که توابع را می‌توان به نام‌ها (از جمله شناسه‌های محلی) مقید کرده، به عنوان آرگومان ارسال کرده و یا از توابع دیگر بازگرداند. این ویژگی این امکان را فراهم می‌کند که برنامه‌ها به شکل اعلانی و ترکیب‌پذیر نوشته شوند، به‌طوری که که توابع کوچک به صورت پودمانی با هم ترکیب می‌شوند. برنامه‌نویسی تابعی گاهی به عنوان مترادفی برای برنامه‌نویسی تابعی محض در نظر گرفته می‌شود. این نوع برنامه‌نویسی زیرمجموعه‌ای از برنامه‌نویسی تابعی است که در آن تمام توابع به عنوان توابع ریاضی و قطعی یا تابع سره تلقی می‌شوند. هنگامی که یک تابع سره با مجموعهٔ آرگومان‌های ثابت فراخونی می‌شود، همیشه همان نتیجه را برمی‌گرداند و نمی تواند تحت تأثیر هیچ‌گونه حالت قابل تغییر یا اثر جانبی دیگری باشد. این برخلاف توابع غیرسره است که معمولاً در برنامه‌نویسی دستوری استفاده می‌شود و می‌تواند اثرات جانبی داشته باشد (مانند تغییر وضعیت برنامه یا گرفتن ورودی از یک کاربر). طرفداران برنامه‌نویسی تابعی محض ادعا می‌کنند که با محدود کردن اثر جانبی، برنامه‌ها اشکالات کمتری داشته؛ همچنین اشکال‌زدایی و تست نرم‌افزار آسان‌تر می‌شود. از سوی دیگر استفاده از این رویکرد برای دستیابی به درستی‌یابی صوری نرم‌افزار مناسب‌تر است. منشأ برنامه‌نویسی تابعی ریشه در تحقیقات دانشگاهی دارد و از حساب لامبدا تکامل پیدا کرده است. از جمله لیسپ معمولی، اسکیم، کلوژر ، زبان برنامه‌نویسی ولفرام، راکت ، ارلنگ، اوکمل، هسکل، و F#. برنامه‌نویسی تابع‌گرا همچنین برای برخی از زبان‌های خاص‌منظوره موفق نقش کلیدی ایفا می‌کند. همچنین بسیاری از زبان‌های برنامه‌نویسی، برنامه‌‌نویسی به سبک تابع‌گرا را پشتیبانی کرده و یا ویژگی‌های تابع‌گرایی پیاده‌سازی کرده‌اند. تاریخچه جبر لاندا که در دههٔ ۱۹۳۰ توسط آلونزو چرچ ابداع شد، یک سیستم صوری محاسباتی است که براساس کاربرد توابع ساخته شده است. در سال ۱۹۳۷ تورینگ ثابت کرد که حساب لاندا و ماشین تورینگ مدل‌های محاسباتی هم‌ارز هستند. همچنین یک فرمول نظری هم‌ارز به نام منطق ترکیبیاتی، توسط موسی شونفینکل و هاسکل کاری در دهه‌های ۱۹۲۰ و ۱۹۳۰ ساخته شد. چرچ بعدها یک سیستم ضعیف‌تر به نام حساب لاندا با نوع‌گذاری ساده را توسعه داد که حساب لاندا را با اختصاص یک نوع به همهٔ عبارت‌ها گسترش می‌داد. اولین زبان برنامه‌نویسی تابعی، LISP، در اواخر دههٔ ۱۹۵۰ برای کامپیوترهای علمی IBM سری 700/7000 توسط جان مک کارتی در انستیتوی فناوری ماساچوست (MIT) توسعه داده شد. توابع LISP با استفاده از نماد لاندای چرچ تعریف شده و به‌وصیلهٔ یک «برچسب» گسترش یافته‌اند تا امکان استفاده تعریف توابع بازگشتی میسر شود. لیسپ برای اولین بار بسیاری از ویژگیهای رویکردی برنامه‌نویسی تابعی را معرفی کرد، هرچند که در نسخه‌های اولیهٔ لیست زبان‌هایی با رویکرد چندگانه بودند و همزمان با تکامل رویکردهای جدید، از سبک‌های برنامه نویسی متعددی پشتیبانی می‌کردند. در حالی که لیسپ معمولی به منظور حفظ و به‌روزرسانی ویژگی‌های رویکردی گویش‌های قدیمی که جایگزین‌شان شد، طراحی شده است. مفاهیم تعدادی مفهوم و رویکرد ویژهٔ برنامه‌نویسی تابع‌گرا بوده و به طور کلی برای برنامه‌نویسی دستوری (از جمله برنامه‌نویسی شیءگرا) بیگانه هستند. | ## بخش 2: برنامه‌نویسی تابعی | با این حال، زبان‌های برنامه‌نویسی اغلب از چندین الگوی برنامه‌نویسی پشتیبانی می‌کنند. بنابراین برنامه‌نویسان با استفاده از زبان های «عمدتاً دستوری» می‌توانند از برخی از این مفاهیمِ ویژهٔ تابع‌گرایی استفاده بکنند. توابع مرتبه یک و مرتبهٔ بالاتر توابع مرتبه بالاتر توابعی هستند که می‌توانند توابع دیگری را به عنوان آرگومان به کار گرفته و یا آن‌ها را به عنوان نتیجه برگردانند. در حسابان، مثالی از یک تابع مرتبهٔ بالاتر عملگر دیفرانسیلی است که مشتق تابع را برمی‌گرداند. توابع مرتبهٔ بالاتر ارتباط نزدیکی با توابع مرتبهٔ اول دارند زیرا توابع مرتبه بالا و توابع مرتبه یک هر دو توابع را به عنوان آرگومان دریافت کرده و به عنوان نتیجه برمیگردانند. تمایز بین این دو ظریف است: «مرتبهٔ بالاتر» یک مفهوم ریاضی از توابعی که بر روی توابع دیگر کار می‌کنند توصیف می‌کند؛ در حالی که «مرتبهٔ اول» یک اصطلاح علوم کامپیوتر برای موجودیت‌هایی در زبان‌های برنامه‌نویسی است که هیچ محدودیتی در استفاده از آن‌ها وجود ندارد (بنابراین توابع مرتبهٔ اول می‌تواند در هر جایی از برنامه که سایر موجودیت‌های مرتبهٔ اول - مانند اعداد - مجاز هستند؛ استفاده شوند. توابع مرتبه بالا امکان استفاده از روش‌های برنامهٔ جزئی یا کارینگ را فراهم می‌کنند. در این تکنیک یک تابع بر روی آرگومان‌های خود یکی یکی اعمال شده و در هر مرحله تابع جدیدی برگردانده می‌شوند که روی آرگومان بعدی اعمال می‌شود. به‌عنوان مثال این روش به برنامه‌نویس اجازه می‌دهد به طور خلاصه تابع پسین را به شکل اپراتور جمع روی عدد طبیعی یک توصیف کند. توابع سره توابع سره (یا عبارت‌ها) هیچ‌گونه اثر جانبی (حافظه یا ورودی/خروجی) ندارند. این بدان معنی است که توابع سره دارای چندین خاصیت مفید هستند که بسیاری از آن‌ها می‌توانند برای بهینه‌سازی کد استفاده شوند: اگر نتیجهٔ یک عبارت سره استفاده نشود، می‌تواند بدون تأثیرگذاری بر عبارات دیگر حذف شود. اگر یک تابع سره با آرگومان‌هایی فراخوانی شود که اثر جانبی ایجاد نمی‌کنند، نتیجهٔ آن با توجه به لیست آرگومان‌ها ثابت است (گاهی به این ویژگی شفافیت ارجاع گفته می‌شود). یعنی فراخوانی دوبارهٔ تابع سره با همان آرگومان‌ها همیشه نتیجهٔ یکسان را برمی‌گرداند. (با استفاده از این ویژگی می‌توان بهینه‌سازی مموایز کردن را پیاده‌سازی کرد) اگر هیچ وابستگی بین داده‌های دو تابع سره وجود نداشته باشد، ترتیب آن‌ها اهمیت ندارد. می‌توان آن‌ها را به شکل موازی اجرا کرد و طبق تعریف نمی‌توانند با یکدیگر تداخل داشته باشند (به عبارتی دیگر، ارزیابی هرگونه تابع سره ایمن است). این به کامپایلر اجازه می‌دهد ترتیب ارزیابی را عوض کرده، و یا ارزیابی عبارات را در یک برنامه ترکیب کند (مثلاً با استفاده از جنگل‌زدایی). اکثر کامپایلرهای زبان‌های دستوری؛ توابع سره را تشخیص داده و بهینه‌سازی «حذف زیرعبارت مشترک» را روی آن‌ها انجام می‌دهند. با این وجود، همیشه نمی‌توانند این کار را برای کتابخانه‌های از پیش کامپایل شده انجام دهند. این کتابخانه‌ها عموماً این‌گونه اطلاعات را در معرض نمایش نمی‌گذارند، بنابراین بهینه‌سازی‌هایی که شامل اینگونه توابع است را غیرممکن می‌سازند. برخی از کامپایلرها، مانند جی‌سی‌سی، کلمات کلیدی دیگری را برای برنامه‌نویس فراهم کرده‌اند تا توابع خارجی را به صورت سره علامت‌گذاری کنند. توابع بازگشتی خود را فراخوانی کرده، یک عمل را آنقدر تکرار می‌کنند تا کنترل اجرا به شرط پایه برسد. به طور کلی، بازگشت نیازمند نگهداری یک پشته است، که در آن به نسبت خطی با عمق تکرار، حافظه مصرف می‌شود. | ## بخش 3: برنامه‌نویسی تابعی | به همین دلیل استفاده از توابع بازگشتی به جای حلقه در زبان‌های دستوری امری بسیار پرهزینه است به طوری که استفاده از تکرار معمولاً ناممکن است. با این حال، یک فرم خاص از بازگشت وجود دارد که به عنوان فراخوانی از انتها شناخته می‌شود. در این حالت خاص کامپایلر می‌تواند همان کدی را تولید کند که در صورت نوشتن حلقه تولید می‌شد. بهینه‌سازی بازگشتی می‌تواند به شکل تبدیل برنامه در حین کامپایل به CPS پیاده‌سازی شود. به این معنی که پیاده‌سازی‌ها باید تعداد نامحدودی از فراخوانی‌های فعال بازگشت از انتها را پشتیبانی کنند. بازگشت از انتها صرفاً به‌منظور بهینه‌سازی استفاده نمی‌شود: این ویژگی به کاربران اطمینان می‌دهد که می‌توانند برای توصیف یک حلقه از بازگشت استفاده کنند؛ با این تضمین که انجام این کار از نظر حافظه بهینه است. علاوه بر این، بر خلاف نام آن، تمام فراخوانی‌های انتها را شامل می‌شود (نه فقط بازگشت از انتها). اگرچه بازگشت از انتها معمولاً با تبدیل کد به حلقه‌های دستوری پیاده‌سازی می‌شود؛ پیاده‌سازی‌ها می‌توانند آن را به روش‌های دیگری نیز پیاده‌سازی کنند. با این حال، هنگامی که این اتفاق می‌افتد، زباله‌روب آن حافظه را برمی‌گرداند به این ترتیب تعداد نامحدودی از فراخوانی‌های فعال از نوع فراخوانی از انتها پشتیبانی می‌شوند. معروف‌ترین مثال‌های این روش کاتامورفیزم و آنامورفیزم (یا همان «تا کردن» و «باز کردن») هستند. این چنین طر‌ح‌های بازگشتی، نقشی مشابه ساختارهای کنترل داخلی مانند حلقه‌ها در زبان‌های دستوری دارند. اغلب زبان‌های برنامه‌نویسی تابعی، توابع بازگشتی را به‌صورت نامحدود پشتیبانی کرده و تورینگ-کامل هستند. به این ترتیب مسئلهٔ توقف در این زبان‌ها تصمیم‌ناپذیر بوده و می‌تواند باعث ناکامل بودن استدلال جبری شوند. بر همین اساس به طور کلی نیاز به وارد کردن ناسازگاری در منطق بیان شده توسط سیستم نوع زبان وجود دارد. بعضی از زبان‌های خاص‌منظوره مانند کو فقط بازگشت خوش‌تعریف را پشتیبانی کرده و قویاً نرمالیزه هستند. (به این معنی که محاسبات بی‌توقف را تنها می‌توان با استفاده از جریان بی‌نهایتی از مقادیر به نام codata بیان کرد). در نتیجه این زبان‌ها تورینگ-کامل نیستند و تعریف ردهٔ خاصی از توابع در آن‌ها ناممکن است، با این وجود با استفاده از این زبان‌ها می‌توان ضمن جلوگیری از مشکلات ایجاد شده توسط بازگشت نامحدود؛ ردهٔ گسترده‌ای از محاسبات کاربردی را توصیف کرد. برنامه‌نویسی کاربردی که محدود به توابع بازگشتی خوش‌تعریف بوده و چند محدودیت دیگر نیز بر آن اِعمال شده باشد، برنامه‌نویسی کاملاً تابعی نامیده می‌شود. ارزیابی دقیق در مقابل ارزیابی نادقیق زبان‌های تابعی را می‌توان براساس نحوهٔ ارزیابی آرگومان‌های توابع، به دو دستهٔ دقیق (مشتاق) یا نادقیق (تنبل) دسته‌بندی کرد. تحت ارزیابی تنبل، تابع طول مقدار 4 را برمی‌گرداند؛ زیرا تلاش نمی‌کند تمام جملات تشکیل دهندهٔ لیست را ارزیابی کند. به طور خلاصه، ارزیابی دقیق همیشه به طور کامل آرگومان‌های تابع را قبل از فراخوانی ارزیابی می‌کند. | ## جمع‌بندی | ارزیابی تنبل آرگومان‌های تابع را ارزیابی نمی‌کند، مگر اینکه مقادیر آن‌ها برای فراخوانی تابع ضروری باشد.