Monografías Plus      Agregar a favoritos      Ayuda      Português      Ingles     

Cálculo de Lambda

Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com
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
Monografias.com
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)
Monografias.com
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) ? u?x.u
Monografias.com
Aplicación de Funciones ?: Ejemplos (?x.(xx))z ? ? (?x.?y.x y)z ? ? (?x.(x ?y.y))?u.v ? ?
Monografias.com
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
Monografias.com
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
Monografias.com
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
Monografias.com
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 ?.
Monografias.com
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.
Monografias.com
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
Monografias.com
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: z?w.(?u.zxu)?v.wv ? z(?w.(?u.zxu)(?v.wv))
Monografias.com
Desambiguación explícita de expresiones, II Se marcan como desambiguadas las variables que no están en la cabecera de una función ?: z(?w.(?u.z x u)(?v.w v))
Monografias.com
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)))
Monografias.com
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)))
Monografias.com
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))))
Monografias.com
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
Partes: 1, 2

Página siguiente 

Comentarios


Trabajos relacionados

  • Pitagoras y el pitagorismo

    Biografía de pitagoras. Armonía de los contrarios. La comunidad pitagorica. Nació hacia el año 578 ac. En samos (rival ...

  • Filósofos de la naturaleza

    Sócrates. La Política. Enseñanzas. El juicio. Tales de Mileto. Platón: Obra; Teoría de las ideas; Teoría del conocimien...

  • Eutanasia

    Definición del término eutanasia. Eutanasia: ¿Existe un derecho a morir?. Formas de aplicación de la eutanasia. La batal...

Ver mas trabajos de Filosofia

 
 

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.

Iniciar sesión

Ingrese el e-mail y contraseña con el que está registrado en Monografias.com

   
 

Regístrese gratis

¿Olvidó su contraseña?

Ayuda