🦕 🤶🏼 👩🏽‍🎨 Escribir un intérprete BASIC al estilo de los 80 💨 🔼 🗡️

Durante varios años he estado trabajando en un proyecto personal para crear (y de hecho investigar) un "emulador falso", es decir, un emulador escrito en JavaScript para una computadora que nunca existió. Se suponía que esta máquina era un tributo a las computadoras de ocho y dieciséis bits de las décadas de 1980 y 1990.

Sin embargo, me encanta la complejidad: esta máquina también usó un nuevo conjunto de instrucciones. Es similar a los kits utilizados en esa época, pero un poco más fácil de trabajar. Nació el Retroputer . A lo largo de los años, el emulador se ha ido expandiendo y mejorando, pero lo más probable es que nunca esté "terminado" (después de todo, este es un proyecto de investigación personal).

Cuando apareció @bbcmicrobot, Quería crear algo similar para el Retroputer. Mis habilidades de desarrollo de JS se limitaban principalmente al front-end, por lo que esta sería una gran excusa para obtener algo de experiencia back-end. Solo hay un problema: Retroputer solo puede entender su propio lenguaje ensamblador. Todavía no tiene soporte BÁSICO.

Entonces se me ocurrió la creación del intérprete BASIC al estilo de los años 80, es decir, completamente en lenguaje ensamblador, como estaba entonces escrito. Decidí que valía la pena compartir mi trabajo porque a menudo no tenemos que sumergirnos en áreas que están tan lejos de las abstracciones habituales. Mi herramienta cotidiana (JavaScript) hace que muchos aspectos sean triviales y, a veces, incluso parece mágico. Comprender el nivel más bajo de procesos a menudo ayuda a comprender estas abstracciones.

Entonces empecemos.

Características de la retrocomputadora

16 ROM (KERNEL) c 1 (scratch space)

512 , 64

16- 6516, 512 4 64

4025, ,

1125

9800

Cuando escribía ensamblador para Retroputer, podía usar la muy útil herramienta Pegjs. Proporcionó una sintaxis de ensamblaje nativa rápida, pero desafortunadamente no existe nada como esto para Retroputer ASM. Es decir, tendremos que ir por el camino difícil.

El análisis en sí se realiza en varias etapas. Un lenguaje que usa un compilador analiza el código en un árbol de sintaxis abstracta (AST) (u otra representación), y luego puede usar este árbol para generar código nativo terminado. Por lo tanto, el programa debe ser sintácticamente correcto para una compilación exitosa.

Algunos intérpretes modernos también tienen este concepto, porque a menudo es útil generar un AST intermedio y ejecutarlo en lugar del código fuente.

Pero para el intérprete BASIC en una máquina con recursos limitados, será más eficiente analizar en varias etapas, algunas de las cuales ocurren en tiempo de ejecución. Sin embargo, esto significa que los errores de sintaxis no se pueden detectar hasta que ejecute el programa y navegue hasta el área del código con el error.

El análisis sintáctico BÁSICO de Retroputer consta de tres etapas:

Conversión de cadenas
Tokenización
Comprobación de sintaxis en tiempo de ejecución

Las dos primeras etapas ocurren cuando el usuario ingresa al programa (o lo descarga). Esto último ocurre durante la ejecución del programa. Básicamente, los dos primeros crean el fuselaje de la aeronave, pero no garantizan que despegará. El último tramo es un piloto de pruebas; esperamos que despegue, pero no estamos seguros de eso hasta que lo intente.

Nota: El código fuente de Retroputer BASIC (en desarrollo) está disponible en GitHub .

Conversión de cadenas

Ésta es la parte más simple de todo el proceso. La cadena introducida por el usuario se convierte a mayúsculas para simplificar (y acelerar) los procesos posteriores. BASIC no distingue entre mayúsculas y minúsculas, por lo que podemos aprovechar eso.

<pre>print 2+2
' becomes:
PRINT 2+2</pre>

Es muy fácil hacer esto en JavaScript, ¿verdad?

theLine = theLine.toUpperCase();

Pero en lenguaje ensamblador, este proceso es más detallado. Necesitamos leer el carácter, convertirlo a mayúsculas y luego almacenarlo en algún lugar.

           ld  y,  0                # y is our index
_loop:     ld  al, [d, x, y]        # [d,x] is pointer to string
           cmp al, 97               # is al (char) in range?
           brs n   _continue        # Not a lowercase char; continue
           cmp al, 123              # high portion
           brs !n  _continue        # not a lowercase char; continue
           and al, 0b1101_1111      # uppercase!
           st  [d, x, y], al        # store back (we modify the original)
_continue: inc y                    # move our index along
           cmp al, 0                # check for NULL
           brs !z _loop             # No? Go back for more.

El código anterior no coincide del todo con la semántica de la versión JavaScript del código. Una diferencia importante es que hoy usamos Unicode para trabajar con texto, por lo que convertir la entrada de minúsculas a mayúsculas a menudo puede ser más difícil y, a veces, imposible (depende del idioma). Retroputer vive en el mundo ASCII (más precisamente, en el mundo de su propia variación ASCII llamada RetSCII), es decir, todos los caracteres admitidos están codificados en ocho bits. Para muchos idiomas, esto es completamente insuficiente, pero cumple con las realidades de esa época.

Esto también significa que podemos usar una linda función ASCII para convertir de minúsculas a mayúsculas. La "A" mayúscula está representada en código ASCII 65y la "a" minúscula está representada por el código97... Si está familiarizado con los poderes de dos, entonces debería haber notado esta diferencia.

Entonces resulta que las letras minúsculas se especifican mediante un número que es exactamente 32 más que el número de letras minúsculas. Si sabemos que el valor está en el rango correcto, ¡solo necesitamos restar 32!

Este enfoque funciona, pero podemos modificar un poco los bits. En el caso de Retroputer, esto no será más rápido que la resta, sin embargo, en ausencia de resta, no tendremos que prestar atención a la bandera de llevar / pedir prestado durante los cálculos. Resulta que podemos usar bit anda bit para desactivar el bit en el lugar del valor 32.

and al, 0b1101_1111         # turn off bit in 32-place
# versus
clr c                       # clear carry
sub al, 32                  # subtract 32

Pero hay una sutileza: no todo se puede convertir a mayúsculas. Por ejemplo, si el usuario agregó un literal de cadena, entonces debemos tener más cuidado, porque no queremos que Retroputer BASIC le grite constantemente al usuario con mayúsculas. (Si bien muchas computadoras de la época no tenían minúsculas, el Retroputer no las tenía).

Por ejemplo:

print "Hello, World!"
' should become:
PRINT "Hello, World!"
' and not
PRINT "HELLO, WORLD!"

Esto significa que debemos realizar un seguimiento de si estamos en medio de una cadena literal. En BASIC, solo hay una designación para esto: comillas dobles. Si el carácter es una comilla doble, podemos poner la bandera y, dependiendo del valor de la bandera, convertir a mayúsculas o dejarlo como está.

Resulta que JavaScript no tiene una funcionalidad incorporada para esto, pero podemos crearlo nosotros mismos:

const len = theLine.length;
let insideString = false;
for (let i = 0; i < len; i++) {
    const ch = theLine[i];
    if (ch === `"`) insideString = !insideString;
    if (!insideString) {
        const newCh = ch.toUpperCase();
        if (ch !== newCh) theLine[i] = newCh;
    }
}

Ahora la lógica en JS se asemeja más a la versión del ensamblador, aunque nuevamente hacemos un pequeño uso del soporte Unicode en JS.

La versión de ensamblador se ve así:

           ld  y,  0                # y is our index
           ld  bl, 0                # === insideString (false)
_loop:     ld  al, [d, x, y]        # [d,x] is pointer to string
           cmp al, 34               # is al a double quote?
           brs !z  check_char       # no? should we uppercase it?
           xor bl, 0xFF             # yes? toggle insideString
_check_char:
           cmp bl, 0xFF             # inside a string?
           brs z   _continue        # yes? don't modify it
           cmp al, 97               # is al (char) in range? "a"
           brs n   _continue        # Not a lowercase char; continue
           cmp al, 123              # high portion           "z"
           brs !n  _continue        # not a lowercase char; continue
           and al, 0b1101_1111      # uppercase!
           st  [d, x, y], al        # store back (we modify the original)
_continue: inc y                    # move our index along
           cmp al, 0                # check for NULL
           brs !z _loop             # No? Go back for more.

Hasta ahora solo hemos hecho la conversión del texto de entrada a mayúsculas, pero puede usar la definición de una cadena literal para otra posibilidad. ¡Podemos hacer una verificación de sintaxis más!

Si al final del proceso averiguamos qué inStringsigue siendo verdadero ( bl = 0xFF), entonces podemos devolver un error, porque eso significa que hay un literal de cadena incompleto en algún lugar de la cadena.

Nota: Resulta que muchas versiones de BASIC son bastante indulgentes con la falta de comillas de cierre en las cadenas. Descubrí esto mientras creaba mi propio intérprete. Aunque lo sea, no me parece correcto, por lo que Retroputer BASIC no lo permite.

Tokenización

El siguiente paso en el análisis es transformar la cadena de entrada en algo más eficiente para que lo ejecute el intérprete de Retroputer BASIC. Estamos tratando de acercarnos lo más posible al concepto de árbol de sintaxis abstracta, pero el resultado aún no será un árbol. Pero será algo que podamos manejar rápidamente en tiempo de ejecución.

Una característica común de las primeras microcomputadoras era una memoria muy limitada. El Retroputer tiene más memoria que la mayoría de las máquinas estándar en ese momento, pero aún mucho menos que las computadoras modernas. Por lo tanto, los programas BASIC largos pueden fácilmente ocupar demasiada memoria si se guardan durante la entrada del usuario.

Para ahorrar espacio, las palabras clave se tokenizan durante la entrada del programa en la memoria... Este proceso convierte palabras clave en tokens de un solo byte. Las palabras clave siempre tienen al menos dos bytes de longitud, por lo que ahorra más a medida que escribe. También significa que podemos usar la tabla de búsqueda en tiempo de ejecución para llamar a las rutinas de lenguaje ensamblador apropiadas.

Sin embargo, Retroputer BASIC fue un poco más lejos que la mayoría de las versiones BASIC de la época. Además, convierte números a formato binario, marca cadenas, calcula referencias de variables y mucho más. Para ser honesto, esto está desperdiciando más espacio, pero los beneficios de la velocidad (y la facilidad de implementación) superan eso.

Así que aquí se utilizan los siguientes pasos:

, , . , , , , .
, , , . , PRINT "Hello, World" «Hello, World» , .

, .
, , , . JavaScript, !

( ). , PRINT !
Retroputer BASIC ( ). . , , .

Retroputer BASIC . , . , Retroputer BASIC.

En el post no entraré en detalles sobre la implementación de esta etapa en lenguaje ensamblador, lo dejo para el futuro. Pero no se preocupe, hay mucho código ahí .

Comprobando la sintaxis en tiempo de ejecución

Por último, pero no menos importante, la verificación de sintaxis en tiempo de ejecución es. Después de convertir el código a un formato tokenizado, es bastante fácil implementarlo.

Primero, en tiempo de ejecución, BASIC verifica si está procesando un token. Todos los tokens tienen habilitado el bit más significativo (es decir, tienen un valor de 128 y superior). Si se encuentra un token, podemos determinar a qué subrutina llamar encontrándolo en la tabla de vectores . También hace que sea trivial mostrar errores de sintaxis: algunas palabras clave no tienen sentido como operadores, por lo que la tabla de vectores simplemente apunta al procedimiento que genera el error de sintaxis.

Una vez que se llama al controlador de token de operador, el controlador asume todo el trabajo de análisis adicional. Para tokens y se puede utilizar la transición entre ellos gettok, gettok-raw,peektok etc. Si el token es algo que el procedimiento no espera, el procedimiento simplemente devuelve un código de error. Es en esta etapa que se detectan los errores de sintaxis y los errores de coincidencia de tipos.

Si el operador debe evaluar la expresión, se realiza otra etapa de análisis. Al analizar una expresión, se utiliza otra tabla de búsqueda de vectores , es decir, podemos interceptar palabras clave que no están relacionadas con una expresión matemática y devolver los errores correspondientes. Por ejemplo, si intenta ingresarPRINT 2+CLS, entonces obtenemos un error de sintaxis en CLS( CLS- esta es la abreviatura de "borrar pantalla").

Nota: a partir de esta tabla, también podemos determinar la prioridad de los operadores matemáticos y el número de parámetros requeridos. Esto es importante para la evaluación real de la expresión, pero también se puede utilizar para detectar casos en los que el usuario no ha proporcionado suficientes argumentos.

Dado que el token se asigna directamente a la entrada de la tabla de búsqueda de vectores, el programa se puede ejecutar con bastante rapidez y con un esfuerzo mínimo. La tarea de analizar cada tipo de operador se confía al propio manipulador y, en general, esto no causa ningún problema en particular. Probablemente los más difíciles de analizar son PRINTyINPUT, pero en cada paso se toma una ficha a la vez.

Dado que muchas de las comprobaciones no se realizan hasta el tiempo de ejecución del programa, esto significa que podemos tener resultados parciales antes de que ocurra el error. Por ejemplo:

PRINT "Hello";CLS
Hello
?Syntax Error

Además, esto significa que si el programa sale de la pantalla en un estado en el que no podemos ver el texto, entonces podemos tener problemas con la eliminación de errores. Si se muestra un error de sintaxis pero no lo vemos, ¿qué debemos hacer?

Esta forma de verificar la sintaxis ciertamente tiene sus inconvenientes, pero permite un intérprete bastante simple.

Tokenizar la entrada del usuario

Como se mencionó anteriormente, era común que las versiones BÁSICAS de esa época usaran tácticas de tokenización. Para ahorrar espacio y aumentar la velocidad de ejecución, las palabras clave se "comprimieron" en tokens de un solo byte (o de doble byte, si se necesitan más palabras clave).

Supongamos que tenemos una línea simple de código que limpia la pantalla e imprime un saludo estándar:

CLS: PRINT "Hello, World"

Si bien esto en sí mismo no ocupa mucha memoria, si escribe un programa largo, muchas palabras en ese programa serán palabras clave. Si los comprime (tokeniza), puede ahorrar una fracción sólida del espacio. Por ejemplo, después de la tokenización de la línea que se muestra arriba, habrá algo como esto en la memoria:

8A E3 B5 FC Hello, World 00 00

No debería ser demasiado difícil convertir esto de nuevo a la construcción original:

Byte	Palabra clave	Notas
8A	CLS
E3	":"	Fin de construcción
32	""	Almacenamos como máximo un espacio
B5	IMPRESIÓN
pensión completa	Línea en código	Luego viene la cadena literal
Hola mundo, 00		Las cadenas tienen terminación nula
00	Fin de línea de código	Las líneas de código también tienen terminación nula

Puede pensar que esto es mucho trabajo, pero el ahorro de espacio puede ser significativo. Esto no es particularmente notable en el ejemplo, pero incluso a partir de él, puede imaginar la rapidez con la que se puede acumular el espacio ahorrado. En este caso, el resultado comprimido es de 19 bytes. El texto fuente consta de 26 bytes (incluido el byte nulo de terminación).

El ahorro de espacio se vuelve importante cuando se trata de que el intérprete BASIC se ejecute en una máquina con muy poca RAM para los programas de usuario. Por lo tanto, dicha compresión es muy importante y atractiva, incluso si no tiene beneficios adicionales.

Entonces, ¿cómo tokenizamos algo como esto? Al principio, parece que JavaScript es bastante trivial para hacer esto. Con una matriz de cadenas, puede reemplazar rápidamente cada palabra clave con el token correspondiente. ¿Cierto?

¿Parece que esto es un trabajo para String#replace? Con un enfoque ingenuo, puede intentar algo como esto:

const tokens = ["CLS", "PRINT", ":" ];
function tokenize (inStr) {
    const newStr = inStr;
    tokens.forEach((token, idx) => newStr = newStr.replace(
        new RegExp(token, "g"), String.fromCharCode(128+idx)
    );
    return newStr;
}

Desafortunadamente, pronto nos damos cuenta de que no podemos sustituir cadenas literales con tokens. Esto significa que debes hacer el procesamiento carácter a carácter, teniendo en cuenta el contexto, para no comprimir elementos que no sean palabras clave.

Este nuevo algoritmo está más cerca del código en lenguaje ensamblador en Retroputer, pero JS aún hace las cosas mucho más fáciles. Aquí está el comienzo del código JS (lo ampliaremos gradualmente en esta publicación):

const tokens = ["CLS", "PRINT", ":" ];

function tokenize(inStr) {
    let out = [];                    // return value is "crunched" array
    let idx = 0;                     // index into inStr
    let ch = "";                     // current character
    while (idx < inStr.length) {
        ch = inStr.charCodeAt(idx);  // get the current character code
        
        // our logic is going to go here

        out.push(ch);                // for now push the character
        idx++;                       // and keep going (next char)
    }
    out.push(0);                     // we end with NUL
    return out;
}

Comenzamos con una lista muy simplificada de tokens, porque nadie quiere ver la tabla completa en este formato (¡ es larga y Retroputer crea tablas de tokens a partir de un archivo JS! ), Pero para nuestros propósitos esto será suficiente. El principio aquí es que cuando vemos un token, escribimos su índice en la matriz de salida.

En este punto, tenemos una función que, por ahora, simplemente convierte la cadena a sus códigos de caracteres equivalentes. Si bien no es particularmente útil, puede servir como un marco conveniente.

La versión en lenguaje ensamblador es bastante similar a la que se muestra arriba.

  do {
    call _get-source-index     # get next character index (in y)
    dl := <BP+source>,y        # read next char from our source string (ch)
    call _adv-source-index     # advance our source index
    call _get-target-index     # get position in target   ("out" in JS)
    <BP+target>,y := dl        # store to target          (out[y] = ch)
    call _adv-target-index     # move it along
    cmp dl, 0                  # was char 0? if so, break
  } while !z

No he incluido en el ejemplo anterior _get-source-indexu otras funciones, porque sus tareas están claras por el nombre: simplemente obtienen, establecen los índices de origen y destino, y también navegan por ellos. Vale la pena señalar que, a diferencia de JS, no hay matrices asignadas dinámicamente en lenguaje ensamblador, por lo que este algoritmo asigna un búfer de tamaño suficiente. A medida que avanzamos en la línea de entrada, necesitamos saber dónde escribir el siguiente token en el búfer de destino y qué está haciendo el índice de destino arriba. Cada una de las funciones anteriores devuelve un índice en formato Y. Por ejemplo, la función _adv-target-indexincrementa el índice de destino en uno (equivalente y++).

Tenga cuidado con los literales

Debemos tener cuidado: los literales de cadena pueden ser confusos para el tokenizador; no podemos simplemente reemplazar cada cadena de caracteres que coincida con una palabra clave con un valor de token. Si vemos un literal de cadena que tiene "CLS" en él, entonces no deberíamos buscar tokenizarlo. No debería ser ejecutable, y si lo mostramos ... entonces, en lugar de eso, mostramos el byte correspondiente al token. Lo más probable es que esto no sea lo que quiso decir el desarrollador.

Por otro lado, los literales numéricos no deberían tener este problema, porque BASIC no tiene palabras clave numéricas. Aun así, no tiene sentido buscar una palabra clave cuando se enfrenta a un número, ¿por qué perder el tiempo?

Tokenizar literales de cadena

Entonces, primero verifiquemos si la línea comienza; en JS no es particularmente difícil hacer esto:

if (ch === 34) {
  out.push (0xFB);             // string-in-code token
  idx++;
  ch = inStr.charCodeAt(idx);  // get next character after the quote
  while (ch !== 34 && idx < inStr.length) {
    out.push(ch);
    idx++;
    ch = inStr.charCodeAt(idx);
  };
  idx++;                       // go past the quote
  out.push(0);                 // end of string
  continue;
}

La comilla doble está representada por el código de carácter 34. Otros lenguajes de programación pueden reconocer muchos más estilos de comillas (como JS o C), pero con BASIC es simple: comillas dobles o nada.

Cuando vemos que comienza una cadena, simplemente podemos tomar los caracteres restantes y agregarlos a la matriz de salida hasta que encontremos otra cita.

Después de leer la cadena completa, se debe agregar un byte cero porque Retroputer BASIC usa cadenas de estilo C. Si quisiéramos usar cadenas de estilo Pascal, podríamos almacenar un contador e insertar la longitud del literal de cadena. En cualquier caso, esto no plantea ningún problema en particular. La única razón por la que he usado cadenas terminadas en nulo es porque es muy fácil trabajar con ellas en lenguaje ensamblador; solo necesitamos compararlas con un byte nulo, no almacenar un contador.

Entonces JavaScript no fue tan difícil. Creo que la mayoría de ustedes decidirá usar algo más abstracto, como una expresión regular. Creo que este código hará que nuestras intenciones sean más obvias.

if (ch === 34) {
  out.push (0xFB);             // string-in-code token
  const stringLiteral = inStr.substr(idx+1).match(/^[^"]*/)[0];
  idx += stringLiteral.length+1;
  out.push(...Array.from(stringLiteral, ch => ch.charCodeAt(0)));
  idx++;                       // go past the quote
  out.push(0);                 // end of string
  continue;
}

El código anterior es más o menos el mismo, pero en lugar de la validación carácter por carácter, dejamos que JS simplemente se ejecute match. Sabemos que obtendremos una coincidencia (estamos en una cadena), por lo que ni siquiera necesitamos verificar si la coincidencia fue exitosa. Luego incrementamos el índice por la longitud de la cadena y copiamos los caracteres en la matriz de salida. En mi opinión, este código es mucho más fácil de entender (sin embargo, implica una comprensión de las expresiones regulares, así como las peculiaridades de la sintaxis de ES6, por ejemplo, …y las funciones de flecha).

Por supuesto, en lenguaje ensamblador, tenemos que hacer manualmente todo el trabajo que hace JS. El resultado es muy similar a nuestro primer intento de escribir código JS:

  cmp dl, constants.QUOTE         # is dl a quote?
  brs !Z not-a-string             # nope; not a string

  call _get-target-index          # get next position in crunch target
  dl := brodata.TOK_CODE_STRING   # "String" token
  <bp+target>,y := dl             # Store it into the crunch target
  call _adv-target-index

still-a-string:
  call _get-source-index
  dl := <bp+source>,y             # get string character
  call _adv-source-index
  cmp dl, constants.QUOTE         # if it's a quote, we can zero it
  if Z { 
    dl := 0 
  }
  call _get-target-index
  <bp+target>,y := dl             # write to target
  call _adv-target-index
  cmp dl, 0                       # are we done?
  brs !Z still-a-string           # no, keep going
  continue                        # next!
not-a-string:

Vale la pena agregar una nota sobre el analizador de lenguaje ensamblador de Retroputer: tiene soporte básico para construcciones de alto nivel como bloques y bucles. Por lo tanto, if Z {…}ejecutará el contenido dentro del bloque cuando se establezca la bandera de cero, y continuese puede usar para volver al comienzo del bloque ( breaktambién se usa para salir del bloque). El ensamblador traduce esto en varias instrucciones de comparación y bifurcación, por lo que la CPU no ve las partes de alto nivel del código, pero hace que el código sea un poco más fácil de escribir.

Tokenizando números

Además, no tiene sentido intentar buscar números en la lista de palabras clave, por lo que podemos simplemente omitirlos. La mayoría de las versiones de BASIC hacen algo similar a la manipulación de cadenas que se muestra arriba: si el carácter leído es un dígito, se concatenará a la salida, después de lo cual el compresor se hará cargo.

Retroputer BASIC (y algunas otras versiones de BASIC, como Atari BASIC) va un paso más allá: convierte un número al formato binario apropiado. Es muy fácil hacer esto: si encontramos un dígito, entonces multiplicamos el acumulador por 10 y sumamos el dígito, continuando así mientras los dígitos continúen apareciendo. (Sin embargo, vale la pena señalar que, si bien Retroputer BASIC solo funciona con valores enteros, agregar números de punto flotante ya está en mi lista de tareas pendientes).

(Debo decir que actualmente Retroputer BASIC no hace nada cuando se produce un desbordamiento de enteros, ya sea con o sin signo. Cuando agrego números de coma flotante, Retroputer también se convierte en coma flotante).

Retroputer BASIC va un paso más allá. : también reconoce números hexadecimales y los convierte a su equivalente binario. Se utiliza como designación para tales números 0x(como en JS), y el lenguaje en sí tiene una lógica adicional para garantizar que se devuelva un error si se especifican varios caracteres x.

En lenguaje ensamblador, verificar si un carácter es un dígito no es tan difícil, pero requiere un par de comparaciones: debe asegurarse de que el código del carácter esté entre 0x30y0x39... (Estos son los códigos de carácter "0" y "9".)

Habiendo recibido un dígito de carácter, podemos usar otra propiedad conveniente del juego de caracteres. 0x30- este es el código de carácter "0", 0x31- el código "1", y así sucesivamente. Podríamos restar si quisiéramos 0x30, pero hay una forma más sencilla: simplemente descarte los cuatro bits más significativos:

and dl, 0b0000_1111

Desafortunadamente, esto no funcionará si necesitamos manejar números hexadecimales. En este caso, puede restar y luego comparar con 10, y luego disminuir en 7 nuevamente si el código es mayor que 10 (dado que los números hexadecimales son "A" - "Z" en mayúsculas).

En JS, puedes usar expresiones regulares nuevamente, y luego cuando obtengamos una coincidencia del número, podemos llamarlo Number(), lo que nos da otra ventaja: los números hexadecimales también se convierten de manera trivial, porque lo Number()hace automáticamente si el número comienza con 0x.

¿Cómo se ve en JavaScript?

if (ch >= 48 && ch <= 57) {
  out.push (0xFD);           // number token
  const numberLiteralStr = inStr.substr(idx).match(/^[\d|A-F|a-f|x|X]+/)[0];
  idx += numberLiteralStr.length;
  const numberLiteral = Number(numberLiteralStr);
  const bytes = new Uint8Array(new Uint16Array([numberLiteral]).buffer);
  out.push(...bytes)
  continue;
}

La expresión regular le permite utilizar cualquier combinación de números o dígitos hexadecimales (más xpara cambiar al modo hexadecimal). La expresión no es la ideal, por ejemplo, te permite usar varias x, pero por ahora esto es suficiente.

En el código anterior, la conversión de números a bytes puede ser cuestionable. Number()Hizo todo el trabajo duro de convertir una cadena de números en un número con el que JavaScript puede trabajar, pero ahora necesitamos representarlo como una secuencia de bytes. Puedes usar matemáticas para hacer esto:

const hiByte = (numberLiteral & 0xFF00) >> 8;
const loByte = (numberLiteral & 0x00FF);

... y es fácil de hacer con un número entero. Pero gracias al uso de matrices JS escritas, no puede hacer todos estos cálculos, pero al mismo tiempo prepararse para manejar números de punto flotante en el futuro (solo reemplazaremos Uint16Arraycon Float64Array).

El código en lenguaje ensamblador para esta tarea es un poco más largo , pero hace un poco más. Retroputer usa una optimización más: si el número es pequeño, entonces se guarda en un formato más pequeño. Esto significa que 0-255 se pueden almacenar en un byte, mientras que los números más largos ocupan dos.

Buscar palabras clave

Así que hemos trabajado bastante, pero hasta ahora no hemos comprimido una sola palabra clave. Habiendo tratado con números y cadenas literales, podemos estar seguros de que todo lo demás es una palabra clave o un nombre de variable. (O un espacio, pero esto es fácil de verificar).

En BASIC, las palabras clave no siempre comienzan con un carácter alfabético, los operadores y delimitadores también se consideran tokens. Pero las variables también comienzan con un carácter alfabético. Por lo tanto, no podemos determinar de inmediato si comprimiremos una palabra clave o una variable. Esto nos conviene: si no encontramos una coincidencia en la lista de tokens, asumiremos que se trata de una variable.

Entonces, ¿cómo verificamos que una palabra clave potencial sea realmente una palabra clave? Si estuviéramos escribiendo en JavaScript, podríamos usar el Array#findIndex.

const tokenMatch = tokens.findIndex(token => 
  inStr.substr(idx).startsWith(token));
if (tokenMatch > -1) {
  out.push(tokenMatch + 128);
  idx += tokens[tokenMatch].length;
  continue;
}

El método Array#findIndexitera sobre la matriz tokensy podemos verificar si comienza inStr(por el actual idx) con el token que estamos verificando. Trabajando con nuestra lista simplificada de tokens, haremos algo como (asumiremos que inStr.substr(idx)===”PRINT”):

simbólico	.startsWith (token)?	Índice
CLS	falso	0
IMPRESIÓN	cierto	1

Nota: al igual que indexOfcon JS, si no se encuentra nada, obtenemos -1.

Si se encuentra una coincidencia, puede almacenar su índice en la matriz devuelta. Pero, ¿cómo distinguimos más tarde una ficha de un símbolo? Fácil: activa el bit más significativo, lo que se puede hacer agregando 128 al valor del token.

(Nota: si necesitamos más tokens que 128, entonces para algunos tokens tendríamos que usar dos bytes. Esto complica un poco las cosas, pero no tanto. Algunas versiones de BASIC hacen esto, por ejemplo, varios BASIC de Microsoft.

Hemos terminado de trabajar en JavaScript, pero ¿cómo lo hacemos en lenguaje ensamblador?

Resulta ser casi lo mismo, pero el código será mucho más largo.

search-keywords:
  bl := [d, x]                 # get first character of current token
  cmp bl, constants.NUL        # if it's NUL, we've exhausted the list
  brs Z exit-keyword-search    # so we're clearly not a keyword
  clr Z                        # compare strings, but with partial equality
  call [vectors.STRCMP]        # so that our source doesn't need NUL between
                               # tokens; c will now be how many chars got 
                               # compared
  if !Z {
    do {                       # no match; advance past our token in the list
      inc x                    # character by character
      bl := [d, x]             # tokens are terminated with NULs
      cmp bl, constants.NUL    # so if we see it, we can stop
    } while !z
    inc x                      # go past the token #
    inc x                      # in the lookup table
    brs search-keywords        # and keep looking for a match
  }
  clr c                        # found the match!
  add x, c                     # c is the length of the match
  inc x                        # past the NUL
  bl := [d, x]                 # bl is now the token #
  call _get-target-index
  <bp+target>,y := bl          # write the token #
  call _adv-target-index
  call _get-source-index       # advance past the token in the source
  clr c
  add y, c                     # by adding the character count
  dec y                        # back off by one (we'll advance again later)
  call _set-source-index
  continue

Bueno, no se ve tan mal. El algoritmo es casi el mismo, solo que la tabla de tokens del lenguaje ensamblador está estructurada de manera ligeramente diferente. Se parece a esto:

CLS   00 80
PRINT 00 81
:     00 82

Cada palabra clave termina con un byte nulo seguido de un número de token.

Sin embargo, nos falta algo importante aquí: ¿cómo se hace esta comparación de cadenas? Existe un procedimiento en el núcleo de Retroputer STRCMPque podemos usar, pero ¿cómo se ve?

strcmp: {
  enter 0x00
  push a
  push b
  push d
  push y
  pushf
  if Z {
    bl := 0x00                  # Checking for full equality
  } else {
    bl := 0x01                  # only checking for partial equality
  }
_main:
  y := 0                        # start of string
top:
  cl := [d, x, y]               # character in string A
  al := <bp+4>,y                # character in string B
  cmp bl, 0x01                  # check if we're doing full equality
  if Z {
    cmp cl, 0                   # we're not, so check for an early nul
                                # in string b
    brs Z strings-are-equal     # if it's NUL, we calling them equal
  }
  cmp cl, al                    # check character
  if Z {
    cmp cl, 0                   # equal, but check for NUL
    brs Z strings-are-equal     # NUL reached, strings are equal
    inc y                       # next character
    brs top                     # not NUL, so keep going...
  }
 # if here, the strings aren't equal
  if N {
    popf                        # string is less than
    set N
    clr Z
    brs _out
  } else {
    popf                        # string is greater than
    clr N
    clr Z
    brs _out
  }
strings-are-equal:
  popf
  clr N                         # Not less than
  set Z                         # but Equal
_out:
  c := y                        # make sure we know how many chars
                                # were compared
  pop y
  pop d
  pop b
  pop a
  exit 0x00
  ret
}

No sé ustedes, pero estoy empezando a amar el método String#startsWithde JS cada vez más . Sí, hace lo mismo, ¡pero no tenemos que escribir toda la lógica interna!

Manejo variable

La compresión de teclas ahora está completa, por lo que podemos terminar. Pero Retroputer BASIC da otro paso adelante: tokenizar variables. Me parece que solo unas pocas versiones de BASIC de los años 80 y 90 hicieron esto, porque en condiciones de memoria limitada puede ser perjudicial. Pero si hay mucha memoria, la tokenización de variables ayuda a mejorar el rendimiento.

Esto es lo que hace Retroputer BASIC:

Lee hasta los dos primeros caracteres del nombre de la variable. (Este fue un inconveniente estándar de las versiones BASIC de la época debido a limitaciones de memoria).
A partir de estos dos caracteres, determina el índice de la variable. "A" es la variable 0, "A0" es la variable 53, y así sucesivamente. La ecuación es bastante simple, pero no nos interesa en este momento.
BASIC . , $ BASIC . .
BASIC , . !

(Nota: cuando Retroputer BASIC aprende a asignar memoria de forma dinámica para las variables, reemplazaremos el índice con un puntero a una variable. ¡Otro elemento en la lista de tareas pendientes!)

Esto hace que la búsqueda de variables sea increíblemente rápida en tiempo de ejecución: no tenemos que analizar el nombre de la variable y calcular el índice cada vez cuando nos encontramos con una variable. En ciclos continuos, los ahorros pueden ser sustanciales. Pero esto tiene un alto costo: necesitamos almacenar el puntero y el nombre de la variable juntos, por lo que para cada variable que encontremos, debemos agregar cuatro bytes adicionales a la salida.

Depende de usted decidir si vale la pena.

Sea como fuere, en JavaScript también es fácil determinar si el resto del flujo de caracteres es una variable:

const variableMatch = inStr.substr(idx).match(/^[A-Z]+[A-Z0-9]*[\$]*/);
if (variableMatch) {
  const variableName = variableMatch[0];
  idx += variableName.length;
  // tokenize it (omitted; nothing new here)
  continue;
}

No describiré en detalle el código que Retroputer usa actualmente para tokenizar variables, es demasiado detallado. Volveremos a ello cuando agregue la asignación de memoria dinámica para las variables.

Tokenización completada

Si ahora probamos nuestro código en JS, obtenemos una matriz de bytes similar a la que Retroputer BASIC usa internamente:

console.log(toHex(tokenize(`CLS: PRINT "Hello, World"`)));
// 80 82 20 81 20 FB 48 65 6C 6C 6F 2C 20 57 6F 72 6C 64 00 00

Vaya, cuánto trabajo para ahorrar unos pocos bytes. Pero cuando solo hay un par de kilobytes de memoria libre, ¡vale la pena! Pero esta no es la única ventaja de comprimir el texto ingresado por el usuario, también aceleramos la ejecución del programa.

Para explicar por qué sucede esto, debemos comprender cómo Retroputer ejecuta el código. No entraré en detalles por ahora, pero en pocas palabras, se requiere lo siguiente para ejecutar el código:

Obtener un byte de la memoria
Si un byte tiene activado el bit más significativo, entonces es un token, de lo contrario es un error de sintaxis (o NUL; en cualquier caso, aquí es donde terminamos con la línea del programa)
Estamos buscando un controlador de token en una matriz; esta matriz contiene punteros a las funciones que procesan el token.
Llamamos al manejador (es responsable de recibir argumentos y similares)
Repetimos todo de nuevo

Esta es otra razón para convertir las palabras clave en token: ejecutar la lógica de la palabra clave se vuelve trivial, simplemente busque la dirección en la matriz y llámela.

Me gustaría enfatizar que si bien la tokenización es importante para ahorrar espacio, también mejora la velocidad de ejecución.

Por ejemplo, un bucle de ejecución JS podría verse así:

const handlers = [ cls, print, endOfStmt ];
bytes.forEach(byte => handlers[byte] && handlers[byte]());

Por supuesto, en realidad no todo es tan simple, es mucho más, ¡pero esto ya es tema para otro post!

Escribir un intérprete BASIC al estilo de los 80

Características de la retrocomputadora