Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Cálculo de Lambda (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

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.

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

Á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

Monografias.com

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.

Monografias.com

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

Monografias.com

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

Monografias.com

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

Monografias.com

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).

Monografias.com

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

Monografias.com

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

Monografias.com

EJERCICIO OPTATIVO
[EVAL LAMBDA] Escribir un programa que evalúe expresiones ? de la forma (?x.E)F.

Monografias.com

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)

Monografias.com

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

Monografias.com

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.

Monografias.com

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.

Monografias.com

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

Monografias.com

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 ?.

Monografias.com

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)

Monografias.com

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)

Monografias.com

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

Monografias.com

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

Monografias.com

Monografias.com

Monografias.com

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.

Monografias.com

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 (+, *, …)

Monografias.com

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

Monografias.com

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

Monografias.com

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)))+

Monografias.com

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))))

Monografias.com

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)))…

Monografias.com

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

Monografias.com

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

Monografias.com

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

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter