« Problemas de Satisfac… « || Inicio || » Cuadernos del CIS: Si… »

¿Se puede liberar la programación del estilo de von Neumann?

Última modificación: 24 de Noviembre de 2016, y ha tenido 110 vistas

Etiquetas utilizadas: || ||

These icons link to social bookmarking sites where readers can share and discover new web pages.
  • BarraPunto
  • Del.icio.us
  • Digg
  • email
  • Facebook
  • Google
  • LinkedIn
  • PDF
  • Reddit
  • Slashdot
  • Twitter

Esta entrada contiene algunas notas extraídas de la charla que dio John Backus (pionero de la computación) al recibir el premio Turing en 1977. El punto más importante de esta charla fue poner de manifiesto que las diferencias entre la programación imperativa y la funcional no responden únicamente a un estilo estético diferente, sino que pueden suponer una diferencia a la hora de tomar caminos más o menos eficientes para resolver un problema.

La charla completa fue publicada en 1978 en un artículo del Communications of the ACM (Vol. 21, No. 8, pages 613–41, August 1978), bajo el título Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs, y las notas que se muestran aquí son una traducción libre de los párrafos de dicho artículo que fueron usados en Notes on Functional Programming with Haskell por H. Conrad Cunningham.


Los lenguajes de programación parecen estar en problemas. Cada lenguaje sucesivo incorpora, con una pequeña depuración, todas las características de sus predecesores junto con algunas pocas nuevas. Algunos lenguajes tienen manuales que superan las 500 páginas, otros hacen uso de complejas descripciones en manuales más cortos haciendo uso de formalismos muy elaborados.

...

Cada nuevo lenguaje reivindica tener propiedades nuevas y de moda, tales como el tipado estricto o estructuras de control bien definidas, pero la realidaad es que pocos lenguajes hacen que programar sea suficientemente fácil o tan seguro que justifique el coste de haber sido creados o ser aprendidos. Como estos incrementos de tamaño solo producen pequeñas mejoras en potencia, lenguajes pequeños y más elegentas, como Pascal, continúan siendo populares. Pero hay una necesidad desesperada por disponer de una metodología potente que nos ayude a pensar sobre programas, y ningún lenguaje de programación convencional ha comenzado a cubrir tal necesidad. De hecho, los lenguajes convencionales crean una confusión innecesaria en la forma en que pensamos acerca de los programas.

...

Con el fin de entender los problemas de los lenguajes de programación convencionales, hemos de examinar previamente su progenitor intelectual, el ordenador de von Neumann. ¿Qué es un ordenador de von Neumann? Cuando von Neumann y otros lo concivieron ... [por 1940], era una idea elegante, práctica, y unificadora que simplificó un gran número de problemas de ingeniería y de programación de la época. Aunque las condiciones que produjeron su arquitectura han cambiado radicalmente, todavía identificamos la noción de “ordenador” con este ... concepto.
En su forma más simple, un ordenador de von Neumann tiene tres partes: una unidad central de proceso (o CPU), una unidad de almacenamiento, y un tubo conector que puede transmitir una palabra entre la CPU y el almacén (y una dirección al almacén). Propongo llamar a este tubo "cuello de botella" de von Neumann. La tarea de un programa consiste en cambiar el contenido del almacén esencialmente de una forma, cuando se considera que esta tarea debe llevarse a cabo enteramente transmitiendo palabras de ida y vuelta a través del cuello de botella de von Neumann, la razón para haber elegido este nombre se hace evidente.

