संकलन समय पर व्याख्या, या C ++ 11 में लैम्ब्डा की वैकल्पिक समझ

HurrTheDurr से C ++ टेम्प्लेट पर गणना के बारे में एक और लेख हाल ही में Habré पर फिसल गया। व्यक्तिगत रूप से उसकी टिप्पणियों में, मैंने एक कॉल देखा:

> प्रत्येक नई रिलीज़ के साथ, आपके दिमाग को C ++ के साथ गैर-तुच्छ रूप से अलग करने के तरीकों की संख्या में वृद्धि जारी है)
उद्धरण 1 >> विशेष रूप से यदि आप खेल के मैदान के कार्यान्वयन के दृष्टिकोण को नहीं बदलते हैं और लगातार सभी गणनाओं को करने की कोशिश करना जारी रखते हैं, लेकिन प्रकारों पर नहीं।

लेकिन क्या ऐसे प्रकारों पर एक सार्वभौमिक कैलकुलेटर लिखना इतना मुश्किल होगा जो सेल्युलर ऑटोमेटन की तुलना में प्रोग्रामिंग के लिए अधिक सुविधाजनक हो? यह आसान हो गया; मैंने इस लेख पर कैलकुलेटर के वास्तविक कोड को लिखने और डिबग करने की तुलना में 30 गुना अधिक समय बिताया।

AveNat ने कुछ समय पहले दो हिस्सों में लैम्ब्डा कैलकुलस का एक परिचय प्रकाशित किया था, इसलिए प्रेरणा तुरंत आई। मैं इस तरह से (आलंकारिक रूप से) लिखना चाहता था:

#include <iostream> #include <LC/kernel.h> #include <LC/church_numerals.h> int main() { //      - typedef ChurchEncode<2> Two; // 2 = λfx.f (fx) typedef ChurchEncode<3> Three; // 3 = λfx.f (f (fx)) // * = λab.λf.a (bf) typedef Lambda<'a', Lambda<'b', Lambda<'f', Apply<Var<'a'>, Apply<Var<'b'>, Var<'f'> > > > > > Multiply; //  (* 2 3) typedef Eval<Apply<Apply<Multiply, Two>, Three>> Output; //    -    typedef ChurchDecode<Output> Result; std::cout << Result::value; } 

और आउटपुट है:

 ilammy@ferocity ~ $ gcc cpp.cpp ilammy@ferocity ~ $ ./a.out 6 

लेख थोड़ा बड़ा हो गया था, क्योंकि मैं उन सभी दिलचस्प चीजों के बारे में बात करना चाहता था जो यहां उपयोग की जाती हैं। और फिर भी इसे लैम्ब्डा कैलकुलस के बारे में ज्ञान के एक बुनियादी सेट की आवश्यकता है। उपरोक्त समीक्षाएं, C ++ का औसत ज्ञान (टेम्प्लेट के साथ), और सामान्य ज्ञान सामग्री को समझने के लिए पर्याप्त होना चाहिए।

कट के तहत एक और टाइपिंग लैम्ब्डा कैलकुलस के संकलन-समय दुभाषिया (मैक्रोज़ और रिकर्सियन के रूप में प्लस कुकीज़) के रूप में सी ++ टेम्पलेट्स की ट्यूरिंग पूर्णता का एक और टिप्पणी की गई रचनात्मक प्रमाण है।

(चूँकि C ++ 03 संकलक के लिए < असममित < कोणीय < कोष्ठक < खाका >>>>> में है, और ज्यादातर मामलों में मैं उनके स्वरूप से परेशान हूँ, या तो संकलन के लिए C ++ 11 समर्थन या sed ':l;s/>>/> >/g;tl' आवश्यक है। sed ':l;s/>>/> >/g;tl' मैक्रोज़ के बारे में भाग को छोड़कर, कोड C ++ 11. की किसी भी अन्य विशेषताओं का उपयोग नहीं करता है)

वाक्य-विन्यास

चलो चलते हैं। जैसा कि आप जानते हैं, लैम्ब्डा कैलकुलस में तीन प्रकार के शब्द होते हैं:

	चर संदर्भ	v - परिवर्तनशील नाम
	मतिहीनता	v - परिवर्तनशील नाम, B - पद
	पिपली	f और x शब्द हैं

इन सभी निर्माणों को C ++ टेम्प्लेट का उपयोग करके प्रस्तुत किया जाना चाहिए। टेम्प्लेट लैंग्वेज में वैल्यू टाइप होती हैं। इनमें से प्रत्येक प्रकार के घटकों के बारे में जानकारी होनी चाहिए। उन्हें घोषित करके, हम स्वयंसिद्धता का परिचय देते हैं "निम्नलिखित भाव मौजूद हैं":

 template <class Var> struct Ref; //  template <class Var, class Exp> struct Lam; //  template <class Fun, class Arg> struct App; //  

हालाँकि, लैम्ब्डा कैलकुलस में चर पूर्ण मान नहीं हैं। चर v अपने आप में कोई मतलब नहीं है, बिना अमूर्त के जो इसे किसी भी मूल्य से जोड़ता है। इसलिए, शब्द एक चर का संदर्भ है , चर का नहीं। इसलिए कार्यक्रम को लिखना आसान बनाकर परिभाषा को थोड़ा सरल बनाया जा सकता है:

 template <char Var> struct Ref; template <char Var, class Exp> struct Lam; template <class Fun, class Arg> struct App; 

हमने पूर्णांक मानों का उपयोग करके टेम्पलेट की क्षमता का लाभ उठाया। लेकिन तार मूल्यों को तार में भी लिखा जा सकता है, जो बहुत सुविधाजनक है: आपको कार्यक्रम में उपयोग किए गए प्रत्येक चर को पहले से घोषित करने की आवश्यकता नहीं है। इसी समय, यह स्पष्ट रूप से दिखाता है कि चर स्वयं मान नहीं हैं (अर्थात, C ++ प्रकार)।
अब हम टेम्प्लेट का उपयोग करके किसी भी लम्बे शब्द को रिकॉर्ड कर सकते हैं!

 typedef Lam<'f', App<Lam<'x', App<Ref<'f'>, App<Ref<'x'>, Ref<'x'>>>>, Lam<'x', App<Ref<'f'>, App<Ref<'x'>, Ref<'x'>>>>>> Y; 

