Ocaml, реализуй freevars letrec используя наборы

Question

Я пытаюсь реализовать letrec с использованием математической лямбда-нотации для функции, но у меня возникли трудности. Мое назначение говорит, что пусть может быть определено как

p(e1) U (p(e2) - {x})

и этот letrec может быть определен как

(p(e1) - {f x}) U (p(e2) - {f}) 

Я успешно реализовал функцию let, чтобы найти freevars в выражении, но я борюсь с реализацией letrec:

let rec fv (e:expr) : S.t = match e with
  | Id name -> S.singleton name
  | Value x -> S.empty 
  | Lambda(name, body) ->  S.remove name (fv body)
  | Let(name, def, body) -> S.union (fv def) (S.diff (fv body) (S.singleton name))   

  | App (e1, e2) | Add (e1, e2) | Sub (e1, e2) | Mul (e1, e2) | Div (e1, e2) | Lt (e1, e2) | Eq (e1, e2) | And (e1, e2) -> S.union (fv e1) (fv e2)

Может кто-нибудь рассказать мне, как это сделать? Должен ли я использовать лямбду? Я довольно растерялся, и реализации, просто пытающиеся следовать определению, были сделаны неправильно с моей стороны, потому что я не могу заставить его работать.

Answer 1

Прочитав ваш вопрос много раз, я понял, что вы пытаетесь вычислить свободные переменные выражения следующим образом:

let rec x = e1 in e2

Сущность let rec это появление x в e1 приняты, чтобы сослаться на значение x это определяется. Так x не свободен в e1, И, как не рекурсивный let, x не свободен в e2 или. Это связано со значением e1,

Поэтому я бы подумал, что реализация будет выглядеть так:

(p(e1) - {x}) U (p(e2) - {x})

Определение, которое вы даете, не имеет смысла (для меня), тем более что нет очевидного смысла для f,

Можно представить, как ограничить эту форму случаями, где x - функция. Может быть, это то, что задание говорит вам.

Если вы дадите несколько подробностей, возможно, кто-то, кто немного разбирается в этих вещах, может помочь

Answer 2

Я согласен с Джеффри, что здесь недостаточно информации. В любом случае, я приведу реализацию, поскольку проблема довольно проста:

type term =
  | Var of string
  | App of term * term
  | Lam of string * term
  | Let of string * term * term
  | Letrec of (string * term) list * term

module S = Set.Make (String)

let rec free = function
  | Var name -> S.singleton name
  | App (f, x) -> S.union (free f) (free x)
  | Lam (arg, body) -> S.remove arg (free body)
  | Let (name, term, body) ->
    S.union (free term) (S.remove name (free body))
  | Letrec (rec_terms, body) ->
    S.diff
      (List.fold_left (fun set (_, term) ->
           S.union set (free term))
          (free body) rec_terms)
      (S.of_list (List.map fst rec_terms))

Обратите внимание, что это не накладывает никаких ограничений на rec связанные условия. Если вы будете разрешать только функции там, то вы можете изменить term отразить это достаточно легко.