Julia Language
combinators

टिप्पणियों

द वाई या जेड कॉम्बिनेटर

यद्यपि जूलिया एक विशुद्ध रूप से कार्यात्मक भाषा नहीं है, लेकिन इसमें कार्यात्मक प्रोग्रामिंग के कई क्षेत्रों के लिए पूर्ण समर्थन है: प्रथम श्रेणी के कार्य , लेक्सिकल स्कोप और क्लोजर ।

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

Y(f) = (x -> f(x(x)))(x -> f(x(x)))

हालांकि, वाई-कॉम्बिनेटर, जेड-कॉम्बिनेटर के एक करीबी रिश्तेदार, वास्तव में काम करेंगे:

Z(f) = x -> f(Z(f), x)

यह कॉम्बिनेटर एक फ़ंक्शन लेता है और एक फ़ंक्शन देता है जिसे जब तर्क x साथ कहा जाता है, तो स्वयं और x पास हो जाता है। किसी फ़ंक्शन को स्वयं पारित करने के लिए यह उपयोगी क्यों होगा? यह वास्तव में फ़ंक्शन के नाम को संदर्भित किए बिना पुनरावृत्ति की अनुमति देता है!

fact(f, x) = x == 0 ? 1 : x * f(x)

इसलिए, Z(fact) इस फ़ंक्शन परिभाषा में दिखाई देने वाली कोई पुनरावृत्ति नहीं होने के बावजूद, फैक्टरियल फ़ंक्शन का पुनरावर्ती कार्यान्वयन बन जाता है। ( Z कॉम्बिनेटर की परिभाषा में पुनरावृत्ति स्पष्ट है, लेकिन यह एक उत्सुक भाषा में अपरिहार्य है।) हम यह सत्यापित कर सकते हैं कि हमारा कार्य वास्तव में काम करता है:

julia> Z(fact)(10)
3628800

इतना ही नहीं, लेकिन यह उतना ही तेज है जितना हम एक पुनरावर्ती कार्यान्वयन से उम्मीद कर सकते हैं। LLVM कोड दर्शाता है कि परिणाम एक पुरानी पुरानी शाखा में संकलित किया गया है, घटाना, कॉल करना और गुणा करना:

julia> @code_llvm Z(fact)(10)

define i64 @"julia_#1_70252"(i64) #0 {
top:
  %1 = icmp eq i64 %0, 0
  br i1 %1, label %L11, label %L8

L8:                                               ; preds = %top
  %2 = add i64 %0, -1
  %3 = call i64 @"julia_#1_70060"(i64 %2) #0
  %4 = mul i64 %3, %0
  br label %L11

L11:                                              ; preds = %top, %L8
  %"#temp#.0" = phi i64 [ %4, %L8 ], [ 1, %top ]
  ret i64 %"#temp#.0"
}

SKI संयोजक प्रणाली

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

लैम्बडा कैलकुलस से एक सीधा अनुवाद

const S = f -> g -> z -> f(z)(g(z))
const K = x -> y -> x
const I = x -> x

हम यूनिट टेस्टिंग सिस्टम का उपयोग करके पुष्टि कर सकते हैं, कि प्रत्येक कॉम्बीनेटर के पास अपेक्षित व्यवहार है।

I कॉम्बिनेटर को सत्यापित करना सबसे आसान है; इसे दिए गए मूल्य को अपरिवर्तित वापस करना चाहिए:

using Base.Test
@test I(1) === 1
@test I(I) === I
@test I(S) === S

के कॉम्बिनेटर भी काफी सीधा है: इसे अपना दूसरा तर्क छोड़ देना चाहिए।

@test K(1)(2) === 1
@test K(S)(I) === S

एस कॉम्बीनेटर सबसे जटिल है; इसके व्यवहार को पहले दो तर्कों को तीसरे तर्क पर लागू करने के रूप में संक्षेप किया जा सकता है, पहले परिणाम को दूसरे पर लागू किया जा सकता है। हम सबसे आसानी से एस कॉम्बिनेटर को इसके कुछ करी रूपों का परीक्षण करके देख सकते हैं। उदाहरण के लिए, S(K) अपना दूसरा तर्क लौटाना चाहिए और अपना पहला त्यागना चाहिए, जैसा कि हम देखते हैं:

@test S(K)(S)(K) === K
@test S(K)(S)(I) === I

S(I)(I) को अपने तर्क को स्वयं लागू करना चाहिए:

@test S(I)(I)(I) === I
@test S(I)(I)(K) === K(K)
@test S(I)(I)(S(I)) === S(I)(S(I))

S(K(S(I)))(K) अपने पहले के लिए दूसरा तर्क लागू करता है:

@test S(K(S(I)))(K)(I)(I) === I
@test S(K(S(I)))(K)(K)(S(K)) === S(K)(K)

ऊपर वर्णित I कॉम्बिनेटर का मानक Base जूलिया में एक नाम है: identity । इस प्रकार, हम निम्नलिखित परिभाषाओं को I की निम्नलिखित वैकल्पिक परिभाषा के साथ फिर से लिख सकते हैं:

const I = identity

एसकेआई संयोजक दिखा रहा है

ऊपर दिए गए दृष्टिकोण के साथ एक कमजोरी यह है कि हमारे कार्य उतने अच्छे नहीं दिखते हैं जितना हम चाहते हैं। क्या हम बदल सकते हैं?

julia> S
(::#3) (generic function with 1 method)

julia> K
(::#9) (generic function with 1 method)

julia> I
(::#13) (generic function with 1 method)

कुछ और जानकारीपूर्ण डिस्प्ले के साथ? इसका जवाब है हाँ! आइए, REPL को फिर से शुरू करें और इस बार परिभाषित करें कि प्रत्येक फ़ंक्शन को कैसे दिखाया जाए:

const S = f -> g -> z -> f(z)(g(z));
const K = x -> y -> x;
const I = x -> x;
for f in (:S, :K, :I)
    @eval Base.show(io::IO, ::typeof($f)) = print(io, $(string(f)))
    @eval Base.show(io::IO, ::MIME"text/plain", ::typeof($f)) = show(io, $f)
end

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

यह कार्यों को अच्छी तरह से प्रदर्शित करता है:

julia> S
S

julia> K
K

julia> I
I

हालाँकि, हम अभी भी समस्याओं में भागते हैं जब हम एक बंद को प्रदर्शित करने का प्रयास करते हैं:

julia> S(K)
(::#2) (generic function with 1 method)

यह प्रदर्शित करना अच्छा होगा कि S(K) । ऐसा करने के लिए, हमें इसका फायदा उठाना चाहिए कि बंदों के अपने अलग-अलग प्रकार हैं। हम typeof और टाइप फ़ील्ड के name फ़ील्ड के primary क्षेत्र का उपयोग करके, इन प्रकारों तक पहुँच सकते हैं और उनके माध्यम से तरीकों को जोड़ सकते हैं। REPL को फिर से पुनरारंभ करें; हम और बदलाव करेंगे:

const S = f -> g -> z -> f(z)(g(z));
const K = x -> y -> x;
const I = x -> x;
for f in (:S, :K, :I)
    @eval Base.show(io::IO, ::typeof($f)) = print(io, $(string(f)))
    @eval Base.show(io::IO, ::MIME"text/plain", ::typeof($f)) = show(io, $f)
end
Base.show(io::IO, s::typeof(S(I)).name.primary) = print(io, "S(", s.f, ')')
Base.show(io::IO, s::typeof(S(I)(I)).name.primary) =
    print(io, "S(", s.f, ')', '(', s.g, ')')
Base.show(io::IO, k::typeof(K(I)).name.primary) = print(io, "K(", k.x, ')')
Base.show(io::IO, ::MIME"text/plain", f::Union{
    typeof(S(I)).name.primary,
    typeof(S(I)(I)).name.primary,
    typeof(K(I)).name.primary
}) = show(io, f)

और अब, आख़िर में, चीजें हम जैसे चाहें उन्हें प्रदर्शित करें:

julia> S(K)
S(K)

julia> S(K)(I)
S(K)(I)

julia> K
K

julia> K(I)
K(I)

julia> K(I)(K)
I