सब कुछ एक फ़ंक्शन है: David Beazley और SICP लेक्चर पर एक समीक्षा

(ezzeriesa.notion.site)

2 पॉइंट द्वारा GN⁺ 2024-11-18 | 1 टिप्पणियां | WhatsApp पर शेयर करें

David Beazley और SICP लेक्चर पर समीक्षा: 1 हफ़्ते का अनुभव

2022 के अंत में David Beazley के SICP लेक्चर में भाग लेने का अपना अनुभव साझा किया गया है। कई मुफ़्त संसाधन उपलब्ध हैं, लेकिन Dave का लेक्चर खास विषयों को चुनकर उन्हें गहराई से समझाने की वजह से बेहद प्रभावी था।

शुरुआत

SICP लेक्चर Scheme भाषा में हुआ, और इसमें Python में एक सरल Scheme interpreter लागू करके बुनियादी अवधारणा substitution मॉडल को समझाया गया।

Scheme भाषा की बुनियाद

Primitive: मूल मान (जैसे integer)
Operator: +, -, *, / जैसे मूल operations को prefix notation में उपयोग करना
define: वेरिएबल परिभाषित करना

> (define x 2)  
> (+ x 3) ; 결과: 5

if: conditional statement
lambda: anonymous function परिभाषित करना

> ((lambda (x) (* x x)) 3) ; 결과: 9

Python में Scheme interpreter

Python का उपयोग करके Scheme कोड को evaluate करने वाला एक सरल interpreter लागू किया गया। मूल operations को Python functions के रूप में परिभाषित किया गया।

definitions = {  
    "+": lambda x, y: x + y,  
    "*": lambda x, y: x * y,  
}

उदाहरण:

> evaluate(("+", 2, 3)) # 결과: 5

इसमें define और lambda का implementation, साथ ही conditional if की handling भी शामिल थी।

substitution model

substitution model प्रोग्राम को समझने का एक सरल तरीका है, जिसमें variables को values से बदलते हुए प्रोग्राम को evaluate किया जाता है। लेकिन जब assignment शामिल होता है, तो यह मॉडल विफल हो जाता है।

State

substitution model के टूटने के उदाहरण के रूप में assignment को लिया जा सकता है। उदाहरण के लिए, बैंक खाते का balance मॉडल करते समय set! का उपयोग करके variable को update किया जाता है।

(define balance 100)  
  
(define (withdraw amount)  
  (set! balance (- balance amount))  
  balance)

इस स्थिति में substitution model पहले और बाद के balance state में अंतर नहीं कर पाता।

इसलिए Environment मॉडल की ज़रूरत पड़ती है। Variables environment के भीतर परिभाषित होते हैं, और हर procedure का अपना environment होता है।

Streams

state को मॉडल करने का एक और तरीका Streams है। Streams lazy evaluation के ज़रिए भविष्य के values को भी मॉडल कर सकते हैं।

infinite loop और evaluation order

evaluation order का अंतर: ज़्यादातर भाषाएँ applicative-order evaluation का उपयोग करती हैं, जिसमें arguments को पहले evaluate किया जाता है।

> (square (+ 1 2)) ; 결과: 9

लेकिन normal-order evaluation arguments की evaluation को तब तक टालता है जब तक उनकी वास्तव में ज़रूरत न हो। इससे infinite loop से बचा जा सकता है।

> (define (p) (p))  
> (define (test x y) (if (= x 0) 0 y))  
> (test 0 (p)) ; 정상 순서에서는 0 반환, 적용 순서에서는 무한 루프

lambda calculus और Church numerals

Church encoding के माध्यम से numbers को procedures के रूप में व्यक्त किया जा सकता है। यह functional programming की एक महत्वपूर्ण अवधारणा है।

(define (zero f) (lambda (x) x))  
(define (increment n) (lambda (f) (lambda (x) (f ((n f) x)))))

zero वह function है जो argument को जैसा है वैसा ही लौटाता है (identity function)।
increment function application को एक बार और लागू करता है।

उदाहरण

> ((zero (lambda (x) (+ x 1))) 0) ; 결과: 0  
> (((increment zero) (lambda (x) (+ x 1))) 0) ; 결과: 1

iteration vs recursion

Scheme for loop की जगह recursion का उपयोग करके दोहराए जाने वाले काम करता है।

recursion उदाहरण: factorial

