लिटिल स्कीमर evens-केवल * & सह

Question

मैं समझ पेज 145.

यहाँ पर लिटिल स्कीमर के evens-only*&co उदाहरण के साथ हो रहा है कठिनाई हो रही हूँ कोड है:

(define evens-only*&co 
(lambda (l col) 
    (cond 
    ((null? l) 
    (col '() 1 0)) 
    ((atom? (car l)) 
    (cond 
     ((even? (car l)) 
     (evens-only*&co (cdr l) 
        (lambda (newl product sum) 
         (col (cons (car l) newl) 
          (opx (car l) product) 
          sum)))) 
     (else 
     (evens-only*&co (cdr l) 
        (lambda (newl product sum) 
         (col newl product (op+ (car l) sum))))))) 
    (else 
    (evens-only*&co (car l) 
        (lambda (newl product sum) 
        (evens-only*&co (cdr l) 
            (lambda (dnewl dproduct dsum) 
             (col (cons newl dnewl) 
              (opx product dproduct) 
              (op+ sum dsum)))))))))) 

प्रारंभिक col हो सकता है :

(define evens-results 
(lambda (newl product sum) 
    (cons sum (cons product newl)))) 

क्या मैं है नहीं मिल रहा है, l'((1) 2 3) के रूप में के साथ, यह फाइनल में तुरंत चला जाता है else(car l)(1) और (cdr l)(2 3) के रूप में। अच्छा, लेकिन , , dsumnewl, product, sum से मेरा दिमाग खाली हो गया है। अगर कोई मुझे स्टेपर चलाने के लिए ड्रैकेट या चेज़ स्कीम या एमआईटी-स्कीम को स्थापित करने के तरीके पर प्रशिक्षित कर सकता है तो यह भी सहायक होगा।

लेकिन शायद मैं बहुत जल्दी चमक रहा हूं। क्या कोई शुरुआती व्यक्ति इस बार जंगली निरंतरता को समझने के लिए पहली बार पढ़ रहा है?

Answer 1

मुझे यह खंड पहले पढ़ने पर उलझन में पाया गया, और केवल इसे जारी रखना शुरू हुआ जब मैं निरंतरता और निरंतरता-गुजरने वाली शैली (जो यह है) के बारे में कहीं और पढ़ता था।

जो कुछ आप पहले से प्राप्त कर रहे हैं उसे समझाने के जोखिम पर, मुझे यह देखने का एक तरीका है कि "कलेक्टर" या "निरंतरता" के बारे में सोचने के लिए फंक्शन के मूल्यों को वापस करने के लिए सामान्य तरीके को बदलना है। प्रोग्रामिंग की सामान्य शैली में, आप एक फ़ंक्शन कॉल करते हैं, एक मान प्राप्त करते हैं, और कॉलर में इसके साथ कुछ करते हैं। उदाहरण के लिए, मानक रिकर्सिव length फ़ंक्शन में गैर-खाली मामले के लिए (+ 1 (length (cdr list))) अभिव्यक्ति शामिल है। इसका मतलब है कि एक बार (length (cdr list)) एक मान देता है, जो गणना करता है उसके साथ होने वाली गणना की गणना होती है, जिसे हम (+ 1 [returned value]) के रूप में सोच सकते हैं। सामान्य प्रोग्रामिंग में, दुभाषिया इन लंबित गणनाओं का ट्रैक रखता है, जो "ढेर" होते हैं, जैसा कि आप पुस्तक के पहले अध्यायों में देख सकते हैं। उदाहरण के लिए, एक सूची की लंबाई की गणना करने के क्रम में हमारे पास "प्रतीक्षा कंप्यूटेशंस" का घोंसला है क्योंकि सूची लंबे समय तक गहराई से कई स्तर है।

निरंतरता-गुजर शैली में, बजाय एक समारोह बुला और का उपयोग कर लौटे बुला समारोह में परिणाम की, हम समारोह जब यह कॉल करने के लिए एक "निरंतरता" के साथ उपलब्ध कराने के द्वारा अपने मूल्य पैदा करता है कि क्या करना है बताओ। (यह एसिंक्रोनस जावास्क्रिप्ट प्रोग्रामिंग में कॉलबैक के साथ आपको क्या करना है, उदाहरण के लिए: result = someFunction(); लिखने के बजाय आप someFunction(function (result) { ... }) लिखते हैं, और result का उपयोग करने वाले सभी कोड कॉलबैक फ़ंक्शन के अंदर जाते हैं)।

यहां length निरंतरता-गुजरने वाली शैली में है, बस तुलना के लिए। मैंने निरंतरता पैरामीटर return कहा है, जो सुझाव देना चाहिए कि यह यहां कैसे कार्य करता है, लेकिन याद रखें कि यह किसी अन्य की तरह सामान्य योजना चर है। (अक्सर इस शैली में निरंतरता पैरामीटर k कहा जाता है)।

(define (length/k lis return) 
    (cond ((null? lis) (return 0)) 
     (else 
     (length/k (cdr lis) 
        (lambda (cdr-len) 
        (return (+ cdr-len 1))))))) 

an article on continuations by Little Schemer co-author Dan Friedman में इस तरह के कोड को पढ़ने के लिए एक सहायक युक्ति है। (पेज 8 पर शुरू होने वाली धारा II-5 देखें)।टीका, यहाँ क्या else खंड ऊपर का कहना है:

कल्पना करें कि आप (cdr lis) पर length/k बुला का परिणाम है, और फोन यह cdr-len, तो एक जोड़ सकते हैं और यह इसके अलावा अपने निरंतरता का परिणाम पारित (return) ।

ध्यान दें कि यह लगभग ठीक दुभाषिया समारोह के सामान्य संस्करण में (+ 1 (length (cdr lis))) का मूल्यांकन (सिवाय इसके कि यह मध्यवर्ती परिणाम (length (cdr lis)) करने के लिए एक नाम देने के लिए नहीं है में क्या करना है क्या है। चारों ओर उत्तीर्ण होकर निरंतरता या कॉलबैक हमने कंट्रोलर को ट्रैक रखने के बजाय नियंत्रण प्रवाह (और मध्यवर्ती मूल्यों के नाम) को स्पष्ट कर दिया है।

चलिए evens-only*&co में प्रत्येक खंड में इस विधि को लागू करते हैं। यह यहां थोड़ा जटिल है तथ्य यह है कि यह फ़ंक्शन तीन मानों के बजाय मूल्य बनाता है: विषम संख्याओं के साथ नेस्टेड सूची हटा दिया; यहां तक ​​कि संख्याओं का उत्पाद; और विषम संख्याओं का योग। यहाँ पहले खंड है, जहां (car l) सम संख्या होने के लिए जाना जाता है:

(evens-only*&co (cdr l) 
       (lambda (newl product sum) 
        (col (cons (car l) newl) 
         (opx (car l) product) 
         sum))) 

कल्पना कीजिए कि आप विषम संख्या को हटाने के परिणाम, गुणा evens है, और सूची के cdr से विषम संख्या जोड़ने, और उन्हें newl, product, और sum क्रमशः कॉल करें। cons सूची के प्रमुख newl पर (क्योंकि यह एक भी संख्या है, इसे परिणाम में जाना चाहिए); सूची के प्रमुख द्वारा product गुणा करें ( के बाद से हम शाम के उत्पाद की गणना कर रहे हैं); अकेले sum छोड़ें; और इन को अपने प्रतीक्षा निरंतरता col पर तीन मान पास करें।

यहाँ इस मामले में जहां सूची के सिर एक विषम संख्या है: जैसा कि पहले

(evens-only*&co (cdr l) 
       (lambda (newl product sum) 
        (col newl product (op+ (car l) sum)))) 

, लेकिन निरंतरता के लिए (यानी "वापसी" उन्हें) newl और product का एक ही मान पास, sum और सूची के प्रमुख के साथ, क्योंकि हम विषम संख्याओं को जोड़ रहे हैं।

और यहाँ पिछले एक है, जहां (car l) एक नेस्टेड सूची है, और जो थोड़ा डबल प्रत्यावर्तन द्वारा जटिल है:

(evens-only*&co (car l) 
       (lambda (newl product sum) 
        (evens-only*&co (cdr l) 
            (lambda (dnewl dproduct dsum) 
            (col (cons newl dnewl) 
             (opx product dproduct) 
             (op+ sum dsum)))))) 

कल्पना कीजिए कि आप, को हटाने संक्षेप और जोड़ने नंबरों से परिणाम हो (car l) में और इन newl, product, और sum पर कॉल करें; तो कल्पना करें कि आपके पास (cdr l), पर एक ही चीज़ करने से परिणाम हैं और उन्हें dnewl, dproduct और dsum पर कॉल करें।आपके प्रतीक्षा निरंतरता के लिए, cons आईएनजी newl और dnewl (क्योंकि हम सूचियों की सूची तैयार कर रहे हैं) द्वारा उत्पादित मान दें; product और dproduct एक साथ गुणा करना; और sum और dsum जोड़ना।

सूचना: - col, दूसरे शब्दों में हर बार जब हम एक पुनरावर्ती कॉल करते हैं, हम पुनरावर्ती कॉल, जो तर्क, l की वर्तमान मूल्यों "पर बंद" के लिए एक नया निरंतरता है, और बदले निरंतरता का निर्माण , आप निरंतरता की श्रृंखला के बारे में सोच सकते हैं जिसे हम रिकर्सन के दौरान और अधिक पारंपरिक रूप से लिखित कार्य के "कॉल स्टैक" मॉडलिंग के रूप में बनाते हैं!

आशा है कि आपके प्रश्न का उत्तर दें। अगर मैं थोड़ा ओवरबोर्ड चला गया हूं, तो केवल इसलिए कि मैंने सोचा था कि, खुद को रिकर्सन के बाद, निरंतरता दूसरे वास्तव में साफ, दिमाग-विस्तार विचार में लिटिल शेमर और सामान्य रूप से प्रोग्रामिंग है।

Answer 2

मैं प्रोग्राम कैसे डिजाइन कर रहा हूं (felleisen et.al.) पढ़ रहा हूं। मैं उस अनुभाग से गुजर रहा हूं जहां उन्होंने स्थानीय परिभाषाओं को परिभाषित किया है। मैंने एक कोड लिखा है जो उपरोक्त शाम को केवल & सह स्थानीय परिभाषा का उपयोग करके लागू करता है। यहाँ मैं क्या लिखा है:

(define (evens-only&co l) 
    (local ((define (processing-func sum prod evlst lst) 
      (cond ((null? lst) (cons sum (cons prod evlst))) 
        ((atom? (car lst)) 
        (cond ((even? (car lst)) (processing-func sum (* prod (car lst)) (append evlst (list (car lst))) (cdr lst))) 
         (else 
          (processing-func (+ sum (car lst)) prod evlst (cdr lst))))) 
        (else 
        (local ((define inner-lst (processing-func sum prod '() (car lst)))) 
        (processing-func (car inner-lst) (cadr inner-lst) (append evlst (list (cddr inner-lst))) (cdr lst))))))) 
    (processing-func 0 1 '() l))) 

परीक्षण के लिए, जब मैं प्रवेश (evens-केवल & सह '((9 1 2 8) 3 10 ((9 9) 7 6) 2)), यह रिटर्न' (38 1920 (2 8) 10 (() 6) 2) जैसा कि छोटे स्कीमर में अपेक्षित था। लेकिन, मेरा कोड एक शर्त में विफल रहता है: जब कोई संख्या भी नहीं होती है, तब भी शाम का उत्पाद अभी भी 1 के रूप में दिखाया जाता है। उदाहरण के लिए (यहां तक ​​कि केवल & सह '((9 1) 3 ((9 9) 7))) रिटर्न '(38 1() (()))। मुझे लगता है कि इसे सुधारने के लिए मुझे एक अतिरिक्त फ़ंक्शन की आवश्यकता होगी। @melwasul: यदि आप स्थानीय परिभाषा से परिचित नहीं हैं, तो इसे यहां पोस्ट करने के लिए खेद है। मेरा सुझाव है कि आप एचटीडीपी भी पढ़ लें। यह शुरुआती लोगों के लिए एक उत्कृष्ट किताब है। लेकिन जो लोग योजना में विशेषज्ञ हैं, वे कृपया मेरे कोड पर भी अपनी टिप्पणियां पोस्ट कर सकते हैं। क्या स्थानीय परिभाषा की मेरी समझ सही है?

Answer 3

answerJon O. अंतर्निहित अवधारणाओं की वास्तव में बहुत गहराई से स्पष्टीकरण है। हालांकि मेरे लिए (और उम्मीद है कि, कुछ अन्य लोगों के लिए भी), इस तरह की अवधारणाओं को समझना उनके दृश्य दृश्य होने पर बहुत आसान है।

तो, मैं डाल दिया है once I did for multirember&co करने के लिए दो प्रवाह चार्ट (समान तैयार, untangling जब l है क्या evens-only*&co

की कॉल के दौरान हो रहा है:

'((9 1 2 8) 3 10 ((9 9) 7 6) 2) 

और col है:

(define the-last-friend 
    (lambda (newl product sum) 
     (cons sum (cons product newl)) 
    ) 
) 

एक प्रवाह-चार्ट, को दर्शाता है कि चर अलग-अलग में कैसे संबंधित हैं प्रत्यावर्तन की erent कदम: दूसरा प्रवाह चार्ट, वास्तविक मान दिखा रहा है, पारित किया जा रहा:

मेरे आशा है, कि क्या यह उत्तर Jon's explanation above को एक सभ्य इसके अलावा हो जाएगा।

Answer 4

संतुलन संबंधी स्यूडोकोड (एक KRC तरह अंकन, कॉल (f x y), जहां यह स्पष्ट है के लिए f x y लेखन) में, यह

evens-only*&co l col 
    = col [] 1 0          , IF null? l 
    = evens-only*&co (cdr l) 
        (newl product sum => 
         col (cons (car l) newl) 
          (opx (car l) product) 
          sum)     , IF atom? (car l) && even? (car l) 
    = evens-only*&co (cdr l) 
        (newl product sum => 
         col newl product (op+ (car l) sum))  , IF atom? (car l) 
    = evens-only*&co (car l) 
        (anewl aproduct asum => 
         evens-only*&co (cdr l) 
             (dnewl dproduct dsum => 
              col (cons anewl dnewl) 
               (opx aproduct dproduct) 
               (op+ asum  dsum))) , OTHERWISE 

यह एक CPS कोड जो इनपुट नेस्ट सूची से सभी evens जमा करता है (यानी एक पेड़) पेड़ की संरचना को संरक्षित करते हुए, और सभी शाम के उत्पाद भी पाता है; गैर evens के लिए के रूप में, यह उन्हें सार:

• अगर l एक खाली सूची है, तीन बुनियादी (पहचान) मान तर्क कर्नल के रूप में पारित कर रहे हैं;

• अगर (car l) सम संख्या, प्रसंस्करण के परिणाम है (cdr l)newl, product और sum, और फिर वे col को तर्क के रूप में पारित कर रहे हैं, जबकि पहले दो consing   ⁄   साथ गुणा करके संवर्धित कर रहे हैं (car l) (यहां तक ​​कि संख्या);

• अगर (car l) एक परमाणु जो सम संख्या, प्रसंस्करण के परिणाम नहीं है (cdr l)newl, product और sum, और फिर वे तीसरे एक के साथ संक्षेप द्वारा संवर्धित साथ col को तर्क के रूप में पारित कर रहे हैं कर रहे हैं (car l) (गैर-संख्या संख्या परमाणु);

• अगर (car l) एक सूची, प्रसंस्करण के परिणाम है (car l)anewl, aproduct और asum, और फिर प्रसंस्करण के परिणाम हैं (cdr l)dnewl, dproduct और dsum, और फिर तीन संयुक्त परिणाम रहे हैं col पर तर्क के रूप में पारित किया गया।

[], 1 और आधार मामले की 0 सूचियों का monoids की पहचान तत्वों क्रमश: गुणन के तहत नंबर, और, इसके अलावा नीचे की संख्याओं को कर रहे हैं। इसका मतलब केवल विशेष मान है जो परिणाम में परिवर्तन नहीं करते हैं, जब इसमें संयुक्त होता है।

एक उदाहरण के रूप में, '((5) 2 3 4) (जो सवाल में उदाहरण के करीब है) के लिए, यह गणना

evens-only*&co [[5], 2, 3, 4] col 
= 
col (cons []     ; original structure w only the evens kept in, 
      (cons 2    ; for the car and the cdr parts 
       (cons 4 []))) 
    (opx 1      ; multiply the products of evens in the car and 
      (opx 2 (opx 4 1))) ; in the cdr parts 
    (op+ (op+ 5 0)    ; sum, for the non-evens 
      (op+ 3 0))  

---

my other answer की तरह (एक बहन सवाल का) बनाता है, यहाँ के लिए एक और रास्ता है इस बारे में, (गार्ड) के साथ एक गपशप मिलान स्यूडोकोड साथ:

evens-only*&co = g where 
    g [a, ...xs...] col 
     | pair? a = g a (la pa sa => 
         g xs (ld pd sd => 
             col [la, ...ld...] (* pa pd) (+ sa sd))) 
     | even? a = g xs (l p s => col [ a, ...l... ] (* a p)  s ) 
     | otherwise = g xs (l p s => col   l   p (+ a s) ) 
    g []   col =     col []    1   0 

अर्थव्यवस्था (और विविधता) की इस अंकन वास्तव में यह बनाता है सभी अधिक स्पष्ट, ईएएस को ier सिर्फ देखने के कार्यों और चर के लिए समान रूप में लंबे समय के नामों में से शब्द सलाद में खो जाने के बजाय, (lambda भाव में) सूची डेटा, खंड समूहों (cond भाव में की तरह), नाम बाइंडिंग के लिए वाक्यात्मक विभाजक के रूप में अतिभारित कोष्ठक के साथ और समारोह कॉल designators सभी देख बिल्कुल एक जैसे। एस-भाव अंकन तो जोड़-तोड़ करने में आसानी के लिए अनुकूल एक मशीन द्वारा की इसी एकरूपता (अर्थात तुतलाना के read और मैक्रो) क्या मानव यह की पठनीयता के लिए हानिकारक है।