Universidad de Costa Rica Escuela de Ciencias de la Computación e Informática

Uso de convenciones de programación para descifrar programas

Resumen

      Uno de los primeros trabajos de investigación que hice fue mi artículo sobre convenciones de programación [DiM-88] para el lenguaje Pascal [CC-85]. Con el tiempo, mis estudiantes de CI-1201 Programación II en la Universidad de Costa Rica y de Algorítmica en el Stvdivm Generale de la Universidad Autónoma de Centro América, se han acostumbrado a usar estas convenciones en sus programas, y esto ha generado que ahora los programas sean más legibles y fáciles de mantener. Con sólo aplicar esas convenciones, hemos logrado hasta que sea natural reutilizar programas (labor en la que mis estudiantes son poco menos que expertos).

      Aunque en teoría todos los programadores debemos hacer bien nuestro trabajo, en la práctica encontramos programas pésimos. Mediante un pequeño ejemplo, quiero exponer la técnica que he usado en muchas ocasiones para averiguar qué hace el código que otro programador escribió. Para eso desarrollo la respuesta a una pregunta que les hice a mis estudiantes en un examen en que evalué el conocimiento que tenían de las convenciones de programación y del tipo abstracto de datos Lista. La pregunta del examen es la siguiente:

PROCEDURE KaWabunga(VAR L :TList);
var cantuca,gula,trimulta_salbaca,banana,
old_last:pnode_replist;begin
if l.rep._last=nil then begin exit;end;
banana:=l.rep._last;old_last:=banana^.next;
cantuca:=l.rep._last;gula:=l.rep.
_last^.next;while gula<>banana
do begin trimulta_salbaca:=gula^.next;gula^.
next:=cantuca;cantuca:=gula;
gula:=trimulta_salbaca;end;banana^.
next:=cantuca;l.rep._last:=old_last;end;

      Para llegar a saber qué hace este procedimiento he seguido los siguiente pasos:

Paso 1: Indentar el código

      Aunque mis estudiantes debieron realizar su trabajo con papel y lápiz, en la práctica el programador profesional debe usar su editor de textos preferido para realizar este trabajo.

      Depués de indentar el procedimiento KaWabunga() obtenemos el siguiente código:

PROCEDURE KaWabunga(VAR L : TList);

var
  cantuca,
  gula,
  trimulta_salbaca,
  banana,
  old_last          : pnode_replist;

begin { KaWabunga }
  if l.rep._last=nil then begin
    exit;
  end;

  banana  := l.rep._last;
  old_last:= banana^.next;
  cantuca := l.rep._last;
  gula    := l.rep._last^.next;

  while gula<>banana do begin
    trimulta_salbaca := gula^.next;
    gula^.next := cantuca;
    cantuca    := gula;
    gula       := trimulta_salbaca;
  end;

  banana^.next := cantuca;
  l.rep._last:=old_last;
end;  { KaWabunga }

Paso 2: Cambiar los identificadores

      Para cambiarles los nombres a las variables lo lógico es usar la opción del editor que permite cambiar sólo palabras; en el caso del editor incorporado en Turbo Pascal, esa opción aparece en la ventana de sustitución (Find & Replace) bajo el encabezado "Whole words only".

      Es importante recordar que siempre debemos realizar las sustituciones de los nombres siguiendo un orden que evite que dos identificadores diferentes terminen llamándose igual. Por ejemplo, si debemos cambiar el identificador "x" por "y", y a "y" por "x", no basta con hacer una de esas dos sustituciones, pues el resultado sería que terminaríamos con todas las variables llamándose "x", o "y". Uso la notación x->y para indicar que usamos al editor para sustituir la hilera "x" por la hilera "y".

      Veamos el siguiente ejemplo, en donde al aplicar la sustitución x->y terminamos con todas las variables llamándose "y":

Antes                Sustitución   Después
  VAR                   x->y         VAR
    x, y: INTEGER;                     y, y: INTEGER;

      La forma correcta de hacer esta sustitución es usar un nombre temporal (z) para alguna de las variables, así:

Antes                Sustitución   Después
  VAR                   x->z         VAR
    x, y: INTEGER;                     z, y: INTEGER;


