Source: http://docplayer.es/2788098-Inferencia-de-tipos-seguros-en-un-lenguaje-funcional-con-destruccion-explicita-de-memoria.html
Timestamp: 2017-01-20 01:56:34+00:00

Document:
⭐Inferencia de tipos seguros en un lenguaje funcional con destrucción explícita de memoria
Download "Inferencia de tipos seguros en un lenguaje funcional con destrucción explícita de memoria"
Monica Santos Montes
1 Inferencia de tipos seguros en un lenguaje funcional con destrucción explícita de memoria Proyecto de Fin de Máster Autor: Manuel Montenegro Montes Profesores directores: Ricardo Peña Marí y Clara María Segura Díaz Facultad de Informática Universidad Complutense de Madrid Septiembre 20072 23 Agradecimientos Quiero expresar mi más sincero agradecimiento a mis directores de proyecto, Clara Segura y Ricardo Peña por su inestimable ayuda y dedicación. Agracezco a Estela(Copyprina) y a Gerardo(D.P.) por su demostrada paciencia en el día de entrega del presente trabajo. También a Alfredo, Sergio, Raúl, Roberto y Juanan porsualegrecompañía(enformadeicono )durantelaredaccióndeestedocumento: esunalástimaqueenlosúltimosmesesantesdesuentregatuviesequedesinstalartan malintencionado software de mi sistema. 34 45 Índice general 1. Introducción Motivación Gestión de memoria en programas funcionales Objetivos Plande trabajo Descripción del lenguaje SAFE Marco delproyecto SELF (Software Engineering and Lightweight Formalisms) Código con Demostración Asociada (PCC) SAFE Ellenguaje SAFE Sintaxis Core-Safe Semántica operacional de Core-Safe Sintaxis Full-Safe Ejemplos Visión generaldel compilador SAFE Inferencia de tipos Hindley-Milner Expresionesde tipo Generación deecuaciones Resolución de ecuaciones Comprobación derestricciones isdata Comprobación dedesigualdades Tipoanotado por elusuario Tratamiento especialde laregión self Detallesdeimplementación Estado degeneración deecuaciones Generación de ecuaciones Sustituciones y resolución de ecuaciones Comprobación derestricciones ydesigualdades Ejemplos6 6 ÍNDICE GENERAL 4. Análisis de compartición Tiposderelaciones decompartición Análisisde lasexpresiones Análisisde lasdefiniciones Análisisde un programa Detallesdeimplementación Estructura de datos Relaciones Información de programa Análisisde expresiones Análisisdel programa Decoración delárbol abstracto Ejemplos Inferencia de tipos SAFE Expresionesde tipo Sistema de tipos Algoritmo deinferencia Recorrido bottom-up delárbol abstracto Recorrido top-down delárbol abstracto Comprobaciones finales Coste delalgoritmo Detallesdeimplementación Entorno deparámetros condenados Definiciones auxiliares Decoración delárbol abstracto resultante Reglasdeinferencia ycheck Cálculodel punto fijo ycomprobaciones finales Ejemplo Casosdeestudio Corrección del algoritmo de inferencia Propiedadesdelsistema detipos Propiedadesdelalgoritmo deinferencia Corrección delalgoritmo Definicionesrecursivas. Punto fijo Conclusiones y trabajo futuro Trabajorelacionado Manejo dememoria mediante regiones Tiposlineales Conclusiones Trabajofuturo7 Capítulo 1 Introducción En este trabajo se describirá con detalle el diseño e implementación de un algoritmo de inferencia para un lenguaje funcional con manejo de regiones y destrucción explícita de memoria, llamado SAFE. Este algoritmo permite trabajar de modo seguro con estructuras de datos, ya que a partir del código fuente de un programa escrito en SAFE garantiza que durante la ejecución del mismo no se producirán accesos a zonas de la memoria ya liberadas. Antes de embarcarse en los detalles resulta necesario ofrecer una visión global del contexto en el que el lenguaje SAFE se encuentra situado, así como una motivación que justifique la necesidad de un lenguaje que proporcione un enfoque semiexplícito de manejo de memoria. Esto será el objetivo de este capítulo Motivación La programación funcional está contenida dentro de un modelo de programación conocido como declarativo. En dicho modelo los programas están centrados es la especificación de los cómputos que se realizan, evitando detalles sobre el modo en el que esto ocurre. En este sentido los lenguajes funcionales están concebidos para ofrecer un mayor nivel de abstracción que los imperativos. Dentro del paradigma funcional los programas están basados en el concepto matemático de función, definida como un conjunto de ecuaciones. La programación funcional tiene como modelo de cómputo subyacente el λ-cálculo, bajo el cual se trabaja sobre expresiones, reduciéndolas sucesivamente hasta obtener un resultado. Los programas escritos en lenguajes funcionales gozan de ciertas propiedades que resultan deseables desde el punto de vista del programador. Una de ellas es la transparencia referencial: lo que define una función es la correspondencia que realiza entre los elementos de su dominio y su rango. Dicho de otra forma, el resultado de evaluar una función depende exclusivamente de sus parámetros de entrada. Esto implica que una expresión se evaluará siempre al mismo valor, independientemente del contexto en el que se encuentre. Una consecuencia de esto es la ausencia del concepto de estado en programación funcional, lo cual facilita la tarea de razonar sobre la corrección 78 8 CAPÍTULO1. INTRODUCCIÓN Figura 1.1: Manejo de memoria en lenguajes funcionales de un programa. En este contexto, los programas funcionales se prestan con relativa facilidad a su análisis estático, mediante el cual a partir del texto del programa se infieren propiedades del mismo. Uno de los análisis más extendidos en los lenguajes funcionales modernos es el análisis de tipos: las expresiones se clasifican según el tipo de valores a los que pueden ser reducidas. Esto garantizará que no se producirán errores de ejecución en el programa por incompatibilidades de tipo. Dentro de los detalles que los lenguajes funcionales abstraen, puede encontrarse el manejo de memoria como un caso particular: En la mayoría de lenguajes funcionales el sistema de ejecución reserva memoria a medida que se necesite, mientras haya espacio disponible. En caso de que se agote, un sistema de recolección de basura detecta aquellas partes de la memoria no son accesibles desde el estado actual de ejecución del programa y, por tanto, pueden reutilizarse. Sin embargo, en determinadas situaciones (aplicaciones críticas en seguridad, sistemas de tiempo real) resultan inaceptables la suspensión temporal del programa para ejecutar el recolector de basura y la parada repentina del programa en caso de que se agote la memoria disponible. Por otra parte, muchos lenguajes imperativos (como por ejemplo C++) permiten que el programador asuma (por ejemplo, mediante operadores new y delete) la reserva y la liberación de memoria. No obstante, este tipo de mecanismo es fuente de numerosos errores: punteros descolgados, memoria no liberada en la terminación del programa, compartición indeseada entre estructuras, etc Gestión de memoria en programas funcionales En relación al manejo de memoria en lenguajes funcionales podemos encontrar varios enfoques: en[hj03] se propone un análisis en tiempo de compilación para obtener cotas superiores lineales sobre el consumo de memoria producido por un programa. Los programas son escritos en un lenguaje funcional con una construcción especial llamada matchqueliberaceldasdememoria.en[tt97,tbe + 06]seofreceunadisciplina de gestión de memoria basada en regiones(esto es, zonas disjuntas de memoria donde los valores son almacenados). Los lugares en el flujo de programa donde se reservan y liberan regiones son inferidos automáticamente. En relación al manejo de memoria basado en regiones se ofrece en [HP99a] un método para comprobar cotas superiores9 1.3. OBJETIVOS 9 de espacio. No obstante, en ninguno de estos trabajos se ofrece un análisis que garantice que la destrucción de estructuras de datos se realiza de forma segura, detectando así en tiempo de compilación los problemas provenientes del manejo explícito de la memoria comentados anteriormente. En el DSIC se ha desarrollado un enfoque semiexplícito de manejo de la memoria, mediante la definición de un lenguaje funcional llamado SAFE, cuya descripción puede encontrarse en el Capítulo 2. En dicho lenguaje el programador especifica cierta información sobre el uso de las estructuras de datos. En particular puede indicar que una determinada estructura de datos no va a utilizarse más y que, por consiguiente, la región de memoria en la que se encuentra puede ser reutilizada. Los beneficios de este enfoque son: 1. Un sistema de tipos garantiza que el uso de estas facilidades de destrucción de estructuras pueden realizarse de forma segura. En particular se evita el acceso a estructuras de datos ya liberadas. 2. Es posible prescindir de un sistema de recolección de basura. Esto facilita la posibilidad de razonar sobre la cantidad de memoria que consume un programa Objetivos El trabajo aquí presentado tiene como objetivo el diseño e implementación del algoritmo de inferencia de tipos seguros para programas escritos en el lenguaje SA- FE. No obstante, para poder realizar dicha inferencia son necesarios algunos análisis previos, concretamente: Inferencia de tipos Hindley-Milner: Se encarga de asignar a cada expresión de un programa su tipo correspondiente. Éste es el algoritmo comunmente utilizado en lenguajes funcionales con disciplina de tipos, como Haskell. La parte fundamental del mismo procede en dos fases: generación de un sistema de ecuaciones (o unificaciones) entre tipos y resolución de dicho sistema. En el caso concreto del lenguaje SAFE se han de incorporar además en dicho algoritmo ciertas particularidades propias provenientes en gran medida del hecho de utilizar un enfoque basado en regiones como sistema de manejo de memoria. Análisis de compartición: Tiene como objetivo aproximar las relaciones de compartición que pueden producirse entre las estructuras de datos durante la ejecución de un programa. Con el resultado de estos dos análisis puede abordarse el análisis de tipos seguros (también llamados tipos SAFE), que extienden a los tipos Hindley-Milner incluyendo información adjunta sobre el uso previsto de las estructuras de datos. En concreto especifican si dichas estructuras resultan directamente destruidas durante una llamada a una función, o apuntan a una celda de memoria que ya ha sido liberada. Durante la10 10 CAPÍTULO1. INTRODUCCIÓN inferencia de estos tipos se tendrá en cuenta esta nueva información para garantizar que las destrucciones no se realizan de forma insegura. Los análisis y algoritmos explicados en este trabajo han sido implementados por el autor del mismo en el marco de la parte frontal de un compilador para el lenguaje SAFE. En el presente trabajo se expondrán algunos detalles relativos a esta implementación. Las aportaciones originales del autor de este trabajo destinadas a satisfacer estos objetivos planteados se muestran a continuación. 1. Aspectos de implementación de la inferencia de tipos Hindley-Milner, incluyendo la extensión ya mencionada del algoritmo de inferencia Hindley-Milner original. 2. Implementación del análisis de compartición de estructuras. Este análisis resulta imprescindible para conocer si la liberación de memoria se realiza de forma segura. Se estudiarán las estructuras de datos utilizadas que permiten un análisis eficiente. 3. Coautordeldiseñodelalgoritmodeinferenciadetipossegurosyautordelaimplementación del mismo. Como ya se ha explicado, el análisis realizado por este algoritmo permite garantizar si un programa no realiza operaciones inseguras, como por ejemplo, el acceso a memoria ya liberada. 4. Demostración de corrección del algoritmo de inferencia de tipos seguros con respecto al sistema de tipos SAFE. El trabajo realizado hasta el momento ha dado lugar a dos publicaciones: en[psm07] se describe el análisis de compartición entre estructuras de datos y en [MPS07] se detalla el algoritmo de inferencia de tipos seguros Plan de trabajo Este trabajo describe algunas de las etapas que conforman el compilador de SAFE. El orden en que estas etapas serán explicadas en este trabajo se corresponde con el orden en el que se suceden durante la compilación. En el Capítulo 2 se introducirá el lenguaje SAFE. Antes de definir su sintaxis y su semántica, se explicarán los conceptos y decisiones principales que motivaron su diseño. ElCapítulo3describiráeldiseñoeimplementacióndelafasedeinferenciadetipos Hindley-Milner aplicado al lenguaje SAFE. Comprenderá tanto el algoritmo de inferencia general como las fases específicas a este lenguaje11 1.4. PLAN DE TRABAJO 11 Por su parte, el Capítulo 4 tratará el diseño e implementación del análisis que aproxima las relaciones de compartición entre variables. Se definirán en primer lugar los distintos tipos de relaciones de compartición que pueden producirse entre estructuras de datos. A continuación se describirá la forma en la que se infieren dichas relaciones a partir de las expresiones que conforman un programa. La información obtenida de la inferencia de tipos Hindley-Milner y el análisis de compartición sirven como base para el algoritmo de inferencia de tipos SA- FE, que será descrito en el Capítulo 5. Antes de describir el propio algoritmo, se introducirá el sistema de tipos que garantiza que no se crean punteros descolgadosenmemoria.porotra parte,sedetallaránalfinaldelcapítulolosaspectosde implementación más relevantes en este algoritmo. El Capítulo 6 se encargará de establecer la relación entre el algoritmo de inferencia de tipos seguros y el sistema de tipos, ambos presentados en el capítulo anterior. En primer lugar se ofrecerá la demostración para determinadas propiedades del algoritmo de inferencia de tipos SAFE. Estas propiedades serán utilizadas para demostrar la corrección de dicho algoritmo de inferencia con respecto al sistema de tipos SAFE. En último lugar, el Capítulo 7 expondrá las conclusiones obtenidas y el trabajo futuro arealizaren elmarco del lenguaje SAFE.12 12 CAPÍTULO1. INTRODUCCIÓN13 Capítulo 2 Descripción del lenguaje SAFE Este capítulo ofrecerá una breve introducción al lenguaje SAFE. En primer lugar se describirá el contexto del proyecto SAFE y el área de investigación en el que se encuentra situado. Posteriormente se definirá el lenguaje Core-Safe y su versión edulcorada Full-Safe. Se pondrá especialatención en elprimero, ya que esellenguaje en el que se realizan la mayoría de los análisis explicados en este trabajo. Una vez expuestas la sintaxis y semántica del lenguaje se mostrarán varios ejemplos que ilustran las funciones de liberación explícita de memoria ofrecidas por el mismo. Por último se describirá brevemente el proceso de compilación de un programa SAFE Marco del proyecto En el Departamento de Sistemas Informáticos y Computación de la Universidad Complutense de Madrid, el grupo de Programación Funcional viene participando en un proyecto (TIN C04) coordinado con las Universidades de Castilla-La Mancha (UCLM), Politécnica de Valencia(UPV) y de Málaga (UMA). Dicho proyecyo recibe el nombre de SELF (Software Engineering and Lightweight Formalisms). En el seno del mismo, el grupo de la UCM trabaja en el campo de investigación del Código con Demostración Asociada (Proof Carrying Code o PCC). Con el fin de ofrecer una visión global del contexto en el que se encuentra situado el lenguaje SAFE, se ofrece a continuación una breve descripción de las líneas de investigación en las que el proyecto SELF está situado SELF(Software Engineering and Lightweight Formalisms) Uno de los problemas actuales dentro del desarrollo de tecnología software es la dificultad cada vez mayor para poder garantizar la fiabilidad de los sistemas desarrollados. El proyecto tiene como objetivo el desarrollo de métodos, herramientas y técnicas necesarias para permitir la creación de software de calidad, estando enfocado en la aplicación práctica a los procesos llevados a cabo por compañías de software. 1314 14 CAPÍTULO 2. DESCRIPCIÓN DEL LENGUAJE SAFE La idea básica del proyecto es el uso de métodos formales ágiles aplicados a Ingeniería del Software, es decir, la aplicación parcial de formalismos a distintos niveles de desarrollo: lenguaje, modelado, análisis y composición. De este modo se trata de mejorar la aplicación real de métodos formales en ciertas fases del ciclo de vida del software. Las actividades realizadas en este contexto pueden enmarcarse en una de estas áreas de investigación: Descripción semántica de componentes software: Análisis de las distintas posibilidades ofrecidas por los lenguajes de especificación y lenguajes funcionales para describir sistemas software. Desarrollo de técnicas para analizar la terminación de especificaciones, su eficiencia y posibles optimizaciones a aplicar. Verificación y depuración del software: Mejora de las técnicas de model checking y código con demostración asociada (PCC), que proporcionan una validación automática de los sistemas software. Dentro de este campo, el proyecto está enfocado a la aplicación de técnicas PCC en entornos de programación declarativa. Optimización de programas multiparadigma: Los lenguajes declarativos multiparadigma (lógicos, funcionales, concurrentes, con restricciones, etc.) ofrecen un alto poder de expresividad. El objetivo es la mejora de la eficiencia de estos lenguajes Código con Demostración Asociada (PCC) El lenguaje SAFE se encuentra en el área de investigación del Código con Demostración Asociada. En este marco, un consumidor de código verifica que el código proporcionado por un productor de código no fiable satisface un conjunto de reglas, que constituyen su política de seguridad. La verificación se realiza mediante la comprobación de una demostración formal que el productor adjunta al código que genera. Dentro del ámbito del lenguaje, la política de seguridad que conforma el principal objetivo del proyecto es la certificación del manejo seguro de la memoria, que implica: 1. La garantía de que no se realiza acceso a punteros descolgados en memoria. 2. La existencia de una cota superior en la cantidad de memoria necesaria para ejecutar un programa. Dicha demostración se incluye en el programa. Estos dos elementos son enfocados desde la perspectiva del análisis de programas. Dichos análisis se basan tanto en las técnicas de interpretación abstracta como en sistemas de tipos y efectos SAFE El lenguaje fuente sobre el que se realizan los distintos análisis comentados anteriormente recibe el nombre de SAFE. Se trata de un lenguaje funcional impaciente15 2.2. EL LENGUAJE SAFE 15 de primer orden con facilidades para la destrucción explícita y copia de estructuras de datos. Por otro lado proporciona regiones (es decir, partes disjuntas de la memoria) donde el programador puede almacenar estructuras de datos. Este trabajo se centrará en dos análisis: compartición entre estructuras de datos e inferencia de tipos seguros. Este último proporciona la base para la generación del certificado de una de las reglas de la política de seguridad particular de este lenguaje: la imposibilidad de acceso a punteros descolgados en memoria El lenguaje SAFE El objetivo principal de esta sección es presentar la sintaxis y semántica del lenguaje funcional SAFE. Antes de eso es necesario introducir los conceptos y decisiones de diseño que subyacen en el mismo. En [PS04] puede encontrarse una explicación más detallada de las definiciones aquí enunciadas y una motivación de las distintas decisiones tomadas. Existen dos versiones del lenguaje SAFE: Full-Safe: Lenguaje en el cual se escriben los programas. Posee una sintaxis similaraladehaskell,incorporandoelusodevariablesderegión,ajustedepatrones destructivo y operaciones de copia y reutilización. Core-Safe: Lenguaje núcleo sobre el que se definen los distintos análisis. Se trata de un subconjunto de Full-Safe. Dentro del proceso de compilación, descrito con detalle en la Sección 2.4, existe una fase de traducción de programas Full-Safe a programas Core-Safe. El análisis de compartición y la inferencia de tipos seguros se definen sobre este último y, por tanto, se realizan tras esta fase de transformación. EJEMPLO 1. A continuación se muestra la definición en lenguaje Full-Safe de una función que calcula la longitud de una lista: length [ ] = 0 length (x : xs) = 1 +length xs Puede observarse que la definición es idéntica a la que podría encontrarse en Haskell, ya que no se hace uso de ninguna de las funciones de manejo explícito de memoria proporcionadas por SAFE. No obstante se incluye aquí este ejemplo para ser comparado con su equivalente Core-Safe, que se muestra a continuación: length ys = case ys of [ ] 0 (x : xs) let n = length xs in 1 +n Pueden encontrarse diferencias significativas. El ajuste de patrones, que en la definición Full-Safe quedaba implícito mediante el uso de distintas ecuaciones, ahora se indica explícitamente mediante la construcción case. Por otro lado, en Core-Safe se obliga a que los parámetros16 16 CAPÍTULO 2. DESCRIPCIÓN DEL LENGUAJE SAFE de una función sean literales o variables. Por tanto, la llamada recursiva a la función length ha tenido que ser separada de la aplicación del operador (+) mediante la construcción let. Otra diferencia entre Full-Safe y Core-Safe es la no existencia de constructoras y funciones infijas en este último. Además existe un renombramiento de variables previo al proceso de transformación, por lo que el código Core-Safe generado realmente por el compilador se asemejaría másaloque semuestraacontinuación: length 30 x = case 30 x of [ ] 0 (:) 31 x 32 x let 33 x = length32 x in (+) 1 33 x No obstante, por motivos de claridad, en los ejemplos Core-Safe mostrados en este capítulo y posteriores no se tendrá en cuenta el renombramiento y se permitirán funciones/constructoras infijas. Antes de comentar los detalles del lenguaje se presentarán los conceptos fundamentales en la definición del mismo: regiones, celdas y estructuras de datos. DEFINICIÓN 1. Una región es un área contigua de memoria en el montón donde se puede construir, leer o destruir estructuras de datos. Tiene un tamaño conocido en tiempo de ejecución y puede ser reservada y liberada completamente en tiempo constante. DEFINICIÓN 2. Una celda es un pequeño espacio de memoria lo suficientemente grande como para almacenar un constructor de datos. En términos de implementación, una celda contiene la marca (o puntero al código) del constructor, y una representación de las variables libres a las que se aplica. Los parámetros del constructor pueden ser valores básicos, o bien punteros a valores no básicos. Por el término lo suficientemente grande se entiende que una celda liberada puede ser reutilizada directamente por el sistema. Una implementación ingenua de ello consiste en incluir en una celda suficiente espacio como para poder almacenar el constructor más grande. Un enfoque más eficiente puede consistir en tener un número fijo de tamaños de celda, todos ellos múltiplos del tamaño más pequeño. La idea fundamental consiste en poder reutilizar una celda en un tiempo constante. DEFINICIÓN 3. Una estructura de datos (ED) es un conjunto de celdas que se obtiene empezando por una celda considerada como la raíz, y hallando el cierre transitivo de la relación C 1 C 2, donde C 1 y C 2 sonceldasdelmismotipo T yen C 1 hay unpuntero a C 2. Por ejemplo, en una lista de listas(tipo [[a]]), las celdas contenidas en la estructuracons-nildelalistamásexternaformanunaed,enlaquenoestánincluidaslaslistas internas. Cada una de estas últimas constituye una ED propia. Durante el diseño del lenguaje se tomaron las siguientes decisiones: 1. Una ED reside completamente en una región. Esta decisión impone una restricción en las constructoras de datos: los hijos recursivos de una celda han de pertenecer a lamisma región que ésta.17 2.2. EL LENGUAJE SAFE UnaEDpuede serpartede otra, odos EDspuedencompartiruna tercera. 3. Los valores básicos (enteros y booleanos) no reservan celdas en ninguna región. Se encuentrandentro delas celdasde una ED,oenlapila. 4. Una función que recibe n parámetros de entrada puede acceder, como mucho, a n +2 regiones. Puede acceder a las EDs de sus parámetros, posiblemente residiendo cada uno en una región distinta. Toda función que devuelva una ED como resultado debe construirla en la regióndesalida.comomáximohayunaregióndesalidaporcadafunción. La expresión que realice la llamada a dicha función es la responsable de suministrar el identificador de región correspondiente. La función recibe la región de salida como un parámetro adicional. Toda función posee una región de trabajo opcional, denominada mediante el identificador self, donde pueden construirse EDs intermedias. La región de trabajo tiene la misma duración que la llamada a la función: Se reserva al inicio dela llamadaalafunción y selibera cuando su ejecución termina. 5. Si un parámetro de entrada a una función es una ED, puede ser destruido por la misma. En ese caso se dice que el parámetro está condenado, porque esta condición dependedeladefinicióndelafunción; nodesuuso. Por destrucción seentiende que el invocador de la función puede asumir con seguridad que las celdas ocupadas por la ED condenada son recuperadas por el sistema de ejecución. 6. Toda función tiene las siguientes posibilidades sobre sus EDs y regiones accesibles: Una funciónsólopuedeleeruna EDque aparececomoparámetrode sólolectura. Una función puede leer (antes de destruir) y debe destruir una ED que es un parámetro condenado. Una función puede construir, leer y destruir EDs en su región de salida y en su región de trabajo Sintaxis Core-Safe La sintaxis para el lenguaje funcional Core-Safe se muestra en la Figura 2.1. Se trata de un lenguaje de primer orden donde se impone la compartición mediante el uso de variables en las aplicaciones de funciones y constructoras. Un programa en Core-Safe, prog, es una secuencia de definiciones de funciones polimórficas recursivas simples seguidas por una expresión principal expr, cuyo valor es el resultado del programa. Toda definición de función sólo puede contener llamadas a funciones previamente definidas y la expresión principal puede llamar a cualquiera de ellas. Si una función construye una ED entonces tendrá un parámetro adicional r18 18 CAPÍTULO 2. DESCRIPCIÓN DEL LENGUAJE SAFE prog dec 1 ;...;dec n ;expr dec f x n = expr {función polimórfica, recursiva simple} f x n i = expr expr a {átomo: literal c o variable x} {copia} x! {reutilización} (f a n i {aplicación de función queconstruye ED} (f a n i ) {aplicación de función} (C a n i {aplicación de constructor} let x 1 = expr 1 in expr {norecursivo, monomórfico} n case x of alt i {case de sólo lectura} n case! x of alt i {case destructivo} alt C x n i expr Figura 2.1: Sintaxis del lenguaje Core-Safe que representa la región de salida donde la ED resultante será construida. Las únicas variables de región que pueden aparecer en el lado derecho de una definición son la región desalida r y laregión de trabajo self. Por otro lado, se permiten declaraciones de tipos de datos algebraicos polimórficos. Estos tipos se supondrán definidos aparte mediante declaraciones data. Existe un tipo de datos predefinido, [a], que representa a las listas de elementos de tipo a. Este tipo dedatos incluye los constructores [ ] y (:). Con respecto a las expresiones, se incluyen las construcciones habituales en lenguajes funcionales: variables, literales, aplicaciones de función y constructor, construcciones let y case. No obstante, existen expresiones adicionales que serán descritas a continuación: Si x apunta a una ED, la expresión representa una copia de la ED apuntada por x, suponiendo que x no resida en r. Por ejemplo, si x es una lista contenida en r = r, entonces es una lista nueva con la misma estructura que x, pero compartiendo sus elementos. La expresión x! indica la reutilización de la ED destruíble a la que x apunta. La reutilización resulta útil cuando no se quiere destruir un parámetro condenado completamente, sino reutilizar parte del mismo. Otra posibilidad(menos eficiente) sería realizar una copia previa de x, permitiendo posteriormente destruir el original. Laexpresióncase! x of indicaqueelconstructormásexternodelaedapuntadaporxesliberadotraselajustedepatrones,demodoquexyanoesaccesible. Las subestructuras recursivas de x podrán ser destruidas en el código posterior mediante otro case! o reutilizadas mediante el símbolo!. Una variable condena-19 2.2. EL LENGUAJE SAFE 19,k : c,k : c [Lit],k : Ca i : Ca i [Cons] [p w],k : p,k : w [Var 1 ] j k l = j (Θ,Ca in ) = n copy(,j,cai ) [p (l,ca n i )],k : Θ,k : Ca i n [Var 2 [p w],k : p!,k : w [Var 3 ] Σ f x i n = e,k +1 : e[a i /x i n,k +1/self] Θ,k +1 : v,k : f a i n Θ k,k : v Σ f x i = e,k +1 : e[a i /x i n,k +1/self,j/r] Θ,k +1 : v,k : f a i Θ k,k : v,k : e 1 Θ,k : c Θ,k : e[c/x 1 ] Ψ,k : v,k : let x 1 = e 1 in e Ψ,k : v [Let 1 ] [App 1 ] [App 2 ],k : e 1 Θ,k : Ca i j k fresh(p) Θ [p (j,ca i n )],k : e[p/x 1 ] Ψ,k : v,k : let x 1 = e 1 in e Ψ,k : v C = C r,k : e r [a j /x rj n r ] Θ,k : v [p (j,ca i n r )],k : case p of C i x ij n i e i m Θ,k : v [Case] C = C r,k : e r [a j /x rj n r ] Θ,k : v [p (j,ca i n r )],k : case! p of C i x ij n i e i m Θ,k : v [Case!] [Let 2 ] Figura 2.2: Semántica operacional de Core-Safe dapuedeserleida,perounavezquehasidodestruidaoreutilizadanosepuede acceder a la misma Semántica operacional de Core-Safe En la Figura 2.2 se muestran las reglas que definen la semántica operacional para expresiones Core-Safe. Un juicio de la forma,k : e Θ,k : v indica que puede reducirse la expresión e a la forma normal v bajo un montón con k + 1 regiones (desde 0hasta k) yque ademásse produce un montón Θ con k +1 regiones. Un montón esuna función que asocia un puntero p con clausuras w de la forma (j,ca n i ),indicandoquelaclausuraseencuentraenlaregión j.unaformanormales,o bienunvalorbásicoc,obienunaconstrucción C a n queseencuentraenlaregión j. Losparámetros a i sonvaloresbásicosopunterosaotrasclausuras.losidentificadores de región son en realidad números naturales. Mediantelanotación [p w] seindicaelmontón enelquepuedeencontrarse el vínculo [p w]. Por el contrario, la notación [p w] denota la unión disjunta delmontón con elenlace [p w].20 20 CAPÍTULO 2. DESCRIPCIÓN DEL LENGUAJE SAFE La semántica de un programa Core-Safe d 1 ;...;d n ;e (no mostrada en las reglas) es la semántica dela expresión principal e bajo un entorno Σ quecontiene todas lasdefinicionesde funciones d 1 ;...;d n. Las reglas [Lit] y [Cons] tan sólo especifican que los valores básicos y construcciones son formas normales. La regla [Cons] no crea ninguna clausura. Realmente las clausurassólo se crean en la regla [Let 2 ], que eslaúnica que reserva memoria. La regla [Var 1 ] accede a la clausura correspondiente. La regla [Var 2 ] realiza una copia completa delaedapuntadaporlavariable p enuna nuevaregión j. Lafunción copy recorre los punteros de las posiciones recursivas de la estructura original, que se encuentraenlaregión l ycreaunaregión j unacopiadetodaslasclausurasrecursivas excepto laclausura raíz C a n i. Si la función copy encuentra un puntero descolgado durante el recorrido, la regla entera fallaría y la derivación quedaría detenida en este punto. Si la copia tiene éxito, laexpresiónprincipalseconvierteenlacopiac a in delaclausuraraíz,dondelospunteros a i de las posiciones recursivas han sido reemplazados por las correspondientes copiasa i (queseencuentranenlaregióndestino j).lospunterosqueseencuentranen posiciones no recursivas son compartidos entre la estructura original y la copia. Por ejemplo, si la ED es una lista que contiene listas, la estructura creada por copy es una copia de la lista externa, mientras que las listas internas son compartidas por la lista original y su copia. La regla [Var 3 ] es similar a [Var 1 ], con la diferencia de que el enlace [p w] se eliminadelmontón yportanto, p nopertenecealdominiodelmontónresultante.esto puede crear punteros descolgados en este último montón, ya que algunas clausuras pueden contener apariciones libres de p. Las reglas [App 1 ] y [App 2 ] muestran cómo se crea una nueva región. El cuerpo de la función se ejecuta en un montón con k + 2 regiones. Esto es, el identificador de región self se asocia con la nueva región k +1, de podrán crearse EDs en la misma o podráserpasadacomoparámetroenunallamadaafunción.mediantelanotación Θ k se indica la restricción del montón Θ a las clausuras contenidas en las regiones desde 0 hasta k. Antes de finalizar la ejecución de la función todas las clausuras creadas en la región k +1 son eliminadas. Esta acción puede resultar ser fuente de punteros potencialmente descolgados. Las reglas [Let 1 ] y [Let 2 ] expresan el carácter impaciente del lenguaje: en primer lugarsereducelaexpresióne 1 aformanormalyposteriormentesereducelaexpresión principal e. Lasapariciones de x 1 en esta última se reemplazan porla forma normal si esun valor básico, opor un puntero si esuna construcción. Por último, las reglas [Case] y [Case!] se diferencian en el hecho de que en esta última el enlace correspondiente al discriminante p es eliminado del montón. Esta acción puede crear también punteros descolgados Sintaxis Full-Safe El lenguaje Core-Safe sólo contiene las construcciones indispensables para poder programar con el lenguaje SAFE. El hecho de ser un lenguaje tan sencillo permite sim- Mostrar más
Objetivos Repasar los conceptos de abstracción de datos y (TAD) Diferenciar adecuadamente los conceptos de especificación e implementación de TAD Presentar la especificación algebraica como método formal Más detalles 4 o Ingeniería Informática
Esquema del tema 1. Introducción 4 o Ingeniería Informática II26 Procesadores de lenguaje Estructura de los compiladores e intérpretes 2. Etapas del proceso de traducción 3. La interpretación 4. La arquitectura Más detalles INDICE Parte I. Conceptos 1. El estudio de los lenguajes de programación 2. Cuestiones de diseño de lenguajes
INDICE Parte I. Conceptos 1 1. El estudio de los lenguajes de programación 1.1. Por qué estudiar lenguajes de programación? 2 1.2. Breve historia de los lenguajes de programación 1.2.1. Desarrollo de los Más detalles EJERCICIOS DE LENGUAJES Y PARADIGMAS DE PROGRAMACIÓN (CUESTIONES DE EXAMEN) PROGRAMACIÓN FUNCIONAL
EJERCICIOS DE LENGUAJES Y PARADIGMAS DE PROGRAMACIÓN (CUESTIONES DE EXAMEN) PROGRAMACIÓN FUNCIONAL María Alpuente y María José Ramírez 1 LENGUAJES Y PARADIGMAS: INTRODUCCIÓN 1. Indica cuál de las siguientes Más detalles Tema 1. Introducción a los TAD
Tema 1. Introducción a los TAD Objetivos En este tema nos ocupamos inicialmente del concepto de abstracción, dedicando la mayor atención a la abstracción de datos, estudiando aspectos relacionados con Más detalles INDICE. XVII Prólogo a la edición en español. XXI 1. Calculo proporcional 1.1. Argumentos y proporciones lógicas
INDICE Prologo XVII Prólogo a la edición en español XXI 1. Calculo proporcional 1.1. Argumentos y proporciones lógicas 1 1.1.1. Introducción 1.1.2. Algunos argumentos lógicos importantes 2 1.1.3. Proposiciones Más detalles Tipos Abstractos de Datos y Diseño por Contrato
Tipos Abstractos de Datos y Diseño por Contrato 1.- Motivación de los tipos abstractos de datos Nuestro objetivo es obtener descripciones apropiadas de los objetos, para lo cual se necesita un método que Más detalles Compiladores y Lenguajes de Programación. Maria de Guadalupe Cota Ortiz
Compiladores y Lenguajes de Programación Maria de Guadalupe Cota Ortiz Organizaciones que rigen las normas para estandarización de Lenguajes de Programación IEEE (Instituto de Ingenieros Eléctricos y Electrónicos) Más detalles Lenguajes y Compiladores
Información: http://www.cs.famaf.unc.edu.ar/wiki/ Profesores: Héctor Gramaglia, Miguel Pagano, Demetrio Vilela Régimen de regularidad y Promoción Se tomarán 2 parciales Promoción: obteniendo al menos 7 Más detalles Capítulo 12: Indexación y asociación
Capítulo 12: Indexación y asociación Conceptos básicos Índices ordenados Archivos de índice de árbol B+ Archivos de índice de árbol B Asociación estática Asociación dinámica Comparación entre indexación Más detalles Tema 3. El modelo Relacional
Tema 3. El modelo Relacional Juan Ignacio Rodríguez de León Resumen Presenta el modelo entidad-relación. Visión de alto nivel de las cuestiones referentes a diseño de bases de datos y los problemas encontrados Más detalles Capítulo V Operaciones Booleanas
85 Capítulo V Operaciones Booleanas 5.1 Introducción Es muy posible que en muchos casos sea necesario comparar dos objetos y determinar cuál es su parte común. Esto implica intersectar los dos objetos Más detalles Tesis de Maestría en Informática
PEDECIBA Informática Instituto de Computación Facultad de Ingeniería Universidad de la República Montevideo, Uruguay Tesis de Maestría en Informática Fusión en presencia de acumuladores Amarante 2010 Martínez Más detalles Introducción a los Tipos Abstractos de Datos
Página 1 de 8 Introducción a los Tipos Abstractos de Datos Introducción: Concepto de abstracción Abstracción funcional y abstracción de datos Construcción de tipos abstractos de datos Especificación de Más detalles Estructuras de Datos. Dr. Pablo E. Fidel Martínez López Lic. en Ciencias de la Computación UNR
Estructuras de Datos Dr. Pablo E. Fidel Martínez López Lic. en Ciencias de la Computación UNR ...but note that an implementation need not be actualized as code a concrete design is sufficient. Chris Okasaki Más detalles FICHEROS Y BASES DE DATOS (E44) 3º INGENIERÍA EN INFORMÁTICA. Tema 10. Álgebra Relacional
FICHEROS Y BASES DE DATOS (E44) 3º INGENIERÍA EN INFORMÁTICA Tema 10. Álgebra Relacional 1.- Introducción. 2.- Una Sintaxis para el Álgebra Relacional. 3.- Asignación Relacional. 4.- Operaciones Tradicionales Más detalles Ingeniería de Software con UML Unified Modeling Language Lenguaje Unificado de Modelado
Ingeniería de Software con UML Unified Modeling Language Lenguaje Unificado de Modelado 1. Introducción Unified Modeling Languaje Fuente: Booch- Jacobson-Rumbauch y diversos sitios Internet, entre otros: Más detalles Optimización de consultas Resumen del capítulo 14
Optimización de consultas Resumen del capítulo 14 Libro: Fundamentos de Bases de Datos Silberschatz et al. 5ed. Dr. Víctor J. Sosa Agenda 1. Visión general 2. Estimación de las estadísticas de los resultados Más detalles DELFOS, UN PROGRAMA INTERACTIVO PARA EL APRENDIZAJE SEMIPRESENCIAL DE DISPOSITIVOS ELECTRÓNICOS Y FOTÓNICOS
DELFOS, UN PROGRAMA INTERACTIVO PARA EL APRENDIZAJE SEMIPRESENCIAL DE DISPOSITIVOS ELECTRÓNICOS Y FOTÓNICOS V. JIMÉNEZ, J. PONS, J. CALDERER, L. PRAT Universitat Politècnica de Catalunya. Departament d'enginyeria Más detalles DEFINICION. Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006
ARBOLES ESTRUCTURAS DE DATOS 2006 DEFINICION Un árbol (tree) es un conjunto finito de nodos. Es una estructura jerárquica aplicable sobre una colección de elementos u objetos llamados nodos; uno de los Más detalles Una variable de clase escalar tiene un nivel de indirección igual a 1. Por ejemplo, las variables i, b y x definidas como se muestra a continuación.
Descripción de la semántica de ALFA En esta descripción sólo se mencionarán los aspectos en los que el lenguaje de programación ALFA pueda diferir de otros lenguajes de programación de alto nivel. Se sobreentienden Más detalles M III ABSTRACCIÓN Y CLASIFICACIÓN
M III ABSTRACCIÓN Y CLASIFICACIÓN COMPLEJIDAD Y ABSTRACCIÓN La abstracción en el desarrollo del programario En todo el proceso de abstracción siempre hay una parte de la situación o del problema que se Más detalles Programación en lenguaje C++
Programación en Lenguaje C++ Objetivos Unidad Tema Subtema Objetivos VI 6.1 Metodología de la programación Metodologías Diseños de algoritmos Creación de algoritmos Entender y aplicar los pasos a seguir Más detalles TEMA 1: INTRODUCCIÓN
1 DISEÑO Y DESARROLLO DE COMPILADORES TEMA 1: INTRODUCCIÓN Qué es un Compilador? Un compilador no es más que un traductor, es decir, un programa que nos permite pasar información de un lenguaje a otro. Más detalles 1 Agencia de viajes: enunciado
1 AGENCIA DE VIAJES: ENUNCIADO 1 1 Agencia de viajes: enunciado Una agencia de viajes mantiene una base de datos con exactamente N clientes y M destinos turísticos. En una situación real, estos valores Más detalles Introducción a la Computación
UNIVERSIDAD RAFAEL BELLOSO CHACÍN FACULTAD DE INGENIERIA INTRODUCCIÓN A LA COMPUTACION UNIDAD II: DATOS, ALGORITMOS Y PSEUDOCODIGOS http://www.urbe.edu/info-consultas/web-profesor/12697883/ ALGORITMO Un Más detalles TAD Lineales: Pila, Cola y Lista
TAD Lineales: Pila, Cola y Lista Objetivos! Dar a conocer los TAD lineales pila, cola y lista! Presentar la especificación de cada uno de los TAD! Discutir implementaciones alternativas para cada uno de Más detalles PROGRAMACIÓN BÁSICA DE LA COMPUTADORA. 1 Introducción. Tabla 1: Instrucciones MIPS
PROGRAMACIÓN BÁSICA DE LA COMPUTADORA 1 Introducción Un sistema de computadora total incluye tanto circuitería (hardware) como programación (software). El hardware consta de los componentes físicos y todo Más detalles BASES DE DATOS MIS 308
2. MODELOS DE DATOS Introducción 2.1 Entidad relación 2.2 Jerárquico 2.3 De red 2.4 Relacional Introducción Hoy en día las empresas manejan una gran cantidad de datos. Cualquier empresa que se precie debe Más detalles Procesadores de lenguaje Tema 5 Comprobación de tipos
Procesadores de lenguaje Tema 5 Comprobación de tipos Departamento de Ciencias de la Computación Universidad de Alcalá Resumen Sistemas de tipos. Expresiones de tipo. Equivalencia de tipos. Sobrecarga, Más detalles Competencias generales vinculadas a los distintos módulos Módulo de Formación Básica
Competencias generales vinculadas a los distintos módulos Módulo de Formación Básica C1. Capacidad para la resolución de los problemas matemáticos que puedan plantearse en la ingeniería. Aptitud para aplicar Más detalles GENERACIÓN DE CÓDIGO
GENERACIÓN DE CÓDIGO INTRODUCCION La generación de código es la fase más compleja de un compilador, puesto que no sólo depende de las características del lenguaje fuente sino también de contar con información Más detalles Unidad II: Diseño de Bases de Datos y el modelo E-R. 2.1 El Proceso de Diseño
Unidad II: Diseño de Bases de Datos y el modelo E-R. 2.1 El Proceso de Diseño El proceso de diseño para una base de datos consta básicamente de 7 pasos, los cuáles se describen en la siguiente imagen. Más detalles Programa Analítico 2010. Asignatura: Resolución de problemas de Optimización en Entornos Industriales
Programa Analítico 2010 Asignatura: Resolución de problemas de Optimización en Entornos Industriales CARRERA: LCC AÑO: 5º CREDITO HORARIO: 8 hs áulicas semanales DESPLIEGUE (primer semestre, segundo semestre Más detalles Nota 2. Luis Sierra. Marzo del 2010
Nota 2 Luis Sierra Marzo del 2010 Cada mecanismo de definición de conjuntos que hemos comentado sugiere mecanismos para definir funciones y probar propiedades. Recordemos brevemente qué son las funciones Más detalles Programación Avanzada para Sistemas de Telecomunicación. Objetos y clases. J.C. Cruellas. Objetos y clases
Programación Avanzada para Sistemas de Telecomunicación Objetos y clases Juan Carlos Cruellas cruellas@ac.upc.es Objetos y clases Concepto de objeto. Concepto de clase. Clases, objetos y programas. Clases Más detalles Arquitectura de Aplicaciones
1 Capítulo 13: Arquitectura de aplicaciones. - Sommerville Contenidos del capítulo 13.1 Sistemas de procesamiento de datos 13.2 Sistemas de procesamiento de transacciones 13.3 Sistemas de procesamiento Más detalles árbol como un conjunto de nodos y líneas
ÁRBOLES CAPÍTULO 6 ÁRBOLES Desde el punto de vista conceptual, un árbol es un objeto que comienza con una raíz (root) y se extiende en varias ramificaciones o líneas (edges), cada una de las cuales puede Más detalles INTRODUCCIÓN. Estructura de Datos Tipos Abstractos de Datos (TAD S) Profs. Lorna Figueroa M. Mauricio Solar F. UTFSM 1 / 2008
INTRODUCCIÓN Estructura de Datos Tipos Abstractos de Datos (TAD S) Para poder obtener un programa que resuelva un problema dado, son necesarios varios pasos : La formulación y especificación del problema Más detalles Migración de datos automática a partir de la información de los esquemas conceptuales 1
Migración de datos automática a partir de la información de los esquemas conceptuales 1 J.Pérez 1, J.A.Carsí 1, I.Ramos 1, V.Anaya 1, J.Silva 1, Departamento de Sistemas Informáticos y Computación Universidad Más detalles Administración de memoria: Funciones y operaciones
Administración de memoria: Funciones y operaciones Facultad de Ingeniería, UNAM Instituto de Investigaciones Económicas, UNAM Índice Introducción 1 Introducción 2 3 4 5 El administrador de memoria Es otra Más detalles {} representa al conjunto vacío, es decir, aquel que no contiene elementos. También se representa por.
2. Nociones sobre Teoría de Conjuntos y Lógica Para llevar a cabo nuestro propósito de especificar formalmente los problemas y demostrar rigurosamente la correctitud de nuestro programas, introduciremos Más detalles Tema 3. Interpretación Abstracta
Tema 3. Interpretación Abstracta Herramientas Avanzadas para el Desarrollo de Software Profesora: Alicia Villanueva DSIC, Escuela Técnica Superior de Ingeniería Informática Curso 2011-2012 Indice Indice Más detalles Apuntes de Matemática Discreta 6. Relaciones
Apuntes de Matemática Discreta 6. Relaciones Francisco José González Gutiérrez Cádiz, Octubre de 2004 Universidad de Cádiz Departamento de Matemáticas ii Lección 6 Relaciones Contenido 6.1 Generalidades..................................... Más detalles ((X A Y ) = A ) si y solo si X = Y, A = B, A X = X, (X A Y ) = X Y, (X A Y ) = X Y
El examen de Lógica y fundamentos del 11-02-2005 resuelto por cortesía de Alberto Castellón 1) Sea A = P(B) el conjunto de los subconjuntos de un conjunto B. a) Pruébese que A es un modelo de la teoría Más detalles Programación Funcional en Haskell
Programación Funcional en Haskell Paradigmas de Lenguajes de Programación 1 cuatrimestre 2006 1. Expresiones, valores y tipos Un programa en lenguaje funcional consiste en definir expresiones que computan Más detalles Significado de las f.b.f (fórmulas bien formadas) en términos de objetos, propiedades y relaciones en el mundo
Significado de las f.b.f (fórmulas bien formadas) en términos de objetos, propiedades y relaciones en el mundo Semánticas del cálculo de predicados proporcionan las bases formales para determinar el valor Más detalles TEMA II: CONJUNTOS Y RELACIONES DE ORDEN. Álgebra II García Muñoz, M.A.
TEMA II: CONJUNTOS Y RELACIONES DE ORDEN OBJETIVOS GENERALES 1. Hacer que el alumno asimile el concepto de conjunto como la estructura algebraica más simple en la que se ambientarán el resto de las estructuras Más detalles Nociones Básicas de Sémantica: Semántica Denotacional
Nociones Básicas de Sémantica: Semántica Denotacional Análisis de Lenguajes de Programación Mauro Jaskelioff 21/08/2015 Acerca de la Semántica Operacional En la semántica operacional el significado de Más detalles Práctica de Integración de Sistemas Aplicación Web.NET: Sitio de Comentarios de Eventos Deportivos
Práctica de Integración de Sistemas Aplicación Web.NET: Sitio de Comentarios de Eventos Deportivos 1. Introducción Curso académico 2009-2010 La práctica de Integración de Sistemas consiste en el diseño Más detalles UNIDAD I INTRODUCCIÓN A LOS CIRCUITOS LÓGICOS 1. ÁLGEBRA DE BOOLE 2. MÉTODO DE REDUCCIÓN DE MAPAS DE KARNAUGH 1-1. R. ESPINOSA R. y P. FUENTES R.
UNIDAD I INTRODUCCIÓN A LOS CIRCUITOS LÓGICOS. ÁLGEBRA DE BOOLE 2. MÉTODO DE REDUCCIÓN DE MAPAS DE KARNAUGH - . INTRODUCCIÓN A LOS CIRCUITOS LÓGICOS. ÁLGEBRA DE BOOLE. ÁLGEBRA DE BOOLE El álgebra de Boole Más detalles Capítulo 4. Requisitos del modelo para la mejora de la calidad de código fuente
Capítulo 4. Requisitos del modelo para la mejora de la calidad de código fuente En este capítulo definimos los requisitos del modelo para un sistema centrado en la mejora de la calidad del código fuente. Más detalles CICLO SUPERIOR DESARROLLO DE APLICACIONES MULTIPLATAFORMA
CICLO SUPERIOR DESARROLLO DE APLICACIONES MULTIPLATAFORMA PROGRAMACIÓN DIDACTICA ANUAL Parte específica del módulo: 0485. Programación Departamento de Familia Profesional de Informática Curso: 2014-15 Más detalles El proyecto realizado consiste en un resolutor de sudokus mediante CSP.
Introducción El proyecto realizado consiste en un resolutor de sudokus mediante CSP. El problema del sudoku fue inventado por Howard Garns en 1979 y se volvió muy popular en Japón en 1986. En España ha Más detalles Introducción a compiladores. Universidad Autónoma de Aguascalientes Prof. Eduardo Serna-Pérez Correo-e: eduardo.serna@gmail.com
Introducción a compiladores Universidad Autónoma de Aguascalientes Prof. Eduardo Serna-Pérez Correo-e: eduardo.serna@gmail.com Introducción a compiladores Definición de compilador Historia de los compiladores Más detalles Java Inicial (20 horas)
Java Inicial (20 horas) 1 Temario 1. Programación Orientada a Objetos 2. Introducción y Sintaxis Java 3. Sentencias Control Flujo 4. POO en Java 5. Relaciones entre Objetos 6. Polimorfismo, abstracción Más detalles Bienvenidos a la presentación: Introducción a conceptos básicos de programación.
Bienvenidos a la presentación: Introducción a conceptos básicos de programación. 1 Los programas de computadora son una serie de instrucciones que le dicen a una computadora qué hacer exactamente. Los Más detalles TEMA 3 (parte 2). Representación del Conocimiento
TEMA 3 (parte 2). Representación del Conocimiento Francisco José Ribadas Pena INTELIGENCIA ARTIFICIAL 5 Informática ribadas@uvigo.es 13 de noviembre de 2009 FJRP ccia [Inteligencia Artificial] 3.2.2 Lógica Más detalles Tema 1: Implementación del sistema de archivos
Tema 1: Implementación del sistema de archivos 1. Introducción 2. Implementación 3. Estructura del almacenamiento secundario Dpto. Tema Lenguajes 1: Implementación y Sistemas del Informáticos. sistema Más detalles 14. ÁRBOLES. 14.1 Fundamentos y terminología básica
Ricardo Ferrís / Jesús Albert Algoritmos y estructuras de datos I 14. ÁRBOLES 14.1 FUNDAMENTOS Y TERMINOLOGÍA BÁSICA... 79 14.2. ÁRBOLES BINARIOS... 81 14.3. FUNDAMENTOS... 82 14.3. OPERACIONES CON ÁRBOLES Más detalles Estructura de Datos. Unidad I Tipos de Datos
Estructura de Datos Unidad I Tipos de Datos Conceptos Básicos Algoritmo: es una secuencia finita de pasos o instrucciones ordenadas crono-lógicamente que describen un método para resolver un problema específico. Más detalles Grupo de Procesadores de Lenguajes - Línea: Código Móvil Seguro
Grupo de Procesadores de Lenguajes - Línea: Código Móvil Seguro Francisco Bavera Martín Nordio Jorge Aguirre Marcelo Arroyo Gabriel Baum Ricardo Medel Resumen En el último tiempo Proof-Carrying Code (PCC) Más detalles Tema: Sobrecarga de Operadores.
Programación II. Guía 7 1 Facultad: Ingeniería Escuela: Computación Asignatura: Programación II Tema: Sobrecarga de Operadores. Objetivos Describir como redefinir (sobrecargar) operadores para que funcionen Más detalles PROGRAMACIÓ DIDÁCTICA: Secuanciación, Temporalización y Unidades Didácticas
Departamento de Informática PROGRAMACIÓN DIDÁCTICA Curso 11-12 1 CONSEJERÍA DE EDUCACIÓN I.E.S. NERVIÓN Departamento de Informática CICLO FORMATIVO: TÉCNICO SUPERIOR EN DESARROLLO DE APLICACIONES MULTIPLATAFORMA. Más detalles PLAN DE ESTUDIOS Y CONTENIDOS MÍNIMOS
CARRERAS DE DOS AÑOS TECNICATURA EN PROGRAMACIÓN DE COMPUTADORAS PLAN DE ESTUDIOS Y CONTENIDOS MÍNIMOS Resolución UB 004/14 ANEXO Tabla general de asignaturas del Plan de Estudios y Obligaciones Académicas Más detalles Denominación de la materia. N créditos ECTS = 36 carácter = OBLIGATORIO SISTEMAS DE SOFTWARE. Ubicación dentro del plan de estudios y duración
Denominación de la materia SISTEMAS DE SOFTWARE N créditos ECTS = 36 carácter = OBLIGATORIO Ubicación dentro del plan de estudios y duración La materia Sistemas de Software está formada por 6 asignaturas Más detalles Tema 3: Bases de datos en Entorno Web
Tema 3: Bases de datos en Entorno Web 1. Introducción. Un sistema de bases de datos proporciona un control centralizado de los datos. Esto contrasta con la situación que prevalece actualmente, donde a Más detalles Examen escrito de Programación 1
Examen escrito de Programación 1 Escuela de Ingeniería y Arquitectura Departamento de Informática e Ingeniería de Sistemas 2 de septiembre de 2015 Se debe disponer sobre la mesa en lugar visible un documento Más detalles Tipos de datos. Lección 1. Programación. Curso 2006-2007. J. A. Bañares, Pedro J. Álvarez, S. Velilla
Lección 1. Programación. Curso 2006-2007 Tipos de datos J. A. Bañares, Pedro J. Álvarez, S. Velilla http://diis.unizar.es/ Departamento de Informática e Ingeniería de Sistemas 2 Tipos de datos, constantes Más detalles U i n d id d a 3. El Element os á bá i s cos de un programa
Programación Digital U id d 3 El t bá i Unidad 3. Elementos básicos de un programa 1. Concepto de Programa Es un conjunto de instrucciones (órdenes dadas a la computadora), que producirán la ejecución Más detalles TEMA II: ÁLGEBRA DE CONMUTACIÓN
TEMA II: ÁLGEBRA DE CONMUTACIÓN En este capítulo veremos los métodos matemáticos que se disponen para las operaciones relacionadas con los circuitos digitales, así como las funciones más básicas de la Más detalles Normativa de reconocimiento y transferencia de créditos de la Universidad Pública de Navarra
Reconocimiento y transferencia 1 Normativa de reconocimiento y transferencia de créditos de la Universidad Pública de Navarra Exposición de Motivos El Real Decreto 1393/2007, de 29 de octubre, por el que Más detalles Generación de Código Intermedio
Generación de Código Intermedio Francisco Rodríguez Zamora Universidad de Costa Rica, Escuela de Ciencias de Computación e Informática San José, Costa Rica francisco.rodriguez@ecci.ucr.ac.cr Jonathan Calderón Más detalles Registro (record): es la unidad básica de acceso y manipulación de la base de datos.
UNIDAD II 1. Modelos de Bases de Datos. Modelo de Red. Representan las entidades en forma de nodos de un grafo y las asociaciones o interrelaciones entre estas, mediante los arcos que unen a dichos nodos. Más detalles ESPACIO VECTORIAL ESPACIO VECTORIAL SUBESPACIO VECTORIAL BASE Y DIMENSIÓN N DE UN
Tema 5.- ESPACIOS VECTORIALES ESPACIO VECTORIAL SUBESPACIO VECTORIAL BASE Y DIMENSIÓN N DE UN ESPACIO VECTORIAL Fundamentos Matemáticosde la Ingeniería 1 Aunque históricamente el primer trabajo de Álgebra Más detalles Carrera: IFM - 0423 3-2-8. Participantes. Representantes de la academia de sistemas y computación de los Institutos Tecnológicos.
1.- DATOS DE LA ASIGNATURA Nombre de la asignatura: Carrera: Clave de la asignatura: Horas teoría-horas práctica-créditos Matemáticas para computación Licenciatura en Informática IFM - 0423 3-2-8 2.- HISTORIA Más detalles Problemas Resueltos de Desigualdades y Programación Lineal
Universidad de Sonora División de Ciencias Exactas y Naturales Departamento de Matemáticas. Problemas Resueltos de Desigualdades y Programación Lineal Para el curso de Cálculo Diferencial de Químico Biólogo Más detalles !!!!!!!! !!!!! Práctica!4.! Programación!básica!en!C.! ! Grado!en!Ingeniería!!en!Electrónica!y!Automática!Industrial! ! Curso!2015H2016!
INFORMÁTICA Práctica4. ProgramaciónbásicaenC. GradoenIngenieríaenElectrónicayAutomáticaIndustrial Curso2015H2016 v2.1(18.09.2015) A continuación figuran una serie de ejercicios propuestos, agrupados por Más detalles TEMA 4. Diseño Lógico de bases de datos relacionales.
TEMA 4. Diseño Lógico de bases de datos relacionales. 1. El modelo relacional La teoría formal que constituye los cimientos de los sistemas relacionales se conoce como modelo de datos relacional. Cuando Más detalles Tablas. Estas serán las tablas que usaremos en la mayoría de ejemplos. Empleado
Álgebra Relacional Un álgebra es un sistema matemático constituido por Operandos: objetos (valores o variables) desde los cuales nuevos objetos pueden ser construidos. Operadores: símbolos que denotan Más detalles Espacios Vectoriales
Espacios Vectoriales Departamento de Matemáticas, CCIR/ITESM 4 de enero de 2 Índice 3.. Objetivos................................................ 3.2. Motivación............................................... Más detalles Prácticas de programación en C con MinGW Developer Studio
Prácticas de programación en C con MinGW Developer Studio MinGW Developer Studio es un entorno de desarrollo integrado (IDE) para la programación en lenguaje C gratuito y cómodo de usar. Se ejecuta en Más detalles Procesamiento y Optimización de Consultas
FACULTAD DE CIENCIAS EXACTAS Y NATURALES DEPARTAMENTO DE COMPUTACIÓN Base de Datos Autores Diego Castro Sergio D Arrigo Leticia Seijas Con la colaboración de Cecilia Briozzo y Alejandro Eidelsztein Indice Más detalles Guía práctica de SQL
Guía práctica de SQL Francisco Charte Ojeda Agradecimientos Introducción Qué es SQL? Aplicaciones de SQL Intérpretes de SQL Tipos de RDBMS Cómo usar este libro Convenciones tipográficas 1. El modelo relacional Más detalles 2 + intexp + intexp. (2) intexp. 2 + intexp
1. Semántica de un lenguaje: primera aproximación El establecer el significado de las frases de un lenguaje de programación es un problema de múltiples aristas en tanto puede tener variados objetivos, Más detalles Evolución histórica 60 -. Metodologías
TEMA 1 INTRODUCCIÓN Historia Evolución de las técnicas de programación Qué es orientado a objetos? Factores cruciales que miden la calidad del software Externos Internos La familia Orientada a objetos Más detalles Compilador del lenguaje MOOL que genera código Objective Caml
Compilador del lenguaje MOOL que genera código Objective Caml Ruben Gonzalez Castro 1 1 Instituto Tecnológico de Culiacán, Av. Juan de Dios Batíz s/n Col. Guadalupe, Culiacán, Sin. 80220 México Tel. 667-713 Más detalles FICHEROS Y BASES DE DATOS (E44) 3º INGENIERÍA EN INFORMÁTICA. Tema 8. Elementos Básicos
FICHEROS Y BASES DE DATOS (E44) 3º INGENIERÍA EN INFORMÁTICA Tema 8. Elementos Básicos 1.- Ejemplo Introductorio. 2.- Dominios. 3.- Relaciones. 4.- Bases de Datos Relacionales. (Capítulo 11 del Date) EJEMPLO Más detalles Grado en Ingeniería Informática
Grado en Ingeniería Informática Competencias Generales y trasversales De acuerdo con la resolución del Consejo de Universidades de fecha 3 de marzo de 2009, para obtener este título de grado en ingeniería Más detalles Diseño y Admón. de Bases de Datos. Ingeniería Informática curso 2010/11
Laboratorio 06. Objetivos: Representación interna de un BD. Tablas, índices e índices full-text. Sesiones: 1 (24 de noviembre de 2010) Ejercicio: 1. Representación interna: 1.1. Copiar al repositorio de Más detalles Máster Universitario en Ingeniería de Caminos, Canales y Puertos Introducción al Análisis Numérico
Máster Universitario en Ingeniería de Caminos, Canales y Puertos Introducción al Análisis Numérico Departamento de Matemática Aplicada Universidad Granada Introducción El Cálculo o Análisis Numérico es Más detalles Glosario. actividad. 1. (tarea) 2. es un subproceso que no requiere mas descomposición.
Glosario Aclaraciones Los conceptos del glosario están ordenados alfabéticamente. Un concepto puede ser un único término como meta o una frase como ambiente de ingeniería de software centrado en procesos. Más detalles Refactorizar (v) Reestructurar el software aplicando una secuencia de refactorizaciones.
Refactorización Definición Refactorización (n) Cambio realizado a la estructura interna del software para hacerlo más fácil de comprender y más fácil de modificar sin cambiar su comportamiento observable. Más detalles INTRODUCCIÓN A. Autor: José Antonio Glez. Reboredo
INTRODUCCIÓN A Autor: José Antonio Glez. Reboredo 1. MÉTODOS FORMALES... 3 1.1. INTRODUCCIÓN... 3 1.2. ESPECIFICACIÓN... 4 1.3. VERIFICACIÓN... 5 1.3.1. COMPROBACIÓN DE MODELOS... 5 1.3.2. PRUEBA DE TEOREMAS... Más detalles Tecnólogo Informático- Estructuras de Datos y Algoritmos- 2009
Árboles Ejemplos de estructuras arborescentes: con forma de árbol Regla de Alcance: los objetos visibles en un procedimiento son aquellos declarados en él mismo o en cualquier ancestro de él (cualquier Más detalles 3.2 Operaciones aritmético-lógicas en Pascal
3.2 Operaciones aritmético-lógicas en Pascal Operadores Los operadores sirven para combinar los términos de las expresiones. En Pascal, se manejan tres grupos de operadores : 1. ARITMÉTICOS 2. RELACIONALES Más detalles RESTRICCIONES DE INTEGRIDAD Y DEPENDENCIAS FUNCIONALES Bases de Datos Universidad de Talca, II Semestre 2006. Jorge Pérez R.
RESTRICCIONES DE INTEGRIDAD Y DEPENDENCIAS FUNCIONALES Bases de Datos Universidad de Talca, II Semestre 2006 Jorge Pérez R. 1 Restricciones de Dominio Son la forma más elemental de restricciones de integridad. Más detalles Tiempo de Compilación. Programa fuente. Secuencia. de caracteres. Scanner. Secuencia. de símbolos Parser. Compilador.
ORGANIZACIÓN DE LA MEMORIA EN TIEMPO DE EJECUCIÓN Compilador Tiempo de Compilación Programa fuente Secuencia de caracteres Scanner Secuencia de símbolos Parser Árbol sintáctico Analizador semántico Generador Más detalles Tema 1: Computadores y Programas
Tema 1: Computadores y Programas Ingeniería Informática Ingeniería Técnica en Informática de Sistemas Ingeniería Técnica en Informática de Gestión Departamento de Ciencia de la Computación e I.A. Universidad Más detalles Integridad y Seguridad. Integridad y Seguridad. Restricción de Dominio. Protección. Índice. create domain. Dominios
Protección Integridad y Seguridad Las Restricciones de Integridad aseguran que las modificaciones realizadas por usuarios autorizados no provocan perdidas de Consistencia Semántica El Control de Acceso Más detalles 2017 © DocPlayer.es Política de privacidad | Condiciones del servicio | Feedback

References: Resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 Resolución 
 Resolución 
 Real Decreto 
 resolución