سؤال

يعد Y-combinator مفهومًا لعلوم الكمبيوتر من الجانب "الوظيفي" للأشياء.معظم المبرمجين لا يعرفون الكثير على الإطلاق عن أدوات التجميع، هذا إذا كانوا قد سمعوا عنها.

  • ما هو المجمع Y؟
  • كيف تعمل المجمعات؟
  • ما هي جيدة ل؟
  • هل هي مفيدة في اللغات الإجرائية؟
هل كانت مفيدة؟

المحلول

إذا كنت مستعدًا لقراءة طويلة، مايك فانير لديه عظيم توضيح.باختصار، إنها تسمح لك بتنفيذ التكرار بلغة لا تدعمها بالضرورة محليًا.

نصائح أخرى

إن أداة التجميع Y هي وظيفة "وظيفية" (وظيفة تعمل على وظائف أخرى) تتيح التكرار، عندما لا تتمكن من الرجوع إلى الوظيفة من داخل نفسها.في نظرية علوم الكمبيوتر، فإنه يعمم العودية, وتجريد تنفيذها، وبالتالي فصلها عن العمل الفعلي للوظيفة المعنية.تعتبر فائدة عدم الحاجة إلى اسم وقت الترجمة للوظيفة العودية بمثابة مكافأة.=)

وهذا ينطبق على اللغات التي تدعم وظائف لامدا.ال تعبيرعادةً ما تعني طبيعة اللامدا المبنية على أساسها أنهم لا يستطيعون الإشارة إلى أنفسهم بالاسم.والتغلب على هذا عن طريق الإعلان عن المتغير، والإشارة إليه، ثم تعيين لامدا له، لإكمال حلقة المرجع الذاتي، هو أمر هش.يمكن نسخ متغير لامدا، وإعادة تعيين المتغير الأصلي، مما يؤدي إلى كسر المرجع الذاتي.

تعد أدوات الجمع Y مرهقة في التنفيذ وغالبًا ما يتم استخدامها ثابت اللغات (التي اللغات الإجرائية غالبًا ما تكون كذلك)، لأن قيود الكتابة عادةً ما تتطلب معرفة عدد الوسائط الخاصة بالوظيفة المعنية في وقت الترجمة.هذا يعني أنه يجب كتابة أداة الجمع y لأي عدد من الوسائط التي يحتاج المرء إلى استخدامها.

يوجد أدناه مثال لكيفية استخدام Y-Combinator وعمله في لغة C#.

يتضمن استخدام أداة الجمع Y طريقة "غير عادية" لإنشاء دالة عودية.يجب عليك أولاً كتابة وظيفتك كجزء من التعليمات البرمجية التي تستدعي وظيفة موجودة مسبقًا، بدلاً من نفسها:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

ثم تقوم بتحويل ذلك إلى دالة تأخذ دالة لتستدعيها، وترجع دالة تقوم بذلك.ويسمى هذا دالة، لأنها تأخذ دالة واحدة، وتجري بها عملية تؤدي إلى دالة أخرى.

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

الآن لديك دالة تأخذ دالة، وترجع دالة أخرى تبدو وكأنها مضروب، ولكن بدلاً من استدعاء نفسها، فإنها تستدعي الوسيطة التي تم تمريرها إلى الدالة الخارجية.كيف تجعل هذا العامل؟تمرير الوظيفة الداخلية لنفسها.يقوم Y-Combinator بذلك، من خلال كونه دالة ذات اسم دائم، والتي يمكنها تقديم التكرار.

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

بدلاً من استدعاء المضروب نفسه، ما يحدث هو أن المضروب يستدعي مولد المضروب (الذي يتم إرجاعه بواسطة الاستدعاء العودي إلى Y-Combinator).واعتمادًا على القيمة الحالية لـ t، فإن الدالة التي يتم إرجاعها من المولد إما أن تستدعي المولد مرة أخرى، مع t - 1، أو ترجع 1 فقط، مما يؤدي إلى إنهاء العودية.

