miércoles, noviembre 28, 2012

BREVE RECUERDO DEL LENGUAJE DE PROGRAMACIÓN MIXAL

Parte del texto presentado aquí proviene de un artículo que publicaré muy pronto. El texto fuente (reproducido en esta entrada) está escrito en TeX, el sistema/lenguaje de programación/tipográfico diseñado por el propio Knuth en la década de los 1970. Se trata de todo un compilador que traduce un archivo fuente (del tipo Mark-Up) en un archivo de impresión.
Es un breve relato de cómo terminé programando computadoras casi por inercia. Si me dediqué a esto (nada brillante que he sido por cierto; tal vez por eso admiro tanto a Knuth quien si ha sido matemático brillante y gran autor) es porque, la verdad sea dicha, no supe qué más hacer en la vida. Me he metido en complejidades literarias y matemáticas y ya olvidé el camino desde donde partí.

\title{BREVE RECUERDO DEL LENGUAJE DE PROGRAMACI\'ON\\
        \texttt{MIXAL}}

\author{Jos\'e Portillo Lugo\thanks{por publicar.}\\
     Historia de la computaci\'on\\
     \texttt{jportillo34@yahoo.com}}

\date{Diciembre 5, 2012}

\maketitle

\begin{abstract}
    Breve relato sobre el tiempo perdido, el orden y la disciplina en el trabajo.
\end{abstract}

\vspace{5 mm}

\begin{quote}
   \begin{flushright}
      \textit{And now I see with eye serene}\\
      \textit{The very pulse of the machine.}\\
      - William Wordsworth, She Was a Phantom of Delight (1804)\\
      (tomada de Fundamental Algorithms - Knuth, Donald E. - 1973)\\
   \end{flushright}
\end{quote}
\\
And now I see with eye serene
The very pulse of the machine.
 - William Wordsworth, She Was a Phantom of Delight (1804)
(tomada de Fundamental Algorithms - Knuth, Donald E. - 1973)

Hace 27 a\~nos yo era un estudiante de segundo semestre de computaci\'on sin m\'as conocimiento sobre las materias en curso. Un estudiante regular con calificaciones regulares, sin mucho inter\'es por la materia. Por supuesto, para ese entonces (mediados de la d\'ecada de los 1980) la computaci\'on ten\'ia casi seis d\'ecadas de antiguedad como disciplina, sobre todo la programaci\'on de computadoras. D\'ecadas de historia que yo ignoraba
completamente. Fue en esa \'epoca que escuch\'e hablar por primera vez sobre un texto de programación
de computadoras llamado \textit{The Art of Computer Programming}.

Su autor era el Prof. Donald Knuth, un matem\'atico quien hab\'ia dedicado gran parte de su
vida a dise\~nar traductores de lenguajes de alto nivel y assemblers durante los a\~nos 1960. Sus habilidades y destrezas las adquir\'o estudando listados assembler de compiladores recientes (para la \'epoca) que usaban en el instituto Case donde cursaba estudios universitarios. Uno de esos traductores era el \texttt{IT} (Internal Translator). \\

Knuth narr\'o su primer encuentro con este programa traductor en una \emph{IBM 650}:\\

\begin{quote}
   \textit{In this program you would punch on cards a algebraic formula. You would say, A = B + C.
           Well, in IT, you had to say, X1 = X2 + X4. Because you didnt have a plus sign, you had to say, A for
           the plus sign. So you had to say, X1 Z X2 A X4. No, S, I guess, was plus, and A was for absolute
           value. But anyway, we had to encode algebra in terms of a small character set, a few letters. There
           werent that many characters you could punch on a card. You punch this thing on a card, and you feed
           the card into the machine. The lights spin around for a few seconds and then -- punch, punch, punch,
           punch -- out come machine language instructions that set X1 equal to X2 + X4. Automatic programming
           coming out of an algebraic formula. Well, this blew my mind. I couldnt understand how this was
           possible, to do this miracle where I had just these punches on the card. I could understand how to write a
           program to factor numbers, but I couldnt understand how to write a program that would convert algebra
           into machine instructions.} \cite{Knuth4}