Antes                Sustitución   Después
  VAR                   y->x         VAR
    z, y: INTEGER;                     z, x: INTEGER;

Antes                Sustitución   Después
  VAR                   z->y         VAR
    z, y: INTEGER;                     y, x: INTEGER;

      Aunque tomó un poco más de esfuerzo, el resultado final es que hemos intercambiado los nombres de "x" y "y".

      Para escoger cuáles son los nombres que usaremos en este paso, lo que hacemos es aplicar el sentido común. En el encabezado del procedimiento aparace el tipo TList, y a lo largo del código se usa la notación Pascal para punteros "^.next". Lo natural entonces es llamar a cada variable con los nombres que usualmente usamos para identificar a los punteros: "p" y "q". Apliquemos entonces las siguientes sustituciones al código que obtuvimos del paso anterior:

cantuca          -> p
gula             -> q
trimulta_salbaca -> xP
banana           -> yP
old_last         -> old_last

      ¿Por qué he escogido los nombres "xP" y "yP"? Bueno, como usualmente usamos "x" y "y" para nombrar cualquier variable, lo que he hecho es agregarles una "P" al final porque sé que estas dos variables son punteros. ¿Por qué no le he cambiado el nombre a "old_last"?. Porque lo más seguro es que ese nombre esté bien puesto, pues ningún programador sería tan torpe de usar un identificador que es tan significativo para nombrar algo diferente a lo que el identificador significa.

      Es importante aclarar el uso de nombres en inglés, y no en español. La principal razón es que los nombres en inglés casi siempre son más cortos. Además, es mucho más fácil nombrar procedimientos en inglés que en español, pues en español muchas veces es necesario calificar los verbos que se usan para nombrar procedimientos con palabras que eliminen ambigüedades. Por ejemplo, la traducción exacta de DISPOSE() es Retorne_Memoria_Dinámica(), que además de ser un identificador muy largo, es incómodo de manipular y de recordar.

      El resultado de aplicar estas sustituciones, con el debido cuidado, es el siguiente código:

PROCEDURE Incognita(VAR L : TList);
VAR
  p,
  q,
  xP,
  yP,
  old_last : PNode_RepList;
BEGIN { Incognita }
  IF L.Rep._last = NIL THEN BEGIN
    EXIT;
  END;

  yP := L.Rep._last;
  old_last := yP^.next;
  p  := L.Rep._last;
  q  := L.Rep._last^.next;

  WHILE q<>yP DO BEGIN
    xP := q^.next;
    q^.next := p;
    p := q;
    q := xP;
  END;

  yP^.next := p;
  L.Rep._last := old_last;
END;  { Incognita }

Paso 3: Usar el conocimiento sobre el programa para mejorar los nombres de las variables

    L.Rep._last ------------------------>-+
                                          |
     elem    next                         v
   +--------+---+   +--------+---+   +--------+---+
+->| elem_1 | *-+-->| elem_2 | *-+-->| elem_3 | *-+->+
|  +--------+---+   +--------+---+   +--------+---+  |
+-<--------------<---------------<-------------------+
         /\                                /\
         ||                                ||
       First(L)                          Last(L)

      Con base en el conocimiento sobre la lista es posible escoger un mejor nombre para cada uno de los identificadores del procedimiento Incognita(). A continuación defino cada una de las sustituciones que resultan de usar el nombre que aparentemente más se ajusta a la función que desempeña cada variable en el programa.

p --> p	El valor de "p" se usa en el ciclo WHILE, y como lo usual es llamar a los punteros "p" o "q", parece que el nombre "p" es el adecuado para esta variable.
q --> first	El valor inicial de esta variable es el siguiente a "L.Rep._last", o sea, que es "first".
xP --> firstNext	En el ciclo WHILE, esta variable siempre sigue a "q", por lo tiene sentido llamarla "el siguiente a q".
yP --> old_last	Esta variable toma el valor "L.Rep._last" desde el principio y su valor nunca cambia, por lo que se mantiene apuntando al último nodo de la lista. Por eso debe llamarse "old_last".
old_last --> old_first	El valor que toma esta variable es el puntero al nodo que sigue al nodo último de la lista. Eso quiere decir que este valor es realmente el primero de la lista, por lo que debe llamarse "old_first", y no "old_last".

      Vemos ahora que el programador que escribió este código usó un pésimo nombre para la variable "old_last". Como yo escribí el procedimiento KaWabunga(), justifico mi acción argumentando que los profesores, a veces, les ponemos "zancadillas" a los estudiantes en los exámenes. Pero eso no es importante; lo que sí lo es, es que muchos programadores usan nombres "clave" para evitar que otros entiendan el código que escriben, y de esa manera protegen su puesto. En forma alguna apruebo esta mala práctica; pero sí es importante saber que no es necesario entender mucho sobre un programa para saber cuándo un identificador está denominado incorrectamente.

      Como en muchas otras actividades, encontramos de nuevo que el sentido común resulta ser un arma eficaz para resolver problemas.

      Al aplicar las sustituciones obtenemos la siguiente versión del procedimiento:

PROCEDURE Incognita(VAR L : TList);

VAR
  p,
  first,
  firstNext,
  old_last,
  old_first : PNode_RepList;
BEGIN { Incognita }
  IF L.Rep._last = NIL THEN BEGIN
    EXIT;
  END;

  old_last  := L.Rep._last;
  old_first := old_last^.next;
  p         := L.Rep._last;
  first     := L.Rep._last^.next;

  WHILE first<>old_last DO BEGIN
    firstNext   := first^.next;
    first^.next := p;
    p           := first;
    first       := firstNext;
  END;

  old_last^.next := p;
  L.Rep._last    := old_first;
END;  { Incognita }

Paso 4: Encontrar la función del procedimiento

      Al examinar la lógica del ciclo WHILE encontramos que los identificadores "first" y "firstNext" están mal denominados, pues el valor del puntero "first" camina desde el principio hasta el final de la lista, y no permanece estático apuntando al principio de la lista como parecía a primera vista. En la práctica también ocurre que el primer nombre que usamos para un identificador no es el más apropiado. Como nos ha ocurrido aquí, con frecuencia nos encontramos en la necesidad de renombrar algunos identificadores para expresar mejor el algoritmo. En el caso que nos ocupa, hagamos entonces las siguientes sustituciones para que el programa sea más claro:

first     ---> q
firstNext ---> qN  (por q-Next)

      La nueva versión del programa es la siguiente:

{ 1}  PROCEDURE Incognita(VAR L : TList);
{ 2}
{ 3}   VAR
{ 4}     p,
{ 5}     q,
{ 6}     qN,
{ 7}     old_last,
{ 8}     old_first : PNode_RepList;
{ 9}   BEGIN { Incognita }                      
{10}     IF L.Rep._last = NIL THEN BEGIN        
{11}       EXIT;
{12}     END;
{13}
{14}     old_last  := L.Rep._last;
{15}     old_first := old_last^.next;
{16}
{17}     p := L.Rep._last;
{18}     q := L.Rep._last^.next;
{19}                                            
{20}     WHILE q<>old_last DO BEGIN   
{21}       qN      := q^.next;              
{22}       q^.next := p;                    
{23}       p  := q;                         
{24}       q  := qN;                        
{25}     END;                               
{26}                                        
{27}     old_last^.next := p;               
{28}     L.Rep._last    := old_first;       
{29}   END;  { Incognita }                 

      Cuando trabajamos con estructuras de datos complicadas porque utilizan punteros, conviene mucho usar gráficos para entender qué hace el código. Como sabemos que el programa trabaja con listas circulares, conviene correrlo viendo el efecto de cada instrucción en un dibujo. Lo primero que debemos hacer es correrlo con la lista vacía. Como una lista vacía se representa con el valor NIL en "L.Rep._last", entonces la condición del IF de la instrucción {10} es verdadera. Podemos concluir entonces que:

1.- Si la lista está vacía, entonces Incognita() no la cambia.

    L.Rep._last
         |
         v   next
   +--------+---+
+->| elem_1 | *-+-->+
|  +--------+---+   |
+-<--------------<--+
    /\     /\
    ||     ||
 First(L) Last(L)

      En este caso, vemos que el valor de las variables "old_last", "old_first", "p" y "q" va a ser el mismo, pues el campo ".next" del nodo apunta hacia sí mismo. Esto implica que la condición del WHILE en la instrucción {20} es falsa. El efecto de la instrucción {21} será el de copiar en el nodo el valor que ya tenía, y lo mismo ocurrirá al cambiar el valor de "L.Rep._last". Concluimos entonces que:

