X-Git-Url: https://git.llucax.com/z.facultad/75.31/presentacion.git/blobdiff_plain/f9bdfd92aa5ded9b0a19df26a04fdac7ad39451a..3dcf13b94e63ba8711b64b7a9c36469234cc0ebd:/presentacion_d.lyx diff --git a/presentacion_d.lyx b/presentacion_d.lyx index e59d805..28a50be 100644 --- a/presentacion_d.lyx +++ b/presentacion_d.lyx @@ -172,8 +172,8 @@ Tipos derivados \layout Standard De los tipos básicos pueden derivarse otros tipos. - Esto tipos son punteros, array y funciones, siendo estas últimas tal vez - un caso muy particular. + Esto tipos son punteros, array (estáticos, dinámicos y asociativos) y funciones +, siendo estas últimas tal vez un caso muy particular. Los array tal vez podrían considerarse tipos compuestos, pero como la variable en sí es un puntero, en realidad no lo es. Es decir, para obtener un elemento del array hay que aplicar aritmética @@ -186,6 +186,63 @@ expl implícitamente \emph default utilizando el operador corchetes. +\layout LyX-Code + +char[] str = +\begin_inset Quotes eld +\end_inset + +hola +\begin_inset Quotes erd +\end_inset + +; // Array dinámico de caracteres +\layout LyX-Code + +str = +\begin_inset Quotes eld +\end_inset + +hola todos +\begin_inset Quotes erd +\end_inset + +; // Se autoredimensiona +\layout LyX-Code + +int[2] arr; // Array (estático) de 2 int +\layout LyX-Code + +int[char[]] hash; // Array asociativo de int cuya clave es un char[] +\layout LyX-Code + +void function() fp; // Puntero a una función void (void) +\layout LyX-Code + +int function(bit) fp2; // Puntero a una función int (bit) +\layout LyX-Code + +int delegate(bit) del; // Delegado de tipo int (bit) +\layout Standard + +Los delegados son algo así como punteros a función con contexto. + El contexto puede ser tanto un objeto como un +\emph on +frame pointer +\emph default + (el puntero al stack en donde se encuentra el padre lexicográfico de una + función anidada). + Veremos un poco más los delegados en la sección +\begin_inset LatexCommand \vref{sub:Operaciones} + +\end_inset + + y en la +\begin_inset LatexCommand \vref{sub:Rutinas} + +\end_inset + +. \layout Subsection Tipos de usuario @@ -383,26 +440,170 @@ ar polimorfismo y herencia. Expresiones \layout Subsection + +\begin_inset LatexCommand \label{sub:Operaciones} + +\end_inset + Operaciones \layout Standard -D provee operaciones las operaciones básicas que provee prácticamente cualquier - lenguaje: asignación, comparación, incremento, decremento, suma, resta, - multiplicación, división, resto, algebra booleana (and, or, xor, not), - shifting. - También provee llamadas a funciones. - Los procedimientos son un caso particular de funciones que no devuelven - nada (void). +D provee las operaciones básicas que provee prácticamente cualquier lenguaje: + asignación, comparación, incremento, decremento, suma, resta, multiplicación, + división, resto, algebra booleana (and, or, xor, not), shifting. +\layout LyX-Code + +int i = 1 << 1; // 0001b << 1 == 0010b == 2 +\layout LyX-Code + +int j = i >> 1; // 2 >> 1 == 0010b >> 1 == 0001b == 1 +\layout LyX-Code + +i -= j; // i = i - j = 2 - 1 = 1 +\layout LyX-Code + +i = -i; // i = -1 +\layout LyX-Code + +i *= 4; // i = i * 4 = -1 * 4 = -4 +\layout LyX-Code + +i >>>= 1; // i = i >>> 1 = 1100b >>> 1 = 1110b = -2 +\layout LyX-Code + +i++; // i = i + 1 = -2 + 1 = -1 +\layout LyX-Code + +i |= j; // i = i | j = 1111b | 0001b = 1111b = -1 +\layout LyX-Code + +i &= j; // i = i & j = 1111b & 0001b = 0001b = 1 +\layout LyX-Code + +bit c = i > j; // c = 1 > 1 = false +\layout LyX-Code + +c = i && j; // c = 1 && 1 = true +\layout LyX-Code + +i = 3 / 2; // i = 3 / 2 = 1 (entero) +\layout LyX-Code + +i = 3 % 2; // i = resto(3/2) = 1 +\layout Standard + +También provee llamadas a funciones y delegados. +\layout LyX-Code + +printf( +\begin_inset Quotes eld +\end_inset + +Hola mundo +\backslash +n +\begin_inset Quotes erd +\end_inset + +); // Llama a void printf(char*, ...) +\layout LyX-Code + +bit ok = esta_ok(10, 1.5); // Llama a bit esta_ok(int, float) +\layout LyX-Code + +int n = objeto.cantidad(); // Llama a int Clase::cantidad(Clase) +\layout LyX-Code + +int delegate(void) delegado; +\layout LyX-Code + +delegado = &objeto.cantidad; +\layout LyX-Code + +n = delegado(); // Llama a objeto.cantidad() \layout Standard Además de esto, provee operaciones propias de un lenguaje imperativo de bajo nivel: aritmética de punteros, operador [] como método alternativo para acceder a una posición de un array, desreferenciamiento, obtención de una dirección de memoria de una variable, etc. - También incluye un operador para comparar si 2 referencias referencian - al mismo objeto y algunas operaciones propias de los arrays, como para - saber si un elemento está dentro del array o concatenación de arrays y - slicing. +\layout LyX-Code + +int[2] arr; +\layout LyX-Code + +arr[1] = 1; // asigno el segundo elemento (empieza en 0) +\layout LyX-Code + +int* p = cast(int*) arr + 1; // apunto a arr[1] +\layout LyX-Code + +*p = 2; // arr[1] = 2 +\layout LyX-Code + +*(--p) = 1; // p apunta a arr[0] y arr[0] = 1 +\layout LyX-Code + +p = &(arr[1]); // p apunta a arr[1] +\layout Standard + +También incluye un operador para comparar si 2 referencias referencian al + mismo objeto. +\layout LyX-Code + +class C { int i = 0; int opEquals(C o) { return i == o.i; } } +\layout LyX-Code + +C c1 = new C; +\layout LyX-Code + +C c2 = new C; +\layout LyX-Code + +C c3 = c1; +\layout LyX-Code + +c1.i = c2.i = 1; +\layout LyX-Code + +c1 is c2; // false +\layout LyX-Code + +c1 is c3; // true +\layout LyX-Code + +c1 == c2; // true +\layout Standard + +y algunas operaciones propias de los arrays y hashes (array asociatios), + como para saber si existe una clave o concatenación y slicing de arrays. +\layout LyX-Code + +int[3] arr; +\layout LyX-Code + +arr[1] = 10; +\layout LyX-Code + +int[2] arr2; +\layout LyX-Code + +arr2[1] = 1; +\layout LyX-Code + +arr3 = arr ~ arr2; // arr3 = (0,10,0,0,1) +\layout LyX-Code + +int[float] hash; +\layout LyX-Code + +hash[1.1] = 1; +\layout LyX-Code + +1.0 in hash; // false +\layout LyX-Code + +1.1 in hash; // true \layout Standard Finalmente provee un operador de resolución de scope, para acceder a variables @@ -410,13 +611,49 @@ Finalmente provee un operador de resoluci \layout Subsection Variables -\layout Comment - -Si hay o no variables sin nombre \layout Standard -El lenguaje cuenta con tipado débil, con conversiones implícitas, por ejemplo, - entre punteros. +El lenguaje provee variables sin nombre a través de punteros y alocación + manual de memoria. + En general las instancias de clases son referencias (no puede ser alocadas + en el stack, en principio), por lo que podría decirse que toda instancia + de clase es una variable sin nombre. + Para alocar memoria se puede usar el operador +\family typewriter +new +\family default + que aloca memoria +\emph on +vigilada +\emph default + por el recolector de basura, o a través de la llamada al malloc de C (en + el módulo +\family typewriter +std.c.stdlib +\family default + en D), que aloca memoria no +\emph on +vigilada +\emph default + por el recolector. + El manejo de referencias es automático, no hay forma de declarar una variable + de tipo referencia. + Si la variable es de tipo clase, será una referencia, si no no (con algunas + excepciones, como al pasarse por parámetro). + Si se desean usar variables sin nombre que no sean clases, hay que usar + punteros. +\layout LyX-Code + +import std.c.stdlib; +\layout LyX-Code + +int* p = cast(int*) malloc(4 * int.sizeof); // Nunca serán recolectados +\layout LyX-Code + +p[3] = 1; +\layout LyX-Code + +free(p); // Lo libero yo \layout Subsection Representación de la memoria @@ -459,39 +696,464 @@ s (punteros) a instancias de una clase (en realidad hay excepciones, ya a mano \emph default e inicializar el objeto en esa memoria, pero no es el caso general). +\layout Standard + +Como dijimos, los tipos simples ocupan una cantidad de memoria fija cada + uno. + Cada tipo derivado tiene sus propias particularidades. +\layout Subsubsection + +array estático +\layout Standard + +El array estático no es más que una región contigua de bytes de tamaño N*S, + siendo N la cantidad de elementos y S el tamaño que ocupa el elemento. + Una variable de este tipo, entonces, no es más que un puntero al primer + elemento. +\layout Subsubsection + +array dinámico +\layout Standard + +Los array dinámicos, como su nombre lo indica, no tienen un tamaño fijo, + por lo tanto se guarda el tamaño además de los elementos en sí. + Una variable de este tipo es entonces un indicador de la cantidad actual + de elementos y un puntero al primer elemento. + Es por esto que típicamente este tipo de array ocupa 8 bytes (4 bytes para + almacenar N y 4 bytes para almacenar el puntero al primer elemento, que + se establecen en tiempo de ejecución) más los N*S para los elementos en + sí. +\layout Subsubsection + +array asociativo (o hash) +\layout Standard + +La representación de este tipo de array no está aún definida, aunque al + igual que los array dinámico dice que la referencia ocupa 8 bytes, pero + no indica para que sirve cada byte, aunque es esperable que sea igual, + 4 bytes para la cantidad de memoria alocada para la tabla de hash y 4 para + el puntero a la tabla en sí. +\layout Subsubsection + +enum +\layout Standard + +No es más que un int con un rango de valores posibles predefinidos y con + nombres simbólicos, por lo que simplemente se almacena como un int y todos + los chequeos se realizan en tiempo de compilación. +\layout Subsubsection + +union +\layout Standard + +Las uniones ocupan en memoria, como mínimo, la misma la cantidad de bytes + que ocupa su elemento de mayor tamaño. + Como el tipo que se está usando para acceder se sabe en tiempo de compilación, + no es necesario almacenar datos extra, pero podría ocupar más lugar si + el compilador hiciera alguna optimización (para que ocupe múltiplos de + una palabra, por ejemplo). +\layout Subsubsection + +struct +\layout Standard + +Las estructuras, al igual que en C, se almacenan de forma contínua ocupando, + como mínimo, +\begin_inset Formula $\sum S_{i}$ +\end_inset + + siendo +\begin_inset Formula $S_{i}$ +\end_inset + + el tamaño del elemento i del struct. + Nuevamente, los tamaños se conocen en tiempo de compilación por lo que + no es necesario guardar datos extra y ocupando más eventualmente si el + compilador optimiza. +\layout Subsubsection + + +\begin_inset LatexCommand \label{sub:repr-class} + +\end_inset + +class +\layout Standard + +Las clases son seguramente las estructuras más complejas. + Basadas en las estructuras, le agregan datos de control para implementar + herencia y polimorfismo. + Para esto debe almacenarse, además de los elementos (no estáticos, o sea + de instancia) como en el struct, un puntero a una tabla virtual (vtable) + y un monitor, ocupando 4 bytes cada uno. + El monitor no está bien especificado para qué sirve, pero supongo que debe + estar relacionado al recolector de basura. + La tabla virtual, a su vez, está compuesta por un puntero a la instancia + de una clase ClassInfo (que guarda datos de la clase en sí) y por todos + los punteros a métodos virtuales (para implementar polimorfismo). + Los atributos estáticos (de clase), como ya se mencionó, se almacenan como + variables globales, ya que se conocen en tiempo de compilación. +\layout Subsubsection + +function +\layout Standard + +Los punteros a funciones se almacenan como un puntero común y corriente, + ya que la +\emph on +firma +\emph default + de la función se conoce en tiempo de compilación y se sabe la cantidad + de datos que se deben apilar y desapilar al hacer el llamado, por lo que + todo ese código puede hacerse en tiempo de compilación independientemente + de donde se encuentre el código de la función a ejecutar. +\layout Subsubsection + +delegate +\layout Standard + +Los delegados deben tener la información del contexto, es por esto que ocupan + 8 bytes (en x86), 4 para el puntero al código de la función y 4 para el + puntero al contexto (sea una instancia de clase o un +\emph on +frame pointer +\emph default +). + Esto se comprobó empíricamente ya que no está definido aún. \layout Subsection Modelo de ejecución \layout Standard -D es un lenguaje imperativo compilado, por lo que d +D es un lenguaje imperativo compilado, por lo que se basa en el modelo de + Von-Newman y sus 3 operaciones básicas: +\layout Enumerate + +Fetch +\layout Enumerate + +Incrementar IP +\layout Enumerate + +Executar instrucción +\layout Standard + +El llamado a funciones se hace a través de la pila, ya que soporta recursión + y hay una pila por cada hilo, ya que soporta multiples hilos. + Además de la cadena dinámica (para el llamado recursivo) tiene cadena estática, + ya que soporta funciones anidadas, con el modelo estático, que busca las + variables en el +\emph on +padre estructural +\emph default + de la función y no en la función apilada inmediatamente arriba. +\layout Comment + +Mencionar operaciones básicas: asignación, jump, push, pop, call, return \layout Subsection Punteros +\layout Standard + +Este lenguaje soporta punteros y referencias, aunque estas últimas son implícita +s (el compilador decide cuando usar una referencia y cuando una copia). + En términos generales, las instancias de clase siempre se referencian a + través de una referencia (jamás se copia un objeto implícitamente). + Como se explicó en la sección +\begin_inset LatexCommand \vref{sub:Operaciones} + +\end_inset + +, se proveen operaciones para tomar la dirección de una variable (su +\emph on +almacén +\emph default +) y desreferenciamiento y aritmética de punteros. + Además se pueden convertir punteros de forma implícita siguiendo algunas + reglas. + Por ejemplo cualquier puntero puede ser convertido implícitamente a un + puntero a +\emph on +void +\emph default + (sin tipo) o a un puntero a una clase ancestro (si es una instancia de + clase). + También se ha dicho que, al igual que en C, hay una relación muy estrecha + entre puntero y array, por lo que cualquier array puede ser convertido + implícitamente a un puntero. \layout Subsection Recolección de basura +\layout Standard + +D provee un recolector de basura, aunque aún no hay muchas definiciones + con respecto a su tipo. + Por el tipo de API que se provee para controlar el recolector de basura, + parece ser del tipo +\emph on +mark-sweep +\emph default + o +\emph on +copy collection +\emph default + ya que se proveen funciones para agregar raices y también parece implementar + algún tipo de algoritmo generacional ya que además de proveer un método + para realizar una recolección completa, provee uno para realizar una recolecció +n generacional. +\layout Standard + +Aunque no parece haber nada definido aún con respecto al recolector de basura + (más que estudiar empíricamente la implementación actual o basarse en lo + que provee la biblioteca estándar para manipular al recolector), se menciona + en varios lugares que el ciclo de colección sólo puede ser lanzado cuando + se intenta alocar nueva memoria. + Es decir, que se puede confiar en que el recolector no va a interrumpir + la ejecución del programa en un fragmento de código en el que no se aloca + memoria. + De cualquier manera, la biblioteca estándar también provee métodos para + desactivar momentáneamente al recolector, por si hay partes críticas del + programa que no deban ser interrumpidas. +\layout Standard + +Además se menciona que el ciclo de recolección debe correr solo; es decir, + que mientras corre el ciclo de recolección no puede haber ningún otro hilo + del programa corriendo al mismo tiempo (cosa que tiene mucho sentido, de + otra forma sería virtualmente imposible seguir el rastro de la memoria). +\layout Subsubsection + +Casos límite +\layout Standard + +D se enfrenta a un problema poco común en la recolección de basura, ya que + la mayor parte de los lenguajes que lo implementan no permiten un manejo + de bajo nivel de la memoria. + Hay varias circunstancias en las cuales el recolector de basura de D puede + fallar. + Veamos algunos casos: +\layout LyX-Code + +void* p; +\layout LyX-Code + +... +\layout LyX-Code + +int x = cast(int)p; +\layout Standard + +En este caso, el comportamiento es indefinido ya que el recolector no verifica + raices que no sean punteros. + Otro caso: +\layout LyX-Code + +void* p = cast(void*)12345678; +\layout Standard + +Si por casualidad la dirección de memoria está siendo manejada por el recolector + de basura, estamos ante un problema. + Otros caso que podrían resultar un tanto confuso es que no se puede confiar + en que un puntero conserve la dirección a la que apunta de forma invariante, + ya que el recolector de basura puede moverlo. + Por lo tanto un código como el siguiente: +\layout LyX-Code + +int* p1, p2; +\layout LyX-Code + +... +\layout LyX-Code + +if (p1 < p2) ...; +\layout Standard + +tiene un comportamiento aleatorio. + Y esto sólo por nombrar algunos problemas que puede acarrear el manejo + de bajo nivel de la memoria usando un recolector de basura. + Claro que si uno necesita un manejo de tan bajo nivel, para estos casos + se puede usar memoria no administrada por el recolector. \layout Subsection Instrucciones +\layout Comment + +por ahora vuela porque no sé a qué se refiere \layout Subsection + +\begin_inset LatexCommand \label{sub:Rutinas} + +\end_inset + Rutinas +\layout Standard + +D provee varios tipos de rutinas, aunque todos basado en el mismo tipo básico, + las funciones. +\layout Subsubsection + +Funciones planas (sin contexto) +\layout Standard + +Estas son las funciones más básicas. + Son funciones de nivel 0 (en cuanto a anidamiento) o estáticas (ya sean + anidadas o de clase), por lo que no necesitan de un contexto (cadena estática) + más que la ubicación de la porción de variables globales (estáticas). + Toman exáctamente la cantidad de parámetros que se especifica en su declaración. +\layout Standard + +Por supuesto estás funciones tienen acceso sólamente a las variables estáticas + (conocidas en tiempo de compilación y almacenadas en el bloque de datos + del programa), ya sean variables estáticas locales de una función o variables + estáticas de clase (recordar que son todas variables globales con un +\emph on +scope +\emph default + limitado). +\layout Subsubsection + +Funciones con contexto +\layout Standard + +Como ya hemos visto, en D hay algunas funciones que necesitan un +\emph on +contexto +\emph default +. + En esta categoría caen tanto los métodos de una instancia de clase como + las funciones anidadas. +\layout Standard + +En el caso de los métodos es muy claro y simple, además de la función, se + necesita saber sobre qué objeto se está aplicando, así que simplemente + se agrega a los parámetros declarados un puntero (o referencia) a una instancia + de la clase. +\layout Standard + +Con las funciones anidadas puede resultar un poco más confuso. + Estás funciones necesitan el +\emph on +frame pointer +\emph default + de la función +\emph on +padre +\emph default + (lexicográficamente hablando) para poder obtener sus variables locales. + Podría pensarse entonces, como si estás funciones agregan un parámetro + extra con el puntero a ese +\emph on +frame pointer +\emph default +. +\layout Subsubsection + +Funciones virtuales +\layout Standard + +Las funciones virtuales tienen la particularidad de no conocerse su dirección + de memoria en tiempo de compilación, por lo tante es necesario agragar + un nivel de indirección al llamarlas. + Es por esto también que es imposible que exista algún tipo de función virtual + sin contexto, ya que debe haber algún contexto que indique, como mínimo, + la dirección de la función a llamar. + D provee funciones virtuales solamente como métodos de instancias de clase + y lo hace de forma implícita (queda en manos del compilador determinar + si una función debe ser virtual o no), es por esto que guarda, como se + explicó en la sección +\begin_inset LatexCommand \vref{sub:repr-class} + +\end_inset + +, una tabla virtual, en donde se almacena el puntero a cada función virtual + de una clase. + Entonces para llamar a una función virtual, se obtiene el objeto al que + pertenece ( +\emph on +contexto +\emph default +) que tiene una tabla virtual. + El offset de esa función en la tabla virtual sí se conoce en tiempo de + compilación así que simplemente se ejecuta la función apuntada por vtable+4+off +set (el 4 es porque lo primero que se almacena en la vtable es el puntero + al objeto de tipo ClassInfo). \layout Subsubsection Pasaje de parámetros \layout Standard -Por copia en demanda (copy on write) y objetos por referencia. +Las funciones toman parámetros, que son siempre por copia en su implementación + real. + El pasaje por referencia se resuelve al igual que en C, utilizando punteros. + Hay un caso muy particular en D, que son las clases, que siempre son pasadas + por referencias. + Es decir, una variable de clase (que referencia una instancia de una clase) + es siempre de tipo puntero, auque sintácticamente sea utilizada como una + variable común, semánticamente se comporta como un puntero. +\layout Standard + +Varias veces se menciona que los parámetros se copian si hay escritura ( +\emph on +copy on write +\emph default +) en la documentación de D, pero se comprobó empíricamente que, como se + especifica en la sección de manejo de memoria, la copia por demanda se + realiza solamente en la biblioteca estándar, no es algo que provea el lenguaje. +\layout Subsubsection + +Funciones con parámetros variables +\layout Standard + +Además soporta, al igual que C, parámetros variables, simplemente proveyendo + métodos para obtener variables de la pila arbitrariamente. + Es decir, a la hora de compilarse un llamado a una rutina con parámetros + variables, se apilan todos los parámetros, se hace el +\emph on +call +\emph default +, y luego se desapilan. + La función llamada tiene entonces, métodos para obtener esos parámetros + extra que no figuraban en la declaración de la función. \layout Subsubsection -Anidamiento +Sobrecarga de funciones +\layout Standard + +D permite sobrecargar funciones. + Es decir, tener 2 funciones con el mismo nombre pero distintas firmas (cantidad + y/o tipo de parámetros). + Al igual que C++, no permite sobrecargar por el tipo de retorno solamente, + ya que por proveer conversiones implícitas sería imposible desambiguar + muchos casos. + Por supuesto esto también debe poder traducirse a funciones planas por + lo que debe haber una forma de identificar unívocamente a cada función + (con un nombre único, asociado a su dirección de memoria). + Para esto se utiliza una técnica conocida como +\emph on +name mangling +\emph default +, que consiste en transformar los nombres de funciones a un nombre único, + aunque no hay ninguna definición aún al respecto de como debe hacerlo D + (fundamental para poder interactuar entre distintos compiladores, ya que + de otra manera no podría encontrar los símbolos en código objeto compilado + por otro compilador). +\layout Standard + +Entonces el compilador, a la hora de evualuar la dirección de una función + sobrecargada, debe fijarse su nombre y sus parámetros, hacer el +\emph on +name mangling +\emph default + para obtener su identificador único y ahora si proseguir como si fuera + un función común y corriente. \layout Section Estructura del programa \layout Subsection Módulos, espacios de nombres, Interfaces +\layout Standard + \layout Section Orientación a objetos