Fundamentos de programación con Módula-2 (3)

 

1.5 Modelos abstractos de cómputo
 
Los lenguajes de programación permiten describir programas o cómputos de manera formal, y por tanto simbólica y rigurosa. La descripción se hace, naturalmente, basándose en determinados elementos básicos y formas de combinación de estos elementos simples para construir programas tan complicados como sea necesario.
 
Existen muchísimos lenguajes de programación distintos, unas veces difieren en aspectos generales, y otras simplemente en detalles. Si analizamos estos lenguajes podremos observar que muchos de ellos utilizan elementos básicos y formas de combinación similares, aunque representándolos con símbolos diferentes.
 
Si de un conjunto de lenguajes de programación basados en elementos computacionales similares extraemos los conceptos comunes, obtendremos un modelo abstracto de cómputo. Este modelo abstracto recoge los elementos básicos y formas de combinación en forma abstracta, prescindiendo de la notación concreta usada en cada lenguaje de programación para representarlos.
 
Existen diversos modelos abstractos de cómputo, o modelos de programación, que subyacen en los lenguajes de programación actuales. Entre ellos están la programación funcional, programación lógica, programación imperativa, modelo de flujo de datos, programación orientada a objetos, etc. Todos estos modelos son modelos universales, en el sentido de que pueden utilizarse para describir cualquier cómputo intuitivamente posible.
 
Quizá el aspecto más interesante a destacar en este análisis de modelos abstractos de cómputo es que un programa que permita resolver un determinado problema puede adoptar formas muy diferentes, dependiendo del modelo de cómputo que se utilice para desarrollarlo. El modelo de programación imperativa es el más extendido, y eso induce a quienes empiezan a estudiar informática a identificar el concepto de programa con el de secuencia o lista de órdenes. Sin embargo, como veremos a continuación, existen otras formas igualmente válidas de representar un programa.
 
1.5.1 Modelo funcional
El modelo de programación funcional se basa casi exclusivamente en el empleo de funciones. El concepto de función se corresponde aquí de manera bastante precisa con el concepto de función en matemáticas. Una función es una aplicación, que hace corresponder un elemento de un conjunto destino (resultado) a cada elemento de un conjunto de partida (argumento) para el que la función esté definida.
 
Por ejemplo, la operación de suma de números enteros es una función en que el conjunto de partida es el de las parejas de números enteros y el de destino es el conjunto de números enteros. A cada pareja de enteros se le hace corresponder un entero, que es su suma.
 
En forma convencional, representaremos como f(x) al resultado que se obtendrá al aplicar la función f al argumento x. Por ejemplo, podemos suponer definidas las funciones de suma, resta y producto en la forma:
 
     Función                                     Resultado
  Suma( a, b )                                 a + b
  Diferencia( a, b )                           a – b
  Producto( a, b )                            a * b
 
Para describir cómputos complejos, las funciones pueden combinarse unas con otras, de manera que el resultado obtenido en una función se use como argumento para otra. De esta manera un cómputo tal como
                  34 x 5 + 8 x 7
puede representarse de manera funcional en la forma
                  Suma( Producto( 34, 5), Producto( 8, 7) )
 
Este es el aspecto que tiene un programa funcional, que será siempre en último extremo una aplicación de una función de unos argumentos, para obtener un resultado. El proceso de cómputo, llamado reducción, se basa en reemplazar progresivamente cada función por el resultado de la misma. Este sistema de evaluación por sustitución es la base del llamado cálculo-landa. Aplicado al ejemplo se tendría:
 
                 Cómputo parcial                                Expresión / Resultado
                                                                    Suma( Producto( 34, 5), Producto( 8, 7) )
                      34 x 5                                      Suma( 170, Producto( 8, 7) )
                       8 x 7                                      Suma( 170, 56 )
                      170 + 56                                    226
 
Las explicaciones anteriores se refieren a cómputos en los que sólo intervienen funciones primitivas, que son las que el computador o máquina abstracta que ejecuta el programa puede evaluar en forma directa. La programación funcional permite la definición por parte del programador de nuevas funciones a partir de las ya existentes. Utilizando de manera convencional el símbolo ::= para indicar definición, podremos crear una nueva función, Cuadrado para obtener el cuadrado de un número basándose en el uso del producto de dos números.
 
                                         Cuadrado( x ) ::= Producto( x, x )
 
Cuando en un cómputo intervienen funciones definidas, la evaluación se sigue haciendo por sustitución. El proceso, llamado reescritura, consiste en reemplazar una función por su definición, sustituyendo los argumentos simbólicos en la definición por los argumentos reales en el cómputo. Por ejemplo, para evaluar (5 + 3)^2 tendremos:
 
              Computo parcial                                   Expresión / Resultado
                                                                    Cuadrado( Suma( 5, 3 ) )
           reducir Suma                                        Cuadrado( 8 )
           reescribir Cuadrado                                Producto( 8, 8 )
           reducir Producto                                         64
 
