Paradigmas

Un paradigma está constituido por los supuestos teóricos generales, las leyes y las técnicas para su aplicación que adoptan los miembros de una determinada comunidad científica. Es un modelo o esquema fundamental que organiza nuestras opiniones con respecto a algún tema en particular. Los paradigmas establecen límites, para resolver problemas dentro de estos, y de esta forma mejorar o proporcionar nuevas soluciones, ya que estos filtran experiencias, se ajustan a los límites, percepciones o creencias. Paradigmas de Programación Representan un enfoque particular o filosofía para la construcción del software. El paradigma imperativo es considerado el más común y está representado, por ejemplo, C, Pascal, COBOL. El paradigma orientado a objetos. Un lenguaje completamente orientado a objetos es Smalltalk. El paradigma funcional está representado por la familia de lenguajes LISP. Otro podría se ser Haskell. El paradigma lógico, un ejemplo es PROLOG. Paradigma Imperativo Fortran introdujo las expresiones simbólicas y subprogramas con parámetros. COBOL introdujo el concepto de descripción de datos. El Algol-60 introdujo el concepto de estructura de bloques, variables, procedimientos, etc. Influenció a numerosos lenguajes posteriores tan fuertemente que fueron llamados lenguajes estilo Algol. Pascal fue el lenguaje estilo Algol que se hizo más popular porque es simple, sistemático e implementado eficientemente. Describe la programación en términos del estado del programa y sentencias que cambian dicho estado. Los programas imperativos son un conjunto de instrucciones que le indican al computador cómo realizar una tarea. Las recetas y las listas de revisión de procesos, a pesar de no ser programas de computadora, son también conceptos familiares similares en estilo a la programación imperativa; cada paso es una instrucción. La programación imperativa recibe este nombre porque está basada en comandos que actualizan variables contenidas en almacenamientos. Tiene estrecha relación para modelar el mundo real. Se caracteriza esencialmente porque las instrucciones que lo componen se ejecutan secuencialmente en un orden preestablecido. La unidad base de ejecución es el programa o conjunto de instrucciones ejecutables, que se divide en una serie de módulos o rutinas distribuidos de acuerdo con una organización jerárquica. En este tipo de programación los datos están desorganizados, son meros apéndices de los programas y tan solo proporcionan valores que sirven para realizar cálculos. Uno de los programas situados en la raíz de la jerarquía recibe el nombre de programa principal y los demás se conocen con el nombre de subprogramas, subrutinas, funciones o procedimientos. En cuanto a los datos, dependiendo del lenguaje que se trate pueden ser globales, accesibles por todos los programas de la jerarquía, o locales, utilizables solo por el programa al que pertenece. Dentro de este tipo de programación podemos encontrar dos divisiones: programación estructurada o programación sin GOTO: presenta bastantes ventajas en cuanto a la facilidad de modularización, documentación y mantenimiento de los programas; programación no estructurada que permiten realizar saltos incondicionales en la ejecución del programa mediante instrucciones GOTO. Paradigma Orientado a Objetos Es el paradigma que está tomando mayor auge en los últimos años. La programación orientada a objetos deriva de conceptos introducidos por Simula, otro lenguaje del estilo Algol. Smalltalk está basado en clases de objetos, un objeto viene a ser como una variable que puede accederse sólo a través de operaciones asociadas con él. Los objetos que son entidades que combinan estado (es decir, datos) y comportamiento (esto es, procedimientos o métodos). La programación orientada a objetos expresa un programa como un conjunto de estos objetos, que se comunican entre ellos para realizar tareas. Lenguajes procedurales: escriben funciones y después les pasan datos. Lenguajes orientados a objetos definen objetos con datos y métodos y después envían mensajes a los objetos diciendo que realicen esos métodos en sí mismos. Paradigma Funcional Están basados en el cálculo lambda (o ?-cálculo), de Alonso Church. LISP fue el primer lenguaje basado enteramente en el Cálculo Lambda. Lisp en su forma pura, está basado enteramente en funciones sobre listas y árboles. Los lenguajes funcionales modernos, tratan a las funciones como valores de primera clase e incorporan también un sistema de tipos avanzado. La secuencia de computaciones llevadas a cabo por el programa se regiría única y exclusivamente por la reescritura de definiciones más amplias a otras cada vez más concretas y definidas. Los programas escritos en un lenguaje funcional están constituidos únicamente por definiciones de funciones Se verifican ciertas propiedades como la transparencia referencial (el significado de una expresión depende únicamente del significado de sus subexpresiones). No existe asignaciones de variables. Falta de construcciones estructuradas como la secuencia o la iteración (solo recursión) Entre los lenguajes funcionales puros: Haskell Miranda Los lenguajes funcionales híbridos: Lisp Scheme Ocaml Standard ML (estos dos últimos, descendientes del lenguaje ML). Paradigma logico Un lenguaje de programación lógica está basado en un subconjunto de la lógica matemática. La computadora es programada para inferir relaciones entre valores más que calcular valores de salida a partir de valores de entrada. PROLOG hizo a la programación lógica popular y es más bien débil e ineficiente, sin embargo fue modificado para agregarle características no lógicas para hacerlo más usable como lenguaje de programación. La mayoría de estos lenguajes se basan en la lógica de predicados. Se definen propiedades de los objetos del dominio de referencia y relaciones entre ellos a través de fórmulas, las cuales usan normalmente el conector implicación. Paradigma Orientado a Eventos La programación dirigida por eventos es un paradigma de programación en el que tanto la estructura como la ejecución de los programas van determinados por los sucesos que ocurran en el sistema o que ellos mismos provoquen. Será el propio usuario -o lo que sea que esté accionando el programa- el que dirija el flujo del mismo. Se llevarán a cabo las inicializaciones y demás código inicial y a continuación el programa quedará bloqueado hasta que se produzca algún evento. Clic del mouse. Llegada de un mensaje por la red. La Programación Orientada a Aspectos (POA) es un paradigma de programación relativamente reciente.Entre los objetivos que se ha propuesto la POA están, principalmente, el de separar conceptos y el de minimizar las dependencias entre ellos. Con el primer objetivo se persigue que cada decisión se tome en un lugar concreto y no diseminado por la aplicación. Con el segundo, se pretende desacoplar los distintos elementos que intervienen en un programa. Su consecución implicaría las siguientes ventajas:Un código menos enmarañado, más natural y más reducido.Mayor facilidad para razonar sobre los conceptos, ya que están separados y las dependencias entre ellos son mínimas.Un código más fácil de depurar y más fácil de mantener.Se consigue que un conjunto grande de modificaciones en la definición de una materia tenga un impacto mínimo en las otras.Se tiene un código más reusable y que se puede acoplar y desacoplar cuando sea necesario. Valores y tipos Llamaremos valor a algo que pueda se evaluado, almacenado, incorporado a una estructura de datos, pasado como argumento a un procedimiento o función, retornado como resultado de una función etc. En otras palabras, un valor es cualquier entidad que existe durante una computación. Por ejemplo en Pascal encontramos los siguientes valores: Valores primitivos (valores de verdad, caracteres, enumerados, enteros y números reales) Valores compuestos (registros, arreglos, conjuntos y archivos) Punteros Referencias a variables Abstracción de procedimiento y función. Un tipo es un conjunto de valores. Cuando decimos que v es un valor del tipo T, significa simplemente que v ? T. Cuando decimos que una expresión E es del tipo T, significa que el resultado de evaluar la expresión E dará un valor de tipo T. Deben exhibir un comportamiento uniforme bajo operaciones asociadas a ese tipo. Por ejemplo el conjunto {23, verdadero, Lunes} no es un tipo; pero {verdadero, falso} si lo es porque exhibe un comportamiento uniforme bajo las operaciones lógicas de negación, conjunción y disyunción; y {..., -2, -1, 0, 1, 2, ...} también lo es, porque todos sus valores exhiben un comportamiento uniforme bajo las operaciones de suma, multiplicación, etc. Tipos primitivos Los tipos primitivos son aquellos que están compuestos por valores atómicos y por lo tanto no pueden ser descompuestos en valores más simples. Seguiremos la siguiente notación para los tipos primitivos: Valor_de_verdad {verdadero, falso} Entero {..., -2, -1, 0, 1, 2, ...} Real {..., -1.0, ..., 0.0, ..., 1.0, ...} Carácter {..., 'a', 'b', ..., 'z', ...} tipo enumerado. Meses {ene, feb, mar, abr, may, jun, jul, ago, sep, oct, nov, dic} un tipo sub- rango. Por ejemplo el tipo subrango 28..31 tiene los valores {28, 29, 30, 31}. Un punto interesante es la cardinalidad de un conjunto (o de un tipo). Escribiremos #S para signi- ficar el número de valores distintos en S. Por ejemplo: #valor_de_verdad = 2 #meses = 12 #enteros = 2 x maxint + 1 (en Pascal) Tipos compuestos Un tipo compuesto (o tipo de datos estructurado) es un tipo cuyos valores están compuestos o estructurados a partir de valores más simples. Los lenguajes de programación soportan una amplia varie- dad de estructuras de datos: tuplas, registros, arreglos, conjuntos, strings, listas, arboles, archivos se- cuenciales, archivos directos, etc. Producto Cartesiano Un tipo simple de composición de valores es el Producto Cartesiano, donde los valores de dos tipos (posiblemente diferente) son apareados. S x T es el conjunto de todos los pares ordenados de valo- res, donde el primer valor de cada par se toma del conjunto S y el segundo del T. Formalmente: S x T = { (x,y) / x ? S; y ? T} La cardinalidad del producto cartesiano es #(S x T) = #S x #T Entendiéndose por cardinalidad de un tipo a la cantidad de valores del mismo. Podemos tomar como ejemplo de producto cartesiano la definición de un registro: Type Fecha : record m : meses; d : 1..31; end; El tipo Fecha tiene el siguiente conjunto de valores {ene, feb, ..., dic} x {1, 2, 3, ..., 31}. O sea 372 pares de la forma (ene, 1) (ene, 2) ... (feb, 1) ... (dic, 31). Uniones Disjuntas Otro tipo de composición de valores son las uniones disjuntas donde los valores se toman de uno de dos tipos (normalmente diferentes). S + T es el conjunto de valores donde cada valor es tomado ya sea de S o de T y es rotulado (izq o der) para indicar de qué conjunto fue tomado: S + T = { izq x / x ? S} ? {der y / y ? T} La cardinalidad está dada por #(S + T) = #S + #T Type precision =(Exact, Aprox); numero = record Case prec: precision of exact: (valEnt: Integer); aprox: (valReal: Real) end El conjunto de valores de este tipo es Integer x Real. Sus valores son: {..., exact (-2), exact (-1), exact (0), exact (1), exact (2), ...} ? {..., aprox (-1.0), ... aprox (0.0), ... aprox (1.0), ... } Mapeo La noción de mapeo o función de un conjunto a otro es muy importante en los lenguajes de pro- gramación. Consideremos una función m que relaciona cada valor x en S con un valor de T. Los valores de T son llamados imágenes de x bajo m y se escribe m(x). m: S ? T es una función de S en T. Si consideramos a S = {u, v} y T = {a, b, c}. Por ejemplo m(x) = {u ? a, v ? c} puede ser una función definida de S en T. Con la notación S ? T definimos el conjunto de todas las funciones posibles de S en T. S ? T = {m / x ? S ? m(x) ? T} La cardinalidad está dada por #S ? T = (#T)#S Por ejemplo un array puede ser entendido como un mapeo: Array [S] of T Type color = (rojo, verde, azul); Pixel = array [color] of 0..1 El conjunto de valores del tipo arreglo es pixel = color ? {0, 1} donde color = {rojo, verde, azul} Los valores para el tipo pixel está dado por ocho combinaciones. {rojo ? 0, verde ? 0, azul ? 0} {rojo ? 1, verde ? 0, azul ? 0} {rojo ? 0, verde ? 0, azul ? 1} {rojo ? 1, verde ? 0, azul ? 1} {rojo ? 0, verde ? 1, azul ? 0} {rojo ? 1, verde ? 1, azul ? 0} {rojo ? 0, verde ? 1, azul ? 1} {rojo ? 1, verde ? 1, azul ? 1} Function par (n: Integer) : Boolean; Begin Par := (n mod 2 = 0); End; Esta función implementa un mapeo particular definido de Integer ? boolean y sus valores son: {0 ? true, ±1 ? false, ±2 ? true, ±3 ? false, ...} Una función impar, implementará otro mapeo de Integer ? boolean. Si una función recibe n valores como parámetros podemos interpretarlo como un simple argu- mento. Una n-tupla. Conjunto Potencia Consideremos un conjunto de valores denominado S. Estamos interesados en valores que son entre si, subconjuntos de S. El conjunto de todos los subconjuntos se llama Conjunto Potencia de S y se escribe formalmente: ?S = {s / s ? S} Las operaciones básicas a un conjunto son las operaciones usuales de la teoría de conjuntos: pertenencia, inclusión, unión e intersección. Cada valor de S puede ser miembro o no de un conjunto particular en ?S. Y además la cardina- lidad del conjunto potencia de S está dada por: #(?S) = 2#S Por ejemplo, considere la siguiente definición Pascal... Type color = (rojo, verde, azul); ConjPot = set of color El conjunto de valores de este tipo es PoSet = ?color es el conjunto de todos los subconjuntos de Color = {rojo, verde, azul}. Los siguientes 8: { } {rojo} {verde} {azul} {rojo, verde} {rojo, azul} {verde, azul} {rojo, verde, azul} Tipos Recursivos Se considera un tipo recursivo a aquel que se compone de valores del mismo tipo y se define en términos de si mismo. Uno de los tipos recursivos son las listas las cuales pueden tener cualquier número de componen- tes inclusive ninguno. El número de componentes es llamado largo de la lista. Una lista es homogénea si todos los elementos de la misma son del mismo tipo. Supóngase que queremos definir un tipo cuyos valores son listas de enteros. Podemos definir dicha lista de enteros como un valor que puede ser vacío o un par que consiste de un entero (cabeza) y la una lista de enteros (cola). Esta definición es recursiva y puede ser escrita como: Lista_enteros = unit + (Entero x Lista_enteros) La cardinalidad de un tipo recursivo es infinito. Por lo tanto nunca podremos enumerar todos los valores para un tipo recursivo. Control de tipos Agrupar valores en tipos permite al programador describir los datos. Previene además que los programas realicen operaciones sin sentido como por ejemplo multiplicar un carácter por un valor de verdad. En este sentido los lenguajes de alto nivel se distinguen de los de bajo nivel donde los tipos son byte y word. Para prevenir la realización de operaciones sin sentido la implementación de los lenguajes deben realizar una comprobación de tipos sobre los operandos. En un lenguaje tipeado estáticamente, cada variable y parámetro tiene un tipo fijo y es elegi- do por el programador. Por lo tanto el tipo de cada expresión puede ser deducido y la comprobación de tipo se realiza en tiempo de compilación. La mayoría de los lenguajes de alto nivel son estáticamente tipeados. En un lenguaje tipeado dinámicamente, solo los valores tienen un tipo fijo. Una variable o parámetros no tienen un tipo designado, pero pueden tomar valores de diferente tipo en diferentes mo- mentos. Esto implica que el tipo de los operandos deben ser chequeados inmediatamente antes de reali- zar una operación en tiempo de ejecución. Lisp y Smalltalk son lenguajes dinámicamente tipeados. El tipeo dinámico implica que la ejecución de un programa será un poco más lenta debido al con- trol de tipos necesario en tiempo de ejecución y también implica que cada valor debe ser rotulado con su tipo de manera de hacer posible el control de tipos. Esta sobrecarga de tiempo y espacio son evitados en un lenguaje estáticamente tipeado porque todo el control de tipos se hace en tiempo de compilación. Una ventaja importante del tipeo estático es la seguridad de que los errores de tipos están garantizados que serán detectados por el compilador. La ventaja de un tipeo dinámico es su flexibilidad. Equivalencia de tipos Considere una operación que espera un operando del tipo T. Suponga que en realidad el operan- do en cuestión es de tipo T'. El lenguaje debe chequear si el tipo T es equivalente a T' (T ? T'). Equivalencia Estructural: T ? T' si y solo si T y T' tienen el mismo conjunto de valores. Mediante la equivalencia estructural se hará el chequeo de tipos comparando las estructuras de los tipos T y T'. (No es necesario, y en general imposible, enumerar todos sus valores). Las siguientes reglas ilustran como podemos decidir si T ? T', definido en términos de productos cartesiano, uniones disjuntas y mapeos. o Si T y T' son dos tipos primitivos. Luego T ? T' si y solo sí T y T' son idénticos. Ej: Integer ? Integer. o Si T = A x B y T' = A' x B'. Luego T ? T' si y solo sí A ? A' y B ? B'. Ej: Integer x Character ? Integer x Character o Si T = A + B y T' = A' + B'. Luego T ? T' si y solo sí A ? A' y B ? B' o A ? B' y B ? A'. Ej: Integer + Character ? Character + Integer o Si T = A ? B y T' = A' ? B'. Luego T ? T' si y solo sí A ? A' y B ? B'. Ej: Integer ? Character ? Integer ? Character o En otro caso, T no es equivalente a T'. Equivalencia de Nombres T ? T' si y solo si T y T' fueron definidos en el mismo lugar. Por ejemplo, considere la siguiente definición Pascal. type T1 = file of Integer; T2 = file of Integer; var F1: T1; F2: T2; procedure p (var F: T1); begin ... end; La llamada a procedimiento "p (F1)" pasaría la verificación de tipos debido a que los tipos de F y F1 son equivalentes. Sin embargo la llamada "p (F2)" fallaría la verificación de tipos debido a que los tipos F y F2 no son equivalentes; T1 y T2 están definidos en diferentes declaraciones. Principio de completitud de tipos "Las operaciones que se puedan realizar en valores pertenecientes a los tipos no deberían ser ar- bitrarias a los mismos". Este principio debe contribuir a que los lenguajes no posean restricciones sobre las operaciones que pueden aplicarse a determinados tipos y de esa manera reducir el poder de un lenguaje de progra- mación. Sin embargo, una restricción podría justificarse por otra, conflicto, consideraciones de diseño etc. Sistema de tipos Cada constante, variable, resultado de función y parámetro formal, deben declararse con un tipo específico. Este sistema de tipos se denomina monomórfico, y hace que el control de tipos sea sencillo. es insatisfactorio, especialmente para escribir software reusable. Muchos algoritmos estándares (tales como los algoritmos de ordenación) son inherentemente estándares, en el sentido de que solo dependen del tipo de valores que se están manejando. Los conceptos relevantes son sobrecarga, que es la habilidad de un identificador u operador a denotar varias abstracciones simultáneamente; polimor- fismo, que tiene que ver abstracciones que pueden operar uniformemente sobre valores de diferentes tipos y herencia, que se refiere al hecho de que subtipos hereden características de supertipos. Monomorfismo Un sistema de tipos monomórfico es aquel en dónde las constantes, variables, parámetros y re- sultado de función, tienen un único tipo. El sistema de tipos de Pascal es básicamente monomórfico. Sobrecarga significa que un número (pequeño) de abstracciones distintas están asociadas al mismo identificador; estas abstracciones no necesariamente deben tener tipos relacionados, ni realizar necesariamente operaciones similares en sus parámetros. Polimorfismo es una propiedad de una única abstracción que tiene una (amplia) gama de tipos relacionados; la abstracción opera uniformemente sobre sus argumentos cualquiera sea su tipo. Sobrecarga Un identificador u operador se dice que está sobrecargado si denota simultáneamente dos o más funciones distintas. En general, la sobrecarga es aceptable solo cuando cada llamada a función no es ambigua; donde la función a ser llamada puede identificarse unívocamente usando la información de tipos disponible. Ejemplo 1: el operador '-' denota simultáneamente cinco funciones distintas. ? Negación de un entero (una función de Integer ? Integer) ? Negación de un real (una función de Real ? Real) ? Diferencia de enteros (una función de Integer x Integer ? Integer) ? Diferencia de reales (una función de Real x Real ? Real) ? Diferencia de conjuntos (una función de Set x Set ? Set) Existen dos tipos de sobrecarga: ? Sobrecarga independiente del contexto (como en Pascal y ML): requiere que S1 y S2 sean distintos. Considere la llamada a la función I (E). Si el parámetro actual E es del tipo S1, entonces I denota a f1 y el resultado es del tipo T1; si E es del tipo S2, entonces I denota f2 y el resultado será del tipo T2. Con la sobrecarga dependiente del contexto la función que se llama es identificada unívocamente por el parámetro actual. ? Sobrecarga dependiente del contexto (como en Ada): requiere que S1 y S2 sean distintos o que T1 y T2 sean distintos. Si S1 y S2 son distintos, la función a llamar puede identificarse como anteriormen- te. Si S1 y S2 no son distintos, pero T1 y T2 son distintos, el contexto debe tenerse en cuenta para identificar la función que se llamará. Considere la llamada a la función I(E), donde E es del tipo S1 (? S2). Si la llamada a la función ocurre en un contexto donde se espera una expresión del tipo T1, en- tonces I debe denotar a f1; si la llamada a la función ocurre en un contexto donde se espera una ex- presión del tipo T2, entonces I debe denotar f2. Con la sobrecarga dependiente del contexto, es po- sible formular expresiones en las cuales la función a llamar no pueda ser identificada unívocamente pero el lenguaje debe prohibir esas expresiones ambiguas. Polimorfismo En un sistema de tipos polimórfico, podemos escribir abstracciones que operan uniformemente sobre argumentos de una amplia gama de tipos relacionados. Abstracciones polimórficas En ML es simple definir una función polimórfica. La clave es definir el tipo de tales funciones usando tipos variables, en vez de tipos específicos. Ejemplo 1: La siguiente función acepta un par de enteros y retorna su suma: fun sum (x: int, y: int) = x + y Esta función es del tipo Integer x Integer ? Integer. La llamada a la función sum (13, 21) retornará 34. Tipos parametrizados Un tipo parametrizado es un tipo que tiene otro(s) tipo(s) como parámetros. Por ejemplo en Pas- cal el tipo file, set y array. Por ejemplo podemos definir file of char o file of integer. Podemos pensar que file es un tipo parametrizado de la forma file of ?. Coersiones Una coersión es un mapeo implícito entre valores de un tipo a valores de un tipo diferente. Ejem- plos típicos de coersiones son mapeos de enteros a números reales y mapeos de caracteres a strings de un único carácter. Una coersión se realiza automáticamente cuando el contexto lo demanda. Esto es ilustrado por la expresión Pascal sqrt (n), donde la función sqrt espera un argumen- to del tipo real, pero n es de tipo entero. Existe un mapeo obvio de Integer a Real: {..., -2 ? -2.0, -1 ? -1.0, 0 ? 0.0, 1 ? 1.0, 2 ? 2.0, ...} por lo tanto la expresión sqrt (n) es legal. Subtipos y herencia Si consideramos un tipo T como un conjunto de valores, podríamos pensar en construir subcon- juntos de T. Llamaremos a cada subconjunto de T subtipo de T. Asociado con cada tipo T, existen un número de operaciones aplicables a los valores de T. Cada una de estas operaciones también serán aplicables a los valores de cualquier subtipo S de T. Podemos pensar que S hereda todas las operaciones asociadas con T. Expresiones Una expresión es una frase de programa que será evaluada para retornar un valor. Las expresiones pueden formarse de diversas maneras. Las fundamentales son: o Literales o Agregados o Llamadas a funciones o Expresiones condicionales o Accesos a constantes y variables Literales Es la clase más simple de expresión, denota un valor fijo y manifiesto de algún tipo. Por ejemplo: 6356 3.1416 '%' ' CONSULTA' Los cuales denotan un entero, un real, un carácter, y un string respectivamente. Agregados Es una expresión que construye un valor compuesto a partir de sus valores componentes. Los valores componente se determinan al evaluar subexpresiones. Llamadas a funciones Una llamada a una función calcula un resultado al aplicar una abstracción de función a un argu- mento. Una llamada a función normalmente tiene la forma F (pa) donde F determina la función a apli- carse, y los parámetros actuales 'pa' determina los argumentos que le serán pasados. Expresiones condicionales Una expresión condicional tienen varias subexpresiones de las cuales solo una se toma para ser evaluada. No todos los lenguajes proveen expresiones condicionales que no es lo mismo que comandos condicionales. Por ejemplo, el lenguaje C provee una expresión condicional: strNum = (a>0? 'positivo' : 'negativo') Acceso a constantes y variables Un tipo de expresiones tiene que ver con el acceso a constantes y variables mediante sus nom- bres. Por ejemplo: const pi = 3.1416; var r : real; En la expresión 2*pi*r se produce un acceso al valor que posee la constante pi la cual retorna el valor 3.1416 y a la variable r la cual retorna el valor que pueda contener la misma. Variables y Actualizaciones En computación, una variable es un objeto que contiene un valor, este valor puede ser inspeccio- nado y actualizado tanto como se desee. Lo más familiar para un programador son las variables que se crean y se usan en un programa particular, tales variables son típicamente actualizadas por la asignación; y son de vida corta. Sin embargo, archivos y bases de datos son también variables. Estas son generalmente de larga vida, existen independientemente de un programa particular. Un almacén es una colección de celdas. Cada celda tiene un estado actual: reservado o no reservado. Cada celda reservada tiene un contenido actual, que es un valor almacenable o indefinido. Ejemplo: considere la variable n en un programa Pascal. 1. La declaración de la variable (var n: Integer) causa que alguna celda no reservada cambie su estado a reservada, y su contenido cambie a indefinido. 2. La asignación n:= 0 cambia a cero el contenido de la celda denotada por n. 3. La expresión n+1 retorna uno más que el contenido de la celda denotada por n. La asignación n:= n+1 suma uno al contenido de esa celda. 4. Al final del bloque que contiene la declaración de n, se revierte el estado de la celda denotada por n a no reservado. Variables Compuestas El valor de un tipo compuesto consiste de componentes que pueden ser inspeccionado separa- damente. Asimismo, una variable de un tipo compuesto consiste de componentes que son variables tam- bién y el contenido de esos componentes pueden ser inspeccionados y actualizados separadamente. Tiempo de Vida de una Variable El intervalo entre la creación y la eliminación es llamado tiempo de vida de una variable. Variables globales y locales Una variable local es aquella que se declara en un bloque y que se usará solo en dicho bloque (por ejemplo un bloque es el cuerpo de una función o procedimiento en Pascal). Una variable global es aquella que se declara en el bloque más externo de un programa. Variables de pila (montículo) Este tipo de variables pueden ser creadas y borradas en cualquier momento. Son anónimas y se crean con un comando. Son accedidas a través de un puntero. Variables Persistentes Una variable persistente es aquella cuyo tiempo de vida va más allá de la activación de un de- terminado programa Comandos Un comando es una frase de programa que será ejecutada para actualizar variables. Hay varios tipos de comandos Saltos Es un comando que no tiene efecto alguno (skip). Ej if E then C else skip Asignaciones Tienen la típica forma V := E. Actualiza la variable V con el valor retornado por la evaluación de la expresión E. Llamadas a procedimientos Aplica una abstracción de procedimiento a una lista de parámetros. Comandos secuenciales El orden en que se ejecutan los comandos es importantes según se actualizan las varibles. Comandos colaterales El orden en que se ejecutan los comandos no es irrelevante. Ej: m:= 7, n:= n+1. Comandos condicionales Tiene un número de subcomandos de los cuales exactamente uno será elegido para ejecutarse. El típico comando es el if. (case) Comandos iterativos También conocido como loop. Tiene un grupo de subcomandos que se ejecutarán repetidamente con un tipo de frase que determina cuando terminará la iteración. (for, repeat, while) Enlace Un concepto común a todos los lenguajes de programación es la habilidad del programador para enlazar o relacionar identificadores con entidades tales como constantes, variables, procedimientos, fun- ciones y tipos. La buena elección de identificadores ayuda a hacer que los programas sean más compren- sibles y fáciles de interpretar. Más aún, relacionar un identificador con una entidad en un lugar y luego utilizar ese identificador para hacer referencia a esa entidad en otros lugares, hace que los programas sean más flexibles. Enlace y ámbitos Podemos decir que una declaración produce una asociación o un enlace entre el identificador declarado y la entidad que denotará. Un entorno o ámbito es un conjunto de enlaces. Alcance En general cada declaración tiene un cierto alcance, que tiene que ver con la porción del programa sobre el cual al declaración es efectiva. Estructura de bloque Un bloque es una frase del programa que delimita el alcance de cualquier declaración que puede contener La estructura de bloques más popular es la anidada donde cada bloque puede ser anidado en otro bloque ? Los bloques pueden ser abstracciones de procedimiento y función pero también pueden ser bloques de comandos. ? Un concepto aún más potente es el de expresiones de bloque. Es una expresión que es evaluada para producir un enlace con un identificador que se usará solo en el bloque donde se define. Alcance y visibilidad Los identificadores pueden aparecer en dos contextos diferentes. Llamaremos ocurrencia de enlace al punto en donde un identificador se declara, y llamaremos ocurrencia de aplicación a cada apa- rición del identificador cuando denota a la entidad a la cual fue enlazado. Por ejemplo: La aparición de n en const n = 7 es una ocurrencia de enlace, en donde n se enlaza al 7. Las apariciones subsecuentes de n en la expresión n * (n+1) son ocurrencias de aplicación, en donde n denota al 7. Enlace estático y dinámico La terminología de enlace estático y dinámico tiene que ver con el momento en que determina- mos que ocurrencia de enlace del identificador I se corresponde con la ocurrencia de aplicación de I. Con enlace estático podemos hacer esto en tiempo de compilación. Con enlace dinámico debemos retardarlo hasta el tiempo de ejecución. Con el enlace estático podemos determinar que ocurrencia de enlace de I se corresponde con una ocurrencia de aplicación de I dada, solo con examinar el código del programa, encontrando el bloque más pequeño que contiene una ocurrencia de aplicación de I que también contiene una ocurrencia de enlace de I. La asociación entre la ocurrencia de aplicación y enlace es fija. Con enlace dinámico la ocurrencia de enlace de I que se corresponde con una ocurrencia de apli- cación de I depende del flujo de control dinámico del programa. La entidad denotada por I es la declara- ción elaborada más recientemente de I dentro del bloque activo actual. Abstracciones Abstracción es un modo de pensamiento en el cual nos concentramos en las ideas generales más que en las manifestaciones específicas de estas ideas En programación, la abstracción alude a la distinción entre (a) qué hace una parte de un progra- ma y (b) cómo está implementado. Cuando se llama a un procedimiento nos concentramos sólo en qué hace dicho procedimiento; sólo cuando escribimos un pro- cedimiento nos interesará el cómo implementarlo. Tipos de abstracción Definiremos una abstracción como una entidad que engloba una computación. Abstracción de función Una abstracción de función engloba una expresión a evaluarse, y cuando es llamada retorna un valor como resultado. El usuario de la abstracción observa solo su resultado, no los pasos por los cuales se evalúa la función. Una abstracción de función es construida a partir de una definición de función: Function I (fp1; ... ; fpn) : T; B Abstracción de procedimiento Una abstracción de procedimiento engloba un comando a ejecutarse, y cuando es llamado actua- lizará variables. El usuario de la abstracción de procedimiento observa solo esas actualizaciones y no lo pasos por los cuales fueron efectuados Una abstracción de procedimiento es construido en Pascal, a partir de una definición de procedi- miento: Procedure I (fp1; ... ; fpn); B El principio de abstracción Como un resumen podemos decir: ? Una abstracción de función es una abstracción sobre una expresión. Quiere decir que una abstracción de función tiene un cuerpo que es una expresión, y una llamada a la función es una expresión que retornará un valor al evaluar el cuerpo de la abstracción de función. ? Una abstracción de procedimiento es una abstracción sobre un comando. Quiere decir que una abs- tracción de procedimiento tiene un cuerpo que es un comando, y una llamada a procedimiento es un comando que actualizará variables al ejecutar el cuerpo de la abstracción de procedimiento. Es posible construir abstracciones sobre cualquier clase sintáctica, con tal que las frases de esa clase especifiquen algún tipo de computación. ? Una abstracción de selección es una abstracción sobre el acceso a variable. Quiere decir que una abstracción de selección tiene un cuerpo que es un acceso a variable, y una llamada al selector es un acceso a variable que retornará una referencia a una variable al evaluar el cuerpo de la abstracción de selección. Parámetros Para aprovechar la potencia del concepto de abstracción, necesitamos abstracciones parametrizadas respecto a los valores con que opera. Un identificador que se usa en una abstracción para denotar un argumento se denomina pa- rámetro formal. Una expresión o frase que se pasa como argumento es denominado parámetro ac- tual por ejemplo 1.0 o a+b en las llamadas circunf (1.0) y cicunf (a+b) respectivamente. Un argumento es el valor que puede pasarse a una abstracción Mecanismo de copia Un mecanismo de copia permite que valores se copien a y/o desde una abstracción cuando se la llama. El parámetro formal X denota una variable local para la abstracción. Un valor se copia en X a la entrada de la abstracción, y/o se copia de X (a una variable no local) a la salida de la abstracción. Debido a que X es una variable local, se crea a la entrada de la abstracción y se elimina a la salida. Un parámetro por valor es una variable local X que se crea a la entrada de la abstracción y se le asigna el valor del argumento. Debido a que X se comporta como una variable local, su valor puede ser inspeccionado y actualizado. Sin embargo cualquier actualización de X no tiene efecto en ninguna varia- ble no local. Un parámetro resultado es todo lo contrario del anterior. En este caso, el argumento debe ser una referencia a una variable. De nuevo una variable local X se crea, pero su valor inicial es indefinido. A la salida de la abstracción el valor final de X es asignado a la variable argumento. Estos dos mecanismos pueden ser combinados para dar resultado a los parámetros valor- resultado. El argumento, de nuevo, debe ser una referencia a variable. En la entrada de la abstracción, la variable local X se crea y se le asigna el valor actual de la variable argumento. A la salida, el valor final de X se asigna nuevamente a la variable argumento. Mecanismo por definición Este mecanismo permite que el parámetro formal X se enlace directamente al argumento. Esto da una semántica simple y uniforme para el paso de parámetros de cualquier valor en el lenguaje de programación (no solo los valores de primera clase). ? En el caso de un parámetro constante, el argumento es un valor (de primera clase). X se enlaza al valor del argumento durante la activación de la llamada a la abstracción. ? En el caso de un parámetro variable (o por referencia), el argumento es una referencia a una varia- ble. X se enlaza a la variable argumento durante la activación de la llamada a la abstracción. Por lo tanto cualquier actualización o inspección de X es realmente una actualización o inspección del argu- mento. ? En el caso de un parámetro procedural, el argumento es una abstracción de procedimiento. X se enlaza al procedimiento (argumento) durante la activación de la llamada a la abstracción. Por lo tanto cualquier llamada a X es realmente una llamada al procedimiento (argumento). ? En el caso se un parámetro funcional, el argumento es una abstracción de función. X se enlaza a la función (argumento) durante la activación de la llamada a la abstracción. Por lo tanto cualquier lla- mada a X es realmente una llamada a la función (argumento). Una desventaja de los parámetros variable es la posibilidad de crear alias. Esto ocurre cuando dos o más identificadores son simultáneamente enlazados a la misma variable. Esto tiende a hacer que los programas sean más difíciles de entender. Orden de Evaluación El orden de evaluación se refiere exactamente al momento en que cada parámetro actual se eva- lúa cuando se llama a una abstracción. Existen básicamente dos posibilidades: ? Evaluar el parámetro actual en el punto de la llamada. ? Retardar su evaluación hasta que el argumento realmente se usa. El primer orden de evaluación se denomina "Evaluación Impaciente" (o evaluación en orden aplicativo). Se evalúa el parámetro actual una sola vez, y en efecto se sustituye el resultado en cada ocurrencia del parámetro formal. El segundo orden de evaluación se denomina "Evaluación en orden normal". No se evalúa inmediatamente el parámetro actual, sino que se sustituye el parámetro actual por cada ocurrencia del parámetro formal. La función sqr se dice que es estricta, lo cual significa que una llamada a esta función puede evaluarse solo si sus argumentos pueden ser evaluados. La función cand se dice que es no estricta en su segundo argumento, lo cual significa que una llamada a esta función puede a veces evaluarse aún cuando su segundo argumento pueda no ser evaluado. Este evaluación se denomina perezosa (lazy evaluation); el argumento se evalúa solo cuando se la necesita por primera vez (que podría ser nunca si la función es no restricta). Un paradigma está constituido por los supuestos teóricos generales, las leyes y las técnicas para su aplicación que adoptan los miembros de una determinada comunidad científica. Es un modelo o esquema fundamental que organiza nuestras opiniones con respecto a algún tema en particular. Los paradigmas establecen límites, para resolver problemas dentro de estos, y de esta forma mejorar o proporcionar nuevas soluciones, ya que estos filtran experiencias, se ajustan a los límites, percepciones o creencias. Paradigmas de Programación Representan un enfoque particular o filosofía para la construcción del software. El paradigma imperativo es considerado el más común y está representado, por ejemplo, C, Pascal, COBOL. El paradigma orientado a objetos. Un lenguaje completamente orientado a objetos es Smalltalk. El paradigma funcional está representado por la familia de lenguajes LISP. Otro podría se ser Haskell. El paradigma lógico, un ejemplo es PROLOG. Paradigma Imperativo Fortran introdujo las expresiones simbólicas y subprogramas con parámetros. COBOL introdujo el concepto de descripción de datos. El Algol-60 introdujo el concepto de estructura de bloques, variables, procedimientos, etc. Influenció a numerosos lenguajes posteriores tan fuertemente que fueron llamados lenguajes estilo Algol. Pascal fue el lenguaje estilo Algol que se hizo más popular porque es simple, sistemático e implementado eficientemente. Describe la programación en términos del estado del programa y sentencias que cambian dicho estado. Los programas imperativos son un conjunto de instrucciones que le indican al computador cómo realizar una tarea. Las recetas y las listas de revisión de procesos, a pesar de no ser programas de computadora, son también conceptos familiares similares en estilo a la programación imperativa; cada paso es una instrucción. La programación imperativa recibe este nombre porque está basada en comandos que actualizan variables contenidas en almacenamientos. Tiene estrecha relación para modelar el mundo real. Se caracteriza esencialmente porque las instrucciones que lo componen se ejecutan secuencialmente en un orden preestablecido. La unidad base de ejecución es el programa o conjunto de instrucciones ejecutables, que se divide en una serie de módulos o rutinas distribuidos de acuerdo con una organización jerárquica. En este tipo de programación los datos están desorganizados, son meros apéndices de los programas y tan solo proporcionan valores que sirven para realizar cálculos. Uno de los programas situados en la raíz de la jerarquía recibe el nombre de programa principal y los demás se conocen con el nombre de subprogramas, subrutinas, funciones o procedimientos. En cuanto a los datos, dependiendo del lenguaje que se trate pueden ser globales, accesibles por todos los programas de la jerarquía, o locales, utilizables solo por el programa al que pertenece. Dentro de este tipo de programación podemos encontrar dos divisiones: programación estructurada o programación sin GOTO: presenta bastantes ventajas en cuanto a la facilidad de modularización, documentación y mantenimiento de los programas; programación no estructurada que permiten realizar saltos incondicionales en la ejecución del programa mediante instrucciones GOTO. Paradigma Orientado a Objetos Es el paradigma que está tomando mayor auge en los últimos años. La programación orientada a objetos deriva de conceptos introducidos por Simula, otro lenguaje del estilo Algol. Smalltalk está basado en clases de objetos, un objeto viene a ser como una variable que puede accederse sólo a través de operaciones asociadas con él. Los objetos que son entidades que combinan estado (es decir, datos) y comportamiento (esto es, procedimientos o métodos). La programación orientada a objetos expresa un programa como un conjunto de estos objetos, que se comunican entre ellos para realizar tareas. Lenguajes procedurales: escriben funciones y después les pasan datos. Lenguajes orientados a objetos definen objetos con datos y métodos y después envían mensajes a los objetos diciendo que realicen esos métodos en sí mismos. Paradigma Funcional Están basados en el cálculo lambda (o ?-cálculo), de Alonso Church. LISP fue el primer lenguaje basado enteramente en el Cálculo Lambda. Lisp en su forma pura, está basado enteramente en funciones sobre listas y árboles. Los lenguajes funcionales modernos, tratan a las funciones como valores de primera clase e incorporan también un sistema de tipos avanzado. La secuencia de computaciones llevadas a cabo por el programa se regiría única y exclusivamente por la reescritura de definiciones más amplias a otras cada vez más concretas y definidas. Los programas escritos en un lenguaje funcional están constituidos únicamente por definiciones de funciones Se verifican ciertas propiedades como la transparencia referencial (el significado de una expresión depende únicamente del significado de sus subexpresiones). No existe asignaciones de variables. Falta de construcciones estructuradas como la secuencia o la iteración (solo recursión) Entre los lenguajes funcionales puros: Haskell Miranda Los lenguajes funcionales híbridos: Lisp Scheme Ocaml Standard ML (estos dos últimos, descendientes del lenguaje ML). Paradigma logico Un lenguaje de programación lógica está basado en un subconjunto de la lógica matemática. La computadora es programada para inferir relaciones entre valores más que calcular valores de salida a partir de valores de entrada. PROLOG hizo a la programación lógica popular y es más bien débil e ineficiente, sin embargo fue modificado para agregarle características no lógicas para hacerlo más usable como lenguaje de programación. La mayoría de estos lenguajes se basan en la lógica de predicados. Se definen propiedades de los objetos del dominio de referencia y relaciones entre ellos a través de fórmulas, las cuales usan normalmente el conector implicación. Paradigma Orientado a Eventos La programación dirigida por eventos es un paradigma de programación en el que tanto la estructura como la ejecución de los programas van determinados por los sucesos que ocurran en el sistema o que ellos mismos provoquen. Será el propio usuario -o lo que sea que esté accionando el programa- el que dirija el flujo del mismo. Se llevarán a cabo las inicializaciones y demás código inicial y a continuación el programa quedará bloqueado hasta que se produzca algún evento. Clic del mouse. Llegada de un mensaje por la red. La Programación Orientada a Aspectos (POA) es un paradigma de programación relativamente reciente.Entre los objetivos que se ha propuesto la POA están, principalmente, el de separar conceptos y el de minimizar las dependencias entre ellos. Con el primer objetivo se persigue que cada decisión se tome en un lugar concreto y no diseminado por la aplicación. Con el segundo, se pretende desacoplar los distintos elementos que intervienen en un programa. Su consecución implicaría las siguientes ventajas:Un código menos enmarañado, más natural y más reducido.Mayor facilidad para razonar sobre los conceptos, ya que están separados y las dependencias entre ellos son mínimas.Un código más fácil de depurar y más fácil de mantener.Se consigue que un conjunto grande de modificaciones en la definición de una materia tenga un impacto mínimo en las otras.Se tiene un código más reusable y que se puede acoplar y desacoplar cuando sea necesario. Valores y tipos Llamaremos valor a algo que pueda se evaluado, almacenado, incorporado a una estructura de datos, pasado como argumento a un procedimiento o función, retornado como resultado de una función etc. En otras palabras, un valor es cualquier entidad que existe durante una computación. Por ejemplo en Pascal encontramos los siguientes valores: Valores primitivos (valores de verdad, caracteres, enumerados, enteros y números reales) Valores compuestos (registros, arreglos, conjuntos y archivos) Punteros Referencias a variables Abstracción de procedimiento y función. Un tipo es un conjunto de valores. Cuando decimos que v es un valor del tipo T, significa simplemente que v ? T. Cuando decimos que una expresión E es del tipo T, significa que el resultado de evaluar la expresión E dará un valor de tipo T. Deben exhibir un comportamiento uniforme bajo operaciones asociadas a ese tipo. Por ejemplo el conjunto {23, verdadero, Lunes} no es un tipo; pero {verdadero, falso} si lo es porque exhibe un comportamiento uniforme bajo las operaciones lógicas de negación, conjunción y disyunción; y {..., -2, -1, 0, 1, 2, ...} también lo es, porque todos sus valores exhiben un comportamiento uniforme bajo las operaciones de suma, multiplicación, etc. Tipos primitivos Los tipos primitivos son aquellos que están compuestos por valores atómicos y por lo tanto no pueden ser descompuestos en valores más simples. Seguiremos la siguiente notación para los tipos primitivos: Valor_de_verdad {verdadero, falso} Entero {..., -2, -1, 0, 1, 2, ...} Real {..., -1.0, ..., 0.0, ..., 1.0, ...} Carácter {..., 'a', 'b', ..., 'z', ...} tipo enumerado. Meses {ene, feb, mar, abr, may, jun, jul, ago, sep, oct, nov, dic} un tipo sub- rango. Por ejemplo el tipo subrango 28..31 tiene los valores {28, 29, 30, 31}. Un punto interesante es la cardinalidad de un conjunto (o de un tipo). Escribiremos #S para signi- ficar el número de valores distintos en S. Por ejemplo: #valor_de_verdad = 2 #meses = 12 #enteros = 2 x maxint + 1 (en Pascal) Tipos compuestos Un tipo compuesto (o tipo de datos estructurado) es un tipo cuyos valores están compuestos o estructurados a partir de valores más simples. Los lenguajes de programación soportan una amplia varie- dad de estructuras de datos: tuplas, registros, arreglos, conjuntos, strings, listas, arboles, archivos se- cuenciales, archivos directos, etc. Producto Cartesiano Un tipo simple de composición de valores es el Producto Cartesiano, donde los valores de dos tipos (posiblemente diferente) son apareados. S x T es el conjunto de todos los pares ordenados de valo- res, donde el primer valor de cada par se toma del conjunto S y el segundo del T. Formalmente: S x T = { (x,y) / x ? S; y ? T} La cardinalidad del producto cartesiano es #(S x T) = #S x #T Entendiéndose por cardinalidad de un tipo a la cantidad de valores del mismo. Podemos tomar como ejemplo de producto cartesiano la definición de un registro: Type Fecha : record m : meses; d : 1..31; end; El tipo Fecha tiene el siguiente conjunto de valores {ene, feb, ..., dic} x {1, 2, 3, ..., 31}. O sea 372 pares de la forma (ene, 1) (ene, 2) ... (feb, 1) ... (dic, 31). Uniones Disjuntas Otro tipo de composición de valores son las uniones disjuntas donde los valores se toman de uno de dos tipos (normalmente diferentes). S + T es el conjunto de valores donde cada valor es tomado ya sea de S o de T y es rotulado (izq o der) para indicar de qué conjunto fue tomado: S + T = { izq x / x ? S} ? {der y / y ? T} La cardinalidad está dada por #(S + T) = #S + #T Type precision =(Exact, Aprox); numero = record Case prec: precision of exact: (valEnt: Integer); aprox: (valReal: Real) end El conjunto de valores de este tipo es Integer x Real. Sus valores son: {..., exact (-2), exact (-1), exact (0), exact (1), exact (2), ...} ? {..., aprox (-1.0), ... aprox (0.0), ... aprox (1.0), ... } Mapeo La noción de mapeo o función de un conjunto a otro es muy importante en los lenguajes de pro- gramación. Consideremos una función m que relaciona cada valor x en S con un valor de T. Los valores de T son llamados imágenes de x bajo m y se escribe m(x). m: S ? T es una función de S en T. Si consideramos a S = {u, v} y T = {a, b, c}. Por ejemplo m(x) = {u ? a, v ? c} puede ser una función definida de S en T. Con la notación S ? T definimos el conjunto de todas las funciones posibles de S en T. S ? T = {m / x ? S ? m(x) ? T} La cardinalidad está dada por #S ? T = (#T)#S Por ejemplo un array puede ser entendido como un mapeo: Array [S] of T Type color = (rojo, verde, azul); Pixel = array [color] of 0..1 El conjunto de valores del tipo arreglo es pixel = color ? {0, 1} donde color = {rojo, verde, azul} Los valores para el tipo pixel está dado por ocho combinaciones. {rojo ? 0, verde ? 0, azul ? 0} {rojo ? 1, verde ? 0, azul ? 0} {rojo ? 0, verde ? 0, azul ? 1} {rojo ? 1, verde ? 0, azul ? 1} {rojo ? 0, verde ? 1, azul ? 0} {rojo ? 1, verde ? 1, azul ? 0} {rojo ? 0, verde ? 1, azul ? 1} {rojo ? 1, verde ? 1, azul ? 1} Function par (n: Integer) : Boolean; Begin Par := (n mod 2 = 0); End; Esta función implementa un mapeo particular definido de Integer ? boolean y sus valores son: {0 ? true, ±1 ? false, ±2 ? true, ±3 ? false, ...} Una función impar, implementará otro mapeo de Integer ? boolean. Si una función recibe n valores como parámetros podemos interpretarlo como un simple argu- mento. Una n-tupla. Conjunto Potencia Consideremos un conjunto de valores denominado S. Estamos interesados en valores que son entre si, subconjuntos de S. El conjunto de todos los subconjuntos se llama Conjunto Potencia de S y se escribe formalmente: ?S = {s / s ? S} Las operaciones básicas a un conjunto son las operaciones usuales de la teoría de conjuntos: pertenencia, inclusión, unión e intersección. Cada valor de S puede ser miembro o no de un conjunto particular en ?S. Y además la cardina- lidad del conjunto potencia de S está dada por: #(?S) = 2#S Por ejemplo, considere la siguiente definición Pascal... Type color = (rojo, verde, azul); ConjPot = set of color El conjunto de valores de este tipo es PoSet = ?color es el conjunto de todos los subconjuntos de Color = {rojo, verde, azul}. Los siguientes 8: { } {rojo} {verde} {azul} {rojo, verde} {rojo, azul} {verde, azul} {rojo, verde, azul} Tipos Recursivos Se considera un tipo recursivo a aquel que se compone de valores del mismo tipo y se define en términos de si mismo. Uno de los tipos recursivos son las listas las cuales pueden tener cualquier número de componen- tes inclusive ninguno. El número de componentes es llamado largo de la lista. Una lista es homogénea si todos los elementos de la misma son del mismo tipo. Supóngase que queremos definir un tipo cuyos valores son listas de enteros. Podemos definir dicha lista de enteros como un valor que puede ser vacío o un par que consiste de un entero (cabeza) y la una lista de enteros (cola). Esta definición es recursiva y puede ser escrita como: Lista_enteros = unit + (Entero x Lista_enteros) La cardinalidad de un tipo recursivo es infinito. Por lo tanto nunca podremos enumerar todos los valores para un tipo recursivo. Control de tipos Agrupar valores en tipos permite al programador describir los datos. Previene además que los programas realicen operaciones sin sentido como por ejemplo multiplicar un carácter por un valor de verdad. En este sentido los lenguajes de alto nivel se distinguen de los de bajo nivel donde los tipos son byte y word. Para prevenir la realización de operaciones sin sentido la implementación de los lenguajes deben realizar una comprobación de tipos sobre los operandos. En un lenguaje tipeado estáticamente, cada variable y parámetro tiene un tipo fijo y es elegi- do por el programador. Por lo tanto el tipo de cada expresión puede ser deducido y la comprobación de tipo se realiza en tiempo de compilación. La mayoría de los lenguajes de alto nivel son estáticamente tipeados. En un lenguaje tipeado dinámicamente, solo los valores tienen un tipo fijo. Una variable o parámetros no tienen un tipo designado, pero pueden tomar valores de diferente tipo en diferentes mo- mentos. Esto implica que el tipo de los operandos deben ser chequeados inmediatamente antes de reali- zar una operación en tiempo de ejecución. Lisp y Smalltalk son lenguajes dinámicamente tipeados. El tipeo dinámico implica que la ejecución de un programa será un poco más lenta debido al con- trol de tipos necesario en tiempo de ejecución y también implica que cada valor debe ser rotulado con su tipo de manera de hacer posible el control de tipos. Esta sobrecarga de tiempo y espacio son evitados en un lenguaje estáticamente tipeado porque todo el control de tipos se hace en tiempo de compilación. Una ventaja importante del tipeo estático es la seguridad de que los errores de tipos están garantizados que serán detectados por el compilador. La ventaja de un tipeo dinámico es su flexibilidad. Equivalencia de tipos Considere una operación que espera un operando del tipo T. Suponga que en realidad el operan- do en cuestión es de tipo T'. El lenguaje debe chequear si el tipo T es equivalente a T' (T ? T'). Equivalencia Estructural: T ? T' si y solo si T y T' tienen el mismo conjunto de valores. Mediante la equivalencia estructural se hará el chequeo de tipos comparando las estructuras de los tipos T y T'. (No es necesario, y en general imposible, enumerar todos sus valores). Las siguientes reglas ilustran como podemos decidir si T ? T', definido en términos de productos cartesiano, uniones disjuntas y mapeos. o Si T y T' son dos tipos primitivos. Luego T ? T' si y solo sí T y T' son idénticos. Ej: Integer ? Integer. o Si T = A x B y T' = A' x B'. Luego T ? T' si y solo sí A ? A' y B ? B'. Ej: Integer x Character ? Integer x Character o Si T = A + B y T' = A' + B'. Luego T ? T' si y solo sí A ? A' y B ? B' o A ? B' y B ? A'. Ej: Integer + Character ? Character + Integer o Si T = A ? B y T' = A' ? B'. Luego T ? T' si y solo sí A ? A' y B ? B'. Ej: Integer ? Character ? Integer ? Character o En otro caso, T no es equivalente a T'. Equivalencia de Nombres T ? T' si y solo si T y T' fueron definidos en el mismo lugar. Por ejemplo, considere la siguiente definición Pascal. type T1 = file of Integer; T2 = file of Integer; var F1: T1; F2: T2; procedure p (var F: T1); begin ... end; La llamada a procedimiento "p (F1)" pasaría la verificación de tipos debido a que los tipos de F y F1 son equivalentes. Sin embargo la llamada "p (F2)" fallaría la verificación de tipos debido a que los tipos F y F2 no son equivalentes; T1 y T2 están definidos en diferentes declaraciones. Principio de completitud de tipos "Las operaciones que se puedan realizar en valores pertenecientes a los tipos no deberían ser ar- bitrarias a los mismos". Este principio debe contribuir a que los lenguajes no posean restricciones sobre las operaciones que pueden aplicarse a determinados tipos y de esa manera reducir el poder de un lenguaje de progra- mación. Sin embargo, una restricción podría justificarse por otra, conflicto, consideraciones de diseño etc. Sistema de tipos Cada constante, variable, resultado de función y parámetro formal, deben declararse con un tipo específico. Este sistema de tipos se denomina monomórfico, y hace que el control de tipos sea sencillo. es insatisfactorio, especialmente para escribir software reusable. Muchos algoritmos estándares (tales como los algoritmos de ordenación) son inherentemente estándares, en el sentido de que solo dependen del tipo de valores que se están manejando. Los conceptos relevantes son sobrecarga, que es la habilidad de un identificador u operador a denotar varias abstracciones simultáneamente; polimor- fismo, que tiene que ver abstracciones que pueden operar uniformemente sobre valores de diferentes tipos y herencia, que se refiere al hecho de que subtipos hereden características de supertipos. Monomorfismo Un sistema de tipos monomórfico es aquel en dónde las constantes, variables, parámetros y re- sultado de función, tienen un único tipo. El sistema de tipos de Pascal es básicamente monomórfico. Sobrecarga significa que un número (pequeño) de abstracciones distintas están asociadas al mismo identificador; estas abstracciones no necesariamente deben tener tipos relacionados, ni realizar necesariamente operaciones similares en sus parámetros. Polimorfismo es una propiedad de una única abstracción que tiene una (amplia) gama de tipos relacionados; la abstracción opera uniformemente sobre sus argumentos cualquiera sea su tipo. Sobrecarga Un identificador u operador se dice que está sobrecargado si denota simultáneamente dos o más funciones distintas. En general, la sobrecarga es aceptable solo cuando cada llamada a función no es ambigua; donde la función a ser llamada puede identificarse unívocamente usando la información de tipos disponible. Ejemplo 1: el operador '-' denota simultáneamente cinco funciones distintas. ? Negación de un entero (una función de Integer ? Integer) ? Negación de un real (una función de Real ? Real) ? Diferencia de enteros (una función de Integer x Integer ? Integer) ? Diferencia de reales (una función de Real x Real ? Real) ? Diferencia de conjuntos (una función de Set x Set ? Set) Existen dos tipos de sobrecarga: ? Sobrecarga independiente del contexto (como en Pascal y ML): requiere que S1 y S2 sean distintos. Considere la llamada a la función I (E). Si el parámetro actual E es del tipo S1, entonces I denota a f1 y el resultado es del tipo T1; si E es del tipo S2, entonces I denota f2 y el resultado será del tipo T2. Con la sobrecarga dependiente del contexto la función que se llama es identificada unívocamente por el parámetro actual. ? Sobrecarga dependiente del contexto (como en Ada): requiere que S1 y S2 sean distintos o que T1 y T2 sean distintos. Si S1 y S2 son distintos, la función a llamar puede identificarse como anteriormen- te. Si S1 y S2 no son distintos, pero T1 y T2 son distintos, el contexto debe tenerse en cuenta para identificar la función que se llamará. Considere la llamada a la función I(E), donde E es del tipo S1 (? S2). Si la llamada a la función ocurre en un contexto donde se espera una expresión del tipo T1, en- tonces I debe denotar a f1; si la llamada a la función ocurre en un contexto donde se espera una ex- presión del tipo T2, entonces I debe denotar f2. Con la sobrecarga dependiente del contexto, es po- sible formular expresiones en las cuales la función a llamar no pueda ser identificada unívocamente pero el lenguaje debe prohibir esas expresiones ambiguas. Polimorfismo En un sistema de tipos polimórfico, podemos escribir abstracciones que operan uniformemente sobre argumentos de una amplia gama de tipos relacionados. Abstracciones polimórficas En ML es simple definir una función polimórfica. La clave es definir el tipo de tales funciones usando tipos variables, en vez de tipos específicos. Ejemplo 1: La siguiente función acepta un par de enteros y retorna su suma: fun sum (x: int, y: int) = x + y Esta función es del tipo Integer x Integer ? Integer. La llamada a la función sum (13, 21) retornará 34. Tipos parametrizados Un tipo parametrizado es un tipo que tiene otro(s) tipo(s) como parámetros. Por ejemplo en Pas- cal el tipo file, set y array. Por ejemplo podemos definir file of char o file of integer. Podemos pensar que file es un tipo parametrizado de la forma file of ?. Coersiones Una coersión es un mapeo implícito entre valores de un tipo a valores de un tipo diferente. Ejem- plos típicos de coersiones son mapeos de enteros a números reales y mapeos de caracteres a strings de un único carácter. Una coersión se realiza automáticamente cuando el contexto lo demanda. Esto es ilustrado por la expresión Pascal sqrt (n), donde la función sqrt espera un argumen- to del tipo real, pero n es de tipo entero. Existe un mapeo obvio de Integer a Real: {..., -2 ? -2.0, -1 ? -1.0, 0 ? 0.0, 1 ? 1.0, 2 ? 2.0, ...} por lo tanto la expresión sqrt (n) es legal. Subtipos y herencia Si consideramos un tipo T como un conjunto de valores, podríamos pensar en construir subcon- juntos de T. Llamaremos a cada subconjunto de T subtipo de T. Asociado con cada tipo T, existen un número de operaciones aplicables a los valores de T. Cada una de estas operaciones también serán aplicables a los valores de cualquier subtipo S de T. Podemos pensar que S hereda todas las operaciones asociadas con T. Expresiones Una expresión es una frase de programa que será evaluada para retornar un valor. Las expresiones pueden formarse de diversas maneras. Las fundamentales son: o Literales o Agregados o Llamadas a funciones o Expresiones condicionales o Accesos a constantes y variables Literales Es la clase más simple de expresión, denota un valor fijo y manifiesto de algún tipo. Por ejemplo: 6356 3.1416 '%' ' CONSULTA' Los cuales denotan un entero, un real, un carácter, y un string respectivamente. Agregados Es una expresión que construye un valor compuesto a partir de sus valores componentes. Los valores componente se determinan al evaluar subexpresiones. Llamadas a funciones Una llamada a una función calcula un resultado al aplicar una abstracción de función a un argu- mento. Una llamada a función normalmente tiene la forma F (pa) donde F determina la función a apli- carse, y los parámetros actuales 'pa' determina los argumentos que le serán pasados. Expresiones condicionales Una expresión condicional tienen varias subexpresiones de las cuales solo una se toma para ser evaluada. No todos los lenguajes proveen expresiones condicionales que no es lo mismo que comandos condicionales. Por ejemplo, el lenguaje C provee una expresión condicional: strNum = (a>0? 'positivo' : 'negativo') Acceso a constantes y variables Un tipo de expresiones tiene que ver con el acceso a constantes y variables mediante sus nom- bres. Por ejemplo: const pi = 3.1416; var r : real; En la expresión 2*pi*r se produce un acceso al valor que posee la constante pi la cual retorna el valor 3.1416 y a la variable r la cual retorna el valor que pueda contener la misma. Variables y Actualizaciones En computación, una variable es un objeto que contiene un valor, este valor puede ser inspeccio- nado y actualizado tanto como se desee. Lo más familiar para un programador son las variables que se crean y se usan en un programa particular, tales variables son típicamente actualizadas por la asignación; y son de vida corta. Sin embargo, archivos y bases de datos son también variables. Estas son generalmente de larga vida, existen independientemente de un programa particular. Un almacén es una colección de celdas. Cada celda tiene un estado actual: reservado o no reservado. Cada celda reservada tiene un contenido actual, que es un valor almacenable o indefinido. Ejemplo: considere la variable n en un programa Pascal. 1. La declaración de la variable (var n: Integer) causa que alguna celda no reservada cambie su estado a reservada, y su contenido cambie a indefinido. 2. La asignación n:= 0 cambia a cero el contenido de la celda denotada por n. 3. La expresión n+1 retorna uno más que el contenido de la celda denotada por n. La asignación n:= n+1 suma uno al contenido de esa celda. 4. Al final del bloque que contiene la declaración de n, se revierte el estado de la celda denotada por n a no reservado. Variables Compuestas El valor de un tipo compuesto consiste de componentes que pueden ser inspeccionado separa- damente. Asimismo, una variable de un tipo compuesto consiste de componentes que son variables tam- bién y el contenido de esos componentes pueden ser inspeccionados y actualizados separadamente. Tiempo de Vida de una Variable El intervalo entre la creación y la eliminación es llamado tiempo de vida de una variable. Variables globales y locales Una variable local es aquella que se declara en un bloque y que se usará solo en dicho bloque (por ejemplo un bloque es el cuerpo de una función o procedimiento en Pascal). Una variable global es aquella que se declara en el bloque más externo de un programa. Variables de pila (montículo) Este tipo de variables pueden ser creadas y borradas en cualquier momento. Son anónimas y se crean con un comando. Son accedidas a través de un puntero. Variables Persistentes Una variable persistente es aquella cuyo tiempo de vida va más allá de la activación de un de- terminado programa Comandos Un comando es una frase de programa que será ejecutada para actualizar variables. Hay varios tipos de comandos Saltos Es un comando que no tiene efecto alguno (skip). Ej if E then C else skip Asignaciones Tienen la típica forma V := E. Actualiza la variable V con el valor retornado por la evaluación de la expresión E. Llamadas a procedimientos Aplica una abstracción de procedimiento a una lista de parámetros. Comandos secuenciales El orden en que se ejecutan los comandos es importantes según se actualizan las varibles. Comandos colaterales El orden en que se ejecutan los comandos no es irrelevante. Ej: m:= 7, n:= n+1. Comandos condicionales Tiene un número de subcomandos de los cuales exactamente uno será elegido para ejecutarse. El típico comando es el if. (case) Comandos iterativos También conocido como loop. Tiene un grupo de subcomandos que se ejecutarán repetidamente con un tipo de frase que determina cuando terminará la iteración. (for, repeat, while) Enlace Un concepto común a todos los lenguajes de programación es la habilidad del programador para enlazar o relacionar identificadores con entidades tales como constantes, variables, procedimientos, fun- ciones y tipos. La buena elección de identificadores ayuda a hacer que los programas sean más compren- sibles y fáciles de interpretar. Más aún, relacionar un identificador con una entidad en un lugar y luego utilizar ese identificador para hacer referencia a esa entidad en otros lugares, hace que los programas sean más flexibles. Enlace y ámbitos Podemos decir que una declaración produce una asociación o un enlace entre el identificador declarado y la entidad que denotará. Un entorno o ámbito es un conjunto de enlaces. Alcance En general cada declaración tiene un cierto alcance, que tiene que ver con la porción del programa sobre el cual al declaración es efectiva. Estructura de bloque Un bloque es una frase del programa que delimita el alcance de cualquier declaración que puede contener La estructura de bloques más popular es la anidada donde cada bloque puede ser anidado en otro bloque ? Los bloques pueden ser abstracciones de procedimiento y función pero también pueden ser bloques de comandos. ? Un concepto aún más potente es el de expresiones de bloque. Es una expresión que es evaluada para producir un enlace con un identificador que se usará solo en el bloque donde se define. Alcance y visibilidad Los identificadores pueden aparecer en dos contextos diferentes. Llamaremos ocurrencia de enlace al punto en donde un identificador se declara, y llamaremos ocurrencia de aplicación a cada apa- rición del identificador cuando denota a la entidad a la cual fue enlazado. Por ejemplo: La aparición de n en const n = 7 es una ocurrencia de enlace, en donde n se enlaza al 7. Las apariciones subsecuentes de n en la expresión n * (n+1) son ocurrencias de aplicación, en donde n denota al 7. Enlace estático y dinámico La terminología de enlace estático y dinámico tiene que ver con el momento en que determina- mos que ocurrencia de enlace del identificador I se corresponde con la ocurrencia de aplicación de I. Con enlace estático podemos hacer esto en tiempo de compilación. Con enlace dinámico debemos retardarlo hasta el tiempo de ejecución. Con el enlace estático podemos determinar que ocurrencia de enlace de I se corresponde con una ocurrencia de aplicación de I dada, solo con examinar el código del programa, encontrando el bloque más pequeño que contiene una ocurrencia de aplicación de I que también contiene una ocurrencia de enlace de I. La asociación entre la ocurrencia de aplicación y enlace es fija. Con enlace dinámico la ocurrencia de enlace de I que se corresponde con una ocurrencia de apli- cación de I depende del flujo de control dinámico del programa. La entidad denotada por I es la declara- ción elaborada más recientemente de I dentro del bloque activo actual. Abstracciones Abstracción es un modo de pensamiento en el cual nos concentramos en las ideas generales más que en las manifestaciones específicas de estas ideas En programación, la abstracción alude a la distinción entre (a) qué hace una parte de un progra- ma y (b) cómo está implementado. Cuando se llama a un procedimiento nos concentramos sólo en qué hace dicho procedimiento; sólo cuando escribimos un pro- cedimiento nos interesará el cómo implementarlo. Tipos de abstracción Definiremos una abstracción como una entidad que engloba una computación. Abstracción de función Una abstracción de función engloba una expresión a evaluarse, y cuando es llamada retorna un valor como resultado. El usuario de la abstracción observa solo su resultado, no los pasos por los cuales se evalúa la función. Una abstracción de función es construida a partir de una definición de función: Function I (fp1; ... ; fpn) : T; B Abstracción de procedimiento Una abstracción de procedimiento engloba un comando a ejecutarse, y cuando es llamado actua- lizará variables. El usuario de la abstracción de procedimiento observa solo esas actualizaciones y no lo pasos por los cuales fueron efectuados Una abstracción de procedimiento es construido en Pascal, a partir de una definición de procedi- miento: Procedure I (fp1; ... ; fpn); B El principio de abstracción Como un resumen podemos decir: ? Una abstracción de función es una abstracción sobre una expresión. Quiere decir que una abstracción de función tiene un cuerpo que es una expresión, y una llamada a la función es una expresión que retornará un valor al evaluar el cuerpo de la abstracción de función. ? Una abstracción de procedimiento es una abstracción sobre un comando. Quiere decir que una abs- tracción de procedimiento tiene un cuerpo que es un comando, y una llamada a procedimiento es un comando que actualizará variables al ejecutar el cuerpo de la abstracción de procedimiento. Es posible construir abstracciones sobre cualquier clase sintáctica, con tal que las frases de esa clase especifiquen algún tipo de computación. ? Una abstracción de selección es una abstracción sobre el acceso a variable. Quiere decir que una abstracción de selección tiene un cuerpo que es un acceso a variable, y una llamada al selector es un acceso a variable que retornará una referencia a una variable al evaluar el cuerpo de la abstracción de selección. Parámetros Para aprovechar la potencia del concepto de abstracción, necesitamos abstracciones parametrizadas respecto a los valores con que opera. Un identificador que se usa en una abstracción para denotar un argumento se denomina pa- rámetro formal. Una expresión o frase que se pasa como argumento es denominado parámetro ac- tual por ejemplo 1.0 o a+b en las llamadas circunf (1.0) y cicunf (a+b) respectivamente. Un argumento es el valor que puede pasarse a una abstracción Mecanismo de copia Un mecanismo de copia permite que valores se copien a y/o desde una abstracción cuando se la llama. El parámetro formal X denota una variable local para la abstracción. Un valor se copia en X a la entrada de la abstracción, y/o se copia de X (a una variable no local) a la salida de la abstracción. Debido a que X es una variable local, se crea a la entrada de la abstracción y se elimina a la salida. Un parámetro por valor es una variable local X que se crea a la entrada de la abstracción y se le asigna el valor del argumento. Debido a que X se comporta como una variable local, su valor puede ser inspeccionado y actualizado. Sin embargo cualquier actualización de X no tiene efecto en ninguna varia- ble no local. Un parámetro resultado es todo lo contrario del anterior. En este caso, el argumento debe ser una referencia a una variable. De nuevo una variable local X se crea, pero su valor inicial es indefinido. A la salida de la abstracción el valor final de X es asignado a la variable argumento. Estos dos mecanismos pueden ser combinados para dar resultado a los parámetros valor- resultado. El argumento, de nuevo, debe ser una referencia a variable. En la entrada de la abstracción, la variable local X se crea y se le asigna el valor actual de la variable argumento. A la salida, el valor final de X se asigna nuevamente a la variable argumento. Mecanismo por definición Este mecanismo permite que el parámetro formal X se enlace directamente al argumento. Esto da una semántica simple y uniforme para el paso de parámetros de cualquier valor en el lenguaje de programación (no solo los valores de primera clase). ? En el caso de un parámetro constante, el argumento es un valor (de primera clase). X se enlaza al valor del argumento durante la activación de la llamada a la abstracción. ? En el caso de un parámetro variable (o por referencia), el argumento es una referencia a una varia- ble. X se enlaza a la variable argumento durante la activación de la llamada a la abstracción. Por lo tanto cualquier actualización o inspección de X es realmente una actualización o inspección del argu- mento. ? En el caso de un parámetro procedural, el argumento es una abstracción de procedimiento. X se enlaza al procedimiento (argumento) durante la activación de la llamada a la abstracción. Por lo tanto cualquier llamada a X es realmente una llamada al procedimiento (argumento). ? En el caso se un parámetro funcional, el argumento es una abstracción de función. X se enlaza a la función (argumento) durante la activación de la llamada a la abstracción. Por lo tanto cualquier lla- mada a X es realmente una llamada a la función (argumento). Una desventaja de los parámetros variable es la posibilidad de crear alias. Esto ocurre cuando dos o más identificadores son simultáneamente enlazados a la misma variable. Esto tiende a hacer que los programas sean más difíciles de entender. Orden de Evaluación El orden de evaluación se refiere exactamente al momento en que cada parámetro actual se eva- lúa cuando se llama a una abstracción. Existen básicamente dos posibilidades: ? Evaluar el parámetro actual en el punto de la llamada. ? Retardar su evaluación hasta que el argumento realmente se usa. El primer orden de evaluación se denomina "Evaluación Impaciente" (o evaluación en orden aplicativo). Se evalúa el parámetro actual una sola vez, y en efecto se sustituye el resultado en cada ocurrencia del parámetro formal. El segundo orden de evaluación se denomina "Evaluación en orden normal". No se evalúa inmediatamente el parámetro actual, sino que se sustituye el parámetro actual por cada ocurrencia del parámetro formal. La función sqr se dice que es estricta, lo cual significa que una llamada a esta función puede evaluarse solo si sus argumentos pueden ser evaluados. La función cand se dice que es no estricta en su segundo argumento, lo cual significa que una llamada a esta función puede a veces evaluarse aún cuando su segundo argumento pueda no ser evaluado. Este evaluación se denomina perezosa (lazy evaluation); el argumento se evalúa solo cuando se la necesita por primera vez (que podría ser nunca si la función es no restricta).