प्रोग्रामिंग: शून्य से भी कम के साथ प्रोग्रामिंग

• यह लेख इंटरव्यू की स्थिति में एक उम्मीदवार द्वारा साधारण FizzBuzz समस्या को lambda calculus-आधारित pure function combinators से लागू करने की व्यंग्यात्मक कथा प्रस्तुत करता है
• नायक JavaScript से शुरुआत करता है, लेकिन धीरे-धीरे S, K, I combinators को परिभाषित करते हुए भाषा की बुनियादी संरचना को खुद ही फिर से निर्मित करता है
• इसके बाद वह boolean, numbers, lists, strings सबको केवल combinators से व्यक्त करता है, और Y combinator के जरिए recursion लागू करता है
• अंततः वह FizzBuzz को पूरी तरह point-free शैली में पूरा करता है, लेकिन कोड इतना फैल जाता है कि मनुष्यों के समझने से परे हो जाता है
• यह लेख प्रोग्रामिंग भाषाओं के सार और abstraction की चरम सीमा को हास्यपूर्ण ढंग से खंगालता है और डेवलपर संस्कृति के आत्म-व्यंग्य को उजागर करता है

---

इंटरव्यू की शुरुआत: FizzBuzz और combinators

• कहानी की शुरुआत उस दृश्य से होती है जहाँ इंटरव्यूअर Dana उम्मीदवार से FizzBuzz समस्या हल करने को कहती हैं
  • उम्मीदवार सामान्य loop की जगह S और K combinators को परिभाषित करते हुए समस्या हल करना शुरू करता है
  • Dana हैरान होती हैं, लेकिन उम्मीदवार कहता है, “बस थोड़ा और करना है,” और आगे बढ़ता रहता है
• उम्मीदवार I, B, C, W, T जैसे कई combinators को परिभाषित करता है और इन्हें एक नई भाषा के बुनियादी घटकों की तरह इस्तेमाल करता है
  • हर combinator function composition, argument swapping, self-application जैसे lambda calculus के मुख्य विचारों को लागू करता है
  • कोड टिप्पणियों में “Bluebird, Cardinal, Warbler, Thrush” जैसे combinator नामों के उपनाम भी दिखाई देते हैं

boolean और numbers की परिभाषा

• उम्मीदवार TRUE, FALSE, NOT को सिर्फ combinators से परिभाषित कर boolean logic तैयार करता है
  • Dana पूछती हैं, “क्या यह lambda calculus है?”, लेकिन उम्मीदवार जवाब देता है, “lambda calculus बहुत भारी-भरकम है।”
• इसके बाद वह ZERO, SUCC, PRED, IS_ZERO आदि को परिभाषित कर number system (Church numeral) बनाता है
  • SUCC successor, PRED predecessor, और DECREMENT ऐसा decrement operation लागू करता है जो 0 से नीचे नहीं जाता
  • ONE से TEN तक की संख्याएँ क्रमवार परिभाषित की जाती हैं

recursion और Y combinator

• उम्मीदवार ADD function को परिभाषित करता है और फिर उसे धीरे-धीरे point-free रूप में बदल देता है
  • वह ADD_MAKER को परिभाषित करता है और recursion संभव करने के लिए उसे Y combinator में लपेट देता है
  • Dana कहती हैं, “JavaScript में भी recursion हो सकती है,” लेकिन उम्मीदवार जवाब देता है, “यह जल्द ही JavaScript नहीं रहेगा।”
• JavaScript की eager evaluation के कारण stack overflow हो जाता है, तो उम्मीदवार Skoobert नामक एक “lazy” JS interpreter में कोड चलाता है
  • नतीजे में सफलतापूर्वक 3 आउटपुट होता है

arithmetic, lists, और strings

• उम्मीदवार SUBTRACT, MULTIPLY, MOD, DIVIDE जैसी सभी arithmetic operations को combinator-आधारित रूप में लागू करता है
  • हर operation IS_ZERO, PRED, SUCC आदि को recursively जोड़कर बनाई जाती है
