Download Fundamentos de Lenguajes de Programación Contenido del curso

Contenido del curso
Fundamentos de Lenguajes de
Programación
MC Mireya Tovar Vidal
FCC- BUAP
Cubículo 5
mtovar@cs.buap.mx
Horario de atención:
martes 11:00-12:00
Cálculo lambda sin tipos
Cálculo lambda con tipos
PFC
Lenguaje de programación funcional
Bibliografía
Evaluación
Lambda Calculi with types
3 exámenes parciales 60%
Henk Barendregt.
Handbook of Logic in Computer Science, Volume II.
Oxford University Press.
Foundations for Programming Languages,
J. C. Mitchell,
MIT Press, 1996
Tareas y ejercicios 20%
Programas y proyecto final 20%
Introducción
Definición de un lenguaje
Un lenguaje de programación es un medio para comunicarse
Imperativos
Orientados a objetos
Funcional
Lógicos
como programas válidos.
Teoría de lenguajes formales bien desarrolladas (Chomsky)
Notación BNF
Sintaxis
Descripción del conjunto de secuencias de símbolos considerados
con una computadora que proporciona las facilidades
necesarias para la programación
Sistema de tipos
Propósito: prevenir errores en tiempo de ejecución
Análisis de tipos en tiempo de compilación
Análisis de tipos en tiempo de ejecución
Semántica
Descripción del significado de instrucciones y expresiones
Formal: axiomática, operacional o denotacional.
Introducción
Programación funcional
En 1936 se introdujeron dos modelos computacionales:
Alan Turing inventó la máquina de Turing y la noción de
función computable en sus máquinas.
Alonzo Church inventó un sistema formal llamado Cálculo-λ
y la noción de función computable en su sistema.
Los lenguajes imperativos como Pascal, C, etc., así como el
lenguaje ensamblador están basados en la máquina de Turing.
Los lenguajes funcionales como ML, Miranda, Haskell etc.,
están basados en el cálculo- λ.
Proporcionan muchos recursos expresivos ausentes en otros LP:
Funciones como ‘ciudadanos de 1ª clase’
2. Sistema de tipos
3. Ausencia de efectos laterales, sin variables globales
4. Evaluación perezosa
Los programas funcionales son pequeños y fáciles de mantener
Los programas funcionales permiten utilizar técnicas de
razonamiento formal
La capacidad computacional de los lenguajes funcionales es
equivalente a la de la máquina de Turing
1.
Sintaxis
Un término e se define como:
Calculo lambda
e
Objetivo
Introducir el cálculo- λ y mostrar como este sistema captura todas
las funciones computables.
Ejemplo
::= x
(identificador)
|
e0 e1
(aplicación)
|
λx. e
(abstracción)
En una abstracción:
x es el argumento
e es el cuerpo de la función
Asociaciones
Función identidad:
λx. x
El nombre después de λ es el identificador del argumento de esta
función.
La expresión después del punto es el “cuerpo” de la definición.
Término válido, correspondiente en Java
public int id(int x){return x;}
Término válido, correspondiente en C:
int id(int x){return x;}
LMN
Se asocia hacía la izquierda
((LM)N)
λx. λy. M
Se asocia hacia la derecha
(λx. (λy. M))
λx. λy. xyz
Una aplicación tiene precedencia
sobre una abstracción
λx. λy.(( x y) z)
Si M, N son las expresiones
M≡
λx.x
N≡y
Respectivamente entonces
MN = (λx.x) y
Y no
λx. ( x y )
Ejercicios
Más reglas
Decidir si son términos bien formados y asociar
λx.λy. xyλz.z
λx.λy.λz.xzyz
Para simplificar la notación los siguientes términos se tomarán
como equivalentes:
λx1.(λx2.(…(λxn.M)…)) es lo mismo que
λx1x2…xn.M
λx.λy.λz.xz(yz)
λx.λy.λz.x(zy)z
Simplificar:
λx.λy. xyλz.z
λx.λy.λz.xzyz
λx.λy.λz.xz(yz)
λx.λy.λz.x(zy)z
Expresiones y funciones
Alcance
Expresiones
En calculo- λ todos los nombres son locales a las
x+y
x + 2*y + z
Funciones
λx. (x+y)
definiciones
λx.t : El alcance de x es el término t
λz. (x + 2*y + z)
Una ocurrencia de la variable x se dice que esta acotada
cuando está ocurre en el cuerpo t de una abstracción λx.t
(λx. y x)(λy. x y)
Aplicación
(λx. (x+y)) 3
= 3+y
(λz. (x + 2*y + z)) 5 = x + 2*y + 5
libre
Parsing: λx. f (f x) = λx.( f (f (x)) )
acotada
acotada
libre
Variables libres y acotadas
Variables
En la función λx.x se dice que x esta “acotada” si sus
El conjunto de variables libres se define de manera inductiva
ocurrencias en el cuerpo de la definición es precedida por λx.
Si no es precedida por un λ se llama “variable libre”.
(λx. y x)(λy. x y)
como:
FV(x)={x}
FV(λx.M)= FV(M) -{x}
FV(M1M2)=F V(M1) ∪ FV(M2)
El conjunto de variables acotadas se define de manera
inductiva como:
libre
BV(x)= ϕ
BV(λx.M)=BV(M) ∪ {x}
BV(M1M2)= B V(M1) ∪ BV(M2)
Ejemplos
Términos cerrados
FV(λx. x (λy.x y z)) = {z}
Un término M se llama cerrado si FV(M)= ϕ. En caso
FV(λx. ((λy. y+2) x) + y ) = {y}
contrario el término se conoce como abierto.
BV(λx. x (λy.x y z)) = {x, y}
BV(λx. ((λy. y+2) x) + y ) = {x, y}
Note que los conjuntos de variables acotadas y libres no son
necesariamente disjuntas; por ejemplo:
x (λxy. x)
Subtérminos
Ejercicios
Subtérmino de un término
Calcular el conjunto de variables libres, acotadas y
Un subtérmino de un término- es alguna parte del término
que esta bien formada de acuerdo a la gramática. El conjunto
de subtérminos se puede define de manera inductiva como:
Sub:: T → P( T)
Sub(x)={x}
Sub(λx.M)=Sub(M) ∪{(λ x.M)}
Sub(M1M2)=Sub(M1) ∪ Sub(M2) ∪ {M1M2}
subtérminos de las siguientes expresiones λ
λx. x(λy.xyz)
λx.λy. xyλz.z
λx.λy.λz.xzyz
λx.λy.λz.xz(yz)
λx.λy.λz.x(zy)z