برنامه نویسی فانکشنال در جاوا اسکریپت - بخش دوم

در این مقاله از راکت قصد دارم درباره برنامه نویسی فانکشنال در جاوا اسکریپت صحبت کنم؛ زبان جاوا اسکریپت این اجازه رو به ما می‌دهد که از پارادایم‌های مختلف مثل OOP، procedural و فانکشنال استفاده کنیم.در بخش اول این مقاله بخشی از برنامه نویسی فانکشنال در جاوا اسکریپت را بررسی کردیم در این مقاله به ادامه آن می‌پردازیم.

Function composition (توابع مرکب)

برمی‌گردیم به دوران دبیرستان، وقتی که چیزی شبیه به این (f ∘ g)(x) را یادگرفتید. به این فکر کنید که همیشه می‌گفتید خب من کی و کجا از این استفاده خواهم کرد؟ خب اینجا جایی است که این به درد شما می‌خورد و بلاخره از آن استفاده می‌کنید :)))).f ∘ g به این صورت خوانده می‌شود؛ " f ترکیب g "؛ به دوشکل می‌توانید درباره این فکر کنید : (f ∘ g)(x) = f(g(x)). شما می‌توانید f ∘ g را به عنوان یک فانکشن تنها یا نتیجه‌ی فراخوانی تابع g و گرفتن خروجی آن و pass کردن آن به f، در نظر بگیرید. توجه داشته باشید که فانکشن‌ها از راست به چپ اعمال می‌شوند – یعنی g را اجرا می‌کنیم و به دنبال آن f را.

چند نکته مهم درباره توابع مرکب

1. ما ‌می‌توانیم هر تعداد فانکشن که خواستیم بسازیم ( به دو مورد محدود نمی‌شویم)
2. یکی از راه‌های ساده برای ساخت فانکشن‌ها، ‌گرفتن خروجی یک تابع و pass کردن آن به بعدی است.(یعنی : f(g(x)) )

// h(x) = x + ۱
// number -> number
function h(x) {
  return x + ۱;
}

// g(x) = x^۲
// number -> number
function g(x) {
  return x * x;
}

// f(x) = convert x to string
// number -> string
function f(x) {
  return x.toString();
}

// y = (f ∘ g ∘ h)(۱)
const y = f(g(h(۱)));
console.log(y); // '۴'