إنه أمر معقد وغامض، ولكن كل شيء يهتز في وقت التشغيل، ومفتاح عمله هو "التنفيذ المؤجل"، وتقسيم التكرار ليشمل وظيفتين.الداخلي F هو مرت كحجة, ، ليتم استدعاؤها في التكرار التالي، فقط إذا لزم الأمر.

لقد رفعت هذا من http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html وهو تفسير كتبته منذ عدة سنوات.

سأستخدم جافا سكريبت في هذا المثال، ولكن العديد من اللغات الأخرى ستعمل أيضًا.

هدفنا هو أن نكون قادرين على كتابة دالة عودية لمتغير واحد باستخدام وظائف فقط من متغيرات واحدة ولا توجد مهام ، وتحديد الأشياء بالاسم ، إلخ.(لماذا هذا هو هدفنا هو سؤال آخر ، دعونا نأخذ هذا فقط كتحدي نقدمه.) يبدو مستحيلًا ، هاه؟على سبيل المثال ، دعنا ننفذ العامل.

حسنًا ، الخطوة 1 هي القول إنه يمكننا القيام بذلك بسهولة إذا خدعنا قليلاً.باستخدام وظائف 2 متغير والتعيين ، يمكننا على الأقل تجنب الاضطرار إلى استخدام المهمة لإعداد العودية.

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

الآن دعونا نرى ما إذا كان بإمكاننا الغش بشكل أقل.حسنًا ، نحن نستخدم المهمة أولاً ، لكننا لسنا بحاجة إلى ذلك.يمكننا فقط كتابة x و y inline.

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

لكننا نستخدم وظائف من متغيرين للحصول على وظيفة متغير واحد.هل يمكننا إصلاح ذلك؟حسنًا ، يتمتع رجل ذكي باسم Haskell Curry بخدعة أنيقة ، إذا كان لديك وظائف ذات ترتيب أعلى جيدًا ، فأنت تحتاج فقط إلى وظائف من متغير واحد.الدليل هو أنه يمكنك الحصول على متغيرات 2 (أو أكثر في الحالة العامة) إلى متغير واحد مع تحول نص ميكانيكي بحت مثل هذا:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

أين ...يظل كما هو تمامًا.(هذه الخدعة تسمى "الكاري" بعد مخترعها.تم تسمية اللغة Haskell أيضًا باسم Haskell Curry.ملف ذلك تحت التوافه عديمة الفائدة.) الآن فقط قم بتطبيق هذا التحول في كل مكان ونحصل على نسختنا النهائية.

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

لا تتردد في محاولة ذلك.تنبيه () الذي يعود، وربطه بزر، أيا كان.يحسب هذا الرمز العوامل ، بشكل متكرر ، دون استخدام التعيين أو التصريحات أو وظائف متغيرين.(لكن محاولة تتبع كيف يعمل من المحتمل أن تجعل رأسك يدور.وتسليمه ، دون الاشتقاق ، سيؤدي إعادة إعادة الإصلاح قليلاً إلى مدونة من المؤكد أن تربكها وتخلطها.)

يمكنك استبدال الأسطر الأربعة التي تحدد العوامل المميزة بشكل متكرر بأي وظيفة عودية أخرى تريدها.

أتساءل عما إذا كان هناك أي فائدة في محاولة بناء هذا من الألف إلى الياء.دعنا نرى.إليك دالة عاملية أساسية متكررة:

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

دعونا نعيد بناء وإنشاء وظيفة جديدة تسمى fact تقوم بإرجاع دالة حوسبة عاملية مجهولة بدلاً من إجراء العملية الحسابية نفسها:

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

هذا غريب بعض الشيء، ولكن لا يوجد شيء خاطئ في ذلك.نحن نقوم فقط بإنشاء دالة عاملية جديدة في كل خطوة.

العودية في هذه المرحلة لا تزال واضحة إلى حد ما.ال fact يجب أن تكون الوظيفة على علم باسمها.دعونا نحدد معلمات المكالمة العودية:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

هذا عظيم، ولكن recurser لا تزال بحاجة إلى معرفة اسمها.دعونا نحدد ذلك أيضًا:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

الآن، بدلاً من الاتصال recurser(recurser) مباشرة، لنقم بإنشاء دالة مجمعة تُرجع نتيجتها:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

