Lenguajes de programación

Informática. Programación. Abstracción de datos. Metalenguajes. Procesadores. Compiladores. Intérprete. Control de datos. Soporte head. C++

  • Enviado por: Víctor Sepúlveda
  • Idioma: castellano
  • País: España España
  • 47 páginas
publicidad
cursos destacados
Cómo Programar para Emprendedores - HTML y CSS
Cómo Programar para Emprendedores - HTML y CSS
Ahorra dinero y dolores de cabeza aprendiendo lo básico de programación con nuestros cursos para...
Ver más información

Aprende jQuery sin sufrimiento
Aprende jQuery sin sufrimiento
En este curso aprenderás a utilizar jQuery desde su instalación hasta que puedas hacer una galería...
Ver más información

publicidad

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

Dotar al lenguaje de la máxima generalidad posible de modo que no existan restricciones o 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>

<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

En 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[1..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 */

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

var n : 1..100;

···

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) 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);

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.

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:

Parametrización de tipos

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);

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.

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. CONTROL DE DATOS

6.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.

6.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:

6.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

6.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.

6.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. ORIENTACIÓN A OBJETOS

8.1. Generalidades

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

" Orientado a objetos " Procedimental

" 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 la información (argumentos) necesaria 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 un método para satisfacer 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.

Herencia

" Las clases pueden organizase 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

8.2. 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

class Base

{ private :

int k;

float x;

public :

proc(int j);

int func();

}

Base b, *c;

8.3. 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 b.proc(n) o (*c).func().

" 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

class Complejo

{ public :

float real;

float imag;

Complejo();

Complejo(float pr);

Complejo(float pr, float pi);

"Complejo();

}

Complejo::Complejo()

{ real = imag = 0; }

Complejo::Complejo(float pr)

{ real = pr; imag = 0; }

Complejo::Complejo(float pr, float pi)

{ real = pr; imag = pi; }

Complejo::"Complejo()

{ printf(“liberando complejo %f %f \n”, real, imag; }

Complejo x, y(4.0), *z;

z = new Complejo(3.14159,2.4);

Control de flujo

class Lengua

{ char *token;

public :

Lengua(char *t);

"Lengua();

}

Lengua::Lengua(char *t)

{ token = t; printf(“Lenguaje %s \n”, token); }

Lengua::"Lengua()

{ printf(“orientado a objetos es %s \n”, token); }

void comprueba()

{ Lengua bb(“Object Pascal”);

···

printf(“es compilado. \n”);

{ Lengua cc(“Pascal”);

···

printf(“también lo es. Pero no \n”);

}

···

printf(“En cambio sí \n”);

}

La clase lista

class Lista

{ int dato;

Lista *nexo;

public :

Lista(Lista *prox, int e)

{ dato = e; nexo = prox; }

Lista *siguiente()

{ return nexo; }

int valor()

{ return dato; }

}

void prueba()

{ int j = 5;

Lista *p = new Lista(0,j);

for(j = 4; j > 0; j--)

{ p = new Lista(p,j); }

}

8.4. Herencia Simple

El concepto

" 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.

" La ejecución de métodos heredados es más lenta que la ejecución de 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).

" En cambio, 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

class Lista

{ Lista *prox;

public :

Lista()

{ prox = 0; }

void agregar(Lista *q)

{ if (prox) prox">agregar(q); else prox = q; }

void enTodos(void f(Lista *))

{ f(this); if (prox) prox">enTodos(f); }

}

class IntLista : public Lista

{ int dato;

public :

IntLista(int k) : Lista()

{ dato = k; }

void imprimir()

{ cout << dato; }

}

void mostrar(IntLista *q)

{ q">imprimir(); }

void prueba()

{ int j = 5;

IntLista *p = new IntLista(j);

for(j = 4; j > 0; j--)

{ p">agregar(new IntLista(j)); }

p">enTodos(mostrar);

}

Enfoques para estructurar clases

" Árbol: todas las clases deben estar contenidas en una sola gran estructura de herencia; como ventaja, la funcionalidad proporcionada en la raíz es heredada por todos los objetos.

" Bosque: las clases que no están lógicamente relacionadas deben ser por completo distintas; como ventaja, la aplicación no está obligada a cargar con una gran biblioteca de clases, de las cuales podrían usarse sólo unas pocas.

" Ambos enfoques parecen depender de la distinción entre lenguajes que usan asignación dinámica de tipos y aquellos que usan asignación estática de tipos.

8.5. 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.6. 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 oops();

}

class VentanaDeTexto : public Ventana

{ char *indice;

int posCursor;

public :

virtual void oops();

}

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::oops()

{ printf(“Ventana-Base”); }

void VentanaDeTexto::oops()

{ printf(“VentanaDeTexto-Derivada %d”, 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.oops() se ejecutará el método de la clase Ventana.

" Si se selecciona (*z).oops()se ejecutará el método de la clase VentanaDeTexto.

Asignación en memoria

Posibles interpretaciones de la asignación

x = y;

"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

Posibles interpretaciones de la igualdad

x == y;

" 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.7. 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

class Lista

{ public :

Nodo *otro;

Lista()

{ otro = (Nodo *) 0; }

void agregar(Nodo *q)

{ if (otro) otro">agregar(q); else otro = q; }

void enTodos(void f(Nodo *))

{ f(this); if (otro) otro">enTodos(f); }

}

class Nodo

{ public :

Nodo *prox;

Nodo()

{ prox = (Nodo *) 0; }

void poner(Nodo *q)

{ prox = q; }

void agregar(Nodo *q)

{ if (prox) prox">agregar(q); else poner(q); }

void enTodos(void f(Nodo *))

{ if(this); if (prox) prox">enTodos(f); }

}

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 (otro) otro">enTodos(f);

if(this);

if (prox) prox">enTodos(f); }

}

Posteriormente, se le puede dar el siguiente uso:

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.8. 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)

{ printf(“Por valor se imprime %d\n”,x.valor(); }

void f2(P *x)

{ printf(“Por indirección se imprime %d\n”,x">valor(); }

void f3(P &x)

{ printf(“Por referencia se imprime %d\n”,x.valor(); }

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 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; }

void virtual dibujar() = 0;

}

class Circulo : public Forma

{ public :

int radio;

void ponerRadio(int i)

{ radio = i; }

void virtual dibujar() = 0;

{ 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é, teniendo en consideración 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 a cada una de las variables declaradas, 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;

9 1 4 8 0 ··· 6

resume X

resume X

resume Y

resume Y