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.
- 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. [↩]
- Dependiendo del sistema se le llama subrutina, rutina, subprograma, función, procedimiento, método… [↩]
- 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. [↩]
- 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. [↩]
The Computador mágico XXV – Ordenador C16B: subrutinas by , unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 Spain License.
{ 2 } Comentarios
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….
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