Y-Combinator مثال عملي

Question

ولقد كنت أقرأ قليلا في الآونة الأخيرة حول البرمجة الوظيفية واني اسعى الى جروك على Y-Combinator. وأنا أفهم أنه يمكنك استخدام Y-Combinator لتنفيذ العودية بشكل فعال في اللغة التي لا تدعم العودية مباشرة. ومع ذلك، كل لغة أنني من المحتمل أن تستخدم بالفعل تدعم العودية لذلك أنا لست متأكدا من مدى فائدة سيكون لاستخدام Y-Combinator لذلك.

هل هناك مثال أفضل العملي لاستخدام Y-Combinator أن أنا في عداد المفقودين؟ وقد أي شخص يستخدم في الواقع واحدة في رمز الإنتاج الحقيقي؟ أو باستخدام Y-Combinator في الحقيقة مجرد ممارسة أكاديمية العقل منحنية (وإن كان باردا جدا).

Answer 1

وانا ذاهب الى نختلف مع إجابات أخرى: <قوية> والنقطة الثابتة (Y) combinator <م> لا أن تكون لها تطبيقات عملية ، لكن ذلك يأخذ العقل الخيال جدا للعثور عليهم . مثل بروس ماك آدم. وهنا مجردة من ورقته ذلك عن الأغطية ذلك حتى :

<اقتباس فقرة>   

ويمكن التعبير عن combinator Y لحساب نقاط ثابتة في المعيار ML. في كثير من الأحيان يتم استخدامه كمثال على قوة المهام العليا، ولكن لا ينظر إليه عادة باعتباره البناء برمجة مفيد. هنا، ونحن ننظر كيف يمكن لتقنية البرمجة على أساس combinator Y ومغلفة يمكن أن تعطي المبرمجين على مستوى من السيطرة على الأعمال الداخلية من الوظائف غير ممكن إلا دون إعادة كتابة واعادة تجميع التعليمات البرمجية. على سبيل التجربة، ويتم تنفيذ خوارزمية W نوع الاستدلال باستخدام هذه التقنية، لذلك يتم إنتاج أن رسائل الخطأ مع الحد الأدنى من التدخل لالخوارزمية. رمز لهذا المثال البرنامج يوضح فائدة حقيقية للمفاهيم والسهولة التي يمكن تطبيقها. وتناقش عدد من تقنيات التنفيذ الأخرى والتطبيقات الممكنة أيضا، بما في ذلك استخدام وظائف العليا لمحاكاة استخدام الاستثناءات واستمرارا.

وانها ورقة الكبرى. وأي شخص مهتم في البرمجة الوظيفية ربما يتمتع قراءته.

Answer 2

هل يمكن أن تحقق في هذا المنصب أنيق على تنفيذ Y Combinator في C #: <لأ href = "http://blogs.msdn.com/madst/archive/2007/05/11/recursive-lambda-expressions.aspx "يختلط =" نوفولو noreferrer "> العودية لامبدا التعبير ، و قد تساعدك على فهم فكرة أفضل.

وأنت قد ترغب في التحقق من بعض المواد لطيفة على ويكيبيديا: الثابتة نقطة combinator و < وأ href = "http://en.wikipedia.org/wiki/Fixed-point_theorem#Fixed_point_theorems_in_discrete_mathematics_and_theoretical_computer_science" يختلط = "نوفولو noreferrer"> الثابتة نظريات النقطة

وكما يقول ناثان، ترتبط العديد من التقنيات الفنية لcombinator Y ومفيدة، حتى تبقى في ذلك! Y هو حقا مفيدة لأنه يتيح لك فهم التعليمات البرمجية بشكل أفضل، ولكن لا أعتقد أن هذا هو مفيدة بشكل خاص لوصف كيف أن يساعد.

Answer 3

ويمكنك التفكير في combinator باسم الجهاز الظاهري الذي يمتد وظيفة الخاص بك، والتي وصف بها غير متكررة وظيفية (= الوظائف العليا).

في بعض الأحيان سيكون من الجميل أن يكون هذا combinator تحت السيطرة البرنامج، أن تفعل أشياء مماثلة لجوانب البرمجة الموجهة (memoizing والبحث عن المفقودين، ...)، ولكن لا لغة البرمجة أعرف يسمح بذلك. ربما سيكون مرهق للغاية في معظم الوقت و / أو من الصعب جدا على التعلم.

Answer 4

يمكن آخرون تصحيح لي إذا كنت مخطئا، ولكن أنا متأكد من أن combinator Y هو الدراسي بدقة. فكروا: لتنفيذه لغتك تحتاج إلى دعم وظائف النظام أعلى ولكن لا العودية. هناك لغة واحدة فقط وأنا أعلم من هذا القبيل: حساب التفاضل والتكامل لامدا

وهكذا حتى التبديل لدينا آلات من آلات تورنج لتعمل على حساب التفاضل والتكامل لامدا، وcombinator Y سيكون الأكاديمي بدقة.

ملحوظة: غيرها من التقنيات الفنية المتعلقة combinator Y <م> هي مفيدة، حتى تبقي في ذلك. وفهم combinator Y مساعدتك على فهم استمرارا والتقييم كسول، الخ.

Answer 5

let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun a b c _ -> Sprite(a,c))

let sprites = 
    let rec y f x = f (y f) x // The Y Combinator
    //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work.
    let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x))
    many1Indents sprite sprites_up

وهنا مثال من مترجم لمكتبة عبة الشريك الأصغر وأنا على صنع في F #. وبشكل أكثر تحديدا، في ما سبق أحتاج أن يكون sprites_up متكرر تطلق على نفسها إلا فإن محلل المسافة البادئة لا تعمل بشكل صحيح.

وبدون Y Combinator، أنا لا يمكن أن فعلت محلل بشكل صحيح وقد اضطرت إلى اللجوء إلى كتابة شيء من هذا القبيل:

let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) 
let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) 
let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) 
let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) 
let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x) 

ولن يكون حلا رائعا، وY Combinator حقا أنقذني هناك. وكان بالتأكيد ليست الشيء الأول الذي جاء إلى الذهن بالرغم من ذلك.