- K programming में REPL पर प्रयोग किए गए code को script में ले जाया जाता है, और बड़े imperative pattern को लगातार छोटे declarative array pattern में घटाने पर ध्यान दिया जाता है
ngn/kscript, REPL input की तरह line-by-line चलती है, और\l file.kसे saved data और functions को REPL में load किया जा सकता है- Wikipedia-शैली के triple-loop matrix multiplication को ज्यों-का-त्यों ले आने पर global variables, nested loops, और mutation बहुत बढ़ जाते हैं, जो K की ताकत के खिलाफ जाता है
- सुधार की प्रक्रिया
+/fold,'each,/:eachright,\:eachleft, transpose हटाने, और tacit conversion से गुजरते हुएmatmul: {x{+/x*y}\:y}सेmatmul: (+/*)\:तक सघन हो जाती है - matrix multiplication का उदाहरण दिखाता है कि K में दक्षता code condensation process को बार-बार दोहराते हुए जटिल प्रक्रियाओं को अधिक पढ़ने योग्य array expression में बदलने में है
REPL-केंद्रित K development flow
- पूरा source code GitHub के
matmul.kमें देखा जा सकता है - K programming का ज़्यादातर काम REPL में होता है, जहाँ पिछले code के ऊपर तेज़ी से प्रयोग और सुधार करना आसान होता है
ngn/kऔरrlfeका संयोजन up/down arrow history को support करता है, इसलिए बड़े K program विकसित करने के लिए काफ़ी है- function को पहले REPL में test करना और फिर उसे actual code में ले जाना एक स्वाभाविक flow है
ngn/kकी prettyprinting हमेशा valid K data लौटाती है, इसलिए कुछ values पहले से compute करके program की speed बढ़ाई जा सकती है
K script execution model
- K script वैसे चलती है जैसे REPL में input दिया गया हो
- हर line क्रम से execute होती है
- अगर line semicolon पर खत्म नहीं होती, तो return value print होती है
- script multi-line definitions की अनुमति देती है, जिससे readability बेहतर होती है
- saved data और functions को REPL में इस्तेमाल करने के लिए
\l file.kचलाया जाता है- file execute होती है
- file का data load होता है
- एक ही file को कई बार load करने पर पुराना data overwrite हो जाता है
\से मिलने वाली REPL help में और commands देखे जा सकते हैं
Array language में pattern को घटाने का तरीका
- K और array programming, pattern को लगातार सरल बनाने की प्रक्रिया है
- बड़े और संभालने में कठिन pattern को छोटे, declarative, और अधिक readable रूप में घटाने के एक से ज़्यादा तरीके हो सकते हैं
- संबंधित चर्चा Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17 में विस्तार से देखी जा सकती है
- आम शुरुआत यह होती है कि GeeksforGeeks या Wikipedia के किसी प्रसिद्ध algorithm को K में translate करने की कोशिश की जाए
- उदाहरण के लिए matrix multiplication का उपयोग किया गया है
जब imperative matrix multiplication को सीधे उठा लिया जाए
- Wikipedia का Matrix multiplication algorithm
i,j,kवाले triple loop औरsumaccumulation से matrixCको भरता है - इसे K में सीधे translate करने पर
A,B,n,m,p,C,i,j,k,sumजैसे बहुत से global values assign करने पड़ते हैं - यह code K को imperative language की तरह इस्तेमाल करता है, इसलिए K की design से अच्छी तरह मेल नहीं खाता
- समस्या को तीन बिंदुओं में समेटा जा सकता है
- global assignment बहुत अधिक है
- कई स्तर के nested loops बचे रहते हैं
- mutation बार-बार होती है
सबसे अंदर वाले loop से मोड़कर घटाना
- सबसे अंदर वाला loop
sumको 0 से initialize करता है,kपर iterate करता है, औरA[i;k]*B[k;j]को accumulate करता है - पहला सुधार यह है कि fold
/का उपयोग करके summation को+/में बदला जाएsumglobal हट जाता है- code
C[i;j]::+/...के रूप में व्यवस्थित हो जाता है
- इसके बाद
'each के array return करने वाले गुण का उपयोग करने परCको mutate किए बिना nested loop के return values को सीधे इस्तेमाल किया जा सकता है - इस चरण के बाद केवल mutation-रहित तीन loops बचते हैं, और मुख्य variables
i,j,kरह जाते हैं
k, j, i को हटाने की प्रक्रिया
- इन तीन variables की भूमिकाएँ इस प्रकार हैं
i,Aकी हर row को index करता हैj,Bकी हर column को index करता हैk,Aकी हर column औरBकी हर row को index करता है
k,Aकी हर row औरBकी हर column को pair करके multiply कराता है, इसलिए बीच वाले index को हटाकर direct matching की जा सकती है- इस चरण में एक loop और
mकी ज़रूरत खत्म हो जाती है
- इस चरण में एक loop और
jको हटाने के लिएBकी हर column लाकर उसेA[i]के साथ pair करना होता हैBको transpose करके eachright/:से हर element pair किया जाता है
iको भी इसी तरह हटाया जा सकता है- eachleft
\:का उपयोग करAकी हर row औरBकी हर column को pair किया जाता है
- eachleft
- इस प्रक्रिया के बाद, बिना globals के यह रूप मिलता है
matmul: {x{+/x*y}/:\:+y}
Transpose हटाना और अंतिम tacit रूप
+transpose की लागत अधिक हो सकती है, इसलिए इसे हटाया जा सकता है- मौजूदा तरीका
xकी हर row औरyकी हर column को multiply करने वाला naive method है - इसके बजाय,
Bकी हर row को पूरेAपर फिट किया जाए तो वही काम implicit रूप से किया जा सकता है
matmul: {x{+/x*y}\:y}
- इस function को Chapter 3 के नियम लागू करके tacit form में बदला जा सकता है
- अंतिम परिणाम इस प्रकार है
matmul: (+/*)\:
अभ्यास से बनने वाली array language intuition
matmul: (+/*)\:K-शैली के matrix multiplication function के रूप में व्यवस्थित हो जाता है- condensation process शुरुआत में कई चरणों वाली लग सकती है
- K का अभ्यास बढ़ने पर code condensation अधिक आसान और intuitive काम बन जाती है
- matrix multiplication, K के array support के साथ अच्छी तरह मेल खाने वाली सरल प्रक्रिया है
- आगे के अध्यायों में ऐसे algorithms पर चर्चा होगी जो K के साथ स्वाभाविक रूप से फिट नहीं बैठते, और उन्हें कैसे संभालना है
1 टिप्पणियां
Hacker News की राय
असल में array languages की संभावना सबसे भरोसेमंद तरीके से दिखाने वाली चीज़ Aaron Hsu का वह वीडियो था, जिसमें वे parallel APL compiler Co-dfns विकसित करने की प्रक्रिया समझाते हैं: https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
उन्होंने HN पर arcfide नाम से semantic density के बारे में भी कई बार लिखा है, और समझाया है कि APL code को इस तरह डिजाइन किया जाता है कि एक ही screen में, लगभग बिना इधर-उधर गए, उसका व्यवहार, आसपास का context और dependencies देखे जा सकें: https://news.ycombinator.com/item?id=13571159
उनका नजरिया यह है कि जब संक्षिप्तता इतनी बढ़ जाए कि algorithm का नाम ही algorithm को विस्तार से लिखने जितनी लंबाई का लगने लगे, तो आप code को अंग्रेज़ी phrases पढ़ने की तरह idiom-level पर पढ़ने लगते हैं, और reusable abstractions बनाने की बजाय screen पर दिख रहे सभी use sites को सीधे बदलना ज्यादा तेज़ हो सकता है
अगर आप array programming से परिचित नहीं हैं, तो शुरुआत के लिए The Array Cast की सिफारिश करूंगा: https://www.arraycast.com/episodes/
RSS पता है https://www.arraycast.com/episodes?format=rss
map/filter/reduce अब लगभग हर जगह हैं, और लगा कि वे यह बात छोड़ रहे हैं कि इन्हें इस्तेमाल करने के लिए ideographic जैसी नई notation system सीखने की जरूरत नहीं है
70 के दशक में paper terminal पर असल overstriking इस्तेमाल करने वाले APL/APL2 से सामना हुआ और तुरंत उससे लगाव हो गया, लेकिन बाद में ML और Haskell के जरिए functional programming जानने के बाद एहसास हुआ कि APL में मुझे वास्तव में array से ज्यादा उसकी function composition क्षमता पसंद थी
Haskell इस मामले में कहीं बेहतर है, क्योंकि यह पूरी तरह pure है और types हर जगह लागू होते हैं; यह APL से ज्यादा मजेदार और शक्तिशाली लगा। मैंने कई छोटे और मध्यम आकार के projects बनाए, LLVM Flang के parser को parser combinator से implement किया जा सकता है यह दिखाने वाला prototype भी बनाया, और हर साल Advent of Code भी कुल मिलाकर कुछ सौ lines में हल करता हूं। अगर आपको APL पसंद है, तो Haskell भी आज़माने लायक है
अब APL का “सोचने के tool के रूप में notation” वाला पहलू मुझे अत्यधिक संक्षिप्तता को justify करने वाली बात जैसा लगता है। composition की ताकत दिखाने के लिए यह अच्छा है, लेकिन clarity को नुकसान भी पहुंचा सकता है
<=<पहले से है, औरfmapजैसा कुछ इस्तेमाल करें तो यह सचमुच बहुत अच्छा चलता है|||,+++,&&&,***भी अच्छे हैं, और UTF-8 operators खुद बनाकर उन्हें और छोटा व सुंदर बनाया जा सकता है। हालांकि अफसोस है कि वास्तविक काम या public serious Haskell code में इस तरह vertical screen space के अनुकूलता बहुत कम दिखती हैArray languages में “N से छोटे उन सभी numbers को खोजना जिनके लिए predicate P true है” जैसे problems को आम तौर पर कैसे handle किया जाता है, यह जानने की उत्सुकता है। उदाहरण के लिए 1000 से छोटे prime numbers खोजना या z के 1,000,000 से छोटे होने पर Pythagorean triples खोजना जैसी form
Imperative language हो तो loop में predicate check करेंगे, और functional language हो तो recursion या lazy list पर map/filter इस्तेमाल करेंगे, लेकिन array languages में मैं इसे आम तौर पर ऐसे समझता हूं कि
1..Narray बनाते हैं, predicate apply करके mask array बनाते हैं, फिर उस mask से original array को filter करते हैंअगर N 1 अरब जैसा बड़ा हो और predicate बहुत कम true हो, तो
1..Narray और mask जैसे दो विशाल temporary arrays बनाना memory और resources के लिहाज से बहुत wasteful लगता है। जानना चाहता हूं कि क्या array languages ऐसे temporary arrays लगातार बनाकर slow हो जाती हैं, या implementation lazy evaluation जैसी किसी approach से optimize करती हैScalar languages में उलटा default एक बार में एक value process करना होता है, इसलिए वे उस potential parallelism को waste करती हैं जिसे array languages SIMD algorithms के रूप में इस्तेमाल करती हैं। यह भी सिर्फ इसलिए बड़ी समस्या नहीं दिखती क्योंकि मौजूदा स्थिति familiar है, और solution इसका भी blocking ही है
असल में array language अच्छी है या नहीं, यह problem पर depend करता है। ज्यादातर practical uses में performance बिल्कुल important नहीं होती, और k की reputation भी शायद k implementation खुद fast language होने से ज्यादा kdb के database के रूप में fast होने से आई है। फिर भी machine-specific detailed optimization के बजाय elegant array algorithms पर focus करने भर से हैरान करने वाली speed मिल सकती है: https://mlochbaum.github.io/BQN/implementation/versusc.html
एक और स्पष्ट तरीका है पूरे body को loop fusion करके temporary arrays बनने से रोकना। एक ज्यादा simple option input/output arrays को कुछ दर्जन KB के chunks में बांटकर unnecessary temporary memory usage को limit करना है, लेकिन मेरी जानकारी में कोई array language यह automatic नहीं करती, और किसी दिन CBQN में इसे आजमाना चाहता हूं। User इसे manually भी कर सकता है, और performance maximize करनी हो तो असल में अक्सर करना पड़ता है
!10000000जैसा 0 से दस मिलियन तक का iota वास्तविक दस मिलियन integers के array के रूप में बनाए बिना simple range की तरह handle करने वाला lazy structure हैबेशक कौन-सा operator इस्तेमाल करते हैं, इस पर depend करता है कि आखिर में वैसा array बन सकता है। साथ ही
+|xजैसे x को reverse करके first element लेने वाले pattern को सिर्फ last element लेने में बदलने जैसी optimization भी होती हैबेशक अलग तरीके से लिखकर इसे avoid किया जा सकता है, लेकिन ऐसे solutions लंबे और कम elegant हो सकते हैं। जिस APL dialect Kap पर मैं काम कर रहा हूं, वह result की जरूरत पड़ने तक computation defer करता है, ताकि intuitive तरीके से code लिखते हुए भी कई cases में discard होने वाले results compute न किए जाएं
Array languages, खासकर k, इस्तेमाल करते हुए मेरी सबसे बड़ी सीखें ये रहीं। Verbs algorithms होते हैं, और imperative/object-oriented languages में find, sort, group जैसे common algorithms को अक्सर खुद implement करना पड़ता है
Verbs या adverbs की sequence मेरे द्वारा इस्तेमाल की गई सबसे direct composition form थी, और composition आसान व natural है। Program statements और expressions का collection नहीं, बल्कि algorithms की composition जैसा दिखने लगता है
Arrays, maps, functions में domain और codomain की concepts को consistently handle करने से design choices सरल हो जाती हैं, और right-to-left evaluation होने पर code पढ़ते समय नजर इधर-उधर नहीं दौड़ानी पड़ती
Data को code में लाने के बजाय code को data तक भेजने का तरीका संभव और preferred है। ज्यादातर बड़े k projects comments हटाने पर network MTU, यानी 1540 bytes के अंदर आ जाते हैं। k के bonus के तौर पर views functional relationships को directly implement कर सकते हैं, और interpreter के जरिए hot code loading से “हमेशा” चलने वाली applications भी संभव हैं
Job interview preparation के लिए K language problems हल करने के बाद मेरी personal, biased और limited impression यह है कि language जानबूझकर obscure है। Puzzles और clever solutions के लिए अच्छी language है
लेकिन array languages और arrays में सोचने का तरीका सिखाने वाली चीज मेरे हिसाब से Python में NumPy arrays के साथ काम करने का अनुभव है
J को करीब 50 घंटे इस्तेमाल करने के experience से मुझे honestly लगा कि यह paradigm बहुत ज्यादा एक तरफ झुका हुआ है
हर problem को arrays की nesting के रूप में सोचना thinking tool के तौर पर मददगार है या नहीं, पता नहीं। अगर problem को अच्छी तरह capture करने वाले data structures freely बना सकें, तो algorithm वाला हिस्सा काफी सरल हो सकता है
APL/J/K इस्तेमाल करने के लिए मुझे लगता है आपको ज्यादा smart होना पड़ता है। ज्यादा flexible languages में जो approach तुरंत possible होती है, वह अक्सर यहां impossible होती है, इसलिए problem को transform करना पड़ता है और उस process में कहीं ज्यादा thinking लग सकती है
यह example K-based है, लेकिन एक और array language J भी है: http://jsoftware.com
J में
dot =: +/ . *,P =: 2 3 4,Q =: 1 0 2,P dot Qलिखने पर P और Q का dot product 10 return होता हैdot←+.×के रूप में लिखा जा सकता है। लेकिन अगर expanded notation किसी ठीक-ठाक छोटे नाम जितनी ही छोटी हो, तो नाम देने की जरूरत ही नहीं, और नाम के आसपास spaces भी डालने पड़ सकते हैंdot = (sum.) . zipWith (*),p = [2, 3, 4],q = [1, 0, 2],p `dot` qऐसे लिख सकते हैंमेरी नजर में फर्क बस इतना दिखता है कि
sumऔरzipWithमें नाम इस्तेमाल होते हैं, और lifting या structure transformation “magic” की तरह नहीं होतेdot::{+/x*y}से लिखा जाता है।P::[2 3 4],Q::[1 0 2],dot(P;Q)form हैउदाहरण देखकर समझ नहीं आ रहा कि इसका मतलब क्या है। क्या किसी भी तरह से performance बेहतर है?
matrix multiplication का syntax छोटा है, लेकिन ऐसा लगता है कि इसकी वजह यह है कि K भाषा कैसे काम करती है, इसके बारे में बहुत सारा built-in context दिमाग में रखना पड़ता है
array language को आज़माकर और paradigm समझ आने तक उससे खेलकर देखना worthwhile है। imperative code अक्सर array style में बेहतर तरीके से व्यक्त होता है, और लंबी, छोटी-छोटी details वाली functions कभी-कभी सिर्फ array operations से, या दूसरे styles के साथ मिलाकर, काफी simplify हो जाती हैं
Haskell में
(+) <$> Just 1 <*> Just 2औरdo x <- Just 1; y <- Just 2; Just (x + y)की तुलना करें, तो इस level की complexity पर मैं हमेशा पहला पसंद करूंगा। दूसरा ज़्यादा space लेता है, इसलिए लगता है कि कुछ ज़्यादा complex हो रहा हैअगर काम ज़्यादा complex हो, तो दूसरा form इस्तेमाल करने के बजाय मैं उसे छोटे functions में तोड़ना चाहूंगा ताकि पहले वाले का कोई variant समझ में आए। यह “कुछ beginners जल्दी पढ़ सकते हैं” को “beginners से ऊपर के लोग पढ़ सकते हैं” में बदलने वाला trade-off है
“कुछ beginners पढ़ सकते हैं” को optimize करने पर diminishing returns बहुत बड़े होते हैं, ऐसा मुझे लगता है; इसके बजाय लक्ष्य “beginners से ऊपर” या कुछ मामलों में “intermediate से ऊपर” लोगों के पढ़ सकने का रखता हूं
किसी भी language को इस्तेमाल करने के भी कई कारण होते हैं और न इस्तेमाल करने के भी। लेकिन मुख्य बात छोटी notation, relative clarity, या fast code में compile होने की क्षमता नहीं है, बल्कि यह है कि बाद में आने वाला programmer उस code को वास्तविक उपयोग के लिए modify और maintain कर पाएगा या नहीं
बहुत बार programmers अपनी leet skills दिखाना चाहते हैं और उन बेचारे लोगों के बारे में नहीं सोचते जिन्हें बाद में आकर वह code संभालना पड़ेगा। व्यवहार में बहुत सारा leet code लंबे समय तक support किए जा सकने वाली चीज़ पाने के लिए फेंकना या पूरी तरह दोबारा लिखना पड़ता है
यह समझने में मुझे लंबा समय लगा, और उसके बाद मैंने ऐसा clean, simple और understandable code लिखने की कोशिश की जिसे दूसरे लोग maintain कर सकें। फेंकने वाला code संगठन की basic infrastructure बनकर जम जाता है और अगली पीढ़ी के लिए समझ से बाहर चीज़ बन जाता है, ऐसा बहुत बार होता है