1.5.2 Modelo de flujo de datos
En este modelo de cómputo, un programa corresponde a una red de operadores interconectados entre sí. Cada operador lo representaremos gráficamente mediante un cuadrado con entradas y salidas, y dentro de él el símbolo de la operación que realiza. Un operador espera hasta tener los valores presentes en sus entradas, y entonces se activa él solo, consume los valores en las entradas, calcula el resultado, y lo envía a la salida. Después de esto vuelve a esperar que le lleguen nuevos valores por las entradas.
 
           34 –>
                         x ——
            5 –>                 |
                                    |
                                    |—–>  + –>
            8 –>                 |
                         x    —-|     
            7 –>
 
   Figura 1.11 Red de flujo de datos.
 
Por ejemplo, la expresión 34 x 5 + 8 x 7 puede ser calculada por la red de la Figura 1.11
 
 
                        —->
                                    x  —-  170
                        —->              |
                                             |—->
                                                          +  —>
                                              —->  

                        —->              |
                                    x —-| 56
                        —->

 
 

                        —->
                                    x  —- 
                        —->              |
                                             |—->
                                                          +  —> 226
                                              —->  

                        —->              |
                                    x —-|
                        —->
 
   Figura 1.12 Evolución de la red de flujo de datos

                       

 
El cómputo se realiza durante la evolución de la red, tal como se indica en la Figura 1.12. Cuando la evolución termina, el resultado está presente en la salida de la derecha.
 
Una red de flujo de datos puede organizarse de manera que opere en forma iterativa, obteniendo no ya un resultado sino una serie de ellos. Por ejemplo, la red de la Figura 1.13 produce la serie de números naturales, a base de reciclar sobre sí mismo un operador incremento. Las pequeñas líneas verticales representan operadores de duplicación o mezcla de valores.
 
                              _________________________
                              |                                      |
                              |                                      |
                              |–>                             <–|
                                    | –>     +1    –>  |
                           0 —>                              —-> 1, 2, 3, 4, …
 
   Figura 1.13 Generación de una serie de números.
 
Esta red no termina nunca de evolucionar. Añadiendo operadores especiales de bifurcación se puede conseguir que se detenga al llegar un resultado adecuado.
 
1.5.3 Modelo de programación lógica
Este modelo abstracto de cómputo corresponde plenamente a lo que se denomina programación declarativa. Un programa consiste en plantear de manera formal un problema a base de declarar una serie de elementos conocidos, y luego preguntar por un resultado, dejando que sea la propia máquina la que decida cómo obtenerlo.
 
En programación lógica los elementos conocidos que pueden declararse son hechos y reglas. Un hecho es una relación entre objetos concretos. Una regla es una relación general entre objetos que cumplen ciertas propiedades. Una relación general entre objetos la escribiremos poniendo el nombre de dicha relación y luego los objetos relacionados entre paréntesis. Por ejemplo:
 
                   Hijo( Juan, Luis )
 
significaría que Juan es hijo de Luis. Si tenemos el árbol genealógico:
 
                     Luis               Ana
                       |                  |
                       |___________|
                                 |
                    ________|________
                    |            |            |
                 Felipe       Juan        Sonia
 
podremos declarar (prescindiendo del sexo) los hechos siguientes:
  
                                 Hechos
                          Hijo( Felipe, Luis )
                          Hijo( Juan, Luis )
                          Hijo( Sonia, Luis )
                          Hijo( Felipe, Ana )
                          Hijo( Juan, Ana )
                          Hijo( Sonia, Ana )
                         
Para realizar una consulta escribiremos el esquema de un hecho en que alguno de los elementos sea desconocido. Esto lo indicaremos usando nombres incógnitas en minúscula, para distinguirlos de los nombres de elementos conocidos, que en este caso se habían escrito en mayúsculas (en lenguaje Prolog se usa el convenio contrario). La consulta será respondida indicando todos los valores posibles que puedan tomar las incógnitas.  Por ejemplo:
 
                        Consulta                          Respuesta
                    Hijo ( x, Ana )                     x = Felipe
                                                           x = Juan
                                                           x = Sonia
 
La verdadera potencia de la programación lógica aparece cuando declaramos reglas. Al realizar consultas basadas en reglas la máquina realiza automáticamente las inferencias (deducciones) necesarias para responderla. Por ejemplo, usando el símbolo ":-" para definir una regla, escribiremos:
 
                               Reglas
                      Padre( x, y ) :- Hijo( y, x )
                      Hermano( x, y ) :- Hijo( x, z ), Hijo( y, z )
 
La primera regla se limita a nombrar la relación inversa de "hijo". La segunda expresa que dos personas son hermanas si son hijas de un mismo padre o madre. Ahora pueden realizarse consultas como las siguientes:
 
                    Consulta                       Respuesta
                 Padre( x, Sonia )              x = Luis
                                                     x = Ana
 
                 Hermano( x, Felipe )         x = Felipe
                                                     x = Juan
                                                     x = Sonia
 
