DSN_XP y las Ciencias matemáticas de la computación

Hacia una ciencia matemática de Computación

DSN_XP recoge de la historia del software, los escritos que nos han parecido muy relevantes y dentro de este listado, en esta ocasión tomamos como referente la propuesta de John McCarthy denominada como Towards a Mathematical Science of Computation

Introducción (1996)

En este artículo discutiré las perspectivas de una ciencia matemática de computación. En una ciencia matemática, es posible deducir de los supuestos básicos, las propiedades importantes de las entidades tratadas por la Ciencia.  Así, a partir de la ley de gravitación de Newton y sus leyes del movimiento, uno puede deducir que las órbitas planetarias obedecen a las leyes de Kepler. 

• ¿Cuáles son las entidades de las que se ocupa la ciencia de la computación? 
• ¿Qué tipo de hechos sobre estas entidades nos gustaría derivar? 
• ¿Cuáles son los supuestos básicos de los que debemos partir? 
• ¿Qué resultados importantes se han obtenido ya? 
• ¿Cómo puede la ciencia matemática ayudar en la solución de problemas prácticos?

Me gustaría proponer algunas respuestas parciales a estas preguntas. Estas respuestas parciales sugieren algunos problemas para el trabajo futuro. Primero, daré algunas respuestas generales muy esquemáticas a las preguntas. Entonces presentare algunos resultados recientes sobre tres cuestiones específicas. Finalmente, intentaré dibujar algunas conclusiones sobre aplicaciones prácticas y problemas para trabajos futuros. 

Este artículo debería considerarse junto con mi artículo anterior [McC63]. 

Los principales resultados del presente documento son nuevos, pero existe cierta superposición, por lo que este documento sería autónomo. Sin embargo, algunos de los temas de este escrito como expresiones condicionales, definición recursiva de funciones y prueba por inducción recursiva se consideran con mucho mayor detalle en el documento anterior.

¿Cuáles son las entidades con las que la ciencia del cómputo debe lidiar?

Estas son problemas, procedimientos, espacios de datos, programas que representan procedimientos en determinados lenguajes de programación y computadores. 

Los problemas y los procedimientos a menudo se confunden. 

• Un problema se define por el criterio que determina si se acepta una solución propuesta. Uno puede comprender un problema completamente sin tener ningún método de solución.  
• Los procedimientos generalmente se construyen a partir de procedimientos elementales. Lo qué pueden ser estos procedimientos elementales y cómo los procesos más complejos se construyen a partir de ellos, este es uno de los primeros temas de la ciencia de la computación. 

Esta temática no es difícil de entender desde que existe una noción precisa de una función computable para guiarnos y computablemente relativa a una colección dada de las funciones iniciales, es fácil de definirla.

• Los procedimientos operan sobre miembros de ciertos espacios de datos y producen miembros de otros espacios de datos, utilizando en general otros espacios de datos como intermediarios. Se conocen varias operaciones para construir nuevos espacios de datos con los más simples, pero todavía no existe una teoría general de espacios de datos representables, comparables a la teoría de funciones computables. Algunos resultados están dados en [McC63].
• Los programas son expresiones simbólicas que representan procedimientos. El mismo procedimiento puede estar representado por diferentes programas en diferentes lenguajes de programación.

Se discutirá el problema de definir semánticamente un lenguaje de programación indicando qué procedimientos representan los programas. En cuanto a la sintaxis de los lenguajes de programación, las reglas que nos permiten determinar si una expresión pertenece al lenguaje han sido formalizadas pero las partes de la sintaxis que se relacionan estrechamente con la semántica, no ha sido tan bien estudiadas

El problema de traducir procedimientos de un lenguaje de programación a otro ha sido muy estudiado y vamos a intentar dar una definición de la corrección de la traducción.

Las computadoras son autómatas finitos. Desde nuestro punto de vista, una computadora está definida por el efecto de ejecutar un programa con una entrada dada, en el estado de su memoria y de sus salidas.

La ciencia de la computación debe estudiar las diversas formas en la que los elementos de los espacios de datos se representan en memoria de la computadora y cómo los procedimientos están representados por programas de cómputo. Bajo esta perspectiva, la mayoría de los trabajos actuales sobre la teoría del autómata no viene al caso.

¿Qué tipos de hechos acerca de los problemas, procedimientos, espacios de datos, programas y computadores nos gustaría derivar?

Ante todo. nos gustaría poder demostrar que determinados procedimientos resuelven determinados problemas dados. Sin embargo, probar esto puede implicar probar una gran cantidad de otros tipos de afirmaciones como: 

1. Dos procedimientos son equivalentes, por ejemplo, si calculan la misma función. 
2. Varias funciones computables satisfacen una determinada relación, como una identidad algebraica o una fórmula del cálculo funcional. 
3. Cierto procedimiento finaliza para ciertos datos iniciales, o para todos los datos iniciales. 
4. Un cierto procedimiento de traducción, traduce correctamente los procedimientos entre un lenguaje de programación y otro. 
5. Un procedimiento es más eficiente que otro procedimiento equivalente si en ese sentido se realiza en menos pasos o requiere menos memoria.
6. Una cierta transformación de los programas conserva la función expresada pero aumenta la eficiencia.
7. Cierta clase de problemas no se puede resolver mediante ningún procedimiento o requiere procedimientos de cierto tipo para su solución

¿Cuáles son los axiomas y reglas de inferencia de una ciencia matemática de computación?

Idealmente, nos gustaría una teoría matemática en la que todo enunciado verdadero acerca de los procedimientos tendría una prueba y preferiblemente una prueba que sea fácil de encontrar, no demasiado larga y fácil de comprobar. 

En 1931, Gödel demostró un resultado, uno cuyas consecuencias inmediatas fueron que no hay teoría matemáticas completa de la computación. Dada cualquier teoría matemática de la computación, hay enunciados verdaderos que pueden expresarse y que no tienen pruebas. Sin embargo, podemos esperar una teoría que sea adecuada para propósitos prácticos, como demostrar que los compiladores funcionan; las declaraciones no demostrables tienden a ser de un carácter bastante arrollador, como que el sistema en sí es consistente. 

Es casi posible hacerse cargo de uno de los sistemas de la teoría de los números elementales como la expuesta en el libro de Mostowski "Sentences Undecidable in Formalized Arithmetic" desde que el contenido de una teoría de la computación es bastante similar. Desafortunadamente, este y otros sistemas similares se diseñaron para facilitar la demostración de meta teoremas sobre el sistema, en lugar de probar teoremas en el sistema. Como resultado, a los enteros se les dio un papel tan especial que pruebas de afirmaciones bastante fáciles sobre procedimientos simples podrían ser extremadamente largas.

Por lo tanto, es necesario construir un nuevo pensamiento similar, teoría en la que ni los números enteros, ni ningún otro dominio (por ejemplo, cadenas de símbolos) se les de un papel especial. Se describen algunos resultados parciales en esta dirección en este escrito. A saber, un formalismo libre de números enteros para describir cálculos ha sido desarrollado y ha demostrado ser adecuado en los casos en que los que puede ser comparado con otros formalismos. 

Se han desarrollado algunos métodos de prueba, pero todavía existe una brecha en lo que respecta a los métodos para demostrar que un procedimiento finaliza. La teoría también requiere extensión para tratar las propiedades de los espacios de datos.

¿Qué resultados relevantes se han obtenido para una ciencia matemática de computación?

En 1936, Turing aclaró la noción de función computable y demostró la existencia de computadores universales que, con un adecuado programa, podría calcular cualquier cosa calculada por cualquier otra computadora. 

Todo nuestros programas almacenados de computadoras, cuando se les proporciona almacenamiento auxiliar ilimitado, son universales, en el sentido de Turing. En cierto sentido subconsciente, incluso las ventas de los departamentos de los fabricantes de computadoras son conscientes de esto y no anuncian instrucciones mágicas que no pueden ser simuladas en máquinas competidoras, pero solo se anuncia que sus máquinas son más rápidas, más baratas, tienen más memoria, o son más fáciles de programar. 

El segundo resultado importante fueron la existencia de clases de problemas irresolubles. Esto mantiene a todas las empresas menos a las más ignorantes de nosotros tratando de inventar un procedimiento de depuración que pueda infaliblemente decir si un programa que se está examinando entrará en un bucle. 

Más adelante en este escrito, discutiremos la relevancia de los resultados de la lógica matemática a un grupo de problemas creativos sobre si es posible que la máquina pueda ser tan inteligente como un ser humano. En mi opinión es muy importante construir un puente más firme entre la lógica y la teoría de funciones recursivas por un lado y la práctica de la computación por el otro. 

Gran parte del trabajo sobre la teoría de los autómatas finitos ha sido motivado con la esperanza de aplicarlo en la computación. Pienso que esta esperanza en su mayoría es en vano porque el hecho de la finitud se usa para mostrar que el autómata eventualmente repetirá un estado. Sin embargo, cualquiera que espere que un IBM 7090 repita un estado, únicamente porque es un autómata finito, está en una espera muy larga.

¿Cómo puede la ciencia matemática de la computación ayudar a la solución práctica de problemas?

Naturalmente, no se pueden prever las aplicaciones más importantes de una ciencia cuando recién comienza. Sin embargo, se pueden prever las siguientes aplicaciones: 

