توابع کلاس اول

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

• فرستادن تابع به عنوان آرگومان تابعی دیگر
• برگرداندن تابع به عنوان مقدار خروجی یک تابع دیگر
• تخصیص دادن یک تابع به یک متغیر
• ذخیره کردن تابع در ساختار داده‌های مختلف

برخی از نظریه‌داران حوزه‌ی زبان‌های برنامه‌نویسی برای توابع کلاس-اول، علاوه بر موارد بالا، پشتیبانی از توابع ناشناس (anonymous functions) را نیز الزامی می‌دانند. در زبان‌هایی که توابع کلاس-اول دارند، نام تابع هیچ وضعیت خاص یا ویژه‌ای ندارد و همانند متغیرهایی از نوع تابع با آنها برخورد می‌شود. اصطلاح توابع کلاس-اول برای اولین بار توسط کریستوفر استراچی در زمینۀ "توابع به عنوان شهروندان درجه-یک" و در اواسط دهۀ 1960 میلادی ابداع شد.

توابع کلاس-اول برای برنامه‌نویسی تابعی الزامی هستند. در برنامه‌نویسی تابعی استفاده از توابع مرتبه‌ی بالا متداول است. یک مثال ساده از تابع مرتبه‌ی بالا، تابع نگاشت (map) است که به عنوان آرگومان و ورودی خود یک تابع و یک لیست می‌گیرد و در نهایت یک لیست جدید برمی‌گرداند که تابع مورد نظر بر روی هر یک از اعضای لیست اعمال شده است. برای اینکه یک زبان برنامه‌نویسی بتواند از تابع نگاشت پشتیبانی کند، باید یک تابع را به عنوان آرگومان تابعی دیگر بپذیرد.

مفاهیم

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

توابع مرتبه‌ی بالا

اطلاعات بیشتر: تابع مرتبه‌بالا

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

در زبان‌هایی که دارای توابع کلاس اول هستند، توابع می‌توانند مانند متغیرهای معمولی، به عنوان ورودی به توابع دیگر داده شوند. بنابراین برای پیاده‌سازی توابع مرتبه‌ی بالا، بهتر است که زبان مورد نظر از توابع کلاس اول پشتیبانی کند. این توابع به دو صورت می‌توانند از توابع کلاس اول استفاده کنند: زمانی که آرگومان‌های ورودی تابع، تابع باشند و زمانی که خروجی تابع، یک تابع باشد.

در زبان پایتون داریم:

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	دارد	دارد	دارد	دارد