(define (factorial n)  
  (if (= n 1)   
    1   
    (* n (factorial (- n 1)))))

यह recursive call stack का उपयोग करता है, इसलिए यह काफ़ी memory ले सकता है।

tail-call optimization

Scheme tail-call optimization के ज़रिए memory usage कम करता है। इसकी वजह से यह iterative process की तरह काम कर सकता है।

(define (factorial n)  
  (define (iter product counter)  
    (if (> counter n)  
        product  
        (iter (* product counter) (+ counter 1))))  
  (iter 1 1))

समापन

David Beazley का लेक्चर SICP की प्रमुख अवधारणाओं को चुनकर गहराई से कवर करता है। खास तौर पर यह functional programming, lambda calculus और evaluation order जैसे विभिन्न programming paradigms को समझने में मदद करता है।

Knuth का उद्धरण

अगर आप सिर्फ़ theory पढ़ रहे हैं, तो इसका मतलब है कि अब practical पहलुओं पर ध्यान देने का समय है; और अगर आप सिर्फ़ practice कर रहे हैं, तो इसका मतलब है कि अब theoretical पहलुओं पर ध्यान देने का समय है।

1 टिप्पणियां

GN⁺ 2024-11-18

Hacker News की राय

चेतावनी के तौर पर, SICP/Lisp/Scheme में गहराई से उतरने पर प्रोग्रामिंग के बारे में सोचने का तरीका बदल सकता है, और ऐसी बौद्धिक उत्तेजना हमेशा स्वागतयोग्य है
लेकिन उन विचारों को किसी object-oriented codebase पर जस का तस लागू करने से अक्सर उलटा असर पड़ता है या टीम के सदस्यों की नाराज़गी मोल लेनी पड़ती है
उदाहरण के लिए, Lisp के बाद हर for loop को forEach में बदलने या हर चीज़ को map/reduce chain बनाने का मन हो सकता है, लेकिन अगर भाषा functional programming को पूरी तरह नहीं अपनाती, तो इससे readability और performance दोनों को नुकसान हो सकता है
आखिरकार, यह याद रखना कि mutable memory और CPU ही code को process करते हैं, ज़मीन से जोड़े रखता है; और आजकल Church numerals जैसे abstract concepts की तुलना में data-oriented design और hardware reality के अनुरूप “mechanical sympathy” रोज़मर्रा में ज़्यादा व्यावहारिक लगती है
- immutability को ज़्यादा सुरक्षित मानता/मानती हूँ
  side effects जितने कम हों, predictability उतनी ज़्यादा होती है, और object-oriented approach अक्सर वहाँ भी इस्तेमाल हो जाती है जहाँ केवल functions काफी होते हैं
  game development में calculations और risky code बहुत होते हैं, इसलिए object-oriented approach काफी अच्छी तरह फिट बैठती है, लेकिन web development में functional programming कहीं ज़्यादा natural है, और SaaS में Elixir जैसी भाषाएँ ज़्यादा reliable, कम bugs वाला और testing-friendly code लिखने में मदद करती हैं
- Common Lisp Object System जैसी चीज़ भी तो है
  ऊपर से forEach, map/reduce जैसी चीज़ें Smalltalk collections में पहले से थीं, और first-class syntax न सही, Object Pascal और C++ में भी copy की गई थीं
  underlying memory mutable होती है, इसलिए जब सच में ज़रूरत हो, तो ML-family languages में भी mutation संभालने के mechanisms होते हैं
- CPU control flow लागू करने का जो इकलौता तरीका अपनाता है, वह goto के काफ़ी करीब है, लेकिन goto Lisp से भी कम लोकप्रिय है
  और ज़्यादा अजीब बात यह है कि modern CPUs पर performance के लिए cache अनिवार्य है, फिर भी memory hierarchy को first-class citizen की तरह treat करने वाली भाषा अभी तक नहीं है
  सबसे करीब शायद Linux-style C दिखता है, जिसमें underscores का मानो समंदर भरा हो