• इसके बाद वह CONS, FIRST, REST, EMPTY को परिभाषित कर list structure बनाता है
  • MAP, FOLD, RANGE, CONCAT जैसी high-order functional operations भी combinator रूप में लागू की जाती हैं
• list को string के रूप में आउटपुट करने के लिए वह renderList, showLines functions लिखता है
  • Dana अब तक जैसे पूरी तरह हार मान चुकी हों, कोई प्रतिक्रिया नहीं देतीं

characters और strings की रचना

• उम्मीदवार character codes को 1 से 9 और फिर 10-10 की इकाइयों में combinators के जरिए परिभाषित करता है
  • CHAR_A से CHAR_Z और CHAR_0 से CHAR_9 तक सबको number combinations के रूप में व्यक्त किया जाता है
• ARRAY function के जरिए strings को list में बदला जाता है, और FIZZ, BUZZ, FIZZBUZZ बनाए जाते हैं
  • extractString function के जरिए list को वास्तविक string में बदला जाता है
  • console output का परिणाम "fizzbuzz" होता है

numbers से strings में रूपांतरण

• वह NUMBER_TO_DIGIT_LIST परिभाषित करता है, जो numbers को digit list में बदलता है, और NUMBER_TO_STRING, जो उसे string में बदलता है
  • DIVIDE, MOD, TEN आदि का उपयोग करके हर digit को अलग किया जाता है
  • DIGITS_NUMERAL list के जरिए number characters की mapping की जाती है
• इस प्रक्रिया से number → character → string रूपांतरण पूरी तरह combinator system के भीतर संभव हो जाता है

FizzBuzz की पूर्णता

• FIFTEEN, ONE_HUNDRED को परिभाषित कर, MAP और RANGE की मदद से 1 से 100 तक की list बनाई जाती है
  • हर संख्या के लिए 3, 5, 15 के multiples की जाँच कर "Fizz", "Buzz", "FizzBuzz" या number string आउटपुट की जाती है
  • showLines(extractString)(FIZZBUZZ_RESULT) से अंतिम परिणाम आउटपुट होता है
• Dana पूछती हैं, “अब संतुष्ट हो?”, लेकिन उम्मीदवार सभी variable definitions हटा देता है और कोड को सिर्फ pure combinators से फिर से लिखता है
  • परिणाम होता है हजारों लाइनों में फैला सिर्फ S और K से बना एक विशाल expression

अंत और अर्थ

• यह लेख प्रोग्रामिंग भाषा के मूलभूत घटकों की पड़ताल करने के साथ-साथ डेवलपर्स की उस प्रवृत्ति का व्यंग्य भी करता है, जिसमें वे साधारण समस्याओं को जरूरत से ज्यादा जटिल बना देते हैं
  • “शून्य से भी कम के साथ प्रोग्रामिंग” शीर्षक भाषा की न्यूनतम इकाइयों से दुनिया को फिर से रचने की कोशिश का प्रतीक है
• यह रचना functional programming, lambda calculus, combinatory logic की गहरी समझ को हास्य और कथा के माध्यम से प्रस्तुत करने वाला तकनीकी साहित्य है
  • साथ ही, यह व्यंग्यात्मक रूप से दिखाती है कि “FizzBuzz जैसी चीज़ को भी दार्शनिक प्रयोग में बदल देने वाली डेवलपर मानसिकता” कैसी होती है

[GN⁺]

Hacker News राय

