cálculo roberto moriyón. cálculo creado por a. church y s.c. kleene en 1930 para establecer una...
Post on 23-Jan-2016
223 Views
Preview:
TRANSCRIPT
Cálculo
Roberto Moriyón
Cálculo
• Creado por A. Church y S.C. Kleene en 1930 para establecer una teoría formal de funciones computables
• Permitió demostrar por primera vez un teorema de indecibilidad: no hay úna función que permita establecer la equivalencia de dos funciones
• Ha dado lugar a los lenguajes de programación funcionales, como Lisp
Expresiones
• Variables x
E ::= V | … V ::= x | y | z | …
• Funciones y.yy
E ::= V | F | … F ::= V.E
• Aplicación de funciones (y.yy)x
xy x(y.yy) (y.yy) (x.xx)
E ::= V | F | EE | (E)
Funciones
• La operación que da lugar a x.E a partir de una expresión E se llama abstracción
• Ejemplo:
y.yy es una abstracción de yy mediante la variable y
• Semántica: Sustitución
(y.(yzy))x.u (x.u)z(x.u) ux.u
Aplicación de Funciones : Ejemplos
• (x.(xx))z ?
• (x.y.x y)z ?
• (x.(x y.y))u.v ?
Funciones : Semántica, II
• Todas las expresiones representan funciones de un argumento (que a su vez es una función de un argumento), cuyos valores son también funciones de un argumento
• Las expresiones se pueden ver como funciones de dos argumentos:
E1 se puede interpretar como la función que a las expresiones E2 y E3 les hace corresponder la expresión E1E2E3
Funciones : Ejemplos
x.x es la función identidad, que a cada función le hace corresponder ella misma
x.y es la función con valor constante la función y
x.y.x es la función que a cada función x le hace corresponder la función constante x
x.y.y es la función constante identidad
Funciones : Ejemplos, II
x.y.x también se puede ver como una función de dos argumentos x e y: la proyección sobre el primer argumento, 1.– Ejemplo: ((x.y.x)u)z (y.u)z u
• Análogamente, x.y.y se puede ver como la proyección 2.
• En general cualquier expresión se puede ver como una función de un número arbitrario de argumentos
Cálculo : Visión global
• El Cálculo se puede ver como un lenguaje de definición de funciones cuyos únicos tipos de datos primitivos son las funciones (no hay números ni cadenas de caracteres), y que incluye un mecanismo de evaluación de las funciones basado en sustitución de variables por expresiones.
• En particular, todas las funciones tienen un argumento que representa a su vez otra función y sus imágenes son a su vez funciones .
Sintaxis del Cálculo : Precedencia
• La gramática que hemos construido es ambigua
• Se desambigua modificando la gramática, bien sea exigiendo la utilización de paréntesis o en base a precedencias
• Es una situación similar a la que ocurre en la aritmética con las sumas y productos, pero algo diferente porque el operador es prefijo y el operador de aplicación no tiene un símbolo propio.
Sintaxis del Cálculo : Precedencia
• La aplicación de funciones tiene mayor precedencia que la abstracción.– Ejemplo: x.yz es una función cuyo valor
constante es yz, o sea que equivale a x.(yz)
• En caso de aplicaciones consecutivas de expresiones, se asocian por la izquierda– Ejemplo:
(x.y.xy)(u.v)z ((x.(y.(xy)))(u.v))z
Desambiguación explícita de expresiones
• Se pone directamente un paréntesis rodeando a cada función que no lo tiene. El paréntesis se abre inmediatamente antes de la y se cierra lo más a la derecha posible
• Normalmente esto es suficiente para poder leer la expresión sin ambigüedad.
• Ejemplo:zw.(u.zxu)v.wv
z(w.(u.zxu)(v.wv))
Desambiguación explícita de expresiones, III
• Se marcan como desambiguadas las subexpresiones que son concatenación de otras dos ya desambiguadas, agrupándolas de izquierda a derecha mediante paréntesis.
z(w.(u.((zx)u))(v.(wv)))
Desambiguación explícita de expresiones, IV
• Se marcan como desambiguadas las funciones lambda cuyo cuerpo está desambiguado.
z(w.(u.((zx)u)) (v.(wv)))
Desambiguación explícita de expresiones, V
• Las dos reglas anteriores se aplican de forma consecutiva en cualquier orden posible.
z(w.((u.((zx)u))(v.(wv))))z(w.((u.((zx)u))(v.(wv))))
Escritura de expresiones
• La principal precaución al escribir expresiones es cuando se quiere aplicar la composición de dos funciones a otra expresión.
• Por ejemplo, para escribir el resultado de aplicar la expresión E al resultado de aplicar la expresión F a la expresión G, se tienen que poner paréntesis, quedando E(FG). Si escribiéramos EFG sin paréntesis la expresión resultante denotaría lo mismo que (EF)G
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
xy
x
y
v
u
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
xz
x
x
x
z
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:
1. Simplificar
2. 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𝓔 ⟶ ℕ𝓔– 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 . EjemploCá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
top related