يمكننا الآن التخلص من recurser الاسم تماما؛إنها مجرد وسيطة للوظيفة الداخلية لـ Y، والتي يمكن استبدالها بالوظيفة نفسها:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

الاسم الخارجي الوحيد الذي لا يزال يشار إليه هو fact, ، ولكن يجب أن يكون واضحًا الآن أنه من السهل تحديد المعلمات أيضًا، مما يؤدي إلى إنشاء الحل الكامل والعام:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y(function(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
});

تصف معظم الإجابات أعلاه ما هو مركب Y يكون ولكن ليس ما هو عليه ل.

مجمعات النقطة الثابتة تستخدم لإظهار ذلك حساب التفاضل والتكامل لامدا يكون تورينج كاملة.هذه نتيجة مهمة جدًا في نظرية الحساب وتوفر أساسًا نظريًا لها البرمجة الوظيفية.

لقد ساعدتني دراسة أدوات دمج النقاط الثابتة أيضًا على فهم البرمجة الوظيفية.بالرغم من ذلك، لم أجد أي فائدة لهم في البرمجة الفعلية.

y الموحد في جافا سكريبت:

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

يحرر:أتعلم الكثير من خلال النظر إلى التعليمات البرمجية، ولكن من الصعب بعض الشيء استيعاب هذه التعليمات البرمجية بدون أي خلفية - آسف لذلك.مع بعض المعرفة العامة التي تقدمها الإجابات الأخرى، يمكنك البدء في تمييز ما يحدث.

الدالة Y هي "المجمع y".الآن نلقي نظرة على var factorial الخط حيث يتم استخدام Y.لاحظ أنك قمت بتمرير دالة إليها تحتوي على معلمة (في هذا المثال، recurse) والذي يتم استخدامه أيضًا لاحقًا في الوظيفة الداخلية.يصبح اسم المعلمة بشكل أساسي اسم الوظيفة الداخلية التي تسمح لها بإجراء مكالمة متكررة (نظرًا لأنها تستخدم recurse() في تعريفه.) يقوم المجمّع y بتنفيذ سحر ربط الوظيفة الداخلية المجهولة مع اسم معلمة الوظيفة التي تم تمريرها إلى Y.

للحصول على الشرح الكامل لكيفية عمل Y للسحر، قم بمراجعة مقالة مرتبطة (ليس بواسطتي راجع للشغل.)

للمبرمجين الذين لم يتعمقوا في البرمجة الوظيفية، ولا يهتمون بالبدء الآن، ولكن لديهم فضول إلى حد ما:

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

وهو يعمل عن طريق تمرير الدالة إلى نفسها كوسيطة، حتى تتمكن من استدعاء نفسها.

إنها جزء من حساب التفاضل والتكامل لامدا، والتي هي في الواقع رياضيات ولكنها في الواقع لغة برمجة، وهي أساسية جدًا لعلوم الكمبيوتر وخاصة البرمجة الوظيفية.

إن القيمة العملية اليومية للمركب Y محدودة، نظرًا لأن لغات البرمجة تميل إلى السماح لك بتسمية الوظائف.

في حال كنت بحاجة إلى التعرف عليه في تشكيلة الشرطة، يبدو كما يلي:

Y = αf.(×x.f (x x)) (×x.f (x x))

يمكنك عادةً اكتشافه بسبب التكرار (λx.f (x x)).

ال λ الرموز هي الحرف اليوناني لامدا، الذي يعطي حساب التفاضل والتكامل لامدا اسمه، وهناك الكثير منها (λx.t) مصطلحات الأسلوب لأن هذا هو ما يبدو عليه حساب التفاضل والتكامل لامدا.

توفر الإجابات الأخرى إجابة موجزة جدًا عن هذا، دون حقيقة مهمة واحدة:لا تحتاج إلى تنفيذ أداة دمج النقاط الثابتة بأي لغة عملية بهذه الطريقة المعقدة، والقيام بذلك لا يخدم أي غرض عملي (باستثناء "انظر، أنا أعرف ما هو جهاز تجميع Y").إنه مفهوم نظري مهم، ولكن ذو قيمة عملية قليلة.

