Download Elementos de un lenguaje de programación

Elementos de un lenguaje de
programación
Lenguajes de Programación
1
Que nos brinda el lenguaje
•
•
•
•
•
a+b
que tipos de valores brinda
qué operaciones proporciona
qué significan los símbolos a y b
es legal sumar a y b
• expresiones y funciones
Lenguajes de Programación
2
Little Quilt
• Manipula objetos geométricos
– ancho
– altura
– patrón
• pueden estudiarse y visualizarse de manera
independiente de los constructores del
lenguaje.
Lenguajes de Programación
3
• Los primeros lenguajes de programación,
manejaban: enteros, reales y arreglos de
enteros y reales. Que podía ser visualizados
y estudiados de forma independiente de
cualquier lenguaje.
Lenguajes de Programación
4
• los dos objetos primitivos del lenguaje son
piezas cuadradas con los siguientes
patrones:
• los retazos se pueden girar y coser
Lenguajes de Programación
5
Reglas de retazos
• un retazo es una de las piezas primitivas, o
• se forma girando 90° un retazo hacia la
derecha, o
• se forma cosiendo un retazo a la derecha de
otro de igual altura
• ninguna otra cosa es un retazo
Lenguajes de Programación
6
• los retazos se pueden girar y coser
• los giros conducen a retazos diferentes
Lenguajes de Programación
7
Sintaxis de las expresiones que
denotan retazos
• La primera etapa en la construcción de un
lenguaje es asignar nombres a las piezas
primitivas y a las operaciones sobre retazos.
• Los objetos se llaman a y b ;las operaciones
son giro y costura.
Lenguajes de Programación
8
• Las expresiones complejas se construyen a partir
de expresiones más simples y las más simples
comienzan con los nombres a y b.
• E es una expresión si:
–
–
–
–
–
E es a, o
E es b, o
E es giro (E1) y E1 es una expresión , o
E es costura (E1 , E2) y E1 y E2 son expresiones
Ninguna otra cosa es una expresión.
Lenguajes de Programación
9
Una versión BNF
• < expresión> ::= a
•
|b
•
| giro (<expresión>)
•
| costura (<expresión>),
<expresión>)
Lenguajes de Programación
10
Semántica de las expresiones
• La semántica de las expresiones especifica
el retazo formado por la aplicación de una
expresión. ¿ qué retazo genera la siguiente
expresión ?
– costura (giro (giro ( b ) ), a)
– la respuesta se construye a partir de los retazos
generados por las sub-expresiones {28}
Lenguajes de Programación
11
Funciones definidas por el
usuario
• El universo de las expresiones se expande al
definir funciones de retazos a retazos.
• Las funciones permiten que los retazos se
especifiquen de manera más conveniente.
– girar a la izquierda (giro_iz)
– colocar un retazo encima de otro del mismo
ancho (apila) {29}
Lenguajes de Programación
12
• De esta forma las operaciones pueden
usarse sin que se necesite pensar:
– fun giro_iz (x) = giro(giro(giro(x)))
– fun apila (x,y) = giro_iz (costura (giro (y), giro
(x)))
– ahora se usa giro_iz (E) para cualquier
expresión y puede usarse para declarar otras;
como es el caso de apila.
Lenguajes de Programación
13
Declaraciones locales
• Las expresiones de asignación o
asociaciones de asignación permiten que
las declaraciones aparezcan dentro de las
expresiones.
– let <declaraciones> in <expresión> end
Lenguajes de Programación
14
• Las expresiones de asignación permiten el
uso de nombres en los lenguajes de
programación
– let
–
– in
– end
fun giro_iz (x) = giro(giro(giro(x)))
fun apila (x,y) = giro_iz (costura (giro (y),
giro (x)))
apila (giro_iz (b), giro (b))
Lenguajes de Programación
15
Nombres definidos por el usuario
para valores
• las declaraciones locales convienen cuando se
escriben expresiones grandes en términos de otras
más simples
– val <nombre> = <expresión>
– asigna nombre a una expresión
• y así la declaración de valores se usa junto con las
declaraciones locales
Lenguajes de Programación
16
• let val x = E1 in E2 end
• significa las apariciones del nombre x en E2
representan el valor de E1
• se puede usar cualquier otro nombre en
lugar de x, sin que cambie el significado de
la expresión.
Lenguajes de Programación
17
• let val sup_izq = giro_izq (b)
•
val inf_der = giro (b)
• in
•
apila (sup_izq, inf_der)
• end
• {31}
Lenguajes de Programación
18
Notaciones de expresiones
• Operador binario: necesita dos operandos
– notación infija
• a+b
– notación prefija
• +ab
– notación posfija
• ab +
Lenguajes de Programación
19
Propiedad asociativa y
precedencia
• En notación infija los operadores aparecen entre
sus operandos
– + b *c
– la división y la multiplicación tienen precedencia sobre
la suma y la resta.
– Sin reglas de precedencia, los paréntesis serían
necesarios
– los operadores con la misma precedencia se agrupan de
izquierda a derecha
– 4-2-1 = 1
Lenguajes de Programación
20
• Operadores
– asociativo a la izquierda: si las sub-expresiones que
contienen apariciones múltiples del operador se
agrupan de izq a der; 4-2-1 = (4-2) -1 = 1. Porque la
resta de la izq es la primera en efectuarse.
• +, -, * y /
– asociativo a la derecha: si las sub-expresiones que
contienen apariciones múltiples del operador se
agrupan de der a izq; 234;
• 3 a la 4 = 81
• 2 a la 81
Lenguajes de Programación
21
Declaraciones y aplicaciones de
funciones
• Una vez declarada una función se puede
aplicar como un operador
• funciones como correspondencias
– función es total
– función es parcial
Lenguajes de Programación
22
Función total
• Si se asocia un elemento del conjunto B con
cada elemento del conjunto A; siendo A el
domino y B el contra dominio.
• A  B, para el conjunto de todas las
funciones de A en B. Si f hace corresponder
a y b, escribimos f(a) = b y b se conoce
como el valor de f en a.
Lenguajes de Programación
23
Función parcial
• Una función es parcial si, por cada a en su
domino A, se tiene que f(a) = b, para
alguna b en B, o f(a) se encuentra indefinida
debido a que no existe una b tal que b = f(a)
Lenguajes de Programación
24
Cómo se calcula el valor de f en a
• Es posible definir una función
– enumeración explícita de sus valores para cada
elemento de su dominio.
•
•
•
•
•
Sucesor (0) = 1
Sucesor (1) = 2
Sucesor (2) = 3
Sucesor (3) = 4
...
Lenguajes de Programación
25
• g(x) es el entero n 0 más grande tal que
n2  x
• esta regla no nos indica explícitamente
cómo calcular el valor de g en x
Lenguajes de Programación
26
Funciones como algoritmos
• En cualquier lenguaje de programación una función va de
la mano con un algoritmo para calcular el valor de la
función en cada elemento de su dominio.
• Las declaraciones de funciones tienen 3 partes:
– el nombre de la función
– los parámetros de la función y
– una regla para calcular un resultado a través de los parámetros
Lenguajes de Programación
27
• fun <nombre> (<parámetros - formales>) =
<cuerpo>;
– ejem: fun sucesor (n) = n + 1;
• la notación prefija es la regla para la
aplicación de funciones declaradas:
– <nombre> (<parámetros-actuales>)
– sucesor (2+3) {notación infija}
Lenguajes de Programación
28
• Nombres que se utilizan para designar a los
parámetros:
– parámetro = parámetros formales
– argumento = parámetros actuales
Lenguajes de Programación
29
Evaluación más interna
• Se calcula como sigue:
– se evalúan las expresiones en <parámetros actuales>,
– se substituyen los resultados en los parámetros
formales del cuerpo de la función,
– se evalúa el cuerpo de la función y
– se devuelve el valor de la función como
respuesta
Lenguajes de Programación
30
• Ejemplo:
– sucesor (2 + 3)
•
•
•
•
se activa activa + para evaluar +(2,3)
se devuelve el resultado 5 de +
se activa el sucesor (5) y
se devuelve la respuesta 6
• la técnica de evaluar los argumentos antes del
cuerpo se conoce también como técnica de
invocación por valor
Lenguajes de Programación
31
Evaluación selectiva
• Si <condición> entonces <expresión>1 otro
<expresión>2
• condición da como resultado
verdadero/falso
• expresiones booleanas
• sólo se evalúa una de las expresiones
dependiendo del valor de la condición
falso/verdadero
Lenguajes de Programación
32
Funciones recursivas
• Una función es recursiva si su cuerpo
contiene una aplicación de f
• f es recursiva si f puede activarse a sí misma
• Existen dos tipos de recursión
– lineal
– cola
Lenguajes de Programación
33
Recursión lineal
• Si la activación f(a) de f puede iniciar como
máximo una nueva activación de f.
• ejemlo:
• fun factorial (n) =
– si n = 0 entonces 1 otro n*factorial (n-1);
Lenguajes de Programación
34
• La evaluación de una función recursiva
lineal tiene dos fases:
– una fase de activación, en la cual se inician las
nuevas activaciones, y
– una fase de solución, en la cual el control
regresa de las activaciones con una modalidad
última entrada - primera salida
Lenguajes de Programación
35
Función factorial líneal
• Ejemplo:
– f(3) = 3 * f(2)
–
= 3 * (2*(f (1))
–
= 3 * (2*(1*f(0)))
–
= 3 * (2*(1*1))
–
= 3 * (2*1)
–
= 3 *2
–
=6
Lenguajes de Programación
36
Recursión de cola
• si una función recursiva puede ser eficientes
si se puede implementar con recursión de
cola
• si devuelve un valor sin necesidad de
recursión o si devuleve simplemente el
resultado de una activación recursiva
Lenguajes de Programación
37
• ejemplo:
– fun g (n,a) =
–
si n = 0 entonces a otro g (n-1, n*a)
–
– g (n,a) =
–
a
si n = 0
g(n-1, n*a) en caso contrario
Lenguajes de Programación
38
• g (3,1)
• si 3 entonces 1 otro g(3-1, 3*1)
• g(3,1) = g(2,3) = g(1,6) = g (0,6) = 6
Lenguajes de Programación
39
g(3,1) = g(2,3)
g(2,3) = g(1,6)
g(1,6) = g(0,6)
Función factorial con
recursión de cola
Lenguajes de Programación
g(0,6) = 6
40
• Todo el trabajo de una función lineal con
recursión de cola se realiza en la fase de
activación, cuando se inician las
activaciones nuevas; siendo la fase de
solución trivial debido a que el valor
calculado por la activación final se
convierte en el valor de toda la evaluación.
Lenguajes de Programación
41
• En el caso de f(3) = 3 * f(2)
• la multiplicación se realiza después de que
el control regresa de la activación de f(2).
Lenguajes de Programación
42
Ambito léxico
• EL cambio de nombre no tiene efecto en el
valor de una expresión, siempre y cuando
cambio es consistente
• la re-asignación de nombres se especifica
con precisión mediante la presentación de
una noción de variables locales o acotadas
Lenguajes de Programación
43
• El principio de re-asignación de nombres es
la base para la regla de ámbito léxico, que
ayuda a determinar el significado de los
nombres en los programas.
• fun sucesor (x) = x +1;
• fun sucesor (n) = n +1;
Lenguajes de Programación
44
• surgen ciertas sutilezas cuando una declaración de
función puede hacer referencia a nombres no
locales, es decir , a nombres que no son
parámetros formales, por ejemplo el resultado de
la función sumay depende del valor de y:
• fun sumay (x) = x + y
• como y no es local algún contexto determina su
valor
Lenguajes de Programación
45
• Las reglas de ámbito léxico usan el texto del
programa que rodea a la declaración de la
función para determinar el contexto en el
cual se evaluarán los nombres no locales.
• El texto del programa es estático, a
diferencia de la ejecución, así que tales
reglas se conocen también como reglas de
ámbito estático.
Lenguajes de Programación
46
Utilizaremos let ...
• Para comprender las reglas de ámbito
léxico:
• let val x = 2 in x + x end
• a val se le conoce como una asociación de x
Lenguajes de Programación
47
• let val x = E1 in E2 end
• que todas las apariciones de x en E2 se
encuentran dentro del ámbito de esta
asociación
• el valor de una expresión no se altera si se
cambia de variable
• let val z = E1 in E2 end
Lenguajes de Programación
48
• Caso de asociaciones anidadas de la misma
variable
• let val x = 2 in val x = x + 1 in x *x end end
Lenguajes de Programación
49
• Se aplica una reasignación de nombres de la
asociación más interna
• let val x = 2 in val y = x + 1 in y *y end end
Lenguajes de Programación
50
Tipos
• El tipo de una expresión nos indica los
valores que esta puede representar y las
operaciones que pueden aplicarse
• es posible sumar los enteros y no los
booleanos
Lenguajes de Programación
51
• un principio de diseño de lenguajes de uso extendido es:
toda expresión debe tener un tipo único y lo que
proporciona un mecanismo para clasificar expresiones
• la única estructura de los datos dentro de la máquina es su
disposición física en memoria
• mismas secuencias de bits pueden ser identificada de
manera diferente por distintos programas:
– entero,
– secuencia de caracteres, o
– como instrucción de máquina
Lenguajes de Programación
52
• Por ejemplo el patrón de bits para el carácter @,
puede ser el mismo patrón de bits que el del
número 64.
• Tal flexibilidad es una característica de las
máquinas de propósito general y una invitación a
la equivocación de los programadores ya que las
máquinas no verifican que que las expresiones se
utilicen como se definen
Lenguajes de Programación
53
• Los tipos en los lenguajes de programación
surgen de necesidades en diferentes niveles:
– nivel de máquina
– nivel de lenguaje
– nivel de usuario
Lenguajes de Programación
54
Nivel de máquina
• Los valores proporcionados directamente por una
máquina pueden clasificarse en tipos básicos:
enteros, caracteres, reales y booleanos. Debido a
que la instrucción de máquina para sumar enteros
suele ser diferente que la instrucción para sumar
reales; los compiladores necesitan información
sobre el tipo para generar expresiones en código
de máquina.
Lenguajes de Programación
55
Nivel de lenguaje
• Además de los tipos básicos, los lenguajes
proporcionan tipos estructurados: arreglos,
registros y listas; que se construyen a partir de
tipos más simples. Los tipos estructurados se usan
para definir las estructuras de datos que
manipulará un programa. El constructor de tipos
es un constructor del lenguaje para definir un tipo
estructurado.
Lenguajes de Programación
56
Nivel de usuario
• Los tipos definidos por el usuario son
grupos de datos con nombres y funciones.
Son los TAD’s que permiten al usuario
enriquecer el lenguaje definiendo tipos que
se adaptan al problema que debe resolverse.
Lenguajes de Programación
57
Tipos estructurados
• A través de la teoría de conjuntos se presentan los
tipos estructurados
• se supone la existencia de algunos conjuntos
básicos:
–
–
–
–
–
bool
color
entero
caracteres
real
{verdadero, falso}
{rojo, blanco, azul}
los enteros
un conjunto de caracteres
un conjunto de números reales
Lenguajes de Programación
58
• Y de tres constructores de conjuntos:
– producto
– función
– secuencia
• la descripción de cada constructor consata de tres
partes:
– la sintaxis
– los elementos del conjunto construido, y
– algunas operaciones para examinar la estructura de los
elementos del conjunto construido
Lenguajes de Programación
59
Producto
• El producto A x B de dos conjuntos contiene pares
ordenados que se escriben como (a,b)
• así el conjunto bol x color tiene seis elementos:
– {(verdadero, rojo), (verdadero, blanco), (verdadero,
azul), (falso,rojo), (falso, blanco), (falso, azul)}
• el conjunto enero x entero
– contiene pares de enteros
Lenguajes de Programación
60
• Asociados con el constructor x se encuentran las
operaciones:
– primero y segundo
– ejemplo : primero (verdadero, azul) = verdadero
– ejemplo : segundo (verdadero, azul) = azul
• operaciones se llaman funciones de proyección
• Un producto de n conjuntos A1xA2 x ...x An
– tuplas (a1,a2, ... an) donde ai es un elemento del conjunto
Ai
Lenguajes de Programación
61
• Función: el conjunto de todas las funciones del
conjunto A al conjunto B se denota:
– A  B aplicación
– la única operación asociada con el conjunto A  B es la
aplicación  toma una f de A  B y un elemento de a
de A y devuelve un elemento de b de B.
– La notación usual para la aplicación de f a a es f(a)
Lenguajes de Programación
62
• Ejemplo : el conjunto color  bool
– consiste en todas las funciones del conjunto color
aplicadas al conjunto bool
– como el conjunto color tiene tres elementos y bool dos,
existen 23 = 8 de esas funciones, una de ellas es la
función que satisface las siguientes igualdades:
• f(rojo) = falso
• f(blanco) = falso
• f(azul) = verdadero
Lenguajes de Programación
63
• Por convención el constructor producto (x) tiene
mayor precedencia que el constructor d función
aplicación () de tal forma que:
– entero x entero  entero
• es el conjunto de todas las funciones de pares de enteros a
enteros
• dentro de estas funciones se encuentran (+, -, *); para
enteros)
– ejemplo: la función + aplicada al par (2, 3) le hace corresponder
el entero 5.
Lenguajes de Programación
64
• Ejemplo el conjunto entero x entero
 bool
– es el conjunto de todas las funciones de pares
de enteros a () booleanos
– estas funciones pueden ser los operadores
relacionales (,,,,,) para comparar
enteros.
Lenguajes de Programación
65
• Secuencias: la cerradura de Kleene o
cerradura estrella de un conjunto A, que se
denota con A*, esta constituida por todas las
tuplas que pueden formarse con los
elementos de A
– ejemplo color* es el conjunto
• {( ),(rojo), (blanco), (azul), (rojo, rojo), (rojo,
blanco), (rojo, azul), ...}
Lenguajes de Programación
66
• La cerradura Kleene se relaciona con los
constructores de listas en los lenguajes de
programación funcionales, donde una lista es una
secuencia finita de elementos.
– Operaciones de listas: nula (sabes si es nula), cabeza
(extrae el primer elemento), cola (extrae el resto de los
elementos)
Lenguajes de Programación
67
• Sistemas de tipos: en un lenguaje es el conjunto de
reglas para asociar tipos a expresiones del lenguaje
– el sistema de tipos rechaza una expresión si esta no se
encuentra asociada a un tipo
– ejemplo FORTRAN, donde una expresión es tanto una
variable como una constante o se forma aplicando los
operadores: +, -, * o / a dos sub - expresiones. El tipo
de una expresión es entero o real
Lenguajes de Programación
68
• Una expresión tiene tipo ssi se cumple una de las
siguientes reglas:
– los nombres de variables que comienzan entre I ..N son
de tipo entero. Todos los demás nombres tienen tipo
real. Ejem. Contador es de tipo real
– Un número tiene tipo real si contiene un punto decimal;
en caso contrario tiene tipo entero
– la clasificación de variables y constantes se extiende a
las expresiones
Lenguajes de Programación
69
• Si las expresiones E y F tienen el mismo
tipo entonces:
–
–
–
–
E+F
E-F
E*F
E/F
• son expresiones del mismo tipo
Lenguajes de Programación
70
• Y que sucede cuentan con tipos distintos ..
– Al no cumplir las reglas se rechaza la expresión
• La principal diferencia entre el sistema de tipos de
FORTRAN y Modula - 2 y C y otrs lenguajes
– es la declaración explícita, que especifiquen el tipo de
una varaible
Lenguajes de Programación
71
• En el centro de todos los sistemas de tipos
se encuentra la siguiente regla para la
aplicación de funciones:
– el símbolo  es un constructor de función, de
modo que S  T es el tipo de una función que
va del tipo S al tipo T:
• Si F es una función de tipo S  T y a tiene tipo S,
entonces f(a) tiene tipo T.
Lenguajes de Programación
72
Variantes de la regla
• Operadores aritméticos: existe una regala asociada
a cada operador op que especifica una expresión E
op F en términos de los tipos E y F
– si E y F son de tipo entero, entonces
E mod F es también de tipo entero
– si mod es una función de tipo entero x entero, y
el par (E,F) es de tipo entero x entero, entonces
mod (E,F) tiene tipo entero
Lenguajes de Programación
73
• Sobrecarga: los operadores familiares
como + y *; tienen sobrecarga, es decir
poseen significados diferentes en diferentes
contextos:
– +: entero x entero  entero
– +: real x real  real
Lenguajes de Programación
74
• Reglas para re-definir un operador
sobrecargado:
– si E y F son de tipo entero entonces
E + F es de tipo entero
– si E y F son de tipo real entonces
E y F son de tipo real
Lenguajes de Programación
75
• Coerción: el sistema de tipos original de
FORTRAN rechazaba expresiones como X
+ I y 2 * 3.142, esta restricción se eliminó
en versiones posteriores ...la expresión
anterior es manejada como 2.0 * 3.142; lo
que hace que el entero 2 se convierta en real
antes de la multiplicación (IMPLICIT
NONE).
Lenguajes de Programación
76
• Polimorfismo: esta función tiene un tipo
parametrizado, conocido también como tipo
genérico.
Lenguajes de Programación
77
Los tipos se usan para la
verificación de errores
• la verificación de Tipos asegura que la de un
programa se apliquen de manera apropiada
• el propósito de la verificación es prevenir errores,
si un programa se ejecuta sin errores de tipo, tiene
seguridad de tipos.
• los programas se verifican estáticamente, hasta
donde es posible; sólo una vez durante la
traducción del texto fuente
Lenguajes de Programación
78
• La verificación dinámica se realiza insertando
código extra en el programa para encontrar errores
inminentes.
– El código extra ocupa espacio y tiempo, lo que significa
que es menos eficiente en tiempo de ejecución.
– Los errores pueden esconderse hasta que son
alcanzados pro la ejecución.
– Los programas grandes suelen tener porciones que se
ejecutan rara vez, así que se puede utilizar mucho
tiempo antes que la verificación dinámica lo detecte.
Lenguajes de Programación
79
• La verificación estática es efectiva y la dinámica
muy cara. Así que la mayoría de los compiladores
sólo hacen verificación estática.
• Las propiedades que dependen de valores
calculados como en tiempo de ejecución como la
división por cero, o los índices de arreglos que se
encuentran dentro de los límites; se verifican muy
rara vez.
Lenguajes de Programación
80
• los términos estricto y no estricto se refiere a la
efectividad con la cual un sistema de tipos evita
errores
• un problema que se puede presentar con un
sistema verificador de tipo estricto es que
rechazará muchos programas
• lo ideal es que un lenguaje tenga verificación
estática usando un sistema de tipos poderoso y
estricto
Lenguajes de Programación
81