LambdaCalculus

El cálculo λ (lambda)

Desarrollado por Alonzo Church en los años de
1930s como un formalismo para expresar
cómputo con funciones
Muchos lenguajes funcionales (ML, Lisp,
Haskell) estan basados en el cálculo lambda
La idea de funciones que acepten funciones
como parámetros viene del cálculo lambda

Alonzo Church
matemático y lógico norteamericano responsable por crear
la base de la computaciónteórica
Profesor de Alan Turing
Tesis de Church – Turing
(funciones computables, la maquina de Turing)
El cálculo lambda es en escencia una forma simple para
denotar funciones y aplicaciones, la idea es aplicar una
función a argumento(s) formando funciones por
abstracción

La sintaxis es simple:
::=
|
| ()
| ( λ . )
son numerosocomo “0” , “1” o funciones
predefinidas como “ + ”, “ * ”
son nombres como x, y.
La tercera regla significa aplicacion de funcion ( f x )
La cuarta regla es la abstracción lambda, para construir
nuevas funciones

La abstraccion lambda
( λ x . ( ( + 1 ) x ) ) ; puede ser reescrita como:
(λx.+1)
Esto es equivalente a ( λ x (+ 1 x ) ) en Scheme
O a un bloque sin nombre con un argumentoen
Smalltalk
es decir, una funcion sin nombre que acepta x
como parámetro, y agrega uno al parametro x

Derivación de ( λ x . ( ( + 1 ) x ) ) :
=> ( λ . )
=> ( λ x .() )
=> ( λ x .( ( ) ) )
=> ( λ x .( ( ) ) )
=> ( λ x .( ( + 1 ) ) )
=> ( λ x .( ( + 1 ) ) )
=> ( λ x .( ( + 1 ) x) )

Aplicación deFunciones
((λx.((+1)x))2)=(λx.+1 x)2
Si llamamos esta función con el parámetro 2:
(λx.+1 x)2
= > (+ 1 2 ) => 3

Los parentesis son necesarios para la aplicación de
funciones para eliminar ambiguedades
De acuerdo con la descripción de la sintaxis:
( λ x . + 1 x ) debería ser escrito como :
(λx.((+1 x))
Para incrementar la legibilidad , se pueden omitir los
parentesis si no presenetan ningunaambiguedad

La operación básica del cálculo lambda es la
aplicación de expresiones:
( ( λ x . + x 1 ) 2 ) es equivalente a ( + 2 1 )
sustituyendo x por 2 y desechando la lambda
Esto es equivalente a aplicar la función con el
argumento 2
Esto es llamado :

La conversion beta

(es el proceso de sustituir una variable ligada en el cuerpo de una abstracción
lambda por el parámetro recibido. Es conocidotambién com ola reducción
beta)

Variables
Una variable x en una expresión ( λ x . E ), se
dice que está ligada a lambda
El alcance de la liga es la expresión E
Una variable no-ligada se dice que es libre
Ejemplo:
(λ x . + x y )
Aquí x es ligada y y es libre

(λx.+xy)2

=> ( + 2 y )

y es como una referencia no-local en esta función
En Scheme:
(define y 5)
((lambda (x) (+ x y )) 2)
;Value 7

EnHaskell
let y = 5
let lam x = x + y
lam 2
7

Las mismas variables pueden aparecer varias veces en
diferentes contextos. Algunas instancias pueden ser ligadas
y otras libres
●

Ejemplo:
(λ x . + ( (λ y . ( ( λ x . * x y ) 2 ) ) x ) y)
La primera x despues del signo * está ligada por un lambda
diferente que la x exterior
La primera instancia de y es ligada, la segunda es libre

Susutitución
(λ x . +( ( λ y . ( ( λ x . * x y ) 2 ) ) x ) y)
=> (λ x . + ( (λ y . ( * 2 y ) ) x ) y)
=> (λ x . + ( ( * 2 x ) ) y)
=> (λ x . + ( * 2 x ) y)

(donde y es libre)

Esta función suma y al producto de 2 con el
argumento. Es decir: (2 * x) + y

Aplicando la Conversion Beta
Paso de valores por valor o por nombre
Paso por valor
(( λ x . ( * x x )) ( + 2 3 ) )
=> ( ( λ x . ( * x x ) ) 5)
=> (* 5 5)
=> 25
Pasopor nombre
(delayed evaluation, outermost evaluation, normal order)
(( λ x . ( * x x )) ( + 2 3 ) )
=> ( * ( + 2 3 )( + 2 3 ))
=> (* 5 5) => 25

El orden de la conversion beta puede afectar el resultado.
Consideremos la expresion: (( λ x . x x) ( λ x . x x))
La sustitución nos dará la misma expresión (ciclo infinito)
Si usamos esta expresión como un argumento para la
funcion:
( ( λ y . 2) ( ( λ...

Leer documento completo

Regístrate para leer el documento completo.