La segunda consulta tiene una respuesta aparentemente errónea. Un análisis detallado nos permite comprobar que el error está en la formulación de la regla, ya que no se le ha informado a la máquina de que una persona no se considera hermana de sí misma. Modificando la regla se obtendrá la respuesta adecuada.
 
                                Reglas
                 Hermano( x, y ) :- Hijo( x, z ), Hijo( y, z ), distinto( x, y )
 
                 Consulta                                 Respuesta
            Hermano( x, Felipe )                    x = Juan
                                                           x = Sonia
 
1.5.4 Modelo imperativo
El modelo de programación imperativa responde a la estructura interna habitual de un computador, que se denomina arquitectura de Von Neumann. Un programa en lenguaje de máquina que aparece como una lista de instrucciones u órdenes elementales que han de ejecutarse una tras otra, en el orden en que aparecen en el programa. El nombre de programación imperativa deriva del hecho de que un programa aparece como una lista de órdenes a cumplir.
 
El orden de ejecución puede alterarse en caso necesario mediante el uso de instrucciones de control. Con ello se consigue ejecutar o no, o repetir, determinadas partes del programa dependiendo de ciertas condiciones en los datos.
 
Las instrucciones de un programa imperativo utilizan datos almacenados en la memoria del computador. Esta capacidad de almacenamiento de valores se representa en los programas imperativos mediante el uso de variables. Una variable no tiene aquí el mismo significado que en matemáticas, sino que representa un dato almacenado bajo un nombre dado. Una variable contiene un valor que puede ser usado o modificado tantas veces como se desee.
 
Un programa imperativo se plantea como el cálculo o modificación de sucesivos valores intermedios hasta obtener el resultado final. Las instrucciones típicas de un programa imperativo son las de asignación, que consisten en obtener un resultado parcial mediante un cálculo elemental que puede ser realizado por la máquina, y que se almacena en una variable para ser utilizado posteriormente.    
 
En los lenguajes de programación simbólicos las instrucciones u órdenes se denominan sentencias. En Modula-2 y otros lenguajes similares la sentencia de asignación se representa en la forma
 
                       variable := expresión
 
La parte derecha de esta sentencia es una expresión aritmética que puede usar variables o valores constantes, así como operadores que estén definidos en el lenguaje, tales como los correspondientes a las operaciones aritméticas habituales: suma, resta, etc. Una sentencia de asignación representa una orden de calcular el resultado de la expresión y luego almacenar dicho resultado como nuevo valor de la variable.
 
Usando sólo expresiones simples y variables auxiliares, podremos expresar el cálculo de
 
                        34 x 5 + 8 x 7
 
mediante las sentencias siguientes
 
         1) a := 34 x 5
         2) b := 8 x 7
         3) c := a + b
 
que obtendrán el resultado final en la variable c.
 
En realidad los lenguajes de programación permiten escribir directamente expresiones complejas. El cálculo anterior podría haberse hecho con una sola sentencia
 
               c := 34 x 5 + 8 x 7
 
Para mostrar cómo las variables en programación imperativa pueden ir modificando su valor paso a paso hasta obtener el resultado deseado, analizaremos el siguiente fragmento de programa, que calcula el valor de 5! = 1x2x3x4x5. En este programa se ha supuesto que existen instrucciones REPETIR y HASTA que permiten programar la repetición controlada de una parte del programa.
 
           1) f := 1
           2) k := 1
           3) REPETIR
           4) k := k+1
           5) f := f x k
           6) HASTA k = 5
 
Este programa obtiene el resultado final en la variable f. La variable k se utiliza para ir disponiendo de los sucesivos valores 2, 3, 4, etc. Las instrucciones 3) y 6) controlan la repetición de 4) y 5). La instrucción
 
            4) k := k + 1
 
tiene el significado siguiente: Se calcula el resultado de la expresión K + 1, usando el valor de k al iniciarse la ejecución de esa instrucción, y el valor obtenido se almacena de nuevo en k reemplazando el valor anterior. La primera vez que se ejecuta esa instrucción k tiene el valor 1, asignado inicialmente por la instrucción 2). Al sumarle 1 se obtiene el valor 2, y la variable k pasa a tener ahora este nuevo valor. Cada vez que se vuelva a ejecutar la instrucción 4) la variable k incrementará su valor en 1 unidad.
 
El análisis detallado del funcionamiento de un programa imperativo puede hacerse mediante una traza en la que se van anotando las sentencias o instrucciones de asignación que se van ejecutando sucesivamente, y los valores que toman las variables inicialmente y tras cada instrucción. En este ejemplo se tendrá:
 
                           Instrucción                     k       f
                                                               ?       ?
                                1)                            ?       1
                                2)                            1       1
                                4)                            2       1
                                5)                            2       2
                                4)                            3       2
                                5)                            3       6
                                4)                            4       6
                                5)                            4      24
                                4)                            5      24
                                5)                            5     120
 
El programa comienza con valores no definidos (?) para las variables. Termina cuando k ha tomado el valor 5, en cuyo caso finalizan las repeticiones y f tiene el valor 120 = 5!.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s