martes, 4 de diciembre de 2007
Definición y activación de los procedimientos
Un procedimiento es un mecanismo en un lenguaje de programación para abstraer un grupo de acciones o de computaciones. El grupo de accidentes se conoce como cuerpo del procedimiento, que está representado en su totalidad por el nombre del procedimiento. Se define procedimiento al proveer una especificación o interfaz y un cuerpo. La especificación le da nombre al procedimiento, una lista de los tipos y nombres de sus parámetros, así como el tipo de su valor devuelto, si es que existe alguno:
El procedimiento intswap intercambia los valores de sus parámetros x y y utilizando la variable local t.
En algunos lenguajes y en algunas situaciones, pueden separarse una especificación de procedimiento de su cuerpo, en el caso de que la especificación deba estar disponible por adelantado:
Note que esta especificación no require que estén especificados los nombres de los parámetros.
En C++ esta clase de especificacación se conoce (de manera confusa) como una declaración, mientras que la definición completa (incluye el cuerpo) se llama definición (en C, las declaraciones se llaman prototipos). Típicamente, incluso cuando una especificación antecedente a una definición debe repetirse con el cuerpo.
Se llama o activa un procedimiento al enunciar su nombre, junto con los argumentos de la llamada, que corresponden a sus parámetros:
Una llamada o un procedimiento transfiere el control al principio del procedimiento llamado (el llamado). Cuando la ejecución llega al final del cuerpo; el control es devuelto al llamador. En algunos lenguajes, puede devolverse el control al llamador antes de llegar al final del cuerpo del llamado, utilizando un enunciado return:
En algunos lenguajes como FORTRAN, para llamar un procedimiento debe también incluirse lq palabra clave CALL, como en
(en FORTRAN, a los procedimientos se les llama subrutinas)
Un lenguaje de programación pudiera hacer la distinción entre procedimientos, mismos que llevan a cabo sus operaciones cambiando sus parámetros o variables no locales, y las funciones que aparecen en expresión y que computan valores devueltos.
Las funciones pueden o no cambiar sus parámetros y variables no locales. En C y C++, todos los procedimientos implícitamente son funciones; aquellas que no devuelvan valores se declaran como void, en tanto que las funciones normales se declaran como que tienen el tipo (devuelto) del valor que devuelven:
En algunos lenguajes, por ejemplo en Ada y FORTRAN, se utilizan diferentes palabras clave para los procedimientos y para las funciones:
En algunos lenguajes sólo existen funciones (esto es, todos los procedimientos deben devolver los valores). Los lenguajes funcionales en particular tiene esta propiedad.
En algunos lenguajes, las declaraciones de procedimientos y de funciones se escriben de una forma similar a las declaraciones de constantes, usando el signo de igual, como en la siguiente declaración de función ML para un procedimiento swap:
El uso de un signo igual para declarar procedimientos está justificado, dado que una declaración de procedimientos le da el nombre del procedimiento un significado que se conserva constante durante la ejecución del programa. Una declaración de procedimiento crea un valor de procedimiento constante y asocia un nombre simbólico –el nombre del procedimiento- a dicho valor.
Un procedimiento se comunica con el resto del programa a través de sus parámetros y también a través de sus referencias no locales, esto es referencias a variables declaradas fuera de su propio cuerpo. Las reglas de alcance que establecen los significados de las referencias no locales.
El procedimiento intswap intercambia los valores de sus parámetros x y y utilizando la variable local t.
En algunos lenguajes y en algunas situaciones, pueden separarse una especificación de procedimiento de su cuerpo, en el caso de que la especificación deba estar disponible por adelantado:
Note que esta especificación no require que estén especificados los nombres de los parámetros.
En C++ esta clase de especificacación se conoce (de manera confusa) como una declaración, mientras que la definición completa (incluye el cuerpo) se llama definición (en C, las declaraciones se llaman prototipos). Típicamente, incluso cuando una especificación antecedente a una definición debe repetirse con el cuerpo.
Se llama o activa un procedimiento al enunciar su nombre, junto con los argumentos de la llamada, que corresponden a sus parámetros:
En algunos lenguajes como FORTRAN, para llamar un procedimiento debe también incluirse lq palabra clave CALL, como en
(en FORTRAN, a los procedimientos se les llama subrutinas)
Un lenguaje de programación pudiera hacer la distinción entre procedimientos, mismos que llevan a cabo sus operaciones cambiando sus parámetros o variables no locales, y las funciones que aparecen en expresión y que computan valores devueltos.
Las funciones pueden o no cambiar sus parámetros y variables no locales. En C y C++, todos los procedimientos implícitamente son funciones; aquellas que no devuelvan valores se declaran como void, en tanto que las funciones normales se declaran como que tienen el tipo (devuelto) del valor que devuelven:
En algunos lenguajes, por ejemplo en Ada y FORTRAN, se utilizan diferentes palabras clave para los procedimientos y para las funciones:
En algunos lenguajes sólo existen funciones (esto es, todos los procedimientos deben devolver los valores). Los lenguajes funcionales en particular tiene esta propiedad.
En algunos lenguajes, las declaraciones de procedimientos y de funciones se escriben de una forma similar a las declaraciones de constantes, usando el signo de igual, como en la siguiente declaración de función ML para un procedimiento swap:
El uso de un signo igual para declarar procedimientos está justificado, dado que una declaración de procedimientos le da el nombre del procedimiento un significado que se conserva constante durante la ejecución del programa. Una declaración de procedimiento crea un valor de procedimiento constante y asocia un nombre simbólico –el nombre del procedimiento- a dicho valor.
Un procedimiento se comunica con el resto del programa a través de sus parámetros y también a través de sus referencias no locales, esto es referencias a variables declaradas fuera de su propio cuerpo. Las reglas de alcance que establecen los significados de las referencias no locales.
jueves, 29 de noviembre de 2007
lunes, 19 de noviembre de 2007
Nuestra primera version de apuntes, lo mejoraremos proximamente.
Manejo de excepciones y de ambientes
En principio, las operaciones de poner de manifiesto y de manejar las excepciones son similares a las llamadas de procedimientos, y pueden implementarse de forma similar. Sin embargo, también existen importantes diferencias. Las principales son:
1.No puede crearse una activación en la pila de tiempo de ejecución para representar que se pone de manifiesto una excepción.
2.Debe localizarse un manejador y “llamar” dinámicamente, en vez de estáticamente como ocurre en las llamadas normales de función.
3.Las acciones de un manejador se basan en el tipo de la excepción, más que el valor de la excepción, a la inversa de la práctica estándar para lenguajes de tipificado estático.
La primera diferencia es fácil de superar: cuando se pone de manifiesto una excepción, no se crea un registro de activación, pero el objeto de la excepción (y su información de tipo) se colocan en una ubicación conocida (un registro o una memoria estática), y se hace un salto al código genérico que lleva a cabo el proceso de buscar un manejador (o de llamar un código de salida si no se encuentra uno). Las direcciones de retorno (para el manejo de éxito de una excepción) también debe ser almacenada en una ubicación conocida, y esta dirección es (bajo el modelo de terminación) la ubicación que sigue en el bloque en el que ocurrió la excepción (o la dirección de remitente de la llamada más reciente si el bloque es un procedimiento).
La segunda diferencia es más problemática. Por lo menos en teoría, los apuntadores hacia los manejadores deben ser conservados en algún tipo de pila. Cada vez que se introduce un código que tiene un manejador asociado, se mete un nuevo apuntador de manejador, y cuando este mismo código sale, el apuntador es sacado de nuevo para poner de manifiesto cualquier manejador anterior. Esta pila debe ser implementada directamente, debe ser mantenida, ya sea en el heap (montón), o en algún otra parte en su área de memoria (es decir a excepción de la pila de tiempo de ejecución), y debe mantenerse un apuntador en la parte superior de la pila actual, ya sea en memoria estática o en un registro.
La tercera el principal problema consiste en cómo registrar la información de tipo necesario (en esencial los nombres de tipo) sin carga general adicional en las estructuras de excepción misma. Una posibilidad es elaborar algún tipo de tabla de búsqueda.
Una vez resuelto los problemas anteriores, la implementación de los manejadores es relativamente simple. La idea básica es recolectar todo el código de manejador agregado a un bloque en particular, formando un solo manejador implementado como un solo enunciado switch que esté basado en el tipo del parámetro de excepción recibido, por un caso por omisión que saca la pila del manejador (ajustando la dirección del remitente actual) y, si es necesario, sacando la pila en tipo de ejecución antes de volver a poner de manifiesto la misma excepción (los bloques de procedimientos deberán tener por lo menos ese ultimo manejador por omisión, incluso si no se maneja de manera explicita las excepciones). Por ejemplo:
Void factor () throw (Unwind, Inputerror)
{ try
Catch (UnexpectedChar u)
{…}
catch (Unwind u)
{…}
catch (Number Expected)
{…}
}
Pop the runtime stack and return to caller;
El principal problema en las técnicas de implementación hasta ahora descrita es que el mantenimiento de la pila del manejador genera una penalización potencial significativa en tiempo de ejecución, incluso para el código que no utilice manejo de excepciones. Será deseable tener una alternativa a la pila del manejador que fuera generada estáticamente y, por lo tanto, no tendría costo alguno para el código que no utiliza el manejo de excepciones. Dicha alternativa es una tabla ordenada de direcciones de código que registra los manejadores disponibles. Cuando ocurre una excepción, el código donde ocurre la excepción (una búsqueda binaria de la tabla de direcciones, por ejemplo). Si no se encuentra ningún manejador, el bloque donde ocurrió la excepción sale y se utiliza la dirección de salida para una nueva búsqueda.
Naturalmente este tipo de tabla de direcciones tiene sus propios problemas. En primer término, la tabla misma puede ser muy grande, haciendo que crezca de manera significativa el uso de la memoria por parte del programa. En segundo término, cuando ocurre una excepción, puede presentarse alguna penalización aún mayor en la velocidad de ejecución debido a múltiples búsquedas de la tabla de direcciones.
PROCEDIMIENTOS Y ENTORNOS
Un procedimiento es un mecanismo en un lenguaje de programación para abstraer un grupo de acciones o de computaciones. El grupo de accidentes se conoce como cuerpo del procedimiento, que está representado en su totalidad por el nombre del procedimiento. Se define procedimiento al proveer una especificación o interfaz y un cuerpo. La especificación le da nombre al procedimiento, una lista de los tipos y nombres de sus parámetros, así como el tipo de su valor devuelto, si es que existe alguno:
//código c++
Void intswap (int& x,int&y)// especificación
{int t= x; // cuerpo
x=y; // cuerpo
y=t;// cuerpo
}
El procedimiento intswap intercambia los valores de sus parámetros x y y utilizando la variable local t.
En algunos lenguajes y en algunas situaciones, pueden separarse una especificación de procedimiento de su cuerpo, en el caso de que la especificación deba estar disponible por adelantado:
Void intswap (int&, int&);// sólo especificación
Note que esta especificación no require que estén especificados los nombres de los parámetros.
En C++ esta clase de especificacación se conoce (de manera confuse) como una declaración, mientras que la definición complete (incluye el cuerpo) se llama definición (en C, las declaraciones se llaman prototipos). Típicamente, incluso cuando una especificación antecedente a una definición debe repetirse con el cuerpo.
Se llama o activa un procedimiento al enunciar su nombre, junto con los argumentos de la llamada, que corresponden a sus parámetros:
Intswap (a,b);
Una llamada o un procedimiento transfiere el control al principio del procedimiento llamado (el llamado). Cuando la ejecución llega al final del cuerpo; el control es devuelto al llamador. En algunos lenguajes, puede devolverse el control al llamador antes de llegar al final del cuerpo del llamado, utilizando un enunciado return:
//código C++
Void intswap (int& x, int&y)
{ if (x == y) return;
int t = x;
x = y;
y = t;
}
En algunos lenguajes como FORTRAN, para llamar un procedimiento debe también incluirse lq palabra clave CALL, como en
CALL INTSWAP (A , B)
(en el FORTRAN, a los procedimientos se les llama subrutinas)
Un lenguaje de programación pudiera hacer la distinción entre procedimientos, mismos que llevan a cabo sus operaciones cambiando sus parámetros o variables no locales, y las funciones que aparecen en expresión y que computan valores devueltos.
Las funciones pueden o no cambiar sus parámetros y variables no locales. En C y C++, todos los procedimientos implícitamente son funciones; aquellas que no devuelvan valores se declaran como void, en tanto que las funciones normales se declaran como que tienen el tipo (devuelto) del valor que devuelven:
int max (int x, int y)
{ return x > y ? x : y;
}
En algunos lenguajes, por ejemplo en Ada y FORTRAN, se utilizan diferentes palabras clave para los procedimientos y para las funciones:
-- Procedimiento en Ada
procedure swap ( x, y: int out integer) is
t: integer;
begin
if ( x = y) then return;
end if;
t :=x;
x :=y;
y :=t;
end swap;
--Función en Ada
fuction max ( x,y: integer ) return integer is
begin
if ( x > y ) then return x;
else return y;
end if;
end max;
En algunos lenguajes sólo existen funciones (esto es, todos los procedimientos deben devolver los valores). Los lenguajes funcionales en particular tiene esta propiedad.
En algunos lenguajes, las declaraciones de procedimientos y de funciones se escriben de una forma similar a las declaraciones de constantes, usando el signo de igual, como en la siguiente declaración de función ML para un procedimiento swap:
(* código ML *)
fun swap ( x, y)=
let val t=!x
in
x :=!y;
y:= t
end;
El uso de un signo igual para declarar procedimientos está justificado, dado que una declaración de procedimientos le da el nombre del procedimiento un significado que se conserva constante durante la ejecución del programa. Una declaración de procedimiento crea un valor de procedimiento constante y asocia un nombre simbólico –el nombre del procedimiento- a dicho valor.
Un procedimiento se comunica con el resto del programa a través de sus parámetros y también a través de sus referencias no locales, esto es referencias a variables declaradas fuera de su propio cuerpo. Las reglas de alcance que establecen los significados de las referencias no locales.
Administración de la memoria dinámica
En un lenguaje imperativo típico como C, la asignación y desasimilación automática del almacenamiento ocurre únicamente para los registros de activación de una pila. También esta disponible bajo control manual la asignación dinámica explicita, así como el uso de apuntadores mediante un “montón” de memoria independiente de la pila.
Los lenguajes con necesidades significativas del almacenamiento en el montón, como Java, están mejor dejando el almacenamiento dinámico fuera de la pila aun administrador de la memoria que incluya recolección automática e la basura.
Cualquier lenguaje que no aplique restricciones significativas al uso de procedimientos deberá incluir la recolección automática de basura, ya que el sistema basado en pilas de llamados y retornos de procedimientos ha dejado de ser correcto.
Se podría intentar resolver este problema utilizando un procedimiento muy sencillo, simplemente no desasignando ninguna memoria una vez que esta ha sido asignada. Esto quiere decir que toda llamada a una función genera en la memoria un nuevo registro de activación, pero a la salida esta memoria no es desasignada.
La administración automática de la memoria se ubica en dos categorías: la recuperación de almacenamiento previamente asignado pero ya no utilizado, aveces conocido como recolección de basura y el mantenimiento para el espacio libre para la asignacion
Mantenimiento de espacio libre
Por lo general el sistema operativo pone un bloque contiguo de memoria para uso de un programa en ejecución. El espacio libre en el interior del bloque es conservado por una lista de bloques libres. Una forma de hacer lo anterior es por medio de una lista vinculada.
Cuando es necesario asignar un bloque de un determinado tamaño, el administrador de la memoria busca un bloque libre que tenga suficiente espacio y después ajusta la lista de espacio libre para eliminar el espacio que se acaba de asignar. Cuando se recupera a memoria, los bloques son devueltos a la lista de espacio libre, después deberán unirse a bloques adyacentes, para formar el bloque contiguo mas grande de memoria libre, El proceso se llama fusión o unión, sin enbargo al unirse una lista puede quedar fragmentada. Para evitar lo anterior, la memoria debe, de vez en cuando, compactarse moviendo todos lo bloques libres para unirlos y crear un solo bloque.
La compactacion involucra gran cantidad de carga general, ya que las ubicaciones de las cantidades asignadas se modificaran y sera necesario cambiar las estructuras de datos y las tablas en el ambiente en tiempo de ejecución para que reflejen las nuevas localizaciones.
Recuperación de almacenamiento
Reconer cunado un bloque de almacenamiento ya no es referenciado, ya se directa o indirectamente mediante apuntadores, es una tarea mucho mas difícil que el mantenimiento mismo de la lista libre. Históricamente se han utilizado dos métodos principales: conteo de referencia y marcar y barrer.
El concepto de refencias es método de recuperación del almacenamiento, ya que procura recuperar espacio tan pronto este deje de estar refernciado. Cada bloque de almacenamiento asignado contiene un campo de conteo adicional que guarda el numero de referencia en relación con otros bloques. Cada que se cambia de referencia este conteo de referencias debe ser actualizado. Cuando el conteo de referencia llega a cero, el bloque puedes ser devuelto a la lista libre. Los inconvenientes de este método es la memoria adicional que necesita para manter actualizados los conteos de referencia mismos, mas serio es el esfuerzo de mantener el conteo, que puede ser muy grande.
El metedo alterno estándar a los conteos de referencia es marcar y barrer. Este método es el que se conoce como perezoso, ya que pospone la recuperación de cualquier almacenamiento hasta que el asignador se quede sin espacio, y en ese momento busca todo el almacenamiento que pueda ser referanciado de regreso a la lista libre. Esto lo hace en dos pasadas. En la primer pasada se siguen todos lo punteros de manera recursiva, iniciándose con el ambiente o la tabla de símbolos actuales, y maraca cada bloque de almacenamiento localizado. Este proceso requiere un bit adicional de almacenamiento para el marcado. En una segunda pasada se barre de manera lineal atavez de la memoria devolviendo los bloques no marcados a la lista libre.
Es posible efectuar una mejoría contabilizadora dividiendo la memoria disponible en dos partes iguales y asignado el almacenamiento solo a una de las partes a la vez. Entonces durante la pasada de marcado todos los bloques se copian de inmediato a la segunda mitad del almacenamiento no en uso; pro lo tanto, a menudo este método se le conoce como parar y copiar.
Conocido como recoleccion generacional de basura, añade un área de almacenamiento permanente al esquema de recuperación. Los objetos asignados que sobrevivan lo suficiente simplemente son copiados al espacio permanente y no son reasignados durante recuperaciones de almacenamiento subsecuentes.
8.4 AMBIENTES, ACTIVACION Y ASIGNACIÓN DE PROCEDIMIENTOS
Para poder mantener el ambiente invocador, es necesario algún concepto de cerradura para resolver referencias no locales. A menudo, es necesario un claro discernimiento de este modelo de ejecución para comprender en su totalidad el comportamiento de los programas, ya que las semánticas de las llamadas de procedimientos esta grabada en dicho modelo.
Un ambiente basado totalmente en pilas ya no resulta adecuado para encarar las variables de procedimientos ni la creación dinámica de estos, y que aquellos lenguajes que tengan estos servicios, en particular los lenguajes funcionales, están obligados a usar un ambiente totalmente dinámico mas complejo con recolección de basura.
8.4.1AMBIENTES TOTALMENTE ESTATICOS
Como ejemplo FORTRAN 77en el cual la asignación de memoria puede llevarse a cabo en tiempo de carga y las localizaciones de todas las variables quedan fijas. Las definiciones e funciones y de procedimientos (o subrutinas) no pueden ser anidadas como en C, y no se permite la recursión a diferencia con C. Toda la información asociada con una función o con una subrutina puede asignarse estáticamente. Cada procedimiento o función tiene un registro de asignación fijo, que ha previsto espacio para las variables y parámetros locales. Las variables globales se definen mediante declaraciones COMMON y se determinan utilizando apuntadores hacia un área común.
Cada registro de la activación se subdivide en varias áreas:
Cuando ocurre una llamada a un procedimiento S, se evalúan los parámetros y sus ubicaciones se almacenan en el espacio para los parámetros del registro de activación de S. El ambiente de instrucciones presentes se almacena como dirección remitente, y se efectúa un salto al apuntador de instrucciones de S. Cuando S sale se efectua un salto a la dirección de retorno.
Como un ejemplo:
Considere el siguiente programa en FORTRAN:
REAL TABLE (10), MAXVAL
READ *,TABLE (1), TABLE ( 2), TABLE (3)
CALL LRGST (TABLE, 3, MAXVAL)
PRINT *, MAXVAL
END
SUBROUTINE LRGST (A, SIZE, V)
INTEGER SIZE
REAL A (SIZE), V
INTEGER K
V = A (1)
DO 10 K = 1, SIZE
IF (A(K) GT. V) V= A (K)
10CONTINUE
RETURN
END
El ambiente de este programa se vería de la siguiente forma:
Forma de la pila de activación durante la ejecución de p:
Para encontrar la referencia no local a la x de q desde el interior de p se puede seguir el enlace de control hasta el registro de activación r pero se encontraría la x local de r. con esto se lograría un alcance dinámico en vez de un alcance léxico. Para lograr el alcance léxico, un procedimiento es que p mantenga un alcance a su ambiente léxico o de definición. A este enlace se le conoce como enlace de acceso, ya que proporciona al acceso a las variables no locales (algunas veces al enlace de acceso se le llama enlace estático). En vista de que p está definido en el interior de q, el enlace de acceso p es el ep existente cuando es definido p, por lo que el enlace de acceso de p apunta a la activación de q. Ahora cada registro de activación necesita de un nuevo campo, el campo del enlace de acceso, y la imagen completa del ambiente para este ejemplo es:
Cuando los bloques están anidados profundamente, para encontrar una referencia no local puede ser necesario seguir varios enlaces de acceso en vez de uno solo.
Por ejemplo, en Ada, para tener acceso a x desde el interior de q, se necesita seguir el enlace de acceso en el registro de activación de p, y acto seguido, siguiendo el enlace de acceso de p hasta el ambiente global. Este proceso se llama encadenamiento de accesos, y la cantidad de enlaces de acceso que deberían seguirse corresponde a la diferencia en niveles de anidamiento, o profundidad de anidamiento, entre el ambiente de acceso y el ambiente definidor de la variable que se está accesando.
Con este orden en el ambiente, la cerradura de un procedimiento se hace significativamente más complejo, ya que cada vez que un procedimiento es llamado, debe incluirse como parte del registro de activación el ambiente definidor de dicho procedimiento. Entonces, una función o un procedimiento en un lenguaje como Ada o Pascal debe representarse no sólo por un apuntador al código para el procedimiento, también por una cerradura que consiste en un par de apuntadores: el apuntador del código o de la instrucción, que se identifica como ip, y el apuntador de enlace de acceso o de ambiente de su ambiente definidor, mismo que identificaremos como ep; esta clausura la escribimos como y la utilizaremos en el análisis que sigue como la representación de los procedimientos.
Por último, este es un ejemplo de un programa en Ada con procedimientos anidados y un diagrama de su ambiente en algún momento de su ejecución. El procedimiento anidado show tiene dos cerraduras diferentes; cada una de ellas corresponde a las dos distintas activaciones de p en las cuales show está definido.
Procedimientos calculados dinámicamente y ambientes totalmente dinámicos.
El ambiente de tiempo de ejecución basado en pilas es adecuado para casi todos los lenguajes estructurados en bloques con alcance léxico. El uso de cerraduras para los procedimientos por sí mismos, siempre y cuando dichos parámetros sean de valor. Un procedimiento que se pasa a otro procedimiento es transferido como una clausura (un par ), y cuando es llamado, su enlace de acceso es la parte ep de su clausura. Ada y Pascal son ejemplos de lenguajes para los cuales esta organización se hace necesaria.
Sin embargo, un ambiente basado en pilas tiene sus limitaciones. Por ejemplo, cualquier procedimiento que pueda devolver un apuntador a un objeto local, ya sea mediante un valor devuelto o a través de un parámetro de paso por referencia, dará como resultado una referencia pendiente al salir del procedimiento, ya que el registro de activación del procedimiento habrá sido desasignado de la pila. El ejemplo más sencillo de lo anterior es cuando se vuelve la dirección de una variable local:
Int * dangle(void)
{ int x;
Return &x;
}
Una asiganción addr = dangle() ahora hace que addr apunte a una ubicación no segura en la pila de activación.
Sin embargo, esta situación no puede suceder en Java, dado que no está disponible la dirección de una variable local. También Ada95 convierte esto en un error al declarar la regla de la vida de tipo acceso: un atributo x’access dando un resultado que corresponde a un acceso dando un resultado que corresponde a un acceso del tipo T (por ejemplo, un tipo apuntador) sólo es permitido si x puede mantenerse en existencia por lo menos el mismo tiempo que T. Por lo anterior, el código Ada equivalente al código C arriba mostrado es:
Type IntPtr is Access Integer;
Function dangle return IntPtr is
x: Integer;
begin
return x’access;
end dangle;
es incorrecto, puesto que la definición del tipo IntPtr acurre en un alcance exterior con relación a x (como debe ser para permitir la definición de dangle) violando la regla de vida de tipo acceso.
Sin embargo, existen situaciones en las que un compilador no puede detectar este error de manera estática. En Ada aún así acurriría una excepción durante la ejecución (Program_Error), pero en C/C++ y en algunos otros lenguajes, este error no será detectado ni estática ni dinámicamente. En la práctica, a los programadores que tienen clara la idea del ambiente les resulta fácil evitar este error.
Ocurre una situación más severa si el diseñador del lenguaje desea extender la expresividad y la flexibilidad del lenguaje el permitir que los procedimientos puedan ser creados dinámicamente, es decir, permitiendo la devolución de procedimientos a partir de otros procedimientos vía un valor devuelto o parámetros de referencia. Este tipo de flexibilidad por lo general es deseable en un lenguaje funcional y en un lenguaje de este tipo, los procedimientos se convierten en lo que se conoce como valores de primera clase. No se aplica ninguna restricción “arbitraria” para su uso. En un lenguaje de este tipo, no puede utilizarse un ambiente basado en pilas, en vista de que la cerradura de un procedimiento definido localmente tendrá un ep que apunta al registro de activación presente. Si dicha clausura está disponible fuera de la activación del procedimiento que la creó, el ep apuntará a un registro de activación que ya no existe. Cualquier llamada subsecuente a dicho procedimiento tendrá un ambiente de acceso incorrecto.
Manejo de excepciones y de ambientes
En principio, las operaciones de poner de manifiesto y de manejar las excepciones son similares a las llamadas de procedimientos, y pueden implementarse de forma similar. Sin embargo, también existen importantes diferencias. Las principales son:
1.No puede crearse una activación en la pila de tiempo de ejecución para representar que se pone de manifiesto una excepción.
2.Debe localizarse un manejador y “llamar” dinámicamente, en vez de estáticamente como ocurre en las llamadas normales de función.
3.Las acciones de un manejador se basan en el tipo de la excepción, más que el valor de la excepción, a la inversa de la práctica estándar para lenguajes de tipificado estático.
La primera diferencia es fácil de superar: cuando se pone de manifiesto una excepción, no se crea un registro de activación, pero el objeto de la excepción (y su información de tipo) se colocan en una ubicación conocida (un registro o una memoria estática), y se hace un salto al código genérico que lleva a cabo el proceso de buscar un manejador (o de llamar un código de salida si no se encuentra uno). Las direcciones de retorno (para el manejo de éxito de una excepción) también debe ser almacenada en una ubicación conocida, y esta dirección es (bajo el modelo de terminación) la ubicación que sigue en el bloque en el que ocurrió la excepción (o la dirección de remitente de la llamada más reciente si el bloque es un procedimiento).
La segunda diferencia es más problemática. Por lo menos en teoría, los apuntadores hacia los manejadores deben ser conservados en algún tipo de pila. Cada vez que se introduce un código que tiene un manejador asociado, se mete un nuevo apuntador de manejador, y cuando este mismo código sale, el apuntador es sacado de nuevo para poner de manifiesto cualquier manejador anterior. Esta pila debe ser implementada directamente, debe ser mantenida, ya sea en el heap (montón), o en algún otra parte en su área de memoria (es decir a excepción de la pila de tiempo de ejecución), y debe mantenerse un apuntador en la parte superior de la pila actual, ya sea en memoria estática o en un registro.
La tercera el principal problema consiste en cómo registrar la información de tipo necesario (en esencial los nombres de tipo) sin carga general adicional en las estructuras de excepción misma. Una posibilidad es elaborar algún tipo de tabla de búsqueda.
Una vez resuelto los problemas anteriores, la implementación de los manejadores es relativamente simple. La idea básica es recolectar todo el código de manejador agregado a un bloque en particular, formando un solo manejador implementado como un solo enunciado switch que esté basado en el tipo del parámetro de excepción recibido, por un caso por omisión que saca la pila del manejador (ajustando la dirección del remitente actual) y, si es necesario, sacando la pila en tipo de ejecución antes de volver a poner de manifiesto la misma excepción (los bloques de procedimientos deberán tener por lo menos ese ultimo manejador por omisión, incluso si no se maneja de manera explicita las excepciones). Por ejemplo:
Void factor () throw (Unwind, Inputerror)
{ try
Catch (UnexpectedChar u)
{…}
catch (Unwind u)
{…}
catch (Number Expected)
{…}
}
Pop the runtime stack and return to caller;
El principal problema en las técnicas de implementación hasta ahora descrita es que el mantenimiento de la pila del manejador genera una penalización potencial significativa en tiempo de ejecución, incluso para el código que no utilice manejo de excepciones. Será deseable tener una alternativa a la pila del manejador que fuera generada estáticamente y, por lo tanto, no tendría costo alguno para el código que no utiliza el manejo de excepciones. Dicha alternativa es una tabla ordenada de direcciones de código que registra los manejadores disponibles. Cuando ocurre una excepción, el código donde ocurre la excepción (una búsqueda binaria de la tabla de direcciones, por ejemplo). Si no se encuentra ningún manejador, el bloque donde ocurrió la excepción sale y se utiliza la dirección de salida para una nueva búsqueda.
Naturalmente este tipo de tabla de direcciones tiene sus propios problemas. En primer término, la tabla misma puede ser muy grande, haciendo que crezca de manera significativa el uso de la memoria por parte del programa. En segundo término, cuando ocurre una excepción, puede presentarse alguna penalización aún mayor en la velocidad de ejecución debido a múltiples búsquedas de la tabla de direcciones.
PROCEDIMIENTOS Y ENTORNOS
Un procedimiento es un mecanismo en un lenguaje de programación para abstraer un grupo de acciones o de computaciones. El grupo de accidentes se conoce como cuerpo del procedimiento, que está representado en su totalidad por el nombre del procedimiento. Se define procedimiento al proveer una especificación o interfaz y un cuerpo. La especificación le da nombre al procedimiento, una lista de los tipos y nombres de sus parámetros, así como el tipo de su valor devuelto, si es que existe alguno:
//código c++
Void intswap (int& x,int&y)// especificación
{int t= x; // cuerpo
x=y; // cuerpo
y=t;// cuerpo
}
El procedimiento intswap intercambia los valores de sus parámetros x y y utilizando la variable local t.
En algunos lenguajes y en algunas situaciones, pueden separarse una especificación de procedimiento de su cuerpo, en el caso de que la especificación deba estar disponible por adelantado:
Void intswap (int&, int&);// sólo especificación
Note que esta especificación no require que estén especificados los nombres de los parámetros.
En C++ esta clase de especificacación se conoce (de manera confuse) como una declaración, mientras que la definición complete (incluye el cuerpo) se llama definición (en C, las declaraciones se llaman prototipos). Típicamente, incluso cuando una especificación antecedente a una definición debe repetirse con el cuerpo.
Se llama o activa un procedimiento al enunciar su nombre, junto con los argumentos de la llamada, que corresponden a sus parámetros:
Intswap (a,b);
Una llamada o un procedimiento transfiere el control al principio del procedimiento llamado (el llamado). Cuando la ejecución llega al final del cuerpo; el control es devuelto al llamador. En algunos lenguajes, puede devolverse el control al llamador antes de llegar al final del cuerpo del llamado, utilizando un enunciado return:
//código C++
Void intswap (int& x, int&y)
{ if (x == y) return;
int t = x;
x = y;
y = t;
}
En algunos lenguajes como FORTRAN, para llamar un procedimiento debe también incluirse lq palabra clave CALL, como en
CALL INTSWAP (A , B)
(en el FORTRAN, a los procedimientos se les llama subrutinas)
Un lenguaje de programación pudiera hacer la distinción entre procedimientos, mismos que llevan a cabo sus operaciones cambiando sus parámetros o variables no locales, y las funciones que aparecen en expresión y que computan valores devueltos.
Las funciones pueden o no cambiar sus parámetros y variables no locales. En C y C++, todos los procedimientos implícitamente son funciones; aquellas que no devuelvan valores se declaran como void, en tanto que las funciones normales se declaran como que tienen el tipo (devuelto) del valor que devuelven:
int max (int x, int y)
{ return x > y ? x : y;
}
En algunos lenguajes, por ejemplo en Ada y FORTRAN, se utilizan diferentes palabras clave para los procedimientos y para las funciones:
-- Procedimiento en Ada
procedure swap ( x, y: int out integer) is
t: integer;
begin
if ( x = y) then return;
end if;
t :=x;
x :=y;
y :=t;
end swap;
--Función en Ada
fuction max ( x,y: integer ) return integer is
begin
if ( x > y ) then return x;
else return y;
end if;
end max;
En algunos lenguajes sólo existen funciones (esto es, todos los procedimientos deben devolver los valores). Los lenguajes funcionales en particular tiene esta propiedad.
En algunos lenguajes, las declaraciones de procedimientos y de funciones se escriben de una forma similar a las declaraciones de constantes, usando el signo de igual, como en la siguiente declaración de función ML para un procedimiento swap:
(* código ML *)
fun swap ( x, y)=
let val t=!x
in
x :=!y;
y:= t
end;
El uso de un signo igual para declarar procedimientos está justificado, dado que una declaración de procedimientos le da el nombre del procedimiento un significado que se conserva constante durante la ejecución del programa. Una declaración de procedimiento crea un valor de procedimiento constante y asocia un nombre simbólico –el nombre del procedimiento- a dicho valor.
Un procedimiento se comunica con el resto del programa a través de sus parámetros y también a través de sus referencias no locales, esto es referencias a variables declaradas fuera de su propio cuerpo. Las reglas de alcance que establecen los significados de las referencias no locales.
Administración de la memoria dinámica
En un lenguaje imperativo típico como C, la asignación y desasimilación automática del almacenamiento ocurre únicamente para los registros de activación de una pila. También esta disponible bajo control manual la asignación dinámica explicita, así como el uso de apuntadores mediante un “montón” de memoria independiente de la pila.
Los lenguajes con necesidades significativas del almacenamiento en el montón, como Java, están mejor dejando el almacenamiento dinámico fuera de la pila aun administrador de la memoria que incluya recolección automática e la basura.
Cualquier lenguaje que no aplique restricciones significativas al uso de procedimientos deberá incluir la recolección automática de basura, ya que el sistema basado en pilas de llamados y retornos de procedimientos ha dejado de ser correcto.
Se podría intentar resolver este problema utilizando un procedimiento muy sencillo, simplemente no desasignando ninguna memoria una vez que esta ha sido asignada. Esto quiere decir que toda llamada a una función genera en la memoria un nuevo registro de activación, pero a la salida esta memoria no es desasignada.
La administración automática de la memoria se ubica en dos categorías: la recuperación de almacenamiento previamente asignado pero ya no utilizado, aveces conocido como recolección de basura y el mantenimiento para el espacio libre para la asignacion
Mantenimiento de espacio libre
Por lo general el sistema operativo pone un bloque contiguo de memoria para uso de un programa en ejecución. El espacio libre en el interior del bloque es conservado por una lista de bloques libres. Una forma de hacer lo anterior es por medio de una lista vinculada.
Cuando es necesario asignar un bloque de un determinado tamaño, el administrador de la memoria busca un bloque libre que tenga suficiente espacio y después ajusta la lista de espacio libre para eliminar el espacio que se acaba de asignar. Cuando se recupera a memoria, los bloques son devueltos a la lista de espacio libre, después deberán unirse a bloques adyacentes, para formar el bloque contiguo mas grande de memoria libre, El proceso se llama fusión o unión, sin enbargo al unirse una lista puede quedar fragmentada. Para evitar lo anterior, la memoria debe, de vez en cuando, compactarse moviendo todos lo bloques libres para unirlos y crear un solo bloque.
La compactacion involucra gran cantidad de carga general, ya que las ubicaciones de las cantidades asignadas se modificaran y sera necesario cambiar las estructuras de datos y las tablas en el ambiente en tiempo de ejecución para que reflejen las nuevas localizaciones.
Recuperación de almacenamiento
Reconer cunado un bloque de almacenamiento ya no es referenciado, ya se directa o indirectamente mediante apuntadores, es una tarea mucho mas difícil que el mantenimiento mismo de la lista libre. Históricamente se han utilizado dos métodos principales: conteo de referencia y marcar y barrer.
El concepto de refencias es método de recuperación del almacenamiento, ya que procura recuperar espacio tan pronto este deje de estar refernciado. Cada bloque de almacenamiento asignado contiene un campo de conteo adicional que guarda el numero de referencia en relación con otros bloques. Cada que se cambia de referencia este conteo de referencias debe ser actualizado. Cuando el conteo de referencia llega a cero, el bloque puedes ser devuelto a la lista libre. Los inconvenientes de este método es la memoria adicional que necesita para manter actualizados los conteos de referencia mismos, mas serio es el esfuerzo de mantener el conteo, que puede ser muy grande.
El metedo alterno estándar a los conteos de referencia es marcar y barrer. Este método es el que se conoce como perezoso, ya que pospone la recuperación de cualquier almacenamiento hasta que el asignador se quede sin espacio, y en ese momento busca todo el almacenamiento que pueda ser referanciado de regreso a la lista libre. Esto lo hace en dos pasadas. En la primer pasada se siguen todos lo punteros de manera recursiva, iniciándose con el ambiente o la tabla de símbolos actuales, y maraca cada bloque de almacenamiento localizado. Este proceso requiere un bit adicional de almacenamiento para el marcado. En una segunda pasada se barre de manera lineal atavez de la memoria devolviendo los bloques no marcados a la lista libre.
Es posible efectuar una mejoría contabilizadora dividiendo la memoria disponible en dos partes iguales y asignado el almacenamiento solo a una de las partes a la vez. Entonces durante la pasada de marcado todos los bloques se copian de inmediato a la segunda mitad del almacenamiento no en uso; pro lo tanto, a menudo este método se le conoce como parar y copiar.
Conocido como recoleccion generacional de basura, añade un área de almacenamiento permanente al esquema de recuperación. Los objetos asignados que sobrevivan lo suficiente simplemente son copiados al espacio permanente y no son reasignados durante recuperaciones de almacenamiento subsecuentes.
8.4 AMBIENTES, ACTIVACION Y ASIGNACIÓN DE PROCEDIMIENTOS
Para poder mantener el ambiente invocador, es necesario algún concepto de cerradura para resolver referencias no locales. A menudo, es necesario un claro discernimiento de este modelo de ejecución para comprender en su totalidad el comportamiento de los programas, ya que las semánticas de las llamadas de procedimientos esta grabada en dicho modelo.
Un ambiente basado totalmente en pilas ya no resulta adecuado para encarar las variables de procedimientos ni la creación dinámica de estos, y que aquellos lenguajes que tengan estos servicios, en particular los lenguajes funcionales, están obligados a usar un ambiente totalmente dinámico mas complejo con recolección de basura.
8.4.1AMBIENTES TOTALMENTE ESTATICOS
Como ejemplo FORTRAN 77en el cual la asignación de memoria puede llevarse a cabo en tiempo de carga y las localizaciones de todas las variables quedan fijas. Las definiciones e funciones y de procedimientos (o subrutinas) no pueden ser anidadas como en C, y no se permite la recursión a diferencia con C. Toda la información asociada con una función o con una subrutina puede asignarse estáticamente. Cada procedimiento o función tiene un registro de asignación fijo, que ha previsto espacio para las variables y parámetros locales. Las variables globales se definen mediante declaraciones COMMON y se determinan utilizando apuntadores hacia un área común.
Cada registro de la activación se subdivide en varias áreas:
Cuando ocurre una llamada a un procedimiento S, se evalúan los parámetros y sus ubicaciones se almacenan en el espacio para los parámetros del registro de activación de S. El ambiente de instrucciones presentes se almacena como dirección remitente, y se efectúa un salto al apuntador de instrucciones de S. Cuando S sale se efectua un salto a la dirección de retorno.
Como un ejemplo:
Considere el siguiente programa en FORTRAN:
REAL TABLE (10), MAXVAL
READ *,TABLE (1), TABLE ( 2), TABLE (3)
CALL LRGST (TABLE, 3, MAXVAL)
PRINT *, MAXVAL
END
SUBROUTINE LRGST (A, SIZE, V)
INTEGER SIZE
REAL A (SIZE), V
INTEGER K
V = A (1)
DO 10 K = 1, SIZE
IF (A(K) GT. V) V= A (K)
10CONTINUE
RETURN
END
El ambiente de este programa se vería de la siguiente forma:
Forma de la pila de activación durante la ejecución de p:
Para encontrar la referencia no local a la x de q desde el interior de p se puede seguir el enlace de control hasta el registro de activación r pero se encontraría la x local de r. con esto se lograría un alcance dinámico en vez de un alcance léxico. Para lograr el alcance léxico, un procedimiento es que p mantenga un alcance a su ambiente léxico o de definición. A este enlace se le conoce como enlace de acceso, ya que proporciona al acceso a las variables no locales (algunas veces al enlace de acceso se le llama enlace estático). En vista de que p está definido en el interior de q, el enlace de acceso p es el ep existente cuando es definido p, por lo que el enlace de acceso de p apunta a la activación de q. Ahora cada registro de activación necesita de un nuevo campo, el campo del enlace de acceso, y la imagen completa del ambiente para este ejemplo es:
Cuando los bloques están anidados profundamente, para encontrar una referencia no local puede ser necesario seguir varios enlaces de acceso en vez de uno solo.
Por ejemplo, en Ada, para tener acceso a x desde el interior de q, se necesita seguir el enlace de acceso en el registro de activación de p, y acto seguido, siguiendo el enlace de acceso de p hasta el ambiente global. Este proceso se llama encadenamiento de accesos, y la cantidad de enlaces de acceso que deberían seguirse corresponde a la diferencia en niveles de anidamiento, o profundidad de anidamiento, entre el ambiente de acceso y el ambiente definidor de la variable que se está accesando.
Con este orden en el ambiente, la cerradura de un procedimiento se hace significativamente más complejo, ya que cada vez que un procedimiento es llamado, debe incluirse como parte del registro de activación el ambiente definidor de dicho procedimiento. Entonces, una función o un procedimiento en un lenguaje como Ada o Pascal debe representarse no sólo por un apuntador al código para el procedimiento, también por una cerradura que consiste en un par de apuntadores: el apuntador del código o de la instrucción, que se identifica como ip, y el apuntador de enlace de acceso o de ambiente de su ambiente definidor, mismo que identificaremos como ep; esta clausura la escribimos como
Por último, este es un ejemplo de un programa en Ada con procedimientos anidados y un diagrama de su ambiente en algún momento de su ejecución. El procedimiento anidado show tiene dos cerraduras diferentes; cada una de ellas corresponde a las dos distintas activaciones de p en las cuales show está definido.
Procedimientos calculados dinámicamente y ambientes totalmente dinámicos.
El ambiente de tiempo de ejecución basado en pilas es adecuado para casi todos los lenguajes estructurados en bloques con alcance léxico. El uso de cerraduras
Sin embargo, un ambiente basado en pilas tiene sus limitaciones. Por ejemplo, cualquier procedimiento que pueda devolver un apuntador a un objeto local, ya sea mediante un valor devuelto o a través de un parámetro de paso por referencia, dará como resultado una referencia pendiente al salir del procedimiento, ya que el registro de activación del procedimiento habrá sido desasignado de la pila. El ejemplo más sencillo de lo anterior es cuando se vuelve la dirección de una variable local:
Int * dangle(void)
{ int x;
Return &x;
}
Una asiganción addr = dangle() ahora hace que addr apunte a una ubicación no segura en la pila de activación.
Sin embargo, esta situación no puede suceder en Java, dado que no está disponible la dirección de una variable local. También Ada95 convierte esto en un error al declarar la regla de la vida de tipo acceso: un atributo x’access dando un resultado que corresponde a un acceso dando un resultado que corresponde a un acceso del tipo T (por ejemplo, un tipo apuntador) sólo es permitido si x puede mantenerse en existencia por lo menos el mismo tiempo que T. Por lo anterior, el código Ada equivalente al código C arriba mostrado es:
Type IntPtr is Access Integer;
Function dangle return IntPtr is
x: Integer;
begin
return x’access;
end dangle;
es incorrecto, puesto que la definición del tipo IntPtr acurre en un alcance exterior con relación a x (como debe ser para permitir la definición de dangle) violando la regla de vida de tipo acceso.
Sin embargo, existen situaciones en las que un compilador no puede detectar este error de manera estática. En Ada aún así acurriría una excepción durante la ejecución (Program_Error), pero en C/C++ y en algunos otros lenguajes, este error no será detectado ni estática ni dinámicamente. En la práctica, a los programadores que tienen clara la idea del ambiente les resulta fácil evitar este error.
Ocurre una situación más severa si el diseñador del lenguaje desea extender la expresividad y la flexibilidad del lenguaje el permitir que los procedimientos puedan ser creados dinámicamente, es decir, permitiendo la devolución de procedimientos a partir de otros procedimientos vía un valor devuelto o parámetros de referencia. Este tipo de flexibilidad por lo general es deseable en un lenguaje funcional y en un lenguaje de este tipo, los procedimientos se convierten en lo que se conoce como valores de primera clase. No se aplica ninguna restricción “arbitraria” para su uso. En un lenguaje de este tipo, no puede utilizarse un ambiente basado en pilas, en vista de que la cerradura de un procedimiento definido localmente tendrá un ep que apunta al registro de activación presente. Si dicha clausura está disponible fuera de la activación del procedimiento que la creó, el ep apuntará a un registro de activación que ya no existe. Cualquier llamada subsecuente a dicho procedimiento tendrá un ambiente de acceso incorrecto.
miércoles, 31 de octubre de 2007
Suscribirse a:
Entradas (Atom)