Why Add Only Present-Symbols to A Shadowing-List?

I wonder if there's another way to resolve a conflict between the symbol and an external symbol from a package I want to use.

For example:

In CL-USER, I use two packages A and B. Both export the symbol cat, that's to say, there is a conflict between A:cat and B:cat. But I hope to refer to A:cat by only writing cat.

The book Practical Common Lisp says,

if a package needs to use two packages that have external symbols of the same name, one of the symbols must be imported into the using package in order to be added to its shadowing list and make the other symbol inaccessible.

It means that I should add the symbol cat to CL-USER's name-symbol table first and then add it to the shadowing list. That's what's bothering me.

Why doesn't CL simply add the symbol cat to the shadowing list together with the name of its home package? Like this:

CL-USER uses A and B. Add A:cat to shadowing list.
Then, shadowing list:
(("CAT" "A") ("another-symbol" "its-home") ...)

When reader reads cat in CL-USER, it first searches "CAT" in CL-USER's name-symbol table and find nothing. Then, it searches it in the shadowing list and find that the cat here means A:cat.

This really resolves the conflict and there is no need to import cat. Why doesn't CL take this approach?

Solution

First of all there are lots of ways the package system could have worked, and many people will argue that the way it does work is far from ideal.

But I think you are confused about shadowing. When a package shadows a symbol it does not shadow it from one particular other package: it shadows it from all possible packages with which there might be a clash. What shadowing does is to say that 'at any future time, if there might be a clash, resolve it in favour of my symbol'. Given that it clearly makes no sense for a shadowing list to mention other packages.

In addition there's a desire to make symbol lookup fast. In particular if you're in some package p and you want to turn a string (non-package-qualified for the sake of argument) into a symbol the algorithm is very simple:

look up name in the current package and return it if found;
if not, look it up in the packages used by the current package as an external symbol and if one (there will be only one!) is found, return it;
intern the symbol in p and return it.

Note that this algorithm does not concern itself with shadowing symbols at all. The time you do need to be concerned about it is only when something changes in the state of the package system:

a package being used by p changes its list of exported symbols (see comment);
the list of packages p uses changes (see comment);
you try to import new symbols into p;
a symbol which is interned in p is uninterned;
(and perhaps some things I have forgotten).

For the first two things, no action is needed, but the system needs to not report an error if a package that p uses now exports a symbol that p is shadowing.

It would be possible in one limited case to have a system which worked by having shadowing be defined in terms of symbol names (strings) rather than symbols. This would make a difference in the case where you want to create a symbol whose home package is the package doing the shadowing: in that case you could delay creating that symbol until it was first mentioned. In this case, perhaps:

(defpackage :foo
  (:use :cl)
  (:shadow #:a))

(in-package :foo)

(find-symbol "A")                       ;false?
'a                                      ;creates A, home package FOO
(find-symbol "A")                       ;true

The gain from doing this is minute: if you're saying you want to shadow something in FOO then presumably you are intending to create that symbol pretty soon, so you might as well just go ahead and create it now. However doing things this way does have cost: the string-to-symbol algorithm is now more complicated, and would have to be:

look up name in the current package and return it if found;
if not, check to see if the name is on the shadowing list and skip the next step if it is;
if you get here it's not found, and the name is not on the shadowing list, so look it up in the packages used by the current package as an external symbol and if one (there will be only one!) is found, return it;
otherwise intern the symbol in p and return it.

Doing this also would not help you in the common case where you wish to prefer a symbol from one of several other packages. Given:

(defpackage :one
  (:use)
  (:export #:a))

(defpackage :two
  (:use)
  (:export #:a))

Then if I create a package THREE, and I want A, in the context of THREE, to be ONE:A then I need to make sure that the string-to-symbol algorithm succeeds in the first step: I need the string "A" to resolve to ONE:A, and for that to happen I need to import that symbol into FOO.

Thus making sure that a package which is going to shadow a symbol already contains that symbol both makes this common case actually work, and in any case simplifies the algorithm for finding symbols.

As I said at the top: there are other ways that the package system could have worked. Finally, I may have simply forgotten some cases above.