Como você implementaria uma função de redução beta em F#?

Question

Estou escrevendo um cálculo lambda em F#, mas estou preso na implementação da redução beta (substituindo parâmetros formais pelos parâmetros reais).

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

Exemplo de uso:

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

Então, eu adoraria ouvir algumas sugestões em relação à maneira como os outros podem fazer isso. Quaisquer idéias seriam muito apreciadas.

Obrigado!

Answer 1

Assumindo que sua representação de uma expressão se parece

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

, você tem uma função subst (x:ident) (e1:expression) (e2:expression) : expression que substitui todas as ocorrências livres de x com e1 dentro e2, e você deseja avaliação normal de pedidos, seu código deve parecer algo assim:

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

o subst A função deve funcionar da seguinte maneira:

Para um aplicativo de função, ele deve se chamar recursivamente nas duas subexpressões.

Para Lambdas, deve se chamar na expressão corporal do Lambda a não ser que O nome do argumento do Lambda é igual ao identificador que você deseja substituir (nesse caso, você pode deixar o Lambda porque o identificador não pode aparecer livremente em nenhum lugar dentro dele).

Para uma variável, ele deve retornar a variável inalterada ou a expressão de substituição, dependendo se o nome da variável é igual ao identificador.