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) ? u?x.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: z?w.(?u.zxu)?v.wv ? z(?w.(?u.zxu)(?v.wv))
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))
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
| Página siguiente |