\end{quote}\\
\\
\begin{codebox}
   \Procname{$\proc{Insertion-Sort}(A)$}
   \li \For $j \gets 2$ \To $\attrib{A}{length}$
   \li \Do
          $\id{key} \gets A[j]$
          \li \Comment Insert $A[j]$ into the sorted sequence
          $A[1 \twodots j-1]$.
          \li $i \gets j-1$
          \li \While $i > 0$ and $A[i] > \id{key}$
          \li \Do
                 $A[i+1] \gets A[i]$
                 \li $i \gets i-1$
          \End
          \li $A[i+1] \gets \id{key}$
   \End
\end{codebox}
\\
Los libros de Knuth eran considerados como dif\'iciles para el estudio. En verdad, a simple vista
con toda la formulaci\'on matem\'atica contenida en el cap\'itulo introductorio del texto no es
extra\~no que se tomara como literatura inpenetrable y vasta para usar como texto de uso b\'asico. Esta
impresi\'on inicial, posteriormente me trajo una contradicci\'on. A trav\'es de los a\~nos conoc\'i
como el libro de Knuth fue usado como texto b\'asico en la Universidad Central de Venezuela durante
la primera parte de la d\'ecada de 1970 para la c\'atedra Laboratorio de Computaci\'on I. Aqu\'i hay
dos puntos fundamentales que entend\'i: lo primero es sentir que hab\'ia yo llegado tarde al oficio
de la programaci\'on de computadoras; lo segundo es el ambiente de rechazo que ya a partir de la d\'ecada de los 1980 se sent\'ia en relaci\'on a la programaci\'on antigua (hermosa y artesana, pudieramos decir) con lenguaje Assembler y c\'odigos de m\'aquina. Posiblemente estoy equivocado pero era mi percepci\'on.\\
\\
Entonces el miedo al texto de Knuth era colosal. Usabamos \textit{Data Structures + Algorithms} escrito
por el gran Prof. Niklaus Wirth, otro gran programador y dise\~nador de lenguajes y traductores.\\

Un buen d\'ia decid\'i romper con ese tab\'u y busqu\'e la edici\'on de 1973 del Volumen 1 del libro de Knuth
titulada "\emph{Fundamental Algorithms}". Entonces le tom\'e cari\~no a la matem\'atica discreta expuesta
y sobre todo a la m\'aquina hipot\'etica \texttt{MIX} (ejemplar de las computadoras existentes en 1962 - a\~no en el que Knuth comenz\'o a escribir su obra). En verdad, la construcci\'on de un programa, a partir de un conjunto de instrucciones b\'asicas, es bastante similar a la construcci\'on de una demostraci\'on matem\'atica a partir de un conjunto de axiomas \cite{Knuth1}. Algunos temas que recuerdo con mucho afecto e inter\'es y que est\'an contenidos en el Volumen 1 son: las funciones generatrices (generating functions), el teorema del binomio y los coeficientes binomiales, el programa de suma y multiplicaci\'on de polinomios y el programa de diferenciaci\'on simb\'olica (cuya subrutina principal contiene una Jump Table muy parecida a la contenida en el simulador \texttt{MIX}, que para este caso "camina" un arbol de  s\'imbolos y no una lista de instrucciones de m\'aquina). El set de instrucciones de la m\'aquina artificial \textt{MIX} (y los nemot\'ecnicos del lenguaje assembler \texttt{MIXAL}, adem\'as de la extructura de programa) son muy similares a los que, para ese entonces (1962-1963) tenia la UNIVAC Solid State Computer; sobre esta m\'aquina (en 1962) Knuth program\'o un compilador FORTRAN II: leyendo el listado Assembler se verifica que \texttt{MIXAL} est\'a fuertemente influenciado por el lenguaje Assembler de la UNIVAC (Figura 0).\\



 Figura 0. Listado subrutina Search y su m\'odulo principal driver - Assembler UNIVAC Solid State
 
\\Para el caso del Teorema del Binomio\\
\\
%
\centerline{$(x+y)^r = \sum_{k}x^ky^{r-k}$} \label{ecu3}\\

\\La descripci\'on era detallada y el autor hac\'ia una excelente rese\~na hist\'orica.\\
\\
El lenguaje con que se programaban y mostraban los algoritmos en ese libro era el assembler \texttt{MIXAL} como ya mencion\'e. Para ese entonces yo conoc\'ia a penas dos lenguajes assembler: el del microprocesador Zilog Z-80 y el del Commodore 64. Sin embargo, con \texttt{MIXAL} aprend\'i otro tipo de instrucciones y de directivas al assembler que eran ejemplares de la programaci\'on ya perdida en el pasado de los a\~nos 1960. Muchos de los llamados "assembleristas" que a\'un viven en nuestro pa\'is estudiaron y aprendieron con \textt{MIXAL}.\\
\\
Knuth se basó mucho en computadoras decimales (no binarias) con memoria dinámica de tambor (Drum machines) como la Burroughs 205, la Burroughs 220 y la IBM 650 (a parte de la UNIVAC Solid State ya indicada). La palabra de datos de la máquina MIX es de cinco (5) grupos de dígitos decimales y signo (+/-AAAAIIFFCC) igual que las computadoras antes indicadas. Nemónicos assembler como LDA, STZ, SUB y ADD son comunes entre la máquina MIX y la IBM 7090 al igual que el uso de registros como A y X. Instrucciones como ADD y STA también están presentes en la IBM 704. El uso de directivas al assembler como END (para señalar el final de un programa y al mismo tiempo indicar la etiqueta que identifica el comienzo del mismo) fue tomada, parcialmente modificada, del assembler para la IBM System/360.



Figura 1. Tambor (Drum) de memoria y palabra de datos decimales - 
Computadora (decimal) Burroughs 205


A mediados de la década de 1960, las técnicas de compilación/traducción y manejo de lenguajes (técnicas de programación) se encontraban muy elaboradas; casi como las conocemos hoy día.

Este a\~no (2012) tuve la oportunidad de compartir informaci\'on con varios amigos (Jos\'e Márquez, Rafael Messana), ex-alumnos de la escuela de computaci\'on de la Universidad Central de Venezuela durante la primera parte de la d\'ecada de 1970. En la c\'atedra Laboratorio de Computación I utilizaban un simulador de la m\'aquina \texttt{MIX}, conjuntamente con un assembler \texttt{MIXAL}, posiblemente el mismo desarrollado por el propio Knuth en la Universidad de Stanford \cite{Knuth3}. Todo este software era procesado en una IBM/360 instalada en Pro-Venezuela (zona rental de Plaza Venezuela). Buenos recuerdos. Lamento mucho que el oficio de programador, hoy d\'ia, se haya transformado en algo refractario y repetitivo, buscando m\'as el quitar y poner componentes, no la creatividad de otrora al dise\~nar algoritmos y luego entender los intr\'insecos del set de instrucciones de una m\'aquina como \texttt{MIX} para luego codificar las instrucciones cuidadosamente seleccionadas en funci\'on a la eficiencia (tiempo de ejecuci\'on y espacio de memoria). Toda una labor de artesan\'ia. Desde hace unos meses he estado revisando el set de instrucciones de la IBm System/360 y System/370 con mi amigo el Prof. Ra\'ul Patiño quien dirigi\'o el instituto ECPI en Caracas a comienzos de la d\'ecada de 1970. Junto a Patiño (a quien tuve el honor de entrevistarle - ver la entrevista publicada en este mismo Blog) me d\'i a la tarea de ejercitar varios casos de uso de instrucciones antiguas como la BC (Branch on Condition), as\'i como tambi\'en instrucciones de alto nivel como la BXxx.\\
\\


Figura 2. Ciclo principal de un Simulador MIX 
implementado en assembler de la IBM/360

