An interpreter for a tiny lexically-scoped language with (global) functions

gistfile1.cl

#||
Let's see if an example works better to explain how lexical scoping works

A naive way to implement lexical scoping threads an environment across
all the operations.  It could, for example, be implemented as an association
list: a list of (variable . value) conses.  In CL, a second environment
is needed for functions (and GO tags, and ...), but it's just more of the
same thing.  An interpreter for a very restricted language with similar
scoping rules, could look like:
||#
(defvar *definitions* ()
  "An alist mapping function names to a list of positional arguments
and a form.")

(defmacro defminifun (name (&rest arguments) &body body)
  ;; ... or &whole
  `(progn
     (push ',(list* name arguments body) *definitions*)
     ',name))

(defmacro defprimitive (name)
  ;; primitives are denoted with a bogus definition.
  `(progn
     (push ',(cons name :cl) *definitions*)
     ',name))

(defun lookup-in-environment (name environment)
  (or (assoc name environment)
      (error "Unknown variable ~S" name)))

(defun augment-environment (names values &optional environment)
  (pairlis names values environment))

(defun mini-eval (form environment)
  (cond ((symbolp form)
         (cdr (lookup-in-environment form environment)))
        ((atom form) form)
        (t (destructuring-bind (op . args) form
             (case op
               (let
                   (destructuring-bind (bindings . body) args
                     (eval-let bindings body environment)))
               (progn
                 (eval-progn args environment))
               (setf
                  (destructuring-bind (variable form) args
                    (let ((value (mini-eval form environment)))
                      ;; (setf (cdr ...)) ... is just syntactic sugar for
                      ;; a regular function, rplacd
                      (rplacd (lookup-in-environment variable environment)
                              value))))
               (t
                  (eval-call op args environment)))))))

(defun eval-let (bindings body environment)
  (let ((new-environment (augment-environment
                          (mapcar #'first bindings)
                          (mapcar (lambda (binding)
                                    (mini-eval (second binding)
                                               environment))
                                  bindings)
                          environment)))
    (mini-eval `(progn ,@body) new-environment)))

(defun eval-progn (args environment)
  (cond ((null args) nil)
        ((null (rest args)) (mini-eval (first args) environment))
        (t (mini-eval (first args) environment)
           (eval-progn (rest args) environment))))

(defun eval-call (function arguments environment)
  (let* ((values (mapcar (lambda (argument)
                           (mini-eval argument environment))
                         arguments))
         (definition (cdr (or (assoc function *definitions*)
                              (error "Unknown function ~S" function)))))
    (if (eql :cl definition)
        (apply function values)
        (destructuring-bind (arguments . body) definition
          (assert (= (length values) (length arguments)))
          (mini-eval `(progn ,@body)
                     (augment-environment arguments values))))))

#||
There are two key elements here:
1. The environment is never leaked to the interpreted program.  It could be
represented in any manner, or even not exist at all, and there could never
be any difference to the program under evaluation.  It really is an
implementation detail (and a bad implementation at that) .

2. Each function gets a fresh environment.  So, while each function can
mutate its own environment, it can never affect that of its callers.  However,
it can still mutate values to which environments (its own or its callers')
refer.

For instance:
||#

(defminifun foo (x y)
  (setf x y))

(mini-eval `(let ((x 42))
              (foo x 5)
              x)
           nil)
=> 42

#||
 * How that can be extended to handle first-class functions
Closures are a classic implementation of first-class functions with lexical
scoping.  The idea is that each function should also carry its environment.
For instance, in EVAL-CALL, instead of

          (mini-eval `(progn ,@body)
                     (augment-environment arguments values))
we would have
          (mini-eval `(progn ,@body)
                     (augment-environment arguments values
                                          function-base-environment))


LAMBDA can then be implemented as an operator that returns a tuple consisting
of the function's definition itself (arguments and body), and of the
(lexical) environment in which the function was defined (evaluated).

Lisp in Small Pieces covers that sort of questions more thoroughly and more
clearly than this paste.  But, again, they're only examples of implementation
techniques, and it's very likely that your favourite implementation do
things differently.
||#