2.- Si la lista tiene sólo un elemento, entonces Incognita() no la cambia.

          L.Rep._last ------->-+
                               |
                               v
         +--------+---+   +--------+---+
      +->| elem_1 | *-+-->| elem_2 | *-+->+
      |  +--------+---+   +--------+---+  |
      +-<--------------<---------------<--+
            ^       ^         ^      ^
            |       |         |      |
old_first --+       q         p      +-- old_last

      Como "q" no apunta a "elem_2", el resultado de ejecutar las instrucciones {21} y {22} es el siguiente:

    L.Rep._last ------->-+
                         |
                         v
   +--------+---+   +--------+---+
+->| elem_1 | *-+-->| elem_2 | *-+->+
|  +--------+---+   +--------+---+  |
+-<--------------<---------------<--+
         ^              ^      ^
         |              |      |
         q              p      qN

      Parece extraño, pero la instrucción {22} deja en el campo ".next" del nodo "elem_1" el mismo valor. Al ejecutar las instrucciones {23} y {24} obtenemos lo siguiente:

    L.Rep._last ------->-+
                         |
                         v
   +--------+---+   +--------+---+
+->| elem_1 | *-+-->| elem_2 | *-+->+
|  +--------+---+   +--------+---+  |
+-<--------------<---------------<--+
         ^            ^   ^    ^
         |            |   |    |
         p            q   qN   +-- old_last

      Todo parece indicar que el programador escribió un programa que sobreescribe los valores en el campo ".next" de cada nodo, pero sin cambiarlos, pues al ejecutar la instrucción WHILE en la línea {20} encontramos que la condición es verdadera pues ya "q" apunta al nodo "elem_2" y en el ciclo nunca cambia el valor de "old_last". También ocurre que el valor de "old_last^.next" no cambia en la instrucción {27}.

      Sin embargo, al ejecutar la instrucciones {28} sí cambia el valor de "L.Rep._last", pues toma el valor de la variable "old_first":

          L.Rep._last
               |
               v
         +--------+---+   +--------+---+
      +->| elem_1 | *-+-->| elem_2 | *-+->+
      |  +--------+---+   +--------+---+  |
      +-<--------------<---------------<--+
            ^   ^           ^   ^    ^
            |   |           |   |    |
old_first --+   p           q   qN   +-- old_last

      Todo el efecto de este trabajo ha sido cambiarle el valor a "L.Rep._last". Recordemos que "L" siempre apunta al final de la lista. Redibujemos el diagrama para ver qué ha ocurrido:

    L.Rep._last ------->-+
                         |
                         v
   +--------+---+   +--------+---+
+->| elem_2 | *-+-->| elem_1 | *-+->+
|  +--------+---+   +--------+---+  |
+-<--------------<---------------<--+

      Es evidente que los nodos de la lista han cambiado de orden. Entonces:

3.- Si la lista tiene dos elementos, Incognita() les cambia el orden a los nodos.

      Ahora podemos avanzar un poco más rápido, pues resulta más clara la función de cada variable en el algoritmo. Veamos qué ocurre cuando la lista tiene tres elementos. Después de ejecutar la instrucción {21} tenemos la siguiente situación:

          L.Rep._last ------------------------>-+
                                                |
                                                v
         +--------+---+   +--------+---+   +--------+---+
      +->| elem_1 | *-+-->| elem_2 | *-+-->| elem_3 | *-+->+
      |  +--------+---+   +--------+---+   +--------+---+  |
      +-<--------------<---------------<-------------------+
            ^   ^               ^               ^     ^
            |   |               |               |     |
old_first --+   q               qN              p     +-- old_last

      El resultado de ejecutar las instrucciones {22}, {23} y {24} es el siguiente:

          L.Rep._last ------------------------------>-+
                                                      |
                    +---------------------------+     |
                    |                           |     |
                    |                           v     v
         +--------+---+   +--------+---+   +--------+---+
      +->| elem_1 | * +   | elem_2 | *-+-->| elem_3 | *-+->+
      |  +--------+---+   +--------+---+   +--------+---+  |
      +-<--------------<---------------<-------------------+
            ^   ^             ^    ^                  ^
            |   |             |    |                  |