pure functions से state encode करने का अच्छा introduction देता है
असल में trees, integers, sum/product types, images, monads वगैरह हर तरह के data के लिए pure functional encodings कहीं ज़्यादा हैं
encoding थोड़ी उलझाऊ हो सकती है, लेकिन साथ ही elegant और छोटी भी होती है
उदाहरण के लिए JavaScript में Maybe monad को functionally implement करें तो यह ऐसा होगा:
Nothing = nothing => just => nothing
Just = v => nothing => just => just(v)
pure = Just
bind = mx => f => mx(mx)(f)
evalMaybe = maybe => maybe("Nothing")(v => "Just " + v)
console.log(evalMaybe(bind(Nothing)(n => pure(n + 1)))) // Nothing
console.log(evalMaybe(bind(Just(42))(n => pure(n + 1)))) // Just 43
- ऐसी implementation उस type के recursion principle से derive की जा सकती है
  data Maybe a = Nothing | Just a
  foldMaybe :: (Unit -> r) -> (a -> r) -> Maybe a -> r
  foldMaybe को दिए जाने वाले दो higher-order functions क्रमशः Nothing और Just से मेल खाते हैं
  हालांकि Nothing वाले हिस्से में थोड़ा और सटीक होने के लिए Unit parameter जोड़ा गया रूप है
- इसे inductive type को उस type के recursor function type में बदलने के रूप में देखा जा सकता है
  type theory में यह काफी शानदार है, लेकिन practical programming के लिए उतना अच्छा नहीं है
- mathematically यह elegant हो सकता है, लेकिन जब इसे alignment या आंतरिक justification के बिना केवल ASCII character set वाली language के जरिए व्यक्त किया जाता है, तो देखने में काफी तकलीफ़देह होता है
- संक्षेप में, untyped lambda calculus Turing complete है
मैंने पहले असली SICP लेक्चर, यानी MIT OCW की 1986 की रिकॉर्डिंग देखी थी
इसकी अक्सर high information density के लिए तारीफ़ होती है, लेकिन असल में छात्रों के सवाल-जवाब, क्लासरूम में “multimedia” presentation की कोशिश पर instructor का ध्यान खींचने में गया समय, और पूरी lesson plan पहले से पूरी तरह व्यवस्थित न होने की वजह से सवाल-जवाब को पहले से रोक न पाने जैसी चीज़ों में काफ़ी समय बर्बाद होता है
ब्लैकबोर्ड पर लिखने में लगा समय भी जोड़ें तो अच्छा-खासा हो जाता है
बेशक material का क्रम जितना चाहें बहस करके बदला जा सकता है, और किसी दिन मैं अपनी समझ के हिसाब से इस content को समझाने वाली video series खुद बनाने की योजना भी रखता हूँ
अच्छा लगता है कि यह lecture Python जैसी ज़्यादा modern language इस्तेमाल करते हुए भी अपनी जड़ों को बनाए रखता है, और Python एक practical multi-paradigm language है, इसलिए भले ही यह पूरी तरह pure न हो, मुझे लगता है कि लोग functional idioms के ज़रिए मिलने वाली expressiveness को पर्याप्त मान्यता नहीं देते
- यह lecture पहले Python में Scheme implement करता है, फिर Scheme में दोबारा Scheme implement करता है
  मेरे हिसाब से Python को इस lecture से हटाया जा सकता है और हटाना चाहिए
  Python में functional programming support बहुत कमज़ोर है
  lists cons-based नहीं हैं, lambdas पर बहुत restrictions हैं, pattern matching भयानक है और expression-based भी नहीं है, namespaces भी अजीब हैं
  Python को modern language कहना भी मुश्किल है; यह 1990s में ही अटका है, और इसके पास ठीक-ठाक C-API है, इसलिए दुर्भाग्य से यह बेहतर languages की कीमत पर बढ़ा है
- Python की functional programming काफ़ी कमज़ोर है, और उस मामले में JavaScript उल्टा बेहतर लगता है
  tail call optimization न होने की वजह से कुछ code exercises के लिए Scheme से पूरी तरह अलग solutions चाहिए होते हैं
  अगर 1:1 translate किया गया code fail हो जाए, तो क्या instructor छात्रों से कहे कि चुनी हुई language की वजह से ऐसा हो रहा है, बस भरोसा कर लो, या फिर सब कुछ stack को externalize करने वाली problem मानकर उसी तरह solve करे—ऐसा लगता है
  SICP को Python में ज़बरदस्ती फिट करना काफ़ी मूर्खतापूर्ण लगता है
- ArsDigita University के lectures भी हैं
  साइट अभी offline है, लेकिन archive.org पर lectures देखे जा सकते हैं
  https://en.m.wikipedia.org/wiki/ArsDigita#ArsDigita_Foundati...
  https://archive.org/details/arsdigita_01_sicp/
  वे पूरे curriculum वाली USB key बेचते थे; अगर कोई ISO upload कर दे तो सच में अच्छा होगा
  https://web.archive.org/web/20190222145553/aduni.org/drives/
