archivo

Archivos Mensuales: agosto 2012

El QXT 640 es un clon del Sinclair QL y fue la respuesta de Sandy al ordenador CST Thor 1 de la compañía CST (otro clon del Sinclair QL). Básicamente el Sandy QXT 640 estaba formado por la placa base original de QL con 128K RAM a la que se la añadía una ampliación “Super QBoard” de la propia Sandy con 512K RAM, un puerto Centronics, el Super Toolkit II, una controladora de disquetes con una 1 o 2 disqueteras, un teclado tipo IBM-AT, una fuete de alimentación interna de 60W y 3 slots de expansión. El sistema conservaba uno de los microdrives que se colocaba debajo de una de las disqueteras.

Se comercializaron varias versiones del QXT 640. La versión con una disquetera costaba 654 libras y con doble disquetera 699 libras. También estaba disponible en forma de kit para que el usuario pudiera construir el ordenador a partir de su QL original, el precio del kit era de unas 259 libras.

Sandy QXT-640

Sandy QXT-640

Anuncios

La recursividad es uno de esos temas que la mayoría de la gente con poca experiencia en programación seguramente ha oído hablar, pero pocos lo comprenden verdaderamente. Si pregunta a esa gente que ha oído hablar de la recursividad probablemente le conteste que la recursividad es algo así como “una rutina que se llama a si misma”.

Esa es una descripción razonable, aunque es algo más que eso. Si una rutina se llamara a si misma continuamente (como en el siguiente ejemplo), ésta se estaría ejecutando de forma indefinida, o al menos mientras el ordenador no agote su memoria.


1000 DEFine PROCedure MENU
1010 MENU
1020 END DEFine MENU

Además de ser una rutina, que se llama a sí misma (o se describe en el términos de sí misma), una rutina recursiva debe tener un mecanismo para garantizar las circunstancias en las se debe llamar a sí misma y cuando se debe proceder a una salida de dicha rutina o un retorno del mencionado procedimiento (o función). Como la recursividad es un tema difícil de explicar clara y brevemente en palabras sencillas, voy a presentar unas pocas rutinas de ejemplo para demostrar los usos de la recursividad en la programación en SuperBASIC.

La mayoría de los programadores que comprenden y utilizan la recursividad son capaces de detectar las tareas que requieren el uso de la recursividad, casi por instinto, pero pocos son capaces de explicar exactamente cómo llegaron a esa decisión. Sin embargo, una vez dominada la recursividad, ésta puede ser una poderosa y eficiente herramienta de programación.

La recursividad puede ser pensada como un proceso en el que una tarea puede ser desglosada en partes más manejables y pequeñas de una forma ordenada. Por lo tanto, la solución a esa tarea o problema se describe en términos de soluciones a problemas similares más pequeños. En este punto, los cerebros de muchas personas tienden a fundirse tratando de seguir las explicaciones, por lo que vamos a considerar un ejemplo muy simple para tratar de ilustrar lo que esto significa.

Supongamos que usted tiene un ejército. Su oponente tiene también un ejército con el mismo número de soldados que usted, por lo que seguramente no le guste la idea de entrar en una batalla donde existe un alto riesgo de que muchos de sus mejores soldados puedan ser asesinados o heridos. Así que decide optar por la estrategia de dividir a su enemigo en grupos más pequeños para simplificar el ataque. Esta estrategia podría ser denominada “divide y vencerás” – la reducción de un problema por medio de la división en varias secciones más pequeñas hasta que se haya terminado.

define procedure Conquista (grupos)
Si todos divididos entonces retornar
Dividir en otra sección (grupos - 1)
Conquistar ese grupo
end define

Tomemos ahora un ejemplo simple de la impresión de una serie de números del 1 al valor ‘n’ (cualquier número entero). Normalmente, enfocaremos el problema simplemente llamado a un procedimiento o instrucción de IMPRIMIR dentro de un bucle FOR. Sin embargo, podríamos escribir lo mismo mediante una rutina recursiva. Lo que estamos tratando de hacer es muy simple para intentar concentrarnos en la teoría y no en el problema en sí mismo. Empezaremos por desglosar el proceso en componentes más simples. Tenemos que imprimir los números, cada uno de los cuales es más grande que el tiene ante sí.

define procedure imprimir_numero (valor)
  Si hemos alcanzado el límite, entonces salir 
       de este prodecimiento
  Imprimir el siguiente número con imprimir_numero
       (valor - 1)
  Imprimir el número en la pantalla
end define

Esto es un pseudocódigo. Ahora vamos a escribir el código en un correcto SuperBASIC.

10 CLS : Print_Number_Up_To 10
20 :
100 DEFine PROCedure Print_Number_Up_To (value)
110   IF value = 0 THEN RETurn
120   Print_Number_Up_To value-1
130   PRINT value
140 END DEFine Print_Number_Up_To

La línea 110 comprueba si se debe ejecutar una vez más el bucle o si se deja de ejecutar la llamada. La línea 120 llama al mismo procedimiento 10 veces, y en cada llamada se decrece el valor pasado al procedimiento en 1 (al igual que un bucle al contar). Esto se va ejecutando hasta que el valor sea igual a 0 (10 veces). En definitiva se está llamado al mismo procedimiento para imprimir pero con 10 parámetros diferentes, cada llamada tiene un parámetro que es diferente a la llamada anterior, en este caso es el valor de la llamada anterior menos 1. Una vez que los 10 valores se calculan, hay 10 procedimientos, cada uno listo para imprimir su propio valor. Después de la décima definición, cuando el valor del parámetro “valor” se ha convertido en 0, los retornos comienzan a entrar en vigor de tal forma que hay 10 vueltas atrás. Recuerde que cada retorno vuelve a la llamada más reciente al procedimiento definido, de modo que la impresión se sucede en el orden inverso a aquel en el que los números se han definido.

