محاسبات افزایشی

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

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

محاسبات افزایشی یک جفت ورودی/خروجی جدید را از یک یا چند رابطه ورودی/خروجی قدیمی به دست می‌آورد. برای انجام این کار، ΔP باید یک تغییر در ورودی را به یک تغییر در خروجی مرتبط کند. مصرف‌کننده نتیجه ممکن است به خروجی کامل به روز شده یا خروجی دلتا یا هر دو علاقه‌مند باشد.

ایستا در مقابل پویا

تکنیک‌های محاسبات افزایشی را می‌توان به‌طور کلی به دو نوع روش تقسیم کرد:

رویکردهای ایستا تلاش می‌کنند تا یک برنامه افزایشی را از یک برنامه P معمولی با استفاده از، به عنوان مثال، طراحی دستی و بازآرایی یا تبدیل‌های خودکار برنامه استخراج کنند. این تغییرات برنامه قبل از اینکه هر ورودی یا تغییر ورودی ارائه شود، رخ می‌دهد.

رویکردهای پویا اطلاعات مربوط به اجرای برنامه P را روی یک ورودی خاص (I1) ثبت می‌کنند و از این اطلاعات زمانی که ورودی تغییر می‌کند (به I2) برای به‌روزرسانی خروجی (از O1 به O2) استفاده می‌کنند. شکل رابطه بین برنامه P، تابع محاسبه تغییر ΔP، که هسته برنامه افزایشی را تشکیل می‌دهد، و یک جفت ورودی و خروجی، I1، O1 و I2، O2 را نشان می‌دهد.

رویکردهای تخصصی در مقابل رویکردهای همه منظوره

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

روش‌های ایستا

مشتقات برنامه

با توجه به یک محاسبات $C=f(x_1,x_2,\dots x_n)$ و یک تغییر بالقوه $x_j:={\mathrm{\Delta }}_{x_j}$ ، می‌توانیم کد را قبل از تغییر (پیش از مشتق) و بعد از تغییر (پس از مشتق) وارد کنیم تا مقدار $C$ سریعتر از اجرای مجدد $f$ به‌روز شود. پیج فهرستی از قوانین برای تمایز رسمی برنامه‌ها در SUBSETL نوشته‌است.

مشاهده نگهداری

در سیستم‌های پایگاه داده ازجمله DBToaster، نماها با جبر نسبی تعریف می‌شوند. نگهداری نمای افزایشی به‌طور ایستا جبر نسبی را تجزیه و تحلیل می‌کند تا قوانین به‌روز شده را ایجاد کند که در حضور به‌روز رسانی‌های کوچک، مانند درج یک ردیف، به سرعت نما را حفظ کند.

روش‌های پویا

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

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

ارزیابی جزئی را می‌توان به عنوان یک روش برای خودکارسازی ساده‌ترین حالت ممکن محاسبات افزایشی در نظر گرفت، که در آن اقدام به تقسیم داده‌ها به دو دسته می‌کند: آنهایی که می‌توانند بر اساس ورودی برنامه متفاوت باشند، و آنهایی که نمی‌توانند (و کوچکترین واحد تغییر به سادگی "همه داده‌هایی است که می‌توانند متفاوت باشند"). ارزیابی جزئی را می‌توان با سایر تکنیک‌های محاسباتی افزایشی ترکیب کرد.

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

سیستم‌های موجود

کامپایلر و پشتیبانی زبان

• افزایش خودکار (همچنین با نام "محاسبات خود تنظیم" و "برنامه ریزی عملکردی تطبیقی")، Delta ML , Haskell Adaptive
• ژنراتور سینتی سایزر کورنل
• IceDust - یک زبان اختصاصی با دامنه خاص.

چارچوب‌ها و کتابخانه‌ها

• Adapton - با پیاده‌سازی در چندین زبان
• محدودیت‌های جریان داده یک طرفه (محاسبات واکنشی در C++)
• جریان بانرخ متفاوت
• جین استریت افزایشی
• دیتالوگ افزایشی (Logicblox)
• پرولوگ افزایشی (XSB)
• رویکردهایی با دامنه خاص:
  • بررسی نوع افزایشی

کاربردها

• پایگاه‌های داده (مشاهده نگهداری)
• ساخت سیستم‌ها
• صفحات گسترده
• محیط‌های توسعه
• محاسبات مالی
• ارزیابی گرامر صفات
• محاسبات نمودار و پرس و جو
• رابط‌های کاربری گرافیکی (مانند React و DOM diffing)
• کاربردهای علمی

جستارهای وابسته

• برنامه‌نویسی واکنشی
• برنامه‌نویسی واکنشی تابعی
• حفظ کردن
• تبدیل دو طرفه