- Python और ज़्यादातर non-Lisp family languages की समस्या यह है कि वे programs को data की तरह handle करने को आसान नहीं बनातीं
  Scheme में जो चीज़ें सरलता से व्यक्त होती हैं, वे दूसरी languages में जटिल exercises बन जाती हैं
  छात्र underlying concepts पर ध्यान देने के बजाय implementation language की उन details पर ध्यान देने लगते हैं जिनकी Scheme में चिंता नहीं करनी पड़ती
जब पहली बार cons/car/cdr को lambdas से implement किया हुआ देखा, तो वह जादू जैसा लगा
हालांकि आखिरकार मुझे लगता है कि यह दिखाता है कि language runtime key/value dictionary implement कर रहा है, और उस implementation को उधार लेकर दूसरी data structures बनाई जा सकती हैं
- Elixir की destructuring logic कहीं ज़्यादा दिलचस्प है, और ES6 का कमजोर version कहीं ज़्यादा practical लगता है
  Elixir में आप शुरुआत से जितना चाहें उतना निकाल सकते हैं
- key/value dictionary नहीं, सिर्फ़ pointers चाहिए
  behavior के बिना closure बस closed variables की ओर pointer होता है, और 2 pointers वाला closure एक pair है जिससे car और cdr मिल सकते हैं
  runtime को pointed targets को definition के बाहर भी इस्तेमाल करने लायक बनाना पड़ता है, इसलिए escape analysis, garbage collection आदि चाहिए, लेकिन dictionary नहीं चाहिए
हाल में theorem proving में यह concept मिला कि 0 != 1 जैसी चीज़ prove करने के लिए सिर्फ़ Church encoding काफ़ी नहीं है, inductive data types चाहिए
इससे जुड़ी बातें मैंने मोटे तौर पर यहाँ डाली हैं, और SICP पर एक अलग आलोचना भी साथ में है: https://intellec7.notion.site/Drinking-SICP-hatorade-and-why...
“सब कुछ बस function है” वाले viewpoint की सीमाओं को बेहतर समझना चाहता हूँ
- अगर inequalities के बारे में इस्तेमाल किए जा सकने वाले दूसरे concrete facts हों, तो लगता है 0 ≠ 1 prove किया जा सकता है
  f = g -> f x = g x theorem से infer करके right side पर inequality fact बना सकते हैं, और फिर उसका contrapositive ले सकते हैं
  यह बात सही लगती है कि Church numerals के बीच inequality को inequality के बारे में दूसरे facts के बिना सीधे prove नहीं किया जा सकता
  दूसरी ओर, inductive data types में proof system एक ही inductive type के दो concrete instances से सबसे बाहरी constructor applications को recursively हटाते हुए equality या inequality को सीधे “observe” कर सकता है
- theorem proving के लिए Sigma types और Pi types, और किसी रूप में equality की अवधारणा चाहिए
  सोचता हूँ कि Scott encoding या Church encoding से यह हासिल किया जा सकता है या नहीं
