Lisp quote work internally

Question

How does lisp quote work internally? For example:

(quote (+ 1 (* 1 2)) )

seems to be equivalent to

(list '+ 1 (list '* 1 2))

which means it is some how symbolizing the Head values recursively. Is this function a built in?

Run (equal (quote (+ 1 (* 1 2))) (list '+ 1 (list '* 1 2))) if you don't believe me.

Colecolectomy

Possible duplicate of When to use 'quote in Lisp – Pleinair

@NathanHughes This is not a duplicate. The question is how is it implemented internally. – Colecolectomy

quote is a special form (not a function) that returns its argument without evaluating it. With function application, on the other hand, all arguments are evaluated beforehand (so if quote was an ordinary function, it would only see 3 as argument, not the list (+ 1 (* 1 2)) (code is data, after all)). So yes, it's built in, and actually does less than function application. – Aglimmer

The conversion from text to symbols is done by the reader, well before quote is used to influence evaluation. – Bryce

Answer 1

How does it work?

quote is really really simple to implement. It does mostly nothing. The quote special operator just returns the enclosed object like it is. Nothing more. No evaluation. The object is not changed in any way.

Evaluation of quoted forms

Probably a good time to read McCarthy, from 1960:

Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

Pages 16/17 explain evaluation with eval. Here:

eq [car [e]; QUOTE] → cadr [e];

or in s-expression notation:

(cond

  ...

  ((eq (car e) 'quote)
   (cadr e))

  ...)

Above code implements the evaluation rule for QUOTE: If the expression is a list and the first element of the list is the symbol QUOTE, then return the second element of the list.

Equivalence of a quoted list with a list created by LIST

(equal (quote (+ 1 (* 1 2)))
       (list '+ 1 (list '* 1 2)))

The result is T. This means that both result lists are structurally equivalent.

(eq (quote (+ 1 (* 1 2)))
    (list '+ 1 (list '* 1 2)))

The result is NIL. This means that the first cons cell of the linked lists are not the same objects. EQ tests whether we really have the same cons cell object.

• QUOTE returns a literal data object. The consequences of modifying this object is undefined. So, don't do it.

• LIST returns a new freshly consed list each time it is called. The fresh new list will not share any cons cells with any earlier allocated list.

So the main difference is that QUOTE is a built-in operator, which returns literal and unevaluated data. Whereas LIST is a function which creates a new,fresh list with its arguments as contents.

See the effects with respect to EQ and EQUAL:

CL-USER 6 > 
(flet ((foo () (quote (+ 1 (* 1 2))))
       (bar () (list '+ 1 (list '* 1 2))))
  (list (list :eq-foo-foo    (eq    (foo) (foo)))
        (list :eq-foo-bar    (eq    (foo) (bar)))
        (list :eq-bar-bar    (eq    (foo) (bar)))
        (list :equal-foo-foo (equal (foo) (foo)))
        (list :equal-foo-bar (equal (foo) (bar)))
        (list :equal-bar-bar (equal (foo) (bar)))))

((:EQ-FOO-FOO    T)
 (:EQ-FOO-BAR    NIL)
 (:EQ-BAR-BAR    NIL)
 (:EQUAL-FOO-FOO T)
 (:EQUAL-FOO-BAR T)
 (:EQUAL-BAR-BAR T))

is quote a function?

quote can't be a function, since it returns its enclosed data unevaluated. Thus it is a special evaluation rule.

If quote were a function, it's arguments were evaluated. But that's exactly what is NOT what quote is supposed to do.

why does Lisp need QUOTE?

Lisp usually uses s-expressions to write Lisp code. So s-expressions have a both purpose to denote data and we use it to write programs. In a Lisp program lists are used for function calls, macro forms and special forms. symbols are used as variables:

(+ n 42)

Here (+ n 42) is a list and n is a symbol. But we also want to use lists as data in our programs and we want to use symbols as data. Thus we have to quote them, so that Lisp will not see them as programs, but as data:

(append '(+ n) '(42))  evaluates to (+ n 42)

Thus in a Lisp program, lists and variables are by default part of the language elements, for example as function calls and variables. If we want to use lists and symbols as literal data, we have to quote them, to prevent the evaluator treating them as Lisp code to evaluate.

Protein

Then how do you implement such function? It doesn't appear you answer the question exactly. – Colecolectomy

@William: quote is not a function. It is a special operator and an implementation is exactly shown in my answer. The two lines inside the COND are an implementation of QUOTE. Additionally read the pages 16/17 in McCarthy's paper. – Protein

It should be possible to implement a lisp parser in lisp just like in Python. That is hardly a runnable function but more of a psuedo code at best. – Colecolectomy

@William: since QUOTE is neither a function, nor a part of a Lisp 'parser' this would be difficult. QUOTE is implemented by the Lisp execution engine, the interpreter or compiler. It's just a clause in an interpreter implementation, which evaluates a quoted data object, to the data object itself. – Protein

@William as Rainer says: QUOTE is part of the implementation of the evaluator: somewhere there is code which says 'if evaluating a list then if the car of the list is QUOTE then if the list has length 2 return the second element then ... various error cases, various other cases ...'. All special operators are essentially parts of the implementation of the evaluator in this way. – Warily

Answer 2

quote does nothing more than return its argument unevaluated. But what is an unevaluated argument?

When a Lisp program is defined, it is either read from textual source into s-expression form or constructed directly in terms of s-expressions. A macro would be an example of generating s-expressions. Either way there is a data structure comprising (mostly) symbols and conses that represents the program.

Most Lisp expressions will call upon evaluation and compilation machinery to interpret this data structure as terms in a program. quote is treated specially and passed these uninterpreted symbols and conses as its argument. In short, quote does almost nothing - the value it returns already exists and is simply passed through.

You can observe the difference between passing through and fresh construction by using eq to test the identity of the return value of quote:

(defun f () '(1 2))

(defun g () (list 1 2))

(eq (f) (f)) => T
(eq (g) (g)) => NIL

As you can see, quote returns the same conses each time through.

Oriole

I believe (eq (f) (f)) is returning true simple because it is a constant. If you use (equal (g) (g)) they both return true. I'm asking how is quote implemented so as it stands this does not answer the question. – Colecolectomy

I believe it's unspecified whether (quote e) must return the same object every time it's evaluated. – Roncesvalles