Regístrate | Conectar
El Tamiz Libros Recursos Series Únete 7 Users Online
Skip to content

Computador mágico XXV – Ordenador C16B: subrutinas




La serie “El computador mágico” está disponible también en forma de libro.

En el último capítulo de esta serie veíamos un programa relativamente complejo que permitía temporizar la salida hacia la pantalla dependiendo de la tecla que habíamos pulsado… pero decíamos que había algunas cosas que eran un poco chapuceras. No eran culpa del diseño del programa… es que con ese ordenador no se podía hacer mucho más. Así que vamos a mejorar el ordenador C16A con una pila, y lo vamos a llamar C16B.

La arquitectura de nuestro nuevo ordenador será la siguiente:

 

Supongo que te has dado cuenta de que, arquitecturalmente, hay poca diferencia: existe un nuevo registro que se llama SP (del inglés Stack Pointer, puntero de la pila). Como probablemente no sabes lo que es una pila, vamos a verla primero a nivel teórico y luego vemos su uso en el C16B.

Una pila almacena “cosas” (en nuestro ejemplo almacenará números enteros de 16 bits), y tiene dos operaciones: PUSH y POP. En este contexto se suelen traducir como “meter” y “sacar” respectivamente. O también “poner” y “quitar”. O mejor dicho: no se traducen; todo el mundo usa los términos en inglés. La gracia es que la pila es un sistema LIFO (Last In First Out, el último en entrar es el primero en salir): si vas metiendo uno o más elementos en la pila, cuando saques, sacarás el último que metiste. Podemos imaginárnoslo como una caja profunda o un barril en el que metemos artículos relativamente voluminosos: metemos el Primero, y se va al fondo; metemos el Segundo, y se queda sobre el Primero; metemos un Tercero, y se queda sobre el Segundo; si ahora sacamos, sacaremos el Tercero; si volvemos a sacar, sacaremos el Segundo. Quizá el siguiente dibujo te ayude a entenderlo:

Date cuenta de que conceptualmente PUSH tiene un “parámetro”. Es decir, cuando hacemos PUSH hay que decir PUSH de ¿qué?. O sea, ¿qué es lo que hay que meter en la pila? En cambio, cuando hacemos POP, lo que obtenemos es lo que haya en lo alto de la pila,[1] no tenemos que decir qué es lo que queremos sacar… lo que sí que hay que decir es qué hacemos con eso que hemos sacado.

Vamos a implementar entonces nuestra pila al final de la memoria principal. Cuando arranca el sistema, hacemos que el registro SP contenga la dirección 0x7FF. Cuando nos pidan meter algo en la pila (PUSH), lo que haremos es escribirlo en la posición de la memoria donde diga SP, y luego restar 1 de SP. Cuando lo que nos pidan sea sacar de la pila (POP), recuperaremos lo que haya en la dirección siguiente a la que apunte SP, y luego sumaremos 1 a SP. A ver si el siguiente dibujo te ayuda a entenderlo:

¿Lo ves? Empieza apuntando al final de la memoria. Cuando hacemos la operación PUSH 1234, se introduce ese 1234 al final, y se resta 1 a SP. Luego se hace PUSH de otro número: el 9876. Después se hace POP, de modo que el 9876 sale de la pila y SP apunta una posición más abajo de nuevo, en este caso al 1234. Fácil, ¿verdad?

Bueno, pues vamos a añadir cuatro instrucciones más a nuestro ordenador. Recordarás que habíamos reservado 4 bits para las instrucciones (16 combinaciones posibles), pero solo teníamos 8 instrucciones usadas. Vamos a añadir otras 4:

Mnemotécnico ¿Qué hace?
NOP No Operation. Operación que no hace nada.
ST <addr> Almacena (del inglés store) el contenido del acumulador en la posición de memoria <addr>. addr es del inglés address, dirección.
LD <addr> Carga (del inglés load) en el acumulador el contenido de la posición de memoria <addr>.
ADD <addr> Suma (del inglés add) el contenido del acumulador con el contenido de la posición de memoria <addr>, y deja el resultado en el acumulador.
BR <addr> Salta (del inglés branch) la ejecución a la posición <addr>. E decir, en vez de continuar ejecutando en PC+1, continúa ejecutando en la posición de memoria <addr>
BZ <addr> Del inglés branch if zero, salta si es cero. Es decir, lo mismo que BR, pero solo si el contenido del acumulador es un 0.
CLR Limpia (del inglés clear) el acumulador. Es decir, pone un 0 en él.
DEC Decrementa (del inglés decrease) el acumulador y deja el resultado en el propio acumulador.
PUSH Mete el valor del acumulador en la pila.
POP Saca el valor de la pila y lo pone en el acumulador.
CALL <addr> Del inglés call, llamar. Pone el valor del PC en la pila y pone <addr> en PC.
RET Del inglés return, retornar. Saca el valor de la pila y lo pone en el PC.

Esta vez no vamos a ver en detalle cómo se hacen estas instrucciones. Cuando vimos el C16A lo vimos con detalle, pero ahora ya sería detallar demasiado. Además de las dos instrucciones que ya hemos visto para operar con la pila, PUSH y POP, hay otras dos que parecen un poco especiales, ¿no? Es decir, también parece que operan con la pila, pero que también hacen algo más, ¿no? Recuerda que PC (Program Counter) apunta a “la siguiente instrucción a ejecutar”, así que “poner X en PC” significa “saltar a X”. Es decir, son como PUSH y POP respectivamente, pero lo que guardan/sacan es el PC, no el acumulador; y además, saltan.

Vamos a ver para qué sirven con un ejemplo (esta vez no vamos a usar el teclado ni la pantalla para nada, para simplificar el ejemplo al máximo): vamos a calcular el factorial de un número.

Es decir, si el número es el 6, vamos a hacer 6x5x4x3x2x1 = 720. Pero claro, nuestro ordenador no sabe multiplicar… solo sabe sumar. En el último artículo vimos un truco para multiplicar números enteros positivos: multiplicar PxQ es sumar Q veces P. Pero una preguntita… ¿esto de multiplicar un número por otro no es algo muy habitual? ¿No podría ocurrírsenos una forma de escribir el “subprograma de multiplicación” una sola vez y luego usarlo tantas veces como necesitemos? Muy buena idea, vamos a ello. El programa que hace eso es el siguiente. Prepárate, porque es bastante largo, pero es probablemente lo más largo que vamos a ver en la serie. Esta vez, como es bastante largo, vamos a escribir a la izquierda las direcciones de memoria, porque si no, nos perdemos.

0×000 /FACTORIAL LD /NUMERO
0×001 BRZ /FINFACTORIAL
0×002 PUSH # R=R*N
0×003 LD /RESULTADO
0×004 PUSH
0×005 CALL /MULTIPLICAR # Llama a la subrutina MULTIPLICAR
0×006 POP
0×007 ST /RESULTADO
0×008 LD /NUMERO
0×009 DEC
0x00A ST /NUMERO
0x00B BR /FACTORIAL
0x00C /FINFACTORIAL NOP # Al llegar aquí, RESULTADO tiene el resultado
0x00D /HALT NOP
0x00E BR /HALT
0x00F /NUMERO 6 # El numero del que hay que calcular el factorial
0×010 /RESULTADO 1 # Resultado parcial y final del factorial
0×011 /MULTIPLICAR POP # Subrutina MULTIPLICAR
0×012 ST /RETORNO # Saco la direccion de retorno de la pila y la guardo en RETORNO
0×013 POP # Saco los dos parametros de la pila y los ugardo en P y Q
0×014 ST /P
0×015 POP
0×016 ST /Q
0×017 CLR
0×018 ST /RES # Ponemos RES a 0
0×019 /MULTIPLICACION LD /P
0x01A BRZ /FINMULTIPLICACION # Bucle mutiplicacion
0x01B DEC
0x01C ST /P
0x01D LD /RES
0x01E ADD /Q
0x01F ST /RES
0×020 BR /MULTIPLICACION
0×021 /FINMULTIPLICACION PUSH # Guardo en la pila el resultado
0×022 LD /RETORNO # Guardo en la pila la dirección de retorno
0×023 PUSH
0×024 /FINMULTIPLICAR RET # Retornar
0×025 /RETORNO 0×000 # Direccion de retorno de la subrutina
0×026 /P 0 # Primer multiplicando
0×027 /Q 0 # Segundo multiplicando
0×028 /RES 0 # Resultado multiplicacion

