Capítulo II Conceptos Fundamentales de Lenguajes de Programación

2.1 Sintaxis y Semántica Descripción de sintaxis y semántica, análisis sintáctico y semántico

1

Definición: Sintaxis y Semántica • SINTAXIS: forma de expresiones, sentencias y unidades de programa • SEMÁNTICA: significado de estas expresiones, sentencias y unidades de programa • Ejemplo: while () do

Elementos Sintácticos • • • • • • • •

Conjunto de carácteres Identificadores Símbolos de operadores Palabras claves y reservadas Comentarios Blancos, delimitadores y paréntesis Expresiones Sentencias

2

Descripción de Sintaxis • Definición de Lenguajes – Reconocimiento (reconoce si string de entrada pertenece al lenguaje) – Generación (genera strings que pertenecen al lenguaje)

• Métodos formales de descripción – Backus Naur Form (BNF) – Extended BNF (EBNF)

Elementos de BNF • Símbolos no terminales – Abstracción que representa una regla

• Símbolos terminales – Tokens de las reglas

• Símbolo de partida – Símbolo no terminal que permite generar un programa

3

Ejemplo de Gramática

::= begin end ::= begin ; end | NULL id> :=

Parse Tree • Expresión

A := A*B + C stmt

id

exp

:=

A exp

exp

+

exp

*

exp

id

id

id

A

B

C

4

Ambigüedad • Para la expresión A := A*B + C existen dos parse tree: stmt

id

stmt

id

exp

:=

A

exp

:= exp

A

*

exp

exp

+

*

exp

id

id

exp

id

C

A

id

id

B

C

exp id

exp

B

A

+

exp

Otro ejemplo de ambigüedad: Dada la siguiente gramática: ::=

if then | if then else



| …

::=

if (C1) then if (C2) then S1 else S2

Reconocer: if_stmt

if

condition

if_stmt

then

stmt

if

then

condition

if_stmt

if

condition

then

stmt

else

stmt

if_stmt

stmt

else

stmt

if

condition

then

stmt

5

Resolución de Ambigüedad • Caso de operadores: – Definir precedencia – A igual precedencia, definir asociatividad por izquierda o derecha

• Caso del if: – Asociar el else con el último if

Extended BNF (EBNF) • Elemento opcional se indica con [ …] • Alternativa puede usar | en una regla • Repetición de elementos se indican con { … }

6

Ejemplos de EBNF ::= if then [ else ] ::= { | }

Grafos Sintácticos

::=

if then { } [ else ] end if



::=

elseif then

else_stmt

condition

if

stmts

then

end if else_if

else_if

elseif

else

condition

stmts

then

stmts

7

Proceso de Compilación Programa Fuente AnálisisLéxico Léxico Análisis Tokens léxicos AnálisisSintáctico Sintáctico Análisis Parse tree Tabla de símbolos

Reconocimiento del programa fuente

AnálisisSemántico Semántico Análisis Código intermedio Generaciónde deCódigo Código Generación Programa Objeto

2.2 Nombres, Ligado y Ámbito Ligado estático y dinámico, reglas de ámbito y prueba de tipos.

8

Conceptos • • • • •

Nombres e Identificadores Variables Tipos Ámbito Constantes

Nombres • Identificador que designa en el lenguaje un elemento u objeto de programa – (e.g. variable, tipo, constante, función, etc.)

• Aspectos de diseño: – Largo (con significativo) del nombre – Tipos de caracteres aceptados (e.g. conector _) – Sensibilidad a mayúsculas y minúsculas – Palabras reservadas

9

Variables • Abstracción de un objeto de memoria, que tiene los siguientes atributos: – – – –

Nombre (identificador) Dirección (l-value: ¿Dónde está localizada?) Valor (r-value: contenido) Tipo (tipo de dato que almacena y operaciones válidas) – Tiempo de vida (¿Cuándo se crea y se destruye?) – Ámbito (¿Dónde se puede referenciar?)

Dirección de una Variable • Un nombre puede ser asociado con diferentes direcciones en diferentes partes y tiempo de ejecución de un programa – El mismo nombre puede ser usado para referirse a diferentes objetos (direcciones), según el ámbito. – Diferentes nombres pueden referirse a un mismo objeto (alias), lo que puede provocar efectos laterales.

