How Lisp (Allegro Common Lisp) uses variables in lambda with ' vs #'

For a start, you should be aware that your tests 1-4 are conforming Common Lisp, while your tests 5 and 6 are not. I believe Allegro is perfectly well allowed to do what it does for 5 and 6, but what it is doing is outside the standard. The bit of the standard that talks about this is the definition of functions like mapcar, which take function designators as argument, and the definition of a function designator:

function designator n. a designator for a function; that is, an object that denotes a function and that is one of: a symbol (denoting the function named by that symbol in the global environment), or a function (denoting itself). The consequences are undefined if a symbol is used as a function designator but it does not have a global definition as a function, or it has a global definition as a macro or a special form. [...]

From this it is clear that a list like (lambda (...) ...) is not a function designator: it's just a list whose car happens to be lambda. What Allegro is doing is noticing that this list is in fact something that can be turned into a function and doing that.

Well, let's just write a version of mapcar which does what Allegro's does:

(defun mapcar/coercing (maybe-f &rest lists)
  (apply #'mapcar (coerce maybe-f 'function) lists))

This just uses coerce which is a function which knows how to turn lists like this into functions, among other things. If its argument is already a function, coerce just returns it.

Now we can write the two tests using this function:

(defun test-5/coercing (y)
  (mapcar/coercing '(lambda (x) (expt x 2))
                   '(1 2 3)))

(defun test-6/coercing (y)
  (mapcar/coercing '(lambda (x) (expt x y))
                   '(1 2 3)))

So, after that preamble, why can't test-6/explicit work? Well the answer is that Common Lisp is (except for for special variables) lexically scoped. Lexical scope is just a fancy way of saying that the bindings (variables) that are available are exactly and only the bindings you can see by looking at the source of the program. (Except, in the case of CL for special bindings, which I'll ignore, since there are none here.)

So, given this, think about test-6/coercing, and in particular the call to mapcar/coercing: in that call, coerce has to turn the list (lambda (x) (expt z y)) into a function. So it does that. But the function it returns doesn't bind y and there is no binding for y visible in it: the function uses y 'free'.

The only way that this could work is if the function that coerce constructs for us were to dynamically look for a binding for y. Well, that's what dynamically-scoped languages do, but CL is not dynamically-scoped.

Perhaps a way of making this even clearer is to realise that we can lift the function creation right out of the function:

(defun test-7 (y f)
  (mapcar f '(1 2 3)))

> (test-7 1 (coerce '(lambda (x) (expt x y)) 'function))

It's clear that this can't work in a lexically-scoped language.

So, then, how do tests 1-4 work?

Well, firstly there are only actually two tests here. In CL, lambda is a macro and (lambda (...) ...) is entirely equivalent to (function (lambda (...) ...)). And of course #'(lambda (...) ...) is also the same as (function (lambda (...) ...)): it's just a read-macro for it.

And (function ...) is a magic thing (a special form) which says 'this is a function'. The important thing about function is that it's not a function: it's a deeply magic thing which tells the evaluator (or the compiler) that its argument is the description of a function in the current lexical context, so, for instance in

(let ((x 1))
  (function (lambda (y) (+ x y))))

The x referred to by the function this creates is the x bound by let. So in your tests 2 and 4 (which are the same):

(defun test-4 (y)
  (mapcar (function (lambda (x) (expt x y)))
      '(1 2 3)))

The binding of y which the function created refers to is the binding of y which is lexically visible, which is the argument of test-4 itself.

Let's add a y parameter to avoid closing over variables and see what kind of values we are manipulating:

USER> (type-of #'(lambda (x y) (expt x y)))
FUNCTION

USER> (type-of (lambda (x y) (expt x y)))
FUNCTION

USER> (type-of '(lambda (x y) (expt x y)))
CONS

As you can see, the two first lambda-like forms are evaluated as functions, while the third is evaluated as a cons-cell. As far as Lisp is concerned, the third argument is just a tree of symbols with no meaning.

Reader macros

I thought that quoting a lambda with ' and using #' in front of a lambda both returned pointers to the function with the only difference being that the #' will compile it first.

Let's go back to the definitions, ' and #' are reader macros, respectively Single-Quote and Sharpsign Single-Quote. They are found in front of other forms, for example 'f is read as (quote f) and #'f is read as (function f). At read-time, f and the resulting forms are just unevaluated data.

We will see below how both special operators are interpreted, but what matters really is the lexical scope, so let's open a parenthesis.

Lexical environment

Lexical environments are the set of bindings in effect at some point of your code. When you evaluate a let or an flet it enriches the current environment with new bindings. When you call EVAL on an expression, you start evaluating from a null lexical environment, even if the call to eval itself is in a non-null environment.

Here x is just unbound during eval:

(let ((x 3)) (eval '(list x))) ;; ERROR

Here we build a let to be evaluated by eval:

(eval '(let ((x 3)) (list x)))
=> (3)

That's all for the crash course on lexical environments.

Special operators

Special operator FUNCTION takes an argument that is either the name of a function (symbol or setf), or a lambda expression; in particular:

The value of function is the functional value of name in the current lexical environment.

Here the lambda expression is evaluated in the current lexical environment, which means it can refer to variable outside the lambda expression. That's the definition of closures, they capture the surrounding bindings.

NB. you do not need to prefix lambda with #', because there is a macro named (lambda ...) that expands into (function (lambda ...)). It looks like this could expand recursively forever, but this is not the case: at first the macro is expanded so that (lambda ...) becomes (function (lambda ...)), then the special operator function knows how to evaluate the lambda expression itself. This means that (lambda ...) and #'(lambda ...) are equivalent. Note in particular that there is nothing about whether one form is compiled or not at this point, the compiler will see the same expression after macroexpansion.

Special operator QUOTE evaluates (quote f) as f, where f itself is unevaluated. In test-5 and test-6, there is no function, just an unevaluated structured expression that can be interpreted as code.

Type coercion

Now, certain functions like MAPCAR are used to apply functions. Notice how the specification says that the function parameter is a function designator:

function --- a designator for a function that must take as many arguments as there are lists.

A designator for a type is not necessarily a value of that type, but can be a value that can be coerced to that type. Sometimes a user wants to specify a pathname, and enters a string, but a string is not a value of type pathname: the system has to converts the string into a pathname.

Common Lisp defines a COERCE function with rules regarding how values can be converted to other values. In you case, mapcar first does (coerce (lambda ...) 'function). This is defined as follows:

If the result-type is function, and object is a lambda expression, then the result is a closure of object in the null lexical environment.

The value is thus evaluated in a null lexical environment, so it does not have access to the surrounding bindings; y is a free variable in your lambda expression, and since it is evaluated in a null environment, it is unbound. That's why test-5 pass but test-6 fails.

Name resolution, compilers and late binding

There is a difference whether you write #'f or 'f when referring to a function f where f is a symbol: in the first case, the expression evaluated to an object of type function, and in the second case, you only evaluate a symbol.

Name resolution for this function can change depending and how the compiler works. With a symbol as a function designator, the function does not even need to be defined, the name is resolved when the symbols has to be coerced as a function.

When you write #'f, some compilers may remove one level of indirection and directly make your code jump to the code associated with the function, without having to resolve the name at runtime.

However, this also means that with such compilers (e.g. SBCL), you need to recompile some call sites on function redefinition, as-if the function was declared inline, otherwise some old code will still reference the previous definition of #'f. This is something that is not necessarily important to consider at the beginning, but it can be a source of confusion to keep in mind when you are live coding.