old_first --+   p             q    qN                 +-- old_last

      Como la condición del WHILE no es verdadera, después de ejecutar una iteración completa del ciclo obtenemos lo siguiente:

          L.Rep._last ------------------------------>-+
                                                      |
                  +--------------------------->-+     |
                  |     +-----<------+          |     |
                  |     |            |          v     v
       +--------+---+   | +--------+---+   +--------+---+
    -->| elem_1 | * |<--+ | elem_2 | * |   | elem_3 | *-+->+
    |  +--------+---+     +--------+---+   +--------+---+  |
    +-<----------------<---------------<-------------------+
              ^               ^              ^  ^     ^
              |               |              |  |     |
old_first ----+               p              q  qN    +-- old_last

      En este momento, la condición del WHILE de la instrucción {20} es verdadera, pues ya "q" le dio vuelta a la lista. Después de ejecutar las instrucciones {27} y {28} obtenemos lo siguiente:

        L.Rep._last
              |   +--------------------------->-+
              |   |     +------------+          |
              v   |     |            |          v
       +--------+---+   | +--------+---+   +--------+---+
       | elem_1 | * |<--+ | elem_2 | * |   | elem_3 | *-+->+
       +--------+---+     +--------+---+   +--------+---+  |
              ^               ^  ^                    ^    |
              |               |  |                    |    |
              |               |  +-----<--------------+----+
              |               |                       |
old_first ----+               p                       +-- old_last

      Como "L" apunta al último nodo de la lista, ahora el último es "elem_1". Además, el primero de la lista siempre es aquél al que el último apunta, por lo que el último de la lista ahora es "elem_3". Como el campo ".next" del nodo "elem_3" apunta a "elem_2", entonces el segundo nodo de la lista es "elem_2". Esto quiere decir que Incognita() ha vuelto al revés la lista, pues al principio el orden que tenía era (1,2,3) y ahora es (3,2,1).

      Si ahora examinamos la función de "p" vemos que siempre está un nodo atrás de "q". El ciclo WHILE lo que hace es cambiar el campo ".next" de cada nodo para que apunte al nodo anterior, esto efectivamente ocurre cuando se ejecuta la instrucción {22}.

      Entonces, lo que el código hace es volver al revés los punteros de los campos ".next" en cada nodo. Esto quiere decir que este procedimiento vuelve al revés la lista "L".

      A primera vista no era obvia la función del procedimiento, pero después de pensar un rato, y de recurrir a unos cuantos dibujos, pudimos descifrar la función del procedimiento Incognita(), cuyo nombre más apropiado por supuesto es Reverse().

Paso 5: Escribir la versión final del procedimiento

PROCEDURE Reverse(       { EXPORT }     { ADH }
  {?} VAR L : TList      { SELF }
);
{ RESULTADO
  Invierte la lista "L" de forma que sus últimos
  elementos pasen a ser los primeros.
  - La implementación no copia los elementos de "L",
    sino que el trabajo se realiza usando cirugía de
    punteros. }
{ EJEMPLO
  L = (1,2,3,4) ==> Reverse(L) ==> L = (4,3,2,1).  }
VAR
  p,
  pN,
  pNN,
  old_last,
  old_first: PNode_RepList;

BEGIN { Reverse }
  { se sale si la lista está vacía }
  IF L.Rep._last = NIL THEN BEGIN
    EXIT;
  END;

  { recuerda cuáles son los nodos en los extremos }
  old_last  := L.Rep._last;
  old_first := old_last^.next;

  { ciclo para volver todos los nodos de la lista }
  p  := L.Rep._last;
  pN := L.Rep._last^.next;
  WHILE pN <> old_last DO BEGIN
    { apunte hacia atrás }
    pNN      := pN^.next;
    pN^.next := p;

    { avance al siguiente nodo }
    p  := pN;
    pN := pNN;
  END;

  { vuelve el puntero del último nodo }
  old_last^.next := p;

  { pone el nuevo último nodo }
  L.Rep._last := old_first;
