Escritura de expresiones ?, II Más en general, si una expresión se aplica a varios argumentos y uno de ellos es a su vez una expresión no atómica, este argumento se debe poner entre paréntesis. Así, E(FG)H denota (E(FG))H , o sea la aplicación de E a los argumentos FG y H, mientras que EFGH denotaría (((EF)G)H), es decir la aplicación de E a los tres argumentos F, G y H.
Representación de expresiones ? como árboles binarios Una expresión ? se puede representar mediante su árbol binario de análisis sintáctico (sin paréntesis), cuyos nodos pueden ser de tipo ? (abstración), ? (áplicación) o variable (son las hojas) Ejemplo: (?x.?y.x y)(?u.v)z (Gp:) ? (Gp:) ? (Gp:) x (Gp:) y (Gp:) ? (Gp:) x (Gp:) y (Gp:) ? (Gp:) ? (Gp:) ? (Gp:) v (Gp:) u (Gp:) z
Cálculo ?: Ambitos de variables Mínima función ? que la contiene y en la que aparece como argumento. Ejemplos (?x.?y.x y)(?u.v)z (?x.?y.x y)(?u.v)z (?x.?y.x y)(?u.v)z Ámbito global
Es semejante al ámbito en un programa
Cálculo ?: Ambitos devariables, II Si se sustituye en una expresión ? una variable cuyo ámbito no es global por otra nueva, la expresión resultante es equivalente Ejemplo: ?x.zx es equivalente a ?y.zy, pero no es equivalente a ?x.yx ni a ?z.zx
Ámbitos de variables: Ejemplo (?x.?z.x(?x.zx))x (Gp:) ? (Gp:) ? (Gp:) x (Gp:) z (Gp:) ? (Gp:) x (Gp:) ? (Gp:) ? (Gp:) x (Gp:) x (Gp:) ? (Gp:) z (Gp:) x
Ambitos de variables: Ejemplo, II En el ejemplo anterior la variable x tiene ámbitos anidados (el segundo está contenido en el primero, que a su vez lo está en el global), lo que dificulta la sustitución y la evaluación de expresiones. La evaluación de expresiones y la sustitución de variables es más sencilla cuando no hay ámbitos anidados. Al igual que en programación, conviene evitar los ámbitos anidados de variables sustituyéndolas por otras.
Expresiones simples Una expresión ? es simple si cada variable aparece en un solo contexto Esta condición es más fuerte que la exigencia de que no haya ámbitos anidados; es análoga a pedir que en un programa cada variable aparezca en un solo bloque. Ejemplos: (?x.?z.x ?x.z x) z no es simple (?x.?u.x ?y.u y) z es simple
Expresiones simples, II En cualquier expresión ? se pueden renombrar las variables de modo que la expresión resultante, equivalente a la inicial, sea simple Para ello basta con sustituir desde los ámbitos más restringidos a los más amplios las variables con ámbitos múltiples por variables nuevas. Ejemplo: (?x.?z.x ?x.z x) z ? (?x.?z.x ?y.z y) z ? (?x.?u.x ?y.u y) z
Evaluación de expresiones simples Dentro de una expresión simple, la aplicación de una función ? a otra subexpresión se evalúa mediante sustitución, rodeando el argumento de paréntesis si es necesario. Ejemplos: (?x.?u.x ?y.u y) z ? ?u.z ?y.u y (?x.?u.x ?y.u y) ?w.w ? ?u. (?w.w) ?y.u y El resultado de la evaluación de una expresión simple puede no ser simple. Ejemplo: (?x.(?y.x) x) ?u.u ? (?y.?u.u) ?u.u
Procedimiento de evaluación total de expresiones ? Para evaluar una expresión se puede hacer repetidamente lo siguiente: Simplificar Evaluar una subexpresión que sea la aplicación de una función ? a otra expresión, sustituyendo la subexprésión evaluada por el resultado (incluyendo paréntesis alrededor si hace falta).
Procedimiento de evaluación total de expresiones ?: Ejemplo (?x.(?u.x u) x) x ? (?y.(?u.y u) y) x ? (?u.x u) x ? x x Otra forma de hacerlo: (?x.(?u.x u) x) x ? (?y.(?u.y u) y) x ? (?y.y y) x ? x x
Ejercicios obligatorios Evaluar lo más posible las siguientes expresiones: [EVAL1] (?x.?y.x y) (?u.u u) v [EVAL2] (?u.u) (?x.?y.x y) v Pasar a forma simple las siguientes expresiones: [SIMPL1] (?x.?y.x(?x.yx))(?u.uxu)x [SIMPL2] ?x.?x.?x.xxx
EJERCICIO OPTATIVO [EVAL LAMBDA] Escribir un programa que evalúe expresiones ? de la forma (?x.E)F.
No terminación de laevaluación total El procedimiento de evaluación total de expresiones ? puede no terminar nunca. Ejemplo: (?x.xx)(?y.yy) al evaluarla una vez da ella misma: (?y.yy)(?y.yy)
Cálculo ?: Reglas de equivalencia Lo anterior justifica definir la evaluación como una regla de equivalencia. Las siguientes reglas permiten obtener expresiones ? equivalentes a otras dadas: Regla ?: Sustitución de variables por otras (en particular, la conversión en expresiones simples) Regla ? (evaluación): Aplicación de funciones Regla ? (concreción): Equivalencia de ?x.Ex con E si x no es una variable libre de E
Cálculo ?: Forma normal Se dice que una expresión ? está en forma normal si no se le puede aplicar ninguna regla de evaluación o concreción. Según hemos visto, hay expresiones ? que no son equivalentes a ninguna otra que esté en forma normal.
Forma normal, II Hay expresiones ? equivalentes a otra en forma normal que admiten evaluaciones indefinidas de subexpresiones suyas. Ejemplo: (?x.?y.x) u ((?v.v v) ?w.ww) Si se evalúa primero el último paréntesis se obtiene una expresión equivalente a la inicial, y por lo tanto se puede continuar realizando la misma operación indefinidamente. Si se evalúa la primera función ?, se obtiene ?y.u ((?v.vv) ?w.ww), y evaluando de nuevo la primera función ? se obtiene u, que está en forma normal.
Ejercicio obligatorio [FNINF] Demostrar que la siguiente expresión ? admite infinitas evaluaciones consecutivas sin que se llegue a una forma normal, pero también se puede evaluar dando lugar a una forma normal: (?a.?b.b) ((?x.y(x x)) (?u.v(u u)) ?w.w
Unicidad de la forma normal Teorema de Church-Rosser: Si una expresión ? se puede transformar mediante aplicaciones sucesivas de reducciónes ?, ? y ? en dos expresiones en forma normal, éstas se pueden transformar una en la otra mediante transformaciones ?.
Teorema de Church-Rosser:Idea de la demostración Si una expresión ? simple incluye dos aplicaciones de función que se pueden evaluar, el orden de evaluación de las mismas es indiferente. Reducción a tres casos Primer caso: Funciones con ámbitos disjuntos ((?x.xx)u)((?y.yy)v)
Teorema de Church-Rosser:Segundo caso Una de las aplicaciones está contenida en el argumento de la otra:
(?x.xux)((?y.ywy)v) (?x.xux)(vwv)
((?y.ywy)v)u((?y.ywy)v) (vwv)u(vwv)
Teorema de Church-Rosser:Tercer caso Una de las dos aplicaciones está conteni-da en el cuerpo de la función de la otra:
(?x.(((?y.yy)u))xxx)v (?x.((uu)xxx))v
((?y.yy)u)vvv (uu)vvv
Teorema de Church-Rosser:Caso general Análogo a uno de los tres anteriores, con árboles arbitrarios en lugar de u, v, w y en lugar de los cuerpos de las funciones
Cálculo ?: Normalización Teorema de normalización: Dada una expresión ?, si existe otra expresión en forma normal equivalente a ella, se puede obtener mediante evaluación total de izquierda a derecha, como sigue: Si hay alguna subexpresión de la expresión dada que sea una función ? y a la que se le pueda aplicar evaluación o concreción, hacerlo sobre la primera de ellas. Simplificar el resultado y repetir lo anterior sobre las expresiones resultantes mientras ello sea posible.
Potencia computacional del Cálculo ? Se puede representar la lógica booleana y las operaciones aritméticas mediante expresiones ? Idea de la demostración: Ver la hoja de problemas número 1 Forma de la representación: T,F???; ?,?,?,???? 0, S,P,N??? ? N??? Definición de funciones recursivas (+, *, …)
Recursividad en el Cálculo ? Teorema del punto fijo (Turing): Para cada expresión E hay otra expresión F que verifica que EF ? F Demostración: Tomamos F ? (?x.E(xx))(?y.E(yy)) Evaluando la aplicación tenemos que F ? E((?y.E(yy))(?y.E(yy))) ? EF
Recursividad en el Cálculo ?, II Observación: El punto fijo de Turing se calcula aplicando una función fija Y, llamada combinador de punto fijo de Turing, a la función cuyo punto fijo se quiere calcular. Concretamente, F ? YE, donde Y ? ?E.(?x.E(xx))(?y.E(yy)) YE habitualmente no tiene forma normal, pero YEH puede tenerla para algunas H
Definición de funciones recursivas en el Cálculo ? Ejemplo: Suma Definición recursiva primitiva habitual: x+y = (x==0) ? y : ((x-1)+y)+1 La traducimos al Cálculo ? en forma de punto fijo: +xy ? ? (Nx) y (S(+(Px) y)) + ? ?x.?y.? (Nx) y (S(+(Px) y)) ? ? (?G.?x.?y.?(Nx)y(S(G(Px) y)))+
Definición de funciones recursivas en el Cálculo ?, II La solución sería el punto fijo asociado: + ? YE ? Y(?G.?x.?y.?(Nx)y(S(G(Px)y))) Si sustituimos Y por su valor obtenemos una expresión sin forma normal (cada evaluación la complica más) Pero si aplicamos la expresión anterior a dos números como S(S0) y S(S0) se obtiene una expresión con forma normal: S(S(S(S(0))))
Cálculo de los valores de funciones recursivas en el Cálculo ?. Ejemplo Cálculo de 2+2: Se puede hacer mediante evaluación total partiendo de la expresión que representa 2+2, que es (YE)22, donde Y ? ?F.(?u.Fuu)(?v.Fvv) E ? ?G.?x.?y.?(Nx)y(S(G(Px)y)) 2 ? … es decir (?F.(?u.F(uu))(?v.F(vv)))(?G.?x.?y.?(Nx)y(S(G(Px)y)))…
Cálculo de los valores de funciones recursivas en el Cálculo ?. Ejemplo Sustituyendo a medias y evaluando, +22 ? E+22 ? ?(N2)2(S(+(P2)2) ? S(+(P2)2) ? S(+12) +12 ? E+12 ? ?(N1)2(S(+(P1)2) ? S(+(P1)2) ? S(+02) +02 ? E+02 ? ?(N0)2(S(+(P0)2) ? 2 +12 ? S2 ? 3 +22 ? S3 ? 4
Ejercicios Definir funciones en el Cálculo ? que representen las siguientes funciones: [LRS] Suma de los n primeros números impares (obligatorio) [LRP] Producto de dos números [LRF] Factorial de un número [LRC] Cociente por defecto de dos números Mostrar el cálculo de la suma de los dos primeros números impares, 2*2, 3! y 5/2
Cálculo ?: Conclusión El Cálculo ? es tan potente como el cálculo de funciones recursivas, es decir tan potente como las máquinas de Turing, como las gramáticas, etc
| Página siguiente |