كيف يمكنك تنفيذ مشغل نقطة ثابتة (Y Combinator) في F#؟

Question

أنا أستخدم F# لإنشاء حساب حساب Lambda. أنا عالق حاليًا في محاولة لمعرفة كيفية تنفيذ مشغل النقطة الثابتة (تسمى أيضًا Y Combinator).

أعتقد أن كل شيء آخر في النظام. يتم تمثيل التعبيرات من خلال الاتحاد التمييزي التالي:

type Expr =
 | Const of int
 | Plus  of Expr * Expr
 | Times of Expr * Expr
 | Minus of Expr * Expr
 | Div   of Expr * Expr
 | Neg   of Expr
 | Var   of string
 | Fun   of string * Expr
 | App   of Expr * Expr
 | If    of Expr * Expr * Expr

لي eval يبدو أن الوظيفة تعمل. الأمثلة التالية جميعها تسفر عن النتائج المتوقعة.
مثال 1:
> eval (Fun("x",Plus(Const 7,Var("x"))));;
val it : Expr = Fun ("x",Plus (Const 7,Var "x"))
مثال 2:
> eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3));;
val it : Expr = Const 10
مثال 3:
> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

لكن كما ذكرت ، أواجه صعوبة في تنفيذ مشغل النقطة الثابتة في حساب حساب Lambda الخاص بي. يتم تعريفه هنا كما:
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

هل يوجد لدى احد أي اقتراحات؟ لقد نظرت إلى الأسئلة الأخرى المتعلقة بـ Y Combinator ، لكنني لم أتمكن من العثور على أي شيء تمكنت من تبنيه بنجاح.

يتم تقدير كل المساعدة.

يحرر: تم إصلاح خطأ مطبعي في الكود ... سابقًا كان لدي Mult بدلاً من Minus في الاتحاد التمييز. مضحك أنني لاحظت ذلك للتو!

Answer 1

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

Y = lambda G. (lambda g. G(lambda x. g g x)) (lambda g. G(lambda x. g g x))

Answer 2

بقدر ما أتذكر ذلك ، هناك فئة كاملة من المتجدات Y في حساب التفاضل والتكامل اللامبدي غير المعقول ، ولكن من الصعب تنفيذ واحد حتى إذا كانت لغتك قد كتبت بدقة ، على الرغم من أن الناس حاولوا القيام بحالات خاصة في ML وأيضًا F#. لا يبدو أنه مفيد للغاية إذا كانت لغتك تدعم التكرار (أي حساب حساب Lambda لا). ألقِ نظرة على المناقشات حول هذا الموضوع الذي رأى Stackoverflow علامة "برمجة وظيفية" عامة أو ML ، أعتقد أن هناك بعض الأفكار التي يجب أن تكون عليها:

y-combinator مثال عملي