• लगता है लोग सोच रहे हैं, “आखिर यह है क्या?”, इसलिए combinator का सार समझाता हूँ
  combinator एक ऐसा function है जो global state को नहीं बदलता और बाहरी variables को capture नहीं करता। वही arguments देने पर यह हमेशा वही result देता है, और सिस्टम के बाकी हिस्सों पर कोई असर नहीं डालता
  ऐसे pure functions को जोड़ने पर एक और combinator बनता है। यानी pure functions की composition भी pure function ही रहती है
  ऐसे functions assembly या C में भी आसानी से लिखे जा सकते हैं। उदाहरण के लिए x64 पर S और K को सीधे implement करके, उसके ऊपर combinator-आधारित Common Lisp compile किया जाए, तो आखिरकार Lisp सिर्फ दो assembly functions के ऊपर चल रहा होगा
  performance शायद बहुत अच्छी न हो, लेकिन अगर अक्सर इस्तेमाल होने वाले कुछ सौ patterns को inline combinator बनाकर नाम दे दिए जाएँ, तो यह काफ़ी practical “machine” बन सकती है
  यह संरचना mutation से डरने वाले Forth, bytecode VM, या उन CPU जैसी भी लगती है जो combinator को “instruction” कहते हैं
  आखिर में combinator को implementation details को जितना हो सके उतना नज़रअंदाज़ करके applied computer science की अभिव्यक्ति कहा जा सकता है। इसलिए इसे lambda calculus से भी सरल कहा जा सकता है
  अगर lambda calculus को कुछ combinator से implement करके, उसके ऊपर Lisp रखा जाए, तो stack के सबसे निचले स्तर पर किए जाने वाले machine-dependent काम बहुत कम हो जाते हैं

  • ऐसा लग रहा है कि कहीं कोई function खुद को call करके seed round पा गया होगा
  • छात्र जीवन में मैंने भी कुछ ऐसा किया था (Lisp नहीं, बल्कि macro expansion होकर lambda calculus में बदलने वाली एक simple language थी) और यह कि सिर्फ S और K से सब कुछ implement किया जा सकता है, सच में चौंकाने वाला था। लेकिन साथ ही यह कितना inefficient है, यह भी उतना ही हैरान करने वाला था। हाँ, instruction set बड़ा होने पर हालत काफ़ी बेहतर हो जाती है
  • सैद्धांतिक रूप से तो सब संभव है, लेकिन व्यवहार में graph rewriting की तुलना में कहीं ज़्यादा practical computing foundation चुननी चाहिए। जब तक आप computability की limits को explore नहीं कर रहे, यह लगभग party trick जैसा है। ऊपर से number representation भी समस्या है। कम से कम two's complement integers और efficient destructors हों तभी प्रभावित हुआ जा सकता है
  • क्या सच में इस तरह combinator के ऊपर implement किया गया Lisp कहीं मौजूद है, यह जानने की उत्सुकता है। अगर है, तो उसे port करना काफ़ी मज़ेदार होगा

• let A = (x) => (y) => (z) => x(z)(y((w) => z))
  

  इसे बस कुछ बार compose करना होता है

  let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A);
  let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A);
  

  “lambda calculus वगैरह कभी इस्तेमाल मत करो। वह बहुत फूली हुई language है.”
  लेकिन असल में combinatory logic उससे भी ज़्यादा फूली हुई है। वही program व्यक्त करने के लिए ज़्यादा bits चाहिए होते हैं
  lambda calculus तो उल्टा सबसे संक्षिप्त languages में से एक है
  JavaScript जैसी eager language में भी arguments को dummy lambda में लपेटकर उसे lazy बनाया जा सकता है। उदाहरण के लिए यह JS BLC interpreter देखें
  संबंधित paper के लिए यह PDF और IOCCC उदाहरण देखें

  • दिलचस्प बात यह है कि सबसे तेज़ lambda calculus interpreters (जैसे uni.c) भी आखिरकार lambda expressions को combinatory logic में बदलकर evaluate करते हैं। बस वे S, K से बड़ा base set इस्तेमाल करते हैं
  • “bloated language” का मतलब ऐसी language है जिसमें अनावश्यक features बहुत हों। जैसे C++ का code C से छोटा हो सकता है, लेकिन वह कहीं ज़्यादा जटिल language है
  • उस code block को देखते हुए जो आवाज़ मुँह से निकलती है, वह लगभग argument list से मेल खाती है
  • लगता है K और S की definitions में parentheses की गलती है। सुधरा हुआ version यह है

    let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A));
    let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A);
    

    और eager language को lazy इस तरह बनाया जा सकता है

    let A = x => y => z => () => x()(z())(y()(w => z()));
    

  • “w क्या है?” यह सवाल उठता है