- सुधारा हुआ link: https://goosetaco.notion.site/Drinking-SICP-hatorade-and-why...
किताब पर खुद यहाँ पहले से चर्चा चल रही है: https://news.ycombinator.com/item?id=42157558
सोच रहा हूँ कि link उस page की शुरुआत के बजाय नीचे वाली discussion पर क्यों जाता है
लगता है इस post को मौजूदा discussion में merge किया जा सकता है
David Beazley Python दुनिया में काफ़ी लीजेंडरी शख्सियत हैं, और यह लेक्चर शुरू में एक चौंकाने वाला आइडिया लगा, लेकिन करीब 2 सेकंड सोचने पर यह परफेक्ट कॉम्बिनेशन लगा, इसलिए अगले लेक्चर में रजिस्टर कर लिया
मुख्य बात यह है कि लगता है आगे software engineers की continuing education कुछ इसी रूप में दिखेगी
- अगर Chapter 5 की compilation को कवर नहीं किया, तो SICP का सबसे अच्छा हिस्सा कवर नहीं किया
“the substitution model” सेक्शन के कोड में typo है
("+", ("fib", ("-", "n", 2)), ("fib", ("-", "n", 1))),
परिभाषित चीज़ fibonacci है और fib परिभाषित नहीं है, इसलिए दोनों fib कॉल साफ़ तौर पर fibonacci होने चाहिए
असली GitHub repository में कोड सही है: https://github.com/savarin/pyscheme/blob/0f47292c8e5112425b5...
मुझे लगता है SICP शानदार है
हालांकि जितना ज़्यादा सीखा और गणित पढ़ा, उतना ही इस निष्कर्ष के करीब पहुंचा कि relations ज़्यादा बुनियादी primitive concept हैं
हर function को relation के सीमित रूप में व्यक्त किया जा सकता है, लेकिन उल्टा बिना काफ़ी अतिरिक्त machinery जोड़े सही नहीं होता
relational database और SQL relational programming के सबसे मशहूर और सफल उदाहरण ज़रूर हैं, लेकिन मुझे लगता है यह क्षेत्र अब भी बड़े पैमाने पर अनछुआ है
अभी मेरी रुचि programming language design से ज़्यादा बहुत छोटे बच्चों को गणित की बुनियाद सिखाने में है
अजीब बात है कि “बड़ा है” जैसे predicate को unary relation के रूप में, और “से बड़ा है” को binary relation के रूप में सिखाना, उसी concept को function के तौर पर पकड़ने की कोशिश से कहीं आसान है
“सब कुछ function है” वाला नजरिया बहुत ज़्यादा simplify किया हुआ है और अक्सर मददगार नहीं होता, इसलिए मुझे यह खास पसंद नहीं
उदाहरण के लिए, ऐसे functions हैं जो cache, RAM, disk वगैरह में फिट नहीं होते; ऐसे functions हैं जिनमें N-way JOIN या search/matching की तरह Big-O explode हो जाता है; और side effects वाले functions भी हैं, जिनमें non-idempotence शामिल है
function पर side-channel attacks के बारे में बहुत कम लोग सोचते हैं
date, time, duration वगैरह पर निर्भर non-deterministic functions भी होते हैं, और functions बीच में fail हो जाते हैं या gracefully fail भी नहीं करते
यह मान लेना भी मुश्किल है कि वे ऐसे resources consume नहीं करते जो shared resource pool इस्तेमाल करने वाले दूसरे “functions” को प्रभावित करते हों
function arguments मनचाहे बड़े या जटिल हो सकते हैं, लेकिन असल दुनिया में सीमाएं हैं, और तब pointers की जरूरत पड़ती है, फिर web या disk जैसे remote references की जरूरत पड़ती है
कब रुकना है बता दें तो अच्छा होगा, मैं बोलता ही जा सकता हूं
- ज़रूरत से ज़्यादा simplification कभी-कभी शानदार हो सकती है
  इस मामले में lambda calculus model “सब कुछ बस function है” approach की बुनियाद है, और यह बहुत सरल होने के साथ-साथ Turing machines आदि की तुलना में संभालने और reasoning करने में आसान है, इसलिए computation का अच्छा model है
  इसी वजह से यह अधिकांश computer logic और proof systems की बुनियाद में है
- उनमें से बहुत-सी चीज़ें functions के रूप में model की जा सकती हैं, और बस उन्हें वास्तव में उसी तरह लिखा जाना चाहिए
  अगर किसी function को resources चाहिए, तो उसे वे resources मांगने वाला बनाइए; अगर वह date/time पर निर्भर है, तो उसे date/time पर निर्भर बनाइए; अगर वह non-deterministic value लौटाता है, तो उसे non-deterministic value लौटाने वाला बनाइए
  functional programming approach के चमकने की एक वजह यह है कि यह आपको इन चीज़ों को गंभीरता से लेने पर मजबूर करती है
  अगर आप implicitly shared resource इस्तेमाल करना चाहते हैं, तो आपको उसे model करना होगा, और implicit shared resource पर निर्भर “function” को असली function से स्पष्ट रूप से अलग किया जाता है
- यहां जिन चीज़ों को function कहा गया है, उनमें से आधी असल में functions नहीं हैं, और functional programming दुनिया में भी कई लोग उन्हें function नहीं कहेंगे
  वे बल्कि procedures के करीब हैं
  function एक procedure है, लेकिन हर procedure function नहीं होता
- theoretical purpose के लिए मुझे लगता है कि वही एकमात्र उम्मीद है