Incremental - वृद्धिशील गणना के लिए लाइब्रेरी

• Incremental एक लाइब्रेरी है जो इनपुट बदलने पर जटिल गणनाओं को कुशलतापूर्वक अपडेट करने में मदद करती है
• यह Umut Acar आदि के self-adjusting computation शोध से प्रेरित है
• स्प्रेडशीट जैसी बड़े पैमाने की गणनाओं को डेटा बदलाव पर कुशलतापूर्वक प्रतिक्रिया देने के लिए संरचित किया जा सकता है
• GUI एप्लिकेशन के व्यू में नए डेटा को कुशलतापूर्वक प्रतिबिंबित किया जा सकता है
• derived data को मूल डेटा के साथ लगातार सिंक में रखा जा सकता है, जैसे filtering या mapping का inverse transformation

---

उपयोग के क्षेत्र

• बदलते इनपुट के अनुसार जटिल गणनाओं को कुशलतापूर्वक अपडेट करता है
• स्प्रेडशीट-शैली की बड़े पैमाने की गणनाओं को डेटा परिवर्तन पर प्रतिक्रिया देने के लिए संरचित किया जा सकता है
• GUI व्यू में नए डेटा को कुशलतापूर्वक एकीकृत किया जा सकता है
• मूल डेटा से निकाले गए derived data को लगातार सिंक्रोनाइज़ रखता है
  • डेटा filtering
  • mapping का inverse transformation

डिज़ाइन पृष्ठभूमि और दस्तावेज़

• Umut Acar आदि का self-adjusting computation शोध से प्रेरित
• विस्तृत API और उपयोग विधि incremental/src/incremental_intf.ml में देखी जा सकती है
• अनौपचारिक शुरुआती सामग्री के रूप में blog post और परिचय वीडियो उपलब्ध हैं

[GN⁺]

Hacker News की राय

• इस तरह की reactive programming आजकल JavaScript UI frameworks में signals नाम से व्यापक रूप से इस्तेमाल होती है, और standardization proposal भी चल रहा है
  Vue, SolidJS, Svelte, Ember, Angular इसका उपयोग करते हैं, और React में MobX और Jotai जैसी implementations हैं। change propagation और directed acyclic graph (DAG) evaluation algorithms के भी कई प्रकार हैं, और मेरी जानकारी में SolidJS 2 Incremental जैसा height-based algorithm इस्तेमाल करता है
  मैं एक implementation पर प्रयोग कर रहा हूँ जो nodes को Int32Array arena में allocate करती है और linked list से जोड़ती है, ताकि dependency edges की संख्या के अनुपात में होने वाले GC load से बचा जा सके
  Rust में भी कई implementations हैं; UI framework के रूप में Leptos है, और rust-analyzer द्वारा इस्तेमाल होने वाले general-purpose incremental computation system के रूप में Salsa है। इसे dependency को automatically track करने वाले build system की तरह भी देखा जा सकता है; tup build tasks को instrument करके यह पता लगाता है कि कौन-सी files पढ़ी गईं और dependency relations सेट करता है। लेखक का लेख और क्लासिक Build Systems à la Carte भी पढ़ने लायक हैं

  • एक हल्का dependency graph बनाया जा सकता है जिसे जल्दी खाली किया जा सके। signals कैसे बदले, यह बताने की ज़रूरत नहीं; बस इतना चिन्हित करना काफी है कि वे बदले हो सकते हैं, और change होने पर dependent targets को खाली करके जब नया data माँगा जाए तब उन्हें फिर से register कर दिया जाए। इस प्रक्रिया में कुछ subscribers को ऐसे changes की notifications मिल सकती हैं जिनमें अब उनकी रुचि नहीं है
    हालांकि, incremental computation और functional reactive programming (FRP) वास्तव में अलग-अलग क्षेत्र हैं। incremental computation delta पर काम करने वाले functions को explicitly derive करता है, जबकि FRP सिर्फ damaged हिस्सों को खोजकर repair करने का तरीका भी अपना सकता है
  • एक और प्रमुख उदाहरण JetBrains Noria है। Noria का मूल किसी UI framework में नहीं बल्कि एक incremental computation platform में है, लेकिन फिलहाल इसका उपयोग JetBrains Air IDE की GUI rendering optimization में हो रहा है
  • जटिल objects के update handling में काफ़ी अंतर दिखता है, और scheduling भी अलग होने की संभावना है

