Ocaml, реализуй freevars letrec используя наборы
Я пытаюсь реализовать 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)
Может кто-нибудь рассказать мне, как это сделать? Должен ли я использовать лямбду? Я довольно растерялся, и реализации, просто пытающиеся следовать определению, были сделаны неправильно с моей стороны, потому что я не могу заставить его работать.
2 ответа
Прочитав ваш вопрос много раз, я понял, что вы пытаетесь вычислить свободные переменные выражения следующим образом:
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 - функция. Может быть, это то, что задание говорит вам.
Если вы дадите несколько подробностей, возможно, кто-то, кто немного разбирается в этих вещах, может помочь
Я согласен с Джеффри, что здесь недостаточно информации. В любом случае, я приведу реализацию, поскольку проблема довольно проста:
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
отразить это достаточно легко.