1. En la actualidad, los lenguajes de programación se construyen de una manera muy poco sistemática. Se inventan una serie de características propuestas y luego argumentamos sobre si cada función vale su costo. Una mejor comprensión de la estructura de los cálculos y de los espacios de datos facilitará ver qué las características son realmente deseables. 
2. Debería ser posible casi eliminar la depuración. La depuración son las pruebas de un programa en los casos que uno espera sean típicos, hasta que parece que funcionan.  Esta esperanza es frecuentemente vana. 

En lugar de depurar un programa, se debe demostrar que cumple con sus especificaciones y esta prueba debe ser verificada por un programa de computadora. Para que esto sea posible, se requieren sistemas formales en los que sea fácil escribir pruebas.

Hay una buena posibilidad de hacer esto, porque podemos requerir de la computadora hacer mucho más trabajo en la verificación de cada paso de lo que un humano está dispuesto a hacer. Por lo tanto, los pasos pueden ser mayores que con los sistemas formales actuales. las perspectivas para esto se discuten en [McC62].

El uso de expresiones condicionales para definir funciones recursivas

En el lenguaje matemático ordinario, existen ciertas herramientas para definir nuevas funciones en términos de las antiguas. Estas herramientas son la composición y la identificación de variables. Da la casualidad de que estas herramientas son inadecuadas computablemente en términos de las anteriores. Entonces se acostumbra definir todas las funciones que pueden razonablemente considerarse que dan una definición verbal. Por ejemplo, la función | x | generalmente se define en palabras. 

Si agregamos una sola herramienta formal, a saber, expresiones condicionales a nuestra notación matemática y si permitimos que se utilicen expresiones condicionales recursivamente de una manera que pueda describirse, podemos definir, de una manera completamente formal, todas las funciones que razonablemente pueden considerarse computables en términos de un conjunto inicial. 

Usaremos la notación ALGOL 60 para expresiones condicionales en este documento. 

Usaremos expresiones condicionales en la forma simple 

si p entonces a si no b 

donde p es una expresión proposicional cuyo valor es verdadero o falso. El valor de la expresión condicional es a si p tiene el valor verdadero y b si p tiene el valor falso. Cuando se utilizan expresiones condicionales, el stock de predicados que uno tiene disponible para construir p es tan importante como el stock de funciones ordinarias que se utilizarán para formar las a y las b por composición. 

A continuación, se muestran ejemplos de funciones definidas por expresiones condicionales:

La primera de ellas es la única definición no recursiva del grupo. Luego, tenemos tres procedimientos diferentes para calcular n !; les puede parecer ser equivalentes por los métodos que se describirán en este documento. Entonces definimos la función predecesora n- para enteros positivos (3- = 2) en términos de la función sucesora n´(2´ = 3) Finalmente, definimos la suma en términos del sucesor, antecesor e igualdad. En todas las definiciones, excepto en la primera, el dominio de las variables se toma como el conjunto de valores no negativos enteros.

Como ejemplo del uso de estas definiciones, mostraremos cómo computar 2! según la segunda definición de n !. Tenemos

Tenga en cuenta que si intentamos calcular n! para cualquier n pero entero no negativo las sucesivas reducciones no terminarían. En tales casos decimos que el cálculo no converge. Algunas funciones recursivas convergen para todos los valores de sus argumentos, algunas convergen para algunos valores de sus argumentos y algunos nunca convergen. Las funciones que siempre convergen se llaman funciones totales, y las otras se llaman funciones parciales. Uno de los resultados más importantes de la teoría de la función recursiva es que no hay formalismo que obtenga todas las funciones totales computables y no funciones parciales.

[McC63] Hemos probado que el método anterior para definir funciones computables, comenzando solo con la función sucesora n` y la igualdad, produce todas las funciones computables de los enteros. Esto nos lleva a afirmar que tenemos el conjunto completo de herramientas para definir funciones que son computables en términos de las dadas funciones base.

Si examinamos la penúltima línea de nuestro cálculo de 2! vemos eso no podemos simplemente considerar la expresión condicional 

si p entonces a si no b 

como función de las tres cantidades p, a y b. Si lo hiciéramos, estaríamos obligados a calcular g (−1,0) antes de evaluar la expresión condicional y este cálculo no convergería. Lo que debe pasar es que cuando p es cierto, tomamos a como el valor de la expresión condicional sin regresar a ver a b.

Cualquier referencia a funciones recursivas en el resto de este artículo se refiere a funciones definidas por los métodos anteriores. 

Probar afirmaciones sobre funciones recursivas

En la sección anterior presentamos un formalismo para dadas funciones base describir funciones que son computables en términos de estas. Nos gustaría tener una teoría matemática lo suficientemente fuerte como para admitir pruebas de esos hechos acerca de los procedimientos de computación que uno normalmente necesita para mostrar que los programas computables cumplen con sus especificaciones. 

En [McC63] mostramos que nuestro formalismo para expresar funciones computables, era lo suficientemente fuerte como para que todos las funciones recursivas de enteros se pueden obtener a partir de la función sucesora y la igualdad. Ahora nos gustaría una teoría lo suficientemente fuerte para que la adición de alguna forma de axiomas de Peano permitiría la demostración de todos los teoremas de una de las formas de la teoría de números elementales. 

Aún no tenemos tal teoría. La dificultad radica en mantener los axiomas y reglas de inferencia de la teoría libres de los enteros u otros dominios, tal como lo hemos logrado con el formalismo para construir funciones.  Ahora enumeraremos las herramientas que tenemos hasta ahora para probar las relaciones entre funciones recursivas. Se comentan con más detalle en [McC63]. 

1. Sustitución de expresiones por variables libres en ecuaciones y otras relaciones. 
2. Reemplazo de una subexpresión en una relación por una expresión que se ha demostrado que es igual a la subexpresión. (Esto se conoce en matemáticas elementales como sustitución de iguales por iguales.)
   
   Cuando estamos tratando con expresiones condicionales, una forma de esta regla más fuerte que la habitual es válida. Supongamos que tenemos una expresión de la forma
   
   
    si p entonces a si no (si q entonces b si no c) 
   
   y deseamos reemplazar b por d. En estas circunstancias, no tenemos que probar la ecuación b = d en general, pero solo el enunciado más débil
   
   
   ∼ p ∧ q ⊃ b = d
   
   Esto se debe a que b afecta el valor de la expresión condicional solo en el caso ∼ p ∧ q es cierto. 
3. Las expresiones condicionales satisfacen una serie de identidades y una teoría completa de las expresiones condicionales, muy similar al cálculo proposicional, es tratada a fondo en [McC63]. Enumeraremos algunas de las identidades tomadas como axiomas aquí. 
   
   
   
   
   
4. Finalmente, tenemos una regla llamada inducción de recursividad para hacer argumentos que en las formulaciones habituales se realizan por inducción matemática. Esta regla puede considerarse que toma uno de los teoremas de la teoría de la función recursiva y dándole el estatus de regla de inferencia. Inducción de recursividad puede describirse de la siguiente manera:
   
   Supongamos que tenemos una ecuación de recursión que define una función f, a saber


f (x 1 , ..., x n ) = ε {f, x 1 , ..., x n } (1)



donde el lado derecho será una expresión condicional en todos los no triviales casos y supongamos que:


1. El cálculo de f (x 1 , ..., x n ) de acuerdo con esta regla converge para un cierto conjunto A de n-tuplas, 
2. las funciones g (x 1 , ..., x n ) y h (x 1 , ..., x n ) satisfacen cada una la ecuación (1) cuando g o h se sustituye por f.  Entonces podemos concluir que g (x 1 , ..., x n ) = h (x 1 , ..., x n ) para todas las n-tuplas (x 1 , ..., x n ) del conjunto A. 

Como ejemplo del uso de la inducción recursiva demostraremos que la función g definida por 


g (n, s) = si n = 0 entonces s si no g (n - 1, n × s) 


satisface g (n, s) = n! × s dados los datos habituales sobre n !, Tomaremos por dado el hecho de que g (n, s) converge para todas las integrales n y s no negativas. Entonces solo necesitamos mostrar que n! × s satisface la ecuación para g (n, s), tenemos


n! × s = si n = 0 entonces n! × s else n! × s 
              si n = 0 entonces s else (n - 1)! × (n × s) 


y esto tiene la misma forma que la ecuación satisfecha por g (n, s). Los pasos en esta derivación son bastante obvios pero también siguen los axiomas mencionados anteriormente y las reglas de inferencia.  En particular, la regla extendida de reemplazo se utilizan varios ejemplos adicionales de demostración por inducción de recursividad se dan en [McC63] y se ha utilizado para probar algunas relaciones bastante complicadas entre funciones computables.

Funciones recursivas, diagramas de flujo y programas algolic

En esta sección quiero establecer una relación entre el uso de funciones recursivas para definir cálculos, la notación del diagrama de flujo y programas expresados como una secuencia de sentencias de asignación de tipos ALGOL, junto con la condicional Go To. A este último lo llamaremos programas Algolic con la idea de ampliar posteriormente la notación y los métodos de prueba para cubrir más el lenguaje ALGOL. Recuerda que nuestro propósito aquí no es crear todavía otro lenguaje de programación, sino proporcionar herramientas para probar hechos sobre programas. 

Para considerar los programas como funciones recursivas, definiremos el estado del vector ξ de un programa en un momento dado, para ser el conjunto de valores actualmente asignados a las variables del programa. En el caso de un programa en lenguaje de máquina, el estado del vector es el conjunto de contenidos actuales de esos registros cuyo contenido cambia durante el curso de la ejecución del programa. 

Cuando se ejecuta un bloque de programa que tiene una sola entrada y salida, el efecto de esta ejecución en el estado del vector puede ser descrito por una función ξ` = r (ξ) dando el nuevo estado del vector en términos del antiguo. 