आगे क्या है?

शब्दों को कैसे लिखना है, यह जानकर, आपको सीखना होगा कि उनकी गणना कैसे करें। यहां, सब कुछ पहले से ही इतना सरल नहीं है, इसलिए, हम टेम्पलेट्स पर नारकीय जादू लिखने के लिए एक काफी प्रसिद्ध दृष्टिकोण को लागू करते हैं: पहले कुछ घोषणात्मक प्रोग्रामिंग भाषा में सब कुछ लिखें, फिर केवल वाक्यविन्यास अंतर को ठीक करें। व्यक्तिगत रूप से, योजना मेरे करीब है, इसलिए मैं इसका उपयोग करूंगा। समान सफलता के साथ, आप हास्केल जैसी किसी भी अन्य कार्यात्मक भाषा को लागू कर सकते हैं। (बेहतर अभी तक, प्रोलॉग।)

हम पहिया को फिर से शब्दों को रिकॉर्ड करने के लिए प्रबलित नहीं करेंगे, लेकिन पारंपरिक सूचियों का उपयोग करेंगे:

 ; Y = λf.(λx.f (xx)) (λx.f (xx)) (define Y '(lambda (f) ((lambda (x) (f (xx))) (lambda (x) (f (xx))) ))) 

हम लैम्ब्डा कैलकुलस के सिंटैक्स को ठीक करते हैं:

 ;  —  , ,  . (define (term? exp) (or (ref? exp) (lam? exp) (app? exp)) ) ;   . (define (ref? exp) (symbol? exp)) ;  —     . (define (lam? exp) (and (list-of? 3 exp) ;   —   lambda. (eqv? 'lambda (first exp)) ;  —     . (list-of? 1 (second exp)) (symbol? (first (second exp))) ;   —  . (term? (third exp)) ) ) ;  —     . (define (app? exp) (and (list-of? 2 exp) (term? (first exp)) (term? (second exp)) ) ) 

इसके बाद, हम एक स्पष्ट फ़ंक्शन को परिभाषित करते हैं जो शब्दों की व्याख्या करेगा, उन्हें सिंटैक्स द्वारा अलग करेगा:

 (define (eval exp) (cond ((ref? exp) (eval-ref exp)) ((lam? exp) (eval-lam (first (second exp)) (third exp))) ((app? exp) (eval-app (first exp) (second exp))) (else (error "eval: syntax error" exp)) ) ) 

बहुत बढ़िया। लेकिन eval-ref कैसे लागू करें? दुभाषिया चर के मूल्य को कैसे जानता है? इसके लिए पर्यावरण जैसी चीज है । वातावरण में, चर और उनके मूल्यों के बीच संबंध संरक्षित हैं। इसलिए, eval वास्तव में इस तरह दिखता है - एक अतिरिक्त तर्क के साथ:

 (define (eval exp env) (cond ((ref? exp) (eval-ref exp env)) ((lam? exp) (eval-lam (first (second exp)) (third exp) env)) ((app? exp) (eval-app (first exp) (second exp) env)) (else (error "Syntax error" exp)) ) ) 

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

 (define (eval-ref var env) (lookup var env) ) 

अमूर्तता का मान एक तर्क का एक अनाम कार्य होना चाहिए। समय आने पर एप्लिकेशन इस फ़ंक्शन को कॉल करेगा। अमूर्तता का अर्थ है अपने शरीर के exp गणना ऐसे वातावरण में करना जहां अमूर्त चर var में तर्क arg पारित होने का मूल्य होता है। bind फंक्शन ऐसे माहौल बनाने का ध्यान रखेगा।

 (define (eval-lam var exp env) (lambda (arg) (eval exp (bind var arg env)) ) ) 

अन्य चर के मूल्य अलग-अलग हो सकते हैं, लेकिन यह विशेष रूप से लैम्ब्डा कैलकुलस में है कि वे उसी स्थान पर बने रहते हैं, जहां अमूर्त को परिभाषित किया गया था (अर्थात, उन्हें पर्यावरण env से लिया गया था)। मूल वातावरण को संरक्षित करने की क्षमता के कारण, ऐसे कार्यों को क्लोजर कहा जाता है।

अंत में, आवेदन arg तर्क के मूल्य के लिए अमूर्त fun के मूल्य को लागू कर रहा है।

 (define (eval-app fun arg env) ((eval fun env) (eval arg env)) ) 

यहां, अमूर्त और इसके तर्क की गणना पहले की जाती है, और फिर कॉल पहले से की जाती है। तदनुसार, eval आवेदन क्रम में लंबित शर्तों की कमी (मूल्य के आधार पर एक कॉल के साथ) करता है।

यह केवल पर्यावरण के साथ काम करने के लिए कुछ कार्यों को निर्धारित करने के लिए बनी हुई है। पर्यावरण में एक चर के मूल्य को खोजने और नए वातावरण बनाने के लिए bind करना:

 (define (bind var val env) ;     : (cons (cons var val) env) ) ; (bind 'x 1 '((y . 2))) ===> ((x . 1) (y . 1)) ; (lookup 'x '((x . 1) (y . 2))) ===> 1 (define (lookup var env) ; (lookup 'y '((x . 1) (y . 2))) ===> 2 (let ((cell (assq var env))) ; (lookup 'z '((x . 1) (y . 2))) ===> #<ERROR> (if cell (cdr cell) (error "lookup: unbound variable" var) ) ) ) 

सुपर! हमारे पास एक लंबो कैलकुलस दुभाषिया है जो शुद्ध कार्यात्मक शैली में लिखा गया है। ( संपूर्ण स्रोत ।) और यह भी काम करता है:

 (eval '((lambda (x) x) B) (bind 'B 42 '()) ) ; ===> 42 

लेकिन किस तरह के कोष्ठक? और C ++ का इससे क्या लेना-देना है?

योजना पर दुभाषिया के स्रोत कोड को देखते हुए, यह अनुमान लगाना अपेक्षाकृत आसान है कि C ++ टेम्प्लेट पर लैम्ब्डा शब्दों की व्याख्या कैसे की जाए। मैं आपको याद दिला दूं कि शब्द स्वयं निम्नलिखित पैटर्न में लिखे गए हैं:

 template <char Var> struct Ref; template <char Var, class Exp> struct Lam; template <class Fun, class Arg> struct App; 

टेम्पलेट फ़ंक्शंस (गलत वाले)

इंटरप्रेटर फ़ंक्शन को Eval कहा जाता है। चूंकि टेम्प्लेट में कोई फ़ंक्शन नहीं हैं, इसलिए हमें कुछ टेम्प्लेट के साथ करना होगा:

 template <class Exp, class Env> struct Eval; 

इस फ़ंक्शन का कॉल टेम्पलेट को त्वरित करना है: Eval<Exp, Env> । इस कॉल का रिटर्न मान C ++ प्रकार होना चाहिए। आइए सहमत हैं कि यदि Eval पारित तर्कों के लिए परिभाषित किया गया है, तो Eval अपने अंदर value प्रकार को परिभाषित करता है:

 typename Eval<Exp, Env>::value 

इस तरह के कोड से आप तर्क Exp और Env (प्रकार के value ) के साथ Eval कॉल का मूल्य प्राप्त कर सकते हैं। यदि कोई विशेष कॉल गलत है (इसका कोई मतलब नहीं है), तो value प्रकार परिभाषित नहीं किया जाएगा और हमें एक संकलन-समय त्रुटि मिलेगी। अन्य "टेम्पलेट फ़ंक्शंस" को एक समान तरीके से परिभाषित किया गया है।

मूल्यांकन और लागू करें

अब, टेम्प्लेट के आंशिक विशेषज्ञता के साथ, हम घोषित रूप से Eval के व्यवहार का वर्णन कर सकते हैं। उदाहरण के लिए, एक चर संदर्भ की गणना Lookup फ़ंक्शन का उपयोग करके वातावरण में एक चर के मूल्य के लिए एक खोज है (यह result माध्यम से मूल्य लौटाता है):

 template <char Var, class Env> struct Eval<Ref<Var>, Env> { typedef typename Lookup<Var, Env>::result value; }; 

अमूर्त गणना का परिणाम Closure टेम्पलेट प्रकार द्वारा दर्शाया गया Closure । एक क्लोजर (अनाम) फ़ंक्शन और इस फ़ंक्शन की परिभाषा का वातावरण संरक्षित करता है:

 template <char Var, class Exp, class Env> struct Eval<Lam<Var, Exp>, Env> { typedef Closure<Lam<Var, Exp>, Env> value; }; 

किसी अनुप्रयोग की गणना करने का परिणाम, गणना किए गए तर्क (गणना फ़ंक्शन द्वारा निष्पादित) के लिए गणना बंद कर रहा है:

 template <class Fun, class Arg, class Env> struct Eval<App<Fun, Arg>, Env> { typedef typename Apply<typename Eval<Fun, Env>::value, typename Eval<Arg, Env>::value>::result value; }; 

इस प्रकार, Eval केवल Ref , Lam , App (और दूसरे तर्क वाले वातावरण) के लिए परिभाषित किया गया है। अन्य तर्कों के साथ Eval कॉल बस संकलन नहीं करते हैं।

चलिए आगे बढ़ते हैं। क्लोजर केवल दुभाषिया डेटा संरचनाएं हैं जो दो मूल्यों (एक फ़ंक्शन और इसकी परिभाषा वातावरण) को संग्रहीत करती हैं। स्वाभाविक रूप से किसी अन्य टेम्पलेट द्वारा कार्यान्वित किया गया:

 template <class Abs, class Env> struct Closure; 

लैम्ब्डा कैलकुलस का पूरा बिंदु Apply फ़ंक्शन की परिभाषा में केंद्रित है। क्लोजर उनकी परिभाषा के वातावरण में गणना की जाती है, जो Bind गणना की गई फ़ंक्शन के तर्क को उसकी वास्तविक स्थिति में बांधकर बढ़ाता है:

 template <class Fun, class Arg> struct Apply; template <char Var, class Exp, class Env, class Arg> struct Apply<Closure<Lam<Var, Exp>, Env>, Arg> { typedef typename Eval<Exp, Bind<Var, Arg, Env>>::value result; }; 

(ध्यान दें कि, सिद्धांत रूप में, Apply जा सकता है किसी भी चीज के लिए सामान्य रूप से परिभाषित किया जा सकता है, न कि केवल अमूर्त आवेदन करने के लिए।

लुकअप और बिंद

यह पर्यावरण से निपटने के लिए बनी हुई है। शुरुआत के लिए, खाली वातावरण रखना अच्छा होगा:

 struct NullEnv; 

अगला, आपको Bind का उपयोग करके वातावरण के विस्तार के लिए एक तंत्र को लागू करने की आवश्यकता है। यह डेटा प्रकार एक नए वातावरण को परिभाषित करता है जिसमें Var वैरिएबल Val वैल्यू से जुड़ा होता है, और शेष वेरिएबल्स के मान Env एनवायरनमेंट द्वारा निर्धारित किए जाते हैं:

 template <char Var, class Val, class Env> struct Bind; 

हमें टेम्प्लेट पर एक प्रकार की लिंक्ड सूची मिली।

अंत में, हमें इस सूची में वांछित चर के मूल्य को खोजने में सक्षम होने की आवश्यकता है - यह सूची के पहले तत्व में उसी नाम के साथ होगा। खोज Lookup कार्य करता है:

 template <char Var, class Env> struct Lookup; 

खाली माहौल में कुछ नहीं होता। यदि वर्तमान परिवेश में वांछित मान है, तो इसे वापस लौटाएं। अन्यथा, हम पुनरावर्ती रूप से शेष पर्यावरण को देखते हैं:

 template <char Var> struct Lookup<Var, NullEnv>; template <char Var, class Val, class Env> struct Lookup<Var, Bind<Var, Val, Env>> { typedef Val result; }; template <char Var, char OtherVar, class Val, class Env> struct Lookup<Var, Bind<OtherVar, Val, Env>> { typedef typename Lookup<Var, Env>::result result; }; 

अंत

इसलिए, 50 लाइनों में, हमने C ++ टेम्प्लेट का उपयोग करके लैम्ब्डा कैलकुलस के सिंटैक्स और शब्दार्थ को पूरी तरह से निर्धारित किया है, जो C ++ टेम्प्लेट का विस्तार करने के लिए तंत्र की ट्यूरिंग पूर्णता साबित करता है (उपलब्ध स्मृति की असीमित मात्रा के अधीन)।

ट्यूरिंग मशीन की परिभाषा को समान मात्रा में लाइनों में निचोड़ा जा सकता है, लेकिन अधिक जटिल डिजाइन के कारण यह अभी भी अधिक क्रियाशील होगा। म्यू-पुनरावर्ती कार्यों की परिभाषा शायद कम होगी, लेकिन बहुत अधिक नहीं। मार्कोव एल्गोरिदम के कार्यान्वयन को देखना दिलचस्प होगा, लेकिन मुझे यह नहीं मिला, स्रोत कोड के आकार का अनुमान लगाना मुश्किल है, और आलस्य खुद को लिखना है।

ठीक है, चलो प्राप्त क्षमताओं ( पूर्ण कोड ) का उपयोग करके एक सरल गणना का प्रयास करें:

 /* ,   */ #include <iostream> int main() { // 1 = λfx.fx typedef Lam<'f', Lam<'x', App<Ref<'f'>, Ref<'x'>>>> One; // 2 = λfx.f (fx) typedef Lam<'f', Lam<'x', App<Ref<'f'>, App<Ref<'f'>, Ref<'x'>>>>> Two; // + = λab.λfx.af (bfx) typedef Lam<'a', Lam<'b', Lam<'f', Lam<'x', App<App<Ref<'a'>, Ref<'f'>>, App<App<Ref<'b'>, Ref<'f'>>, Ref<'x'>>> >>>> Plus; // Output := (+ 1 2) typedef Eval<App<App<Plus, One>, Two>, NullEnv>::value Output; // --...    ? Output::invalid_field; } 

 ilammy@ferocity ~/dev/tlc $ g++ -std=c++11 lc.cpp lc.cpp:   «int main()»: lc.cpp:79:5: :   «Output {aka Closure<Lam<'f', Lam<'x', App<App<Ref<'a'>, Ref<'f'> >, App<App<Ref<'b'>, Ref<'f'> >, Ref<'x'> > > > >, Bind<'b', Closure<Lam<'f', Lam<'x', App<Ref<'f'>, App<Ref<'f'>, Ref<'x'> > > > >, NullEnv>, Bind<'a', Closure<Lam<'f', Lam<'x', App<Ref<'f'>, Ref<'x'> > > >, NullEnv>, NullEnv> > >}»      Output::invalid_field; ^ 

कार्यक्रमों को निष्पादित करने का यह तरीका आम तौर पर बुरा नहीं है, लेकिन मैं इसे और अधिक आरामदायक बनाना चाहूंगा।

कई शब्दों का विस्तार

सबसे पहले, टेम्पलेट दुभाषिया की निकटता इसकी आंतरिक डेटा संरचनाएं हैं। केवल सी ++ प्रकार उनके अनुरूप हैं, लेकिन मूल्य नहीं। इंटरप्रेटर के अंदर उनके साथ काम करना आवश्यक है और इसे कभी भी टेम्पलेट तंत्र के ढांचे के बाहर नहीं ले जाना चाहिए। (इसलिए, उन्हें जानबूझकर प्रकारों द्वारा अपरिभाषित छोड़ दिया जाता है।)

दूसरे, यह स्पष्ट है कि यदि तर्कों को चर्च की संख्या के रूप में प्रस्तुत किया जाता है, तो उनके जोड़ का परिणाम भी चर्च संख्या होगा, दो तर्कों का एक फ़ंक्शन जो पहले तर्क एन को दूसरे एक एन बार पर लागू करता है। (इसलिए हम आउटपुट पर बिल्कुल बंद हो गए, जैसा कि जीसीसी आउटपुट कहता है।) लेकिन हमें इस फ़ंक्शन के साथ क्या करना चाहिए? वास्तव में, तर्कों के रूप में, हम केवल उसके लिए समान कार्य कर सकते हैं!

दरअसल, अब हमारा दुभाषिया केवल शुद्ध लंबो गणनाओं को समझता है, जिसमें केवल सार, अनुप्रयोग और चर (जो अमूर्त या अनुप्रयोगों को संदर्भित करते हैं) हैं। वाक्यविन्यास लैम्बडा शब्दों को विशेष रूप से इन तीन घटकों से बना देता है। इस नियम के किसी भी उल्लंघन के परिणामस्वरूप एक संकलन त्रुटि होगी।

गणना परिणामों को समझने में सक्षम होने के लिए, लागू लैम्ब्डा कैलकुलस का उपयोग करना आवश्यक है - इसमें शब्दों के सेट का विस्तार एक निश्चित विषय सेट के तत्वों द्वारा किया जाता है। हमारे मामले में, यह बहुत सारे C ++ डेटा प्रकार होंगे।

हम उनके लिए इसी शब्द का परिचय देते हैं:

 template <class T> struct Inj; 

यह लैम्ब्डा पथरी के कई शब्दों में टाइप T एक इंजेक्शन को दर्शाता है।

वाक्य-विन्यास का विस्तार करने के बाद, भाषा के शब्दार्थ को स्पष्ट करना आवश्यक है - Eval साथ यह निर्धारित करने के लिए कि नए वाक्य-विन्यास का अर्थ क्या है। खैर ... चूंकि T एक मनमाना मूल्य है, इसलिए Eval केवल यह जानता है कि ऐसा मूल्य मौजूद है। इस तरह की स्थितियों में एक फ़ंक्शन को दिया जा सकता है, इसका एकमात्र अर्थ पहचान है:

 template <class T, class Env> struct Eval<Inj<T>, Env> { typedef T value; }; 

अब हम संख्याओं (प्रकारों द्वारा दर्शाए गए) को तर्कों के रूप में पारित कर सकते हैं:

 struct Zero { static const unsigned int interpretation = 0; }; 

यह पता लगाना बाकी है कि फ़ंक्शन को कैसे पारित किया जाए, और हम चर्च संख्याओं को सामान्य int संख्या में बदल सकते हैं। आखिरकार, यदि आप वेतन वृद्धि फ़ंक्शन को शून्य एन बार पर लागू करते हैं, तो आप एक प्राकृतिक संख्या एन के साथ समाप्त हो जाएंगे।

कल्पना करें कि किसी तरह हम दुभाषिया के लिए Succ (उत्तराधिकारी) और Zero पास करके ऐसा करने में सक्षम थे। हम पता लगाएंगे कि जब ऐसा कोई फंक्शन होता है तो क्या होता है:

 Eval<App<Inj<Succ>, Inj<Zero>>, Env>::value Apply<Eval<Inj<Succ>, Env>, Eval<Inj<Zero>, Env>>::result Apply<Succ, Zero>::result 

बिंगो! Succ व्यवहार को निर्धारित करने के लिए, आपको इसके लिए Apply करने की आवश्यकता है! (ऐसे परिवर्तनों को डेल्टा नियम कहा जाता है ।)

उदाहरण के लिए, वेतन वृद्धि फ़ंक्शन को कैसे परिभाषित किया जाता है:

 struct Succ; template <class N> struct Apply<Succ, N> { typedef struct _ { static const unsigned int interpretation = N::interpretation + 1; } result; }; 

Apply होने का वापसी मूल्य result रूप में घोषित किया जाना चाहिए। इसलिए, वेतन वृद्धि एक डेटा प्रकार है जो संरचनात्मक रूप से ऊपर वर्णित Zero समान है। यह हमें गैर-मानक डेटा प्रकारों के रूप में प्राकृतिक संख्याओं का प्रतिनिधित्व करने की अनुमति देता है, जबकि इसी मूल्य के साथ एक नियमित int प्राप्त करने की क्षमता बनाए रखता है।

अब अंत में आप जोड़ का परिणाम प्रदर्शित कर सकते हैं! ( पूर्ण कोड ।)

 /* ,   */ #include <iostream> int main() { // 1 = λfx.fx typedef Lam<'f', Lam<'x', App<Ref<'f'>, Ref<'x'>>>> One; // 2 = λfx.f (fx) typedef Lam<'f', Lam<'x', App<Ref<'f'>, App<Ref<'f'>, Ref<'x'>>>>> Two; // + = λab.λfx.af (bfx) typedef Lam<'a', Lam<'b', Lam<'f', Lam<'x', App<App<Ref<'a'>, Ref<'f'>>, App<App<Ref<'b'>, Ref<'f'>>, Ref<'x'>>> >>>> Plus; // Sum = (+ 1 2) typedef App<App<Plus, One>, Two> Sum; // Result := (Sum +1 =0) typedef App<App<Sum, Inj<Succ>>, Inj<Zero>> Output; typedef Eval<Output, NullEnv>::value Result; std::cout << Result::interpretation; } 

 ilammy@ferocity ~/dev/tlc $ g++ -std=c++11 lc.cpp ilammy@ferocity ~/dev/tlc $ ./a.out 3 

वैश्विक पर्यावरण और मुक्त चर

मुझे लगता है कि आपने पहले ही ध्यान दिया है कि main() हम हमेशा खाली वातावरण के साथ Eval कहते हैं, और सभी आवश्यक सार "इनलाइन" हैं। लेकिन यह आवश्यक नहीं है। यदि आप पहले Eval कॉल के लिए कुछ वातावरण पास करते हैं, तो यह गणना की गई अवधि के लिए एक वैश्विक भूमिका निभाएगा: यह मुक्त चर के मूल्यों को निर्धारित करता है - जो लंबोदर सार के साथ जुड़ा नहीं है।

हालाँकि, कोई वातावरण में केवल एक प्रकार का फ़ंक्शन नहीं ले सकता है और न ही रख सकता है। वातावरण में मान होते हैं , इसलिए पहले उन्हें गणना करने की आवश्यकता है ( पूर्ण कोड ):

 /* ... */ #include <iostream> int main() { /*  One, Two, Plus  */ // Unchurch = λn.(n +1 =0),     int typedef Lam<'n', App<App<Ref<'n'>, Ref<'I'>>, Ref<'O'>>> Unchurch; // Result := (Unchurch (+ 1 2)) typedef Eval<App<Ref<'U'>, App<App<Ref<'+'>, Ref<'1'>>, Ref<'2'>>>, Bind<'+', typename Eval<Plus, NullEnv>::value, Bind<'1', typename Eval<One, NullEnv>::value, Bind<'2', typename Eval<Two, NullEnv>::value, Bind<'U', typename Eval<Unchurch, Bind<'I', Succ, Bind<'O', Zero, NullEnv>> >::value, NullEnv>>>> >::value Result; std::cout << Result::interpretation; } 

वातावरण दुभाषिया की स्मृति का प्रतिनिधित्व करता है। यदि यह एक लिंकर के साथ एक संकलक था, तो संकलित कार्यों को वहां झूठ बोलना होगा। दुभाषिया के मामले में, वे "पूर्व-परिकलित" स्थिति में हैं - पहले से ही Eval से गुजर चुके हैं।

एक और Unchurch जो ध्यान देने लायक है Unchurch है Unchurch मुफ्त चर। वे बिना किसी Inj आसपास के वातावरण में प्रवेश करते हैं। ऐसा इसलिए भी है क्योंकि दुभाषिया की स्मृति में इन मूल्यों को इस तरह से दर्शाया गया है। उन्हें केवल कार्यक्रमों के पाठ में लिखने के लिए आवश्यक है (लंबोदर शब्दों में)।

मैक्रो

किसी ने पर्याप्त रूप से नहीं लिया है कि कई तर्कों के कार्यों को लिखने के लिए उन्हें मैन्युअल रूप से क्यूरेट करने की आवश्यकता है? और ये सभी स्थिरांक Ref<'foo'> ?

और वैसे, लैम्ब्डा कैलकुलस में भी सुविधाजनक संक्षिप्ताक्षर स्वीकार किए जाते हैं:

को	के बाद

उसी को लागू करते हैं।

मैक्रोज़ को लागू करने के लिए कई दृष्टिकोण हैं। हमारे मामले के लिए, हमें सबसे सरल एक का चयन करना चाहिए: एक बाहरी प्रीप्रोसेसर। "बाहरी" का अर्थ है कि कार्यक्रम के बाहर स्थूल परिभाषाएँ संसाधित की जा रही हैं। यही है, हम इसके अंदर मैक्रोज़ को व्यक्त करने के लिए लैम्ब्डा कैलकुलस के लिए कोई नया वाक्यविन्यास पेश नहीं करेंगे; यह बहुत जटिल होगा। मैक्रोप्रोसेसर बस कार्यक्रम पर "गड्ढे" करता है और एक साफ लैंबडा शब्द का आउटपुट करता है - उसी तरह, उदाहरण के लिए, MOC Qt में काम करता है।

दो चरण

उस क्षण तक, हमारे कार्यक्रमों के जीवन में केवल एक महत्वपूर्ण घटना थी - Eval का उपयोग करके उनके मूल्य का निर्धारण। अब यह विस्तार के साथ अधिक मैक्रो विस्तार जोड़ देगा। Eval इनपुट को खिलाया जाने वाला सब कुछ पहले Expand माध्यम से पारित किया जाना चाहिए। हम एक नया सुविधाजनक Compute फ़ंक्शन पेश करते हैं जो इन क्रियाओं को जोड़ती है:

 template <class Exp> struct Expand; template <class Exp, class Env> struct Compute { typedef typename Eval<typename Expand<Exp>::result, Env>::value value; }; 

Expand केवल एक तर्क स्वीकार करता है। हम मानते हैं कि यह एक ब्लैक बॉक्स है: इनपुट पर, मैक्रोज़ के साथ एक कार्यक्रम, आउटपुट पर, उनके बिना। हमारे सरल मामले में, किसी भी मैक्रोइन्वायरमेंट की आवश्यकता नहीं है।

मैक्रो कार्यान्वयन

अब मैक्रों को स्पष्ट रूप से Expand अंदर लागू करने की आवश्यकता है। हमें कुछ Lam_ और App_ की आवश्यकता है, जिन्हें निम्नानुसार विस्तारित किया गया है:

को	के बाद
Lam_<'x', 'y', ..., 'z', B>	Lam<'x', Lam<'y', ..., Lam<'z', B>...>>
App_<A, B, C, ..., Z>	App<...App<App<A, B>, C>, ..., Z>
App_<'a', ...>	App_<Ref<'a'>, ...>

C ++ 11 में मनमाने ढंग से आने वाले पैटर्न दिखाई दिए हैं, जो कार्य को आसान बनाता है। C ++ 03 संकलक के मालिक केवल एक हजार और एक विशेषज्ञता को पीड़ित कर सकते हैं और लिख सकते हैं: दो तर्क के लिए Lam_3 , तीन के लिए App_4 , चार के लिए App_4 , आदि। ठीक है, या इससे भी अधिक विकृत करने के लिए और नीचे दिखाए गए सभी चीजों को दोहराएं। देशी सी ++ प्रीप्रोसेसर।

Lam_

सच है, यहां तक ​​कि सी ++ 11 टेम्पलेट्स की अपनी सीमाएं हैं, इसलिए वाक्यविन्यास को थोड़ा और दायर करना होगा।तर्कों का एक बंडल केवल टेम्पलेट का अंतिम तर्क हो सकता है, इसलिए आपको Lam_एक विशेष "तर्क धारक" दर्ज करने की आवश्यकता है:

 template <char... Vars> struct Args; template <class Args, class Exp> struct Lam_; template <char Var, class Exp> struct Expand<Lam_<Args<Var>, Exp>> { typedef typename Expand<Lam<Var, Exp>>::result result; }; template <char Var, char... Vars, class Exp> struct Expand<Lam_<Args<Var, Vars...>, Exp>> { typedef Lam<Var, typename Expand<Lam_<Args<Vars...>, Exp>>::result> result; }; 

Expandविस्तार प्रक्रिया के दौरान बार-बार कॉल पर ध्यान दें । वे आवश्यक हैं, क्योंकि Expand<...>::result यह हमेशा मैक्रोज़ के बिना एक शुद्ध लंबोदर शब्द होना चाहिए ।

App_

साथ ही, C ++ 11 टेम्पलेट एक बंडल में तर्क-संख्या और तर्क-प्रकार को मिलाने की अनुमति नहीं देते हैं, इसलिए App_दो संगत विकल्प होंगे। Pechalka।

कार्यान्वयन App_s(वर्णों के लिए) और App_i(प्रकार के लिए) अधिक मात्रा में हैं, इसलिए स्पॉइलर के तहत स्पष्टीकरण और कोड छिपे हुए हैं।अंततः, हम निम्नलिखित सरल परिभाषाएँ लिखते हैं। वे स्पॉइलर के तहत माना जाने वाले फ़ंक्शन को कॉल करते हैं जो सभी गंदे काम करते हैं, जिसके बाद वे खुद एक बार फिर से परिणाम चलाते हैं Expandताकि आउटपुट पर कोई अनसुलझी मैक्रोज़ न बचे।

 template <char... Exps> struct App_s; template <class... Exps> struct App_i; template <char... Exps> struct Expand<App_s<Exps...>> { typedef typename Expand< typename App_wrap<Nil, typename ToRefList_s<Exps...>::result >::result >::result result; }; template <class... Exps> struct Expand<App_i<Exps...>> { typedef typename Expand< typename App_wrap<Nil, typename ToRefList_i<Exps...>::result >::result >::result result; }; 

बाकी

और अंतिम लेकिन महत्वपूर्ण जोड़। विस्तारक को सही ढंग से अंतर्निहित भाषा निर्माण को संभालना चाहिए, मैक्रोज़ को उजागर करना जहां वे मिल सकते हैं:

 template <char Var> struct Expand<Ref<Var>> { typedef Ref<Var> result; }; template <char Var, class Exp> struct Expand<Lam<Var, Exp>> { typedef Lam<Var, typename Expand<Exp>::result> result; }; template <class Fun, class Arg> struct Expand<App<Fun, Arg>> { typedef App<typename Expand<Fun>::result, typename Expand<Arg>::result> result; }; 

जो अच्छी तरह से किया और उस काम में Expandसमानताएं देखा । ( पूर्ण मैक्रो समर्थन कोड ।)EvalApply

प्रत्यावर्तन

परिणामी कैलकुलेटर के ट्यूरिंग के अनुसार पूर्णता के बारे में कहा, हम किसी भी तरह एक पल को दरकिनार कर देते हैं, सरल अंकगणित से संतुष्ट होते हैं। आखिरकार, एक ट्यूरिंग-पूर्ण प्रणाली आपको चक्रों को व्यक्त करने की अनुमति देती है ! हम एक गुट के उदाहरण ( ड्रम रोल ) का उपयोग करके चक्रीय गणना पर विचार करते हैं ।

लैम्ब्डा कैलकुलस में, पुनरावृत्ति को सीधे व्यक्त नहीं किया जा सकता है, क्योंकि सार में नामों की कमी है। अपने सामान्य रूप में पुनरावृत्ति लिखने के लिए, आपको एक जादुई ऑपरेटर की आवश्यकता होती है जो Recएक सामान्य अमूर्तता के समान है Lam, लेकिन एक अतिरिक्त तर्क के साथ अमूर्त बनाता है - परिभाषित अमूर्त के लिए एक लिंक।

हालांकि, चालाक गणितज्ञों ने इस सीमा के आसपास एक रास्ता खोज लिया है: तथाकथित वाई-कॉम्बिनेटरनिश्चित बिंदुओं के बारे में कार्यात्मक समीकरणों के समाधान के रूप में पुनरावर्ती कार्यों को व्यक्त करने की अनुमति देता है। यह क्या है और पिछले वाक्य को कैसे समझा जाता है, आप कहीं और पढ़ सकते हैं, लेकिन अब यह महत्वपूर्ण है कि वाई-कॉम्बिनेटर को इस तरह लिखा जाए:

 // Y = λf.(λx.f (xx)) (λx.f (xx)) typedef Lam<'f', App<Lam<'x', App<Ref<'f'>, App_s<'x', 'x'>>>, Lam<'x', App<Ref<'f'>, App_s<'x', 'x'>>>>> Y; 

इसके साथ व्यक्त करने के लिए एक पुनरावर्ती कार्य जो एक भाज्य की गणना करता है, आपको सबसे पहले इसके लिए आवश्यक गणितीय और तार्किक ऑपरेटरों को निर्धारित करना होगा: गुणन, घटाव, तुलना। इसके अलावा, चर्च के नंबर लिखने का एक अधिक सुविधाजनक तरीका हस्तक्षेप नहीं करेगा। सभी परिभाषाएं यहां पाई जा सकती हैं (अंतिम चार खंड), वे लैम्ब्डा कैलकुलस में समान कार्यों की मानक परिभाषा हैं। (यदि आपने इस बिंदु को पढ़ने में महारत हासिल की है, तो उनके कार्यान्वयन को समझने में कोई समस्या नहीं होनी चाहिए।)

अंततः, सभी आवश्यक परिभाषाएं संबंधित वर्णों से जुड़ी हुई हैं और पर्यावरण में फिट होती हैं StandardLibrary। अब आप खूबसूरती से और आसानी से फैक्टरियल के लिए जनरेटिंग फंक्शन लिख सकते हैं :

 // F = λfn.if (= n 0) 1 // (* n (f (- n 1))) typedef Lam_<Args<'f', 'n'>, App_i<Ref<'?'>, App_s<'=', 'n', '0'>, Ref<'1'>, App_i<Ref<'*'>, Ref<'n'>, App_i<Ref<'f'>, App_s<'-', 'n', '1'>>> > > Fact_gen; 

यह सामान्य एक से भिन्न होता है जिसमें यह एक अतिरिक्त तर्क लेता है f- तथ्यात्मक गणना फ़ंक्शन (पहले से ही सामान्य)। वाई Combinator की भूमिका कि समारोह पैदा करने की है Fact_genएक समारोह को परिभाषित करने Factके लिए App<Fact_gen, Fact>≡ Fact- यह कहा जाता है "एक निश्चित बिंदु को खोजने के लिए।"

ठीक है, आइए इस सब को एक साथ लागू करने की कोशिश करते हैं, (YF 1) की गणना - इकाई के भाज्य:

 /* ... */ #include <iostream> int main() { /*  Y  Fact_gen */ typedef Compute<App<Ref<'U'>, App_i<Y, Fact_gen, MakeChurch(1)> >, StandardLibrary>::value Result; std::cout << Result::interpretation; } 

 ilammy@ferocity ~/dev/tlc $ g++ -std=c++11 lc.cpp 2>&1 | wc -c 64596 

संकलित नहीं। और 64 किलोबाइट त्रुटि लॉग। क्यों?

यह सब गणना का विषय है। सामान्य वाई-कॉम्बिनेटर गणना के सामान्य आदेश के आधार पर लिखा जाता है । इसमें, एक टुकड़ा f (xx)पहले (xx)शरीर में एक प्रतिस्थापन का कारण होगा f, और उसके बाद ही, यदि आवश्यक हो, तो मूल्य (xx)की गणना की जाएगी (आलसी प्रतिस्थापन के साथ भी)।

आवेदक आदेश के मामले में (मूल्य से कॉल), इस अभिव्यक्ति का तुरंत मूल्यांकन किया जाता है, जो स्पष्ट रूप से एक अनंत लूप की ओर जाता है (यदि आप यह देखते हैं कि तर्क x क्या होना चाहिए) के बराबर है। उदाहरण के लिए, स्कीम लैम्ब्डा कैलकुलस इंटरप्रेटर जो पहले दिखाया गया है, लूप किया गया है।

यदि आप gcc द्वारा लॉग थूक को डिक्रिप्ट करते हैं, तो यह कहता है कि:

 struct Apply< Closure< Lam<'x', App<Ref<'f'>, App<Ref<'x'>, Ref<'x'>>>>, Bind<'f', Closure<Fact_gen, StandardLibrary>, StandardLibrary > >, Closure< Lam<'x', App<Ref<'f'>, App<Ref<'x'>, Ref<'x'>>>>, Bind<'f', Closure<Fact_gen, StandardLibrary>, StandardLibrary > > > 

प्रकार का निर्धारण नहीं करता है result, अर्थात, इस कॉल का कोई मतलब नहीं है। संकलक ने अंतहीन पैटर्न प्रतिस्थापन चक्र को देखा और तोड़ दिया, जो मानक ( 14.7.1 / 15 ) द्वारा अपरिभाषित है ।

C ++ टेम्प्लेट्स एपेरेटिव ऑर्डर में गणना भी करते हैं, क्योंकि फंक्शन कॉल typename Eval<Exp, Env>::valueटेम्पलेट को इंस्टेंट करना है। एक Evalतात्कालिकता स्पष्ट रूप से एक उदाहरण की आवश्यकता है Expऔर Env।

गणनाओं के आवेदन के क्रम वाली भाषाओं में, आपको जेड-कॉम्बिनेटर का उपयोग करना चाहिए - वाई-कॉम्बिनेटर का एक संशोधन, जिसमें अभिव्यक्ति को (xx)एक अमूर्त में लपेटा जाता है, जो इसकी समयपूर्व गणना को रोकता है:

 // Z = λf.(λx.f (λy.xxy)) (λx.f (λy.xxy)) typedef Lam<'f', App<Lam<'x', App<Ref<'f'>, Lam<'y', App_s<'x', 'x', 'y'>>>>, Lam<'x', App<Ref<'f'>, Lam<'y', App_s<'x', 'x', 'y'>>>>>> Z; 

अब संकलन त्रुटियाँ दिखाई नहीं दे रही हैं, साथ ही साथ इसका अंत भी। जाहिर है, इस बार हमने कंपाइलर को पीछे छोड़ दिया और जबरदस्ती इसे दोबारा खोलने के लिए मजबूर किया। यह मान लेना उचित है कि यह केवल एक पुनरावर्ती तथ्यात्मक कॉल हो सकता है।

इसे रोको!और कंपाइलर को भी फैक्टरियल को खुद में बदलना कब बंद करना चाहिए? मेरा मतलब है, जब हम उसे ऐसा करने से रोकना चाहते हैं? सिद्धांत रूप में, इसके लिए ऑपरेटर जिम्मेदार है If: जब फैक्टरियल तर्क शून्य होता है, तो आपको एक को वापस करने की आवश्यकता होती है, और पुनरावर्ती कॉल करने का प्रयास नहीं करना चाहिए। और यह कैसे निर्धारित किया जाता है If?

 typedef Lam_<Args<'c', 't', 'f'>, App_s<'c', 't', 'f'>> If; 

एक अमूर्त की तरह। सब कुछ ठीक लगता है, चर्च बुलियन स्थिरांक के लिए मानक परिभाषा ... लेकिन यह केवल सामान्य कटौती के आदेश के लिए डिज़ाइन किया गया है! आवेदन के क्रम में, यह Ifशर्त के साथ एक साथ दोनों शाखाओं की गणना करता है, और उसके बाद ही एक विकल्प बनाता है।

समस्या को जेड-कॉम्बिनेटर के समान एक तरह से हल किया जा सकता है: लंबित गणनाओं को एक अमूर्त में लपेटें। हालांकि, Ifहालत के मामले में सिर्फ लपेटने की जरूरत नहीं है। इसलिए, दुर्भाग्य से, यदि आवेदक भाषाओं में एक सुविधाजनक कार्य नहीं हो सकता है। हालाँकि, इसे एक मैक्रो बनाया जा सकता है!

 template <class Cond, class Then, class Else> struct If; template <class Cond, class Then, class Else> struct Expand<If<Cond, Then, Else>> { typedef typename Expand< App_i<Cond, Lam<'u', Then>, Lam<'u', Else>, Lam<'u', Ref<'u'>> > >::result result; }; 

कड़ाई से बोलते हुए, चर 'u'को किसी भी मुफ्त चर के साथ मेल नहीं खाना चाहिए Thenया Else। हमारी मैक्रो प्रणाली ऐसा अवसर (स्वच्छता) प्रदान नहीं करती है। सामान्य तौर पर, हमारे पास बहुत सीमित संख्या में चर नाम हैं। इसलिए, हम पहचानकर्ता 0को गैर-मिलान पहचानकर्ता के रूप में आरक्षित करते हैं :

 template <char Var> struct Lookup<Var, NullEnv>; template <class Env> struct Lookup<0, Env>; template <char Var, class Val, class Env> struct Lookup<Var, Bind<Var, Val, Env>> { typedef Val result; }; 

अब, आखिरकार, फैक्टरियल काम करेगा। ( पूर्ण कोड ।)

 ilammy@ferocity ~/dev/tlc $ time g++ -std=c++11 lc.cpp -DARG=6 real 0m12.630s user 0m11.979s sys 0m0.466s ilammy@ferocity ~/dev/tlc $ ./a.out 720 

दुर्भाग्य से, मैं सात के तथ्य की गणना करने के लिए इंतजार नहीं कर सकता था, इस तथ्य का उल्लेख नहीं करने के लिए कि 32-बिट सिस्टम पर कंपाइलर बस स्टैक ओवरफ्लो से मर जाता है। लेकिन फिर भी! ..

निष्कर्ष

इस दुभाषिया से शायद कोई व्यावहारिक इंजीनियरिंग लाभ नहीं है, लेकिन विचार ही आनंदमय है। C ++ टेम्पलेट सैद्धांतिक कंप्यूटर विज्ञान में "गलती से ट्यूरिंग-पूर्ण" चीजों में से एक हैं। मेरे पास केवल यही भावना थी कि जब मुझे पता चला कि x86- प्रोसेसर का पृष्ठ प्रबंधन सबसिस्टम भी ट्यूरिंग-पूर्ण है। यदि यह दुभाषिया आपको एकल C ++ स्टेटमेंट को निष्पादित किए बिना गणना करने की अनुमति देता है, तो MMU आपको प्रोग्राम के एक मशीन निर्देश को निष्पादित किए बिना गणना करने की अनुमति देता है।

दुर्भाग्य से, मैंने केवल डीसीपीएल को आठवें अध्याय तक पढ़ा है , इसलिए टाइप किए हुए लंबो कैलकुलस के लिए दुभाषिया लिखना एक अभ्यास के रूप में पाठकों के लिए छोड़ दिया गया है। इसके लिए मेरे पास अभी भी बहुत कम गणितीय प्रशिक्षण है।

पीएस हर समय, जब मैं एक पोस्ट लिख रहा था, तो सोचा था कि मुझे नहीं छोड़ा: "यह या तो पहले से ही बूस्ट में है, या वहां तीन लाइनों में लिखा गया है।"