کتابخانه‌هایی مثل Ramda و lodash نیز وجود دارند که روش‌های زیباتری را برای ترکیب فانکشن‌ها یا composing functions ارائه می‌دهند. به جای اینکه به سادگی مقدار برگشتی را از یک فانکشن به فانکشن دیگر pass کنیم، می‌توانیم کمی این فانکشن مرکب را با مفاهیم ریاضی حل کنیم. در‌واقع می‌توانیم یک فانکشن مرکب واحد ساخته شده از دیگر فانکشن‌ها ایجاد کنیم ( به عنوان مثال ، ( (f ∘ g)(x) ).

// h(x) = x + ۱
// number -> number
function h(x) {
  return x + ۱;
}

// g(x) = x^۲
// number -> number
function g(x) {
  return x * x;
}

// f(x) = convert x to string
// number -> string
function f(x) {
  return x.toString();
}

// R = Ramda
// composite = (f ∘ g ∘ h)
const composite = R.compose(f, g, h);

// Execute single function to get the result.
const y = composite(۱);
console.log(y); // '۴'

بسیار خب، دریافتیم که می‌توانیم ترکیب فانکشن را در جاوا اسکریپت نیز انجام دهیم. اما مسأله مهم چیست؟ خب اگر شما واقعاً از برنامه نویسی فانکشنال استفاده می‌کنید، در حالت ایده‌آل تمام برنامه‌ی شما چیزی جز فانکش‌های مرکب نخواهد بود. در کد شما هیچ حلقه‌ای (for, for...of, for...in, while, do ) وجود نخواهد داشت. اما این غیرممکن است، می‌گویید این‌طور نیست! این جاست که باید به سمت دو موضوع بعدی یعنی فانشکن‌های بازگشتی و مرتبه بالا (recursion and higher-order functions) برویم.

Recursion

بیایید تابعی را اجرا کنیم که حاصل‌ضرب یک عدد را محاسبه می کند. قبل از آن اجازه دهید تعریف حاصل‌ضرب(factorial) را یادآوری کنیم :

n! = n * (n-۱) * (n-۲) * ... * ۱.

همین! N! یعنی حاصل تمام اعداد صحیح از n تا ۱ .ما می‌توانیم یک حلقه بنویسیم که آن را به راحتی برای ما محاسبه کند.

function iterativeFactorial(n) {
  let product = ۱;
  for (let i = ۱; i <= n; i++) {
    product *= i;
  }
  return product;
}

توجه کنید که product و i هردو بارها و بارها در داخل حلقه reassign می‌شوند. این یک روش استاندارد برای حل این مسأله است. خب حالا چگونه می‌توانیم این کار را به روش فانکشنال انجام دهیم؟ ما باید حلقه را حذف کنیم و مطمئن شویم که هیچ متغییری برای  reassign شدن نداریم. Recursion یکی از قدرتمندترین ابزار در جعبه ابزار برنامه‌نویسان فانکشنال است. Recursion از ما می‌خواهد تا مسأله اصلی را به بخش‌های کوچکتری تبدیل کنیم که شبیه به همان مسئله‌ اصلی است.

محاسبه حاصل‌ضرب یک مثال عالی‌ست. برای محاسبه n!، باید به سادگی n را بگیریم و در تمام اعداد صحیح کوچک‌تر ضرب می‌کنیم. این همان چیزی است که گفتیم:

n! = n * (n-۱)

خب! ما یک sub-problem برای حل (n-۱)! پیدا کردیم و این شبیه به مسأله اصلی یعنی n! است. چیز دیگری هم برای توجه وجود دارد: مورد پایه و اساسی ما. حالت پایه به ما می‌گوید که چه زمانی باید recursion را متوقف کنیم. اگر ما هیچ حالت پایه‌ای نداشتیم، recursion برای همیشه ادامه خواهد داشت. و اگر تعداد زیادیrecursive call داشته باشیم، خطای stack overflow رخ خواهد داد.

حالت پایه برای فانکشن فاکتوریل چیست؟ در ابتدا ممکن است فکر کنید که هنگامی است که  n == ۱ است، اما به دلیل مسائل پیچیده ریاضی، هنگامی‌ست که n == ۰. ۰! است. با توجه به این اطلاعات، بیایید یک فانکشن فاکتوریل recursive (بازگشتی)‌بنویسیم.

function recursiveFactorial(n) {
  // Base case -- stop the recursion
  if (n === ۰) {
    return ۱; // ۰! is defined to be ۱.
  }
  return n * recursiveFactorial(n - ۱);
}

خب، بیایید recursiveFactorial(۲۰۰۰۰) را حساب کنیم. بله…… چراکه نه! وقتی این کار را انجام می‌دهیم، چیزی که بدست می‌آوریم این است:

Stack overflow error

خب اینجا چه خبر است؟ خطای stack overflow دریافت کردیم! این به دلیل recursion بی‌نهایت نیست. ما می‌دانیم که حالت پایه را هندل کردیم‌( مثال :n === ۰ ). این به خاطر این است که مرورگر دارای یک استک محدود است و ما از حد آن فراتر رفتیم. هر فراخوانی recursiveFactorial باعث می‌شود یک فریم جدید روی استک قرار بگیرد؛ در‌واقع می‌توانیم استک را به صورت مجموعه‌ای از جعبه‌های روی‌ هم چیده شده تجسم کنیم. هر بار که recursiveFactorial فراخوانی می‌شود،‌یک جعبه جدید به بالا اضافه می‌شود. نمودار زیر یک نسخه از شکل ظاهری استک را در هنگام محاسبه recursiveFactorial نشان می‌دهد (۳).

 توجه داشته باشید که استک واقعی، فریمی که در بالاست، آدرس حافظه را از جایی که باید بعد از اجرا شدن return شود، ذخیره می‌کند. اما من ترجیح داده‌ام مقدار return شده را با متغییر r به تصویر بکشم. من این کار را کردم چراکه توسعه‌دهندگان جاوا اسکریپت معمولاً نیازی به تفکر درباره آدرس‌های حافظه ندارند.

استک محاسبه بازگشتی ۳! ( سه فاکتوریل)

می‌توانید تصور کنید که استک برای n = ۲۰۰۰۰ خیلی بزرگ‌تر است. آیا کاری هست که بتوانیم در این باره انجام دهیم؟ معلومه که بله! به عنوان بخشی از ویژگی‌های ES۲۰۱۵ (aka ES۶)، بهینه‌سازی و رفع این مشکل اضافه شده است. به اصطلاح به آن بهینه‌سازی proper tail calls (PTC) گفته می‌شود. اگر آخرین کاری که فانکشن recursive انجام می‌دهد این باشد که خودش را فراخوانی می‌کند و نتیجه را برگرداند، مرورگر این اجازه را می‌دهد که فریم‌های استک را elide یا omit کنید.

درواقع بهینه‌سازی برای فانکشن‌های recursive هم کار خواهد کرد، اما برای سادگی کار، ما فقط روی یک فانکشن recursive متمرکز می‌شویم.

به استک بالا توجه کنید، پس از فراخوانی فانکشن recursive ، هنوز یک محاسبه اضافی برای انجام وجود دارد.( به عنوان مثال :n * r). این به این معنیست که مرورگر نمی تواند آن را با استفاده از PTC بهینه سازی کند. با این حال،‌ می‌توانیم فانکشن را به شکلی بازنویسی کنیم که تا آخرین مرحله recursive call باشد. یک ترفند برای انجام این کار، pass کردن نتیجه‌ی میانی (به عنوان مثال در مورد حاصل) به فانکشن به عنوان یک آرگومان است.

'use strict';

// Optimized for tail call optimization.
function factorial(n, product = ۱) {
  if (n === ۰) {
    return product;
  }
  return factorial(n - ۱, product * n)
}

بیایید هم‌اکنون استک بهینه شده را هنگام محاسبه فاکتوریل تصور کنیم (۳). همانطور که نمودار زیر نشان می دهد، در این حالت استک هرگز بیش از دو فریم رشد نمی‌کند؛ و دلیل آن این است که ما تمام اطلاعت ضروری ( برای مثال: حاصل) را بهrecursive فانکشن pass کرده‌ایم.

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

استک بهینه شده برای محاسبه بازگشتی ۳!‌ (‌سه فاکتوریل) با استفاده از PTC

اکنون این مورد را در یک مرورگر به دلخواه خود اجرا کنید، فرض کنید در safari اجرا کرده‌اید، و سپس جوابی که خواهید گرفت، بی‌نهایت یا Infinity است ( عددی بالاتر از حداکثر تعداد قابل نمایش در جاوا اسکریپت) اما می‌بینید که خطای stack overflow دریافت نکردیم، پس خوب است! حالا در مورد مروگرهای دیگر چه فکر می‌کنید؟ به نظر می‌رسد که safari تنها مرورگری است که PTC را پیاده‌سازی کرده و ممکن هم هست که در این زمینه تنها مرورگر باشد. جدول سازگاری را در ادامه آورده‌ام:

سازگاری PTC

مرورگرهای دیگر استاندارد دیگری را به نام syntactic tail calls (STC) برای رقابت پیش می‌برند."Syntactic" به این معنیست که شما باید از طریق سینتکس جدید مشخص کنید که می‌خواهید این فانکشن را در بهینه سازی tail-call شرکت دهید. حتی با اینکه هنوز پشتیبانی گسترده‌ای در مرورگرها وجود ندارد، اما هنوز هم ایده‌ی خوبیست که recursive فانکشن‌های خود را بنویسید که هر زمان (که به هر حال) می‌آید، برای بهینه‌سازی tail-call آماده باشند.

در قسمت بعد و آخرین قسمت از این مقاله برنامه نویسی به Higher-order function ها و Currying خواهیم پرداخت. امیدوارم تا حدودی پی برده باشید که برنامه نویسی فانکشنال در جاوا اسکریپت به چه نحویست.

منبع