• Incremental library का उद्देश्य शायद उस समस्या को हल करना है जिसमें source data बदलने पर computation graph को आंशिक रूप से फिर से concretize करना पड़ता है। यह एक अच्छे build system जैसा है और functional programming में भी आम तौर पर इस्तेमाल होने वाला उपयोगी दृष्टिकोण है
  incremental computation के क्षेत्र में Differential Dataflow, उससे सटी हुई तकनीक Timely Dataflow, और DBSP भी हैं। Feldera, DBSP पर आधारित है और Materialize को Differential Dataflow से जुड़े लोग चला रहे हैं
  मैं वित्तीय data और workloads के लिए विशेष एक अलग approach modolap विकसित कर रहा हूँ। यहाँ हल करने के लिए कई बड़े और महत्वपूर्ण सवाल हैं। इस संदर्भ में Signals and Threads का build systems episode भी देखना उपयोगी होगा

  • modolap का मुख्य button दबाते ही बिना किसी explanation के सीधे 2,000 डॉलर Stripe payment पर पहुँच जाना काफ़ी साहसी है
  • openivm एक SQL-to-SQL compiler है जो व्यापक aggregate operations को incremental operations के रूप में implement करता है, और materialized views को automatically maintain करने के लिए DuckDB extension भी देता है

• Goldman ने भी लगभग 30 साल पहले financial instrument pricing के लिए यही approach इस्तेमाल की थी। वहाँ लगभग 13 साल काम करने के दौरान मुझे Node Purpling पर लंबी चर्चाएँ याद हैं
  computer science आगे बढ़ चुका है और मेरी नज़र में यह graph approach नहीं है, लेकिन differentiation जैसे computations महंगे होते हैं, इसलिए runs की संख्या को सैद्धांतिक न्यूनतम के जितना संभव हो उतना करीब लाना चाहिए। इससे जुड़ी HN चर्चा भी है

  • इसी वजह से अनौपचारिक रूप से bank python कहे जाने वाला environment बना, और यह लेख इसे अच्छी तरह कवर करता है
    dedicated in-house IDE को देखते ही ग़ुस्से में नौकरी छोड़ देने का मन न भी करे, तब भी नए लोगों को ढलने में असामान्य रूप से लंबा समय लगता है, और कई महीने बाद भी बुनियादी रूप से अलग तत्व सीखते रहना पड़ता है — यही बात समस्या को सबसे अच्छी तरह बयान करती है। मुझे भी अपने काम को पूरी तरह समझने में लगभग ढाई साल लगे थे
    यह समझ आने तक कि दोबारा training देनी पड़ेगी, लगभग कोई modern training भी नहीं थी। सबसे खराब हिस्सा UI बनाने के लिए coding करना था, और नए projects में इसके इस्तेमाल की मंज़ूरी नहीं मिलती थी

• मेरी पसंदीदा technical talks में से एक है Seven Implementations of Incremental: https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/

• कुछ साल पहले मेरी dataflow programming में गहरी रुचि थी, और लगता है बहुत-से लोग इस समस्या तक अलग-अलग दिशाओं से पहुँचे थे। इस library को देखते ही मुझे तुरंत Clojure का Javelin याद आया

• अगर यह दिलचस्प लगे, तो Incremental के ऊपर बनी UI library Bonsai भी देखने लायक है
  React जैसी libraries virtual DOM की मदद से अनावश्यक काम को प्रभावी ढंग से छोड़ देती हैं, लेकिन virtual DOM खुद बनाने में भी समय लगता है। Bonsai virtual DOM को भी incremental बना देता है, और इसके साथ काम करना भी मज़ेदार है
  मैंने Revery, जिसका अब maintenance नहीं होता, के लिए एक desktop UI library बनाई थी, लेकिन वह Bonsai के काफ़ी पुराने version का उपयोग करती है

• मैं पूरी तरह नहीं समझ पाया कि यह observable pattern से कैसे अलग है, जहाँ इनपुट नया मान publish करता है, computation से गुजरता है, और नया परिणाम subscriber तक पहुँचता है।
  इसमें change detection और जब मान वही रहे तो propagation रोकने जैसी optimization होंगी, लेकिन यह observable में भी संभव है। stabilize के साथ recomputation से पहले बदलावों को batch करना भी दिलचस्प है, पर यह भी observable से implement किया जा सकता है।
  जानना चाहता हूँ कि क्या मुख्य अंतर internal introspection से computation graph को अपने-आप बनाना है, या कोई और अधिक बुनियादी बात है

  • यह इस पर निर्भर करता है कि आप observable pattern को कैसे define करते हैं। यहाँ बुनियादी बात lazy evaluation और graph nodes के बीच weak connection है। node values केवल observe करने पर materialize होती हैं, और execution के दौरान graph structure में बदलाव भी लचीले ढंग से संभाले जाते हैं।
    अगर केवल कुछ nodes को observe किया जा रहा हो, तो पूरे graph को materialize करने की ज़रूरत नहीं होती। आप किसी भी समय computation रोक सकते हैं, graph को आंशिक रूप से updated स्थिति में छोड़ सकते हैं, फिर inputs में और बदलाव कर सकते हैं, और बाद में जिन nodes में रुचि है उनका materialization जारी रख सकते हैं; algorithm सारे changes को व्यवस्थित कर देता है।
    incremental computation मूल रूप से ऐसा व्यापक शब्द है जो इन गुणों को समेटता है, और उसी system को observer और subscriber model के रूप में भी बनाया जा सकता है। classic Excel spreadsheet इसका अच्छा उदाहरण है, और Salsa algorithm explained भी देखना उपयोगी है
  • मोटे तौर पर observable में आप किसी target को subscribe करते हैं और values सुनते हैं, जबकि Incremental computation और state के पूरे DAG में फैले cache के अधिक करीब है। इससे केवल ज़रूरी हिस्सों को फिर से compute करके optimization की जा सकती है।
    Ron Minsky की talk बहुत अच्छी है
  • यह लेख incremental और streaming systems के परिदृश्य को समझने में मदद करता है
  • मेरा भी लगभग यही विचार था। पहली नज़र में यह dependency tracking वाले reactive programming के बहुत करीब लगता है। जिज्ञासा है कि असली फायदा API usability है, या वे internal optimizations हैं जिन्हें सामान्य observable implementation में व्यवहारिक रूप से पाना मुश्किल होता है
  • बुनियादी रूप से यह graph ही है, लेकिन विशाल और dynamically changing graph में changes को सही और कुशल ढंग से compute करने का तरीका है।
    आप ऐसे diamond-shaped subgraph की कल्पना कर सकते हैं जो सैकड़ों intermediate nodes में बंटता है और अलग-अलग लंबाई वाले paths से होकर फिर मिल जाता है। कुछ paths में min(A, B) हो सकता है, और केवल maximum वाला पक्ष बदल रहा हो।
    साधारण observer तरीका computation को संभावित रूप से exponential रूप से बढ़ा सकता है और concurrency समस्याएँ भी पैदा कर सकता है। यह library graph structure को dynamically बदलने पर भी near-optimal और correct रहती है। observer वगैरह से भी वही परिणाम पाया जा सकता है, लेकिन performance cliffs से बचते हुए उसे सही ढंग से implement करना कहीं अधिक कठिन है

• Jane Street project की खासियत यह है कि वह research या niche systems में रहे विचारों को ऐसे रूप में पैक करता है जिसे developers वास्तव में इस्तेमाल कर सकें। library अपनाए बिना भी इसके design documents आम तौर पर पढ़ने लायक होते हैं

• Electric Clojure client-server boundary के पार incremental rendering देता है। सबसे मिलता-जुलता मुझे SolidJS लगता है, लेकिन SolidJS केवल frontend तक सीमित है

• मैंने पहले कुछ ऐसा ही बनाया था और उसके लिए लगभग कोई precedent नहीं मिला था। उपयोग का उद्देश्य खत्म हो जाने पर project बंद कर दिया, लेकिन इसे फिर देखना चाहता हूँ; npm पर यह अभी भी data-rambler नाम से मौजूद है।
  विचार यह था कि JavaScript runtime में load की जा सकने वाली domain-specific language (DSL) को data streams feed किए जाएँ। modules data को कई output streams में बदलते थे, और फिर उन्हें अलग reporting library को भेजा जाता था ताकि template-based dynamic reports बन सकें।
  पहला version ही काफ़ी शक्तिशाली था, लेकिन complexity घटाने के लिए इसे अधिक JavaScript-जैसे syntax में सुधारने की बड़ी योजना भी थी