حساب کاربری
​
تغیر مسیر یافته از - برنامه نویسی تابعی
زمان تقریبی مطالعه: 12 دقیقه
لینک کوتاه

برنامه‌نویسی تابعی

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

جان مک کارتی دانشمند کامپیوتر آمریکایی در اواخر دهه ١٩۵٠ اولین زبان برنامه نویسی تابعی را در انستیتوی فناوری ماساچوست برای کامپیوتر های علمی توسعه داد.

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

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

منشأ برنامه‌نویسی تابعی ریشه در تحقیقات دانشگاهی دارد و از حساب لامبدا تکامل پیدا کرده است. حساب لاندا یک سیستم صوری محاسبات است که صرفاً مبتنی بر توابع می‌باشد. برنامه‌نویسی تابعی به شکل تاریخی کمتر از برنامه‌نویسی دستوری محبوب بوده است. با این حال بسیاری از زبان‌های تابع‌گرا امروزه در صنعت و آموزش دیده می‌شوند. از جمله لیسپ معمولی، اسکیم، کلوژر ، زبان برنامه‌نویسی ولفرام، راکت ، ارلنگ، اوکمل، هسکل، و F#. برنامه‌نویسی تابع‌گرا همچنین برای برخی از زبان‌های خاص‌منظوره موفق نقش کلیدی ایفا می‌کند. مانند R در آمار، J ، K و Q در آنالیز مالی، و XQuery / XSLT برای XML. زبان‌های اعلانی خاص‌منظوره مانند SQL و Lex / Yacc از برخی عناصر برنامه‌نویسی تابع‌گرا استفاده می‌کنند. مانند ممنوع کردن مقادیر قابل تغییر. همچنین بسیاری از زبان‌های برنامه‌نویسی، برنامه‌‌نویسی به سبک تابع‌گرا را پشتیبانی کرده و یا ویژگی‌های تابع‌گرایی پیاده‌سازی کرده‌اند. مانند C++11 ، کاتلین، پرل، پی‌اچ‌پی، پایتون، و اسکالا.

فهرست

  • ۱ تاریخچه
  • ۲ مفاهیم
    • ۲.۱ توابع مرتبه یک و مرتبهٔ بالاتر
    • ۲.۲ توابع سره
    • ۲.۳ بازگشت
    • ۲.۴ ارزیابی دقیق در مقابل ارزیابی نادقیق
  • ۳ همچنین ببینید
  • ۴ منابع
  • ۵ مطالعهٔ بیشتر
  • ۶ پیوند به بیرون

تاریخچه

جبر لاندا که در دههٔ ۱۹۳۰ توسط آلونزو چرچ ابداع شد، یک سیستم صوری محاسباتی است که براساس کاربرد توابع ساخته شده است. در سال ۱۹۳۷ تورینگ ثابت کرد که حساب لاندا و ماشین تورینگ مدل‌های محاسباتی هم‌ارز هستند. او نشان داد که حساب لاندا تورینگ-کامل است. حساب لاندا اساس همهٔ زبان‌های برنامه‌نویسی تابعی را تشکیل می‌دهد. همچنین یک فرمول نظری هم‌ارز به نام منطق ترکیبیاتی، توسط موسی شونفینکل و هاسکل کاری در دهه‌های ۱۹۲۰ و ۱۹۳۰ ساخته شد.

چرچ بعدها یک سیستم ضعیف‌تر به نام حساب لاندا با نوع‌گذاری ساده را توسعه داد که حساب لاندا را با اختصاص یک نوع به همهٔ عبارت‌ها گسترش می‌داد. این پایه و اساس برنامه‌نویسی عملکردی با سیستم نوع ایستا را تشکیل می‌دهد.

اولین زبان برنامه‌نویسی تابعی، LISP، در اواخر دههٔ ۱۹۵۰ برای کامپیوترهای علمی IBM سری 700/7000 توسط جان مک کارتی در انستیتوی فناوری ماساچوست (MIT) توسعه داده شد. توابع LISP با استفاده از نماد لاندای چرچ تعریف شده و به‌وصیلهٔ یک «برچسب» گسترش یافته‌اند تا امکان استفاده تعریف توابع بازگشتی میسر شود. لیسپ برای اولین بار بسیاری از ویژگیهای رویکردی برنامه‌نویسی تابعی را معرفی کرد، هرچند که در نسخه‌های اولیهٔ لیست زبان‌هایی با رویکرد چندگانه بودند و همزمان با تکامل رویکردهای جدید، از سبک‌های برنامه نویسی متعددی پشتیبانی می‌کردند. گویش‌های بعدی این زبان، مانند Scheme و Clojure، و شاخه‌هایی مانند Dylan و جولیا، به دنبال ساده‌سازی و منطقی‌سازی Lisp پیرامون یک هستهٔ کاملاً تابعی بودند. در حالی که لیسپ معمولی به منظور حفظ و به‌روزرسانی ویژگی‌های رویکردی گویش‌های قدیمی که جایگزین‌شان شد، طراحی شده است.

مفاهیم

تعدادی مفهوم و رویکرد ویژهٔ برنامه‌نویسی تابع‌گرا بوده و به طور کلی برای برنامه‌نویسی دستوری (از جمله برنامه‌نویسی شیءگرا) بیگانه هستند. با این حال، زبان‌های برنامه‌نویسی اغلب از چندین الگوی برنامه‌نویسی پشتیبانی می‌کنند. بنابراین برنامه‌نویسان با استفاده از زبان های «عمدتاً دستوری» می‌توانند از برخی از این مفاهیمِ ویژهٔ تابع‌گرایی استفاده بکنند.

توابع مرتبه یک و مرتبهٔ بالاتر

توابع مرتبه بالاتر توابعی هستند که می‌توانند توابع دیگری را به عنوان آرگومان به کار گرفته و یا آن‌ها را به عنوان نتیجه برگردانند. در حسابان، مثالی از یک تابع مرتبهٔ بالاتر عملگر دیفرانسیلی d / d x

است که مشتق تابع f
را برمی‌گرداند.

توابع مرتبهٔ بالاتر ارتباط نزدیکی با توابع مرتبهٔ اول دارند زیرا توابع مرتبه بالا و توابع مرتبه یک هر دو توابع را به عنوان آرگومان دریافت کرده و به عنوان نتیجه برمیگردانند. تمایز بین این دو ظریف است: «مرتبهٔ بالاتر» یک مفهوم ریاضی از توابعی که بر روی توابع دیگر کار می‌کنند توصیف می‌کند؛ در حالی که «مرتبهٔ اول» یک اصطلاح علوم کامپیوتر برای موجودیت‌هایی در زبان‌های برنامه‌نویسی است که هیچ محدودیتی در استفاده از آن‌ها وجود ندارد (بنابراین توابع مرتبهٔ اول می‌تواند در هر جایی از برنامه که سایر موجودیت‌های مرتبهٔ اول - مانند اعداد - مجاز هستند؛ استفاده شوند. این شامل آرگومان‌های ورودی و مقادیر بازگشتی از توابع نیز هست).

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

توابع سره

توابع سره (یا عبارت‌ها) هیچ‌گونه اثر جانبی (حافظه یا ورودی/خروجی) ندارند. این بدان معنی است که توابع سره دارای چندین خاصیت مفید هستند که بسیاری از آن‌ها می‌توانند برای بهینه‌سازی کد استفاده شوند:

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

اکثر کامپایلرهای زبان‌های دستوری؛ توابع سره را تشخیص داده و بهینه‌سازی «حذف زیرعبارت مشترک» را روی آن‌ها انجام می‌دهند. با این وجود، همیشه نمی‌توانند این کار را برای کتابخانه‌های از پیش کامپایل شده انجام دهند. این کتابخانه‌ها عموماً این‌گونه اطلاعات را در معرض نمایش نمی‌گذارند، بنابراین بهینه‌سازی‌هایی که شامل اینگونه توابع است را غیرممکن می‌سازند. برخی از کامپایلرها، مانند جی‌سی‌سی، کلمات کلیدی دیگری را برای برنامه‌نویس فراهم کرده‌اند تا توابع خارجی را به صورت سره علامت‌گذاری کنند. بدین ترتیب این دست بهینه‌سازی‌ها فعال می‌شود. فورترن ۹۵ همچنین اجازه می‌دهد توابع به‌صورت سره تعریف شوند. در C++11 کلمهٔ کلیدی constexpr با معانی مشابه اضافه شده است.

بازگشت

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

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

الگوهای بازگشتی متداول را می‌توان به وسیلهٔ انتزاع توابع مرتبهٔ بالاتر کنار زد. معروف‌ترین مثال‌های این روش کاتامورفیزم و آنامورفیزم (یا همان «تا کردن» و «باز کردن») هستند. این چنین طر‌ح‌های بازگشتی، نقشی مشابه ساختارهای کنترل داخلی مانند حلقه‌ها در زبان‌های دستوری دارند.

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

ارزیابی دقیق در مقابل ارزیابی نادقیق

زبان‌های تابعی را می‌توان براساس نحوهٔ ارزیابی آرگومان‌های توابع، به دو دستهٔ دقیق (مشتاق) یا نادقیق (تنبل) دسته‌بندی کرد. تفاوت فنی در معناشناسی عبارات حاوی محاسبات خطادار یا واگرا است. در ارزیابی دقیق، ارزیابی هر جمله حاوی زیرمجموعه‌ای خطادار، با خطا مواجه می‌شود. به عنوان مثال، عبارت: 

print length([2+1, 3*2, 1/0, 5-4])

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

همچنین ببینید

  • برنامه‌نویسی تابعی محض
  • مقایسه رویکردهای برنامه‌نویسی
  • ارزیابی مشتاق
  • لیست مباحث برنامه‌نویسی تابعی
  • تابع تودرتو
  • برنامه‌نویسی تابعی استقرایی
  • برنامه ریزی تابعی واکنشی

منابع

  1. ↑ Hudak, Paul (September 1989). "Conception, evolution, and application of functional programming languages" (PDF). ACM Computing Surveys. 21 (3): 359–411. doi:10.1145/72551.72554.
  2. ↑ Hughes, John (1984). "Why Functional Programming Matters".
  3. ↑ "Wolfram Language Guide: Functional Programming". 2015. Retrieved 2015-08-24.
  4. ↑ "Functional programming - Kotlin Programming Language". Kotlin. Retrieved 2019-05-01.
  5. ↑ Dominus, Mark J. (2005). Higher-Order Perl. Morgan Kaufmann. ISBN 978-1-55860-701-9.
  6. ↑ Holywell, Simon (2014). Functional Programming in PHP. php[architect]. ISBN 9781940111056.
  7. ↑ The Cain Gang Ltd. "Python Metaclasses: Who? Why? When?" (PDF). Archived from the original (PDF) on 30 May 2009. Retrieved 27 June 2009.
  8. ↑ Turing, A. M. (1937). "Computability and λ-definability". The Journal of Symbolic Logic. Cambridge University Press. 2 (4): 153–163. doi:10.2307/2268280.
  9. ↑ Haskell Brooks Curry; Robert Feys (1958). Combinatory Logic. North-Holland Publishing Company. Retrieved 10 February 2013.
  10. ↑ Church, A. (1940). "A Formulation of the Simple Theory of Types". Journal of Symbolic Logic. 5 (2): 56–68. doi:10.2307/2266170. JSTOR 2266170.
  11. ↑ John McCarthy (1960). "Recursive functions of symbolic expressions and their computation by machine, Part I." (PDF). Communications of the ACM. ACM New York, NY, USA. 3 (4): 184–195.
  12. ↑ Guy L. Steele; Richard P. Gabriel (February 1996). The Evolution of Lisp (PDF). In ACM/SIGPLAN Second History of Programming Languages. pp. 233–330. doi:10.1145/234286.1057818. ISBN 978-0-201-89502-5.
  13. ↑ Dick Pountain. "Functional Programming Comes of Age". BYTE.com (August 1994). Archived from the original on 2006-08-27. Retrieved August 31, 2006.
  14. ↑ "ISO/IEC JTC 1/SC 22/WG5/N2137". International Organization for Standardization. July 6, 2017.
  15. ↑ "Revised^6 Report on the Algorithmic Language Scheme". R6rs.org. Retrieved 2013-03-21.
  16. ↑ "Revised^6 Report on the Algorithmic Language Scheme - Rationale". R6rs.org. Retrieved 2013-03-21.
  17. ↑ Clinger, William (1998). "Proper tail recursion and space efficiency". Retrieved 2020-04-29.
  18. ↑ Baker, Henry (1994). "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A." Archived from the original on 3 March 2006.
  19. ↑ Turner, D.A. (2004-07-28). "Total Functional Programming". Journal of Universal Computer Science. 10 (7): 751–768. doi:10.3217/jucs-010-07-0751.

