How is "+" Implemented in Common Lisp Using Special Operators/Forms

Question

In On Lisp (page 9), one can find the following claim:

Functions are the building-blocks of Lisp programs. They are also the building-blocks of Lisp. In most languages the + operator is something quite different from user-defined functions. But Lisp has a single model, function application, to describe all the computation done by a program. The Lisp + operator is a function, just like the ones you can define yourself. In fact, except for a small number of operators called special forms, the core of Lisp is a collection of Lisp functions. What’s to stop you from adding to this collection? Nothing at all: if you think of something you wish Lisp could do, you can write it yourself, and your new function will be treated just like the built-in ones.

My question is how exactly would something like a + operator be implemented using the following special operators? Or are there actually more operators being used and Graham is just being imprecise and dramatic?

block      let*                  return-from      
catch      load-time-value       setq             
eval-when  locally               symbol-macrolet  
flet       macrolet              tagbody          
function   multiple-value-call   the              
go         multiple-value-prog1  throw            
if         progn                 unwind-protect   
labels     progv                                  
let        quote    

Is there a way to see source code for these functions?

Answer 1

In other language, with Algol being the most common and APL perhaps being the most obvious, making user defined abstractions that are indistinguishable from the functions and forms the language is shipped with is quite special.

Thus I think you misread the text. Imagine that you want make a numeric library that extends the language concept of numbers with perhaps Intervals. You make a library and define a way to create intervals and make your library work on number and intervals. If you had a library that did math you could just use your class in the library and it would work out of the box with intervals given that you have defined all the functions you need. Now in most Algol languages +, /, ... are not functions but operators and they have special rules so even though C++ has made operator overloading not many other languages has support for making a + that works with your new interval type. The solution would be functions which clearly won't look like the language own primitives since they are operators. In APL all the primitives have special symbols and all user defined doesn't so all user defined abstractions are easy to see are since they are not fancy symbols.

Today we come out with new revisions of Java, JavaScript, C++, etc. quite often. It's needed since those languages don't have a way to abstract on their own syntax in the language. JavaScript today has babel which basically gives you a method of transpiling one syntax to the other, but it has yet to transpile a feature that lets you do that from the language. These are things Lisp has had for several decades and modern languages are getting lisp features, but some are still sparse.

I've made a lisp language that had the same lack of numbers as the very first lisp since I wasn't interested in it. I also had to make 99 bottles of beer in that language. I used lists and symbols and made and defined +, -, zerop. and when you look at the actual program you can not see that it lacks numbers.

I enjoy Guy L. Steele's talk from 98 about extending programming languages. He is the original author of Scheme and have been involved in many languages, including Java and Common Lisp.

Answer 2

cl:+ just behaves like a function and is treated like a function.

It's not necessary that you can define it yourself or that it can be defined only using the other already defined CL standard operators. It's very likely that the definition of cl:+ uses implementation specific internal functionality.

Common Lisp has three types of operators: functions, macros and special operators.

The standard does not say much about how they are implemented. There is reason to believe that a Common Lisp implementation will have additional internal operators used to implement the standard ones.

• There is a fixed number of special operators - though a CL implementation may provided additional special operators. Special operators are not functions and there is no way for the user to define special operators.

• CL defines a bunch of standard macros and ways for the user to define new macros. How the standard macros are defined is not specified.

• CL defines a bunch of standard functions and ways for the user to define new functions. How the standard functions are defined is not specified.

Answer 3

On a practical level, you're correct in observing that it's not particularly efficient to implement + using only the core special forms, without any arithmetic-aware low-level utilities (since CPUs tend to be very good at arithmetic).

Graham's point, I believe, is more that there's nothing inherent in the + function in Common Lisp which would prevent you from defining it yourself. In most languages (C++ being another exception), + would be implemented in a fundamentally different way than user-defined functions. Two common reasons are because + usually uses infix notation, whereas function calls use func(arg1, arg2) notation; and it's not usually possible to define new user-created functions using random symbols like a plus sign.

Common Lisp, on the other hand, doesn't have this limitation. + uses the same syntactic structure as any other function, so that reason doesn't apply; and similarly, Common Lisp lets you use many different characters in function names.

For instance, this works fine (with a warning) in GNU clisp, whereas there would be no possible way to do the same thing in, say, JavaScript:

(defun + (a b) (- a (- 0 b))) ; using '- to avoid having to look up other forms

Answer 4

He's not saying every function is implemented in terms of these special forms.

He's saying + (like every other function) is a function:

• It can be called using the normal syntax (+ x y z) (where + is the function and x, y, z the arguments).
• The arguments will be evaluated first: (f (g) (h)) will call both g and h before calling f, even if f happens to be +.
• You can pass it around like any other function and call it through funcall and apply: (let ((x #'+)) (funcall x 1 2 3)) is 6.

The point is that these properties do not necessarily hold for special forms. if does not evaluate all of its arguments first; you can't take a reference to let and call it indirectly; etc.

Of course that still leaves the door open for "compiler magic". At some point + has to perform low-level operations that depend e.g. on how numbers are implemented. The details will look different depending on your Lisp compiler.

Answer 5

Here's the source from sbcl in src/code/numbers.lisp

(macrolet ((define-arith (op init doc)
             `(defun ,op (&rest numbers)
                (declare (explicit-check))
                ,doc
                (if numbers
                    (let ((result (the number (fast-&rest-nth 0 numbers))))
                      (do-rest-arg ((n) numbers 1 result)
                        (setq result (,op result n))))
                    ,init))))
  (define-arith + 0
    "Return the sum of its arguments. With no args, returns 0.")
  (define-arith * 1
    "Return the product of its arguments. With no args, returns 1."))