END;  { Reverse }

      De la discusión anterior se puede concluir que la función de "q", que yo llamé "pN" en la versión original de Reverse(), es la de servir de pivote para cambiar el valor del puntero en el campo ".next" del siguiente nodo. Es discutible que los nombres de variable "p", "pN" y "pNN" sean los identificadores que mejor ayudan a expresar el algoritmo. Cuando escribí este algoritmo me parecieron los mejores, pero sé que algunos programadores disienten.

Conclusión

      Ya existen muchas herramientas que le pueden ayudar al programador a entender el código de un programa [KP-78]. Para el lenguaje C desde hace mucho existe el comando "bc" que ayuda a indentar un programa. En Turbo Pascal, la casa Turbo Power vende un producto llamado Turbo Analyst que, entre otras cosas, incluye herramientas para reformatear el código fuente.

      Pero, independientemente de la cantidad de ayuda mecánica, el programador siempre deberá usar el más poderoso de todos sus recursos: el cerebro [Dij-75]. Nunca dejará de ser necesario pensar para arreglar entuertos en los programas.

Reconocimientos

PROGRAM Test;
{ RESULTADO
  Este programa sirve para ver lo que hace el
  procedimiento Kawabunga(). }

USES
  Elem, List;

PROCEDURE KaWabunga(VAR L : TList); { ... }
PROCEDURE Incognita(VAR L : TList); { ... }

VAR
  L : TList;
  e : TElem;
  c : CHAR;
BEGIN
  WriteLn('==================================');
  List.Init(L); Elem.Init(e);

  List.Print(L, OUTPUT); Write('==> '); KaWabunga(l);
  List.Print(L, OUTPUT); WriteLn;

  Elem.put(e, 'a', 0);   Append(l, e);
  List.Print(L, OUTPUT); Write('==> '); KaWabunga(l);
  List.Print(L, OUTPUT); WriteLn;

  Elem.put(e, 'b', 0);   Append(l, e);
  List.Print(L, OUTPUT); Write('==> '); KaWabunga(l);
  List.Print(L, OUTPUT); WriteLn;

  Elem.put(e, 'c', 0);   Push(l, e);
  List.Print(L, OUTPUT); Write('==> '); KaWabunga(l);
  List.Print(L, OUTPUT); WriteLn;

  Elem.put(e, 'd', 0);   Append(l, e);
  List.Print(L, OUTPUT); Write('==> '); KaWabunga(l);
  List.Print(L, OUTPUT); WriteLn;

  List.Clear(L);
  FOR c := 'a' TO 'z' DO BEGIN
    Elem.put(e, c, 0);   Append(l, e);
  END;
  List.Print(L, OUTPUT); WriteLn;
  WriteLn('   ==>');                    KaWabunga(l);
  List.Print(L, OUTPUT); WriteLn;

  Elem.done(e); List.Done(L);
END. { Test }

Bibliografía

      Este artículo está disponible en Internet en la siguiente dirección:
         http://www.di-mare.com/adolfo/p/reverse.htm

Indice

[-]	Resumen
[-]	Paso 1: Indentar el código
[-]	Paso 2: Cambiar los identificadores
[-]	Paso 3: Mejorar los nombres de las variables
[-]	Paso 4: Encontrar la función del procedimiento
[-]	Paso 5: Escribir la versión final del procedimiento
[-]	Conclusión
[-]	Reconocimientos
	Bibliografía
	Indice
	Acerca del autor
	Acerca de este documento
	Principio Indice Final

Acerca del autor

Adolfo Di Mare <adolfo@di-mare.com>

Acerca de este documento

Referencia:	Di Mare, Adolfo: Uso de convenciones de programación para descifrar programas, Revista Ingeniería, Facultad de Ingeniería, Universidad de Costa Rica, Volumen 6, Número 2, pp [45-54], 1996.
Internet:	http://www.di-mare.com/adolfo/p/reverse.htm
Autor:	Adolfo Di Mare <adolfo@di-mare.com>
Contacto:	Apdo 4249-1000, San José Costa Rica Tel: (506) 207-4020       Fax: (506) 438-0139
Revisión:	ECCI-UCR, Enero 1998
Visitantes: