توابع کلاس اول
به یک زبان برنامهنویسی در علوم کامپیوتر، دارای تابع کلاس اول گفته میشود اگر آن زبان با توابع خود به صورت شهروند درجهی اول رفتار کند. این موضوع به این معنی است که زبان مورد نظر از چنین کارهایی پشتیبانی کند:
- فرستادن تابع به عنوان آرگومان تابعی دیگر
- برگرداندن تابع به صورت مقدار نهایی یک تابع دیگر
- اختصاص دادن مقدار یک تابع به یک متغیر
- ذخیره کردن تابع در داده ساختارهای مختلف
برخی از نظریهداران حوزهی زبانهای برنامهنویسی برای توابع کلاس اول، علاوه بر موارد بالا، پشتیبانی از توابع ناشناس (anonymous functions) را نیز الزامی میدانند. در زبانهایی که توابع کلاس اول دارند، نام تابع هیچ معنای خاص یا ویژهای ندارد و همانند متغیرهای معمولی رفتار میشود با این تفاوت که نوع آن متغیر، از نوع تابع است. اصطلاح توابع کلاس اول برای اولین بار توسط شخص کریستوفر استراچی به کار برده شده است. او برای اولین بار در مورد رفتار زبانهای برنامهنویسی با توابع به صورت شهروند درجهی اول در اواسط دههی ۱۹۶۰ میلادی در مقالهای به نام مفاهیم بنیادی در زبانهای برنامهنویسی (Fundamental Concepts in Programming Languages) نوشته بود.
توابع کلاس اول برای برنامهنویسی تابعی الزامی هستند. در برنامهنویسی تابعی استفاده از تابع مرتبهی بالا متداول است و توابع کلاس اول در این بخش لازم هستند. یک مثال ساده از چنین تابع مرتبهی بالا، تابع filter است که به عنوان آرگومان و ورودی خود یک تابع و یک لیست میگیرد و در نهایت یک لیست جدید برمیگرداند که تابع مورد نظر بر روی هر یک از اعضای لیست اعمال شده است و لیست جدید فیلتر شده است. برای اینکه یک زبان برنامهنویسی بتوان از تابعی چون فیلتر پشتیبانی کند، آن زبان حتماً باید بتواند یک تابع را به عنوان آرگومان تابعی دیگر بپذیرد.
مفاهیم
در این بخش نحوهی پیادهسازی یا شبیهسازی اصطلاحات مختلف برنامهنویسی در زبانهای دارای تابع کلاس اول (هسکل و پایتون) و زبانهای فاقد آن (سی)، بررسی میشود.
توابع مرتبهی بالا
توابع مرتبهی بالا، توابعی هستند که حداقل یک تابع در آرگومانهای ورودی یا خروجی آن وجود داشته باشد. بقیهی توابع، توابع مرتبهی اول هستند.
در زبانهایی که دارای توابع کلاس اول هستند، توابع میتوانند مانند متغیرهای معمولی، به عنوان ورودی به توابع دیگر داده شوند. بنابراین برای پیادهسازی توابع مرتبهی بالا، بهتر است که زبان مورد نظر از توابع کلاس اول پشتیبانی کند. این توابع به دو صورت میتوانند از توابع کلاس اول استفاده کنند: زمانی که آرگومانهای ورودی تابع، تابع باشند و زمانی که خروجی تابع، یک تابع باشد.
در زبان پایتون داریم:
def addition(n):
return n + n
numbers = (1, 2, 3, 4)
result = map(addition, numbers)
در زبان هسکل داریم:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
زبانهایی که از توابع کلاس اول پشتیبانی نمیکنند، معمولاً با استفاده از قابلیبتهایی همچون اشارهگر به تابع یا نمایندهها، توابع مرتبهی بالا را پیادهسازی میکنند. مثلاً در زبان سی داریم:
void map(int (*f)(int), int x[], size_t n) {
for (int i = 0; i <n; i++)
x[i] = f(x[i]);
}
توابع کاری (Curry)
توابع کاری، توابعی هستند که چندین آرگومان را به صورت یکی پس از دیگری، به عنوان ورودی میگیرند: در ابتدا یک آرگومان یا پارامتر را میگیرد و سپس تابعی برمیگرداند که آرگومان بعدی را میگیرد و به همین ترتیب ادامه میدهد تا تمامی پارامترها به تابع داده شوند. در این مرحله، تابع محاسبه میشود و مقدار نهایی برگردانده میشود.
نام این توابع از اسم منطقدان معروف، هسکل کاری آمده است.
در زبان پایتون داریم:
def compose(g, f):
def h(*args, **kwargs):
return g(f(*args, **kwargs))
return h
در زبان هسکل داریم:
multThree :: (Num a) => a -> a -> a -> a
multThree x y z = x * y * z
در زبانی همانند سی که در آن از توابع کلاس اول پشتیبانی نمیکند، پیادهسازی توابع کاری با استفاده از اشارهگر به تابع و توابع متغیر امکان پذیر است. هر چند این گونه پیادهسازیها، مشکلات خود را دارند: توابع کاری نمیتوانند از لحاظ نوع متغیر بررسی یا چک شوند. همچنین چون این در این توابع تعداد آرگومانها و نوع آنها مشخص نیست، میزان حافظهای که برنامه باید برای هر متغیر اختصاص بدهد، در ابتدا معلوم نیست و برنامه اندازهی تمام متغیرها را به صورت اندازهی یک عدد صحیح (integer) در نظر میگیرد.
توابع ناشناس و توابع تو در تو
توابع ناشناس، توابعی هستند که نام مشخصی ندارند. در زبانهایی که از توابع ناشناس پشتیبانی میشود، میتوان تابع را به عنوان یک آرگومان به یک تابع مرتبهی بالا ورودی داد.
در زبان پایتون داریم:
main_function = lambda x: x * 2
در زبان هسکل داریم:
main = map (\x -> 3 * x + 1) [1, 2, 3, 4, 5]
در زبان سی داریم:
int f(int x) {
return 3 * x + 1;
}
int main() {
int list[] = {1, 2, 3, 4, 5};
map(f, list, 5);
}
برابری توابع
همانطور که بحث برابری بین متغیرها در زبانهای برنامهنویسی مطرح است، در این زمینه نیز منطقی است که سؤال شود که آیا در مورد توابع هم میتوان برابری آنها را سنجید یا خیر. این سؤال سادهای نیست و لازم است بین انواع برابری توابع تمایز قائل شود:
برابری گسترده
دو تابع f و g را برابر به صورت گسترده مینامند اگر به ازای هر ورودی، خروجی برابری داشته باشند. با این تعریف، هر نوع پیادهسازی از انواع الگوریتمهای مرتبسازی برابر هستند. نتیجهگیری در مورد برابری توابع به صورت گسترده، امکانپذیر نیست و حتی در مورد توابعی که ورودیهای محدودی دارند، امر سادهای نیست. بنابراین زبانهای برنامهنویسی برابری تابعهای خود را به صورت برابری گسترده پیادهسازی نمیکنند.
برابری فشرده
دو تابع f و g را برابر به صورت فشرده مینامند اگر ساختار داخلی یکسانی داشته باشند. پیادهسازی این نوع برابری نیز در زبانهای برنامهنویسی راحت نیست.
برابری مرجعی
از آنجایی که پیادهسازی دو برابری بالا امکانپذیر نیست، بیشتر زبانهای برنامهنویسی برای بررسی برابری توابع، از این نوع برابری استفاده میکنند. در این نوع برابری، تمام توابع با استفاده از یک علامت مشخص میشوند و برابری دو تابع بر اساس برابری علامت آنها تعیین میشود. دو تابع کاملاً برابر که به صورت جدا تعریف شدهاند، در این تعریف برابر نخواهند بود.
پشتیبانی زبانها
پشتیبانی از توابع کلاس اول در زبانهای مختلف به صورت زیر است:
زبان | توابع مرتبهبالا | توابع تو در تو | |||
---|---|---|---|---|---|
آرگومان | نتایج | شناس | ناشناس | ||
زبانهای مبتنی بر Algol | ALGOL 60 | دارد | ندارد | دارد | ندارد |
ALGOL 68 | دارد | دارد | دارد | دارد | |
Pascal | دارد | ندارد | دارد | ندارد | |
Ada | دارد | ندارد | دارد | ندارد | |
Oberon | دارد | به صورت غیر تو در تو | دارد | ندارد | |
Delphi | دارد | دارد | دارد | 2009 | |
زبانهای مبتنی بر C | C | دارد | دارد | ندارد | ندارد |
C++ | دارد | دارد | C++11 | C++11 | |
C# | دارد | دارد | 7 | 2.0/3.0 | |
Objective-C | دارد | دارد | با استفاده از توابع ناشناس | 2.0+Blocks | |
Java | تا قسمتی | تا قسمتی | با استفاده از توابع ناشناس | Java 8 | |
Go | دارد | دارد | با استفاده از توابع ناشناس | دارد | |
Limbo | دارد | دارد | دارد | دارد | |
Newsqueak | دارد | دارد | دارد | دارد | |
Rust | دارد | دارد | دارد | دارد | |
زبانهای تابعی | Lisp | نحو | نحو | دارد | دارد |
Scheme | دارد | دارد | دارد | دارد | |
Julia | دارد | دارد | دارد | دارد | |
Clojure | دارد | دارد | دارد | دارد | |
ML | دارد | دارد | دارد | دارد | |
Haskell | دارد | دارد | دارد | دارد | |
Scala | دارد | دارد | دارد | دارد | |
F# | دارد | دارد | دارد | دارد | |
OCaml | دارد | دارد | دارد | دارد | |
زبانهای اسکریپتی | Javascript | دارد | دارد | دارد | دارد |
Lua | دارد | دارد | دارد | دارد | |
PHP | دارد | دارد | با استفاده از توابع ناشناس | 5.3 | |
Perl | دارد | دارد | دارد | دارد | |
Python | دارد | دارد | دارد | فقط بیان | |
Ruby | نحو | نحو | بدون scope | دارد | |
زبانهای دیگر | Fortran | دارد | دارد | دارد | ندارد |
Io | دارد | دارد | دارد | دارد | |
Maple | دارد | دارد | دارد | دارد | |
Mathematica | دارد | دارد | دارد | دارد | |
MATLAB | دارد | دارد | دارد | دارد | |
Smalltalk | دارد | دارد | دارد | دارد | |
Swift | دارد | دارد | دارد | دارد |
منابع
- ↑ Structure and Interpretation of Computer Programs. Section ۱٫۳ Formulating Abstractions with Higher-Order Procedures. شابک ۰-۲۶۲-۰۱۰۷۷-۱.
- ↑ Programming language pragmatics, by Michael Lee Scott, section 11.2 "Functional Programming".
- ↑ «The Implementation of Lua 5.0». Journal of Universal Computer Science: ۱۱۵۹–۱۱۷۶. doi:10.3217/jucs-011-07-1159.
- ↑ Burstall, Rod; Strachey, Christopher (2000). "Understanding Programming Languages" (PDF). Higher-Order and Symbolic Computation. 13 (52): 11–49. doi:10.1023/A:1010052305354. Archived from the original on February 16, 2010. (also on 2010-02-16
- ↑ "Higher-order function". Wikipedia (به انگلیسی). 2019-12-31.
- ↑ "First-class function". Wikipedia (به انگلیسی). 2020-01-25.
- ↑ Eric Elliott. Composing Software.
- ↑ "Currying". Wikipedia (به انگلیسی). 2020-01-29.
- ↑ «Python Advanced: Currying in Python». www.python-course.eu. دریافتشده در ۲۰۲۰-۰۲-۰۱.
- ↑ «Higher Order Functions - Learn You a Haskell for Great Good!». learnyouahaskell.com. دریافتشده در ۲۰۲۰-۰۲-۰۱.
- ↑ «functional programming - Is there a way to do currying in C?». Stack Overflow. دریافتشده در ۲۰۲۰-۰۲-۰۱.
- ↑ «Wayback Machine» (PDF). web.archive.org. ۲۰۱۶-۰۸-۲۶. بایگانیشده از اصلی (PDF) در ۲۶ اوت ۲۰۱۶. دریافتشده در ۲۰۲۰-۰۲-۰۱.
- ↑ "Anonymous function". Wikipedia (به انگلیسی). 2020-01-28.
- ↑ Andrew W. Appel (1995). "Intensional Equality ;=) for Continuations".
- ↑ "Extensionality". Wikipedia (به انگلیسی). 2018-06-10.
- ↑ "Extensional and intensional definitions". Wikipedia (به انگلیسی). 2019-10-01.