\\
Para finalizar esta breve memoria incluyo un ejemplo de traducci\'on (compilaci\'on) manual desde un mini programa originalmente escrito en lenguaje C++ hacia el Assembler \texttt{MIXAL}, y desde ese lenguaje intermedio hacia instrucciones de la m\'aquina \texttt{MIX}. Se trata de un ejercicio en nostalgia. Los sistemas de programaci\'on actuales, con todo su set de librer\'ias API, la necesidad de asociar y enlazar objetos (con relaciones de herencia), y preprocesamiento complejo (como el caso del lenguaje C y sus derivados), producen una cantidad adicional de c\'odigo andamiaje para manejo interno. La traducci\'on hacia \texttt{MIXAL} la hice manualmente, tal como lo hac\'ia hace 25 años como ejercicio: de izquierda a derecha aparece la instrucci\'on de m\'aquina \texttt{MIX}, seguida de la direcci\'on en la memoria hipot\'etica y finalizando con la sentencia Assembler \texttt{MIXAL}.\\
\\
Segu\'i la convenci\'on tomada por algunos compiladores de Lenguaje C con los cuales trabaj\'e a lo largo de los a\~nos, en cuanto a la generaci\'on de c\'odigo para ciclos constantes como el FOR. El ejemplo es muy simple pero sirve como muestra del uso de registros \'indice como contadores descendientes (al estilo de la instrucci\'on de decremento autom\'atico BCT de la IBM System/360).\\


%
% Ensayo de tabbing para la escritura de codigo en assembler.
%
\begin{verbatim}
*     EJEMPLO DE TRADUCCIÓN (MANUAL) DE UNA SENTENCIA COMPLEJA "FOR"                         
*           EN ASSEMBLER MIXAL PARA LA MÁQUINA ARTIFICIAL MIX                                  

*     ======================================================                         
*                           AUTOR: JOSE PORTILLO LUGO, 2012                                          
*                                                                                             
* MÁQUINA MIX    DIR  ASSEMBLER MIXAL                                                         
*--------------   ---- -------------------------------------------------------------------

                                               ORIG  000                                                    
+0000 00 00 00   0000 TASA         CON   0                                                       

                        0049                 ORIG  49                                                      
                        0050 STK           ORIG  *+1            Stack de trabajo                         
                        0052 RESUL        ORIG  *+2            Declaración de símbolos                  
                        0054 PORC         ORIG  *+2                                                     
                        0056 X              ORIG  *+2                                                     
                        0058 TEMP         ORIG  *+2                                                                   
                        0060 Z              ORIG  *+2                                                     
                        0062 Y              ORIG  *+2                                                     
                        0064 BUFFCRD    ORIG  *+2            Buffer de entrada/salida                
*                                                                                              

                                I              EQU   1              Se optimiza el uso de I y J,             
                                J              EQU   2              usando los registros rI1 y rI2             
                                CARDRD     EQU   16             Unidad Lectora - Tarjetas   
                                CARDWR    EQU   17             Unidad Perforadora - Tarjetas
*                                                                                             
                                               ORIG  100            Subrutina - cálculo                     
+0128 00 02 32   0100 FOREXPR    STJ   5F             Establece enlace de la Subrutina        
+0052 00 05 33   0101                 STZ   RESUL          resul=0                                 
+0001 00 02 49   0102                 ENT1  1              i=1                                     
+0008 00 02 50   0103                 ENT2  8              j=8                                     
+0002 00 02 55   0104                 ENTX  2                                                      
+0060 00 05 31   0105                 STX   X              x=2                                     
+0003 00 02 55   0106                 ENTX  3                                                      
+0066 00 05 31   0107                 STX   Y              y=3                                     
+0025 00 02 55   0108                 ENTX  25                                                     
+0064 00 05 31   0109                 STX   Z              z=2                                     
+0058 00 05 08   0110                 LDA   0,2            j                                       
+0060 00 05 03   0111                 MUL   X              x                                       
+0005 00 02 06   0112                 SLAX  5                                                      
+0054 00 05 24   0113                 STA   TEMP           j*x                                     
+0064 00 05 08   0114                 LDA   Z              z                                       
+0066 00 05 03   0115                 MUL   Y              y                                       
+0005 00 02 06   0116                 SLAX  5              z*y                                     
+0062 00 05 01   0117                 ADD   TEMP           j*x+z*y                                 
+0052 00 05 24   0118                 STA   RESUL                                                  
+0126 00 00 39   0119                 JMP   4F             Evalua condiciones                      
+0052 00 05 08   0120 3H             LDA   RESUL          Inicio del ciclo                        
+0000 00 05 03   0121                 MUL   TASA                                                   
+0005 00 02 06   0122                 SLAX  5                                                      
+0100 00 05 04   0123                 DIV   100            (resul*tasa)/100                        
+0054 00 05 24   0124                 STA   PORC                                                   
+0001 00 01 49   0125                 DEC1  1              i--                                     
+0128 00 07 39   0126 4H             J1Z   5F             Termina el ciclo                
+0120 00 00 39   0127                 JMP   3B             Continua el ciclo                       
+0001 00 00 39   0128 5H            JMP   *              Enlace de retorno - Subrutina           
*                                                                                              

                                              ORIG  500            Driver principal del programa           
+0001 00 02 32   0500 MAIN        STJ   END            Establece enlace - Sistema Operativo NIX
+0000 00 05 33   0501                STZ   TASA                                                   
+0054 00 05 33   0502                STZ   PORC                                                   
+0053 00 16 34   0503                JBUS  *(CARDRD)     Espera por Lectora - Tarjetas           
+0067 00 16 36   0504                IN    BUFFCRD(CARDRD) Lectura                               
+0067 00 02 55   0505                LDX   BUFFCRD                                                
+0000 00 05 15   0506                STX   TASA           Tasa para el cálculo                    
+0100 00 00 39   0507                JMP   FOREXPR        Invoca Subrutina                        
+0054 00 05 15   0508                LDX   PORC           RX = porc

+0067 00 05 31   0509                STX   BUFFCRD        Almacena en buffer salida               
+0510 00 17 34   0510                JBUS  *(CARDWR)     Espera por perforadora - Tarjetas       
+0067 00 17 37   0511                OUT   BUFFCRD(CARDWR) Perfora                               
+0000 00 02 05   0512                HLT                  Enlace de retorno - Sistema Operativo NIX

                                              END   MAIN                                                   
*                                                                                             
\end{verbatim}
\\

\page
* Fuente en lenguaje C++ simplificado:                                                        \\
{\obeylines \sfcode`;=3000
{\bf void main()}
\{ // Cuerpo principal del programa
\qquad {\bf int} ${\it tas}=0$, ${\it porc}=0$;\\

\qquad ${\it tas} = getchar()$;
\qquad forexpr({\it tas}, {\it &porc});
\qquad putchar({\it &porc});
\}

{\bf void forexpr}(int tasa, int &porcen)
\{ // Subrutina - cálculo
\qquad {\bf int} $i=1$, $j=8$, $resul=0$, $x=2$, $y=3$, $z=25$;\\

\qquad {\bf for}($resul=j*x+z*y&, $porcen=0$; $i \geq 1$; $porcen=(resul*tasa)/100$, i--);
\}
\par}
%
%----------------------------%
% Referencias bibliográficas %
%----------------------------%
%
\begin{thebibliography}{7}
\bibitem{Knuth1} Knuth, Donald E. \textit{The Art of Computer Programming, Vol. 1 Fundamental Algorithms}, 1973.
\bibitem{Knuth2} Knuth, Donald E. \textit{3-TRAN Interpreter Compiler source listing}, 1964.
\bibitem{Knuth3} Knuth, Donald E., Sites R. L. \textit{MIX/360 Users Guide}, 1971.
\bibitem{Knuth4} Computer Museum. \textit{Oral History of Donald Knuth}, 2007.
\bibitem{Akers1} Akers, Max Neil. \textit{A Proposed Programming System for Knuth MIX Computer}, 1969.
\bibitem{Burr} Burroughs. \textit{Burroughs 205 Electronic Data Processing Systems Handbook}, 1957.
\end{thebibliography}
 


No hay comentarios.: