मैं साइमन पेटन जोन्स, एट अल द्वारा लिखे गए पेपर को पढ़ रहा था। नाम “Playing by the Rules: Rewriting as a practical optimization technique in GHC”। दूसरे खंड में, अर्थात् “ मूल विचार ” वे लिखते हैं:जीएचसी में एक व्यावहारिक अनुकूलन तकनीक के रूप में पुनर्लेखन: क्या इसकी वास्तव में आवश्यकता है?
पर विचार परिचित
mapसमारोह, एक सूची के प्रत्येक तत्व के लिए एक समारोह लागू होता है। हास्केल में लिखा,mapइस तरह दिखता है:
map f [] = []
map f (x:xs) = f x : map f xs
अब मान लें कि संकलक का सामना करना पड़ता
mapके निम्नलिखित कॉल:
map f (map g xs)
हम जानते हैं कि यह अभिव्यक्ति बराबर है
map (f . g) xs
(जहां “। ” फ़ंक्शन संरचना है), और हम जानते हैं कि बाद की अभिव्यक्ति पूर्व की तुलना में अधिक कुशल है क्योंकि कोई मध्यवर्ती सूची नहीं है। लेकिन संकलक के पास ऐसा कोई ज्ञान नहीं है।
एक संभावित पुनर्जन्म यह है कि संकलक स्मार्ट होना चाहिए --- लेकिन प्रोग्रामर हमेशा उन चीजों को जानता होगा जो संकलक नहीं समझ सकते हैं। एक और सुझाव यह है: प्रोग्रामर को ऐसे ज्ञान को सीधे संकलक को संवाद करने की अनुमति दें। यही वह दिशा है जिसे हम यहां खोजते हैं।
मेरा सवाल है, हम कंपाइलर को स्मार्ट क्यों नहीं बना सकते? लेखकों का कहना है कि “ लेकिन प्रोग्रामर हमेशा उन चीजों को जानता होगा जो संकलक ” को नहीं समझ सकते हैं।
map f (map g xs)
map g xsmap f [] = []साथ सम्मिलित है: हालांकि, वह एक मान्य जवाब क्योंकि संकलक वास्तव में पता लगा सकते हैं किmap f (map g xs)map (f . g) xsके बराबर है नहीं है, और यहाँ कैसे है।इसलिए
map g [] = []।map f (map g []) = map f []।map f []map f [] = []के साथ एकीकृत करता है।इसलिए
map f (map g []) = []।map g xsmap f (x:xs) = f x : map f xsके साथ एकीकृत करता है।इसलिए
map g (x:xs) = g x : map g xs।map f (map g (x:xs)) = map f (g x : map g xs)।map f (g x : map g xs)map f (x:xs) = f x : map f xsके साथ एकीकृत करता है।इसलिए
map f (map g (x:xs)) = f (g x) : map f (map g xs)।
इसलिए हम अब नियम है:
map f (map g []) = []
map f (map g (x:xs)) = f (g x) : map f (map g xs)
आप देख सकते हैं f (g x) सिर्फ (f . g) और map f (map g xs) रिकर्सिवली बुलाया जा रहा है। यह वास्तव में map (f . g) xs की परिभाषा है। इस स्वचालित रूपांतरण के लिए एल्गोरिदम बहुत सरल लगता है। तो फिर से लिखने के नियमों के बजाय इसे लागू क्यों नहीं करें?
यह उपयोगी होगा अगर आप मुझे एक ठोस उदाहरण दिखा सकें नियमों को फिर से लिखना बेहतर है। –
क्या आपने स्ट्रीम फ़्यूज़न पर लिंक किए गए पेपर को देखा था? –