مطالعهٔ بیشتر

  • Abelson, Hal; Sussman, Gerald Jay (1985). Structure and Interpretation of Computer Programs. MIT Press. Archived from the original on 26 December 2017. Retrieved 21 August 2020.
  • کسینو ، گای و میشل مونی. رویکرد کاربردی به برنامه نویسی . کمبریج ، انگلیس: انتشارات دانشگاه کمبریج ، 1998.
  • کوری ، هاسکل بروکس و فیز ، رابرت و کریگ ، ویلیام. منطق ترکیبیاتی . جلد I. شرکت انتشارات هلند شمالی ، آمستردام ، 1958.
  • Curry, Haskell B.; Hindley, J. Roger; Seldin, Jonathan P. (1972). Combinatory Logic. Vol. Vol. II. Amsterdam: North Holland. ISBN 978-0-7204-2208-5. Curry, Haskell B.; Hindley, J. Roger; Seldin, Jonathan P. (1972). Combinatory Logic. Vol. Vol. II. Amsterdam: North Holland. ISBN 978-0-7204-2208-5. Curry, Haskell B.; Hindley, J. Roger; Seldin, Jonathan P. (1972). Combinatory Logic. Vol. Vol. II. Amsterdam: North Holland. ISBN 978-0-7204-2208-5.
  • دومینیوس ، مارک جیسون. پرل سفارش بالاتر مورگان کافمن 2005
  • Felleisen, Matthias; Findler, Robert; Flatt, Matthew; Krishnamurthi, Shriram (2001). How to Design Programs. MIT Press.
  • گراهام ، پل ANIS LISP مشترک . Englewood Cliffs، New Jersey: Prentice Hall ، 1996.
  • MacLennan ، Bruce J. برنامه نویسی کاربردی: تمرین و نظریه . آدیسون وسلی ، 1990.
  • O'Sullivan, Brian; Stewart, Don; Goerzen, John (2008). Real World Haskell. O'Reilly.
  • پرات ، ترنس ، دبلیو و ماروین V. زلکوویتز. زبان‌های برنامه‌نویسی: طراحی و اجرا . چاپ 3 Englewood Cliffs، New Jersey: Prentice Hall ، 1996.
  • Salus، Peter H. زبانهای برنامه نویسی کاربردی و منطقی . جلد 4 کتابچه راهنمای زبان‌های برنامه‌نویسی. ایندیاناپولیس ، ایندیانا: انتشارات فنی مک میلان ، 1998.
  • تامپسون ، سایمون. هاسکل: مهارت برنامه نویسی کاربردی . هارلو ، انگلیس: آدیسون وسلی لانگمن محدود ، 1996.

پیوند به بیرون

  • Ford, Neal (2012-01-29). "Functional thinking: Why functional programming is on the rise". Retrieved 2013-02-24.
  • Akhmechet, Slava (2006-06-19). "defmacro – Functional Programming For The Rest of Us". Retrieved 2013-02-24. یک مقدمه
  • برنامه‌نویسی تابعی در پایتون (توسط دیوید مرتز): قسمت 1 ، قسمت 2 ، قسمت 3
آخرین نظرات
  • توابع
  • توابع
کلیه حقوق این تارنما متعلق به فرا دانشنامه ویکی بین است.