كيف يمكنك تنفيذ وظيفة الحد من بيتا في F#؟

Question

أنا أكتب حساب التفاضل والتكامل Lambda في F#، لكنني عالق في تنفيذ الحد من بيتا (استبدال المعلمات الرسمية مع المعلمات الفعلية).

(lambda x.e)f
--> e[f/x]

مثال على الاستخدام:

(lambda n. n*2+3) 7
--> (n*2+3)[7/n]
--> 7*2+3

لذلك أحب أن أسمع بعض الاقتراحات فيما يتعلق بكيفية قيام الآخرين بذلك. اي افكار يمكن ان تكون رائعه للعرض.

شكرًا!

Answer 1

على افتراض أن تمثيلك للتعبير يبدو

type expression = App of expression * expression
                | Lambda of ident * expression
                (* ... *)

, ، لديك وظيفة subst (x:ident) (e1:expression) (e2:expression) : expression الذي يحل محل جميع الأحداث الحرة لـ x مع e1 في e2, ، وتريد تقييم الطلب العادي ، يجب أن يبدو الرمز الخاص بك شيئًا كهذا:

let rec eval exp =
  match exp with
  (* ... *)
  | App (f, arg) -> match eval f with Lambda (x,e) -> eval (subst x arg e)

ال subst يجب أن تعمل الوظيفة على النحو التالي:

لتطبيق الوظيفة ، يجب أن تسمي نفسها بشكل متكرر على كل من التعبيرات الفرعية.

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

بالنسبة للمتغير ، يجب إما إرجاع المتغير دون تغيير أو التعبير عن الاستبدال اعتمادًا على ما إذا كان اسم المتغير مساوياً للمعرف.