• “FizzBuzz जानते हो?”
  “बिलकुल। 10-character code golf version, juniors के लिए समझ आने वाला 12-line version, या अजीब ज्ञान-प्रदर्शन वाला पूरी तरह उल्टा-पुल्टा version?”

  • इसे देखकर मैंने C64 BASIC में सबसे तेज़ FizzBuzz implement करके देखा। सुबह का समय मज़े में बर्बाद किया
    नतीजे का लिंक

• combinator logic की व्याख्या सच में शानदार थी। लिखने का अंदाज़ इस series की याद दिलाता है

  • व्याख्या से ज़्यादा यह दिखाने वाला प्रदर्शन लगता है। फिर भी काफ़ी प्रभावशाली था
  • पक्का लगता है कि उस series से प्रेरणा ली गई है। लेखक का नाम लिया होता तो और अच्छा रहता
  • UK में Online Safety Act की वजह से पहुँच blocked है, यह अफ़सोस की बात है

• मुझे पहले पढ़ा हुआ “FizzBuzz in TensorFlow” लेख याद आ गया
  लिंक

  • अच्छा लगा कि इस बार कम-से-कम साथ चल पाना संभव था

• इस तरह का programming interview frame थोड़ा ग़लत लगता है
  interview का मकसद है (1) उम्मीदवार की programming knowledge जाँचना, (2) कंपनी की programming culture fit देखना
  उदाहरण के लिए अगर JavaScript position के लिए भर्ती हो रही है और कोई combinatory logic में बहुत डूबा हुआ है, तो संभव है कि cultural fit न बैठे। इसलिए reject होना अजीब नहीं है

  • शायद इस series का संदर्भ है। हालाँकि मूल पाठ में यह साफ़ नहीं कहा गया
  • कभी-कभी HN commenters ऐसे लगते हैं जैसे वे मज़ा भूल चुके लोग हों
  • programming की विविधता पर ज़ोर देना सही है, लेकिन वह भी किसी खास ecosystem expertise को चुनने का एक रूप है। ज़्यादातर मामलों में यह legacy code या मौजूदा ecosystem के उपयोग के लिए किया गया चयन होता है
  • “IQ कम हो तो reject” जैसी बातें मज़ेदार हैं, लेकिन आख़िरकार पैसे काफ़ी हों तो किसी भी OOP/FP/FRP style के साथ खुद को ढाला जा सकता है
  • असल दुनिया में ऐसे आदर्श interview बहुत कम होते हैं। ज़्यादातर मामलों में हताश interviewers अपनी worldview थोपते हैं। असली काम का interview की चीज़ों से लगभग कोई लेना-देना नहीं होता

• Moses Schönfinkel को याद करने का समय है
  उन्होंने 1920 में Hilbert के छात्र रहते हुए combinatory logic का आविष्कार किया था। रूस लौटने के बाद वे मानसिक बीमारी से जूझे और ग़रीबी में मॉस्को में उनकी मृत्यु हुई। Wikipedia के अनुसार, उनके papers पड़ोसियों ने जलावन के लिए जला दिए थे

• आख़िरी code block इतना बड़ा है कि horizontal scroll आ जाता है (166KB)
  S और K curried functions हैं, जो एक बार में सिर्फ एक argument लेते हैं
  ज़्यादा जानकारी के लिए यह StackOverflow answer देखें

  • scroll करते समय syntax highlighting के हार मानने वाला क्षण सबसे मज़ेदार था

• “Bluebird, cardinal, warbler, thrush” जैसे पक्षियों वाले नाम बहुत पसंद आए। इन्हें नई naming convention बनाना चाहता हूँ
  “Barendregt. Church तो बहुत mainstream है.”
  “जल्द ही यह JavaScript भी नहीं रहेगा.”
  ऐसा लगता है जैसे Douglas Adams, SICP पढ़ा रहे हों

  • ये पक्षी वाले नाम Smullyan की 『To Mock a Mockingbird』 से आए हैं। उसमें और भी ज़्यादा पक्षी आते हैं

• “वह क्या… Y combinator है?”
  “हाँ। recursion के लिए उसकी ज़रूरत होती है.”
  मज़ेदार तथ्य: fixed-point combinator अनंत संख्या में हैं। यानी Y combinator के बिना भी recursion को implement करने के अनंत तरीके हैं