Cálculo lambda P86813

Tu programa tiene que leer expresiones lambda y saber realizar 3 operaciones básicas del lambda cálculo: calcular las variables “gastadas”, calcular las variables libres, y realizar substituciones.

Expresiones lambda.

El lenguaje de las expresiones lambda (expresiones a partir de ahora) se describe con los siguientes tres casos y con ninguno más:

• Cadenas de caracteres de la 'a' a la 'z' son expresiones (variables).
• Dada una expresión B y una variable v, la cadena formada por el caracter '\', seguido de v, seguido del caracter '.' seguido de B (\v.B) es una expresión (abstracción).
• Dadas dos expresiones F y A, la cadena formada por el caracter '(', seguido de F, seguido del caracter ' ' (blanco), seguido de A, seguido del caracter ')' ((F A)) es una expresión (aplicación).

Variables gastadas.

El conjunto de variables gastadas VG(E) de una expresión E es el conjunto de todas las variables de la 'a' a la 'z' que aparecen en la expresión E, de cualquier forma. Equivalentemente,

Variables libres.

El conjunto de variables libres VL(E) de una expresión E se define de esta forma:

Substitución.

La substitución E[x := E′] de una variable v en una expresión E por otra expresión E′ se define de la siguiente forma:

Observad que, cuando E es de la forma \v.B, no siempre es posible realizar la substitución. Esto siempre puede corregirse aplicando una conversión alpha, descritas a continuación, en la expresión \v.B reemplazando v por una variable no gastada. Sin embargo, las entradas del problema serán tales que nunca os va a ser necesario hacer una conversión alpha para hacer la substitución.

Entrada

Un juego de pruebas es una secuencia de cálculos, cada uno de los cuales ocupa una línea. Los cálculos pueden ser de la forma “G E”, “L E” o “S x E E′”, donde E y E′ son expresiones válidas y x es una variable. Ninguna de las líneas ocupará más de 2000 caracteres. En los cálculos de tipo S se os garantiza que la substitución puede hacerse, sin que sea necesario que hagáis ninguna conversión alpha en ningún momento.

Salida

Por cada cálculo, tu programa debe escribir una línea con la respuesta. Escribe las variables gastadas VG(E) de E si la petición es de tipo G, las variables libres VL(E) de E si es de tipo L, y la substitución E[x := E′] si la petición es de tipo S. Escribe un conjunto de variables como una secuencia ordenada alfabéticamente de las mismas (fíjate en los ejemplos). Observa que el resultado de la substitución puede ser más largo de 2000 caracteres.

Puntuación

• TestA:  ‍25 Puntos ‍

  Pruebas de no más de 200 expresiones que sólo contienen peticiones de cálculo de tipo ‍G.

• TestA:  ‍40 Puntos ‍

  Pruebas de no más de 200 expresiones que sólo contienen peticiones de cálculo de tipo ‍L.

• TestA:  ‍35 Puntos ‍

  Pruebas de no más de 200 expresiones que sólo contienen peticiones de cálculo de tipo ‍S.

Observación (no relacionada con el problema)

Si sois capaces de resolver este problema, estáis muy cerca de poder evaluar expresiones lambda. A continuación describimos los pasos necesarios.

Conversión alpha.

El cambio en el nombre de la variable v en expresiones de la forma \v.B crea expresiones equivalentes.

Reducciones beta.

Cualquier expresión de la forma (\x.B A) se reduce a B[x := A], donde puede haber sido necesario aplicar una conversión alpha sobre ||x.B renombrando x en una variable no gastada.

Forma normal.

Una expresión se dice que está en forma normal cuando no pueden aplicarse más reducciones beta a ninguna de sus subexpresiones.