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  |