Prolog Calculo Lambda
Páginas: 8 (1837 palabras)
Publicado: 14 de octubre de 2012
PARADIGMAS DE PROGRAMACIÓN
2006 CALCULO LAMBDA
CALCULO LAMBDA
El cálculo lambda fue desarrollado por Alonso Church en la década del 30 con el objeto de dar una teoría general de las funciones. El cálculo lambda ha sido empleado como fundamento conceptual de los lenguajes de programación, aportando: una sintaxis básica una semántica para el concepto de función como proceso de transformaciónde argumentos en resultados un medio para definir primitivas de programación
SINTAXIS DEL CALCULO LAMBDA La sintaxis del Cálculo Lambda ( CL ) es la siguiente:
::= | . | ( )
En esta sintaxis no existe el concepto de o ¿Qué implica esto? El formalismo no tendrá primitivas, no nos permitirá emplear funciones con el concepto de módulos abstractos.
En esta nueva sintaxis laabstracción funcional es: Cuerpo de la abstracción funcional
.
Lista de argumentos
La sintaxis propuesta utiliza la representación de Funciones con un sólo argumento. Una Función que requiera más de un argumento se representa de la sgte. forma:
x1. x2. .... xn. M
CALCULO LAMBDA Tiene por objeto explicitar el concepto que representa el empleo de funciones como medio de transformación deargumentos en resultados.
A este formalismo lo denominamos CÁLCULO, ya que el mismo empleará un conjunto de axiomas, y reglas de inferencia (de la misma forma que lo utilizan los sistemas formales) para representar el medio de transformación mencionado.
REGLAS DEFINIDAS EN EL CL De acuerdo a la sintaxis propuesta, una aplicación funcional tendrá el siguiente formato (M N) la cual producirá unresultado, como consecuencia de la correspondiente regla del cálculo, R La consistencia del sistema requiere que la aplicación funcional y el resultado puedan ser interpretadas como expresiones equivalentes (M N) R es decir, que representan el mismo valor. (resultado)
El cálculo del resultado de una aplicación funcional será obtenido mediante la generación de expresiones equivalentes poraplicación de las reglas del cálculo que definiremos a continuación. La relación de equivalencia entre expresiones del cálculo tendrá las propiedades: reflexividad simetría transitividad M=M M=N M=N N=M N=P M=P
más las siguientes, que resultan lo suficientemente intuitivas M=N M=N M=N (M P) = (N P) (P M) = (P N) x.N= x.M
La regla del cálculo que permite generar expresiones que satisfagan larelación de equivalencia se denomina
Regla Beta
La Regla Beta establece como sustituir en el cuerpo de la abstracción funcional cada ocurrencia de la variable que hace de argumento nominal por el argumento efectivo de la aplicación funcional correspondiente. 1 ( (x) exp(2 * x + y) (4) ) 2 argumento nominal argumento efectivo La regla Beta especifica los pasos 1 y 2
Esta idea es recogida por laRegla Beta expresada de la siguiente forma
( x .M N) = [N/x] M
la parte derecha de la expresión se interpreta como:
“el término que se obtiene de introducir N en lugar de x, toda vez que x ocurre libre en M”
OCURRENCIA DE UN TERMINO Definición. Ocurrencia de P en Q Clausura P ocurre en P Inducción Si P ocurre en M o N P ocurre en (M N) P ocurre en x.M Si P ocurre en M o P es igual a xPor ejemplo, dado en el siguiente término: ( (x y) x.(x y) ) (x y) ocurre dos veces x ocurre tres veces y ocurre dos veces
Los conceptos que necesitamos a continuación son los de ocurrencia libre y ligada de un variable. Definición. Una ocurrencia de la variable x en un término P es ligada sí y solo sí, x ocurre en un subtérmino de P de la forma x.M Si se aplica esta definición en elsiguiente término ( y.(y y) x.(x y)) x e y ocurren ligadas ya que el término contiene los subtérminos y.(y y) y ocurre ligada (3 veces) x.(x y) x ocurre ligada (2 veces)
Definición. La variable x ocurre libre en en término N, solamente sí: 1. N = x 2. N = z.M tal que x z, y x ocurre libre en M 3. N = (P Q) donde x ocurre libre en M y/o en P Definición. Si x ocurre libre al menos un vez en un...
2006 CALCULO LAMBDA
CALCULO LAMBDA
El cálculo lambda fue desarrollado por Alonso Church en la década del 30 con el objeto de dar una teoría general de las funciones. El cálculo lambda ha sido empleado como fundamento conceptual de los lenguajes de programación, aportando: una sintaxis básica una semántica para el concepto de función como proceso de transformaciónde argumentos en resultados un medio para definir primitivas de programación
SINTAXIS DEL CALCULO LAMBDA La sintaxis del Cálculo Lambda ( CL ) es la siguiente:
::= | . | ( )
En esta sintaxis no existe el concepto de o ¿Qué implica esto? El formalismo no tendrá primitivas, no nos permitirá emplear funciones con el concepto de módulos abstractos.
En esta nueva sintaxis laabstracción funcional es: Cuerpo de la abstracción funcional
.
Lista de argumentos
La sintaxis propuesta utiliza la representación de Funciones con un sólo argumento. Una Función que requiera más de un argumento se representa de la sgte. forma:
x1. x2. .... xn. M
CALCULO LAMBDA Tiene por objeto explicitar el concepto que representa el empleo de funciones como medio de transformación deargumentos en resultados.
A este formalismo lo denominamos CÁLCULO, ya que el mismo empleará un conjunto de axiomas, y reglas de inferencia (de la misma forma que lo utilizan los sistemas formales) para representar el medio de transformación mencionado.
REGLAS DEFINIDAS EN EL CL De acuerdo a la sintaxis propuesta, una aplicación funcional tendrá el siguiente formato (M N) la cual producirá unresultado, como consecuencia de la correspondiente regla del cálculo, R La consistencia del sistema requiere que la aplicación funcional y el resultado puedan ser interpretadas como expresiones equivalentes (M N) R es decir, que representan el mismo valor. (resultado)
El cálculo del resultado de una aplicación funcional será obtenido mediante la generación de expresiones equivalentes poraplicación de las reglas del cálculo que definiremos a continuación. La relación de equivalencia entre expresiones del cálculo tendrá las propiedades: reflexividad simetría transitividad M=M M=N M=N N=M N=P M=P
más las siguientes, que resultan lo suficientemente intuitivas M=N M=N M=N (M P) = (N P) (P M) = (P N) x.N= x.M
La regla del cálculo que permite generar expresiones que satisfagan larelación de equivalencia se denomina
Regla Beta
La Regla Beta establece como sustituir en el cuerpo de la abstracción funcional cada ocurrencia de la variable que hace de argumento nominal por el argumento efectivo de la aplicación funcional correspondiente. 1 ( (x) exp(2 * x + y) (4) ) 2 argumento nominal argumento efectivo La regla Beta especifica los pasos 1 y 2
Esta idea es recogida por laRegla Beta expresada de la siguiente forma
( x .M N) = [N/x] M
la parte derecha de la expresión se interpreta como:
“el término que se obtiene de introducir N en lugar de x, toda vez que x ocurre libre en M”
OCURRENCIA DE UN TERMINO Definición. Ocurrencia de P en Q Clausura P ocurre en P Inducción Si P ocurre en M o N P ocurre en (M N) P ocurre en x.M Si P ocurre en M o P es igual a xPor ejemplo, dado en el siguiente término: ( (x y) x.(x y) ) (x y) ocurre dos veces x ocurre tres veces y ocurre dos veces
Los conceptos que necesitamos a continuación son los de ocurrencia libre y ligada de un variable. Definición. Una ocurrencia de la variable x en un término P es ligada sí y solo sí, x ocurre en un subtérmino de P de la forma x.M Si se aplica esta definición en elsiguiente término ( y.(y y) x.(x y)) x e y ocurren ligadas ya que el término contiene los subtérminos y.(y y) y ocurre ligada (3 veces) x.(x y) x ocurre ligada (2 veces)
Definición. La variable x ocurre libre en en término N, solamente sí: 1. N = x 2. N = z.M tal que x z, y x ocurre libre en M 3. N = (P Q) donde x ocurre libre en M y/o en P Definición. Si x ocurre libre al menos un vez en un...
Leer documento completo
Regístrate para leer el documento completo.