La línea 10 hace una primera llamada al procedimiento con el valor más alto (en este caso 10). En esta primera llamada, el valor es 10, por lo que el retorno no es ejecutado. El programa a continuación pasa a la línea que contiene la llamada a imprimir un número pero especificando un nuevo valor. El próximo número en dicha llamada es el 9, con lo que el procedimiento se llama de nuevo con “valor-1”, o 10-1 en este caso. Esta llamada aún no retorna ya que el valor que se le pasa a la rutina sigue sin ser 0, con lo que se invocará de nuevo a si mima con el valor 9-1 u 8. Este se ejecuta una y otra vez hasta que se alcanza el valor 0, entonces los beneficios de la rutina recursiva empieza a entrar en acción. Cuando se alcanza el 0, la llamada que retoma su ejecución era cuando el parámetro pasado tenía el valor 1, por lo que éste se imprime en primer lugar. Luego retornará cuando el valor contenía 2, y así sucesivamente hasta retornar a la primera llamada donde el valor tenía 10. Espero que todo esto tenga sentido para usted. En caso de que no, aquí va una traza de la ejecución del programa.

10 llamada a Print_Number_Up_To con “value” = 10
100 definición del procedimiento, se le da el valor 10
     a la variable llamada "value"
110 se evalúa la expresión si "value" ha alcanzado
    el valor de 0
120 el valor 0 no se ha alcanzado, entonces llamamos al
    procedimiento otra vez con el valor de 10-1, (o 9)
100 regresa a la definición del procedimiento. 
    Esta vez, value=9
110 comprueba si se ha alcanzado 0, en este caso aun no.
120 se invoca de nuevo al procedimiento con 
    value-1 (9-1, u 8)
100 ... y así sucesivamente hasta que el value=0
110 se llega en este momento a value=0, así que se retorna 
    desde este procedimiento a la llamada anterior donde
    el valor previo de value era 1 (recuerde que nosotros 
    llamamos la última vez en la línea 120 convalue=1)
130 ahora se imprime el valor (1)
140 end define - fin de llamada al procedimiento, así 
    que se retorna a la llamada anterior, esta llamada fue
    ejecutada cuando value contenía el valor de 2. 
    Retornando a la siguiente sentencia después de 
    la línea 120 que contenía la llamada.
130 se imprime el valor actual (2) y así sucesivamente
    hasta que se imprimen los 10 valores.

Por supuesto, enfocar este problema de imprimir números de esta manera es como utilizar un martillo para cascar una nuez. Pero me parece que ayudan a explicar la técnica porque se trata de un ejemplo corto y bastante fácil de seguir paso a paso. Escribir cada paso sobre el papel le ayudará a entenderlo.

La recursividad a menudo se utiliza cuando se necesita una rutina similar para una serie de operaciones o donde los cálculos que se exijan sólo contienen una ligera diferencia en cada llamada a la rutina, pero donde la rutina sea suficientemente capaz de hacer frente a estas variaciones y las condiciones finales son suficientemente bien conocidas por ser claramente definibles. Esto es muy importante en la recursividad, la prueba a realizar cuando la rutina tiene que dejar de llamarse a si misma es vital para garantizar el correcto funcionamiento y el éxito en la finalización correcta. El siguiente ejemplo no es un programa real (¡no intente ejecutarlo como un programa BASIC!), es un “recorte” de código que le ayudará a mostrar el algoritmo de una forma simplificada de cómo funciona de forma general una rutina recursiva.

DEFine PROCedure Rutina_Recursiva (parámetro)
  LOCal lista de valores locales
  ... aquí se coloca el código que se precise
  IF fin condición THEN RETurn
  Rutina_Recursiva con parámetros variable
  Acciones que se ejecutan mientras
     se desenreda la llamada recursiva
END DEFine

La rutina establece el valor de sus propias variables cada vez que se ejecuta la llamada, además comprueba si el final de condición se cumple o no, entonces se llama a sí misma de nuevo con datos ligeramente diferentes, según sea necesario. Una cosa que podría ser no obvio es la necesidad de variables locales en el procedimiento. Si necesita crear variables temporales para calcular o apoyar a los valores que difieren en cada llamada al procedimiento, es necesario que las diferentes variables en cada llamada no destruyan los valores con que hemos trabajado, esto en muchas ocasiones es difícil de establecer.

En esta etapa, puede que no sea obvio el por qué alguien necesite o quiera usar la recursividad. La primera vez que me enfrenté a la recursividad hace algunos años, me pareció una especie de técnica repetitiva inventada por alguien muy inteligente que quería impresionar a los demás con una especie de código mágico que nadie pudiera entender. Siempre parece como si hubiera una forma más simple de hacer las cosas sin un código tan enrevesado. De alguna manera esto es cierto, por lo general hay una forma no recursiva de resolver un problema implementado como una llamada recursiva, pero por lo general suele ser más largo, menos elegante y menos eficiente (por no hablar de más lento). El arte reside en ser capaz de detectar los casos en que la recursividad es un beneficio para el programador. En cierta medida, este viene con experiencia y con conocimiento de un “estándar” en aplicaciones y rutinas donde se utiliza la recursividad. En términos de los procesos del pensamiento, usted tiene que meditar repetidamente patrones en los que se debería aplicar, o cuestionarse si una tarea se puede dividir y hacer más eficiente en secciones (de tipo “divide y vencerás”). Recuerdo que en una lectura de un libro de texto, hace algún tiempo, se mencionaba que la recursividad es un acto de fe, ya que es muy difícil seguir exactamente lo que uno hace en una rutina recursiva, es difícil estar seguro de que la rutina se llevará a cabo exactamente como usted espera o como piensa que se llevará a cabo. Seguramente cuando usted escriba la rutina al final se sorprenderá a si mismo de lo que la rutina está haciendo realmente.

A continuación le presentaré algunos ejemplos reales de rutinas recursivas, algunas usarán funciones y otros procedimientos. Espero que al menos algunos de estos ejemplos le ayude a ver cómo funciona la recursividad, y el motivo por el cual la recursividad puede ser una técnica de programación muy útil.

– Factoriales. Esta rutina matemática es uno de los ejemplos clásicos de la recursividad como técnica de programación. Se trata de calcular el total de una serie de productos de números, desde 1 hasta n. n! que es pronunciado como “n factorial”, consiste en el producto de todos los números enteros desde 1 hasta n.

n! = n * (n-1) * (n-2) … * 2 * 1

– Exploración de un sub-directorio. La rutina permite explorar todos lo ficheros que cuelgan de todos los sub-directorios de un disco duro (o disquete de alta capacidad). Sólo funciona en sistemas con «nivel 2» de directorios (creados con el comando MAKE_DIR básico, por ejemplo).

– Una rutina de ordenación de cadenas muy rápida, llamada “Quicksort”, donde los datos se van dividiendo en grupos más pequeños, cada uno de los cuales se van ordenando y dividiendo hasta quedar la lista totalmente ordenada. El algoritmo consiste en una rutina que se llama a si misma para ir ordenando los pequeños grupos que se van creando.

– Una rutina de relleno, donde polígonos irregulares se pueden rellenar con un determinado color. Esta rutina no es tan rápida como otras que se puedan encontrar en programas comerciales, pero funcionan correctamente. Desafortunadamente se requiere un toolkit para el uso de una instrucción que nos da el color de un pixel de la pantalla. Yo he usado mi propia extensión, PIXEL% x,y (donde x e y son las coordenadas de un punto en una pantalla estándar del QL, 512×256) pero se puede utilizar rutinas equivalentes como las de Simon N. Goodwin, las cuales se pueden llamar cambiando la instrucción y empleando los parámetros adecuados. De hecho, hay dos rutinas, una muy simple, que ilustra el principio básico (que funciona, pero no es muy eficiente), y la segunda, que incluye un elemento de buffering (o apilado) para reducir el coste general y llamar a la rutina de trabajo más rápidamente que el primer ejemplo.

– El rompecabezas llamado Torres de Hanoi. Consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en la primera varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento. El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente. Las reglas son: 1) Sólo se puede mover un disco cada vez, 2) un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo y 3) sólo puedes desplazar el disco que se encuentre arriba en cada varilla. No es un problema muy complejo de resolver, pero muestra cómo utilizar las técnicas de recursividad para resolver el rompecabezas de una manera elegante.

1. Factoriales

Esta rutina nos permite calcular el producto de una serie de números hasta llegar a un valor dado. El término “n!” (pronunciado n factorial) se utiliza para representan este producto.

n! = n * (n-1) * (n-2) … hasta … * 2 * 1

Así por ejemplo 5! es 5*4*3*2*1, que resulta 120. Esto se puede codificar con un bucle FOR de la siguiente manera:

INPUT 'Factorial de > ';n
LET factorial = 1
FOR number = n TO 1 STEP -1
  LET factorial = factorial*number
END FOR number

Esto es perfectamente válido, pero vamos a hacer lo mismo empleando una función recursiva. El cálculo se puede realizar siguiendo las mismas etapas tal cual está escrito en la fórmula anterior, la multiplicación de un número por un número menos de la secuencia hasta llagar a 1. Por lo tanto, la secuencia incluye (i) el cálculo del número próximo, (ii) la actualización del valor total multiplicando el total por el próximo valor hasta que lleguemos hasta el último valor que es 1.

100 INPUT 'Factorial de > ';n : PRINT Factorial(n)
110 DEFine FuNction Factorial (num)
120   IF num = 1 THEN RETurn 1
130   RETurn num * Factorial (num - 1)
140 END DEFine

Esta rutina en realidad es algo más extensa que la primera, aunque se debe en parte a la definición de la función. Esta función devuelve el primer número multiplicado con la llamada a si misma con el siguiente valor descendente como parámetro. Cuando se llega a 1 tenemos simplemente que devolver ese valor 1 (línea 120) en lugar del cálculo de la multiplicación con el siguiente número de la serie (línea 130).

2. Lectura de subdirectorios

Esta rutina sólo tiene sentido para aquellos que tengan instalados en sus QL las facilidades de manejo de subdirectorio. Esto incluye la Gold Card, Super Gold Card, QXL, los emuladores de Atari ST-QL, también son validos aquellos sistemas con Trump Cards o SuperQBoards con una actualización nivel-2 de la ROM (actualización de Jurgen Falkenburg o Jochen Merz).

Al hacer un DIR de un disquete o disco duro que contiene directorios se obtienen los archivos del directorio actual y los nombres de los posibles subdirectorios, los cuales se muestran precedidos del símbolo ‘->’. Para obtener una lista de los archivos de esos subdirectorios se tiene que hacer otro DIR de ellos. Si esa lista contiene a su vez otros subdirectorios se deben ejecutar de forma sucesiva los comandos DIR sobre ellos para obtener la lista completa de todos los ficheros y subdirectorios del disco. Nos será útil plantear, para evitar esto, un procedimiento o rutina para explorar todos los archivos de todos los directorios a partir de un directorio concreto especificado. Así cuando empezamos a rastrear siguiendo adelante debemos explorar todos los subdirectorios, pero una vez agotado un camino debemos iniciar otros caminos si los hubiera hasta completar toda la exploración. De esta forma lograríamos enumerar todos los archivos y subdirectorios.

Aquí hay un resumen de cómo vamos a construir la rutina:

procedure extender_dir (unidad,directorio)
  Variables locales
  Abrir directorio
  Si fallo, retornar
  Leer todo los nombres en directorio
    ¿se ha terminado? si es así, cerrar directorio y salir del bucle
    obtener seiguiente fichero
    ¿es un nombre de directorio?
      si, hacer extender_dir en ese direcotorio llamada recusriva 
      no, imprimir ahora el fichero
    fin si
  final del bucle de lectura de nombres
fin de procedure

y así es como he decidido escribir la rutina en SuperBASIC:


100 REMark extended dir of all sub-directories
110 Extended_DIR 'win1_',''
120 :
130 DEFine PROCedure Extended_DIR (drive$,directory$)
140   LOCal loop,ch,d$,fp,n$
150   ch = FOP_DIR (drive$&directory$) : REMark open channel to directory
160   IF ch  0 THEN 
220       REMark a directory length of 0 may be a deleted file
230       BGET #ch: REMark file type byte
240       IF CODE(INKEY$(#ch)) = 255 THEN 
250         REMark this name is a subdirectory, so we need to DIR this
260         REMark if you want directory names printed, add this
270         REMark PRINT d$;' ->'
280         Extended_DIR drive$,d$
290       ELSE 
300         PRINT d$
310       END IF 
320     END IF 
330     fp = fp + 64
340   END REPeat loop
350 END DEFine Extended_DIR

Tenga en cuenta que la rutina, tal como está, no imprime los nombres de directorios sino sólo los nombres de archivo. Para imprimir los nombres de directorios, al igual que un comando DIR, debe eliminar la declaración REMark de la línea 270. Recuerde que la llamada a la rutina debe hacerse con dos parámetros, el primer parámetro con la unidad y el segundo con el nombre del directorio. Éstos se usan por separado dentro del cuerpo de la rutina.

3. Rutina de ordenación Quicksort

La rutina “quicksort” es una de las rutinas de ordenación más rápidas que pueden ser programadas en SuperBASIC. He encontrado dos variantes. La primera variante es más fácil de usar, pero no es tan rápida como la segunda variante, que tiene ciertos requisitos especiales que la hacen un poco menos conveniente en cuanto a su uso.

Quicksort hace su trabajo barajando punteros a las secciones de datos que van a ser ordenados y ordenando esas en secciones más pequeñas. Esto reduce el número total de pasadas a través de los datos que ralentiza otras rutinas de ordenación tales como el método “Burbuja” (Bubble Sort). Ya hemos utilizado la frase “divide y vencerás” para describir cómo trabajan algunas rutinas recursivas, y esto es precisamente lo que hace esta rutina de ordenación.

Esta rutina no es un ejemplo de rutina recursiva muy fácil de seguir – si usted desea seguir paso a paso el funcionamiento del programa, trate de asignar un pequeño conjunto de datos que se vayan a ordenar y trate de hacer un seguimiento, en cada parte del programa, de cómo se van clasificando dichos datos hasta conseguir el objetivo de ordenar la lista completa.

Este procedimiento en SuperBASIC está diseñado para ordenar cadenas; para ordenar arrays de números simplemente cambie las cadenas en la rutina (el nombre termina con $) por variables numéricas (enteros, finalizando con %, o variables de coma flotante). El segundo parámetro es el índice inferior del array que va a ser ordenado, generalmente 0, y el tercer parámetro es el índice más alto de dicho array (NO el total de número de items) generalmente el número total de elementos-1, siempre y cuando el primer subíndice sea 0.

100 Q_Sort array_name$,0,entries%-1
110 :
120 DEFine PROCedure Q_Sort (array$,bottom,top)
130   LOCal sort_loop,low,high,ptr
140   low  = bottom
150   high = top
160   ptr  = bottom
170   REPeat sort_loop
180     IF low >= high THEN EXIT sort_loop
190     IF array$(low) > array$(high) THEN
200       REMark need to swap these strings
210       temp$        = array$(low)
220       array$(low)  = array$(high)
230       array$(high) = temp$
240       REMark how do we shuffle pointers to sections
250       IF ptr = low THEN
260         low = low + 1
270         ptr = high
280       ELSE
290         high = high - 1
300         ptr  = low
310       END IF
320     ELSE
330       IF ptr = low THEN high = high - 1 : ELSE low = low + 1
340     END IF
350   END REPeat sort_loop
360   IF ABS(top - bottom) THEN RETurn : REMark can't sort 1 item!
370   Q_Sort array$,bottom,ptr - 1
380   Q_Sort array$,ptr + 1,top
390 END DEFine Q_Sort

4. Relleno de gráficos

Una rutina de relleno de gráficos consiste en llenar un área de la pantalla (regular o irregular) con un determinado color. Sea cual sea el color de relleno, la rutina debe asegurarse de no pintar zonas fuera del contorno delimitado por el área (polígono regular o irregular). La rutina de relleno comienza a partir de un punto situado dentro del área que se quiere rellenar, a partir de ahí, la rutina va poco a poco rellenando del color elegido el área demarcada. Imagine el boceto de una casa con ventanas, puertas y el techo ya diseñado. A partir de algún punto en la pared, se cubre toda la superficie de pared de toda la casa de un determinado color pasando alrededor de las ventas y puertas sin salirse fuera.

El principio básico es que, cualquiera que sea la línea a partir de la cual vamos a empezar el llenado, buscaremos a la izquierda para ver si podemos llenar, luego buscaremos la derecha para comprobar lo mismo, a continuación miramos encima y a continuación debajo para ver si podemos avanzar en esas direcciones. Si podemos hacerlo llenaremos con nuestro color elegido y a continuación seguiremos haciendo lo mismo hasta que no podamos ir más lejos. Debemos volver sobre nuestros pasos al punto que partimos en caso de que no podamos avanzar por una determinada dirección. Con un polígono irregular, lo que suele ocurrir es que se llena en la medida en que se pueda avanzar y, a continuación, empezar desde el punto de comienzo para encontrar otra dirección a partir de la cual se pueda continuar con el trabajo, y así sucesivamente. A este tipo de relleno a menudo se denomina por inundación (flood) porque emula a cómo el agua va inundando un lugar, llenando poco a poco bit a bit.

Esta rutina difiere con respecto al comando FILL del QL en el sentido que puede hacer frente a las llamadas formas re-entrante (formas irregulares que se pueden doblar de nuevo en si mismas). El comando FILL del QL funciona de una manera diferente a este tipo de relleno, y eso significa que (por lo general) es más rápido que la rutina de llenado por inundación, pero la rutina por inundación puede hacer frente a una variedad más amplia de formas y polígonos que se vaya a rellenar, por lo tanto, es capaz de llenar formas irregulares bastante complejas, mientras que para hacer lo mismo es posible que necesite más de un comando FILL del QL para rellenar una figura compleja correctamente. La otra gran diferencia es que la rutina por inundación trabaja correctamente sólo después de que el perímetro haya sido dibujado completamente, mientras que el comando FILL almacena los puntos y líneas a rellenar como un esquema del perímetro a dibujar, normalmente rellenando la figura cuando el perímetro esté cerrado. De cara al usuario hay poca diferencia, el resultado final es normalmente similar, pero para el programador hay una gran diferencia en cuanto a la codificación de las dos rutinas.

Para hacer que la rutina por inundación funcione, nosotros necesitamos una rutina que examine el color de un determinado pixel en la pantalla. Muchos toolkits de extensión al BASIC suministran utilidades de este tipo (por ejemplo la función PIXEL del DIY Toolkit). En esta rutina yo he usado una extensión llamada PIXEL% que requiere los siguientes parámetros (adapte esta rutina a las extensiones que usted usa). Desafortunadamente, el SuperBASIC estándar del QL carece de una función de este tipo.

x = coordenada x a través de la pantalla
y = coordenada y hacia abajo en la pantalla

Ambos, ‘x’ e ‘y’ asumen que estamos en una ventana que cubre el total de la pantalla, por ejemplo 0,0 es la esquina superior izquierda de la pantalla.

El esquema de la rutina no es demasiado difícil de comprender, pero la forma final de las rutinas es horrible para tratar de entenderlas, especialmente en lo más avanzado de las dos rutinas, que incluye un sistema de buffering para reducir el número masivo de llamadas recursivas realizada por el sistema, asi como una ayuda para acelerar la segunda rutina en comparación con la primera.

procedimiento relleno_desde punto comienzo x,y 
  si punto no rellenable entonces retornar
  rellenar a la izquierda de este punto 
  rellenar a la derecha de este punto 
  desde izquierda a derecha
    relleno_desde punto encima esta linea 
    relleno_desde punto debajo esta linea 
  fin escaneo izquierda a derecha 
fin definición procedimiento

Esto puede ser escrito de la siguiente forma, usando la mencionada extensión PIXEL%(x,y). Las primeras 3 líneas dibujan una caja dentro de otra con una brecha entre ellas, que va a ser rellenada por la rutina. La segunda línea en el procedimiento Fill_Outline (IF y255) protege el programa cuando el color de relleno intenta ir fuera de la parte superior o inferior de la pantalla. La rutina es llamada pasándole 4 parámetros al procedimiento Fill_Outline:

x = coordenada x a partir de la que se comienza el relleno (0 a 511)
y = coordenada y a partir de la que se comienza el relleno (0 a 255)
direction = dirección en que la rutina rellena, -1 = arriba, +1 = abajo
colour = número del color de la tinta usado en el relleno
100 WINDOW 512,256,0,0 : CLS : INK 7
110 BLOCK 100,100,50,50,7 : BLOCK 96,98,52,51,0
120 BLOCK 60,80,70,60,7   : BLOCK 56,78,72,61,0
130 Fill_Outline 100,55,-1,7 : REMark -1 = upward, +1 = downward
140 STOP
150 :
160 DEFine PROCedure Fill_Outline (x,y,direction,colour)
170   LOCal loop,a,lp%,rp%
180   IF y  255 THEN RETurn
190   IF PIXEL%(x,y) = colour THEN RETurn
200   lp% = x
210   REPeat loop
220     IF lp% = 0 THEN EXIT loop
230     IF PIXEL%(lp%-1,y) = colour : EXIT loop
240     lp% = lp% - 1
250   END REPeat loop
260   rp% = x
270   REPeat loop
280     IF rp% = 511 THEN EXIT loop
290     IF PIXEL%(rp%+1,y) = colour : EXIT loop
300     rp% = rp% + 1
310   END REPeat loop
320   BLOCK rp%-lp%+1,1,lp%,y,colour
330   FOR a = lp% TO rp%
340     Fill_Outline a,y+direction,direction,colour
350     Fill_Outline a,y-direction,-direction,colour
360   END FOR a
370 END DEFine Fill_Outline

El problema con esta rutina es que se llega a un callejón sin salida y, a continuación, ha de volver sus pasos hacia atrás para llenar en una dirección opuesta, esto consume mucho tiempo para algunas figuras. Podemos mejorar esto añadiendo un buffer que filtra algunos puntos en la dirección opuesta que no pueden ser rellenados, lo que a su vez significa que no tiene que volver sobre una gran cantidad de píxeles que ya se han llenado. Aún así sigue existiendo un retraso después del llenado en el último punto, pero se puede ahorrar tiempo utilizando una pila o un buffer similar a este. En el relleno de puntos en la dirección opuesta se actualizan a medida que la rutina va en una dirección, por lo que la pila (actualmente un array de enteros) crece para recordar las coordenadas rellenables fuera del punto de relleno original, entonces una vez que la rutina para en esa dirección, empieza a leer coordenadas de píxel de la pila para recordar donde volver. A continuación, trata de avanzar en la dirección opuesta, pero en caso de encontrar otra vez puntos fuera de la dirección de relleno que pueda comprobar más tarde, también los añade a la pila. Y así continúa el proceso hasta que haya terminado todos los puntos.

100 WINDOW 512,256,0,0 : CLS : INK 7
110 BLOCK 100,100,50,50,7 : BLOCK 96,98,52,51,0
120 BLOCK 60,80,70,60,7   : BLOCK 56,78,72,61,0
130 Fill_From 100,55,-1,7 : REMark -1 = upward, +1 = downward
140 STOP
150 :
160 DEFine PROCedure Fill_From (fx,fy,direc,col)
170   LOCal xst%(512),yst%(512),stack%
180   REMark this routine requires a 'stack'
190   DIM xst%(512),yst%(512)
200   stack% = 0 : REMark nothing on stack at first, of course!
210   Fill_Outline fx,fy,direc,col
220 END DEFine Fill_From
230 :
240 DEFine PROCedure Fill_Outline (x,y,direction,colour)
250   LOCal loop,a,lp%,rp%
260   IF y  255 THEN RETurn
270   IF PIXEL%(x,y) = colour THEN RETurn
280   lp% = x
290   REPeat loop
300     IF lp% = 0 THEN EXIT loop
310     IF PIXEL%(lp%,y-direction) > colour THEN xst%(stack%) = lp% :
             yst%(stack%) = y-direction : stack% = stack%+1
320     IF PIXEL%(lp%-1,y) = colour : EXIT loop
330     lp% = lp% - 1
340   END REPeat loop
350   rp% = x
360   REPeat loop
370     IF rp% = 511 THEN EXIT loop
380     IF PIXEL%(rp%,y-direction) > colour THEN xst%(stack%) = rp% :
             yst%(stack%) = y-direction : stack% = stack%+1
390     IF PIXEL%(rp%+1,y) = colour : EXIT loop
400     rp% = rp% + 1
410   END REPeat loop
420   BLOCK rp%-lp%+1,1,lp%,y,colour
430   FOR a = lp% TO rp%
440     Fill_Outline a,y+direction,direction,colour
450   END FOR a
460   REPeat loop
470     IF stack% = 0 : EXIT loop
480     stack% = stack% - 1
490     Fill_Outline xst%(stack%),yst%(stack%),-direction,colour
500   END REPeat loop
510 END DEFine Fill_Outline

La rutina tiene el inconveniente de que en figuras muy complejas puede provocar el agotamiento del espacio de la pila. En la gran mayoría de los casos, una pila de 512 espacios será suficiente. Estas rutinas tienen como ventaja que muestran en la pantalla la mayor parte de lo que está sucediendo, así que usted puede hacerse una idea de cómo “piensa” la rutina. Después de un tiempo, incluso con figuras complejas, ¡puede predecirse cómo va a ser rellenada la figura!

5. El puzzle de las Torres de Hanoi

El puzzle de las Torres de Hanoi consta de tres varillas y varios anillos de diferente diámetro. Lo que usted tiene que hacer es mover todos los anillos de la primera varilla a la segunda siguiendo las normas siguientes. Sólo puede mover un anillo a la vez. Ningún anillo puede colocarse en una varilla donde un anillo más pequeño quede debajo de uno mayor (es decir, los anillos grandes no pueden colocarse encima de uno menor). Por lo tanto, debemos utilizar la tercera varilla como almacén temporal. Sólo se puede desplazar el anillo que se encuentre en la parte superior de la varilla. De esta manera podemos ir desplazando los anillos de la primera varilla a la segunda de tal manera que al final del rompecabezas la segunda varilla contenga todo los anillos en el mismo orden que se encontraban en la primera varilla. Se puede dar una solución a este problema simplemente usando una rutina recursiva para mover progresivamente los anillos de una varilla a otra. Puede, si lo desea, agregar rutinas para animar la solución. Si usted es realmente ambicioso, y ha visto el pequeño robot de Tony Firshman y Reeves Laurence en el stand de TF Serivces en los “QL Shows” controlado por un QL equipado con una interfaz y Minerva, ¡tal vez desee considerar la manera de programar el robot para que pueda solucionar este puzzle! El programa puede hacer frente a cualquier número (dentro de lo razonable) de anillos, siempre empezando con el anillo 1 para el más pequeño y el número más alto para el anillo más grande. Con un número de varillas pequeño, podemos seguir los movimientos, por ejemplo, con una pequeña pila de monedas, siempre y cuando se puedan recordar que moneda estaban en qué anillo. Con más de 3 ó 4 anillos las instrucciones pueden llegar a ser bastante largas, dada la necesidad de estar rotando continuamente los anillos para evitar que el animo más grande esté por encima de otro más pequeño.

He aquí un programa en SuperBASIC que resuelve el rompecabezas.

100 REMark Towers of Hanoi puzzle
110 INPUT'How many rings > ';rings
120 Hanoi rings,1,2,3
130 :
140 DEFine PROCedure Hanoi(r,peg_a,peg_b,peg_c)
150   IF r = 0 THEN RETurn
160   Hanoi r-1,peg_a,peg_c,peg_b
170   PRINT'Move ring ';r;' from peg ';peg_a;' to peg ';peg_b
180   Hanoi r-1,peg_c,peg_b,peg_a
190 END DEFine Hanoi

Por ahora, podría ser suficiente para comprender cómo trabaja esta rutina el emplear una pila de monedas y reproducir la secuencia según la imprime el programa. Escriba un flujo generalizado de lo que hay que hacer y verá que el patrón a seguir emerge en su cabeza sin darse cuenta. Verá entonces que el problema es fácil de resolver. Escribir un programa para resolver esto no es una tarea obvia, especialmente para producir una solución tan corta como esta.


Fuente:
Artículo original: http://www.dilwyn.me.uk/docs/articles/recursion.zip
Dilwyn Jones (Tal-y-bont, Gales, Reino Unido).

QStripper es un programa de códgio abierto para sistemas Windows y Linux que permite abrir múltiples documentos Quill del Sinclair QL y exportarlos a diversos formatos.

Los formatos de exportación soportados son:
– Texto
– Html
– Docbook XML
– PDF
– ODF, Open Document Format para Open/Libre Office.

Antes de la exportación, el programa permite la edición del documento Quill así como su impresión.

El autor de QStripper es Norman Dunbar, y tanto el código fuente como los binarios se pueden descargar desde el sitio Web del proyecto http://qstripper.sourceforge.net/.

QStripper

QStripper

Los entusiastas del QL que escriben artículos en revistas y post en foros o blogs tienden a utilizar a menudo abreviaturas. En esos artículos o post se da por sentado que el lector entiende dicha abreviaturas, pero el problema es que eso no siempre es así, lo que dificulta la comprensión del texto para los usuarios ocasionales del QL o los usuarios con menos experiencia. Esto no pasa solamente en la plataforma QL sino en cualquier otra plataforma informática actual o del pasado, donde cada una de ellas tiene su típica “jerga” de términos particulares.

Para facilitar la compresión de esas abreviaturas, a continuación presentamos a modo de glosario, las más comúnmente usadas en el mundo QL.

AH, JM, JS, MG – nombres abreviados dados a las diferentes versiones de la ROM del QL emitida por Sinclair. Las letras se refieren en realidad a la versión de SuperBASIC. Para la versión de SuperBASIC de Minerva (otra versión posterior del sistema operativo, ver más abajo) el equivalente es “JSL”, mientras que SBASIC de SMSQ (ver más abajo) se utiliza ‘HBA’

ALTKEY – es una facilidad proporcionada por Toolkit 2 (ver más abajo) para asociar una cadena de caracteres a una combinación de teclas. Así cuando se mantiene presionada la tecla ALT junto con otra tecla especifica definida por el usuario, da como resultado una secuencia de texto para ahorrar algo de mecanografía. Por ejemplo, si se define ALTKEY ‘p’,’print’ y más tarde tecleas ALT p, el sistema imprime por consola el texto “print”.

BOOT – Un programa o un pedazo de código que define la forma en que un programa o equipo se inicia. En el QL tiene un significado particular, ya que es un programa especial que se ejecuta automáticamente cuando el QL arranca y normalmente es un programa SuperBASIC.

CON – Ventana de la consola. Un tipo de ventana de pantalla en el QL en la que se puede imprimir información y desde la que se puede capturar información del teclado. Si ha abierto una ventana de tipo CON, no sólo se puede utilizar PRINT para escribir la información en la pantalla, también puede utilizar INPUT para permitir que el usuario escriba en la información en esa parte de la pantalla. Cuando el QL se pone en marcha, SuperBASIC comienza con tres canales CON abiertos en la pantalla, identificados como #0, #1 y #2.

CTRL-C. Se trata de una combinación de teclas (las teclas ‘CTRL’ y ‘c’) con un significado especial en el QL, destinado a conmutar entre los distintos programas que están en memoria ejecutándose al mismo tiempo. Este proceso de conmutación entre los programas se denomina “conmutación de tareas”.

DD – Doble Densidad, se refiere normalmente a un tipo de disco flexible o de disquetera.

DS – (Double Sided) (doble cara), normalmente se refiere a un tipo de disco flexible o de disquetera.

ED – (Extra Density) Densidad extra o extra alta densidad. Se refiere a los discos flexibles de 3.2 megabytes para el QL o a sus disqueteras con las que se pueden formatear estos discos de 3.5 pulgadas.

EE – (Extended Environment), un término usado para describir la combinación de PTR_GEN, WMAN y HOT_REXT que le dan al QL un sistema para la restauración de contenido de ventanas, teclas de acceso rápido, manejo de menús estándar y cosas así. Este término equivalente también a “Pointer Environment” (PE).

FDD – (Flopy Disk Drive), unidad de disco flexible.

GC – Gold Card. Una tarjeta de ampliación muy popular para el Sinclair QL. Incluye un microprocesador más potente, ampliación de memoria y controladora de disquetes.

HERMES – No es una abreviatura, este es el nombre de un chip que sustituye al procesador secundario 8049 que se incluye en el QL original. Lo comercializó TF Services y está diseñado para mejorar el manejo del teclado, los puertos serie y el sonido.

HOT_REXT – Es una parte de “Pointer Environment” (o “Extended Environment”). Este archivo controla las teclas de acceso rápido (ver más abajo), y proporciona una serie de nuevos comandos al SuperBASIC que permiten el control de las teclas de acceso rápido para iniciar los programas o realizar acciones específicas independientes del programa que esté utilizando en ese momento. Por ejemplo, puede definir una tecla de acceso rápido que cuando se presiona se iniciaría una copia de Quill independientemente de lo que se estuviera haciendo en ese momento.

HOTKEY – Es un término equivalente a HOT_REXT descrito anteriormente.

I2C – Es un bus de sistema utilizado por Minerva MK 2 comercializado por TF Services.

MINERVA – Es un sistema operativo implementado en un chip para el QL que remplaza al QDOS original. Las versiones originales del sistema operativo QDOS para el QL tuvieron algunos problemas que no fueron corregidos antes de que el QL dejara de fabricarse. Minerva es el sistema operativo producido por TF Services que corrige estos problemas y que también añade algunas facilidades extra.

PAR – Abreviatura utilizada para representar a un puerto paralelo para la conexión a una impresora. En el QL original, las impresoras debían ser serie y se conectaban a cualquiera de los puertos serie del QL, SER1 o SER2. Con la introducción de la tarjeta de expansión Super GoldCard se introdujo un puerto paralelo que se identificaba como PAR. Este dispositivo existe también en un PC equipado con un emulador (como QPC), o un sistema con la QXL (ver más abajo). Un puerto paralelo difiere de un puerto serie en que el puerto paralelo puede enviar varios bits de información por un cable al mismo tiempo (normalmente 8) en lugar de enviarlos de uno en uno como el caso del puerto serie. En el QL, la impresión a través de un puerto paralelo por lo general es más rápido que por el puerto serie, pero tiene varios inconvenientes, (a) los cables tienen que ser más cortos que los serie de cara a la fiabilidad de las comunicaciones, y (b) la información generalmente sólo puede ser de salida hacia el equipo al que está conectado el QL con lo cual no es posible obtener información de vuelta, por esto no es posible conectar dos ordenadores vía el dispositivo PAR para compartir información

PTR_GEN – La interfaz de puntero para el sistema de ventanas del QL. PTR_GEN es responsable de controlar el puntero del ratón en la pantalla y de guardar y restaurar el contenido de las ventanas de programas. También permite conmutar entres distintos programas mediante la combinación de las teclas CTRL-C.

QDOS – “QL Drive Operating System” o “QL Disk Operating System”. Es el sistema operativo del QL que básicamente lo hace funcionar. QDOS es responsable de la puesta en marcha del QL cuando se enciende, y proporciona el código necesario y las rutinas que le permiten hacer cualquier cosa, desde la impresión en la pantalla, la multi-tarea de sus programas, el manejo de discos, el manejo de la red local, etc.

Q-emuLator – Un emulador para el Sinclair QL con versiones para sistemas Windows y Mac OS. Emula desde un QL básico hasta sistemas ampliados tales como Aurora, Gold Card, Q40/Q60. Existe una versión básica gratuita y otra versión comercial con funcionalidad y emulación ampliada.

QLay – Es un emulador del Sinclair QL gratuito para sistemas basados en Windows 95, DOS y Linux.

QPac – “QL Pointer Accessories”, conjunto de accesorios para el sistema de ventanas extendido (Pointer Environment) del QL. Lo conforman dos paquetes (QPac 1 y QPac2) producidos por Tony Tebby para mejorar el entorno de trabajo del QL. QPAc1 aporta una serie de programas pequeños pero útiles tales como una calculadora, una máquina de escribir y un reloj con alarma. QPAc2 además de esto aporta un sistema manejo de archivos con menús, botones para la ejecución de programas y varios servicios adicionales para facilitar el control de la multitarea y el sistema de ventanas del QL.

QPC – QL en el PC, es un emulador comercial que permite a un PC ejecutar software QL. Integra el sistema operativo SMSQ/E y es muy utilizado por la comunidad actual de usuarios QL.

QVME – Es una tarjeta gráfica para el Atari ST que permite la emulación de un sistema QDOS.

QXL – Una tarjeta que se conecta a una ranura ISA (Industry Standard Architecture) de los PC estándar, y que permite ejecutar cualquier software QL en un PC con DOS mucho más rápido que un QL original.

RAMDISK – Un driver del sistema operativo QDOS que permite almacenar información en la memoria de una manera muy similar a un disquete o un cartucho de Microdrive. El acceso es muy rápido, pero el contenido se pierde al apagar o reiniciar el QL. Útil para copiar los archivos en forma temporal en un ordenador con sola unidad de disco, por ejemplo.

SB – Ver SuperBASIC.

SBASIC – Una versión mejorada del SuperBASIC del QL, suministrada con el sistema operativo SMSQ.

SGC – Super Gold Card, es una tarjeta que mejora la Gold Card. Incluye más memoria (4 MB), un procesador más potente (68020), puerto paralelo y la posibilidad de controlar cuatro unidades de disquetes.

SER – El nombre que se da a los puertos serie del QL. Es el equivalente a los puertos COM1: o COM2: del PC. En el QL estándar y en los emuladores usaremos SER1 o SER2 para hacer referencia al puerto serie 1 o puerto serie 2 respectivamente. SER es una abreviatura de SERIE, lo que significa que cada bit de información se envía a estos puertos uno tras otro, en serie, en lugar de 8 bits a la vez.

SMSQ – Es una versión mejorada del sistema operativo original del QL. Se diseñó en principio para las tarjetas QXL de Miracle Systems. A diferencia de SMSQ/E, esté no incluye el entorno de ventaneas (PE).

SMSQ/E – Es la versión extendida del sistema operativo SMSQ para el QL. SMSQ/E integran los componentes de PE como son PTR_GEN, WMAN y HOT_REXT para el soporte del “Pointer Environment” (el entorno de ventanas del QL). Además ofrece un gran número de características adicionales a SMSQ, por ejemplo: dispositivos adicionales, el almacenamiento en buffers, la capacidad de cambiar la resolución de pantalla, etc.

SuperBASIC – Es el nombre dado a la versión BASIC del QL. Fue diseñado por una señora llamada Jan Jones de Sinclair.

THING – El término Thing es usado dentro del sistema operativo del QL para hacer referencia virtualmente a “cualquier cosa” dentro de la memoria del QL. Puede ser un controlador de dispositivo, un área de datos, puede ser un menú, puede ser una extensión del sistema, puede ser un programa, etc. La primera ventaja de los Thing es que tienen un nombre único. Se puede identificar a un Thing por su nombre, y localizarlo en la memoria del sistema. Un Thing puede estar localizado en cualquier sitio en la memoria del QL, y la única forma de encontrarlo es por su nombre (de forma similar a como nos referimos a un fichero específico en el sistema de archivos por medio de su nombre).

TK2 – Abreviatura de Toolkit 2. Consiste en un conjunto de extensiones adicionales que proporcionan al SuperBASIC comandos extra para mejorar el lenguaje BASIC y el sistema operativo del QL. Fue escrito originalmente por el gurú del QL Tony Tebby, el creador del QDOS, y está disponible en forma de chip EPROM conectable al puerto ROM del QL o como módulo software a cargar en el arranque del QL. Sin embargo, lo más común es que venta integrado en las tarjetas de expansión, talas como la TrmpCard, o las GoldCard. También se incluye con las versiones SMSQ y SMSQ/E del sistema operativo del QL.

uQLx – Un emulador gratuito del Sinclair QL para los sistemas basados en Unix / Linux. Su autor es Richard Zidlicky.

WMAN – Es el gestor de ventanas (Window Manager) que forma parte del “Pointer Environment” (PE). Proporciona un conjunto de menús y rutinas de visualización a las que un programador puede acceder para asegurar que todos los programas tienen un “estándar” de apariencia, y que todos los programas PE parezcan coherentes entre sí. Siempre se utiliza junto con PTR_GEN (véase más arriba).

——-
Fuente:
http://www.dilwyn.me.uk/docs/articles/index.html
(por Dilwyn Jones)
——-