فيما يلي تطبيق JavaScript لـ Y-Combinator والدالة العاملية (من مقالة دوغلاس كروكفورد، المتوفرة على: http://javascript.crockford.com/little.html).

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

Y-Combinator هو اسم آخر لمكثف التدفق.

لقد كتبت نوعًا من "دليل البلهاء" إلى Y-Combinator في كل من Clojure وScheme من أجل مساعدة نفسي في التعامل معه.لقد تأثروا بالمواد الموجودة في "The Little Schemer"

في المخطط:https://Gist.github.com/z5h/238891

أو كلوجور:https://Gist.github.com/z5h/5102747

كلا البرنامجين التعليميين عبارة عن تعليمات برمجية تتخللها تعليقات ويجب قصها ولصقها في المحرر المفضل لديك.

العودية مجهولة

إن أداة دمج النقاط الثابتة هي وظيفة ذات ترتيب أعلى fix وهذا بحكم التعريف يفي بالتكافؤ

forall f.  fix f  =  f (fix f)

fix f يمثل الحل x لمعادلة النقطة الثابتة

               x  =  f x

يمكن إثبات مضروب العدد الطبيعي بواسطة

fact 0 = 1
fact n = n * fact (n - 1)

استخدام fix, ، يمكن استخلاص البراهين البناءة التعسفية على الوظائف العامة/العودية بدون مرجعية ذاتية مجهولة.

fact n = (fix fact') n

أين

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

مثل ذلك

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

وهذا دليل رسمي على ذلك

fact 3  =  6

يستخدم بشكل منهجي معادلة مجمع النقطة الثابتة لـ يعيد كتابة

fix fact'  ->  fact' (fix fact')

حساب التفاضل والتكامل لامدا

ال حساب التفاضل والتكامل لامدا غير مكتوب تتكون الشكلية من قواعد خالية من السياق

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

أين v يتراوح على المتغيرات، جنبا إلى جنب مع بيتا و تخفيض إيتا قواعد

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

يستبدل تخفيض بيتا كافة التواجدات المجانية للمتغير x في الجسم التجريدي ("الوظيفة"). B من خلال التعبير ("الحجة") E.يؤدي تقليل إيتا إلى التخلص من التجريد الزائد.يتم حذفه في بعض الأحيان من الشكلية.ان غير القابل للاختزال التعبير، الذي لا تنطبق عليه قاعدة التخفيض، موجود طبيعي أو الشكل الكنسي.

λ x y. E

هو اختصار ل

λ x. λ y. E

(التعددية التجريدية)،

E F G

هو اختصار ل

(E F) G

(ارتباطية يسار التطبيق) ،

λ x. x

و

λ y. y

نكون مكافئ ألفا.

التجريد والتطبيق هما "الأساسان اللغويان" الوحيدان لحساب التفاضل والتكامل لامدا، لكنهما يسمحان بذلك التشفير من البيانات والعمليات المعقدة بشكل تعسفي.

أرقام الكنيسة هي ترميز للأعداد الطبيعية المشابهة للأرقام الطبيعية البديهية.

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

دليل رسمي على ذلك

1 + 2  =  3

باستخدام قاعدة إعادة الكتابة لتخفيض النسخة التجريبية:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

المجمعات

في حساب التفاضل والتكامل لامدا المجمعات هي تجريدات لا تحتوي على متغيرات حرة.بكل بساطة: I, ، مجمع الهوية

λ x. x

متماثل لوظيفة الهوية

id x = x

مثل هذه المجمعات هي المشغلين البدائيين حساب الجمع مثل نظام التزلج.

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

تخفيض بيتا ليس كذلك التطبيع بقوة;لا تتقارب جميع التعبيرات القابلة للاختزال، "redexes"، إلى الشكل الطبيعي في ظل تقليل بيتا.مثال بسيط هو التطبيق المتباين للأوميغا ω الموحد

λ x. x x

إلى نفسها:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

يتم إعطاء الأولوية لتقليل التعبيرات الفرعية الموجودة في أقصى اليسار ("الرؤوس"). أمر تطبيقي تطبيع الحجج قبل الاستبدال، النظام العادي لا.تشبه الاستراتيجيتين التقييم الحريص، على سبيل المثال.C، والتقييم البطيء، على سبيل المثال.هاسكل.

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

يتباعد في ظل التخفيض التجريبي للطلب التطبيقي

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

منذ ذلك الحين في حازم دلالات

forall f.  f _|_  =  _|_

ولكنها تتقارب في ظل تخفيض النسخة التجريبية ذات الترتيب الطبيعي البطيء

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

إذا كان التعبير له شكل عادي، فسوف يجده تخفيض بيتا ذو الترتيب العادي.

ي

الخاصية الأساسية لل Y مجمع النقطة الثابتة

λ f. (λ x. f (x x)) (λ x. f (x x))

اعطي من قبل

   Y g
=  (λ f. (λ x. f (x x)) (λ x. f (x x))) g
=  (λ x. g (x x)) (λ x. g (x x))           =  Y g
=  g ((λ x. g (x x)) (λ x. g (x x)))       =  g (Y g)
=  g (g ((λ x. g (x x)) (λ x. g (x x))))   =  g (g (Y g))
. . .                                      . . .

التكافؤ

Y g  =  g (Y g)

هو متماثل ل

fix f  =  f (fix f)

يمكن لحساب التفاضل والتكامل لامدا غير المكتوب تشفير البراهين البناءة التعسفية على الوظائف العامة/العودية.

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(الضرب تأخر، التقاء)

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

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

إن تخفيض النسخة التجريبية ذات الترتيب العادي يجعل حساب التفاضل والتكامل لامدا غير الموسع غير الموسع بمثابة نظام إعادة كتابة كامل تورينج.

في هاسكل، يمكن تنفيذ أداة دمج النقاط الثابتة بشكل أنيق

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

يتم تطبيع كسل هاسكل إلى النهاية قبل تقييم جميع التعبيرات الفرعية.

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

ينفذ combinator y العودية المجهولة.لذلك بدلا من

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

يمكنك ان تفعل

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

وبطبيعة الحال، يعمل y-combinator فقط في لغات الاتصال بالاسم.إذا كنت تريد استخدام هذا في أي لغة عادية للاستدعاء حسب القيمة، فستحتاج إلى z-combinator ذي الصلة (سوف يتباعد y-combinator/حلقة لا نهائية).

كمبتدئ لcombinators، وجدت مقالة مايك فانيير (شكرًا نيكولاس مانكوسو) ليكون مفيدًا حقًا.أود أن أكتب ملخصًا، إلى جانب توثيق فهمي، إذا كان من الممكن أن يكون مفيدًا للبعض الآخر سأكون سعيدًا جدًا.

من سيء الجودة ل أقل كربي

باستخدام مضروب كمثال، نستخدم ما يلي almost-factorial وظيفة لحساب مضروب الرقم x:

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

في الكود الزائف أعلاه، almost-factorial يأخذ في الوظيفة f والرقم x (almost-factorial يتم طبخه، لذلك يمكن اعتباره يؤدي وظيفته f وإرجاع دالة 1-arity).

متى almost-factorial يحسب مضروب ل x, ، فإنه يفوض حساب مضروب ل x - 1 لتعمل f ويتراكم تلك النتيجة مع x (في هذه الحالة يتم ضرب نتيجة (x - 1) في x).

يمكن أن ينظر إليه على أنه almost-factorial يأخذ في سيء الجودة إصدار دالة مضروب (والتي يمكن حسابها فقط حتى الرقم x - 1) ويعود أ أقل كربي إصدار المضروب (الذي يحسب حتى الرقم x).كما في هذا النموذج:

almost-factorial crappy-f = less-crappy-f

إذا مررنا مرارا وتكرارا أقل كربي نسخة من العامل إلى almost-factorial, ، سنحصل في النهاية على دالة العامل المطلوبة f.حيث يمكن اعتباره:

almost-factorial f = f

نقطة الإصلاح

حقيقة ان almost-factorial f = f وسائل f هل نقطة الإصلاح من الوظيفة almost-factorial.

لقد كانت هذه طريقة مثيرة للاهتمام حقًا لرؤية العلاقات بين الوظائف المذكورة أعلاه وكانت لحظة رائعة بالنسبة لي.(يرجى قراءة مشاركة مايك حول نقطة الإصلاح إذا لم تقم بذلك)

ثلاث وظائف

للتعميم، لدينا غير العودية وظيفة fn (مثل مضروبنا تقريبا)، لدينا نقطة الإصلاح وظيفة fr (مثل و لدينا)، ثم ماذا Y يفعل هو عندما تعطي Y fn, Y تقوم بإرجاع وظيفة نقطة الإصلاح لـ fn.

لذلك باختصار (مبسطة بافتراض fr يأخذ معلمة واحدة فقط؛ x يتدهور الى x - 1, x - 2...في التكرار):

  • نحن نحدد الحسابات الأساسية مثل fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), ، هذا ال مفيدة تقريبا وظيفة - على الرغم من أننا لا نستطيع استخدامها fn مباشرة على x, ، سيكون مفيدًا قريبًا جدًا.هذا غير العودي fn يستخدم وظيفة fr لحساب نتيجته
  • fn fr = fr, fr هي نقطة الإصلاح fn, fr هل مفيد funciton، يمكننا استخدامها fr على x للحصول على النتيجة لدينا
  • Y fn = fr, Y إرجاع نقطة الإصلاح للدالة، Y أصبح لاذعا مفيدة تقريبا وظيفة fn داخل مفيد fr

اشتقاق Y (غير مشمول)

وسوف تخطي اشتقاق Y والذهاب إلى الفهم Y.يحتوي منشور مايك فاينر على الكثير من التفاصيل.

شكل Y

Y يتم تعريفه على أنه (في حساب التفاضل والتكامل لامدا شكل):

Y f = λs.(f (s s)) λs.(f (s s))

إذا قمنا باستبدال المتغير s في الجانب الأيسر من الوظائف، نحصل على

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

وبالفعل نتيجة (Y f) هي نقطة الإصلاح f.

لماذا (Y f) عمل؟

على حسب التوقيع f, (Y f) يمكن أن تكون دالة لأي دالة، للتبسيط، لنفترض (Y f) تأخذ معلمة واحدة فقط، مثل دالة المضروب لدينا.

def fn fr x = accumulate x (fr (- x 1))

منذ fn fr = fr, ، نواصل

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

ينتهي الحساب العودي عندما يكون الجزء الداخلي أكثر (fn fr 1) هي الحالة الأساسية و fn لا يستخدم fr في الحساب.

انظر الى Y مرة أخرى:

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

لذا

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

بالنسبة لي، الأجزاء السحرية من هذا الإعداد هي:

  • fn و fr تعتمد على بعضها البعض: fr "يلتف" fn في الداخل، في كل مرة fr يستخدم لحساب x, ، إنه "يولد" ("يرفع"؟) أ fn ويفوض الحساب لذلك fn (يمر في حد ذاته fr و x);على الجانب الآخر، fn يعتمد على fr والاستخدامات fr لحساب نتيجة مشكلة أصغر x-1.
  • في الموعد fr يستخدم لتعريف fn (متى fn الاستخدامات fr في عملياتها) الحقيقية fr لم يتم تعريفها بعد.
  • إنه fn الذي يحدد منطق العمل الحقيقي.مرتكز على fn, Y يخلق fr - دالة مساعدة على شكل معين - لتسهيل عملية الحساب fn في العودية طريقة.

لقد ساعدني على الفهم Y بهذه الطريقة في الوقت الراهن، وآمل أن يساعد.

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

فيما يلي إجابات على الأسئلة الأصلية, ، مجمعة من المقالة (وهو يستحق القراءة تمامًا) المذكور في إجابة من نيكولاس مانكوسو, ، بالإضافة إلى إجابات أخرى:

ما هو المجمع Y؟

إن أداة التجميع Y هي دالة "وظيفية" (أو دالة ذات ترتيب أعلى - دالة تعمل على وظائف أخرى) تأخذ وسيطة واحدة، وهي دالة غير متكررة، وتقوم بإرجاع نسخة من الوظيفة التي هي العودية.


عودي إلى حد ما =)، ولكن تعريف أكثر تعمقا:

المجمِع — هو مجرد تعبير لامدا بدون متغيرات حرة.
المتغير الحر - هو متغير ليس متغيرا منضما.
متغير منضم - متغير موجود داخل النص الأساسي لتعبير لامدا الذي يحتوي على اسم المتغير كأحد الوسائط الخاصة به.

طريقة أخرى للتفكير في هذا الأمر هي أن المجمِّع هو عبارة عن تعبير لامدا، حيث يمكنك استبدال اسم المجمِع بتعريفه في كل مكان يتم العثور عليه ويجعل كل شيء لا يزال يعمل (سوف تدخل في حلقة لا نهائية إذا كان المجمِع تحتوي على إشارة إلى نفسها، داخل جسم لامدا).

Y-combinator هو مجمع ذو نقطة ثابتة.

النقطة الثابتة للدالة هي عنصر من نطاق الوظيفة الذي يتم تعيينه لنفسها بواسطة الوظيفة.
ذلك بالقول، c هي نقطة ثابتة من الدالة f(x) لو f(c) = c
هذا يعنى f(f(...f(c)...)) = fn(c) = c

كيف تعمل المجمعات؟

تفترض الأمثلة أدناه قوية + ديناميكية الكتابة:

كسول (ترتيب عادي) Y-combinator:
ينطبق هذا التعريف على اللغات ذات الكسل (أيضًا:التقييم المؤجل، حسب الحاجة) - استراتيجية التقييم التي تؤخر تقييم التعبير حتى تكون قيمته مطلوبة.

Y = λf.(λx.f(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

ما يعنيه هذا هو أنه بالنسبة لوظيفة معينة f (وهي دالة غير متكررة)، يمكن الحصول على الدالة العودية المقابلة أولاً عن طريق الحوسبة λx.f(x x), ، ثم قم بتطبيق تعبير لامدا على نفسه.

صارم (أمر تطبيقي) Y-combinator:
ينطبق هذا التعريف على اللغات ذات الصارمة (أيضًا:حريص، جشع) التقييم - استراتيجية التقييم التي يتم من خلالها تقييم التعبير بمجرد ربطه بمتغير.

Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))

وهو مثل الكسلان في طبيعته، ولكن فيه زيادة فقط λ مغلفة لتأخير تقييم الجسم لامدا.لقد سألت سؤال آخر, ، تتعلق إلى حد ما بهذا الموضوع.

ما هي جيدة ل؟

مسروق مستعار من إجابة من كريس أميرمان:يقوم Y-combinator بتعميم التكرار، وتجريد تنفيذه، وبالتالي فصله عن العمل الفعلي للوظيفة المعنية.

على الرغم من أن Y-combinator لديه بعض التطبيقات العملية، إلا أنه في الأساس مفهوم نظري، وسيؤدي فهمه إلى توسيع رؤيتك الشاملة ومن المحتمل أن يزيد من مهاراتك التحليلية والمطورة.

هل هي مفيدة في اللغات الإجرائية؟

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

و كما ذكره كريس أميرمان:تحتوي معظم اللغات الإجرائية على كتابة ثابتة.

لذا أجب على هذا - ليس حقًا.

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

يمكن لهذا المشغل تبسيط حياتك:

var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(h) {
        return function() {
            return f.apply(h(h), arguments);
        };
    });
};

ثم تتجنب الوظيفة الإضافية:

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

وأخيرا، اتصلت fac(5).

أعتقد أن أفضل طريقة للإجابة على هذا السؤال هي اختيار لغة، مثل JavaScript:

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

الآن أعد كتابتها بحيث لا تستخدم اسم الوظيفة داخل الوظيفة، ولكن لا تزال تستدعيها بشكل متكرر.

المكان الوحيد اسم الوظيفة factorial ينبغي أن ينظر إليه في موقع الدعوة.

تَلمِيح:لا يمكنك استخدام أسماء الوظائف، ولكن يمكنك استخدام أسماء المعلمات.

عمل المشكلة.لا تبحث عنه.بمجرد حلها، سوف تفهم المشكلة التي يحلها المجمع y.

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top