Considere un programa descrito por el diagrama de flujo de la fig. 1.

Los dos bloques internos de cómputo se describen mediante las funciones f (ξ) y g (ξ), indicando cómo estos bloques afectan el estado del vector. Los óvalos de decisión se describen mediante los predicados p (ξ), q 1 (ξ) y q 2 (ξ) que define las condiciones para tomar varios caminos. Deseamos describir la función r (ξ) que da el efecto a todo el bloque, en términos de las funciones f y g y los predicados p, q 1 y q 2 . Esto se hace con la ayuda de dos funciones auxiliares s y t. s (ξ) describe el cambio en ξ entre el punto etiquetado como s en el gráfico y la salida final del bloque; t se define de manera similar con respecto al punto etiquetado t. Podemos leer las siguientes ecuaciones directamente del diagrama de flujo:

r (ξ) = s (f (ξ))

s (ξ) = si p (ξ) entonces r (ξ) si no t (g (ξ))

t (ξ) = si q 1 (ξ) entonces r (ξ) si no q 2 (ξ) entonces ξ si no t (g (ξ))

De hecho, estas ecuaciones contienen exactamente la misma información que el diagrama de flujo.

Considere la función mencionada anteriormente, dada por

g (n, s) = si n = 0 entonces s si no g (n - 1, n × s)

Corresponde, como dejamos que el lector se convenza a sí mismo, al programa Algolic 

Este diagrama de flujo se muestra en la fig. 2.

En el diagrama de flujo se describe mediante la función fac (ξ) y la ecuación 

fac (ξ) = si p (ξ) entonces ξ si no fac (g (f (ξ)))

donde p (ξ) corresponde a la condición n = 0, f (ξ) al enunciado n: = n - 1 y 

g (ξ) al enunciado s: = n × s.

dónde

p (ξ) ≡ c (n, ξ) = 0,

f (ξ) = a (s, c (n, ξ) ∗ c (s, ξ), ξ),

g (ξ) = a (n, c (n, ξ) - 1, ξ)

y así

fac (ξ) = a (n, 0, a (s, c (n, ξ)! × c (s, ξ))).

Consideraremos que el estado del vector tiene muchos componentes, pero los únicos componentes afectados por el presente programa son el componente s y el componente n. 

Para calcular explícitamente con los estados del vector, introducimos la función c (var, ξ) que denota el valor asignado a la variable var en el estado del vector ξ, y también introducimos la función a (var, val, ξ) que denota el estado del vector que resulta cuando el valor asignado a var en ξ se cambia a val y los valores de las otras variables no se modifican.

Los predicados y funciones de los estados del vector mencionados anteriormente serían:

p (ξ) = (c (n, ξ) = 0)

g (ξ) = a (n, c (n, ξ) - 1, ξ)

f (ξ) = a (s, c (n, ξ) × c (s, ξ), ξ)

