Capítulo 3: Semántica Abstracciones ------------- Una abstracción en un lenguaje de programación es cualquier cosas que tenga un nombre (usualmente un identificador). Ejemplos: variables, constantes, tipos, procedimientos, estructuras, clases, etc. Variables --------- Una declaración del tipo: int i= 5; introduce una variable de nombre i. Definiciones: +------------+ i | 5 | +------------+ - identificador i : Secuencia de caracteres para el nombre. - valor 5 : Contenido en un instante dado. - localidad +-----+ : La dirección y tamaño que ocupa la variable. (location) | | Puede ser asignado estáticamente en tiempo de +-----+ compilación (variables de Fortran o var. globales en C) o dinámicamente en tiempo de ejecución (variables locales en Pascal, C o Java). - tipo int : denota el universo de valores que puede almacenar y las operaciones que se pueden realizar con ella. La propiedad esencial de una variable es que puede ser asignada. i = 1; Cambia el valor almacenado en la variable. Constantes ---------- Ejemplos: 5, 3,14, "hola", true - Propiedad fundamental: no pueden ser asignadas. Su valor es inalterable. Problema en algunas implementaciones de C: char *p = "hola"; char *q= "hola"; p[0]= 'H'; /* => ¡q[0]=='H'! */ Por eso, en las implementaciones modernas de C, los strings se colocan en una zona de memoria read-only. Esto hace que la asignación p[0]= ... da segmentation fault. sol.: char p[5]; char *q= "hola"; strcpy(p, "hola"); p[0]= 'H'; - También se les puede dar nombre: Pascal: const pi= 3.14; pi:= 3.14159; da error Java: final double pi= 3.14; pi= 3.14159; da error · en ambos casos pi no es un l-value · el = en este caso no es una asignación, si no una inicialización. · conceptualmente, una constante no tiene asociada una localidad Propiedades de variables y constantes ------------------------------------- - Tiempo de vida (life time): el tiempo de vida de una variable especifica el momento en que se crea hasta el momento en que se destruye. - Alcance léxico (scope): es la porción de código en donde la variable es visible. Ejemplo 1 en C: int g1; extern int g2; int i; int P(int p) { int l; while (...) { int i; (*) Q(); if ( ... ) { int j; ... } else { double x; ... } } } void Q() { ... } - g1, g2, i: son variables globales y por lo tanto viven desde que se crea el proceso hasta que se termina. Su alcance es cualquier parte del archivo a partir de su declaración, excepto i en (*) en donde hay otra variable i. - el extern en g2 significa que esa variable es declarada en otro archivo. - P, Q: son constantes globales. - p y l: son locales al procedimiento y por lo tanto viven desde su declaración hasta el retorno del procedimiento. Su alcance es desde que se declaran hasta la llave '}' que termina el procedimiento. Obs.: durante la ejecución de Q, p y l siguen vivas, sin embargo no están en el alcance de Q. - i en (*), j y x: son locales a un bloque de un procedimiento y viven desde el instante en que se declaran hasta que termina la ejecución del bloque. El alcance es desde la instrucción que las declara hasta la llave '}' que termina el bloque. Obs.: conceptualmente se crea y destruye una instancia de i para cada iteración del ciclo (pero no en la implementación). - En Java, el tiempo de vida y alcance es similar al de C, solo que una vez que se declara una variable, no se puede declarar otra variable con el mismo nombre, ni aun en un bloque interno. - En C y Java, gracias al tiempo de vida de las variables locales es posible administrarlas en una pila. El registro de activación tiene el espacio para todas las variables locales: +-------+ | p | (4 bytes) +-------+ | l | (4 bytes) +-------+ | i | (4 bytes) +-------+ | j | x | (8 bytes= máximo entre 4 y 8 bytes) | | | +-------+ De esta forma, declarar una nueva variable local tiene costo cero en tiempo de ejecución. Ejemplo 2 en Java: class Point { public Point(int x, int y) { this.x= x; this.y= y; count++; } public void add(int dx, int dy) { x+= dx; y+= dy; } int x, y; private static int count= 0; static int getCount() { return count; } } - Las variables x e y son variables de instancia de la clase Point. Su tiempo de vida se inicia cuando el objeto es creado con new Point(...) y dura indefinidamente. En la práctica, el recolector de basuras (GC) recicla su espacio cuando detecta que la aplicación ya no puede alcanzar ese objeto. El alcance de x y e es toda la clase (desde el "{" hasta el "}"), exceptuando los métodos estáticos y los métodos que definen variables locales o parámetros con el mismo nombre. Las x e y son accessibles adicionalmente por medio de la notación obj.var. Debido al tiempo de vida ilimitado de las variables de instancia, los objetos no se pueden colocar en la pila, si no que se administran en un heap. - La variable count es una variable de clase. Su tiempo de vida se inicia cuando se carga la clase y finaliza con el término del proceso. El alcance es toda la clase. Además es accesible con la notación Clase.var. Atributos de las abstracciones en los L.P. ------------------------------------------ - Robustez (safety): que nunca ocurra algo malo. Ejemplos de cosas malas: · que una variable double se acceda como si fuese int (error de tipos) · que se acceda a una variable cuando su tiempo de vida expiró - Vivacidad (liveness): que ocurra algo bueno tarde o temprano. Ejemplos de cosas buenas: · que se llegue a recolectar el espacio utilizado por un objeto que ya no es accesible por la aplicación · que un programa no quede en un ciclo infinito - Eficiencia: que se ocupen pocos recursos. Los lenguajes de programación modernos, como Java, ML o Smalltalk, ponen el énfasis en la robustez, luego la vivacidad y por último la eficiencia. Esto se debe a que los errores por falta de robustez son muy difíciles de diagnosticar. La robustez conlleva ineficiencia o mayor tiempo de programación. En lenguajes como C, el énfasis está en la eficiencia, debido a que fue diseñado en tiempos en que los computadores eran 10000 veces más lentos que hoy. La eficiencia conlleva dificultad para depurar los programas. Tipos ----- El tipo de una variable caracteriza el universo de valores que puede almacenar y las operaciones que se pueden realizar con ella. - Tipos primitivos: int, char, double, boolean, etc. Una variable de un tipo primitivo es atómica, es decir no se puede asignar en forma parcial. - Tipos compuestos: arreglos, estructuras, clases de objetos. Se pueden asignar por componentes. - Tipos referencia. El valor es la referencia de un objeto que se encuentra en otro sitio. Las variables de tipo referencia se denominan punteros. - Tipos estáticos vs. tipos dinámicos: · Lenguajes estáticamente tipados: el código fuente especifica un tipo para cada variable. Ejemplos: Java, C, Pascal, etc. · Lenguajes dinámicamente tipados: no se especifica tipo para las variables en el código fuente, pero durante la ejecución, cada objeto/variable sí tiene un tipo. La verificación de tipos se hace durante la ejecución. Ejmplos: Scheme, Smalltalk, Prolog. - Eficiencia vs. robustez: · Lenguajes débilmente tipados: no siempre se verifica que un dato se acceda con el tipo adecuado. Ejemplo en C: double x= 1.0; double *px= &x; int i= *(int*)px; /* i contiene basura! */ · Lenguajes fuertemente tipados: se garantiza que el tipo es el correcto. Ejemplo en Java: Object s= "1"; int i= ((Integer)s).intValue(); // Cast exception en tiempo de ejecución Subtipos -------- Un tipo T1 es subtipo de T2, lo que se anota T1<=T2 si todos los valores de T1 están incluidos en T2. Si T2 incluye valores que no están en T1 se anota T1=T(e3) ---------------------------- ---------------------------- T(e1 ? e2 : e3)= T(e3) T(e1 ? e2 : e3)= T(e2) Problema: A a= cond ? new B() : new C(); con B error de tipos pero % ? (A)new B() : (A)new C(); funciona. lo que debería ser es: T(e1)=boolean ^ (existe t minimal y único tq T(e2)<=t ^ T(e3)<=t) ----------------------------------------------------------------- T(e1 ? e2 : e3)=t - Más extraña es la regla para la concatenación de strings: T(e1)=String v T(e2)=String --------------------------- T(e1+e2)=String El operando que no es un string se coerciona a String. En el caso de un objeto se hace invocando operando.toString(). Tipos compuestos ---------------- Un tipo compuesto describe un conjunto de valores en donde cada valor es un mapa de asociación, i.e. cada valor es un conjunto de pares ordenados: { (i0, v0), (i1, v1), ... } en donde cada par se forma de un índice y un valor. Características: número de componentes (o pares), tipo de las componentes. - Tipos homogéneos: arreglos. Los índices siempre están en un intervalo de los enteros. El tipo es uniforme para todos los valores. En Java, un arreglo de strings de 3 elementos contiene valores como: { (0, "hola"), (1, "que"), (2, "tal") } y su tipo se denota como String[] La regla de inferencia de tipos es: T(a)= t[] ^ T(i)= int Ejemplo: double[] d= new double[3]; ----------------------- d[2]= 1.0; T(a[i])=t ---- t= double, a= d, i= 2 Se implementan en un área contigua de memoria: para acceder al i-ésimo elemento hay que sumar el inicio con i*tamaño de los elementos. El acceso es bastante eficiente. La excepción es cuando los valores son de un tipo compuesto, porque en tal caso el tamaño no es una potencia de 2, por lo que la multiplicación no se puede hacer con un desplazamiento. No es el caso de Java, porque en Java los arreglos de objetos contienen solo referencias (de tamaño 4 bytes). - Tipos heterogéneos: estructuras o clases de objetos. Los índices son etiquetas estáticas o campos (conocidas en tiempo de compilación). El tipo de los valores varía. En Java la clase class Point { double x, y; } denota valores como: { (x, 1.0), (y, 3.0) }. Su tipo se denota como {(x, double), (y, double)} La regla de inferencia de tipos es: T(o)= C ^ (f, t) está en C Ejemplo: Point p; -------------------------- p.x= 1.0; T(o.f)= t --- o=p, C=Point, f=x, t=double Se implementan en un área contigua de memoria: en tiempo de compilación se calcula un desplazamiento constante para cada etiqueta. Para acceder al campo x se suma el inicio con el desplazamiento. Suponiendo que la dirección de inicio se encuentra en un registro en cualquiera microprocesador de hoy en día, esto se hace en una sola instrucción de máquina. - Arreglos asociativos: tipo de los índices y los valores varía. Ejemplo 1: el tipo Map en Java. Map map= new HashMap(); map.put(new Integer(1), "hola"); map.put("que", new int[]{ 1, 2, 3}); map contiene: { ( Integer(1), "hola"), ( "que", arreglo[1, 2, 3]) } · En Java, estos arreglos no son parte del lenguaje. Se implementan como bibliotecas de clases. · El problema es que hasta la version 1.4, el tipo de índices y valores es siempre Object, lo que obliga a usar casts al acceder a un índice: (String)map.get(new Integer(1)) · En Java 1.5 aparecen los tipos paramétricos: Map map; // arreglo que asocia strings -> reales. Ejemplo 2: los arreglos asociativos de Perl (aunque solo de strings a strings) Se implementan usando tablas de hashing, árboles de búsqueda binaria en memoria discontigua. Si bien son eficientes, acceder a un elemento cuesta unas 10 veces más que el acceso en un arreglo homogéneo. Objetos, referencias y punteros ------------------------------- - Un objeto es una variable en memoria que posee una referencia. - Una referencia es una etiqueta que permite diferenciar un objeto de otros objetos en memoria. Típicamente se implementa como la dirección en memoria del objeto. En general el tipo de un objeto puede ser primitivo o compuesto. En Java solo puede ser un tipo compuesto: una clase o un arreglo. En C, Pascal, Scheme o ML, también puede ser un tipo primitivo. - El conjunto de referencias a objetos de tipo T es en sí mismo un tipo y lo anotaremos como T* (por analogía a C y C++). También se puede declarar variables cuyo tipo es una referencia. Si el tipo de una variable p es tipo T* el valor almacenado en ella es una referencia (y no el valor del objeto). Se dice que p es un puntero. - Comparación entre objetos y punteros +-------+ +------+------+ p1 | o-+------>| 1.0 | 2.0 | objeto A +-------+ +-->+------+------+ | +-------+ | p2 | o-+---+ +-------+ +-------+ +------+------+ p3 | o-+------>| 1.0 | 2.0 | objeto B +-------+ +------+------+ +-------+ +------+------+ p4 | o-+------>| 3.0 | 4.0 | objeto C +-------+ +------+------+ · Igualdad de objetos: cuando dos objetos contienen el mismo valor. En la figura A y B son iguales, pero son distintos de C. · Identidad de objetos: cuando dos punteros referencian el mismo objeto. p1 y p2 referencian el mismo objeto A. En ese caso se dice que p2 (o p1) es un alias (cuando dos o más punteros referencian el mismo objeto). p1 y p3 son distintos aún cuando los objetos A y B son distintos. Punteros en C ------------- En C el operador & permite obtener una referencia de una variable. int i= 1, j= 2; int *p1= &i; p1 se inicializa con una referencia de i int *p2= p1; p2 % *p1= 3; i==*p1==*p2==3, j==2 p2= &j; a p2 se asigna una referencia de j => *p2==2 *p1= 4 i==*p1==4, j==*p2==2 - El operador unario * es el operador de contenido y permite obtener el objeto referenciado por un puntero. - Es posible referenciar objetos cuyo tiempo de vida expiró! int *p; { int a= 1; p= &a; ... } /* variable a expira */ printf("%d", *p); /* seguramente es 1 */ { int b= 2; ... } printf("%d", *p); /* podría ser 2! */ En C *no se especifica* cual es el contenido de una variable que ya expiró. Puede ser basura como puede ser el valor tenía antes que expirara. De la misma forma un procedimiento puede retornar punteros a variables que expiraron: double *makeDouble() { double *p= makeDouble(); double x= 0.0; printf("%e", *p); /* seguramente 0.0 */ return &x; printf("%e", *p); /* basura! */ } El problema es que el primer printf creo un registro de activación en la posición de memoria que ocupó alguna vez x. - Reglas de inferencia de tipos: v es un l-value ^ T(v)=t T(e)=t* ------------------------ ------- T(&v)=t* T(*e)=t - También se pueden declarar punteros a punteros: int **pp= &p1; El tipo de pp es int** Esto se lee el contenido del contenido de pp es un int. - Un arreglo de tipo T en C es una referencia del primer objeto de una área de memoria contigua que contiene varios objetos de tamaño fijo y conocido (numerados con índices 0, 1, etc.): int a[10], i; a es una referencia. T(a)=int* a= &i; es un *error* porque a es un valor, no una variable. - aritmética de punteros: Los operadores + y - permite obtener referencias de objetos dentro de un arreglo: int *p= p+2; equiv. a int *p= &p[2], p referencia el obj. con índice 2 - Regla de inf.: T(e)=t* ^ T(i)<=int T(e1)=T(e2)=t* -------------------- -------------- T(e+i)=t*, T(e-i)=t* T(e1-e2)=int La relación entre + y - es tq: (p+i)-p= i Obs.: la suma de punteros (i.e.: p+q) no tiene sentido. - El operador binario de subindicación [], que se usa como p[i], permite recuperar el objeto dentro del arreglo determinado por p, y con índice determinado por i. Es equivalente a *(p+i). - Dado un objeto o de tipo T y su referencia r de tipo T*, la expresión: (T´*)r entrega un referencia al mismo objeto, como si fuese de tipo T´, pero no se hace ningún tipo de conversión en la representación. Ej.: double d= 123.0, *p= &d; int *q= (int*)d; o simplemente q= (int*)&d; printf("%d", *q); basura! p y q apuntan al mismo trozo de memoria, pero p lee los bits contenidos en el formato signo, mantisa y exponente, mientras que q lee los bits contenidos en el formato enteros en complemento de 2. Regla de inf.: T(p)= t* ----------- T((t´*)p)=t´* - Gracias a los casts, malloc se implementa en C. Unix ofrece la llamada a sistema sbrk que extiende el espacio de direcciones de un proceso, entregando un puntero al inicio de la extensión de memoria. Malloc es un procedimiento de biblioteca que organiza la memoria adicional entregada por sbrk como un heap (nada que ver con la estructura de datos heap del curso de algoritmos): un montón de memoria. Para pedir memoria para una estructura de datos se usa: (struct Nodo*)malloc(sizeof(struct Nodo)) malloc entrega un trozo de memoria. El cast permite verlo del tipo requerido. - El espacio requerido para un objeto puede quedar en el stack: struct Punto { int x, y; }; Punto *proc() { Punto punto; Punto *ppunto= (Punto*)malloc(sizeof(struct Punto)); ... return ppunto; /* jamas &punto, por favor! */ } · La variable local punto es de tipo Punto, i.e. punto es el objeto. El objeto queda localizado en el registro de activación de proc, i.e. en la pila y por lo tanto su tiempo de vida dura hasta el "}". · La variable local ppunto es de tipo Punto* y por lo tanto es un puntero que referencia un objeto de tipo Punto, ppunto no es el objeto de tipo Punto como en el caso anterior (aunque en C un puntero también es un objeto). Como ppunto es una variable local, ppunto queda localizado en la pila y su tiempo de vida se acaba en el "}". El espacio requerido por el objeto referenciado por ppunto se pide con malloc. Este lo coloca en el heap y por lo tanto su tiempo de vida se acaba cuando explícitamente se invoca free(ppunto), que libera el objeto referenciado por ppunto, no el puntero. · Para acceder a los campos de punto: punto.x, punto.y · Para acceder a los campos del objeto referenciado por ppunto: ppunto->x <=> (*ppunto).x ppunto.x error de tipos, ppunto no es una estructura · Colocar un objeto en el heap es 10 veces más lento que colocarlo en la pila: si la eficiencia importa, cree los objetos en la pila. · alloca permite pedir memoria en la pila! void proc(int n) { int *p= (int*)alloca(n * sizeof(int)); ... } El objeto se destruye automáticamente al retorno del procedimiento en donde se creo, pero cuidado! todavia pueden quedar referencias de él. - Un objeto puede contener punteros, lo que hace posible implementar estructuras de datos recursivas como listas enlazadas, árboles de búsqueda binaria, etc. struct Nodo { int info; struct Nodo *next; }; struct Nodo *first= ... malloc ...; - Definición de tipos: typedef typedef unsigned int UINT; UINT u, *w; <=> unsigned int u, *w; typedef struct S **V; V v1, *v2; <=> struct S **v1, ** *v2; typedef double (*Fun)(double x); Fun f, g; <=> double (*f)(double x), (*g)(double x); Objetos en Java --------------- A pesar de que el marketing dice que Java no tiene punteros, Java sí los tiene: todas las variables cuyo tipo es un objeto, en realidad son punteros. Ej. class Punto { double x, y; } Punto a= new Punto(); - El tipo del objeto creado por new es Punto. - El tipo de la variable a es Punto* (conceptualmente) Características del sistema de objetos de Java: - Todos los objetos son de alguno de los tipos compuestos (instancias de clases y arreglos). - No existen objetos de tipo primitivo: no es posible conocer la dirección de variables int, double, etc. - Las variables locales de tipo primitivo (incluyendo las referencias) se colocan en la pila. - Todos los objetos se crean en el heap y tienen tiempo de vida ilimitado. - No existen variables cuyo tipo conceptual sea un tipo compuesto. - No hay aritmética de punteros Por lo tanto no es necesario establecer una diferencia en la declaración de un puntero y la declaración de un objeto (como es el caso de C): cuando se declara Punto a, se subentiende Punto* a. - Ejemplo: Punto proc() { Point punto= new Punto(); ... return punto; } · La variable punto es de tipo Punto *, se coloca en el registro de activación de proc y por lo tanto dura hasta el "}". · El objeto creado con new es de tipo Punto, se coloca en el heap y dura tiempo ilimitado. El recolector de basuras recicla su espacio cuando detecta que no es accesible por la aplicación. - Se pueden crear estructuras de datos recursivas: class Nodo { String info; Nodo prox; } Nodo n1= new Nodo(); // (*) n1.prox= new Nodo(); // (**) · El tipo conceptual de la variable n1.prox es Nodo*: es un puntero! · prox queda localizado dentro del objeto creado en (*). · El objeto creado en (**) es otro objeto, localizado en el heap y referenciado por n1.prox. - Los casts de objetos en Java son dinámicamente verificados: (A)e es normalmente aceptado por el compilador, aunque el tipo inferido para e no sea A. Pero se verifica en tiempo de ejecución que el objeto referenciado por la expresión e sea de tipo A o un subtipo de A. Si no lo es: ClassCastException. - Los arreglos no son punteros como en C. Siempre se crean en el heap. Solo pueden ser referenciados por las variables. Punto[] puntos= new Punto[10]; · El tipo conceptual de puntos es Punto[]* (puntero a un arreglo). · El tipo del objeto creado es Punto[]. - Relación de subtipos: · int < double, pero int[] no es < double[] · si PuntoAColor es subclase de Punto: PuntoAColor < Punto PuntoAColor[] < Punto[] . Cuidado: Punto[] puntos= new PuntoAColor[10]; // correcto puntos[0]= new PuntoAColor(); // correcto puntos[1]= new Punto(); // -> ArrayStoreException en tiempo de ejecución · Cuando el tipo de los elementos de un arreglo es otro objeto, toda asignación requiere ser verificada en tiempo de ejecución! - El tipo T[][] representa un arreglo de referencias de arreglos. double[][] m= new double[10][10]; <=> double[][] m= new double[10][]; for (int i= 0; i<10; i++) m[i]= new double[10]; double[] v= m[0]; // v corresponde a la primera fila de m - Arreglos parcialmente creados: · double[][] m; es legal · double[10][10] m; es un error: el tipo no lleva tamaño · new double[][] es un error · new double[][10] es un error · new double[10][20][][] sí es legal