Irónicamente, una gran parte del tráfico que pasa por este cuello de botella no corresponde a datos útiles, sino únicamente son nombres para esos datos, así como operaciones y datos usados únicamente para poder manejar esos nombres. Antes de que una palabra pueda ser enviada a través del tubo, su dirección debe estar en la CPU; por tanto, o bien debe haber sido enviada a través del tubo desde el almacén, o bien ha sido generada por alguna operación de la CPU. Si la dirección ha sido enviada desde el almacén, entonces su dirección o bien debe haber sido enviada desde el almacén, o generada en la CPU, y así continuamente. Si, por otra parte, la dirección se generó en la CPU, o bien ha sido generada por una regla fija (por ejemplo, “añade 1 al contador del programa") o por una instrucción que ha tenido que ser enviada a través del tubo, en cuyo caso su dirección ha debido ser enviada previamente, y así continuamente. Seguramente debe haber alguna forma menos primitiva de hacer cambio en el almacén que enviando grandes cantidades de números a través del cuello de botella de von Neumann.

Pero este tubo no es únicamente un cuello de botella literalmente para el tráfico de datos de un problema, sino, y más importantemente, es un cuello de botella intelectual que nos ha tenido atados a pensar en una-palabra-cada-vez en vez de motivarnos a pensar en términos de unidades conceptuales mayores.

...

Los lenguajes de programación convencionales son, básicamente, versiones más complejas y a más alto nivel de ordenadores de von Neumann. Nuestra ... vieja creencia de que existe solo un tipo de ordenador es la base de nuestra creencia de que existe solo un tipo de lenguaje de programación, el lenguaje convencional de von Neumann. Las diferencias entre Fortran y Algol 68, aunque considerables, son menos significantes que el hecho de que ambos están basados en el estilo de programación de un ordenador de von Neumann. Aunque me refiero a los lenguajes convencionales como "lenguajes de von Neumann" para hacer notar su origen y estilo, por supuesto no culpo a este gran matemático por sus complejidades. De hecho, se puede decir que yo también arrastro alguna responsabilidad por este problema. [Nota: Backus fue uno de los diseñadores de Fortran y de Algol-60.]

Los lenguajes de von Neumann usan variables para imitar las celdas de almacenamiento de los ordenadores; las estructuras de control se encargan de moverlas y de secuenciar las instrucciones de la CPU; y las sentencias de asignación imitan su lectura, almacenamiento y aritmética. Las sentencias de asignación son el cuello de botella de von Neumann de los lenguajes de programación, y nos mantienen atados a pensar en términos de una-palabra-cada-vez de forma similar a como hace el cuello de botella de un ordenador.

Consideremos un programa típico, en su núcleo encontraremos un buen número de sentencias de asignación conteniendo algunas variables etiquetadas. Cada sentencia de asignación produce un resultado de una palabra. El programa debe producir la ejecución de estas sentencias muchas veces, mientras altera los valores de las etiquetas, con el fin de realizar el cambio global deseado en el almacén, ya que éste debe ser realizado una-palabra-cada-vez. De esta forma, el programador se tiene que encargar del flujo de palabras a través del cuello de botella de asignaciones ya que diseña el anidamiento de sentencias de control que causan las repeticiones necesarias.

Más aún, las sentencias de asignación dividen la programación en dos mundos. El primero de ellos abarca las partes derechas de las sentencias de asignación. Es un mundo ordenado de expresiones, un mundo que tiene propiedades algebráicas útiles (salvo que estas propiedades son destruidas habitualmente por efectos secundarios). Es el mundo en el que tiene lugar la mayoría de la computación.
El segundo mundo de los lenguajes de programación convencionales es el mundo de las asignaciones. La sentencia principal en este mundo es la propia sentencia de asignación. Todas las demás sentencias del lenguaje existen con el fin de hacer posible la ejecución de estas asignaciones. Este mundo de asignaciones es un mundo desordenado, con muy pocas propiedades matemáticas útiles. La programación estructurada puede verse como un modesto esfuerzo por introducir algún orden en este mundo caótico, pero logra poco al atacar los problemas fundamentales creados por el estilo de programación de una-palabra-cada-vez de von Neumann, con su primitivo uso de bucles, subíndices, y control de ramificación del flujo.
Nuestra fijación en los lenguajes de von Neumann ha continuado la primacia del ordenador de von Neumann, y nuestra dependencia en él ha provocado que los lenguajes que no son de von Neumann resulten caros de producir y tengan un desarrollo limitado. La ausencia de estilos de programación eficientes y a gran escala que se funden en principios distintos a los de von Neumann ha privado a los diseñadores de fundamentos intelectuales para nuevas arquitecturas de ordenadores.


A partir de las notas anteriores puede ser interesante explicitar la clasificación que suele realizarse en los lenguajes de programación:

  •  Lenguajes Imperativos
    1. Un programa en un lenguaje imperativo tiene un estado implítico (esto es, valores de variables, contadores de programa, etc.) que es modificado (esto es, afectado por efectos secundarios) por medio de constructores (esto es, comandos) del lenguaje original.
    2. Como resultado, generalmente tales lenguajes tienen una noción explícita de secuenciación (de los comandos) para permitir un control preciso y determinista de los cambios del estado.
    3. Por tanto, los programas imperativos expresan cómo ha de computarse algo.
    4. Estos son los lenguajes de von Neumann o convencionales de los que hablaba Backus.
    5. Están especialmente adecuados a las arquitecturas de ordenadores tradicionales.
    6. La mayoría de los lenguajes existentes hoy en día están en esta categoría: Fortran, Algol, Cobol, Pascal, Ada, C, C++, Java, etc.
  • Lenguajes Declarativos
    1. Un programa en un lenguaje declarativo no tiene un estado implícito. Cualquier información necesaria sobre estados debe ser manejada explícitamente.
    2. Un programa se construye a partir de expresiones (o términos) más que comandos.
    3. La ejecución repetitiva se consigue por medio de recursión, más que por secuenciación.
    4. Los programas declarativos expresan qué debe ser computado (más que cómo debe hacerse).
    5. Los lenguajes declarativos se dividen habitualmente en dos subtipos:
      • Lenguajes Funcionales (o aplicativos)
        1. El modelo de computación subyacente es el concepto matemático de función.
        2. En una computación, una función se aplica a cero o más argumentos para calcular un valor simple, de forma determinista.
        3. Ejemplos de lenguajes funcionales puros son: FP, Haskell, Miranda, Hope, Orwell
        4. Ejemplos de lenguajes funcionales hibridos son: Lisp, Scheme, SML (Scheme & SML have powerful declarative subsets)
      • Lenguajes Relacionales (o lógicos)
        1. El modelo de computación subyacente es el concepto matemático de relación (o predicado).
        2. Una computación es la asociación no determinista de un grupo de valores (normalmente se usa bactracking para resolver los valores adicionales).
        3. Ejemplos de lenguajes relacionales son: Prolog (pure), Parlog, KL1 (La mayoría de las implementaciones de Prolog tienen características imperativas, como el corte y la posibilidad de añadir y eliminar claúsulas).

« Problemas de Satisfac… « || Inicio || » Cuadernos del CIS: Si… »