Podemos probar por inducción de recursividad que fac (ξ) = a (n, 0, a (s, c (n, ξ)! × c (s, ξ), ξ),

pero para hacerlo debemos utilizar los siguientes hechos sobre las funciones del estado básico del vector:

1. c (u, a (v, α, ξ)) = si u = v entonces α si no c (u, ξ)
2. a (v, c (v, ξ), ξ) = ξ
3. a (u, α, a (v, β, ξ)) = si u = v entonces a (u, α, ξ) de lo contrario a (v, β, a (u, α, ξ))
   La prueba es paralela a la prueba anterior de que
   g (n, s) = n! × s,

pero las fórmulas son más largas.

Si bien todos los diagramas de flujo corresponden inmediatamente a funciones recursivas de el estado del vector, lo contrario no es el caso. La traducción desde la función recursiva al diagrama de flujo y por lo tanto al programa Algolic es inmediata, sólo si las ecuaciones de recursividad están en forma iterativa. Supongamos que tenemos una ecuación de recursividad

r (x 1 , ..., x n ) = E {r, x 1 , ..., x n , f 1 , ..., f m }

donde E {r, x 1 , = ldots, x n , f 1 , ..., f m } es una expresión condicional que define la función r en términos de las funciones f 1 , ..., f m . Se dice que E está en modo iterativo si r nunca aparece como el argumento de una función, sino sólo en términos de expresión condicional principal en la forma

... luego r (...).

En los ejemplos, todas las definiciones recursivas excepto

n! = si n = 0 entonces 1 si no n × (n - 1)!

están en forma interactiva. En ese, (n - 1)! ocurre como un término de un producto. 

Las funciones recursivas no iterativas se traducen en programas Algolic que se utiliza recursivamente como procedimiento. Los cálculos numéricos generalmente pueden transformarse en forma iterativa, pero los cálculos con expresión simbólica usualmente no pueden, a menos que las cantidades que juegan el papel de listas introducido explícitamente.

Inducción de recursividad en programas Algolic

En esta sección ampliamos el principio de inducción de recursividad para que pueda aplicarse directamente a los programas de Algolic sin antes transformarlos en funciones recursivas. Considere el programa Algolic 

Queremos demostrar que es equivalente al programa 

Antes de dar esta prueba describiremos el principio de inducción de recursividad tal como se aplica a una clase simple de diagramas de flujo. Supongamos que tenemos un bloque de programa representado por la fig. 3a. Supongamos que hemos probado que este bloque es equivalente al diagrama de flujo de la fig. 3b donde el bloque sombreado es el bloque original de nuevo. Esto corresponde a la idea de una función que satisface una ecuación funcional. Ahora podemos concluir que el bloque de la fig. 3a es equivalente al diagrama de flujo de la fig. 3c para aquellos estados del vector para los que el programa no quede atascado en un bucle en la fig. 3c. 

Esto se puede ver de la siguiente manera, suponga que, para una entrada particular, el programa de la fig. 3c da la vuelta al bucle n veces antes de salir. Considere el diagrama de flujo que resulta cuando toda la fig. 3b se sustituye por el bloque sombreado (o amarillo) y luego sustituido en esta figura nuevamente, etc., un total de n sustituciones. El estado del vector al pasar por este diagrama de flujo se someterá exactamente a las mismas pruebas y cambios que al pasar por el flujo. 3c y, por lo tanto, saldrá en n pasos sin pasar por el bloque sombreado (o amarillo). Por tanto, debe salir con el mismo valor como en la fig. 3c. Por lo tanto, para cualquier vector para el que el cálculo de la fig. 3c converge, fig. 3a es equivalente a la fig. 3c.

Por tanto, para utilizar este principio para demostrar la equivalencia de dos bloques, probamos que satisfacen la misma relación, de tipo 3a-3b, y que el 3c correspondiente converge.

Aplicaremos este método para demostrar que los dos programas mencionados anteriormente son equivalentes. El primer programa se puede transformar de la siguiente manera:

La operación utilizada para transformar el programa es simplemente escribir por separado la primera ejecución de un bucle.

En el caso del segundo programa vamos:

Las operaciones utilizadas aquí son: primero, la introducción de una rama espuria, después de lo cual se realiza la misma acción independientemente de la forma en que la rama vaya; segundo, una simplificación basada en el hecho de que si la rama va por la primera vía, luego n = 0, junto con la reescritura de uno de los lados derechos de una declaración asignada y tercero, eliminación de una etiqueta correspondiente a una declaración nula y lo que podría llamarse una anti-simplificación de una secuencia de declaraciones de asignación. Aún no hemos elaborado un conjunto de reglas formales que justifique estos pasos, pero las reglas se pueden obtener de las reglas dadas anteriormente para sustitución, reemplazo y manipulación de expresiones condicionales. 

El resultado de estas transformaciones es mostrar que los dos programas, satisface cada uno una relación de la forma: programa es equivalente a

El programa correspondiente a la fig. 3c en este caso, es precisamente el primer programa que asumiremos siempre converge. Esto completa la prueba.

La descripción de los lenguajes de programación

Los lenguajes de programación deben describirse sintácticamente y semánticamente. Esta es la distinción. La descripción sintáctica incluye: 

1. Una descripción de la morfología, es decir, qué expresiones simbólicas representan programas gramaticales. 
2. Las reglas para el análisis de un programa en partes y su síntesis de las partes. Por tanto, debemos ser capaces de reconocer un término que represente un suma y extraer de ella los términos que representan los sumandos. 

La descripción semántica del lenguaje debe decir lo que los programas significan. El significado de un programa es su efecto sobre el estado del vector en el caso de un lenguaje independiente de la máquina, y su efecto sobre el contenido de la memoria en el caso de un programa en lenguaje máquina.

Sintaxis abstracta de los lenguajes de programación

La forma normal de Backus que se utiliza en el informe ALGOL describe la morfología de los programas ALGOL de forma sintética. Es decir, describe cómo se construyen los distintos tipos de programas a partir de sus partes. Esto sería mejor para traducir a ALGOL que para el problema más habitual de traducir desde ALGOL. 

La forma de sintaxis que describiremos ahora difiere de la forma normal de Backus de dos maneras. Primero, es analítico en lugar de sintético; dice cómo desarmar un programa, en lugar de cómo armarlo. En segundo lugar, es abstracto en el sentido de que es independiente de la notación utilizada para su representación, digamos sumas, pero solo afirma que pueden ser reconocidas y desmontadas.

Considere un fragmento de los términos aritméticos de ALGOL, incluidas las constantes y las variables y sumas y productos. Como simplificación adicional, se debe considerar que las sumas y los productos tienen exactamente dos argumentos, aunque el caso general no es muy difícil. Supongamos que tenemos un término t. Desde la perspectiva de traducción, primero debemos determinar si representa una constante, una variable, una suma o un producto. Por lo tanto, postulamos la existencia de cuatro predicados: isconst (t), isvar (t), issum (t) e isprod (t). Supondremos que cada término satisface exactamente uno de estos predicados. 

Considere los términos que son variables. Un traductor deberá poder saber si dos símbolos son ocurrencias de la misma variable, por lo que necesitamos un predicado de igualdad en el espacio de variables. Si las variables tienen que ser ordenadas se requiere una relación de ordenación. 

Considere las sumas. Nuestro traductor debe poder seleccionar los sumandos y por lo tanto postulamos la existencia de funciones addend (t) y augend (t) definidas en aquellos términos que satisfacen issum (t). Del mismo modo, tenemos las funciones mplier (t) y mpcand (t) definidas en los productos. Desde el análisis de un término debe terminar, el predicado definido recursivamente

debe converger y tener el valor verdadero para todos los términos.

Los predicados y funciones cuya existencia y relaciones definen la sintaxis, son precisamente las necesarias para traducir del lenguaje, o para definir la semántica. Por eso no es necesario que nos importe si las sumas están representadas por a + b, o + ab, o (PLUS AB), o incluso por los números de Gödel 7 a 11 b .

Es útil considerar lenguajes que tienen tanto una analítica como una sintaxis sintética que satisface ciertas relaciones. Continuando con nuestro ejemplo de términos, la sintaxis sintética está definida por dos funciones mksum(t, u) y mkprod (t, u) que, cuando se dan dos términos t y u, dan su suma y producto respectivamente.  Llamaremos regular a la sintaxis si las sintaxis analítica y sintética están relacionadas por las relaciones plausibles:

Una vez que se ha decidido la sintaxis abstracta de un lenguaje, se puede elegir el dominio de las expresiones simbólicas que se utilizarán. Entonces uno puede definir las funciones sintácticas explícitamente y se satisfacen a si mismas, preferiblemente probando que satisfagan las relaciones adecuadas. Si tanto el analítico como el sintético se dan funciones, no tenemos las difíciles y a veces insolubles problemas de análisis que surgen cuando los lenguajes se describen sólo sintéticamente.

En ALGOL las relaciones entre las funciones analítica y sintética no son del todo regulares, es decir, las relaciones sólo se mantienen hasta una equivalencia. Por tanto, se permiten paréntesis redundantes, etc.

Semántica

Las funciones sintácticas analíticas se pueden utilizar para definir la semántica de un lenguaje de programación. Para definir el significado de los términos aritméticos descritos anteriormente, necesitamos dos funciones más de naturaleza semántica, uno analítico y otro sintético. Si el término t es una constante, entonces val (t) es el número que t denota. Si α es un número mkconst (α) es la expresión simbólica que denota este número. Tenemos las relaciones obvias 

1. val (mkconst (α)) = α
2. isconst (mkconst (α))
3. isconst (t) ⊃ mkconst (val (t)) = t

Ahora podemos definir el significado de los términos diciendo que el valor de un término para un vector de estado ξ viene dado por 

Podemos ir más lejos y describir el significado de un programa en un lenguaje de programación de la siguiente manera: El significado de un programa se define por su efecto en el estado del vector. Es cierto que esta definición deberá elaborarse para tener en cuenta la entrada y la salida. 

En el caso de ALGOL deberíamos tener una función

ξ = algol (π, ξ), 

que da el valor ξ del vector de estado después de que el programa ALGOL π se haya detenido, dado que se inició al principio y que el vector de estadoin icialmente era ξ. Esperamos publicar en otro lugar una descripción recursiva del significado de un pequeño subconjunto de ALGOL. 

Las reglas de traducción también se pueden describir formalmente. A saber,

1. Una máquina se describe mediante una función
   x = máquina (p, x)
   dando el efecto de operar el programa de máquina p en un vector de máquina x.
2. Una representación invertible x = rep (ξ) de un vector de estado como una máquina se da el vector.
3. Una función p = trans (π) que traduce programas fuente a máquina se dan programas.
   La exactitud de la traducción se define por la ecuación
   
   rep (algol (π, ξ)) = máquina (trans (π), rep (ξ)). 

Cabe señalar que trans (π) es una función abstracta y no un programa de máquina . Para describir los compiladores, necesitamos otra función abstracta invertible , u = repp (π), que da una representación del programa fuente en la memoria de la máquina lista para ser traducida. Un compilador es entonces un programa de máquina tal que trans (π) = máquina (compilador, repp (π)).

Las limitaciones de las máquinas y los hombres como solucionadores de problemas

¿Puede un hombre hacer un programa de computadora que sea tan inteligente como él? La pregunta tiene dos partes. Primero, preguntamos si es posible en principio, en vista de los resultados matemáticos sobre indecidibilidad e incompletitud, la segunda parte es una cuestión del estado de la programación en lo que respecta a inteligencia artificial. Incluso si la respuesta a la primera pregunta es "no", uno todavía puede intentar llegar lo más lejos posible en la resolución de problemas por máquina.

Supongo que, en principio, no existe tal limitación. Sin embargo, la discusión completa involucra las partes más profundas de la teoría de la función recursiva y no se han desarrollado todas las matemáticas necesarias.

Considere el problema de decidir si una oración de cálculo bajo de predicados es un teorema. Muchos problemas de las matemáticas actuales o de interés científico puede formularse de esta forma y ​​este problema resulta equivalente a muchos otros problemas, incluido el problema de determinar si un programa en una computadora con memoria ilimitada se detendrá alguna vez. 

Según Post, esto equivale a decidir si un número entero es un miembro de lo que Post llama un conjunto creativo. Myhill demostró que todo conjunto creativo es equivalentes en un sentido bastante fuerte, de modo que en realidad sólo hay un clase de problemas en este nivel de insolubilidad.

Sobre este problema se conocen los siguientes hechos:

1. Existe un procedimiento que hará lo siguiente: Si el número está en el conjunto creativo, el procedimiento dirá "sí" y si el número no está en el conjunto creativo, el procedimiento no dirá "sí", puede decir "no" o puede ejecutarse de forma indefinida.
2. No existe un procedimiento que siempre diga "sí" cuando la respuesta es "sí", y siempre dirá "no" cuando la respuesta sea "no", si un procedimiento tiene la propiedad (1) que a veces debe ejecutarse indefinidamente. Por tanto, no hay procedimiento que siempre puede decidir definitivamente si un número es miembro de un conjunto creativo, o de manera equivalente, si una oración del predicado inferior el cálculo es un teorema, o si un programa ALGOL con una entrada dada nunca parará. Este es el sentido en el que estos problemas no tienen solución.
3. Ahora llegamos al sorprendente resultado de Post. Podríamos intentar hacerlo también como sea posible. Es decir, podemos intentar encontrar un procedimiento que siempre diga "sí" cuando la respuesta es "sí", y nunca dice "sí" cuando la respuesta es "no" y que dice "no" para una clase tan grande de casos negativos como sea posible, por lo tanto delimitando el conjunto de casos en los que el procedimiento continúa indefinidamente tanto como podamos. Post demostró que ni siquiera se puede hacer lo mejor posible. Es decir, Post dio un procedimiento que, al recibir cualquier otra decisión parcial procedimiento, daría uno mejor. El mejor procedimiento decide todos los casos el primer procedimiento decidido, y una clase infinita de nuevos. Primero vista esto parece sugerir que Emil Post era más inteligente que cualquier otro posible máquina, aunque el propio Post se abstuvo modestamente de dibujar este conclusión. Cualquiera que sea el programa que proponga, Post puede hacerlo mejor. Sin embargo, esto es injusto para los programas. A saber, el procedimiento de mejora de Post es en sí mismo mecánico y puede llevarse a cabo por máquina, de modo que la máquina puede mejorar su propio procedimiento o incluso puede mejorar la publicación, si se le da una descripción de los propios métodos de Post para tratar de decidir oraciones del predicado inferior cálculo. Es como un concurso para ver quién puede nombrar el mayor número. El hecho de que pueda sumar uno a cualquier número que des, no prueba que sea mejor que tu.
4. Sin embargo, la situación es más complicada que esto. Obviamente, el proceso de mejora puede llevarse a cabo un número finito de veces y poco pensamiento muestra que el proceso se puede llevar a cabo un número infinito de veces. Es decir, sea p el procedimiento original y la mejora de Post procedimiento se llamará P, entonces P n p representa el procedimiento original mejorado n veces. Podemos definir P ω p como un procedimiento que aplica p durante un tiempo, luego P D por un tiempo, luego p nuevamente, luego P p , luego P 2 p, luego p, luego P p , luego P 2 p, entonces P 3 p, etc. Este procedimiento decidirá cualquier problema que cualquier P n voluntad decidir, por lo que con razón puede llamarse P ω p. Sin embargo, P ω p es en sí mismo sujeto al proceso de mejora original de Post y el resultado puede llamarse P ω + 1 p. ¿Hasta dónde puede llegar esto? La respuesta es técnica. Es decir, dado cualquier recursivoα ordinal transfinito, se puede definir P α p. Un ordinal recursivo es un recursivo ordenamiento de los enteros que es un buen ordenamiento en el sentido de que cualquier subconjunto delos números enteros tienen un miembro mínimo en el sentido del orden. Por lo tanto, tenemos un concurso para tratar de nombrar el ordinal recursivo más grande. Aquí parece que estamos atascado, porque el límite de los ordinales recursivos no es recursivo. Sin embargo, esto no excluye la posibilidad de que haya una mejora diferente proceso Q, de modo que Qp es mejor que P α p para cualquier α ordinal recursivo.
5. Hay otra complicación más. Suponga que alguien nombra lo que reclamaciones es un gran ordinal recursivo. Nosotros, o nuestro programa, podemos nombrar un agregando uno, pero ¿Cómo sabemos que el procedimiento que él afirma es un ordenamiento recursivo, ¿de verdad? Dice que lo ha probado en algún sistema de la aritmética. En primer lugar, puede que no estemos seguros de que su sistema dela aritmética es correcta o incluso consistente. Pero incluso si el sistema es correcto, según el teorema de Gödel, está incompleto. En particular, hay ordinales que no se puede probar que sean así en ese sistema. Rosenbloom, en su libro "Elementos de lógica matemática" llegó a la conclusión de que el hombre era en principio superior a las máquinas porque, dado cualquier sistema formal de aritmetica, podría dar un sistema más fuerte que contenga oraciones verdaderas y probables eso no se pudo probar en el sistema original. Lo que Rosenbloom se perdió presumiblemente por razones sentimentales, es que el procedimiento de mejora es en sí mismo mecánico, y sujeto a iteración a través de los ordinales recursivos, por lo queque estamos de vuelta en la gran carrera ordinal. De nuevo nos enfrentamos a la complicación de probar que nuestros grandes ordinales son realmente ordinales.
6. Estas consideraciones tienen poca importancia práctica en su presente formar. Es decir, el proceso de mejora original es tal que la mejora Es probable que el proceso sea demasiado lento para obtener resultados en un tiempo razonable, ya sea realizado por el hombre o por la máquina. Sin embargo, puede ser posible poner este jerarquía en alguna forma utilizable. Para concluir, permítanme reafirmar que la cuestión de si existen limitaciones en principio de los problemas que el hombre puede hacer que las máquinas resuelvan comparado con su propia capacidad para resolver problemas, realmente es una técnica pregunta en la teoría de la función recursiva.

Referencias

[McC62] John McCarthy. Verificación de pruebas matemáticas por computadora. En Proceedings Symposium on Recursive Function Theory (1961). Sociedad Americana de Matemáticas, 1962.

[McC63] J. McCarthy. Una base para una teoría matemática de la computación. 1 en
P. Braffort y D. Hirschberg, editores, Programación informática y Sistemas formales, páginas 33–70. Holanda Septentrional, Amsterdam, 1963

DSN_XP y la sentencia GoTo

 Estructura del software 

Un caso contra la declaración GO TO.

Desde hace varios años estoy familiarizado con la observación de que la calidad de los programadores es una función decreciente de la densidad de instrucciones go to en los programas que producen. Más tarde descubrí por qué el uso de la instrucción go to tiene efectos tan desastrosos y me convencí de que la instrucción go to debería eliminarse de todos los lenguajes de programación de "nivel superior" (es decir, todo excepto —quizás— código simple de máquina). 

En ese momento no le di demasiada importancia a este descubrimiento; Ahora presento mis consideraciones para su publicación porque en discusiones muy recientes en las que surgió el tema, se me ha instado a hacerlo.

Mi primer comentario es que, aunque la actividad del programador termina cuando ha construido un programa correcto, el proceso que tiene lugar bajo el control de su programa es el verdadero tema de su actividad, ya que es este proceso el que tiene que lograr el efecto deseado, es este proceso el que en su comportamiento dinámico debe satisfacer las especificaciones deseadas. Sin embargo, una vez realizado el programa, se delega en la máquina la “realización” del proceso correspondiente.

Mi segunda observación es que nuestros poderes intelectuales están más bien orientados a dominar las relaciones estáticas y que nuestros poderes para visualizar procesos que evolucionan en el tiempo están relativamente poco desarrollados. Por esa razón, debemos hacer (como programadores sabios conscientes de nuestras limitaciones) nuestro mejor esfuerzo para acortar la brecha conceptual entre el programa estático y el proceso dinámico, para hacer la correspondencia entre el programa (esparcido en el espacio de texto) y el proceso ( extendido en el tiempo) lo más trivial posible.

Consideremos ahora cómo podemos caracterizar el progreso de un proceso. (Puedes pensar en esta pregunta de una manera muy concreta: supongamos que un proceso, considerado como una sucesión temporal de acciones, se detiene después de una acción arbitraria, ¿qué datos tenemos que arreglar para que podamos rehacer el proceso hasta que ¿El mismo punto?) Si el texto del programa es una pura concatenación de, digamos, declaraciones de asignación (para el propósito de esta discusión consideradas como descripciones de acciones individuales), es suficiente señalar en el texto del programa a un punto entre dos acciones sucesivas descripciones. (En ausencia de ir adeclaraciones Puedo permitirme la ambigüedad sintáctica en las tres últimas palabras de la oración anterior: si las analizamos como "sucesivas (descripciones de acción)" nos referimos a sucesivas en el espacio de texto, si las analizamos como "descripciones (acciones sucesivas)" queremos decir sucesivas en el tiempo). Llamemos a tal puntero a un lugar adecuado en el texto "índice textual".

Cuando incluimos cláusulas condicionales ( si B entonces A ), cláusulas alternativas ( si B entonces A1 más A2), cláusulas de elección tal como las introdujo CARHoare ( caso [i] de ( A1, A2, ....., An )) o expresiones condicionales introducidas por J. McCarthy ( B1 → E1, B2 → E2, ....., Bn → En ), el hecho es que el progreso del proceso permanece caracterizado por un solo índice textual.

Una vez que incluimos en nuestros procedimientos de lenguaje debemos admitir que un índice textual único ya no es suficiente: en el caso de que un índice textual apunte al interior de un cuerpo de procedimiento, el progreso dinámico solo se caracteriza cuando también aportamos a qué llamada del procedimiento al que nos referimos. Con la inclusión de procedimientos podemos caracterizar el progreso del proceso a través de una secuencia de índices textuales, siendo la longitud de esta secuencia igual a la profundidad dinámica de la llamada al procedimiento.

Consideremos ahora las cláusulas de repetición (como, mientras que B repite A o repite A hasta que B). Lógicamente hablando, tales cláusulas son ahora superfluas, porque podemos expresar la repetición con la ayuda de procedimientos recursivos. Por razones de realismo, no deseo excluirlos: por un lado, las cláusulas de repetición se pueden implementar con bastante comodidad con el equipo finito actual, por otro lado, el patrón de razonamiento conocido como "inducción" nos hace bien equipados para retener nuestra capacidad intelectual, captar los procesos generados por las cláusulas de repetición. 

Con la inclusión de las cláusulas de repetición, los índices textuales ya no son suficientes para describir el progreso dinámico del proceso. Con cada entrada en una cláusula de repetición, sin embargo, podemos asociar un llamado “índice dinámico”, contando inexorablemente el número ordinal de la correspondiente repetición actual. Como las cláusulas de repetición (al igual que las llamadas a procedimientos) se pueden aplicar anidadas,

El punto principal es que los valores de estos índices están fuera del control del programador: se generan (ya sea por la redacción de su programa o por la evolución dinámica del proceso), lo desee o no. Proporcionan coordenadas independientes en las que describir el progreso del proceso.

¿Por qué necesitamos tales coordenadas independientes? La razón es, y esto parece ser inherente a los procesos secuenciales, que podemos interpretar el valor de una variable solo con respecto al progreso del proceso. Si deseamos contar el número, n decir, de las personas en una sala vacía inicialmente, podemos lograr esto mediante el aumento de n por 1 cada vez que vemos a alguien entrar en la habitación; en el momento intermedio en el que hemos observado que alguien entra en la habitación pero aún no hemos realizado el aumento posterior de n , su valor es igual al número de personas en la habitación menos uno.

El uso desenfrenado de la declaración go to tiene como consecuencia inmediata que resulta terriblemente difícil encontrar un conjunto significativo de coordenadas en las que describir el progreso del proceso. Por lo general, las personas también tienen en cuenta los valores de algunas variables bien elegidas, pero esto está fuera de discusión porque es relativo al progreso que se debe entender el significado de estos valores. 

Con la instrucción go to uno puede, por supuesto, seguir describiendo el progreso de forma única mediante un contador que cuenta el número de acciones realizadas desde el inicio del programa (es decir, una especie de reloj normalizado). La dificultad es que tal coordenada, aunque única, es completamente inútil: en tal sistema de coordenadas se vuelve un asunto extremadamente complicado definir todos esos puntos de progreso donde, digamos, n es igual al número de personas en la habitación menos uno.

La declaración go to tal como está es demasiado primitiva, es una invitación demasiado a hacer un lío en el programa. Uno puede considerar y apreciar las cláusulas consideradas como un freno a su uso. No pretendo que las cláusulas mencionadas sean exhaustivas en el sentido de que satisfagan todas las necesidades; pero cualesquiera que sean las cláusulas que se sugieran (por ejemplo, cláusulas de cancelación), deben satisfacer el requisito de que se pueda mantener un sistema de coordenadas independiente del programador para describir el proceso de una manera útil y manejable.

Es difícil terminar este artículo con un reconocimiento justo: ¿debo juzgar por quién ha sido influenciado mi pensamiento? Es bastante obvio que Peter Landin y Christopher Strachey no me dejan de influir, y que no me arrepiento de su influencia sobre mí. Finalmente, me gustaría dejar constancia (como lo recuerdo con bastante claridad) de cómo Heinz Zemanek, en la reunión previa a ALGOL a principios de 1959 en Copenhague, expresó de manera bastante explícita sus dudas sobre si la declaración go to debería tratarse en pie de igualdad sintáctica con la declaración de asignación. Hasta cierto punto me culpo por no haber sacado las consecuencias de su comentario.

La observación sobre lo indeseable de la declaración go to está lejos de ser nueva. Recuerdo haber leído la recomendación explícita de restringir el uso de la declaración go to para alarmar salidas, pero no he podido rastrearla; presumiblemente, ha sido realizado por CAR Hoare. En [1, Sec. 3.2.1] 

Wirth y Hoare juntos hacen un comentario en la misma dirección para motivar la construcción del caso: “Como el condicional, refleja la estructura dinámica de un programa más claramente que ir a declaraciones y conmutadores, y elimina la necesidad de introducir una gran cantidad de etiquetas en el programa ".

En [2] Guiseppe [sic] Jacopini parece haber demostrado la superfluidad (lógica) de la declaración go to . Sin embargo, no se recomienda el ejercicio de traducir un diagrama de flujo arbitrario más o menos mecánicamente en uno sin saltos. Entonces, no se puede esperar que el diagrama de flujo resultante sea más transparente que el original.

REFERENCIAS:

Wirth, Niklaus y Hoare, CAR Una contribución al desarrollo de ALGOL. Comm. ACM 9 (junio de 1966), 413–432.

Böhm, Corrado y Jacopini, Guiseppe. Diagramas de flujo, máquinas de Turing y lenguajes con solo dos reglas de formación. Comm. ACM 9 (mayo de 1966), 366–371.

DSN_XP y la OTAN 1968

 Sobre los informes técnicos del software

Reuniones de la OTAN 

Dagstuhl-Seminar 9635: 

"History of Software Engineering" Schloss Dagstuhl, 

August 26 - 30, 1996

The 1968/69 NATO

Software Engineering Reports

Tomado como fuente original a este enlace

Brian Randell

Departamento de Ciencias de la Computación

Universidad de Newcastle upon Tyne

Informes técnicos de ingeniería de software 1968/69

Reuniones Ingeniería de Software OTAN

La idea de la primera Conferencia de Ingeniería de Software de la OTAN y en particular la de adoptar el entonces prácticamente desconocido término "ingeniería de software" como su título (deliberadamente provocador), creo que vino originalmente del profesor Fritz Bauer. 

F.L. Bauer

Del mismo modo, si mi memoria no me falla, fue él quien destacó la importancia de proporcionar un informe sobre la conferencia y quien nos convenció a Peter Naur y a mí de ser los editores. (En ese momento trabajaba en IBM TJ Watson Research Center en los EE. UU., Pero conocí a "Onkel Fritz" por haber sido miembro del Comité IFIP Algol durante varios años). 

B.Randell

P. Naur

Como resultado, se acordó que Peter y yo nos quedaríamos una semana más después de la conferencia para editar el borrador del informe, aunque acordamos trasladarnos de Garmisch-Partenkirchen a Munich durante esta segunda semana.

Conferencia sobre el software

Citando nuestro Informe de la Conferencia de 1968 [Naur y Randell, enero de 1969]:

"El trabajo real en el informe fue una empresa conjunta de varias personas. La gran cantidad de mecanografía y otras tareas de oficina, tanto durante la conferencia como durante un período posterior, fueron realizadas por la señorita Doris Angemeyer, la señorita Enid Austin, la señorita Petra Dandler, la señora Dagmar Hanisch y la señorita Erika Stief. 

Durante la conferencia, Larry Flanigan, Ian Hugo y Manfred Paul tomaron notas. Ian Hugo también manejó la grabadora. La revisión y clasificación de los pasajes de las contribuciones escritas y las discusiones estuvo a cargo de Larry Flanigan , Bernard Galler, David Gries, Ian Hugo, Peter Naur, Brian Randell y Gerd Sapper. 

L.K. Flanigan

I.Hugo

M. Paul

B. Galler

D. Gries

La redacción final fue realizada por Peter Naur y Brian Randell. La preparación de la copia final mecanografiada del informe fue realizada por la señorita Kirsten Anderson en Regnecentralen, Copenhague, bajo la dirección de Peter Naur ".

Aportes colectivos

Reuniones OTAN

Como yo y otros participantes hemos testificado desde entonces, se desarrolló una atmósfera tremendamente emocionada y entusiasta en la conferencia. Esto fue cuando los participantes se dieron cuenta del grado de preocupación común acerca de lo que algunos estaban dispuestos a denominar la "crisis del software" y surgió un acuerdo general sobre la importancia de tratar de convencer no solo a otros colegas, sino también a los responsables políticos en todos los niveles. de la gravedad de los problemas que se estaban discutiendo. 

Por lo tanto, a lo largo de la conferencia hubo un énfasis continuo en cómo se podía informar mejor de la conferencia. De hecho, al final de la conferencia, Peter y yo habíamos recibido una propuesta de estructura detallada para la parte principal del informe. Esto se basó en una estructuración lógica de los temas cubiertos, en lugar de seguir un modelo estricto de la forma real en que la conferencia sucedió.

Peter y yo estuvimos muy contentos de tener tal orientación sobre la estructura y el contenido general del informe, ya que ambos deseábamos crear algo que fuera verdaderamente un informe de conferencia, en lugar de un mero informe personal sobre una conferencia a la que habíamos asistido. 

De hecho, Peter argumentó que no deberíamos proporcionar ningún texto adicional nosotros mismos, sino que deberíamos producir la parte principal del informe simplemente completando la estructura acordada con citas directas adecuadas de contribuciones habladas y escritas a conferencias. 

Sin embargo, le convencí de que breves introducciones editoriales y pasajes de enlace mejorarían la continuidad y la legibilidad general del informe. Entonces, (junto con la decisión de que una pequeña selección de los textos escritos también se incorporarían en su totalidad como apéndices), llegamos a la forma final del informe.

Documentación técnica 

En Munich trabajamos a partir de las notas tomadas por los relatores, que habíamos arreglado para que fueran tecleadas, tal como se hicieron, a los números de las grabaciones en las cintas grabadas. Las cintas no se transcribieron sistemáticamente, ya que este proceso suele tardar entre cinco y seis veces en tiempo real. Más bien, usamos las notas de los relatores y nuestras memorias para localizar secciones particularmente interesantes y oportunas de las cintas y solo estas fueron transcritas. 

De esta manera construimos un gran conjunto de citas transcritas, que complementamos con citas adecuadas de las contribuciones escritas. Luego, para cada sección del informe, uno u otro de nosotros intentó convertir el conjunto relevante de citas en un relato coherente y pseudo-literal de la discusión sobre ese tema.

El trabajo en Munich fue tan agradable como intenso y brindó muchas oportunidades para volver a escuchar algunas de las discusiones más memorables, de modo que muchas de ellas quedaron grabadas mucho más profundamente en mi memoria y tuvieron un efecto más fuerte en mis posteriores investigaciones, de lo que hubiera sido el caso si yo simplemente hubiera participado en la conferencia. 

El informe estaba prácticamente completo al final de la semana en Munich, y luego Peter Naur se llevó todo con él a Copenhague, donde se produjo un primer borrador completo utilizando una máquina de escribir controlada por cinta de papel (supongo que era un redactor flexible), una técnica que parecía novela en ese momento, pero que él nos aconsejó acertadamente ayudaría mucho en la preparación de un texto final preciso. 

Cuerpo de conocimientos

(Mi memoria me dice que este borrador se circuló luego a los participantes para comentarios y correcciones antes de ser impreso. La impresión y distribución reales fueron realizadas por la OTAN, y el Informe estuvo disponible en enero de 1969, solo tres meses después de la conferencia. 

Las copias se distribuyeron gratuitamente a pedido y rápidamente logró una amplia distribución y atención. Una de las reacciones más agradables entre los participantes fue la de Doug McIlroy, quien lo describió como "¡un triunfo de las citas mal aplicadas!". (Fue solo muchos años después que supe por un breve artículo de Mary Shaw que Al Perlis entregó copias del informe a los estudiantes graduados en ciencias de la computación de CMU con las palabras "Aquí, lea esto. Cambiará su vida". [ Shaw 1989])

Tal fue el éxito de la primera conferencia que los organizadores buscaron y obtuvieron el patrocinio de la OTAN para una segunda conferencia, que se celebraría un año después en Italia. 

Peter Naur, sabiamente, no estaba dispuesto a repetir su labor editorial, pero yo, más bien precipitadamente, después de algunas dudas iniciales acepté hacerlo, esta vez en cooperación con John Buxton. 

Según recuerdo, los planes para la segunda conferencia se discutieron en una reunión celebrada en una oficina en la sede de la OTAN. Mi principal recuerdo es que la oficina estaba presidida por una caja fuerte muy grande e impresionante, que para mi diversión se reveló completamente vacía cuando nuestro anfitrión, al final de la reunión, la abrió para guardar las botellas de las que bebe y que nos habían servido antes. 

Durante estas discusiones preparatorias proporcioné, basado en mi experiencia ganada con esfuerzo en Munich, lo que con orgullo consideré una lista muy bien pensada de requisitos con respecto a las instalaciones que necesitaríamos tener en Roma. (El más importante de ellos fue que el equipo editorial debería tener acceso a tiempo completo a un hablante de italiano que ayudaría a resolver cualquier dificultad que pudiera surgir, de esto, más adelante).

Mi (sobre) confianza inicial también se debió en parte al hecho de que esta segunda vez, a John y a mí nos habían ofrecido los servicios de tiempo completo de dos escritores técnicos experimentados de ICL, a saber, Ian Hugo (que había estado muy involucrado en la preparación del primer informe) y Rod Ellis, y cada uno de nosotros había dispuesto que nos acompañaran a Roma una secretaria experta, Margaret Chamberlain y Ann Laybourn, respectivamente. 

Ian, por cierto, pasó a ayudar a fundar Infotech, una empresa que posteriormente, durante un período de años, organizó una gran cantidad de conferencias técnicas, cada una de las cuales condujo a la publicación de un Informe sobre el estado del arte, cuyo formato coincidía estrechamente al de los informes de la OTAN.

Segunda conferencia

Informe de conferencia

En el evento, la segunda conferencia fue mucho menos armoniosa y exitosa que la primera y nuestra tarea editorial resultó ser muy diferente. Citando nuestra introducción al Informe de la Conferencia de 1969 [Buxton y Randell, abril de 1970]:

Finalmente, la seriedad de esta brecha de comunicación y la comprensión de que no era más que un reflejo de la situación en el mundo real, hicieron que la brecha en sí se convirtiera en un tema importante de discusión. . . . . En vista de estos acontecimientos, no es de extrañar que los editores no recibieran un resumen claro de la conferencia en cuanto a la estructura y contenido del informe ".

Por lo tanto, la tarea de producir un informe que fuera a la vez respetable y razonablemente preciso fue mucho más difícil de lo que podría haber imaginado y no fue ayudado por todo tipo de dificultades que sufrimos, casi todas las cuales se habrían resuelto mucho más fácilmente si se había proporcionado un organizador local según lo acordado. No obstante, algunos de los participantes expresaron su grata sorpresa por nuestro informe, cuando recibieron posteriormente un borrador para su verificación, y evidentemente lo consideraron más positivamente que la conferencia que pretendía documentar.

... Todas estas adversidades, cuyo impacto habría sido mucho menor si hubiéramos tenido el asistente local prometido, de hecho ayudaron a unirnos como equipo. El brillante don de Rod Ellis para el mimetismo también ayudó al proporcionar muchos momentos agradables de hilaridad general, ya que, adaptando su elección al tema en cuestión, intercambió sin esfuerzo conversaciones con nosotros entre las voces de Edsger Dijkstra, Fritz Bauer y muchos de los demás participantes cuyos comentarios de la conferencia habían sido capturados para la posteridad por nuestras grabadoras.

De hecho, terminamos el informe temprano el viernes por la noche, a tiempo para una cena de celebración final, una vez que Rod e Ian habían regresado de la Universidad de Roma, donde habían hecho copias del informe preliminar (y, de manera bastante apropiada, roto la fotocopiadora). Sin embargo, fue en consonancia con el resto de la semana que casi todos los camareros de restaurantes en Roma eligieron ese momento para ir a la huelga; de hecho, vimos una gran procesión de ellos desfilar frente a nuestras ventanas gritando y agitando pancartas, de modo que tuvimos que contentarnos con una excelente cena en el hotel.

Algo que había olvidado por completo hasta que volví a leer la introducción del Informe de 1969 mientras preparaba este breve relato fue que este segundo informe se redactó en la Universidad de Newcastle upon Tyne, a donde me había mudado de IBM en el ínterin. De hecho, algunos de los primeros trabajos del mundo sobre composición tipográfica informatizada se habían realizado en Newcastle. Citando del informe: "La versión final del informe fue preparada por Kynock Press, utilizando su sistema de tipografía por computadora (ver Cox, NSM y Heath, WA: 'La integración del proceso de publicación con datos manipulados por computadora'. Papel presentado en el Seminario sobre sistemas de publicación automatizados, 7-13 de septiembre de 1969, Universidad de Newcastle upon Tyne, Proyecto de investigación de composición tipográfica por computadora), el procesamiento preliminar del texto se realizó utilizando el sistema de manejo de archivos de Newcastle.

A diferencia de la primera conferencia, en la que se aceptó plenamente que el término ingeniería de software expresaba una necesidad más que una realidad, en Roma ya existía una ligera tendencia a hablar como si el tema ya existiera. Y quedó claro durante la conferencia que los organizadores tenían una agenda oculta, a saber, la de persuadir a la OTAN para que financie la creación de un Instituto Internacional de Ingeniería de Software. Sin embargo, las cosas no salieron según su plan. Las sesiones de discusión que estaban destinadas a proporcionar evidencia de un fuerte y amplio apoyo a esta propuesta estuvieron marcadas por un considerable escepticismo y llevaron a uno de los participantes, Tom Simpson de IBM, a escribir una espléndida sátira corta sobre " Masterpiece Engineering ".

John y yo decidimos más tarde que el texto de Tom Simpson proporcionaría un conjunto apropiado, aunque algo irreverente, de observaciones finales a la parte principal del informe. Sin embargo, en el evento fuimos "persuadidos" por los organizadores de la conferencia para eliminar este texto del informe. Estoy seguro de que esto se debió únicamente a sus referencias sarcásticas a un "Instituto de ingeniería de obra maestra". Siempre he lamentado que cediéramos a la presión y permitiéramos que nuestro informe fuera censurado de esa manera. Entonces, a modo de expiación, adjunto una copia del texto como Apéndice a este breve conjunto de reminiscencias.

No fue una sorpresa para ninguno de los participantes en la conferencia de Roma que no se hiciera ningún intento de continuar la serie de conferencias de la OTAN, pero el tren de la ingeniería de software comenzó a rodar a medida que muchas personas comenzaron a usar el término para describir su trabajo, en mi opinión a menudo con muy poca justificación. Reaccionando a esta situación, durante muchos años hice un punto particular de negarme a usar el término o estar asociado con cualquier evento que lo usara. De hecho, no fue hasta unos diez años después que cedí, al aceptar una invitación para ser uno de los oradores invitados en la Conferencia Internacional de Ingeniería de Software en Munich en 1979. 

Los otros oradores invitados fueron Barry Boehm, Wlad Turski y Edsger Dijkstra. Me pidieron que hablara sobre ingeniería de software como era en 1968, Barry sobre el estado actual, Habló sobre el futuro de la ingeniería de software y Edsger sobre cómo debería desarrollarse. Me divertí mucho preparando mi artículo [Randell 1979] ya que incluí numerosos desafíos implícitos a Barry, cuya charla estaba programada inmediatamente después de la mía, para justificar afirmaciones sobre el progreso desde 1968. Ignoró cuidadosamente todos estos desafíos, o tal vez no los reconoció. Lamento decir.

En mi intento de 1979 de describir la escena de 1968/9, no me pareció apropiado insistir en mis experiencias al ayudar a editar los dos informes de la OTAN, por lo que estoy muy contento de haber tenido motivos para completar mis reminiscencias personales de ingeniería de software, así que ... hablar. Agradezco a los organizadores de esta conferencia por darme esta oportunidad y, en particular, un medio tardío para publicar el texto que fue tan tristemente censurado del Informe de la Conferencia de 1969.

Referencias

1. JN Buxton y B. Randell, (Ed.). Técnicas de ingeniería de software: Informe sobre una conferencia patrocinada por el Comité de Ciencia de la OTAN, Roma, Italia, 27 al 31 de octubre de 1969, Bruselas, División de Asuntos Científicos, OTAN, abril de 1970, 164 p.

2. P. Naur y B. Randell, (Ed.). Ingeniería de software: Informe de una conferencia patrocinada por el Comité Científico de la OTAN, Garmisch, Alemania, del 7 al 11 de octubre de 1968, Bruselas, División de Asuntos Científicos, OTAN, enero de 1969, 231 p.

3. B. Randell. "Ingeniería de software en 1968", en Proc. del IV Int. Conf. sobre Ingeniería de Software, págs. 1-10, Munich, 1979.

4. M. Shaw. "Recuerdos de un estudiante de posgrado (para el panel," Una retrospectiva de veinte años de las conferencias de ingeniería de software de la OTAN ")," en Proc. 11 ° Int. Conf. sobre Ingeniería de Software, vol. 11, págs. 99-100, 1989. (Reimpreso en Annals of the History of Computing, Anecdotes Department, 11, 2, 1989, págs.141-143).

DSN_XP y el Documento de Visión

Herramientas DSN_XP

Documento de Visión 

Un observador siempre registra todo lo que observa, esa es su función, por lo tanto es preciso ubicarse en un sitio con mayor perspectiva de visión [DSN_XP]

DSN_XP fue inicialmente conceptuada como una metodología para el desarrollo de software, su diseño evidenció poco a poco que podía ser utilizada para realizar investigaciones casi de cualquier tipo, ya no sólo importaba cómo fabricar productos software… sino que, era posible investigar a la misma Ingeniería del Software (IS) y sus metodologías.

Un poco de historia 

Nuestra primera referencia hacia el método de observación y registro en las investigaciones técnicas DSN_XP la encontramos cuando desarmamos MSF como marco de trabajo referente para el desarrollo de software, gracias a la referencias teóricas y la dirección técnica que tuvimos durante el desarrollo de la tesis, acompañados por nuestro Director de Tesis, el Ing. Patricio Negrete.

Ingeniero Patricio Negrete

Patricio tuvo la gentileza de acompañarnos durante todo el trayecto que implicó el desarrollo de nuestro marco teórico de conocimientos para el desarrollo del modelo de ciclo de vida de las tesis de grado que tuviesen que realizar software como parte de su propuesta.

MSF y su visionar

Modelo MSF 3.0 tomado como referente para el desarrollo de nuestra propuesta

DSN_XP entra en contacto con su primer marco de trabajo (a diferencia de los otros métodos que estaban siendo denominados como metodologías de desarrollo), MSF Microsoft Solutions Framework en su versión 3.0 lo que nos permitió estudiar la fase denominada como VISIÓN, dentro de la cual se elabora un documento técnico denominado como Documento de Visión. 

El documento de visión es una herramienta documental propia de la arquitectura técnica al servicio del negocio. pues mientras los métodos de desarrollo se enfocaban en el software, MSF introduce en su mirada arquitectónica, la arquitectura empresarial bajo la noción del entendimiento del negocio como un elemento fundamental para la certeza del proyecto tecnológico a desarrollar que implicaba el conceptuar una solución basada en la tecnología de Microsoft.

Nota: El documento de visión fue transformándose en las siguientes versiones de DSN_XP a su versión  1.0 en herramientas más agiles y centradas en el cliente como lo son el café temático y la propuesta de INCEPTION.

Esta entrada no profundiza en el modelo MSF 3.0, pero se enfoca en describir un artefacto adoptado por DSN_XP que podía ser utilizado en el modelo que estábamos diseñando para el desarrollo de software como tesis de grado en la universidad.

Esquema conceptual de la visión

La meta de la Fase de Visión, es lograr alcanzar aprobar un hito de acuerdo a lo visionado con el equipo del proyecto y la organización, el cual se culmina el trabajo del equipo durante esta fase y significa un acuerdo entre el cliente y el equipo sobre los aspectos críticos del proyecto.

Dentro de los productos considerados como entregables de esta fase se encuentra el documento de visión que contiene los lineamientos del producto que va a ser desarrollado, las necesidades que deben ser atendidas por esta visión, sus características funcionales y un cronograma inicial.

Para un documento de visión efectivo, su desarrollo debe terminar con el fin de la Fase de Visión y debe incluir los siguientes elementos:

• Una sentencia de la visión.
• Una investigación de escenarios de usuarios.
• Información competitiva.
• Características principales y funcionales.
• Cronograma estimado.

Escribir una sentencia de la visión

Durante los años de1960, cuando los USA trataban de colocar al hombre en la luna, su presidente creó una visión para cada uno de aquellos que estuviesen detrás del proyecto en el país, parafraseando sería:

En la década siguiente, enviaremos al hombre a la luna y lo traeremos de vuelta a salvo.

La sentencia de visión debe poseer los atributos de metas SMART, que son:

• Específico
• Medible
• Alcanzable
• Relevante
• Basada en tiempo

Una vez presentada la sentencia de visión, cada miembro del equipo del proyecto deberá instantáneamente conocer los temas relevantes que son más importantes para cualquier factor de éxito.

en efecto, una buena regla para sintetizar la sentencia de visión es hacerla tan clara que un nuevo empleado comenzará con una buena oportunidad de trabajar hacia la solución enfocada que es consistente con las metas del negocio y su empleo actual.

Reportando las investigaciones de usuario

Cuando el equipo aprende acerca de su cliente y de sus usuarios, son los primeros logros de cada cosa que se logra. Visitas de usuarios, investigaciones contextuales, investigaciones de mercado, grupos focales e incluso visitas internacionales para ayudar a capturar la información necesaria para describir al cliente primario y sus usuarios.   Adicionalmente, esta investigación provee información para la creación de escenarios de uso que describen el cómo los usuarios trabajan actualmente y cómo trabajarían inel futuro con el producto.

Proveer información competitiva

Dado que el producto provee un retorno apropiado de inversión tanto ahora como en los paisajes competitivos del futuro. ¿Qué otra solución sería posible para satisfacer las necesidades del cliente?

El equipo debe asegurarse que el producto y su visión, resuelvan las necesidades o el problema del cliente de mejor manera que cualquier otra solución variable y que se encuentre en la forma adecuada de justificar la inversión.

La mejor solución al problema del cliente no suele ser siempre un producto basado en software y si lo fuese, no deberá asumirse que  el software debe construirse desde un boceto.  Se requiere investigar otras soluciones provistas por sistemas que pueden dar pauta de las funcionalidades requeridas para lograr satisfacer la necesidad o problema e incluso identificando una solución comercial para dicho problema.

DSN_XP y el Marco Regenerativo

 Diseño Regenerativo

Marco de trabajo para diseños regenerativos

DSN_XP entra en contacto con el marco regenerativo gracias a la base de conocimientos que se imparte por parte del equipo de EL MANZANO y su proyecto INCUBAR.

Marco regenerativo

Dentro de las capacitaciones sobre emprendimientos de impacto aplicando este marco regenerativo, DSN_XP toma las áreas de conocimiento que dan soporte a la toma de decisiones sobre las cuales deben equilibrarse tanto la situación actual en el presente, así como la planificación responsable del uso de los recursos comunitarios en el futuro y es justamente esta noción de comunidad la que sostiene la mirada teórica de este marco de trabajo, a saber:

La mirada de la industria y del negocio son cubiertas por la perspectiva que denominamos BusinessView, la ingeniería del software y los modelos del ciclo de vida son estudiados por la perspectiva del SoftwareView, sin embargo, el estudio de los aspectos que involucran el pensamiento humano y su inteligencia y comportamiento como asentamiento social son estudiados por la perspectiva TeamView y esta perspectiva involucra el resolver la pregunta fundamental en el siglo 20 ¿Qué puedo hacer desde mis propias capacidades? dentro de esta perspectiva encontramos nuestro estudio denominado #OccupyMySelf.

¿Qué es el diseño regenerativo?

Diseño energético y su impacto

Responder a esta pregunta requiere dejar en claro algunos conceptos pues se necesitan en dicho proceso e introducir al pensamiento sistémico como uno de los elementos a considerar dentro de la trayectoria regenerativa.

Las dimensiones del marco regenerativo son tanto a nivel de consumo energético, como a nivel de impacto por el tipo de asentamiento social que  se tiene en base al diseño.

En estos tiempos de creciente incertidumbre y volatilidad, debemos tener la capacidad para adaptarnos y responder a los desafíos más importantes del mundo con el objetivo de alcanzar una verdadera prosperidad global.

Una solución es un sistema económico circular que reestructure las finanzas y los negocios para priorizar la sustentabilidad y la accesibilidad a través de nuestra cadena global de suministro de recursos, garantizando así los medios de subsistencia en todo el mundo. Este sistema regenerativo estará formado por una nueva era de conciencia social y cultural, que aprecie verdaderamente la interconexión de los sistemas socioeconómicos de la humanidad y nuestro entorno. El principal desafío será asegurar que el sistema global se alinee con los principios fundamentales y universales de la vida.

Para lograr esto, primero debemos considerar a la riqueza de una manera holística, midiendo constantemente la riqueza financiera junto con el capital ambiental, cultural, social e intelectual. Es más fácil decirlo que hacerlo, ya que la humanidad ha seguido su camino de crecimiento económico a cualquier costo social y ambiental desde la Revolución Industrial. 

El modelo económico de “tomar, hacer y disponer”, característico de la época, está colapsando a medida que el crecimiento exponencial de la población y el consumo excesivo de recursos causan una miríada de presiones globales sin precedentes.

Pensamiento regenerativo

Como sistema regenerativo, la economía circular puede tener muchas consecuencias positivas que mejoran la calidad de vida, la comunidad y el medio ambiente.

Crear valor para cada jugador en su ecosistema más amplio ayudará a que el sistema prospere a largo plazo. 

Nutrir a las personas (piense en los usuarios, empleados o socios) y a los sistemas naturales que se basan directamente en su organización o la apoyan puede ser una fuente de crecimiento, creatividad e innovación. Por ejemplo, la creación de una red de producción local brinda apoyo económico a su área circundante, lo que a su vez podría brindar a la comunidad la riqueza y la capacidad para comprar su producto o servicio.

Pasos

1. Considere apoyar la circularidad tanto de su organización como de su mercado fomentando el bienestar, la educación o la prosperidad de sus empleados, usuarios y sus comunidades.
   ¿Qué sucede si invirtiera en la propiedad, la educación o el bienestar de los empleados en todos los lugares donde opera? ¿Cómo podrías hacer esto? Enumere tantas opciones como sea posible.
   Si implementó algunas de estas ideas, ¿Cómo podría mejorar la productividad?,¿Cómo podría una comunidad más saludable, bien educada y próspera, que está conectada con la naturaleza, apoyar mejor a su organización tanto a corto como a largo plazo? ¿Qué beneficios podría traer esto en términos de retención y atracción de talento? ¿O aumentar la confianza y la lealtad de la comunidad local? ¿Cómo podría esto, a su vez, mejorar la prosperidad de su organización?
2. A continuación, piense en tantas formas como sea posible de medir este tipo de impacto dentro de su sistema. Esto lo ayudará a demostrar el valor de sus esfuerzos e inversiones desde el principio, y le permitirá construir una narrativa sólida para socios o inversores existentes y potenciales. 
3. Si desea un poco más de inspiración, vea el video de Douglas Rushkoff que explica el poder regenerativo de una economía más circular.