¿Cómo se implementa una función de reducción de beta en C #?

Question

Estoy escribiendo un cálculo lambda en C #, pero estoy atascado en la aplicación de la beta-reducción (sustituyendo parámetros formales con los parámetros reales).

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

ejemplo de uso:

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

Así que me gustaría escuchar algunas sugerencias en cuanto a la forma en que otros podrían ir sobre esto. Cualquier idea sería muy apreciados.

Gracias!

Answer 1

Asumiendo que su representación de una expresión se parece a

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

, que tiene una función subst (x:ident) (e1:expression) (e2:expression) : expression que sustituye todas las ocurrencias libres de x con e1 en e2, y desea que la evaluación de orden normal, el código debe ser algo como esto:

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

La función subst debería funcionar de la siguiente manera:

Para una aplicación de función debe llamarse a sí mismo de forma recursiva en ambas subexpresiones.

Para lambdas debe llamarse a sí misma en la expresión corporal de la lambda a menos que nombre del argumento de la lambda es igual al identificador que desea reemplazar (en cuyo caso sólo se puede dejar ser el lambda porque la lata identificador 't parecen libremente en cualquier lugar dentro de él).

Para una variable que debe o bien volver la variable sin cambios o la sustitución-expresión en función de si el nombre de la variable es igual al identificador.