Intentemos escribir en Lisp ... un traductor de un lenguaje imperativo simple. No, no, no me equivoqué: es el traductor. Se transmitirá en el código Lisp. Y luego este código puede ser ejecutado por el sistema Lisp.
Aquí, el servicio inestimable será proporcionado por el hecho de que en Lisp no existe una barrera entre el código y los datos (esta es una propiedad rara de algunos lenguajes de programación llamados "homo-identidad"). Pero las capacidades visuales de Lisp también jugarán un papel importante.
Como implementación, usaré HomeLisp . Los interesados pueden adaptar este proyecto a Common Lisp. Diré de inmediato: en relación con el problema en consideración, la diferencia significativa entre Common Lisp y HomeLisp es solo en el procesamiento de líneas y archivos.
Descargue una versión portátil de HomeLisp aquí . La documentación también se encuentra en el mismo sitio. Aquellos que lo deseen pueden copiar el código del artículo y verificar de inmediato el rendimiento.
El tema que llamó su atención sirvió de base para mi taller en el famoso Novosibirsk LSHUP-2018 . Los resultados del taller se pueden encontrar aquí . Y luego establecí mi enfoque. Supongo que el lector está familiarizado con el lenguaje Lisp.
Bajando
Comencemos con el "lenguaje imperativo simple" que transmitiremos en Lisp.
El idioma solo procesará datos numéricos. El código en este lenguaje consta de funciones (procedimientos que devuelven valores). Entre estas funciones, una debería llamarse main. Es con esta función que comienza la ejecución del código. Aunque ¿por qué atarte así? Escribimos funciones en un lenguaje imperativo, se transmiten en Lisp y se pueden usar junto con las funciones de Lisp. Pero no nos adelantemos ...
El conjunto de operadores de lenguaje es habitual: asignación, ramificación, ciclo aritmético, salida anticipada del ciclo, entrada, salida y llamada a funciones. Sin embargo, sintácticamente, una llamada de función se ejecuta como una asignación (resultado de una llamada). Deje que los comentarios contengan un asterisco en la primera posición de la línea. El lenguaje, por supuesto, debería proporcionar la capacidad de crear funciones recursivas. Para hacerlo más claro, daré ejemplos de código: imprimir números impares sucesivos y calcular su suma:
proc main() local s,n,k input n for i=1 to n k=2*i-1 print k s=s+k end_for print s end_proc
En su espíritu, es un lenguaje básico. Lo llamaré "mini-básico". Nuestro traductor debe convertir el código dado a la siguiente función Lisp:
(defun main nil (let ((s 0) (n 0) (k 0)) (setq n (read)) (iter (for i from 1 to n) (setq k (- (* 2 i) 1)) (printline k) (setq s (+ sk))) (printline s)))
Realmente me gusta el paquete iterate , que se implementa como una macro en los paquetes profesionales Common Lisp. En HomeLisp, la función iter (que implementa una gran parte de las capacidades de iteración macro) se incluye en el lenguaje principal. Fue mi adicción a iter lo que hizo que los ciclos de nuestro "mini-básico" se tradujeran en llamadas de iter.
¿Dónde comenzar la implementación? Comencemos seleccionando el archivo a transmitir y leyendo e imprimiendo ese archivo línea por línea. Tendremos que iniciar el traductor muchas veces, por lo que es conveniente que comience desde el principio. Así es como podría verse esta función:
(defun start (&optional (fname nil)) (setq *numline* 0) (setq *flagerr* nil) (when (null fname) (setq fname (sysGetOpenName (sysHome) "-|*.mbs"))) (let ((fi (gensym 'fi))) (when fname (filOpen fi fname _INPUT) (loop (getLine fi) (when (or *flagerr* (filEOF fi)) (return t))) (filClose fi) (when *flagerr* (printsline "**** ")))) (unset '*numline*) (unset '*flagerr*))
La función tiene un parámetro opcional fname : el nombre del archivo cuyos contenidos se transmitirán. Al ingresar a la función, se crean dos variables globales: numLine, número de línea del archivo fuente y flagerr , el indicador de estado de error. Antes de que la función finalice, estas variables se destruyen (la función HomeLisp no establecida destruye las variables globales).
Si se omite el nombre del archivo de entrada, se llama al cuadro de diálogo estándar de Windows para seleccionar el archivo (sysGetOpenName) . El directorio actual (sysHome) se utiliza como directorio de inicio. A continuación, se crea un carácter único para el manipulador de archivos y el archivo se abre para la lectura de texto. Luego, en un bucle sin fin, el archivo se lee línea por línea (función getLine ). Después de cada operación, se verifica si se ha producido un error y si se alcanza el final del archivo. Si se produce un error o se corrige el final del archivo, el ciclo se rompe, el archivo se cierra y, si hubo errores, se muestra un mensaje final.
En realidad, la función getLine realiza la lectura del archivo:
(defun getLine (fil) (let ((stri "")) (loop (when (filEof fil) (return "")) (setq *numline* (add1 *numline*)) (setq stri (filGetline fil)) (printsline (strCat (format *numline* "0000") " " (strRTrim stri))) (setq stri (strATrim stri)) (unless (or (eq "" stri) (eq "*" (strLeft stri 1))) (return stri)))))
Esta función acepta el identificador de un archivo abierto y, en un bucle infinito, realiza las siguientes acciones:
- comprueba el final del estado del archivo. En este caso, el bucle se rompe y la función devuelve una cadena vacía;
- el contador de líneas leídas aumenta en uno;
- se lee la siguiente línea del archivo;
- la línea de lectura se imprime con la eliminación de posibles espacios a la derecha;
- si la línea de lectura no está vacía y no contiene un asterisco en la primera posición, entonces
vuelve de la función;
Por lo tanto, todas las líneas del archivo en su forma original caen en la lista de salida.
Entramos en procedimientos
Ahora enseñemos nuestro código para dividir la secuencia de entrada en procedimientos separados. Primero, la cadena ingresada deberá dividirse en tokens (unidades léxicas de entrada indivisibles). Este proceso se llama análisis; Tenemos que crear un analizador. Escribir analizadores es un tema clásico, hay bibliotecas de analizadores listos para usar y herramientas especiales que le permiten generar el analizador necesario ... Seguiremos nuestro propio camino.
Antes de describir el algoritmo analizador, prestamos atención al hecho de que todos los caracteres de la cadena de entrada se pueden dividir en dos clases:
- Caracteres ordinarios;
- Separador de caracteres.
Entonces, en el operador de asignación "x = 15 + y ^ 2", los caracteres x, 1,5, y y 2 son caracteres ordinarios, y los caracteres "espacio" , + , ^ son delimitadores. ¿Cómo es un personaje normal diferente de un separador? Separador: siempre separa un token de otro. Nuestro operador de asignación, dividido en tokens, se ve así: “x”, “=”, ”15”, “y”, “^”, “2” .
Como puede ver, no todos los delimitadores caen en el resultado del análisis (los espacios, en particular, no caen). Llamaremos a los separadores que no entran en el resultado como separadores del primer tipo. Otros separadores se llamarán separadores del segundo tipo.
La entrada del analizador será una cadena, la salida es una lista de tokens de cadena. Como unidad, se utilizará una variable local: la batería. La batería inicialmente contiene una cadena vacía.
El algoritmo de análisis puede ser el siguiente: leemos la línea de entrada carácter por carácter. Si conoces un personaje normal, concatena con la batería. Si se encuentra un delimitador, entonces:
- Para el separador del primer tipo, restablecemos el valor de la batería (si no está vacío) a la lista de salida, borramos la batería y procedemos a leer el siguiente carácter;
- Para el separador del segundo tipo, también volcamos el valor de una batería no vacía en la lista de salida, y luego ingresamos el separador aceptado del segundo tipo (como un token independiente) en la lista de salida, borramos la batería y procedemos a leer el siguiente carácter.
Aquí está el código del analizador:
(defun parser (txt &optional (d1 " ,") (d2 "()+-*/\^=<>%")) (let ((res nil) (lex "") ) (iter (for s in-string (strCat txt (strLeft d1 1))) (cond ((plusp (strInd d1 s)) (when (> (strLen lex) 0) (collecting lex into res)) (setq lex "")) ((plusp (strInd d2 s)) (when (> (strLen lex) 0) (collecting lex into res)) (collecting s into res) (setq lex "")) (t (setq lex (strCat lex s))))) res))
Además del parámetro requerido, la función tiene dos parámetros opcionales: d1 contiene una cadena, cada uno de los cuales tiene un separador del primer tipo, y la línea d2 contiene separadores del segundo tipo.
La lógica del programa de la función del analizador se describió anteriormente. Solo debe tenerse en cuenta que antes de comenzar a trabajar, se agrega un separador al final de la línea de entrada. Esto se hace para que el último token procesado "cuelgue" en la batería (la variable local lex juega el papel de la batería).
Vamos a ver nuestro analizador "en acción":
(parser "x = 15 + y^2") ==> ("x" "=" "15" "+" "y" "^" "2")
Así es, ¿no es así? Pero trabajar con listas de cadenas no es del todo Lisp. Pasemos de la lista de cadenas a la lista de átomos. Para hacer esto, necesitamos una función que ... pegue todos los tokens nuevamente en una línea larga (pero inserte un espacio entre los tokens), luego pegue el corchete de apertura al comienzo de esta línea, cierre el corchete de cierre hasta el final ... y luego fuerce a Lisp a leer la lista:
(defun mk-intf (txt) (let ((lex (parser txt " ," "()+-*/\^=<>%")) (intf "")) (iter (for a in lex) (setq intf (strCat intf a " "))) (input (strCat "(" intf ")"))))
Ahora, si enviamos el operador de asignación a la entrada de la función mk-intf, obtenemos:
(mk-intf "x = 15 + y^2") ==> (X = 15 + Y ^ 2)
Lo cual, ves, es mucho mejor.
Ahora cambiemos un poco la función de inicio: esta función tendrá que leer y procesar procedimientos completos:
(defun start (&optional (fname nil)) (setq *numline* 0) (setq *flagerr* nil) (when (null fname) (setq fname (sysGetOpenName (sysHome) "-|*.mbs"))) (when fname (let ((fi (gensym 'fi))) (filOpen fi fname _INPUT) (loop (let ((curr-proc (action-proc fi))) (when (or *flagerr* (filEOF fi)) (return t)) (eval curr-proc))) (filClose fi)) (when *flagerr* (printsline "**** "))) (unset '*numline*) (unset '*flagerr*))
En el cuerpo del bucle, se llama a la función action-proc (para procesar el procedimiento), que formará el cuerpo del procedimiento aceptado ya en Lisp. El cuerpo del procedimiento, almacenado como una expresión S en la variable curr-proc , se pasa a la entrada de eval . ¡Y la función aceptada se "reencarna" en el entorno Lisp!
¿Qué debe hacer action-proc ? Esta función recibe el identificador del archivo abierto como parámetro. La función lee el archivo línea por línea del archivo, omite líneas vacías y comentarios, analiza el resto de las líneas, lo traduce a un formulario de lista y genera el cuerpo del procedimiento.
Gradualmente "aprenderemos" la generación de acción-proc . Y comencemos enseñando nuestra función para reconocer el principio y el final de un procedimiento. En un mini-básico, el comienzo del procedimiento es:
proc name(p1,p2,p3)
intenta analizar una línea como esta:
(mk-intf "proc name(p1,p2,p3)") ==> (PROC NAME (P1 P2 P3))
¿Cómo debería responder la función action-proc a esta entrada? Naturalmente, asegurándose de que el encabezado de la lista sea un átomo PROC , debe tomar el segundo elemento de la lista como el nombre de la función y el tercer elemento como la lista de parámetros. El nombre y la lista de parámetros deben almacenarse en variables locales. Cuando se lee el operador end_proc , debe formar un formulario defun con un cuerpo vacío (hasta ahora) del nombre de la función y la lista de parámetros, y devolver este formulario como resultado. Así es como se ve:
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil)) (loop (setq stmt (mk-intf (getLine fi))) (when (null stmt) (return t)) (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt))) ((eq (car stmt) 'end_proc) (return t)) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) `(defun ,proc-name ,proc-parm (quote OK))))
Para la formación final de la cláusula defun , se utiliza un bloqueo inverso. Tenga en cuenta que el procedimiento generado devolverá un átomo OK como resultado.
Ahora podemos verificar nuestro código en acción. Ponga el siguiente código en el archivo 0000.mbs:
proc f1(x,y) end_proc proc f2(x) end_proc
Ejecute el procedimiento de inicio , seleccione 0000.mbs y vea en la consola:
0001 proc f1(x,y) 0002 end_proc 0003 proc f2(x) 0004 end_proc
Si lo desea, puede asegurarse de que la máquina Lisp ahora tenga dos funciones (hasta ahora inútiles) f1 y f2 :
(getd 'f1) ==> (EXPR (XY) (QUOTE OK)) (getd 'f2) ==> (EXPR (X) (QUOTE OK))
Por otra parte! Ya se pueden iniciar:
(f1 1 2) ==> OK (f2 2) ==> OK
Nuestro traductor respiró por primera vez ...
Entrada, salida y variables locales.
Ahora es el momento de enseñarle a nuestro traductor recién nacido cómo manejar la entrada , la impresión y los operadores locales .
La forma más fácil de manejar la entrada y la impresión. Ambos operadores tienen la misma estructura de sintaxis: palabra clave y variable. La entrada del operador x debe convertirse en una forma de Lisp (setq x (lectura)) . En consecuencia, el operador de impresión x se convierte en un formulario (línea de impresión x) . Para almacenar estos formularios, debe proporcionar el cuerpo de la variable local en la función action-proc . Esta variable acumulará formas que realizan cálculos de la función futura. Entonces todo es bastante simple:
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil) (loc-var nil) (body nil)) (loop (setq stmt (mk-intf (getLine fi))) (when (null stmt) (return t)) (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt))) ((eq (car stmt) 'end_proc) (return t)) ((eq (car stmt) 'print) (setq body (append body (list (cons 'printline (cdr stmt)))))) ((eq (car stmt) 'input) (setq body (append body (list (list 'setq (cadr stmt) (list 'read) ))))) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) `(defun ,proc-name ,proc-parm ,@body)))
Ahora preparemos este código fuente en un mini-básico:
proc f1(x,y) print x print y end_proc proc f2(x) input x print x end_proc
e intente traducirlo ... Tendremos dos funciones Lisp f1 y f2 . Veamos sus expresiones definitorias y asegurémonos de que se generen correctamente:
(getd 'f1) ==> (EXPR (XY) (PRINTLINE X) (PRINTLINE Y)) (getd 'f2) ==> (EXPR (X) (SETQ X (READ)) (PRINTLINE X))
Puede llamar a estas funciones y asegurarse de que funcionan exactamente como se esperaba. No deje que le moleste que ingresemos el valor en la variable del parámetro, simplemente todavía no tenemos variables locales ... Vamos a agregarlas.
El operador local puede estar en cualquier parte del procedimiento y ocurrir más de una vez. Si se encuentra el operador local durante el procesamiento de un procedimiento, debe tomar una lista de variables y guardarla en una variable local. Una vez que se cumple la instrucción end_proc, debe generar el formulario let y "encerrar" todas las instrucciones ejecutables (por ahora, solo ingresar e imprimir ). Así es como se verá action-proc :
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil) (loc-var nil) (lv nil) (body nil)) (loop (setq stmt (mk-intf (getLine fi))) (when (null stmt) (return t)) (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt))) ((eq (car stmt) 'end_proc) (return t)) ((eq (car stmt) 'print) (setq body (append body (list (cons 'printline (cdr stmt)))))) ((eq (car stmt) 'input) (setq body (append body (list (list 'setq (cadr stmt) (list 'read) ))))) ((eq (car stmt) 'local) (setq loc-var (append loc-var (cdr stmt)))) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) (iter (for a in (setof loc-var)) (collecting (list a 0) into lv)) `(defun ,proc-name ,proc-parm (let ,lv ,@body))))
La lista de variables locales se acumula en la variable loc-var . Una vez que se completa el procesamiento del procedimiento, se crea una lista de pares del formulario (nombre 0) a partir de esta lista. Al mismo tiempo, la duplicación de nombres idénticos no es deseable ... ¿Cómo prevenirlo? Por supuesto, es posible verificar en cada procesamiento del operador local si hay nombres duplicados (si los hay, dar un mensaje de error). Pero, me parece, es mejor eliminar las repeticiones, que es lo que hace la llamada setof . Ahora traduzcamos y ejecutemos este programa:
proc f1(x,y) local a,b,c print x print y input a print a end_proc
Nos aseguramos de que funcione exactamente como sugiere el algoritmo. ¡Pero lo más interesante está por delante!
Desde aquí puedes descargar la versión final de lo que estamos haciendo w codificado ...
¡Continuará!