Intérprete de lenguaje Lisp-like

Un lenguaje de la familia Lisp se basa en dos funciones principales: eval y apply. eval toma como argumento una lista de la forma (f x y z) donde f es una función matemáticamente pura, es decir, sin efectos no explícitos, x y z son los argumentos que se le van a pasar a f y los paréntesis delimitan la lista. Por otro lado, apply toma una función y una lista y evalúa la función con todos los elementos de la lista como argumentos. Es decir, (apply f '(1 2 3)) se evalúa a (f 1 2 3). Estas dos funciones permiten modelar la computación de una forma tan elegante que le han ganado a "Lisp" (la nube confusa de lenguajes que comparten unas cuantas características como: las expresiones S, eval y apply como corazón del lenguaje, código como información, etcétera.) una vida de 68 años (contando desde la publicación de «Funciones recursivas de expresiones simbólicas y su cómputo a máquina, Parte I» por John McCarthy en 1958), que no tiene apariencia de acabar pronto. Este pequeño proyecto mío implementa lo más básico para un lenguaje de esta familia: eval, apply y un REPL. El propósito de este artículo es explicar cada una de sus partes.

El proyecto entero está escrito en Guile scheme y licenciado bajo la GPL 3.0. El código fuente se puede encontrar aquí: repo en codeberg.

Mi implementación de eval toma dos argumentos: expr y env, la expresión a evaluar y el ambiente en el que se evalúa.

(define (call expr env) (let ((head (eval (car expr) env)))

Aquí env es una association list, una lista de asociaciones, tiene la forma ((x . 10) (y . 20) (mensaje . "hola")), en esta estructura ((name . val) (name1 . val1)) codifica los nombres de todas las variables definidas junto con su valor. En el ejemplo anterior, diríamos que x = 10, y = 20 y mensaje = "hola". La función continúa:

(if (not (pair? expr))
      (if (symbol? expr)
          (let ((sym (assoc expr env)))
            (if sym
                (cdr sym)
                (throw 'error "symbol no found")))
          expr)
      () ;; Lo mostraré más adelante, esto es la rama en la que entran las funciones/formas especiales

Preguntamos: ¿Es expr un no par?, que es lo mismo que decir ¿Es expr atómico?, en el caso de que el ordenador nos responda: «Sí.», nosotros le respondemos: «¿Es expr un símbolo?», Si la computadora nos responde «No.», nosotros le mandamos: «Al que te pidió evaluar expr, sé recíproco para con él, y regrésale expr como te lo dio.», pues con una expresión de estas propiedades no se puede hacer mucho más. Si se da que expr es un símbolo, ordenamos al ordenador «Busca en env este símbolo», y como la función assoc regresa #f si el primer argumento no existe dentro del segundo, guardamos el valor para el siguiente if. Aquí entra en juego una parte peculiar de Guile: solamente #f se considera falso, puede parecer obvio, claro, pero esto significa que cualquier resultado excepto un #f literal es truthy, es decir que con este como if-expression if ejecutará la then-expression, en nuestro caso, (cdr sym), y como assoc regresó un par de forma (nombre . valor) esto se evaluará a valor. En el caso que assoc regrese #f, es decir, expr no existe en env, causamos una excepción con el mensaje "symbol not found", que se traduce como: símbolo no encontrado.

(define (call expr env))

Como eval, call toma expr y env.

(if (procedure? head)
    ;; built-in/primitive
    (apply head (map (lambda (x) (eval x env)) (cdr expr)))

Primero, evaluamos (car expr) en el env que recibimos como argumento y le asignamos el nombre head. Si este head evaluado es un procedimiento (una función), simplemente usamos el apply de nuestro lenguaje host, Guile. Como dice el comentario esto solo debería usarse para built-ins del intérprete (*, /, +, -).

(if (and (pair? head)
         (eq? (car head) 'closure))
    (let* ((parameters (cadr head))
           (body (caddr head))
           (arguments (cdr expr)))
        (if (= (length parameters) (length arguments))
          (let* ((eval-args (map (lambda (x) (eval x env))
                                 arguments))
                 (inside-env (append (map cons parameters eval-args)
                                  env)))
            (eval body inside-env))
          (throw 'error "num of args and params do not match")))
    (throw 'error "not valid"))

Llegamos a la else-expr, primero que todo nos aseguramos de que head sea un par, para después poder llamar (car head) y saber si tratamos con un closure. Si head es un closure, entramos al bloque let* y extraemos parameters (los parámetros que toma la función), body (el cuerpo de la función) y arguments (los argumentos que le pasamos a la función).

Si parameters y arguments tienen el mismo tamaño entramos en el bloque let*, si no levantamos una excepción "num of args and params do not match", el número de argumentos y parámetros no son iguales. En el bloque let*, creamos eval-args, que es, como dice el nombre, todos los argumentos que tomamos evaluados. Construimos inside-env anexando el mapeo de cons entre parameters y eval-args, que regresa una association list, lista de asociaciones, con cada parámetro emparejado a un argumento.

Después de todo, simplemente evaluamos body dentro de inside-env.

Para hacer algo, tenemos que comunicarnos con el usuario.