Search code examples
macroscommon-lispsymbols

What is the purpose of the `intern` function?

I'm following an article where the author defines the following macro:

(defmacro make-is-integral-multiple-of (n)
  (let ((function-name (intern (concatenate
                                'string
                                (symbol-name :is-integral-multiple-of- )
                                (write-to-string n)))))
    `(defun ,function-name (x)
       (equal 0 (mod x, n)))))

The macro is easy to read and understand, but I wonder: when and why do we explicitly need the intern function?

Removing it breaks the macro, which then returns the error:

The value "IS-INTEGRAL-MULTIPLE-OF-3"
is not of type
  (OR SYMBOL CONS).

Does that mean that intern must be called every time the macro is supposed to define a new symbol? Are there any uses of intern outside of a defmacro statement? Insights are welcome.

Solution

  • Why intern a symbol?

    symbols are usually thought as named objects used to name functions, variables, types and other things in Lisp. Symbols usually should be the same object when they have the same name (and are in the same package).

    (eq 'foo 'foo)

    If one executes the above code, then it usually would evaluate to T: to times reading the same symbol from input makes it also the same object.

    The data structure which keeps the mapping from names (-> strings) to symbols is in Common Lisp called a package. Now there are two basic operations:

    • intern : looks for a symbol in a package with a certain name. If there is none, it creates a new symbol.

    • find-symbol : looks for a symbol of a certain name in a package. It returns the found symbol. If there is no symbol, then it returns two values: NIL and NIL. The second value indicates, that the symbol with such a name wasn't found.

    The reader (the functionality in Lisp which reads s-expressions and creates data structures) also needs to be able to lookup symbols and to create new ones if necessary.

    For example (read-from-string "FOO") would internally call (intern "FOO" *package*).

    This allows us to type at the REPL:

    CL-USER > (eq 'foo 'foo)
T

    Reading the first foo let's the reader create a new symbol if there is none. Reading then the second foo just returns the existing symbol named foo.

    The user of Lisp can also create new symbols: by using INTERN or MAKE-SYMBOL.

    eq then will do something like a pointer comparison to see if two objects (here -> symbols) are the same objects. Internally looking up a name in a package is typically a hashtable lookup.

    Historically in LISP a list or an array were sometimes used to keep track of all symbols. Then btree data structures were used for faster lookup. Common Lisp implementations use internally hashtables to map from names (-> strings) to symbols.

    Function names

    The name of a function needs to be of type (OR SYMBOL CONS). This is required by the Common Lisp standard.

    Thus the name needs to be a symbol or a list. Usually function names in Lisp have to be symbols. That they can be lists is relatively special for setf functions. In Common Lisp it can only be a list like (setf foo), with setf as the first symbol. Other lists as function names are not allowed in plain Common Lisp. (side-note, the older Lisp Machine Lisp had other lists as function names).

    (defun foo (bar)     ; FOO is a symbol and the name of the function
  (+ 42 bar))

    The following is unusual and actually a feature of Common Lisp:

    (defun (setf a) (new-value thing)    ; (setf a) is the name of the function
  (setf (first thing) new-value))

    Generating Function Names with INTERN and MAKE-SYMBOL

    So, if you want to generate a new function name, it typically needs to be a symbol. First generate the new name as a string and then generate a symbol from that string.

    There are several ways to create a symbol. INTERN will look if the symbol already exists in the package (the current package is the default). If it does not exist, it will create a new one and intern that symbol in that package.

    One could also use MAKE-SYMBOL to create a symbol, but that symbol would not be in any package. This makes it usually difficult to access that symbol.

    Typically a function name should be a symbol, which is interned in some package. Only in rare situations, for example some cases of computed code, it can be useful to have an uninterned symbol as a function name. Uninterned symbols can't be looked up by name from a package.