Как бы вы реализовали функцию бета-сокращения в F #?

Question

Я пишу лямбда-исчисление на 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 должна работать следующим образом:

Для приложения-функции он должен вызывать себя рекурсивно в обоих подвыражениях.

Для лямбда-выражений он должен вызывать себя в выражении лямбда-тела , если имя аргумента лямбда-выражения равно идентификатору, который вы хотите заменить (в этом случае вы можете просто оставить лямбда-выражение, потому что идентификаторне может свободно появляться где-либо внутри него).

Для переменной она должна либо возвращать переменную без изменений, либо выражение замены в зависимости от того, равно ли имя переменной идентификатору.