miércoles, 17 de noviembre de 2010

Cálculo Lambda (puntos extras)

Hola compañeros hoy les hablare un poco acerca del Cálculo Lambda

Este Cálculo Lambda fue desarrollado en los 30's por Alonso Church con la finalidad de dar una teoría general a las funciones.

Este ha sido empleados como un fundamento conceptual de los lenguajes de programación aportando:

  • Una semantica para el concepto de funciones como proceso de transformación de argumentos en resultados
  • Un medio para definir primitivas de programación 
  • Una sintaxis básicas
La sintaxis del cálculo Lambda es así 



         

El calculo Lambda tiene como objetivo explicar como se representan las funciones como medio de transformación de argumentos de resultados.
Devido a esto se le llamo "Calculo" ya que en este se emplean un conjunto de axiomas y reglas de inferencia.

Este calculo tiene reglas que de acuerdo a la sintaxis propuesta, una aplicación funcional tiene que tener el siguiente formato:

( M N )

por lo cual esto obtendrá un resultado "R" y la consistencia del sistema requiere que sean equivalentes (M N) = R es decir que tengan el mismo valor.

La Regla Beta 

Esta regla dice como sustituri en el cuerpo de la abstracción funcional cada ocurrencia de la variable que se hace de argumento nominal por el argumento efectivo de la aplicación funcional correspondiente.

Regla Beta: Definición de Sustitución 

En elcaso en que M sea la variable a sustituir, se relaciona de la siguiente manera:

[N/x] x :=: N

En el caso de la M siendo una variable, pero diferente de la sustituida, se realiza de la siguiente manera:

[N/x]y :=: y ; y≠x

Un ejemplo de esto seria el siguiente:


Esta idea es recogida por la Regla Beta expresada de la siguiente forma


La parte derecha de la expresión se puede decir como "El termino de que produce al introducir N en lugar de x, toda vez que ocurre libre M"

Ocurrencia de un Termino

Como definición es la ocurrencia de P en Q

Si P ocurre en M o N = P ocurre en (M N)
Si P ocurre en M o P es igual a x = P ocurre en λx.M

( (x y) λx.(x y) )
(x y) ocurre dos veces
 x ocurre tres veces 
 y ocurre dos veces


Una ocurrencia de la variable x en un término P y es ligada sí y solo sí, x ocurre en un subtérmino de P de la forma λx.M


Este es solo un poco acerca de la que es el Calculo Lambda, aquí abajo les dejare páginas con mas información acerca del mismo.



Gracias :)


1 comentario: