On function/value namespaces in Emacs Lisp

Trying to understand why there are different namespaces for functions and values in Lisp₂, I was diving into that a little bit. The notes taken and macros written on that way are shown here. Providing local namespaces for the development of further macros, they can help to prevent unwanted free name capture.

When diving into that topic, you eventually stumble upon Technical Issues of Separation in Function Cells and Value Cells¹. According to that paper, among others a prime reason for two separate namespaces is the existence of macros, as expressed in the well known citation taken from there: "a single namespace is of fundamental importance, and therefore macros are problematic [… but] macros are fundamental, and therefore a single namespace is problematic".

So which problem with macros is solved by applying different namespaces? When accidentally naming a local variable the same as a global function, with a single namespace this would hide the global function. While not being encouraged at all, name clashes could be resolved within a local environment without refactoring the variable names. For example, if the function was not addressed within the environment, the fact that it is hidden wouldn't be a problem at al. But this would work only as long as no macros are used. Because macros can expand arbitrary code into the environment, the prerequisite given above could not be checked.

To solve this problem of name collisions in macro expansions, the following aspects need to be handled. For variable names of let-environments within the macro expansion, it is typically handled by creating uninterned anonymouns symbols (by means of gensym) replacing their value symbols. This way, for variables, effectively a local namespace is created only visible within the macro expansion. Next, local variable names of the outer environment a macro expansion is inserted into can't be addressed from within the macro expansion as long as they can't be known in the macro definition. So addressing an arbitrary value symbol from within macro expansion would be an error, if that name was not communicated somehow.

Stays the question of function names being addressed from within the macro expansion. Here, in accordance to the previous statement, the set of global functions can be seen as being communicated. So macros should expect being able to address global function names regardless of the local environment they are expanded into. To make this work, the problem mentioned above would be mitigated by using a common function namespace shared between the place the macro is defined in and environments it is expanded into. Given that, macros could expect function names addressed in their definition to be valid also in the places they are expanded into.

But in the paper mentioned above, an example is given also showing name collisions in function namespace. It is repeated here, slightly adopted to emacs lisp:

(defmacro foo (x y) `(cons 'foo (cons ,x (cons ,y nil))))

(defun baz (x y)
  (cl-flet ((cons (x y) (cons y x)))
    (foo x y)))

(baz 1 2)

Which results in an output probably not intended by the macro author:

(((nil . 2) . 1) . foo)

This could be solved within the macro by replacing the function symbol cons by it's function object valid when the macro was defined instead of resolving it in the place of it's expansion:

(defmacro foo (x y)
  `(funcall ,(symbol-function 'cons) 'foo
            (funcall ,(symbol-function 'cons) ,x
                     (funcall ,(symbol-function 'cons) ,y nil))))

(defun baz (x y)
  (cl-flet ((cons (x y) (cons y x)))
    (foo x y)))

(baz 1 2)

Which now gives the result probably intended:

(foo 1 2)

But now, the funcall function name is still subject to possible free name capture. The paper's section concludes: "With the advent of FLET, LABELS, and MACROLET, the risk of conflict is considerably higher".

What's done manually in this example to solve that conflict is quite similar to the solution used by hygienic macros. It involves resolving free symbols from within a macro expansion using the lexical context of the corresponding macro definition. But maybe this was not at all intended by the macro. After all, it is a valid use case to globally replace the implementation of certain functions at runtime, which then actually should be respected not only globally, but also by macro expansions.

In Let over Lambda², Hoyte concludes, "Hygienic macros are, in the best of situations, a beginner's safety guard-rail; in the worst of situations they form an electric fence, trapping their victims in a sanitised, capture-safe prison".

The considerations shown above give a strong hint that a common global function namespace is expected to exist, having the properties of being shared between all global parts of a running system and still being dynamically modifyable (within boundaries) while staying in a consistent state.

So an alternate approach would be not to fix the problem within the macro definition, but instead in the place the macro is expanded into. As local variable names are expected to not being hidden by macro expansions—and consequently, pushing the responsibility of not doing that into the definition of macros, the same could also be done for local function names. But here, as a common global function namespace is expected, the responsibility of not hiding it within a local environment should be placed exactly upon these local environment definitions and not be pushed to the macro definitions.

In consequence, local function definitions would have to make sure their names don't clash with any global function definition, so these local functions could be only addressed from expressions located lexically within the local environment, but not from macros expanded into that place.

This idea can't be implemented as a macro, as this would involve code walking prior to macro expansion. But to implement a reliable code walking function, prerequisite is to bring the syntax tree serving as input into a normal form, where each expression is a list consisting of a symbol or a lambda expression in first position and symbols or normalized expressions in all further positions. So, for example let-constructs would be replaced by lambda calls, macro applications introducing different syntax would be expanded. Given this it is clear there is no normal form and, consequently, no reliable code walking without macro expansion. On the other side, with macros expanded already, the function calls that should not be addressing local function definitions are already in place. And then, after macro expansion, there is no distinction between function calls resulting from macro expansion and function calls subject to local function definitions. Nevertheless, the following experiment can illustrate what to do manually to avoid name clashes when using local functions.

In each place a local function is addressed within the environment, it would be replaced by a unique symbol, but before macro expansion takes place. Otherwise, it would also modify the macro expansion, which we don't want to happen here.

The macro local-flet uses a function code-walking the given body, doing this replacement. Fortunately, given the definition of a separate function namespace, function names can only appear in exactly two situations: in the function position of expressions, or being sharp-quoted; that is as argument to the function function. Unfortunately, as shown above, actually code-walking isn't that easy, so this works only in simple cases.

The macro expects the same arguments as cl-flet and creates a local function namespace not visible to macro expansions within.

(defmacro local-flet (fdefs &rest body)
  (declare (indent defun))
  (let ((fncsyms (cl-loop for (name . _) in fdefs collect
                          `(,name . ,(gensym name)))))
    (cl-labels ((local/assoc-value-safe (name assoc)
                                      (pcase name
                                        (`(lambda ,args ,body) `(lambda ,args ,(local/replace-local-functions fncsyms body)))
                                        (name (let ((val (assoc name assoc)))
                                                (if val (cdr val)
                                                  name)))))
                (local/replace-local-functions (fncsyms expr)
                                             (pcase expr
                                               (`(function ,fnc) `(function ,(local/assoc-value-safe fnc fncsyms)))
                                               (`(quote . ,rest) `(quote . ,rest))
                                               (`(,fnc . ,args) `(,(local/assoc-value-safe fnc fncsyms)
                                                                  .
                                                                  ,(cl-loop for elem in args collect
                                                                            (local/replace-local-functions fncsyms elem))))
                                               (value value))))
      `(cl-flet ,(cl-loop for (name . expr) in fdefs collect
                          `(,(local/assoc-value-safe name fncsyms) . ,expr))
         ,@(cl-loop for expr in body collect
                    (local/replace-local-functions fncsyms expr))))))

Using this, the function definition from the example above could be modified as follows, resolving the issue without any need to modify the macro:

(defmacro foo (x y) `(cons 'foo (cons ,x (cons ,y nil))))

(defun baz (x y)
  (local-flet ((cons (x y) (cons y x)))
    (foo x y)))

(baz 1 2)

(foo 1 2)

And, demonstrating simultaneous application of the local function and the macro expansion shows that it works lexically:

(defun baz (x y)
  (local-flet ((cons (x y) (cons y x)))
    (cons 0 (foo x (funcall #'cons '(cons 3 4) y)))))

(baz 1 2)

((foo 1 (2 cons 3 4)) . 0)

Now, if you additionally choose to replace the global definition of cons using a dynamic approach like cl-letf, as expected this affects the global environment and macro expansions, but leaves the local definition.

In a similar way, a local-labels macro would be devised. But there, the local function definitions, possibly having recursive definitions, would also be subject to the replacement.

But as code-walking without prior macro expansion cannot work reliably, this stays an idea. In real life, it can be taken as a hint to use unique names also for local functions. So it seems to be a good idea to use same the naming conventions as those used for global functions in emacs lisp, prepending function names with a package name, in a similar way also for local function definitions.

In a similar way, a macro can be used to create a local value namespace within macro expansions, this way avoiding interference with the environment a macro is expanded into. The macro shown here is an extension of the with-gensyms macro³. The syntax of that macro, with-macro-namespace, is similar, just naming a list of value symbols. These symbol names can then be used safely and "un-unquoted" within the actual macro definition.

This is similar to the idea of metatronic macros⁴. But there, the value symbols used within macro expansion are enclosed within special syntax. This seems to be unnecessary, as the names to be handled this way are already declared.

The macro works by building a quoted expression (which generates the s-exp to be used as macro expansion), but then unquoting all references to the value symbol names of the detached namespace. It is done by expanding each quoted list into a list expression whose elements are quoted. If an element is declared to be part of the detached namespace, instead it is not quoted, this way effectively and implicitely unquoting it.

It then expands to an expression where the variables are defined and initialized as gensyms, then putting in the quoted s-exp previously built. So at the end, it automates what is typically done when writing macros—after all, that's what macros are made for, arent they?

(provide 'macro-namespace)

(defmacro with-macro-namespace (syms body)
  (declare (indent defun))
  (let ((pquote (gensym)))
    (let ((qbody
           (macroexpand-all `(cl-macrolet ((quote (arg)
                                                  (cond
                                                   ((atom arg) (if (member arg (quote ,syms))
                                                                   arg
                                                                 `(,',pquote ,arg)))
                                                   ((eq (car arg) 'outer) `(,',pquote ,(cadr arg)))
                                                   (`(list ,@(mapcar (lambda (elem) `(quote ,elem))
                                                                     arg))))))
                               ,body))))
      `(let ,(mapcar (lambda (sym)
                       `(,sym (gensym ,(symbol-name sym))))
                     syms)
         (cl-macrolet ((,pquote (arg) `(quote ,arg)))
           ,qbody)))))

So instead of writing (just for the sake of an example):

(defmacro foo (expr)
  (let ((val (gensym)))
    `(let ((,val ,expr))
       (1+ ,val))))

you would juse use this:

(defmacro foo (expr)
  (with-macro-namespace (val)
    `(let ((val ,expr))
       (1+ val))))

expanding to

(defmacro foo (expr)
  (let ((val (gensym "val")))
    (cons 'let
          (cons
           (list
            (list val expr))
           (list
            (list '1+ val))))))

and be fine.

If a variable of an outer namespace having the same name as a variable of the local macro namespace is to be addressed from within the expansion, this can be done with the outer form. This works in a way similar to using function, explicitely addressing names of the function namespace from within value namespace. Here, it just translates (outer val) to a quoted symbol 'val (actually just leaving it being quoted), so it can also be used when addressing arbitrary symbols not defined in the local namespace without any harm. It just makes sure that the unquoting mechanism for local value symbol names is overridden. At the end, this macro gives a fine-grained and explicit control for avoiding and adressing symbols from an environment a macro is expanded into.

In conclusion, all function names should be considered (somehow globally) visible to arbitrary code and therefore must be unique, even when defined within local environments. Macros addressing a function cannot expect them to be hidden by local function definitions. A solution to this could use an approach similar to that of implementing package namespaces, which also aim to prevent name clashes between globally visible function names.

On the other side, lexical variable names can only be used within their lexical environment. So here it's up to the macro expansions to make sure not to interfere with them. This can be addressed using local variable namespaces.

As long as these two points are respected, the separate function namespace helping to prevent hiding global functions within local value environments can serve as another building block to make macros work as expected.