Как бы вы реализовали функцию бета-восстановления в 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 Функция должна работать следующим образом:

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

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

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