• Ejemplo: – Union y punteros en C y C++ – Variables dinámicas en PERL

10

Ligado (Binding) • Definición: Proceso de asociación de un atributo a una entidad del lenguaje. – Variable: Dirección, tipo Nombre – Operador: Código Símbolo

• El tiempo de ligado se refiere al instante en que sucede la asociación: – Estática: diseño o implementación del lenguaje; compilación, enlace o carga del programa – Dinámica: ejecución del programa

a) Ligado de Tipos a Variables • Variables deben ser ligadas a un tipo antes de usarlas. • Ligado Estático: con declaración explícita o implícita – Lenguajes modernos usan sólo declaración explícita – C y C++ hacen la diferencia entre declaración y definición

• Ligado Dinámico: en el momento de la asignación – Ventaja: Permite programar en forma genérica – Desventaja: disminuye capacidad de detección de errores y aumento del costo (ejecución)

11

b) Ligado a Memoria y Tiempo de Vida de Variables • El carácter de un lenguaje está en gran medida determinado por cómo se administra la memoria. • A la variables se les puede asignar y liberar memoria de un espacio común (liberación implícita requiere de un recolector de basura). • Las variables escalares, según tipo de ligado, se clasifican en: – Estáticas – Dinámica de stack – Dinámica de heap

b.1) Variables Estáticas • Ligadas antes de la ejecución • Ventajas – Útil para variables globales – Para variables sensibles a la historia de un subprograma (e.g. uso de static en variables de funciones C y C++) – Acceso directo permite mayor eficiencia

• Desventajas – Falta de flexibilidad – No soportan recursión – Impide compartir memoria entre diferentes variables

12

b.2) Variables Dinámicas de Stack • Ligadas (a la memoria) en el momento en que la ejecución alcanza el código asociado a la declaración. • Típicamente el tipo se liga estáticamente. • En Pascal se asigna memoria en el momento de ingresar al bloque que define el ámbito de la variable. • En C y C++ las variables son por defecto de este tipo (denominadas variables automáticas).

b.3) Variables Dinámicas de Heap • La memoria se asigna y libera en forma explícita por el programador, usando un operador del lenguaje o una llamada al sistema – C++ dispone del operador new y delete – C usa llamada al sistema malloc() y free() – Java no permite la liberación explícita

• Ventaja: útil para estructuras dinámicas usando punteros. • Desventaja: Dificultad en su uso correcto

13

Tipo de Datos • Para generalizar, supongamos: – La asignación es un operador binario con una variable y una expresión como operandos – Un subprograma es un operador cuyos parámetros son sus operandos

• Verificación de tipo es asegurar que los operandos de un operador son de tipo compatible. • Un tipo compatible es uno legal o que mediante reglas el compilador lo puede convertir a legal. • La conversión automática de tipo se denomina coerción

Verificación de Tipo • Si todos los tipos se ligan estáticamente verificación de tipos se puede hacer estáticamente.

• Ligado dinámico requiere realizar una verificación de tipo en tiempo de ejecución. • Lenguajes modernos prefieren una verificación de tipo estática • Verificación de tipo se complica cuando se permite almacenar valores de diferente tipo en una variable

=> (e.g. Registro con variante en Pascal y Union en C).

14

Tipificado Fuerte (strong typing) • Un lenguaje es de tipificado fuerte si permite detectar siempre los errores de tipo: – Cada nombre debe ser ligado estáticamente a un tipo – Ligado dinámico a memoria requiere verificación en tiempo de ejecución

• Ejemplos: – ¡Pascal casi lo es! (registro con variante es excepción) – C y C++ no lo son (parámetros en funciones y union) – Java si lo es (permite forzar conversión de tipo)

Compatibilidad de Tipos • Compatibilidad de nombre – Las variables están en la misma declaración o usan el mismo nombre de tipo – Fácil implementación, pero muy restrictivo

• Compatibilidad de estructura – Si los tipos tienen la misma estructura – Más flexible, pero de difícil implementación

• Algunos lenguajes permiten forma intermedia! (e.g. Equivalencia declarativa en Pascal)

15

Ejemplo: C y C++ struct s1 {int c1; real c2 }; struct s2 {int c1; real c2 }; s1 s2

x; y = x;

/* error de compatibilidad */

typedef char* pchar; pchar p1, p2; char* p3 = p1;

Ámbito (Scope) • Rango de sentencias en el cual un nombre es visible. • Nombres pueden ser sólo referenciadas dentro del ámbito. • Nombres no locales son los que son visibles dentro de un bloque, pero han sido declarado fuera de él.

16

2.3 Tipos de Datos Tipos de datos simples, estructurados y punteros

2.3.1 Tipos de Datos Simples Tipos primitivos, representación, tipos definidos por el usuario

17

Introducción • ¿Cómo calzan los tipos de datos con problemas del mundo real? • Evolución de los tipos: • • • • •

Números enteros y reales Arreglos y Registros Cadenas de Caracteres Definidos por el usuario Tipo de dato abstracto

Tipos Ordinales • Un tipo ordinal es aquel que puede ser asociado a un número natural (ordenados) • Tipos ordinales primitivos: – entero, caracter y booleano

• Tipos ordinales definidos por el usuario: – 1) Enumerados – 2) Subrangos

18

Representación de Números • Características de Representación – Conjunto Finito – Rango de representación y precisión depende del largo del registro

• Tipos de Representación – Números enteros – Números de punto fijo – Números de punto flotante

Tipo Enumerado • Se enumeran todos los posibles valores a través de constantes literales. • Relación de orden permite definir operadores relacionales y predecesor y sucesor. • Mejoran facilidad de lectura y fiabilidad • Normalmente no se usan en E/S

19

Ejemplo : C y C++ ::= enum [] { } ::= | , ::= | =

enum color {rojo, amarillo, verde=20, azul}; color col = rojo; color* cp = &col; if (*cp == azul) // ...

Tipo Subrango • • • •

Subsecuencia contigua de un tipo ordinal Introducido por Pascal Mejora lectura y fiabilidad Ejemplo: Pascal type mayuscula indice

= ´A´..´Z´; = LUNES .. VIERNES;

20

Tipos de Datos Primitivos • Numérico – Entero (e.g. C permite diferentes tipos de enteros: signed, unsigned, short, long) – Punto flotante (e.g C permite float y double) – Decimal (típicamente 4 bits por dígito decimal) • Booleano (típicamente ocupa un byte) • Caracter (típicamente un byte y código ASCII; Java usa Unicode con 2 bytes)

2.3.2 Tipos de Datos Estructurados Arreglos, Registros y Strings

21

Tipo Arreglo • Es un tipo estructurado consistente en un conjunto ordenado de elementos que se identifican por su posición relativa mediante un índice. • Existe un tipo asociado a los elementos y al índice. • Índice se escribe entre: – paréntesis redondo (Basic) o – cuadrado (Pascal, C, C++ y Java).

• Verificación de rango del índice mejora fiabilidad (Pascal y Java lo hacen).

Arreglos Multidimensionales • Pascal permite sólo dos dimensiones TYPE matriz = ARRAY [subindice, subindice] OF real;

• C y C++ real matriz [DIM1][DIM2];

22

Inicialización de Arreglos • ANSI C y C++ char *mensaje = “Hola mundo\n”; char *dias[] = {“lu”, ”ma”, “mi”, “ju”, “vi”, “sa”, “do”};

• Java int[] edades = { 7, 12, 18, 21, 25 };

• Pascal no lo permite

Operadores con Arreglo • Pascal y C y no tienen soporte especial (sólo selector con subíndice []) • C++ permite definir una clase arreglo por el usuario y operadores tales como subíndice, asignación, inicialización, etc. • Java define los arreglos como tipos especiales de objetos. Permite uso de subíndice, cálculo del largo y otros métodos.

23

Operadores con Arreglo • C/C++ no tiene chequeo de rango para los índices. Tampoco permite averiguar el largo de un arreglo. • Pascal provee chequeo de rango • Java provee chequeo de rango y permite conocer el largo del arreglo. int[] arr = {1,2,3,4,6,7,2,3}; for(int i=0;i “Enero”, … 12 => “Diciembre” ); print $dias{7};

Arreglos Asociativos • C++ provee mapas y multimapas a travé de la STL (Standard Template Library) – Mapas: una clave, un valor. – Multimapas: un clave, múltiples valores.

• Java provee interfaces para diccionarios e implementaciones de tablas hash.

25

Arreglos Asociativos • Hashing – Ubicación de un elemento dentro del arreglo por una función matemática sobre la clave. – Los arreglos son casos especiales, donde la clave es el índice y la función matemática es la identidad. – Permite que las claves sean estructuras más complejas. clave

f(clave)

posición

Tipo Registro • Permite composición heterogénea de elementos de datos Cada elemento se identifica por un nombre (campo o miembro) – Introducido por COBOL (data division) – En C equivale a struct – Concepto de clase en O-O soporta registros (e.g. C++ y Java)

26

Ejemplo: Registros en C y C++ (struct) struct empleado_t { struct { char primer[10]; char paterno[10]; char materno[10]; } nombre; int sueldo; } empleado_t

pelao, guaton;

guaton.sueldo = 550000; strcpy( pelao.nombre.primer, “Juan”);

Ejemplo: Registros en Pascal TYPE empleado_t = RECORD nombre : RECORD primer: PACKED ARRAY [1.10] OF char; paterno: PACKED ARRAY [1.10] OF char; materno: PACKED ARRAY [1.10] OF char; END {nombre}; sueldo : integer END; VAR pelao, guaton : empleado_t; BEGIN … pelao.sueldo := 550000;

27

Cadena de Caracteres (String) • Principalmente para la comunicación máquina-usuario y para manipulación de textos – Mejora la facilidad de escritura

• ¿Es una cadena un tipo primitivo? – Algunos lenguajes lo proveen como tipo (Java y Perl) – Otros sólo como arreglo de caracteres (C, C++ y Pascal)

• ¿Puede el largo variar dinámicamente?

Strings: Operaciones Básicas • • • • •

Asignación Comparación Concatenación Largo Transformación (e.g. de string a entero)

28

Ejemplo de String en C char str[20]; … if (strcmp(str,”Hola”){ … else { … }

Strings: Calce de Patrones (Pattern matching) • Perl hace uso de expresiones regulares – Ejemplo: – /[A-Za-z][A-Za-z\d]+/ permite calzar un identificador – /^(\s+)\s+(s+)\s+(\s+)$/ permite calzar tres palabras

29

Diseño de String • Diseño de string considera: – Largo estático (Pascal y Java) – Largo dinámico limitado (e.g. C y C++) – Largo dinámico (Perl)

• Último es el más flexible, pero es más costoso de implementar y ejecutar.

Tipo Union • Permite almacenar diferentes tipos de datos en diferentes tiempos en una misma variable. • Reserva espacio de memoria igual al mayor miembro definido. • Todos los miembros comparten la memoria y comienzan desde la misma dirección. • Su uso es en general poco seguro. • Java no provee este tipo de estructura

30

Ejemplo: C y C++

union direccion { char dominio[20]; int IP[4]; };

IP Dominio

2.3.3 Tipo Puntero Operaciones, problemas de uso, tipo referencia e implementación

31

Tipo Puntero • Su valor corresponde a una dirección de memoria, habiendo un valor especial nulo (nil) que no apunta a nada. • Aplicaciones: Método de gestión dinámica de memoria (acceso a variables dinámicas de heap) Método de direccionamiemto indirecto • No corresponde a un tipo estructurado, aun cuando se definen en base a un operador de tipo

Operaciones con Punteros • Asignación: asigna a la variable como valor una dirección a algún objeto de memoria. • Desreferenciación: entrega el valor del objeto apuntado. – Operador * en C y C++ (e.g. *ptr) – Operador ^ en Pascal (e.g. ptr^) – Aritmética de punteros en C y C++

32

Ejemplo en C 7023 432 432 2145 ptr 7127 j

int j, *ptr; ptr= (int*) malloc(sizeof(int)); *ptr = 432; j = *ptr;

Problema con Punteros Dejar colgado (dangling) typedef tipo* ptipo; tipo x; ptipo p, q; p= (ptipo) malloc(sizeof(tipo)); ... q= p; ... free(p); ... /* puede que la variable de heap sea reasignada */ *q = x;

33

Problema con Punteros Pérdida de variables dinámicas de heap tipo*

p;

p= (tipo *) malloc(sizeof(tipo)); ... p= (ptipo *) malloc(sizeof(tipo)); /* se pierde la variable asignada anteriormente */

• Se pierde el acceso a la variable, convirtiéndose en basura dado que no puede ser reasignada

Punteros y Estructuras en C y C++ struct nodo_t { Autoreferencia tipodato info; struct nodo_t *siguiente; }; typedef nodo_t* enlace_t; enlace_t nodo; #ifndef C++ nodo = (enlace_t) malloc(sizeof(nodo_t));

34

Punteros y Arreglos en C y C++ • Un arreglo es en realidad una constante de tipo puntero int a[10]; int *pa; pa = &a[0]; pa = a; /* hace lo mismo que la linea anterior */

Aritmética de Punteros en C y C++ #define ALLOCSIZE 1000 /* tamaño del buffer */ static char allocbuf[ALLOCSIZE]; /* el buffer */ static char* allocp = allocbuf; /* primera posición libre */ char *alloc(int n) / retorna puntero a “n” caracteres */ {

35

Tipo Referencia en C++ • Un tipo referencia es una variable tipo puntero constante que es implícitamente desreferenciada. • Dado que es constante, debe ser inicializada en su definición.

int valor = 3; int &ref_valor = valor; • La referencia actúa como alias de una variable.

Referencias en Java • Java extiende la forma de variables de referencia de C++, haciendo innecesario y, por lo tanto, eliminando el uso de punteros. – Java permite asignar un nuevo objeto a una variable de referencia – Todo objeto sólo se referencia con estas variables

• En Java liberación de objetos es implícita • Requiere de un recolector de basura

36

Métodos de Reclamo de Basura • Contadores de Referencia (impaciente) – Se mantiene un contador de referencia por cada celda – Se incrementa con una nueva referencia y se decrementa cuando se pierde una referencia – Celda se libera tan pronto cuenta llega a cero (cuando se convierte en basura)

• Recolección de Basura (perezoso) – Se acumula basura hasta que se agota la memoria – Si se agota la memoria se identifican las celdas de basura y se pasan a la lista de celdas libres

Recolección de Basura void* allocate (int n) { if (!hay_espacio) { /* recolectar basura */ 1) marcar todo los objetos del heap como basura; 2) for (todo puntero p) { if (p alcanza objeto o en el heap) marcaro como NO basura;

37

Evaluación de los Métodos • Contadores de referencia – Requiere bastante memoria para mantener contadores – Asignaciones a punteros requiere de más tiempo de ejecución para mantener contadores

• Recolección de basura – Basta un bit por celda para marcar basura – Mal desempeño cuando queda poca memoria

2.4 Expresiones y Asignaciones Expresiones aritméticas y lógicas, sobrecarga de operadores, conversiones de tipo, evaluación con cortocircuito

38

Introducción • Lenguajes imperativos se caracterizan por el uso dominante de expresiones y asignaciones • El valor de las expresiones depende del orden de evaluación de operadores y operandos • Ambigüedades en el orden de la evaluación puede conducir a diferentes resultados

Expresiones Aritméticas • Orden de evaluación está principalmente definida por las reglas de precedencia y asociatividad • Paréntesis fuerzan determinado orden

39

Reglas de Precedencia de Operadores Aritméticos

Reglas de Asociatividad

40

Expresión Condicional /* version N°1 */ int abs(int n) { if (n>=0) return n; else return –n; }

Efectos Laterales Funcionales • Orden de evaluación de los operandos puede producir resultados diferentes si existen efectos laterales • Ejemplo: int a = 2; int f1() { return a++; } int f2 (int i) { return (--a * i);

41

¿Cómo evitar efectos laterales de funciones? • Deshabilitar efectos laterales en la evaluación de funciones – Quita flexibilidad, por ejemplo habría que negar acceso a variables globales

• Imponer un orden de evaluación a las funciones – Evita que el compilador puede realizar optimizaciones – Enfoque seguido en Java (evaluación de izquierda a derecha).

Sobrecarga de Operadores • Un mismo operadores puede ser usado con diferentes tipos de operandos y para diferentes fines. • Ejemplo: + para sumar enteros y reales (tb. strings) & en C es AND al bit y operador de dirección • Ayuda a mejorar la lectura, pero puede que errores de escritura no sean detectados.

42

Sobrecarga de Operadores definidas por el Programador • Algunos lenguajes con soporte de TDA permiten • al programador sobrecargar símbolos de • operadores (e.g. ADA, Fortran 90 y C++)

matrix A, B, C, D; D = A + (B*C); /* es mas conveniente, pero requiere de

Conversiones de Tipo • Clases: extensión o estrangulamiento – Extensión: paso de entero a punto flotante o subrango de enteros a entero – Estrangulamiento: paso de real a entero, de tipo base a subrango en general

• En general, extensión es más segura, pero puede tener algunos problemas (e.g. pérdida de precisión en la mantisa de entero a real)

43

Coerción en Expresiones • Coerción es cuando la conversión de tipo es implícitamente asumida por el compilador. • Da más flexibilidad al uso de operadores, pero reduce la posibilidad de detectar errores y introduce código adicional. • Ada y Modula-2 admiten pocos casos de coerción • Java enteros cortos (byte, short y char) se convierten a int. • Conversión explícita se denomina casting

Expresiones Relacionales Operación

Pascal

C

=

==

No es igual



!=

Mayor que

>

>

Menor que

<

<

Igual

44

Operadores Booleanos • Incluye: AND, OR, NOT y, a veces, XOR. • La precedencia está generalmente definida de mayor a menor: NOT, OR y AND • Operadores aritméticos tienen mayor precedencia que relacionales y , generalmente, booleanos menor que relacionales (excepto Pascal). • La asignación en C, C++ y Java es el operador que tiene la menor precedencia

Ejemplos: Operadores relacionales y lógicos

C: b + 1 > b*2 /* aritmeticos primero */ C: l

i

a > 0 || a < 5 l i */

/*

45

Corto Circuito o Término Anticipado de Evaluación

C: (a >=0) || (b < 10)

while ( (c = getchar()) != EOF && c != ´\n´) { procesar linea; Lenguaje

Operadores Std.

Eval. Anticipada

Valor

ADA

and , or

and then , or else

Boolean

Algol 68

and/&/

C, Java

, or/

andf , orf - user defined

bool

&,|

&& , ||

Boolean

C++

& , bitand , | , bitor

&& , and , || , or

Boolean

Eiffel

and , or

and then , or else

BOOLEAN

JavaScript

&,|

&& , ||

Last value

Lisp

none

and , or

Last value

Perl

&,|

&& , and , || , or

Last value

Python

&,|

and , or

Last value

V. Basic

And , Or

AndAlso , OrElse

Boolean

No tienen Eval. Anticipada BASIC, Pascal, Fortran

Corto Circuitos en los Lenguajes Imperativos • C, C++ y Java definen corto circuito para: && y || (AND y OR) • Pascal no lo especifica (algunas implementaciones los tienen, otras no)

46

Sentencias de Asignación • Permite cambiar dinámicamente el valor ligado a una variable • Basic, C, C++ y Java usan = • Algol, Pascal y ADA usan := • C, C++ y Java permiten incrustar una asignación en una expresión (actúa como cualquier operador binario)

Operadores Compuestos y Unarios de Asignación • Sólo presentes en C, C++ y Java sum += A[i]; equivale a:

sum = ++contador; equivale a:

47

Asignación Condicional • C, C++ y Java permiten: (a > 0) ? cuenta1: cuenta2 = 0; • Equivale a: if (a > 0) cuenta1 = 0;

else cuenta2 = 0;

Asignación en Expresiones • C, C++ y Java permiten incrustar asignaciones en cualquier expresión • Permite codificar en forma más compacta • La desventaja de esta facilidad es que puede provocar efectos laterales, siendo fuente de error en la programación • Es fácil equivocarse confundiendo == y =

48

Asignación en Expresiones ... int x,y; x=0; y=1; if(x=y) x++; ...

... int x,y; x=0;y=1; if((x=y)==1) x++; System.out.println("x:"+x+", y:"+y); ...

•En C entrega x=2 e y=1 •En Java entrega error de compilación

•En Java entrega x=2 e y=1

2.5 Estructuras de Control Expresiones aritméticas y lógicas, sobrecarga de operadores, conversiones de tipo, evaluación con cortocircuito

49

Introducción • Ejecución es típicamente secuencial • Normalmente se requieren dos tipos de sentencias de control: – Selección de alternativas de ejecución – Ejecución repetitiva de un grupo de sentencias

• En principio basta tener un simple goto selectivo, pero es poco estructurado

1) Sentencias Compuestas • Permite agrupar un conjunto de sentencias • Ejemplos: – begin y end en Pascal – Paréntesis de llave en C, C++ y Java

50

2) Sentencias de Selección • Selección binaria Ejemplo: if-else o if (solo)

• Selección múltiple Ejemplos: – case en Pascal – switch en C, C++ y Java – elseif en ADA

3) Sentencias Iterativas • Bucles controlados por contador Ejemplo: for en C

• Bucles controlados por condición Ejemplo: – while, do-while en C, C++ y Java – do-until en Pascal

• Bucles controlados por Estructuras de Datos – Ejemplo: foreach en Perl – Java 1.5 acaba de introducir una especie de foreach.

51

4) Salto Incondicional • Uso de rótulos o etiquetas – Ejemplo: goto FINAL

• Restricciones: – Sólo rótulos en el ámbito de la variable – Rótulos deben ser constantes

2.6 Subprogramas Ámbito, comprobación de tipos, semántica de paso de parámetros, funciones genéricas, implementación

52

Características de un Subprograma • Permite crear abstracción de proceso: – encapsulando código – definiendo una interfaz de invocación para paso de parámetros y resultados

• Permite reutilizar código, ahorrando memoria y tiempo de codificación. • Existe en forma de procedimiento y función.

Mecanismo de Invocación Subprograma Invocación y suspensión Reanudación

Parámetros Activación Retorno

Resultados

53

Elementos en la Definición de Interfaces de Subprograma • Nombre: permite referenciar al subprograma como unidad e invocarlo. • Parámetros (Opcional): Define la comunicación de datos (nombre, orden y tipo de parámetros formales): • Valor de retorno: Opcional para funciones (tipificado). • Excepciones (Opcional): Permite manejo de un evento de excepción al retornar el control.

Firmas y Protocolos de la Interfaz • La firma (signature), o prototipo, es un contrato entre el invocador y el subprograma que define la semántica de la interfaz. • El protocolo especifica cómo debe realizarse la comunicación de parámetros y resultados (tipo y orden de los parámetros y, opcionalmente, valor de retorno).

procedure random( in real illa; t l l t);

54

Parámetros • Parámetros formales son variables mudas que se ligan a los parámetros reales (actuales) cuando se activa el subprograma. – Normalmente ligado se hace según posición en la lista.

• Parámetros permiten comunicación explícita de datos y, a veces, también (otros) subprogramas. • Comunicación implícita se da a través de variables no locales, lo que puede provocar efectos laterales.

Semántica de Paso de Parámetros • Modo de interacción de parámetro actual a formal puede ser: – entrega de valor (IN) – recibo de valor (OUT) – ambos (INOUT)

• La implementación de la transferencia de datos puede ser: – copiando valores, o – pasando referencias (o puntero)

55

Paso por Valor (pass-by-value) • Modo IN e implementado normalmente con copia de valor – Implementación con paso de referencia requiere protección de escritura, que puede ser difícil

• Permite proteger de modificaciones al parámetro actual, pero es más costoso – (más memoria y tiempo de copiado)

• Permite usar expresiones como parámetro actual

Paso por Resultado (pass-by-result) • Modo OUT y normalmente implementado con copia (mismas complicaciones que por valor) • Parámetro formal actúa como variable local, pero al retornar copia valor a parámetro actual • Parámetro actual debe ser variable • Dificultades: – Existencia de colisiones en los parámetros actuales, puede conducir a ambigüedad – Cuándo se evalúa dirección de parámetro actual?

56

Paso por Valor-Resultado (pass-by-value-result) • Modo INOUT con copia de parámetros en la entrega y en el retorno – Por esto, llamada a veces paso por copia

• Mismas dificultades que paso por valor y paso por resultado

Paso por Referencia (pass-by-reference) • Modo INOUT e implementación con referencias • Parámetro formal y real comparten misma variable • Ventaja: Comunicación es eficiente en: – espacio (no requiere duplicar variable) – tiempo (no requiere copiar)

• Desventaja – Acceso es más lento (indirección) – Es fuente de error (modificación de parámetro real) – Creación de alias a través de parámetros actuales

57

Paso por Nombre (pass-by-name) • Modo INOUT, pero diferente a los modelos anteriores • Nombres del parámetro real se liga al parámetro formal en el momento de la activación, pero valor o dirección se liga en el momento de la referencia • Es muy flexible, pero costoso (lento) y difícil de implementar y entender • Usado en ALGOL 60, discontinuándolo en versiones sucesivas

Ejemplo 1: Paso por Referencia vs. Paso por ValorResultado

58

Ejemplo 2: Paso por Referencia vs. Paso por Nombre

Paso de Parámetros en lenguajes • Fortran – Variables por referencias y escalares por valorresultado • Algol 60 – Por defecto paso por nombre, y permitía valorresultado • Ada – Valor, resultado, y valor-resultado • Modula2 – Por defecto Paso por valor, y permite por referencia

59

Paso de Parámetros en lenguajes • C: Paso por valor, y por referencia usando punteros – Puntero pueden ser calificado con const; se logra semántica de paso por valor (sin permitir asignación) – Arreglos se pasan por referencia (son punteros)

• C++: Igual que C, más paso por referencia usando operador & – Este operador también puede ser calificado con const, permitiendo semántica paso por valor con mayor eficiencia (e.g. paso de grandes arreglos)

• Java: Todos los parámetros son pasados por valor, excepto objetos que se pasan por referencia – No existencia de punteros no permite paso por referencia de escalares (si como parte de un objeto)

• Pascal: Por defecto paso por valor, y por referencia si se usa calificativo var.

Funciones como Parámetro • En Pascal function integrar (function fun(x:real): real; bajo, real) :punteros real; a funciones) • En C lto: (solo usando float integrar (float *fun(float), float bajo, float alto);

60

Sobrecarga de Subprogramas • En el mismo ámbito existen diferentes subprogramas con el mismo nombre. • Cada versión debiera tener una firma diferente, de manera que a partir de los parámetros reales se pueda resolver a cual versión se refiere. • Las versiones pueden diferir en la codificación • Es una conveniencia notacional, que es evidente cuando se usan nombres convencionales, como en siguiente ejemplo

Ejemplo: Sobrecarga de Funciones en C++ y Java double abs(double); int abs(int); abs(1); // invoca int abs(int); abs(1.0); // invoca double abs(double);

61

Subprogramas Genéricos • Permite crear diferentes subprogramas que implementan el mismo algoritmo, el cual actúa sobre diferentes tipos de datos. • Mejora la reutilización, aumentando productividad en el proceso de desarrollo de software. • Polimorfismo paramétrico: Parámetros genéricos de tipos usados para especificar los tipos de los parámetros de un subprograma • Sobrecarga de subprogramas corresponde a un polimorfismo ad-hoc

Funciones Genéricas en C++ template Tipo maximo (Tipo a, Tipo b) { return a>b ? a : b; } int x, y, z; char u, v, w; z = maximo(x, y);

62

Sobrecarga de Operadores definida por el Usuario • Permite que el usuario sobrecargue operadores existentes en el lenguaje (Lo permiten ADA y C++)

int operator * ( const vector &a, const vector &b, int len) { int sum = 0; for (int i = 0; i < len; i++) sum += a[i] + b[i]; return sum; } ...

63