A ver si logramos entenderlo. Lo mejor es quitarnos rápido de en medio las cosas que son fáciles: las líneas con el /HALT son igual que antes, para terminar ahí. /NUMERO contiene inicialmente el número del que queremos calcular el factorial y /RESULTADO es donde dejaremos el resultado, obviamente, el factorial.

Luego, lo mejor es ir entendiendo bloques sencillitos. Veamos… las líneas 0×000 a 0×001 y 0×008 a 0x00B, ¿qué hacen? Ojo, que estoy olvidándome de momento de lo que hay entre medias: solo esas seis líneas. ¿Qué hacen? Ya lo hemos visto antes: carga una dirección de memoria y la van decrementando hasta que llega a 1. Esa dirección de memoria es /NUMERO, así que esas 6 líneas van contando hacia atrás 6, 5, 4, 3, 2, 1… y entre medias parece que hacen algo con ese /NUMERO. ¿Entendido esto?

Entonces, ¿qué está haciendo con ese /NUMERO entre medias, en las líneas 0×002 a 0×007? Primero mete /NUMERO en la pila. Luego mete /RESULTADO en la pila. Luego llama a /MULTIPLICAR. Y luego saca algo de la pila y lo guarda en /RESULTADO.

Uhm… no acabo de entenderlo del todo…

¿Y si intentamos entender qué hace esa llamada a /MULTIPLICAR? Recuerdas que el CALL /MULTIPLICAR lo que hace es saltar a /MULTIPLICAR, metiendo previamente en la pila el valor actual de PC, ¿verdad? Y una vez que llega a /MULTIPLICAR, ¿qué hace? Son las líneas 0×011 a 0×022. De esas líneas, si lo miramos con cuidado, hay un pedazo que ya sabemos qué hace: lo que hay entre la 0×017 y la 0x01E es lo mismo que en el artículo anterior usábamos para multiplicar dos números: sumar P veces Q. El resultado de esa multiplicación acaba en /RES.

Así que lo único raro es lo que hay alrededor de eso. Lo que hace es: sacar un valor de la pila y guardarlo en /RETORNO. Sacar un elemento de la pila y guardarlo en /P. Sacar otro valor de la pila y guardarlo en /Q. Luego multiplica con el bucle que ya hemos visto. Luego mete /RES en la pila. Luego mete /RETORNO en la pila. Y luego llama a RET. Sabemos que RET lo que hace es saltar a donde diga la última entrada de la pila.

¿Lo vas viendo? Vamos a verlo un poco más en abstracto:

Bucle principal Subrutina: MULTIPLICAR
Guardo /NUMERO en la pila
Guardo /RESULTADO en la pila
Llamo a la subrutina
Saco de la pila a /RETORNO
Pongo 0 en /RES
Saco de la pila a /Q
Saco de la pila a /P
Multiplico /P x /Q y el resultado va a /RES
Pongo /RES en la pila
Pongo /RETORNO en la pila
Retorno
Saco de la pila a /RESULTADO

La gracia de esto es que lo que el “programa principal” mete en la pila, la “subrutina” lo saca y lo utiliza. Cuando acaba, mete en la pila el resultado, que será extraído por el programa principal.

¡Estupendo! ¡Eso es una subrutina![2]

Todas las subrutinas funcionan más o menos así:

  • Quien va a llamarlas mete en la pila los parámetros de la subrutina, en un cierto orden prefijado que es el que espera la subrutina.
  • La subrutina hace lo que tenga que hacer, que puede ser incluso llamar a otras subrutinas (¡o incluso llamarse a sí misma!), y pone el resultado en la pila.[3]
  • La subrutina termina devolviendo el control a su llamador (especificando la próxima instrucción a ejecutar, que es la siguiente a la instrucción CALL).
  • Quien llamó saca de la pila el resultado y continúa su proceso.

¡Es un invento maravilloso! Podemos hacer subrutinas para multiplicar, restar, contar, comparar, esperar… Y después, las vamos combinando unas con otras para hacer rutinas más complejas: rutinas que hagan logaritmos, que calculen sudokus o que preparen café con leche. Y luego, desde el programa principal las vamos llamando. Esta es la única forma razonable de hacer programas complejos. Gran parte del trabajo de los programadores consiste en organizar estas subrutinas de forma lo más inteligente posible para que el programa funcione rápido, sea fácil de mantener en el futuro, se programe rápidamente…

