برنامه‌نویسی تابعی
در علوم کامپیوتر، برنامه‌نویسی تابعی یک رویکرد برنامه‌نویسی است که در آن برنامه‌ها توسط محاسبه و ترکیب توابع ساخته می‌شوند. برنامه‌نویسی تابعی یک رویکرد برنامه‌نویسی اعلانی است که در آن تعریف توابع درخت‌هایی از عبارت‌ها هستند که هر کدام از این عبارات به جای یک توالی از عبارات دستوری که وضعیت برنامه را تغییر می‌دهند؛ صرفاً یک مقدار برمی‌گردانند.
در برنامه‌نویسی تابعی، توابع به عنوان شهروندان درجه یک تلقی می‌شوند، این بدان معنی است که توابع را می‌توان به نام‌ها (از جمله شناسه‌های محلی) مقید کرده، به عنوان آرگومان ارسال کرده و یا از توابع دیگر بازگرداند. دقیقاً مانند هر نوع داده دیگر. این ویژگی این امکان را فراهم می‌کند که برنامه‌ها به شکل اعلانی و ترکیب‌پذیر نوشته شوند، به‌طوری که که توابع کوچک به صورت پودمانی با هم ترکیب می‌شوند.
برنامه‌نویسی تابعی گاهی به عنوان مترادفی برای برنامه‌نویسی تابعی محض در نظر گرفته می‌شود. این نوع برنامه‌نویسی زیرمجموعه‌ای از برنامه‌نویسی تابعی است که در آن تمام توابع به عنوان توابع ریاضی و قطعی یا تابع سره تلقی می‌شوند. هنگامی که یک تابع سره با مجموعهٔ آرگومان‌های ثابت فراخونی می‌شود، همیشه همان نتیجه را برمی‌گرداند و نمی تواند تحت تأثیر هیچ‌گونه حالت قابل تغییر یا اثر جانبی دیگری باشد. این برخلاف توابع غیرسره است که معمولاً در برنامه‌نویسی دستوری استفاده می‌شود و می‌تواند اثرات جانبی داشته باشد (مانند تغییر وضعیت برنامه یا گرفتن ورودی از یک کاربر). طرفداران برنامه‌نویسی تابعی محض ادعا می‌کنند که با محدود کردن اثر جانبی، برنامه‌ها اشکالات کمتری داشته؛ همچنین اشکال‌زدایی و تست نرم‌افزار آسان‌تر می‌شود. از سوی دیگر استفاده از این رویکرد برای دستیابی به درستی‌یابی صوری نرم‌افزار مناسب‌تر است.
منشأ برنامه‌نویسی تابعی ریشه در تحقیقات دانشگاهی دارد و از حساب لاندا تکامل پیدا کرده است. حساب لاندا یک سیستم صوری محاسبات است که صرفاً مبتنی بر توابع می‌باشد. برنامه‌نویسی تابعی به شکل تاریخی کمتر از برنامه‌نویسی دستوری محبوب بوده است. با این حال بسیاری از زبان‌های تابع‌گرا امروزه در صنعت و آموزش دیده می‌شوند. از جمله لیسپ معمولی، اسکیم، کلوژر ، زبان برنامه‌نویسی ولفرام، راکت ، ارلنگ، اوکمل، هسکل، و F#. برنامه‌نویسی تابع‌گرا همچنین برای برخی از زبان‌های خاص‌منظوره موفق نقش کلیدی ایفا می‌کند. مانند R در آمار، J ، K و Q در آنالیز مالی، و XQuery / XSLT برای XML. زبان‌های اعلانی خاص‌منظوره مانند SQL و Lex / Yacc از برخی عناصر برنامه‌نویسی تابع‌گرا استفاده می‌کنند. مانند ممنوع کردن مقادیر قابل تغییر. همچنین بسیاری از زبان‌های برنامه‌نویسی، برنامه‌‌نویسی به سبک تابع‌گرا را پشتیبانی کرده و یا ویژگی‌های تابع‌گرایی پیاده‌سازی کرده‌اند. مانند C++11 ، کاتلین، پرل، پی‌اچ‌پی، پایتون، و اسکالا.
جبر لاندا که در دههٔ ۱۹۳۰ توسط آلونزو چرچ ابداع شد، یک سیستم صوری محاسباتی است که براساس کاربرد توابع ساخته شده است. در سال ۱۹۳۷ تورینگ ثابت کرد که حساب لاندا و ماشین تورینگ مدل‌های محاسباتی هم‌ارز هستند. او نشان داد که حساب لاندا تورینگ-کامل است. حساب لاندا اساس همهٔ زبان‌های برنامه‌نویسی تابعی را تشکیل می‌دهد. همچنین یک فرمول نظری هم‌ارز به نام منطق ترکیبیاتی، توسط موسی شونفینکل و هاسکل کاری در دهه‌های ۱۹۲۰ و ۱۹۳۰ ساخته شد.
چرچ بعدها یک سیستم ضعیف‌تر به نام حساب لاندا با نوع‌گذاری ساده را توسعه داد که حساب لاندا را با اختصاص یک نوع به همهٔ عبارت‌ها گسترش می‌داد. این پایه و اساس برنامه‌نویسی عملکردی با سیستم نوع ایستا را تشکیل می‌دهد.
اولین زبان برنامه‌نویسی تابعی، LISP، در اواخر دههٔ ۱۹۵۰ برای کامپیوترهای علمی IBM سری 700/7000 توسط جان مک کارتی در انستیتوی فناوری ماساچوست (MIT) توسعه داده شد. توابع LISP با استفاده از نماد لاندای چرچ تعریف شده و به‌وصیلهٔ یک «برچسب» گسترش یافته‌اند تا امکان استفاده تعریف توابع بازگشتی میسر شود. لیسپ برای اولین بار بسیاری از ویژگیهای رویکردی برنامه‌نویسی تابعی را معرفی کرد، هرچند که در نسخه‌های اولیهٔ لیست زبان‌هایی با رویکرد چندگانه بودند و همزمان با تکامل رویکردهای جدید، از سبک‌های برنامه نویسی متعددی پشتیبانی می‌کردند. گویش‌های بعدی این زبان، مانند Scheme و Clojure، و شاخه‌هایی مانند Dylan و جولیا، به دنبال ساده‌سازی و منطقی‌سازی Lisp پیرامون یک هستهٔ کاملاً تابعی بودند. در حالی که لیسپ معمولی به منظور حفظ و به‌روزرسانی ویژگی‌های رویکردی گویش‌های قدیمی که جایگزین‌شان شد، طراحی شده است.
تعدادی مفهوم و رویکرد ویژهٔ برنامه‌نویسی تابع‌گرا بوده و به طور کلی برای برنامه‌نویسی دستوری (از جمله برنامه‌نویسی شیءگرا) بیگانه هستند. با این حال، زبان‌های برنامه‌نویسی اغلب از چندین الگوی برنامه‌نویسی پشتیبانی می‌کنند. بنابراین برنامه‌نویسان با استفاده از زبان های «عمدتاً دستوری» می‌توانند از برخی از این مفاهیمِ ویژهٔ تابع‌گرایی استفاده بکنند.
توابع مرتبه بالاتر توابعی هستند که می‌توانند توابع دیگری را به عنوان آرگومان به کار گرفته و یا آن‌ها را به عنوان نتیجه برگردانند. در حسابان، مثالی از یک تابع مرتبهٔ بالاتر عملگر دیفرانسیلی formula_1 است که مشتق تابع formula_2 را برمی‌گرداند.
توابع مرتبهٔ بالاتر ارتباط نزدیکی با توابع مرتبهٔ اول دارند زیرا توابع مرتبه بالا و توابع مرتبه یک هر دو توابع را به عنوان آرگومان دریافت کرده و به عنوان نتیجه برمیگردانند. تمایز بین این دو ظریف است: «مرتبهٔ بالاتر» یک مفهوم ریاضی از توابعی که بر روی توابع دیگر کار می‌کنند توصیف می‌کند؛ در حالی که «مرتبهٔ اول» یک اصطلاح علوم کامپیوتر برای موجودیت‌هایی در زبان‌های برنامه‌نویسی است که هیچ محدودیتی در استفاده از آن‌ها وجود ندارد (بنابراین توابع مرتبهٔ اول می‌تواند در هر جایی از برنامه که سایر موجودیت‌های مرتبهٔ اول - مانند اعداد - مجاز هستند؛ استفاده شوند. این شامل آرگومان‌های ورودی و مقادیر بازگشتی از توابع نیز هست).
توابع مرتبه بالا امکان استفاده از روش‌های برنامهٔ جزئی یا کارینگ را فراهم می‌کنند. در این تکنیک یک تابع بر روی آرگومان‌های خود یکی یکی اعمال شده و در هر مرحله تابع جدیدی برگردانده می‌شوند که روی آرگومان بعدی اعمال می‌شود. به‌عنوان مثال این روش به برنامه‌نویس اجازه می‌دهد به طور خلاصه تابع پسین را به شکل اپراتور جمع روی عدد طبیعی یک توصیف کند.
توابع سره (یا عبارت‌ها) هیچ‌گونه اثر جانبی (حافظه یا ورودی/خروجی) ندارند. این بدان معنی است که توابع سره دارای چندین خاصیت مفید هستند که بسیاری از آن‌ها می‌توانند برای بهینه‌سازی کد استفاده شوند: اکثر کامپایلرهای زبان‌های دستوری؛ توابع سره را تشخیص داده و بهینه‌سازی «حذف زیرعبارت مشترک» را روی آن‌ها انجام می‌دهند. با این وجود، همیشه نمی‌توانند این کار را برای کتابخانه‌های از پیش کامپایل شده انجام دهند. این کتابخانه‌ها عموماً این‌گونه اطلاعات را در معرض نمایش نمی‌گذارند، بنابراین بهینه‌سازی‌هایی که شامل اینگونه توابع است را غیرممکن می‌سازند. برخی از کامپایلرها، مانند جی‌سی‌سی، کلمات کلیدی دیگری را برای برنامه‌نویس فراهم کرده‌اند تا توابع خارجی را به صورت سره علامت‌گذاری کنند. بدین ترتیب این دست بهینه‌سازی‌ها فعال می‌شود. فورترن ۹۵ همچنین اجازه می‌دهد توابع به‌صورت "سره" تعریف شوند. در C++11 کلمهٔ کلیدی codice_1 با معانی مشابه اضافه شده است.
تکرار (حلقه) در زبان‌های تابعی معمولاً از طریق بازگشت انجام می‌شود. توابع بازگشتی خود را فراخوانی کرده، یک عمل را آنقدر تکرار می‌کنند تا کنترل اجرا به شرط پایه برسد. به طور کلی، بازگشت نیازمند نگهداری یک پشته است، که در آن به نسبت خطی با عمق تکرار، حافظه مصرف می‌شود. به همین دلیل استفاده از توابع بازگشتی به جای حلقه در زبان‌های دستوری امری بسیار پرهزینه است به طوری که استفاده از تکرار معمولاً ناممکن است. با این حال، یک فرم خاص از بازگشت وجود دارد که به عنوان فراخوانی از انتها شناخته می‌شود. در این حالت خاص کامپایلر می‌تواند همان کدی را تولید کند که در صورت نوشتن حلقه تولید می‌شد. بهینه‌سازی بازگشتی می‌تواند به شکل تبدیل برنامه در حین کامپایل به CPS پیاده‌سازی شود. همچنین روش‌های دیگری برای پیاده‌سازی این بهینه‌سازی وجود دارد.
استاندارد زبان اسکیم پیاده‌سازی بازگشت از انتها را الزام می‌کند. به این معنی که پیاده‌سازی‌ها باید تعداد نامحدودی از فراخوانی‌های فعال بازگشت از انتها را پشتیبانی کنند. بازگشت از انتها صرفاً به‌منظور بهینه‌سازی استفاده نمی‌شود: این ویژگی به کاربران اطمینان می‌دهد که می‌توانند برای توصیف یک حلقه از بازگشت استفاده کنند؛ با این تضمین که انجام این کار از نظر حافظه بهینه است. علاوه بر این، بر خلاف نام آن، تمام فراخوانی‌های انتها را شامل می‌شود (نه فقط بازگشت از انتها). اگرچه بازگشت از انتها معمولاً با تبدیل کد به حلقه‌های دستوری پیاده‌سازی می‌شود؛ پیاده‌سازی‌ها می‌توانند آن را به روش‌های دیگری نیز پیاده‌سازی کنند. به‌عنوان مثال، CHICKEN عمداً یک پشته نگهداری کرده و اجازه می‌دهد سرریز کند. با این حال، هنگامی که این اتفاق می‌افتد، زباله‌روب آن حافظه را برمی‌گرداند به این ترتیب تعداد نامحدودی از فراخوانی‌های فعال از نوع فراخوانی از انتها پشتیبانی می‌شوند. (علی‌رغم این که حلقه‌ای تولید نشده است).
الگوهای بازگشتی متداول را می‌توان به وسیلهٔ انتزاع توابع مرتبهٔ بالاتر کنار زد. معروف‌ترین مثال‌های این روش کاتامورفیزم و آنامورفیزم (یا همان «تا کردن» و «باز کردن») هستند. این چنین طر‌ح‌های بازگشتی، نقشی مشابه ساختارهای کنترل داخلی مانند حلقه‌ها در زبان‌های دستوری دارند.
اغلب زبان‌های برنامه‌نویسی تابعی، توابع بازگشتی را به‌صورت نامحدود پشتیبانی کرده و تورینگ-کامل هستند. به این ترتیب مسئلهٔ توقف در این زبان‌ها تصمیم‌ناپذیر بوده و می‌تواند باعث ناکامل بودن استدلال جبری شوند. بر همین اساس به طور کلی نیاز به وارد کردن ناسازگاری در منطق بیان شده توسط سیستم نوع زبان وجود دارد. بعضی از زبان‌های خاص‌منظوره مانند کو فقط بازگشت خوش‌تعریف را پشتیبانی کرده و قویاً نرمالیزه هستند. (به این معنی که محاسبات بی‌توقف را تنها می‌توان با استفاده از جریان بی‌نهایتی از مقادیر به نام codata بیان کرد). در نتیجه این زبان‌ها تورینگ-کامل نیستند و تعریف ردهٔ خاصی از توابع در آن‌ها ناممکن است، با این وجود با استفاده از این زبان‌ها می‌توان ضمن جلوگیری از مشکلات ایجاد شده توسط بازگشت نامحدود؛ ردهٔ گسترده‌ای از محاسبات کاربردی را توصیف کرد. برنامه‌نویسی کاربردی که محدود به توابع بازگشتی خوش‌تعریف بوده و چند محدودیت دیگر نیز بر آن اِعمال شده باشد، برنامه‌نویسی کاملاً تابعی نامیده می‌شود.
زبان‌های تابعی را می‌توان براساس نحوهٔ ارزیابی آرگومان‌های توابع، به دو دستهٔ "دقیق (مشتاق)" یا "نادقیق (تنبل)" دسته‌بندی کرد. تفاوت فنی در معناشناسی عبارات حاوی محاسبات خطادار یا واگرا است. در ارزیابی دقیق، ارزیابی هر جمله حاوی زیرمجموعه‌ای خطادار، با خطا مواجه می‌شود. به عنوان مثال، عبارت:  print length([2+1, 3*2, 1/0, 5-4])  تحت ارزیابی دقیق، به دلیل تقسیم صفر در عنصر سوم لیست خطا ارزیابی می‌شود. تحت ارزیابی تنبل، تابع طول مقدار 4 را برمی‌گرداند؛ زیرا تلاش نمی‌کند تمام جملات تشکیل دهندهٔ لیست را ارزیابی کند. به طور خلاصه، ارزیابی دقیق همیشه به طور کامل آرگومان‌های تابع را قبل از فراخوانی ارزیابی می‌کند. ارزیابی تنبل آرگومان‌های تابع را ارزیابی نمی‌کند، مگر اینکه مقادیر آن‌ها برای فراخوانی تابع ضروری باشد.