Ingeniero en Informática
Lenguajes de programación
1. INTRODUCCIÓN
1.1. EVOLUCIÓN DE CONCEPTOS
• Abstracción de Datos
" Tipos elementales
" Tipos estructurados
" Tipos abstractos
• Abstracción de Control
" Sentencias
" Unidades de programa
1.2. CLASIFICACIÓN DE LENGUAJES
Los lenguajes, en general, admiten la siguiente posible clasificación:
Lenguajes
Naturales (idiomas)
De programación
De máquina
Simbólicos
De bajo nivel (ensambladores)
De alto nivel
Imperativos (Fortran, Pascal, C, Ada)
Funcionales (Lisp, Apl, Forth)
Lógicos (Prolog)
Orientados a objetos (C++, Eiffel, Java, Smalltalk)
Los lenguajes de programación, según su nivel de abstracción, admiten la siguiente categorización gráfica:
1.3. CRITERIOS DE DEFINICIÓN Y DISEÑO DE LENGUAJES
• Ortogonalidad
Contemplar todas las combinaciones posibles de un conjunto de características de un lenguaje, dotándolo de un grado de generalidad tal que excluya las restricciones o los casos especiales. Como una muestra de carencia de ortogonalidad en Pascal, el tipo de un parámetro formal no puede ser anónimo, es decir, no es posible declararlo explícitamente como, por ejemplo,
procedure noort(var a : array[1..10] of real);
debiéndose declarar
procedure noort(var a : A);
después de la declaración global
type A = array[1..10] of real;
• Claridad sintáctica
Permitir que las diferencias semánticas se manifiesten en diferencias sintácticas.
• Orientación
Proveer una sintaxis comprometida con la orientación del lenguaje.
• Extensión
Facilitar la implementación de estructuras inexistentes en función de las existentes.
• Portabilidad
Proveer una definición del lenguaje independiente de las características de una máquina en particular.
• Eficiencia
" En traducción
" En ejecución
" En construcción
1.4. SINTAXIS
• Definición
La sintaxis de un lenguaje es un conjunto de reglas que determinan si las sentencias de un programa están bien formadas o no.
• Objetivo
Proveer una notación que permita la comunicación entre el programador y el procesador del lenguaje.
• Criterios sintácticos
" Legibilidad
" Facilidad de escritura
" Facilidad de traducción
" Ausencia de ambigüedad.
Por ejemplo, M(i) puede significar un elemento del arreglo M ó una llamada a la función M.
• Elementos Sintácticos
" Set de caracteres
" Identificadores
" Símbolos para operadores
" Palabras claves y reservadas.
Una palabra clave es un identificador que constituye la parte no cambiante de una instrucción. Una palabra reservada es una palabra clave no declarable como identificador de usuario.
" Comentarios
" Abreviaciones
" Espacios
" Delimitadores
" Formatos fijo y libre
" Expresiones
" Sentencias
" Estructura de unidades de programa
" Definición separada: Cada unidad representa un bloque sintáctico independiente (Fortran).
" Definición anidada: Las unidades aparecen como declaraciones y pueden contener sus propias definiciones de unidades (Pascal).
" Definición centralizada de datos: Las declaraciones de datos para todas las unidades se centralizan en una única división ( Cobol).
• Gramáticas
Una gramática representa la definición formal de la sintaxis de un lenguaje. Consta de un conjunto de reglas que especifican las secuencias de símbolos (ítems de léxico) que forman estructuras sintácticas en el lenguaje definido.
• Metalenguajes
Un metalenguaje es una gramática formal destinada a la descripción de un lenguaje. Existen tres metalenguajes comúnmente utilizados.
" BNF (Backus-Naur-Form)
Notación desarrollada por los especialistas Backus y Naur para definir lenguaje Algol60
Ejemplo de BNF para lenguaje Pascal:
<sentencia for> ::= for <variable> := <intervalo> do <sentencia>
<intervalo> ::= <valor inicial> to <valor final> | <valor inicial> downto <valor final>
<sentencia for> ::= for <variable> := <valor inicial> <hasta> <valor final>do <sentencia>
<hasta> ::= to | downto
<variable> ::= <identificador>
<identificador> ::= <letra>{<letra>|<dígito>}o
<letra>::= A | B ... | Z | a | b ... | z
<dígito>::= 0 | 1 | 2 ... | 9
<valor inicial>::= <expresión>
<valor final>::= <expresión>
Alternativamente se pueden usar reglas BNF en forma recursiva.
<alfanum> ::= <letra> | <dígito>
<secuencia> ::= <alfanum> | <alfanum> <secuencia>
<identificador> ::= <letra> | <letra> <secuencia>
Los símbolos <, >, |, {, }, ::=, no son parte del lenguaje definido, sino parte del mecanismo de descripción y reciben el nombre de metasímbolos. El símbolo ::= significa "se define como". Las secuencias encerradas entre < > constituyen símbolos no terminales (o metavariables) y las secuencias restantes (subrayadas y otras) símbolos terminales.
" Diagramas sintácticos
Constituyen un método de descripción de lenguajes, equivalente a la BNF, originalmente propuesto por Wirth.
Equivalencias entre BNF y diagramas sintácticos:
" <S> ::= <v1> | <v2> ··· | <vk>
" Cada ocurrencia de un símbolo terminal corresponde al diagrama
" Cada ocurrencia de un símbolo no terminal corresponde al diagrama
" Una producción de la forma <S> ::= {<x>}0 corresponde al diagrama
" Una producción de la forma <S> ::= {<x>}1 corresponde al siguiente diagrama
Diagramas sintácticos para Lenguaje Pascal:
· Identificador
· Sentencia if
· Sentencia while
· Sentencia compuesta
" CBL (COBOL-Like)
Constituye una extensión de la BNF destinada a la descripción sintáctica del lenguaje Cobol. Incluye la siguiente simbología:
" Elementos opcionales se denotan entre paréntesis cuadrados
[ x ]
" Elementos alternativos se listan verticalmente entre paréntesis llave
" Elementos alternativos opcionales se listan verticalmente entre paréntesis cuadrados.
" La repetición de los elementos se indica mediante tres puntos a continuación de una ocurrencia del elemento.
[ x ] ···
Ejemplos:
<entero> ::=
<identificador> ::=
1.5. SEMÁNTICA
La semántica de un lenguaje especifica el significado algorítmico de un programa y se define como un conjunto de reglas que describen el comportamiento de ese lenguaje en tiempo de ejecución.
Una expresión sintáctica, mediante BNF, como
<fecha> ::= <d><d>/<d><d>/<d><d>
puede tener dos interpretaciones semánticas; por ejemplo, 12/03/99 se entiende como 12 de Marzo de 1999 en Chile y 03 de Diciembre de 1999 en EEUU.
1.6. PROCESADORES DE LENGUAJES
• Procesador
Es una máquina capaz de ejecutar acciones expresadas en algún lenguaje concreto (actualmente, sólo lenguaje de máquina).
• Traductor
Es un decodificador que acepta programas escritos en algún lenguaje fuente y genera programas, funcionalmente equivalentes, en algún lenguaje objeto.
• Compilador
Es un traductor cuyo lenguaje fuente es un lenguaje de alto nivel y cuyo lenguaje objeto es un lenguaje de máquina.
Lenguaje de alto nivel
ð
Lenguaje ensamblador
ð
Lenguaje de máquina (código reubicable)
ð
Lenguaje de máquina (código real)
• Intérprete
Es un procesador cuyo lenguaje concreto es un lenguaje de alto nivel. Sin embargo, como ningún computador es capaz de ejecutar un código distinto al de máquina, se debe simular mediante software la existencia de un computador cuyo lenguaje de máquina es un lenguaje de alto nivel.
• Diferencias entre compilador e interprete
" El compilador sólo traduce; el intérprete decodifica y ejecuta.
" El compilador acepta las instrucciones según su secuencialidad física (las traduce sólo una vez); el intérprete los acepta según su secuencialidad lógica (puede procesar varias veces algunas e ignorar completamente otras instrucciones).
2. OBJETOS DE DATO
2.1. COMPONENTES DE UN OBJETO
La memoria de un computador es capaz de representar objetos de cualquier naturaleza lógica.
Cada objeto de dato tiene un nombre el cual, sintácticamente, es un identificador (exceptuando los literales).
Cada nombre tiene atributos, una referencia (si es un nombre de variable) y un valor: los atributos determinan las propiedades de un nombre, siendo el más importante el tipo; la referencia es un número que identifica a la celda de memoria que contiene un valor asociado a un nombre; el valor es uno perteneciente al conjunto conocido como tipo.
2.2. CONSTANTES
Un objeto de dato cuyo valor no se modifica durante la ejecución, se denomina constante. Una constante cuyo nombre es la representación escrita de su valor se denomina literal. Una constante cuyo nombre es un identificador se denomina constante declarada.
const Pi = 3.1416; {Constante declarada}
···
x := 3.1416; {Literal}
z := Pi;
2.3. VARIABLES
Un objeto de dato cuyo valor suele modificarse durante la ejecución se denomina variable.Una variable es una cuádrupla
X = (N,A,R,V)
donde
N = Nombre
A = Atributo
R = Referencia
V = Valor
Gráficamente:
2.4. DECLARACIONES
Una declaración es una sentencia de programa que provee al traductor del lenguaje información sobre los atributos de una variable. Por ejemplo, la traducción de la declaración en Pascal
var x : integer;
provoca el siguiente efecto gráfico:
Sin embargo, la traducción de la declaración en Fortran
Integer x
provoca el siguiente efecto gráfico:
ya que Fortran sitúa todos los objetos de dato en un área de memoria contigua al código, situación que se mantiene invariante durante ejecución.
2.5. BINDING (LIGADURA)
• Definición
Ligadura es la acción de asociar tipo, referencia o valor a un nombre de variable.
• Ligadura en lenguajes fuertemente tipados (variables estáticas y automáticas)
La asociación de un tipo a una variable se conoce como ligadura estática, anticipada ó en tiempo de compilación.
(N + T)
La asociación de una referencia a una variable se conoce como ligadura intermedia ó en tiempo de creación.
((N + T) + R))
La asociación de un valor a una variable se conoce como ligadura dinámica ó en tiempo de ejecución.
(((N + T) + R) + V)
• Ligadura en lenguajes débilmente tipados (variables dinámicas)
La asociación de un tipo a una variable se conoce como ligadura dinámica, tardía ó en tiempo de ejecución. Sin embargo, en este caso, los tipos están ligados a los valores y los valores están representados a partir de cierta referencia. Luego, la ligadura dinámica puede consistir en crear un valor de cierto tipo a partir de una referencia y asociar esa referencia a un nombre de variable, ó bien, asociar a un nombre de variable una referencia en la cual existe un valor de cierto tipo.
(N + (R +(T + V)))
2.6. OPERACIONES
En un lenguaje, una operación (inherente a un tipo de dato) se puede definir como una función que transforma una lista de argumentos en una lista de resultados.
Luego, cada operación tiene un dominio (conjunto de argumentos posibles) y un recorrido (conjunto de resultados posibles).
nombreOperación : (tipoArgumento, tipoArgumento, ...) ! (tipoResultado, tipoResultado, ...)
Por ejemplo:
+ : (real, real) ! (real)
= : (entero, entero) ! (boolean)
* : (real, entero) ! (real)
ord : (carácter) ! (entero)
2.7. EXPRESIONES
• Definición
Una expresión es un conjunto bien formado de operadores y operandos cuyo objetivo es la generación de un valor.
• Alternativas de descripción sintáctica
" Notación prefija
Ordinaria * ( + ( a , b ) , - ( c , d ) )
Cambridge ( * (+ a b ) (- c d ) ) {Lenguaje Lisp}
Polaca * + a b - c d
" Notación infija (convencional)
a + b * c - d
" Notación postfija
Ordinaria ( ( a , b) + , ( c , d ) - ) *
Polaca inversa a b + c d - *
• Control de secuencia
Las reglas implícitas de control destinadas a eliminar el excesivo uso de paréntesis en expresiones exentas de ambigüedad, en notación convencional son:
" Prioridad de operadores
Si x = 12 e y = 3 entonces el valor de la expresión x - 3 * y es 3 en Pascal y 27 en Smalltalk.
" Asociatividad para operadores de idéntica prioridad
Si x = 7 e y = 4 entonces el valor de la excpresión x - y - 3 es 0 en Pascal y 6 en APL.
3. SENTENCIAS
3.1. ASIGNACIÓN
• Definición
Una asignación es una sentencia que almacena el valor del argumento ubicado a la derecha del símbolo que la representa, en la referencia del argumento ubicado a la izquierda del mismo.
• l-valor y r-valor
En la sentencia x := x + 1, la variable x tiene un doble comportamiento respecto al valor contenido en su referencia: a la izquierda, uno activo que lo modifica, y a la derecha, uno pasivo que sólo lo usa.
Referencia y valor corresponden, respectivamente, a los conceptos l-valor y r-valor (left-value y right-value) los cuales expresan la función que ellos desempeñan a ambos lados de un símbolo de asignación.
Consideraciones:
" Cada variable tiene un l-valor que designa su ubicación en memoria.
" Una constante sólo tiene r-valor.
" En una variable subindicada A[i], el l-valor es la ubicación en memoria del i-ésimo elemento de A y el r-valor es el valor almacenado en esa ubicación
" Si p es una variable puntero, su r- valor es la dirección a la cual p apunta y su l-valor es la ubicación en la cual esa dirección se encuentra almacenada. Gráficamente:
Para una variable, el l-valor es único; sin embargo, un l-valor puede pertenecer a más de una variable.
En este, caso, x e y tienen el mismo l-valor, razón por la cual x es llamada "alias de y" e y "alias de x". Lenguaje Fortran provee el concepto de alias a través de la sentencia Equivalence.
• Implementación
Sea la sentencia a := b;
" El compilador genera código para calcular el r-valor de b en algún registro R.
" Si los tipos de a y b son distintos, el compilador genera código para convertir en R (si es posible) el r-valor de b al tipo de a.
" El compilador genera código para almacenar el contenido del registro R en el l-valor de a.
• Formas
Ciertos lenguajes, como C, definen la asignación como una operación binaria infija con prioridad inferior a la de las restantes operaciones sobre tipos elementales. Por ejemplo:
a = ( b = c + d ) + ( e = f + g );
También, en C, se acepta la expresión m[++i] = i.
Algunos lenguajes, como PL/I, permiten asignaciones de la forma A = B, donde A y B pueden ser de tipos estructurados compatibles. Si A es un arreglo en PL/I, la asignación A=0 lo inicializa con ceros.
La modalidad
v1 , v2 , ... , vk ! e1 , e2 , ... , ek
constituye una asignación múltiple de acuerdo a una correspondencia posicional entre l-valores y r-valores. Resulta útil para intercambiar valores entre variables, por ejemplo:
p, q ! q, p;
3.2. INICIALIZACIÓN
Una inicialización consiste en proporcionar un valor a una variable antes de comenzar la ejecución del código al cual pertenece.
La inicialización puede ser implícita, por ejemplo asignar el valor cero a todas las variables numéricas, o explícita, si aparece como parte de una declaración. Por ejemplo:
int v[5] = {11, 22, 33, 44, 55};
3.3. CONTROL DE SECUENCIA
• Control de secuencia implícito
La ejecución procede según el orden físico de las sentencias que conforman una unidad de código.
• Ejecución paralela
Ciertos lenguajes permiten la ejecución paralela conceptual de un bloque de instrucciones.
Para expresar paralelismo, Dijkstra sugiere la estructura parbegin/parend:
parbegin
S1;
S2;
···
Sn;
parend;
Gráficamente:
Por ejemplo:
parbegin
c[1]:= a[1] * b[1];
c[2]:= a[2] * b[2];
c[3]:= a[3] * b[3];
parend;
• Sentencia goto
El objetivo de la sentencia goto es el traspaso explícito del control a una instrucción con label desde cualquier punto de un programa, excepto cuando tal instrucción se encuentra al interior de un bloque.
Ejemplo:
label L;
var A : array[0..9] of integer;
i : integer;
begin
i := 0;
L : read(A[i]);
i := i + 1;
if i < 10 then
goto L;
end;
• Sentencias de selección
" Selección simple (if-then)
" Selección doble (if-then-else)
" Selección múltiple (case)
• Sentencias de repetición
" Repetición "mientras" (while)
" Repetición "hasta" (repeat)
" Repetición con variable de control (for)
• Sentencias de I/O
Constituyen la interfaz de comunicación con las rutinas del sistema operativo destinadas a la transferencia de datos.
• Sentencias de invocación
Constituyen el mecanismo de activación de unidades de programa.
• Sentencias estructuradas
Corresponde a la concepción recurrente de sentencia compuesta o bloque. Ciertos lenguajes, como C, permiten declarar variables locales al interior de un bloque, por ejemplo:
{ int i = 0;
···
{ int j = 0;
···
}
···
}
4. TIPOS DE DATOS
4.1. CONCEPTOS BÁSICOS
• Definición de tipo
Un tipo de dato es un conjunto de objetos con una colección de operaciones. Tal conjunto se conoce como dominio.
• Tipo elemental de dato
También conocido como escalar, es aquel cuyo dominio consta sólo de valores constantes (enteros, reales, lógicos, caracteres).
• Tipo estructurado de dato
También conocido como agregado, es aquel en el cual cada uno de los valores de su dominio es una composición de objetos de tipo escalar y/o agregado (producto cartesiano, aplicación finita, unión discriminada, conjunto potencia).
4.2. ESTRUCTURA DE TIPOS
La estructura de los tipos de datos en un lenguaje la determinan dos componentes:
• Equivalencia
Criterio con el cual se decide que dos objetos son del mismo tipo. Si los tipos de los dos objetos tienen el mismo nombre, entonces la equivalencia es nominal; en cambio, si tienen la misma estructura, la equivalencia es estructural. Ejemplo :
type E = integer;
A = array[1..10] of integer;
var x1 : integer;
x2 : integer;
x3 : E;
v1 : array [1..10] of integer;
v2 : A;
v3 : A;
Equivalencia nominal ! x1 eq x2 y v2 eq v3 (el tipo de v1 es anónimo)
Equivalencia estructural ! x1 eq x2 eq x3 y v1 eq v2 eq v3
• Conversión
La conversión de tipos en un lenguaje se realiza con el propósito de transformar la representación interna de un r-valor según la representación interna del respectivo l-valor. La conversión se puede materializar de dos formas:
" Conversión implícita o coerción.
" Conversión explícita o casting.
Por ejemplo, con el siguiente código en lenguaje C
float p, q;
int s, n;
s = 5;
n = 2;
p = s/n; /* coerción */
q = (float)s/n; /* casting y coerción */
printf( %f %f \n , p, q);
se despliegan los valores 2.0 y 2.5 para p y q, respectivamente.
Esto debido a que la división entre los enteros s y n genera un valor entero, el cual se convierte al tipo de p (coerción). En la siguiente línea, se crea una copia temporal de tipo float del entero s; luego, se calcula la división entre el valor de la copia float de s y el valor de una copia float de n (coerción).
En C, un operador de casting es un operador unario.
4.3. COMPROBACIÓN DE TIPOS
Comprobación de tipos es la acción consistente en verificar la consistencia entre un l-valor y un r-valor. La comprobación puede ser estática, si ocurre durante el proceso de compilación, o dinámica, si ocurre durante el proceso de ejecución.
La comprobación estática es más segura y eficiente que la dinámica. Sin embargo, esta última (aunque más costosa en tiempo y espacio) dota de mayor flexibilidad a los lenguajes. Costosa en tiempo en cuanto a la asignación y desasignación de almacenamiento, al acceso de datos y la ejecución de la operación misma de comprobación. Costosa en espacio debido a que el compilador no puede establecer el tamaño de ciertos objetos lo cual impone el uso de formas de gestión menos eficiente (por ejemplo, heap).
Si el objetivo del diseño de un lenguaje es la seguridad, entonces se intentará que toda la comprobación de tipos se realice durante la compilación. Lamentablemente, esto no es siempre posible. Es casi inevitable la existencia de determinados tipos que fuerzan a comprobaciones en tiempo de ejecución. Esto puede ocurrir, por ejemplo, con los intervalos.
Si se tiene
type rango = 1..100;
var k, n : rango;
···
n := 2*k + 1;
el valor que se intenta asignar a n sólo se puede comprobar durante ejecución. La misma situación se presenta con la comprobación de índices de arreglos. Por esta razón, casi no existen lenguajes en los cuales toda la comprobación de tipos se realice durante compilación. ML es una de las excepciones. A esta clase de lenguajes se les conoce como "fuertemente tipados".
En lenguajes similares a Pascal, la comprobación de tipos es extraordinariamente simple. Si la comprobación es estática, a partir de la declaración, el compilador guardará en la tabla de símbolos, para cada objeto, el tipo al que pertenece y, para cada operación, los tipos de sus operandos. Luego, al compilar una sentencia comprobará, consultando la tabla, si los objetos tienen el tipo adecuado. Por ejemplo, si se tiene
x := f(x) + z;
el compilador comprobará que x tenga el tipo del parámetro formal de f, que el tipo de f, el de x y el de z coincidan y todos ellos sean compatibles.
Si la comprobación fuera dinámica, el proceso sería similar, pero durante la ejecución; para ello, el compilador, al procesar las declaraciones, generará instrucciones que almacenen el tipo asociado a cada objeto para que esté disponible durante la ejecución. Posteriormente, al procesar una instrucción, el compilador generará instrucciones que consulten la información almacenada sobre los tipos de los objetos, y que comprueben que los valores que se van obteniendo durante la ejecución de la instrucción tienen el tipo adecuado.
5. UNIDADES DE PROGRAMA
5.1. UNIDADES SUBORDINADAS
Los lenguajes de programación permiten que un programa esté compuesto de cierto número de unidades, conocidas como subprogramas, las cuales se pueden desarrollar en forma independiente y cumplen un objetivo bien definido resultante del proceso de descomposición de un problema.
Los subprogramas soportan la definición de una acción abstracta (cuerpo de un subprograma) y su uso (invocación del subprograma).
Los datos declarados al interior de un subprograma se conocen como locales.
La invocación de una unidad de programa durante ejecución se conoce como activación.
Una activación se compone de un segmento de código, de contenido fijo, y un registro de activación de contenido variable, el cual incluye toda la información necesaria para ejecutar la unidad.
Un subprograma se puede activar desde otra unidad, a la cual se le devolverá el control una vez finalizada la ejecución de aquel. Luego, el registro de activación debe almacenar la dirección de retorno al efectuarse la invocación.
Un subprograma puede referenciar variables no locales, pertenecientes a otro registro de activación que esté activo durante toda la ejecución. Tales variables reciben el nombre de globales.
El entorno de referencia para una activación de cierta unidad S consta de los objetos contenidos en el registro de activación de S (entorno local) y de los objetos contenidos en los registros de activación de otras unidades (entorno global).
• Estructura tipo Fortran
Cada unidad se compila por separado y se asocia a un registro de activación cuyo tamaño se determina antes de la ejecución y permanece ligado a la unidad durante la ejecución del programa, aun cuando tal unidad no esté activa.
El ámbito de una variable se reduce a la unidad en la cual se ha declarado. Sin embargo, las unidades pueden tener acceso a variables globales, declaradas mediante sentencias Common, las cuales se pueden considerar pertenecientes a un registro de activación que es global para todas las unidades.
Esta modalidad no soporta las activaciones recursivas. Por ejemplo:
• Estructura tipo Algol
Dos unidades cualesquiera de código fuente pueden ser disjuntas o bien anidadas. El ambiente (contexto de validez) de una variable x local a una unidad U es U y todas las unidades al interior de U, para las cuales x tiene el carácter de global. Las variables locales se crean implícitamente al activarse la unidad y la cantidad de almacenamiento requerido por ellas se determina en tiempo de traducción.
Al igual que en Fortran, el tamaño del registro se conoce en tiempo de traducción. Sin embargo, el referido registro es asignado y ligado dinámicamente al respectivo código con cada nueva activación.
Con el fin de hacer posible el retorno desde una unidad activa es necesario que el registro de activación contenga:
" La dirección de retorno, determinada por el puntero al segmento de código de la unidad que llama, más el desplazamiento al interior de ese segmento.
" El enlace dinámico, o puntero al registro de activación de la unidad que llama.
El tratamiento de los registros de activación es de naturaleza LIFO y, consecuentemente, la estructura de soporte el stack. Esto favorece la implementación de algoritmos recursivos.
Gráficamente:
Representación de un stack de registros de activación:
• Invocaciones explícitas
La comunicación entre unidades de programa se puede efectuar mediante parámetros. A diferencia de la comunicación a través de entornos globales, los parámetros permiten la variabilidad de los elementos transferidos en diferentes llamadas. Luego, los parámetros formales constituyen parte del registro de activación.
Generalmente, los lenguajes utilizan la modalidad de correspondencia posicional entre parámetros actuales y formales en llamadas a subprogramas.
Sin embargo, existe una alternativa conocida como correspondencia nominal, en la cual se indica explícitamente en la invocación la correspondencia entre parámetros actuales y formales. Por ejemplo, en la invocación:
Inicializar (Tabla is V, Limite is N);
V y N son los parámetros actuales que corresponden a los parámetros formales Tabla y Limite en una definición como
procedure Inicializar(Limite: in integer; Tabla: in out Arreglo);
• Invocaciones implícitas
Ciertos lenguajes contemplan la invocación implícita de una unidad cuando se produce alguna situación de excepción. Esta cualidad permite excluir aquellos errores que podrían desviar la atención del objetivo principal del programa.
Las unidades que se activan cuando se detecta alguna irregularidad se denominan manejadores de excepciones.
Un manejador de excepciones en Delphi se establece como bloque protegido, delimitado por try/end, en cuyo interior las palabras reservadas except o finally proveen dos formas alternativas de comportamiento: except se usa para tratar errores mediante una instrucción ad-hoc; finally para ejecutar acciones finales de liberación de recursos tales como memoria.
Ejemplos:
function Potencia(Base, Exponente : Real) : Real;
begin
try
Result := Exp(Ln(Abs(Base))*Exponente);
if (Base < 0) And (Odd(Trunc(Exponente))) then Result := -Result;
except
on EMathError do Result := 0;
end;
end;
function Fib(N : Byte) : Longint;
type Puntero = ^Arreglo;
Arreglo = Array[0..255] of Longint;
var Lista : Puntero;
B : Byte;
F : Longint;
begin
New(Lista);
try;
Lista^[0] := 0;
Lista^[1] := 1;
for B := 2 to N-1 do Lista^[B] := Lista^[B-1] + Lista^[B-2];
F := Lista^[N-1];
finally
Dispose(Lista);
end;
Result := F;
end;
5.2. UNIDADES SIMÉTRICAS
Las unidades simétricas, o corrutinas, son unidades que se activan mutua, alternada y explícitamente. El código, en Algol68:
corroutine X;
begin
···
resume Y;
···
resume Y;
···
end;
corroutine Y;
begin
···
resume X;
···
resume X;
end;
se puede representar, gráficamente, como sigue:
X Y
La sentencia "resume" tiene un comportamiento similar al de una sentencia "call" con la salvedad de que el punto de entrada a la corrutina es variable.
La ejecución de una sentencia "resume" en X involucra dos acciones:
" Almacenar en la dirección de reinicio la dirección de la sentencia inmediatamente posterior a resume Y.
" Accesar la dirección de reinicio de Y para obtener la dirección en la cual debe continuar la ejecución.
5.3. UNIDADES CONCURRENTES
Dos procesos son paralelos si se pueden ejecutar (conceptualmente) en forma simultánea.
Dos procesos paralelos son disjuntos si, durante ejecución, no acceden a recursos compartidos.
Dos procesos paralelos son concurrentes si, durante ejecución, interactúan compitiendo por el acceso a recursos compartidos (competición) y cooperando para alcanzar un objetivo común (cooperación).
Los procesos concurrentes interactúan en forma correcta sólo si existe una cierta relación de procedencia entre sus acciones elementales, lo cual se logra estableciendo una adecuada sincronización entre ellos.
Mecanismos de sincronización:
• Semáforos
Un semáforo constituye un mecanismo de bajo nivel y se define como un objeto de dato que toma valores enteros y sobre el cual se pueden realizar las operaciones atómicas P y V.
• Monitores
Un monitor es un tipo abstracto de dato con las operaciones primitivas Agregar y Extraer. La exclusión mutua en el acceso a recursos compartidos está implícitamente garantizada por la implementación. Sin embargo, la cooperación debe programarse explícitamente, suspendiendo y activando procesos mediante operaciones primitivas.
• Rendezvous
Es el mecanismo proporcionado por el lenguaje Ada para establecer la sincronización de procesos concurrentes (a los que se les denomina "tasks") mediante el cual desaparece la distinción entre entidades activas (procesos) y pasivas (monitores). Este esquema refleja más claramente el comportamiento de un sistema concurrente en una estructura distribuida, en la cual recursos ajenos son administrados por procesos que actúan como guardianes.
6. PARAMETRIZACIÓN
Cada uno de los elementos que participan en la representación de una variable (nombre, tipo, referencia y valor) es susceptible de ser parametrizado. Sin embargo, la parametrización del tipo establece una diferencia conceptual importante en la categorización de los lenguajes.
Luego, se diferenciará entre parametrización de datos (para aludir al nombre, la referencia o el valor) y parametización de tipos. Por otra parte, además de datos, también es posible la parametrización de subprogramas.
6.1. PARAMETRIZACIÓN DE DATOS
Considérense los siguientes subprogramas:
procedure uno(<modalidad> a, b : integer);
begin
a := 7;
b := 5;
end;
procedure cero;
var c, d : integer;
begin
c:= 5;
d := 7;
uno(c, d);
write(c, d);
end;
• Llamada por nombre
Bajo esta modalidad, al producirse una invocación, cada parámetro formal es textualmente sustituido por el respectivo parámetro actual.
En este caso, <modalidad> ::= name.
Ejemplo:
c : = 5;
d := 7;
uno(c, d);
write(c, d);
! !
7 5
ya que la regla de sustitución establece que, en "uno", las sentencias a ejecutar son:
c := 7;
d := 5;
Gráficamente:
Esta regla, aparentemente simple, puede provocar efectos inesperados. Por ejemplo, si se tiene
procedure swap(name a, b : integer);
var temp : integer;
begin
temp := a;
a := b;
b := temp;
end;
la llamada
swap(i, v[i]);
puede producir un resultado imprevisible e incorrecto, ya que la regla de sustitución especifica que las sentencias a ejecutar son:
temp := i;
i:= v[i];
v[i] := temp;
de modo que, si i = 3 y v[3] = 4 antes de la llamada, entonces i = 4 y v[4] = 3 al finalizar la ejecución.
1 2 3 4 5 n
v :
Otra situación poco clara se presenta con el código
procedure dos;
var c: integer;
procedure swap(name a, b : integer);
var temp : integer;
begin
temp := a;
a := b;
b := temp;
c := c + 1;
end;
procedure tres...
var c, d : integer;
begin
c := 5;
d := 7;
swap(c, d);
write(c,d);
end;
begin
c := 5;
tres;
end;
ya que la regla de sustitución especifica que las sentencias a ejecutar son:
temp := c;
c := d;
d := temp;
c := c + 1;
segmento de código en el cual la variable c de la última línea no es la misma que aparece en las líneas primera y segunda.
• Llamada por referencia
Los parámetros actuales transfieren su referencia a los respectivos parámetros formales. Si se acepta como parámetro actual una expresión, se transfiere la dirección de la variable temporal que contiene el valor de la expresión.
En este caso, <modalidad> ::= ref.
Ejemplo:
c : = 5;
d := 7;
uno(c, d);
write(c, d);
! !
7 5
Gráficamente:
• Llamada por copia
Los parámetros actuales se relacionan con sus respectivos parámetros formales mediante la asignación de valores.
Existen tres formas:
" Llamada por valor
Los valores de los parámetros actuales se utilizan para inicializar los respectivos parámetros formales.
En este caso, <modalidad> ::= in.
Ejemplo:
c : = 5;
d := 7;
uno(c, d);
write(c, d);
! !
5 7
Al producirse la invocación de "uno" se ejecutan las acciones a := c y b := d;
Gráficamente:
" Llamada por resultado
Los parámetros formales no se inicializan al invocarse el subprograma pero, al terminar éste su ejecución, los valores de aquellos son asignados a los respectivos parámetros actuales usados en la llamada.
En este caso, <modalidad> ::= out.
Ejemplo:
uno(c, d);
write(c, d);
! !
7 5
Al finalizar la ejecución de "uno" se ejecutan las acciones c := a y d := b;
Gráficamente:
" Llamada por valor-resultado
Se trata de un efecto combinado de llamada por valor, al producirse la invocación, y llamada por resultado, al terminar la ejecución del subprograma.
En este caso, <modalidad> ::= in out.
Ejemplo:
c : = 5;
d := 7;
uno(c, d);
write(c, d);
! !
7 5
Gráficamente:
• Llamada por indirección
Se trata de una llamada por valor en la cual el parámetro formal recibe la dirección de la variable utilizada como parámetro actual.
En este caso, también <modalidad> ::= in. Sin embargo, en la definición se debe anteponer el operador de indirección (por ejemplo, *) al nombre del parámetro formal y, en la invocación, se debe anteponer el operador de dirección (por ejemplo, &) al nombre del parámetro actual.
procedure uno(in *a, *b : integer);
begin
*a := 7;
*b := 5;
end;
procedure cero;
var c, d : integer;
begin
c := 5;
d := 7;
uno(&c, &d);
write(c, d);
! !
7 5
end;
Gráficamente:
6.2. PARAMETRIZACIÓN DE TIPOS
• Unidades genéricas
En lenguaje Ada, la parametrización de tipos se define mediante el concepto de unidad genérica y se implementa mediante el concepto de macro-expansión.
Una unidad genérica es una unidad formal (modelo) cuyos parámetros son instalados en tiempo de traducción produciéndose una unidad actual.
La parametrización de tipos involucra un alto nivel de abstracción y disminuye el tamaño del código fuente.
Sea el siguiente subprograma genérico en lenguaje Ada:
generic type T;
procedure Swap(X, Y : in out T) is
Temp : T;
begin
Temp:= X;
X := Y;
Y := Temp;
end;
En este caso, el tipo de X e Y es el parámetro que debe ser sustituido en tiempo de traducción.
La producción de distintos subprogramas, que difieran sólo en el tipo de sus argumentos, se puede lograr, por ejemplo, mediante:
procedure Swapinteger is new Swap (integer);
procedure Swapreal is new Swap (real);
• Plantillas de funciones
En lenguaje C++, las funciones genéricas, es decir las funciones que parametrizan tipos, se presentan como plantillas de funciones. Se escribe una definición de plantilla de función con el propósito de que el compilador genere, en forma automática, tantos códigos objeto de función como llamadas con diferentes tipos de argumentos existan.
Una plantilla de función se define, por ejemplo, como template <CLASS T>, donde template y CLASS son palabras reservadas y T es un parámetro formal de tipo (puede haber varios).
#include <iostream.h>
template <CLASS T>
void printArray(T *array, const int k)
{ for(int i = 0; i < k; i++)
cout << array[i] << " ";
cout << '\n';
}
main()
{ const int ak = 4, bk = 6, ck = 5;
int a[4] = {1, 2, 3, 4};
float b[6] = {1.1, 2.2, 3.3, 4.4, 5.5, 6.6};
char c[5] = "Hola";
cout << "El arreglo a contiene: \n";
printArray(a, ak);
cout << "El arreglo b contiene: \n";
printArray(b, bk);
cout << "El arreglo c contiene: \n";
printArray(c, ck);
return 0;
}
6.3. PARAMETRIZACIÓN DE SUBPROGRAMAS
El envío de un subprograma como parámetro requiere pasar una referencia al segmento de código del parámetro actual y la información respecto del entorno no local de ese parámetro.
Por consiguiente, un subprograma parámetro se puede representar como un par ordenado (c, r) donde c es un puntero al segmento de código y r un puntero al registro de activación de la unidad que contiene la definición del subprograma. Por ejemplo:
procedure P...
···
procedure A...
···
begin
···
end;
procedure B(procedure X);
var y: integer;
procedure C...
···
begin
···
end;
begin
X;
B(C);
···
end;
begin
···
B(A);
···
end;
P llama a B con el procedimiento A como parámetro actual. Como B tiene definido un parámetro formal X, la llamada a X activa el procedimiento A. Seguidamente, B se autoinvoca con el procedimiento C como parámetro actual.
ypedef int function(int);
typedef int vector[5];
vector v = {5, 6, 7, 8, 9};
int mas(int k)
{ return k + 2; }
int por(int k)
{ return 2*k; }
int suma(function *f)
{ int i, s = 0;
for(int i = 0; i < 5; i++)
s += f(v[i]);
return s;
}
void main()
{ printf("%d", suma(mas));
printf("%d", suma(por));
}
7. CONTROL DE DATOS
7.1. DEFINICIONES
• Alcance
Rango de código en el cual está activo un nombre de objeto, es decir, segmento de programa en el cual todas las instancias de un identificador se refieren al mismo objeto de dato.
• Extensión
Tiempo de ejecución durante el cual una variable se encuentra ligada a su referencia.
• Entorno de referencia
Conjunto de objetos de dato activos al interior de un segmento de código. Queda determinado por las reglas de alcance que provee el lenguaje.
7.2. REGLAS DE ALCANCE
• Estáticas
Permiten determinar el alcance de un nombre de objeto de dato durante compilación (Fortran, Pascal, C, Ada, etc.).
Esta modalidad se basa en el concepto de registros de activación léxicamente anidados, es decir, el uso de un objeto de dato genera una búsqueda del nombre de ese objeto en (el registro de activación de) la unidad en curso; si no se encuentra allí, se le busca en la primera unidad que incluya (léxicamente) a aquella; de no encontrarse en ese ambiente, se le busca en la siguiente unidad jerárquicamente superior; este proceso se puede extender hasta llegar al programa principal.
• Dinámicas
Permiten determinar el alcance de un nombre de objeto de dato durante ejecución (Apl, Lisp, Snobol, etc.).
Bajo esta modalidad, el uso de un objeto de dato provoca la búsqueda del nombre de ese objeto en (el registro de activación de) la unidad en curso; si no se encuentra allí, se le busca en la unidad que invocó a aquella; de no encontrarse en ese ambiente, el proceso de búsqueda continúa en sentido inverso al de las invocaciones, hasta encontrar el objeto en cuestión.
• Ejemplo
Con respecto a la ejecución del siguiente código:
program Alcance(input, output);
var b: integer;
procedure Z;
begin
write(b);
end;
procedure Y;
var b: integer
begin
b := 9;
Z;
end;
begin
b := 5;
Y;
end.
según las reglas de alcance estático, se imprime 5 y, según las reglas de alcance dinámico, se imprime 9. Gráficamente:
7.3. IMPLEMENTACIÓN
• Alcance estático
En Fortran, la extensión de los objetos de datos en un programa coincide con el tiempo destinado a su completa ejecución. Cuando se invoca un subprograma, se activan todos los objetos locales, con excepción de aquellos declarados en una sentencia Common. Al terminar la ejecución del subprograma, se desactivan todos los objetos locales (manteniendo los últimos valores adquiridos) y se activan todos los objetos de la unidad que lo invocó. Cada subprograma posee un registro de activación que contiene:
" Objetos locales
" Parámetros
" Dirección de área Common
" Dirección de retorno
En Pascal, la extensión de los objetos de datos en un programa comienza en el instante en que este se activa y termina cuando devuelve el control a la unidad que lo invocó. La excepción la constituyen los datos creados con new los cuales sólo son destruidos con dispose. Cada subprograma posee un registro de activación que contiene:
" Objetos locales
" Parámetros
" Enlace a objetos no locales activos
" Dirección de retorno
" Enlace dinámico
La referenciación de objetos no locales se consigue mediante una cadena de punteros estáticos, lo cual significa que cada registro de activación incluye un puntero al registro de activación del primer subprograma que lo contenga léxicamente.
Lo anterior se encuentra condicionado por las operaciones push y pop de registros (según se concreten las invocaciones y concluyan las ejecuciones de subprogramas) sobre un stack de registros de activación.
Con respecto al código:
program U;
procedure A;
procedure B;
procedure C;
begin
A;
end {C};
begin
C;
end {B};
procedure D;
begin
B;
end {D};
begin
D;
end {A};
begin
A;
end {U}.
la cadena de punteros estáticos es:
y el stack de registros de activación, presenta el siguiente comportamiento:
• Alcance dinámico
El soporte de las reglas de alcance dinámico es un stack de registros de activación y la referenciación de objetos de datos no locales desencadena procesos de búsqueda determinados por el comportamiento LIFO. El registro de activación perteneciente a cada unidad de programa contiene:
" Objetos locales
" Parámetros
" Dirección de retorno
" Enlace dinámico
7.4. EXTENSIÓN DE DATOS
Las características de los datos determinan su extensión y se establecen durante el proceso de definición de un lenguaje.
Existen tres categorías de datos:
• Estáticos
Tienen una extensión coincidente con la ejecución de la totalidad del programa. El soporte de almacenamiento es un área fija de memoria (Fortran).
• Automáticos
Tienen una extensión determinada por el tiempo que toma la ejecución de la totalidad de la unidad en la cual se encuentran definidos. El soporte de almacenamiento es un stack de registros de activación.
• Dinámicos
Tienen una extensión definida por el programador, quien los crea y destruye explícitamente. El soporte de almacenamiento es un bloque de memoria denominado heap.
Dependiendo de la extensión inherente a los datos, cada lenguaje utiliza una o más alternativas de soporte de almacenamiento.
7.5. SOPORTE HEAP
Un heap es un bloque de memoria compuesto de elementos de tamaño fijo o variable, dentro del cual se puede reservar o liberar espacio de manera no estructurada.
• Heap de elementos de tamaño fijo
Si k es el tamaño de un elemento (en bytes) y n es la cantidad total de elementos del heap, entonces éste ocupará un espacio de k*n bytes.
En un heap, el espacio disponible tiene la estructura de una lista de enlace simple; luego, cada vez que se solicita espacio, se desplaza el puntero de acceso al próximo elemento libre, y se retorna un puntero al primer elemento del espacio reservado.
Los elementos que conforman una variable, pueden distribuirse, por ejemplo, del siguiente modo:
" Nombre y Referencia, en un espacio fijo de memoria (tabla de variables).
" Atributo y Valor, en un espacio al interior de un heap (a partir de la referencia).
El proceso de devolución de elementos en desuso a la lista de espacio disponible es simple, sin embargo, el proceso de identificación de esos elementos como tales resulta ser extremadamente complejo. Existen tres formas de solución a este problema:
" Devolución explícita
Mecanismo que permite al programador identificar y devolver los elementos en desuso. Presenta dos inconvenientes:
" Dangling reference
Puntero a un elemento que ha sido devuelto a la lista de espacio disponible. Conceptualmente, en Pascal,
new(p); q := p; dispose(p); {q es una dangling reference}
Como ejemplo de dangling reference en lenguaje C se tiene
int *f(void)
{ int x = 1;
return &x;
}
donde la función f retorna una dangling reference debido a que la extensión de la variable local x termina con la activación de f.
" Garbage
Elemento en condición de ser reutilizado pero inaccesible debido a su no devolución a la lista de espacio disponible. Conceptualmente, en Pascal,
new(p); p:=q;
Dangling reference es, potencialmente, más peligroso que garbage.
" Cuenta referencias
Consiste en incluir, al interior del espacio para cada variable en el heap, un contador de referencias que lo apuntan. Al reservarse un espacio, el contador se inicializa en 1; cada vez que se le asocia una nueva variable, el contador se incrementa en 1; en cambio, cada vez que una variable se desliga de ese espacio, el contador se decrementa en 1. Si el contador toma el valor 0, el espacio en cuestión se devuelve a la lista de espacio disponible.
" Garbage Collection
Esta técnica consiste en que, cuando la lista del espacio disponible se agota y se requiere más memoria, se suspende temporalmente la ejecución del proceso solicitante precediéndose a marcar los elementos en uso y recolectar los elementos en desuso (devolverlos a la lista de espacio disponible).
• Heap de elementos de tamaño variable
En este caso, se desea organizar el espacio disponible en bloques del máximo tamaño posible. Luego, inicialmente, el heap tiene el carácter de bloque disponible único y, solicitar un bloque de m bytes implica:
" Avanzar m posiciones al puntero de acceso.
" Retornar la dirección a la cual apuntaba el puntero de acceso.
A causa de la variabilidad en el tamaño de los bloques, el problema de reutilización de espacio se puede resolver de dos formas:
" Buscar en la lista el espacio disponible y reservar un bloque del tamaño adecuado devolviendo, si existe, el espacio sobrante de la lista.
" Generar un único bloque de espacio disponible mediante el desplazamiento de todos los elementos en uso hacia un extremo del heap (compactación).
8. EL MODELO DE ORIENTACIÓN A OBJETOS
8.1. GENERALIDADES
• Abstracción
Modelo conceptual de un ente real, que sólo considera los aspectos esenciales e ignora los aspectos no esenciales.
• Abstracción de datos
Técnica de programación que permite definir tipos de datos inexistentes en un lenguaje a partir de los existentes.
• Abstracción de control
Técnica de programación que permite la codificación de algoritmos mediante estructuras de control en calidad de sentencias o en calidad de unidades (de código).
• Tipo Abstracto de Dato (TAD)
Modelo conceptual representativo de un conjunto de objetos cuyas características sólo se pueden establecer a través de una colección de operaciones.
• Definición
Especificación de un TAD.
• Representación
Especificación de los objetos de dato seleccionados para soportar un TAD.
• Implementación
Especificación de las operaciones (algoritmos) definidas sobre un TAD.
• Codificación
Especificación de la representación y la implementación según las formalidades sintácticas de un lenguaje de programación.
• Programa
Unidad que integra la codificación según las exigencias de estructura sintáctica inherentes a un lenguaje de programación.
• Procedimiento
Unidad reutilizable de código que no contempla restricciones de accesibilidad a los datos ni garantías de ocultamiento de los mismos.
• Módulo
Modelo de especificación de TAD, de naturaleza reutilizable, que contempla restricciones de accesibilidad a los datos y encapsulamiento (ocultamiento de los datos) y que no provee la capacidad de instanciación.
• Clase
Modelo de especificación de TAD que provee encapsulamiento e instanciación. Se trata de un modelo de tipo más una implementación, cuyo modelo de construcción es similar al de un producto cartesiano.
• Objeto
Ejemplar (o instancia) de una clase visto como una combinación de estado y comportamiento.
8.2. ORIENTACIÓN A OBJETOS
• Definición
Se entiende por Orientación a Objetos al conjunto de propiedades que, aplicadas al diseño y la construcción de software, permite el desarrollo de complejos sistemas de información a partir de componentes.
Las propiedades más importantes del modelo orientado a objetos son la abstracción, la modularidad, el encapsulamiento, la jerarquía y el polimorfismo.
• Abstracción
Propiedad consistente en representar sólo las características esenciales de un objeto, omitiendo aquellos aspectos no esenciales.
• Modularidad
Propiedad consistente en subdividir una aplicación en pequeñas partes, llamadas módulos, tan independientes del todo y de las restantes partes como sea posible.
• Encapsulamiento
Propiedad que consistente en ocultar al mundo exterior la información contenida en la representación de un objeto.
Permite, además, que cada módulo integrante de una aplicación conste de dos partes: la interfaz y la implementación. La interfaz constituye la vista externa de un módulo. La implementación corresponde a la codificación del comportamiento de un objeto.
• Jerarquía
Propiedad que permite ordenar estructuralmente las abstracciones. Las dos formas jerárquicas más importantes son la especialización (relación es-un) y la agregación (relación tiene-un).
• Polimorfismo
Propiedad consistente en permitir a una entidad la adopción de múltiples formas. El polimorfismo permite referirse a objetos de clases diferentes mediante un mismo código y realizar la misma operación de diferentes formas según la naturaleza del objeto referenciado.
8.3. TIPOS ABSTRACTOS DE DATOS
• Individualización de conceptos
Tipo: Colección de elementos de características similares.
Abstracto: No concreto, conceptual.
Dato: Objeto representable computacionalmente.
• Definición
Un Tipo Abstracto de Dato es un modelo constituido por un conjunto de objetos y una colección de operaciones realizables sobre ellos.
• Codificación
Los lenguajes procedimentales no contemplan encapsulamiento, razón por la cual la representación (datos) no es exclusiva de la implementación (operaciones).
Los lenguajes modulares proveen encapsulamiento, exclusividad de la implementación sobre la representación, pero no instanciación.
Los lenguajes orientados a objetos proveen encapsulamiento, exclusividad de la implementación sobre la representación e instanciación.
8.4. LA PROGRAMACIÓN ORIENTADA O OBJETOS
• Conceptos introductorios
" Un objeto es un modelo de una entidad real.
" Los objetos se manipulan a través de mensajes.
" Los mensajes que reconoce un objeto definen su comportamiento.
" Un mensaje enviado a un objeto activa un método.
" Objetos de un mismo tipo constituyen una clase.
" Un objeto es un ejemplar (o una instancia) de su clase.
" Las variables de ejemplar de un objeto representan su estado.
• Evolución de los lenguajes de programación
Lisp Flavors Loops Clos
Eiffel
Simula Smalltalk
Actor
Algol Objective C
C C++ Java
Pascal Object Pascal Delphi
1960 1970 1980 1990
• Paradigmas de programación
" Orientado a objetos " Procedimental
" Objeto " Variable
" Clase " Tipo
" Método " Procedimiento
" Mensaje " Llamada
" Jerarquía de clases " Jerarquía de tipos
• Conceptos relacionados
" Procedimental " Orientado a objetos
" Universo cerrado " Universo abierto
" Acoplamiento fuerte " Acoplamiento débil
" Strong typing " Weak typing
" Nombre!tipo " Tipo!valor
" Tipos manifiestos " Tipos latentes
" Ligadura anticipada " Ligadura tardía
" Eficiencia " Flexibilidad
• Mensajes y métodos
" Un objeto (agente emisor) envía un mensaje a otro objeto (agente receptor).
" El mensaje tiene codificada la petición de una acción.
" El mensaje incluye los datos (argumentos) necesarios para satisfacer la petición.
" Si el receptor acepta el mensaje, acepta la responsabilidad de ejecutar la acción indicada.
" En respuesta a un mensaje, el receptor ejecuta el método que satisface la petición.
• Clases y ejemplares
" Todos los objetos son ejemplares de una clase.
" La clase del receptor determina el método que se activa como respuesta a un mensaje.
" Todos los objetos de una clase usan el mismo método en respuesta a mensajes similares.
8.5. CLASES Y MÉTODOS
• Fundamentos
" Los objetos son ejemplos de TAD's.
" Un TAD tiene dos caras: una exterior, la que ve el usuario, y una interior, la que sólo ve el programador.
" El usuario ve nada más que un conjunto de operaciones que definen el comportamiento de la abstracción.
" El programador ve las variables de datos que se usan para mantener el estado interno del objeto.
" Un ejemplar es un representante de una clase.
" Una variable de ejemplar es una variable interna mantenida por un ejemplar.
" Cada ejemplar tiene su propia colección de variables de ejemplar.
" Las variables de ejemplar sólo son modificables por los métodos definidos en la clase.
" Un objeto es la combinación de estado y comportamiento.
" El estado lo determinan las variables de ejemplar.
" El comportamiento lo determinan los métodos.
" Desde el exterior, los clientes sólo pueden ver el comportamiento de los objetos.
" Desde el interior, los métodos proporcionan el comportamiento apropiado mediante las modificaciones del estado.
" La interfaz describe la forma en que un objeto se conecta con el mundo.
" La implementación describe cómo se logra la responsabilidad prometida en la interfaz.
" Una clase se puede concebir como un registro con dos variedades de campos: datos y procedimientos.
" Los datos constituyen las variables de ejemplar.
" Los procedimientos constituyen los métodos.
• Ejemplo 1
class Stack
{ private:
int v[100];
int top;
public:
void create();
void push(int e);
int pop();
int empty();
};
void Stack::create()
{ top = "1;}
void Stack::push(int e)
{ if(top < 99)
{ top++;
v[top] = e;
}
}
int Stack::pop()
{ int m;
if (top > "1)
{ m = top;
top "";
return v[m];
}
else
return 0;
}
int Stack::empty()
{ return top == "1;}
void main()
{ Stack s;
int i, k, n;
cout << "Ingrese un valor entero menor que 99: ";
cin >> n;
s.create();
for (i = 0; i < n; i++)
{ cout << "Ingrese un valor entero : ";
cin >> k;
s.push(k);
}
while (!s.empty())
{ k = s.pop();
cout << "Ultimo valor: " << k << endl;
}
}
8.6. MENSAJES Y EJEMPLARES
• Notación en C++
" Los métodos se conocen como funciones miembro y las variables de ejemplar como miembros de datos.
" Si D es una subclase de una clase B, entonces D se conoce como clase derivada y B como clase base.
" La notación del envío de mensajes es la misma utilizada para referenciar campos de un registro, es decir, nombre del receptor, seguido por un punto, seguido por el selector de mensaje (nombre de una función miembro). Por ejemplo, s.pop() o (*p).pop().
" Un constructor es un método que tiene el mismo nombre de la clase.
" El constructor se ejecuta siempre que se crea un objeto.
" El mecanismo de constructores se puede combinar con la capacidad de sobrecarga (dos o más cuerpos de función conocidos por el mismo nombre).
" La ambigüedad de las funciones sobrecargadas se obvia mediante la diferencia en las listas de parámetros.
" Se usa esta capacidad para proporcionar más de un estilo de inicialización.
" Un destructor es un método con el mismo nombre de la clase, precedido por el símbolo ".
" El destructor se ejecuta al producirse la liberación del espacio asignado a un objeto: para un objeto automático, cuando termina la ejecución del bloque que contiene la declaración; para un objeto dinámico, cuando se aplica el operador delete.
• Ejemplo 2
class Complejo
{ public:
float real;
float imag;
Complejo();
Complejo(float pr);
Complejo(float pr, float pi);
void imprimir();
"Complejo();
};
Complejo::Complejo()
{ real = imag = 0; }
Complejo::Complejo(float pr)
{ real = pr; imag = 0; }
Complejo::Complejo(float pr, float pi)
{ real = pr; imag = pi; }
void Complejo::imprimir()
{ cout << "(" << real << "," << imag << ")"; }
Complejo::"Complejo()
{ cout << "liberando complejo " << real << imag; }
void main()
{ Complejo x, y(4.0), *z;
z = new Complejo(3.14159,2.4);
x.imprimir();
y.imprimir();
(*z).imprimir();
}
• Ejemplo 3
class Fraccion
{ private:
int num;
int den;
public:
Fraccion(int, int);
void imprimir();
float valor();
};
Fraccion::Fraccion(int p, int q)
{ num = p;
den = q;
}
void Fraccion::imprimir()
{ cout << '\n';
cout << num << "/" << den << "=";
}
float Fraccion::valor()
{ return (float)num/den; }
void main()
{ int n, d;
float x;
do
{ cout << "Numerador:";
cin >> n;
cout << "Denominador:";
cin >> d;
if (d != 0)
{ cout << "Objeto de clase Fraccion";
Fraccion f(n,d);
f.imprimir();
x = f.valor();
cout << x;
}
}while (d != 0);
}
• Ejemplo 4
class Lengua
{ char *token;
public:
Lengua(char *t);
"Lengua();
};
Lengua::Lengua(char *t)
{ token = t;
cout << "Lenguaje" << token << endl;
}
Lengua::"Lengua()
{ cout << "orientado a objetos es" << token << endl; }
void main()
{ Lengua bb("Object Pascal");
cout << "es compilado." << endl;
{ Lengua cc("Pascal");
cout << "también lo es. Pero no" << endl;
}
cout << "En cambio sí" << endl;
}
• Ejemplo 5
class Lista
{ private:
int dato;
Lista *link;
public:
Lista(Lista *next, int e)
{ dato = e; link = next; }
Lista *siguiente()
{ return link; }
int valor()
{ return dato; }
}
void main()
{ int j = 5;
Lista *p = new Lista(0,j);
for(j = 4; j > 0; j"")
{ p = new Lista(p,j); }
}
• Separación entre interfaz e implementación
La separación entre interfaz, implementación y uso de una clase resulta ser uno de los principios fundamentales la ingeniería de software. Con esto, los cambios en la implementación, que no alteren la interfaz, pasan desapercibidos por los clientes de la clase.
Una forma consiste en crear un archivo, con extensión ".h", destinado a la interfaz de una clase y otro, con extensión ".cpp", destinado a la implementación de la misma. Otra forma consiste en crear un único archivo, con extensión ".h", destinado a la interfaz e implementación de una clase. El uso de esa clase se consigue creando un "main" en un archivo con extensión ".cpp", que incluya al archivo con extensión ".h".
• Ejemplo 6
// Interfaz de la clase Stack en el archivo defstack.h
#ifndef defstack
#define defstack
class Stack
{ private:
int v[100];
int top;
public:
Stack();
void push(int);
int pop();
int empty();
};
#endif
// Implementación de la clase Stack en un archivo con extensión cpp
#include <iostream.h>
#include "defstack.h"
Stack::Stack()
{ top = -1;}
void Stack::push(int e)
{ if(top < 99)
{ top = top + 1;
v[top] = e;
}
}
int Stack::pop()
{ int m;
if (top > -1)
{ m = top;
top = top - 1;
return v[m];
}
else
return 0;
}
int Stack::empty()
{ return top == -1;}
// Uso de la clase Stack en un archivo con extensión cpp
#include <iostream.h>
#include "defstack.h"
main()
{ Stack s;
int i, k, n;
cout << "Ingrese un valor entero menor que 99: ";
cin >> n;
s.create();
for (i = 0; i < n; i++)
{ cout << "Ingrese un valor entero : ";
cin >> k;
s.push(k);
}
while (!s.empty())
{ k = s.pop();
cout << "Ultimo valor: " << k << endl;
}
return 0;
}
8.7. PLANTILLAS DE CLASES
• El concepto
Para personalizar la definición de una plantilla genérica de clase se requiere de uno o más parámetros de tipo. Es el compilador quien genera el código fuente para tantas clases diferentes como instancias diferentes de tipos existan en calidad de parámetros actuales. Una plantilla de clase se define, por ejemplo, como, template <class T>.
• Ejemplo 6
// Interfaz de la clase Stack en el archivo defstack.h
#ifndef defstack
#define defstack
template <class T>
class Stack
{ public:
Stack(int = 10);
"Stack();
int push(const T&);
int pop(T&);
int empty() const
{ return top == "1; }
private:
int largo;
int top;
T *p;
};
template <class T>
Stack< T>::Stack(int s)
{ largo = s;
top = -1;
p = new T[largo];
}
template <class T>
Stack< T>::"Stack()
{ delete [] p; }
template <class T>
int Stack< T>::push(const T &e)
{ if (top < largo - 1)
{ p[++top] = e;
return 1;
}
return 0;
}
template <class T>
int Stack< T>::pop(T &e)
{ if (!empty())
{ e = p[top--];
return 1;
}
return 0;
}
#endif
// Uso de la clase Stack en un archivo con extensión cpp
#include <iostream.h>
#include "defstack.h"
void main()
{ Stack<float> fs(5);
float f = 1.1;
cout << "Se pone un elemento en el stack fs \n";
while (fs.push(f))
{ cout << f << ' ';
f += 1.1;
}
cout << "\n El stack está lleno. No se puede poner el valor " << f
<< "\n\n Se saca un elemento del stack fs" << endl;
while (fs.pop(f))
cout << f << ' ';
cout << "\n El stack está vacío. No se puede sacar " << endl;
Stack<int> is;
int i = 1;
cout << "Se pone un elemento en el stack is \n";
while (is.push(i))
{ cout << fi<< ' ';
i++;
}
cout << "\n El stack está lleno. No se puede poner el valor " << i
<< "\n\n Se saca un elemento del stack is" << endl;
while (is.pop(i))
cout << i << ' ';
cout << "\n El stack está vacío. No se puede sacar " << endl;
};
8.8. HERENCIA SIMPLE
• El concepto
" Las clases pueden organizarse como una estructura jerárquica.
" Una subclase hereda atributos de una superclase.
" Una metaclase es una superclase que sólo se usa para crear subclases y para la cual no existen ejemplares directos.
" Una subclase puede anular un método de una superclase con el propósito de contemplar una excepción.
• Jerarquía de clases
Mamífero
Felino Humano Monotremas
Sociólogo Ingeniero Artista
Ana Luis Ornitorrinco Equidna
• Caracterización
" Herencia: propiedad que permite a los ejemplares de una subclase acceder a los datos y métodos de la clase paterna.
" La herencia es transitiva.
" Contradicción entre herencia como extensión y herencia como reducción:
" Una subclase tiene todas las propiedades de la clase paterna y otras más.
" Una subclase es una forma más especializada de la clase paterna.
" No se necesita reescribir el código del comportamiento heredado ! aumenta la velocidad de desarrollo.
" Muchos usuarios pueden emplear las mismas clases.
" La reutilización de software sólo exige conocer la naturaleza del componente y su interfaz.
" Los métodos heredados se ejecutan más lentamente que el código especializado.
" El abuso de la herencia sustituye una forma de complejidad por otra.
" Sean dos conceptos abstractos S, B:
" Si tiene sentido el enunciado “S es-un B”, entonces es probablemente correcto hacer de S una subclase de B (p. e. un rombo es-un polígono).
" Si es más evidente el enunciado “S tiene-un B”, entonces es probablemente correcto hacer de B un atributo de S (p. e. un rombo tiene-un perímetro).
• Ejemplo 1
class Eslabon
{ private:
int dato;
public:
Eslabon(int d)
{ dato = d; }
int Valor()
{ return dato; }
}
class Cadena : public Eslabon
{ private:
Cadena *sig;
public :
Cadena(Cadena *s, int e) : Eslabon(e)
{ sig = s; }
Cadena *Nex()
{ return sig; }
int Info()
{ return Eslabon::Valor(); }
}
void main()
{ int j = 5;
Cadena *q, *p = new Cadena(0,j);
for(j = 4; j > 0; j--)
{ p = new Cadena(p,j); }
q = p;
for(j = 5; j > 0; j--)
{ cout << "\nValor" << p->Info() << '\n';
p = p->Nex();
}
}
• Miembros protegidos
Los miembros públicos de clase base son accesibles por cualquier función del programa. Los miembros privados de clase base son accesibles por cualquier función miembro o amiga de la clase base.
Los miembros protegidos de clase base son accesibles por cualquier función miembro o amiga de clase la clase base o por cualquier función miembro o amiga de las clases derivadas de la clase base.
• Ejemplo 2
// Interfaz de la clase Par en el archivo depar.h
#ifndef depar
#define depar
class Par
{ public:
Par(const float, const float);
void imprimir() const;
protected:
float px;
float py;
};
#endif
// Implementación de la clase Par en el archivo depar.cpp
#include <iostream.h>
#include "depar.h"
Par::Par(const float x, const float y)
{ px = x;
py = y;
}
void Par::imprimir() const
{ cout << "(" << px << "," << py << ")"; }
// Definición de la clase Trio en archivo detrio.h
#ifndef detrio
#define detrio
#include "depar.h"
class Trio : public Par
{ public:
Trio(const float, const float, const float);
void imprimir() const;
private:
float pz;
};
#endif
// Implementación de la clase Trio en archivo detrio.cpp
#include <iostream.h>
#include "detrio.h"
Trio::Trio(const float x, const float y, const float z) : Par(x, y)
{ pz = z;}
void Trio::imprimir() const
{ cout << "(" << px << "," << py << "," << pz << ")"; }
// Uso de la clase Trio en el archivo usotrio.cpp
#include <iostream.h>
#include "detrio.h"
void main()
{ Trio t(1.5, 2.5, 3.5);
t.imprimir();
}
• Ejemplo 3
class Ficha0
{ protected:
int numref;
char *titulo;
public:
void almacenar(int, char *);
void mostrar();
int refigual(int);
};
void Ficha0::almacenar(int nr, char *t)
{ numref = nr;
titulo = new char[strlen(t)+1];
strncpy(titulo,t,10);
}
void Ficha0::mostrar()
{ cout << " " << numref << " " << titulo;
cout << '\n' << numref << '\n' << titulo;}
int Ficha0::refigual(int k)
{ return k == numref; }
class Ficha1: public Ficha0
{ private:
char *autor;
public:
void almacenar(int, char *, char *);
void mostrar();
int refigual(int);
};
void Ficha1::almacenar(int nr, char *t, char *a)
{ Ficha0::almacenar(nr,t);
autor = new char[strlen(a)+1];
strncpy(autor,a,10);
}
void Ficha1::mostrar()
{ Ficha0::mostrar();
cout << " " << autor << '\n';
}
int Ficha1::refigual(int k)
{ return Ficha0::refigual(k); }
class Ficha2: public Ficha0
{ private:
int numero;
char *nombre;
public:
void almacenar(int, char *, int, char *);
void mostrar();
int refigual(int);
};
void Ficha2::almacenar(int nr, char *t, int k, char *n)
{ Ficha0::almacenar(nr,t);
numero = k;
nombre = new char[strlen(n)+1];
strncpy(nombre,n,10);
}
void Ficha2::mostrar()
{ Ficha0::mostrar();
cout << " " << numero << " " << nombre << '\n';
}
int Ficha2::refigual(int k)
{ return Ficha0::refigual(k); }
• Ejemplo 4
#include <stdio.h>
#include <iostream.h>
class Nodo
{ public:
Nodo *link;
Nodo()
{ link = (Nodo *) 0; }
void poner(Nodo *q)
{ link = q; }
void agregar(Nodo *q)
{ if (link) link->agregar(q); else poner(q); }
void ver()
{ cout << "Valor :" << endl; }
void enTodos(void f(Nodo *))
{ f(this); if (link) link->enTodos(f); }
};
class Lista
{ public:
Nodo *next;
Lista()
{ next = (Nodo *) 0; }
void agregar(Nodo *q)
{ if (next) next->agregar(q); else next = q; }
void enTodos(void f(Nodo *))
{ if (next) next->enTodos(f); }
};
class NodoEnteros: public Nodo
{ private:
int dato;
public:
NodoEnteros(int i) : Nodo()
{ dato = i; }
void ver()
{ Nodo::ver();
cout << "Dato :" << dato;
}
};
void mostrar(NodoEnteros *p)
{ p->ver(); }
void main()
{ Lista h;
h.agregar(new NodoEnteros(3));
h.agregar(new NodoEnteros(5));
h.agregar(new NodoEnteros(7));
h.enTodos(mostrar);
}
8.9. LIGADURA Y ENLACE
• Definiciones
" Ligadura es la acción de asociar tipo, referencia o valor a un nombre de variable.
" Enlace es la acción de asociar una llamada de unidad de programa con el código de la misma.
• Enlace de métodos
" Si el enlace entre un mensaje y un método se basa en las características del nombre del objeto, entonces se trata de un enlace estático o anticipado.
" Si el enlace entre un mensaje y un método se basa en las características del valor del objeto, entonces se trata de un enlace dinámico o tardío.
• Comparación
" La ligadura estática y el enlace estático se caracterizan por su eficiencia.
" La ligadura dinámica y el enlace dinámico se caracterizan por su flexibilidad.
" La ligadura estática simplifica una implementación aun si se combina con el enlace dinámico.
" Si la ligadura estática simplifica una implementación, el enlace estático la simplifica aún más.
" En construcción, la eficiencia es de bajo nivel, mientras que la flexibilidad es de alto nivel.
8.10. MEMORIA Y HERENCIA
• El modelo
" Una subclase agrega nuevos métodos a los proporcionados por la superclase.
" Una subclase define un método con el mismo nombre de uno definido en la clase paterna. Esto anula el método de la superclase pues, cuando se envía un mensaje a un objeto, la búsqueda del respectivo método se inicia en ese objeto.
" Un constructor de subclase siempre invoca al constructor de la clase paterna antes de ejecutar el propio.
" Si Rombo es una subclase de Polígono, entonces un objeto de clase Polígono puede tomar valores de clase Rombo, ya que un rombo es-un polígono.
• Distribución en memoria
Sean las siguientes definiciones de clase y declaraciones de variables:
class Ventana
{ int alto, ancho;
public:
virtual void mismo();
}
class VentanaDeTexto: public Ventana
{ char *indice;
int posCursor;
public :
virtual void mismo();
}
Ventana x;
Ventana *y, *z;
y = new VentanaDeTexto;
z = y;
Interpretación:
" Se reservará en el stack espacio para un objeto de clase Ventana y se ligará a la variable x.
" Se reservará en el heap espacio para un objeto de clase VentanaDeTexto y su dirección se asignará a la variable y.
La asignación x = *y se interpreta como sigue:
" Se copiarán en x sólo los valores de las variables de ejemplar apuntadas por y que existan en x (slicing).
" La semántica asegura que sólo los métodos definidos en la clase Ventana pueden ser invocados usando x.
Respecto de los métodos definidos en Ventana pero anulados en VentanaDeTexto, considerar:
void Ventana::mismo()
{ cout << "Ventana-Base"; }
void VentanaDeTexto::mismo()
{ cout << "VentanaDeTexto-Derivada" << posCursor; }
cuya interpretación es la siguiente:
" Para objetos representados en el stack, el enlace de un mensaje con un método virtual se basa en la clase de la declaración.
" Para objetos representados en el heap, el referido enlace se basa en la clase del valor actual.
" Si se selecciona x.mismo() se ejecutará el método de la clase Ventana.
" Si se selecciona (*z).mismo()se ejecutará el método de la clase VentanaDeTexto.
• Asignación
La sentencia x = y tiene dos posibles interpretaciones:
" Semántica de copia: Se almacena el valor de y en la referencia de x.
" Semántica de punteros: Semántica de copia en la cual el valor almacenado es la referencia de un objeto.
• Igualdad
La expresión x == y tiene dos posibles interpretaciones:
" Equivalencia estructural: x e y son iguales si cada miembro de x tiene el mismo valor de cada miembro de y. Aquí puede suceder que, si y es ejemplar de una subclase de x, entonces x==y sea verdadero pero y==x sea falso.
" Identidad de objetos: x e y son iguales si x e y tienen como valor la misma referencia de objeto.
8.11. HERENCIA MÚLTIPLE
• El concepto
" Capacidad de una clase para heredar de dos o más superclases.
" Herencia simple ! especialización.
" Herencia múltiple ! combinación.
Pintor Artista
PintorDeCasas PintorDeRetratos Alfarero
• Ejemplo
#include <stdio.h>
#include <iostream.h>
class Eslabon
{ private:
int dato;
public:
Eslabon(int d)
{ dato = d; }
int Valor()
{ return dato; }
};
class Cadena
{ private:
Cadena *sig;
public :
Cadena(Cadena *s)
{ sig = s; }
Cadena *Prox()
{ return sig; }
};
class Doble : public Cadena, public Eslabon
{ private:
Doble *ant;
public :
Doble(Doble *d, Doble *s, int e) : Cadena(s), Eslabon(e)
{ ant = d;
if(s != 0)
s->ant = this;
}
Doble *Prev()
{ return ant; }
Doble *Nex()
{ return (Doble*)Prox(); }
int Info()
{ return Valor(); }
};
void main()
{ int j = 5;
Doble *r, *q, *p = new Doble(0,0,j);
r = p;
for(j = 4; j > 0; j--)
{ p = new Doble(0,p,j); }
q = p;
p = r;
for(j = 5; j > 0; j--)
{ cout << "\nValor" << p->Info() << '\n';
p = p->Prev();
}
for(j = 5; j > 0; j--)
{ cout << "\nValor" << p->Info() << '\n';
p = p->Nex();
}
}
• Ejemplo
Considérese la estructura de árbol
interpretada como:
" Una lista de listas enlazadas.
" En un nivel, cada nodo apunta a un hermano.
" Cada nodo en un nivel, puede también apuntar a una lista enlazada que representa a sus descendientes.
Utilizando las definiciones previas de Lista y Nodo, se puede establecer una definición para un árbol como el anterior, de la siguiente manera:
class Arbol : public Nodo, public Lista
{ int valor;
public :
Arbol(int i)
void imprimir()
void agregar(Arbol *q)
void agregarHijo(Arbol *q)
void agregarHermano(Arbol *q)
void enTodos(void f(Nodo *))
}
Arbol::Arbol(int i)
{ valor = i; }
Arbol::imprime()
{ cout << valor; }
Arbol::agregar(Arbol *q)
{ Lista::agregar(q); }
Arbol::agregarHijo(Arbol *q)
{ Lista::agregar(q); }
Arbol::agregarHermano(Arbol *q)
{ Nodo::agregar(q); }
Arbol::enTodos(void f(Nodo *))
{ if (nodos) nodos">enTodos(f);
if(this);
if (prox) prox">enTodos(f); }
}
main()
{ Arbol *t = new Arbol(17);
t">agregar(new Arbol(12));
t">agregaHermanor(new Arbol(25));
t">agregarHijo(new Arbol(15));
t">enTodos(mostrar);
}
8.12. POLIMORFISMO
• Significado
" Un objeto polimórfico es aquel que admite valores de diferentes tipos durante ejecución.
" El polimorfismo favorece la reutilización de software de alto nivel con diferentes abstracciones de bajo nivel.
" El polimorfismo puro consiste en definir una función con argumentos de diferentes tipos.
" El polimorfismo ad-hoc o sobrecarga consiste en definir un mismo nombre para múltiples funciones.
" En los lenguajes con enlace dinámico de métodos, todos los objetos son potencialmente polimórficos.
• Lenguajes con enlace estático
" El polimorfismo aparece a través de la diferencia entre la clase de la declaración (la clase estática) y la clase del valor actual del objeto (la clase dinámica).
" Un objeto puede tener un valor de su clase estática o de cualquier subclase de esa clase.
" Para objetos automáticos el polimorfismo se logra sólo mediante el uso de indirecciones o referencias.
" Para un objeto declarado por valor, la clase dinámica se ve siempre forzada a ser la misma que la clase estática.
" Para un objeto declarado por indirección o por referencia, la clase dinámica se mantiene.
• Ejemplo
class P
{ public:
virtual int valor()
{return 1; }
}
class Q: public P
{ public:
virtual int valor()
{ return 2; }
}
void f1(P x)
{ cout << "Por valor se imprime" << x.valor(); }
void f2(P *x)
{ cout << "Por indirección se imprime" << x">valor(); }
void f3(P &x)
{ cout << "Por referencia se imprime" << x.valor(); }
void main()
{ Q z;
P r, *s, &t;
r = z;
s = &z;
t = z;
f1(z);
f2(&z);
f3(z);
}
" La llamada f1(z) convierte el valor de z en uno de clase P que es la clase del parámetro formal x ! se desplegará el valor 1.
" La llamada f2(&z) no convierte el valor de z pues f2(P *x) define un parámetro formal polimórfico ! se desplegará el valor 2.
" La llamada f3(z) no convierte el valor de z pues f3(P &x) también define un parámetro formal polimórfico ! se desplegará el valor 2.
• Sobrecarga
" Un nombre de función está sobrecargado si existen dos o más cuerpos de función definidos con ese nombre
" Existe sobrecarga cuando un único nombre designa dos o más funciones distintas las cuales proporcionan acciones semánticas similares sobre diferentes tipos de datos
" La coerción es un mecanismo, semánticamente distinto a la sobrecarga, que convierte el tipo de un valor en otro
" Lo anterior permite que, por ejemplo, la suma (+) de dos valores numéricos pueda tener diferentes interpretaciones:
" Cuatro funciones correspondientes a E+E, E+R, R+E y R+R ! existe sobrecarga pero no coerción.
" Dos funciones correspondientes a E+E y R+R; en los otros casos el valor E es forzado a convertirse en R ! existe una combinación de sobrecarga y coerción.
" Una función correspondiente R+R; en los casos restantes el valor E es forzado a convertirse en R ! existe coerción pero no sobrecarga.
• Métodos diferidos
" Un método diferido (o método virtual puro) es un método anulado cuyo comportamiento en la superclase es nulo.
" En C++, un método diferido debe declararse como una función virtual sin cuerpo a la cual se le asigna el valor 0.
" No es posible definir ejemplares de una clase que contenga un método diferido no anulado.
" La redefinición de métodos diferidos debe aparecer en una subclase inmediata.
• Ejemplo
class Forma
{ public:
Punto esquina;
void ponerEsquina(Punto &p)
{ esquina = p; }
virtual void dibujar() = 0;
};
class Circulo: public Forma
{ public:
int radio;
void ponerRadio(int i)
{ radio = i; }
void dibujar()
{ dibujarCirculo(esquina + radio, radio); }
};
GUÍA DE EJERCICIOS
1. Explicar la diferencia entre Lenguaje de Máquina y Lenguaje Simbólico.
2. Describir el criterio de "ortogonalidad" en la definición de un lenguaje. Citar un ejemplo.
3. Explicar el criterio sintáctico conocido como "ausencia de ambigüedad". Citar un ejemplo.
4. Comentar, desde el punto de vista sintáctico, el código
IF IF THEN ELSE = THEN ELSE THEN = ELSE;
5. Describir, brevemente, las alternativas de estructura de definición sintáctica para programas y subprogramas.
6. Citar un caso en el cual un lenguaje de alto nivel constituye lenguaje objeto.
7. Describir el proceso de traducción conocido como "carga".
8. Comente las siguientes afirmaciones:
a) "Un compilador procesa varias veces una sentencia de repetición".
b) "Un intérprete puede no procesar alguna sentencia en un código".
9. Comente las siguientes afirmaciones:
a) "Con respecto al elemento sintáctico 'estructura de programas y subprogramas', la alternativa de definición anidada, concebida por ciertos lenguajes, no involucra un aspecto semántico".
b) "Un metalenguaje constituye la definición formal de los datos que procesa un traductor".
10. Una multilista es una estructura compuesta de átomos y multilistas. Por ejemplo, la multilista
( 1 2 ( 3 4 ( 5 ) 6 ) 7 8 )
consta de cinco elementos: cuatro átomos y una multilista.
Describir, mediante BNF, la representación sintáctica de multilistas de números enteros.
11. Un árbol general G se define como un objeto vacío ó un nodo con un conjunto de árboles G. Describir, mediante BNF, la sintaxis de la representación lineal de árboles generales como, por ejemplo:
25 ( -43 ( 36 , -59 , 94 ) , 71 ( 87 ) )
12. Representar mediante BNF y diagramas sintácticos la declaración de:
a) Registros en lenguaje Pascal.
b) Arreglos en lenguaje C.
13. Describir, mediante BNF, la representación sintáctica del anverso de la cédula nacional de identidad. La foto y la firma constituyen meta-variables que no deben definirse.
14. Dada la expresión en notación convencional
a - b + c - ( d + e - f )
y considerando las dos posibles opciones de asociatividad:
a) Evaluarla sabiendo que a,b,c,d,e,f = 9,7,5,4,6,8.
b) Expresar su equivalente en notaciones pre y postfija.
15. Con respecto al programa
Program Asocia(Input,Output);
Var x, y, z : Integer;
Function F(Var p, q : Integer) : Integer;
Begin
p := p + 2;
q := q + 2;
F := p - q + 1;
End;
Begin
x := 6;
y := 3;
z := x - y + F(x,y) - (x - y + 1);
Write(x,y,z);
End.
indicar los valores que se imprimen y explicar porqué:
a) Sabiendo que Pascal asocia por la izquierda.
b) Basándose en la parte anterior, si se aplica asociatividad por la derecha.
16. Las expresiones a b + c " d " e / + a " b " c / d e tienen exactamente la misma estructura sintáctica en notación infija.
a) Identificar la notación en que está escrita cada una de ellas.
b) Escribir las respectivas expresiones en notación infija, con todos los paréntesis necesarios para incorporar ambas opciones de asociatividad.
17. Con respecto a la expresión a " b * c " d * e " f, con a, b, c, d, e, f ! 6, 1, 4, 3, 2, 5, escribir todas las expresiones alternativas que se generan al incorporar los paréntesis necesarios para que cada operación evidencie su carácter binario, considerando todas las opciones posibles de prioridad y asociatividad. Posteriormente, indicar el valor que se obtiene al evaluar cada una de las expresiones obtenidas.
18. Escribir, en lenguaje Pascal, un código en el cual se manifieste el concepto de alias, utilizando exclusivamente dos variables. Justificar.
19. Si, en lenguaje C, se declara int *p, n, representar gráficamente esas variables e indicar el efecto que consigue el par de asignaciones { p = &n; n = *p; }.
20. Con respecto al código
i = 5;
p = &i;
q = &p;
i = **q + 2;
a) Declarar los tipos de datos adecuados.
b) Identificar los conceptos l-valor y r-valor en cada una de las instrucciones.
21. ++C define la sentencia "equivalence", modalidad Fortran. Con respecto al código en ++C:
void enigma()
{ float x = 3.3, y = 4.4, z = 5.5;
equivalence int i, j, k;
i = x;
printf("i = %d\n",i);
j = y;
printf("i = %d j = %d\n",i,j);
k = z;
printf("i = %d j = %d k = %d\n",i,j,k);
}
a) Indicar los valores que se imprimen y explicar porqué.
b) Escribir un código en Pascal que consiga el mismo efecto.
22. Dado el siguiente código en lenguaje Ada:
k := 1;
while k <= 100 loop
j := j + k;
k := k + 1;
end loop;
a) Describir mediante BNF y diagramas la sintaxis de la sentencia while.
b) Escribir códigos equivalentes en Pascal y C, utilizando todas las opciones de repetición provistas por ambos lenguajes.
23. Se sabe que Pascal-- es una versión de Pascal que no dispone de sentencias de repetición. Implementar, de manera no recursiva en Pascal--, la función Suma con el propósito de calcular el valor de la suma de n números enteros ingresados por teclado.
24. Indicar los efectos que se logran con las siguientes sentencias en lenguaje C:
a) m = (j > k) ? j : k;
b) printf("%d + %d = %d\n",x,y,z);
c) p = n << 2; si el valor de n es 15
d) i = j = k = 7;
e) s = f + ++g + --h; si f, g y h tienen el mismo valor
f) v %= w; si el valor de v es 11 y el valor de w es 3
g) p = *q * *r * *s;
h) q = &a[3][2];
25. Con respecto al siguiente código en C:
c = getchar();
switch (c)
{ case 'A' : b = b + 1;
case 'B' : if (j = x)
z = 4;
break;
case 'C' :
case 'D' : a = b + z;
case 'E' : printf("ANSI"\n);
break;
default : m[i++] = 3;
}
a) Destacar tres elementos relevantes involucrados en la sentencia switch para su implementación en otro lenguaje.
b) Implementar el código anterior en lenguaje Pascal.
26. Explicar el efecto de la asignación i,a[i] := a[i],i.
27. Con respecto al siguiente programa en Fortran
program constante
real i, x, res
x = 3.0
res = potencia(x,4.0)
print 7, res
do 6 i = 1.0, 4.0, 1.0
res = res - 1.0
6 continue
print 7, res
stop
7 format(F10.2)
end
function potencia(x,n)
real n, p, x
p = 1.0
8 if(n.EQ.0.0) goto 9
p = p*x
n = n - 1.0
goto 8
9 continue
potencia = p
return
end
indicar los valores que se imprimen y explicar porqué, considerando que, para asociar parámetros actuales con formales, este lenguaje sólo provee llamada por referencia..
28. Con respecto a la expresión recurrente del factorial de un entero no negativo n:
a) Escribir, en C, la función recursiva "fact".
b) Identificar los elementos que conforman el registro de activación para "fact".
c) Si cada elemento del registro de activación para "fact" ocupa k bytes y la memoria disponible al momento de producirse el llamado es de m bytes, determinar el menor valor de n para el cual se debe producir una interrupción por overflow.
29. Con respecto al código:
Function X(m, n: Integer) : Integer;
Begin
If n = 0 Then
X := m
Else
X := X(n, m mod n);
End;
a) Identificar los elementos que conforman el registro de activación para X.
b) Determinar la máxima cantidad de registros de activación existentes en el stack, en un momento dado, con la llamada X(6,4).
c) Determinar la máxima cantidad (en bytes) de memoria requerida con la invocación X(12,8), si cada elemento del registro de activación ocupa 4 bytes.
d) Indicar el objetivo de la función X.
30. Con respecto al siguiente código:
type indice = 1..1000;
arreglo = array[indice] of real;
var v : arreglo;
procedure Colgado(a : ref arreglo; i, n : in integer);
var x, y : real;
begin
if i < n then
begin
x := a[i];
y := a[n];
Colgado(a,i+1,n-1);
a[n] := x;
a[i] := y;
end;
end;
b) Indicar el objetivo del procedimiento Colgado si, siempre, el 2do parámetro actual tiene el valor 1 y el 3er parámetro actual representa el número de elementos que contiene el 1er parámetro actual. Usar como ejemplo v := (6,8,9,7) y la invocación Colgado(v,1,4).
c) Si, el código ejecutable de Colgado ocupa 200 bytes y al invocar Colgado(v,1,199) existen 3256 bytes de memoria disponible, determinar la cantidad (en bytes) de memoria disponible al ejecutarse Colgado por última vez.
31. El número de Stirling de primera clase se define como
0 si k=0
S(n,k) = 1 si k=n
S(n-1,k-1) - (n-1)*S(n-1,k) si 0<k<n
donde n es un número natural.
a) Identificar los elementos que conforman el registro de activación para "stirling".
b) Si, el código ejecutable de "stirling" ocupa 100 bytes, todos los elementos del registro de activación son del mismo tamaño y, el espacio de memoria requerido para la ejecución normal de la función invocada con n=5 y k=2 es de 200 bytes, determinar el tamaño (en bytes) de cada elemento del registro de activación.
32. En cada uno de los casos, construir una tabla con todas las variables que tengan direcciones de memoria distintas, mostrar los valores que toma cada una de ellas, indicar los valores que se imprimen y citar el efecto logrado, al ejecutarse el código:
procedure Zero;
var p, q : integer;
procedure One<parámetros>;
begin {One}
p := p + q;
q := p - q;
p := p -q;
end {One};
begin {Zero}
p := 4;
q := 7;
One(q,p);
write(p,q);
end {Zero};
Si, <parámetros> tiene la forma
a) (p, q : in out integer)
b) (p, q : ref integer)
c) (p, q : name integer)
33. Con respecto a la ejecución del siguiente código:
int Tres(int k)
{ return(k); }
int Dos(int Y, int j)
{ return(j + Y); }
int Uno(int X, int i)
{ return(i + X); }
void Main()
{ display(Uno(Dos(Tres(3),2),1)); }
a) Mostrar claramente la secuencia de invocaciones mediante el stack del registros de activación e indicar el valor desplegado en Main.
b) Citar y explicar claramente el concepto que más se destaca en este código.
34. Mostrar los cambios ocurridos sobre cada variables declarada, al ejecutarse el código.
Program Exito(Input,Output);
Type Tabla = Array[1..10] Of Integer;
Var a : Tabla;
i : Integer;
Procedure Fracaso<lista de parámetros>;
Var i : Integer;
Begin
For i := 1 To 10 Do a[i] := i;
For i := 1 To 9 Do q[i+1] := p[a[i]] + 1;
End;
Begin
For i := 1 To 10 Do a[i] := 11 - i;
Fracaso(a,a,a);
End.
si, <lista de parámetros> tiene la forma:
a) (p,q,a:Tabla)
b) (Var p,q:Tabla; a:Tabla)
c) (Name p,q:Tabla; a:Tabla)
35. Con respecto a la ejecución del código
Program Pormas(Output);
Var s, t : Integer;
Procedure Por(x, y : Name Integer);
Begin
x := x*y;
y := x*y;
end;
Procedure Mas(s, t : Ref Integer);
Begin
s := s + t;
t := s + t;
Por(s,t);
end;
Begin
s := 1;
t := 2;
Mas(s,t);
Print(s,t);
end.
escrito en un lenguaje con reglas de alcance estáticas:
a) Indicar la cantidad de direcciones distintas existentes para todas las variables utilizadas.
b) Mostrar los valores que toma cada variable e indicar los valores que finalmente se imprimen.
c) Explicar las modalidades de paso de parámetros utilizadas.
36. El código
logical mas(logical in a, logical in b)
{ mas := a + b; }
permite obtener el resultado de la suma (or) de dos valores de tipo logical.
a) Agregar y/o modificar el código necesario para que la unidad "mas" permita, además, sumar valores de tipos integer, rational y real.
b) Citar el concepto utilizado en la parte anterior y, además, las formalidades de definición e implementación en modalidad Ada.
37. Dado el código
Program Cero(I,O);
Var j, k, x, z : Integer;
Procedure Uno(y : In Integer; z : Ref Integer);
Begin
z := j + k;
Writeln(k,y,z);
j := j + y;
k := k + y;
End;
Procedure Dos(x : Ref Integer);
Var k : Integer;
Begin
x := x + j;
k := 1;
Uno(x,k);
Writeln(j,k,x);
End;
Function Tres(w : In Integer) : Integer;
Var j : Integer;
Begin
j := 5;
Dos(j);
Tres := w*j;
End;
Begin
j := 2;
k := 3;
x := Tres(3*j);
z := k + j;
Writeln(j,k,x,z);
End.
definir el entorno de referencia para cada unidad de programa e indicar los valores que se imprimen, si se utilizan reglas de alcance:
a) Estáticas.
b) Dinámicas.
38. Explicar el concepto de "registros de activación léxicamente anidados".
39. Con respecto al código
void main();
int a, b, c;
int efe(int c);
begin /* efe */
efe := a + b + c;
end /* efe */;
void equis(int g, int h);
int b;
begin /* equis */
b := h - 2;
if g > 0 then
zeta(g-1,h+1)
else
begin
b := efe(h-g);
a := a + b;
display(b,g+h);
end;
end /* equis */;
void zeta(int d, int e);
int a;
begin /* zeta */
if d > 0 then
begin
a := b + d;
equis(d-1,e+1);
c := efe(e-d);
display(a,c,d+e);
end;
end /* zeta */;
begin /* main */
a := 3;
b := 4;
c := 8;
zeta(a,b);
display(a,c);
end /* main */.
representar gráficamente el entorno de referencia de cada unidad de programa, mostrar las variaciones que presenta cada una de las variables declaradas e indicar los valores desplegados, al utilizar reglas de alcance:
a) Estáticas.
b) Dinámicas.
40. La extensión de los datos puede ser de carácter estático y/o automático. Explicar como se manifiesta este concepto en los lenguajes C, Fortran y Pascal.
41. Considérese
Type Nombre = 'a'..'z';
Puntero = -1..255;
Direc = Array[Nombre] Of Puntero;
Heap = Array[0..255] Of Byte;
donde Nombre representa posibles nombres de variables y Puntero las direcciones asignadas a un área de memoria heap de elementos de tamaño fijo.
Si D es de tipo Direc, H de tipo Heap, v de tipo Nombre y p de tipo Puntero entonces D[v] = p está asociada a H[p] = k, lo cual significa que la variable v ocupa k posiciones de memoria a partir de la dirección p+1. Si D[v] = -1, entonces la variable v está en desuso.
Implementar, en Pascal, el operador Disponible(D,H) que determina la cantidad de memoria desocupada en el área heap.
42. La tabla de variables de un código en ejecución se ha definido de la siguiente forma:
Type Variable = Record
nombre : String[8];
largo : Natural;
referencia : Direccion;
End;
Tabla = Array[1..100] Of Variable;
Además, se dispone de la función Libre(H), que retorna la cantidad de bytes que el administrador del heap registra como disponible en todo momento, y de la variable global Size (exclusiva del administrador) que indica el tamaño del área heap en bytes.
Conforme a esta especificación, implementar el operador Garbage(T,n) que determina el porcentaje de memoria en calidad de garbage al interior del heap, para un programa en ejecución cuya tabla T contiene n variables.
43. Explicar, brevemente, significado y relación entre los siguientes conceptos: método, variable de ejemplar, es-un, comportamiento, tiene-un y estado.
44. Si se tiene class B y class D : public B indicar y explicar el efecto que produce la ejecución del constructor y, luego, del destructor de la variable D x.
45. Existen dos interpretaciones para una asignación de la forma <objeto1> ! <objeto2> : semántica de copia y semántica de punteros.
a) Explicar en qué consiste cada una de ellas.
b) Indicar como se presenta la asignación en C++.
46. Es posible percibir la herencia como expansión o bien como reducción. Explicar en qué consiste este contrasentido.
47. Considérense las siguientes definiciones:
class Base
{ int j;
public :
virtual void prueba()
}
void Base::prueba()
{ cout << “Clase Base”; }
class Derivada : public Base
{ int k;
public :
virtual void prueba()
}
void Derivada::prueba()
{ cout << “Clase Derivada”; }
Si se declara
Base b1, b2 *b3;
Derivada *c1, *c2;
a) Respecto de la distribución en memoria (stack y heap), explicar el efecto producido por las sentencias:
b3 = new Derivada;
c1 = new Derivada;
b1 = *b3;
b2 = *c1;
c2 = c1;
b) Indicar la salida desplegada y explicar porqué, al ejecutarse cada una de las sentencias:
b1.prueba;
b2.prueba;
c2.prueba;
resume X
resume X
resume Y
resume Y
9 1 4 8 0 ··· 6
66
Descargar
| Enviado por: | Smack Down |
| Idioma: | castellano |
| País: | Chile |
Todos los derechos reservados.