Por lo tanto, hemos hecho una subrutina que multiplica los dos números que le pasemos como parámetros. Recapitulemos entonces: teníamos un bucle que contaba de 6 hacia abajo, hasta llegar a 1: 6, 5, 4, 3, 2, 1. Y, dentro de ese bucle, tenemos que el resultado es el resultado [anterior] multiplicado por el número. Es decir, vamos multiplicando 1×6. Luego el resultado de eso lo multiplicamos x5. El resultado de eso x4… Y así hasta llegar a 1. ¡Eso es el factorial! Lo hemos conseguido: nuestro programa calcula el factorial de un número.[4]

Muchas veces utilizamos algún tipo de pseudocógico para ir explicando lo que va haciendo de forma un poco más abstracta. Por ejemplo, podemos decir:

numero = 6 Línea 0x00F
resultado = 1 Línea 0×010
mientras (numero != 0) { Líneas 0×000, 0×001
  resultado = multiplicar(resultado,numero) Líneas 0×002 a 0×007
  numero = numero -1 Líneas 0×008 a 00A
} Líneas 0x00B
# El resultado está en resultado
subrutina multiplicar(p, q) { Líneas 0×011 a 0×016
  res = 0 Líneas 0×017, 0×018
  mientras (p != 0) { Líneas 0×019, 0x01A
    p = p -1 Líneas 0x01B, 0x01C
    res = res + q Líneas 0x01D a 0x01F
  } Línea 0×020
  devolver res Líneas 0×021 a 0×024
}

Fíjate en que es lo mismo, pero puesto de una forma un poco más abstracta… eso es lo que veremos en el próximo capítulo.

 

 

  1. Técnicamente, en español se denomina la “cabeza de la pila”, y sacar un elemento de la pila con un POP, lo llamamos “descabezar” la pila. []
  2. Dependiendo del sistema se le llama subrutina, rutina, subprograma, función, procedimiento, método… []
  3. Por cierto: el factorial lo hemos calculado con un algoritmo iterativo. La forma elegante y sencilla de hacerlo es con un algoritmo recursivo, que se basa en que factorial(N) = N*factorial(N-1). Pero no quería contar ambas cosas a la vez para no liar más a los lectores sin experiencia en estas lides. []
  4. Date cuenta de que no tenemos ninguna instrucción para comprobar si es un 1, que podríamos ahorrárnoslo, y por eso tenemos que perder el tiempo multiplicando por 1. []

Sobre el autor:

J ( )

 

{ 2 } Comentarios

  1. Gravatar Alex | 27/01/2014 at 09:21 | Permalink

    Llevaba meses sin pasar por El Cedeazo. Veo que sigue adelante con esta serie.

    Vaya curro que se está dando ¿Hasta dónd va a llegar?

    Explicará también conceptos de arquitectura como segmentación de cauce, predicción de saltos, procesamiento superescalar, caché, paginación, protección de memoria, memoria virtual? Al menos su ordenador debería cubrir algo de esto.

    Explicará también temas de sistemas operativos como gestión de procesos, gestión memoria, sistemas de ficheros..? A su ordenador mágico también habrá que introducirle un sistema operativo.

    Pues no le queda trabajo ni nah….

  2. Gravatar J | 28/01/2014 at 08:38 | Permalink

    Alex,

    a nivel técnico no entrará tan abajo. Solo introduciremos muy ligeramente la MMU. Sí que veremos sistemas operativos, tanto una visión histórica como una visión más funcional (aunque todos los tres apartados que nombras irán en el mismo capítulo, así que imagina que la profundidad no será mucha).

    Ten en cuenta cuál es el lector objetivo de la serie, no es un curso universitario de arquitectura de ordenadores (cuando yo estudié esto en la carrera, desde la electrónica del principio hasta los sistemas operativos del final pudieron ser del orden de 8 o 10 asignaturas distintas, y aquí lo estamos condensando en un solo monográfico).

Escribe un comentario

Tu dirección de correo no es mostrada. Los campos requeridos están marcados *

Al escribir un comentario aquí nos otorgas el permiso irrevocable de reproducir tus palabras y tu nombre/sitio web como atribución.