Monthly Archives: January 2014

The less-familiar parts of Lisp for beginners — eq, eql, equal, equalp, =

One thing the newcomer to Lisp from C++ might wonder about is why there are so many ways to compare for “equality”.  The short list includes eq, eql, equal, equalp, and =.  Newcomers writing code tend to just toss one of those in and then change it around if the code doesn’t behave as desired, but this can be dangerous as the resulting code may only be producing the desired results accidentally, on a particular platform, and not be correct, portable code.  Some introductions to Lisp do a good job of explaining the differences between these equality comparison functions, while others do not.  Let’s go over them, with an eye to how the C++ programmer might view them.

In C++, it is common for the programmer to define an operator== to compare two objects of the same or different classes for “equality”.  This is helpful to the programmer, but can be a problem for the maintainer, as the programmer generally codes the operator to be “equal for my purposes, in the code I plan to write”.  When another programmer comes along, they will likely have to review all definitions of operator== to make sure that they understand what definition of equality is being tested here.

In Lisp, a few different definitions of equality are available with these functions.  The programmer is always free, of course, to define other named functions to test yet other definitions of equality, preferably with function names that help to clarify to the reader of the code what, exactly, is being checked.

To begin, please review the discussion on object allocation in this earlier article on define-modify-macro.  As outlined there, entities in Lisp tend to fall into three allocation categories.  There are objects and structures, which must always be explicitly allocated, and are always passed by reference.  There are arrays and lists, which form their own category of in-memory objects, but which can have multiple entry points giving different views.  Finally, there are numbers, characters, keywords, and symbols, which can be passed by value, and are not explicitly constructed.

So, we start with eq.

  • Two references to objects or structures are only equal by the definition of eq when they are pointers to the same in-memory object.  If a modification is made to one of these data structures through one reference, the change is reflected in the other reference, and the references continue to compare as eq after this modification.
  • The same rule applies for arrays and lists.  Two references to a list are equal under eq only if they point to the same in-memory list, and both point to the same starting node.  You saw the consequences of this in the discussion of defconstant earlier in this series.
  • The third category of numbers, characters, keywords, or symbols.  Numbers and characters should not be compared with eq, as there is no guarantee of behaviour.  Keywords and symbols will compare eq if they are the same symbol (generally, if they have the same printable representation).

Next, we go to eql.

  • On objects and structures, eql behaves the same as eq.
  • The eql function is not intended for arrays and lists.  It may not behave as expected.  Use equal or equalp.
  • The eql function also compares for equality on numbers and characters.  It should not be used on keywords and symbols.  Also, it is not guaranteed to behave as expected on floating-point numbers.  Use = for numeric comparison.

On to equal.

  • Do not use equal to compare objects or structures.
  • For arrays and lists.  Two references to arrays are equal if they are references to the same in-memory object.  Strings and bit-vectors, which are specialized arrays, are treated differently, and are compared element-by-element.  Two lists are equal if they have the same structure, and all of their elements are separately equal.
  • The equal function on numbers and characters behaves exactly like eql.

Next, equalp.

  • This function can operate on structures, but not usefully on objects.  Two structures are equalp if they have the same class (i.e. are incarnations of the same structure), and all slots in the two structures are separately equalp.
  • On arrays and lists, two references are equalp if they have the same layout (number of dimensions for arrays, cons structure for lists), and all the elements are separately equalp.  In effect, if they would print out the same, they are equalp.
  • Two numbers are equalp if they have the same numeric value.  For keywords and symbols, use only eq.  For characters, equalp is the same as equal.

Finally, =.

  • This function cannot be used on structures or objects.
  • This function cannot be used on arrays and lists.
  • This function behaves exactly like equalp on numeric values.  It cannot operate on non-numeric arguments.

The first four functions form a progression: eq eql equal equalp.  It will never be the case that eq is true, while one of the functions to its right is false, and that rule applies down the chain.  Two objects that are equal will always be equalp.

You’ll note that equalp behaves differently for instances of classes and for structures.  This is unlike C++, where classes and structures are semantically identical save for the default access qualifier (in the absence of public/protected/private keywords).

That’s the overview of the functions.  Now, looking at it from the other direction, how do you compare categories of objects:

  • Objects (instances of classes) are compared with eq, which tells  you whether two references are to the same in-memory object.  Any other comparison must be made with user-written functions.
  • Structures are compared with eq, eql, equal or equalp.  If eq, eql, or equal, they are the same in-memory structure.  If equalp, they may or may not be the same structure, but they are instances of the same structure definition, with equal slot values.
  • Arrays (but not strings or bit-vectors) are equal if they point to the same array, and equalp if they have the same dimensions and the same contents in each element.
  • Strings and bit-vectors are equal if they have the same contents.
  • Lists are eq if they point to the same entry point of the same in-memory object.  They are equalp if they have the same layout with equalp contents.
  • Symbols and keywords are eq if they evaluate the same, generally if they have the same printable representation.
  • Characters are eql if they print the same.  Testing under eq is not guaranteed to produce the expected results.
  • Numbers are = if they are mathematically equal, regardless of type.

Next, we show these comparison in action:
 

(defclass example-class ()
  ((slot-A      :accessor get-A
                :initform :A)
   (slot-B      :accessor get-B
                :initform :B)))

(defun compare-instances ()
  (let ((instance-1 (make-instance 'example-class))
        (instance-2 (make-instance 'example-class)))
    (format t "Two different instances of example-class, with same contents~%")
    (format t "Under EQ, they compare to: ~A~%"
            (eq instance-1 instance-2))
    (format t "Under EQUALP, they compare to: ~A~%"
            (equalp instance-1 instance-2))))

(defstruct (example-struct)
  (slot-A       :A)
  (slot-B       :B))

(defun compare-structs ()
  (let ((struct-1 (make-example-struct))
        (struct-2 (make-example-struct)))
    (format t "Two different instances of example-struct, with same contents~%")
    (format t "Under EQ, they compare to: ~A~%" 
            (eq struct-1 struct-2))
    (format t "Under EQUALP, they compare to: ~A~%"
            (equalp struct-1 struct-2))))

(defun compare-arrays ()
  (let ((array-1 (make-array '(2 2) 
                             :initial-contents '((:A :B)
                                                 (:C :D))))
        (array-2 (make-array '(2 2) 
                             :initial-contents '((:A :B)
                                                 (:C :D)))))
    (format t "Two different arrays, with same dimensions and contents~%")
    (format t "Under EQUAL, they compare to: ~A~%" 
            (equal array-1 array-2))
    (format t "Under EQUALP, they compare to: ~A~%"
            (equalp array-1 array-2))))

(defun compare-strings ()
  (let ((string-1 "abc")
        (string-2 "abc"))
    (format t "Two different strings, with same contents~%")
    (format t "Under EQ, they compare to: ~A~%" 
            (eq string-1 string-2))
    (format t "Under EQUAL, they compare to: ~A~%" 
            (equal string-1 string-2))))

(defun compare-lists-1 ()
  (let* ((struct-1 (make-example-struct))
         (struct-2 (make-example-struct))
         (list-1 (list struct-1))
         (list-2 (list struct-2)))
    (format t "Two different lists, each with its own example-struct, ~%")
    (format t "those two structs being EQUALP~%")
    (format t "Under EQUAL, they compare to: ~A~%" 
            (equal list-1 list-2))
    (format t "Under EQUALP, they compare to: ~A~%" 
            (equalp list-1 list-2))))

(defun compare-lists-2 ()
  (let* ((struct-1 (make-example-struct))
         (list-1 (list struct-1))
         (list-2 (list struct-1)))
    (format t "Two different lists, each containing the same example-struct~%")
    (format t "Under EQ, they compare to: ~A~%" 
            (eq list-1 list-2))
    (format t "Under EQUAL, they compare to: ~A~%" 
            (equal list-1 list-2))))

(defun compare-numbers ()
  (let ((val-1 (/ 1 2))
        (val-2 0.5d0)
        (val-3 (complex 0.5 0.0)))
    (format t "The value 1/2, expressed as rational, real, and complex:~%")
    (format t "Comparing rational to real under =  ~A~%" 
            (= val-1 val-2))
    (format t "Comparing rational to complex under =  ~A~%" 
            (= val-1 val-3))
    (format t "Comparing real to complex under =  ~A~%" 
            (= val-2 val-3))))

With output:
 
CL-USER> (compare-instances)
Two different instances of example-class, with same contents
Under EQ, they compare to: NIL
Under EQUALP, they compare to: NIL
NIL
CL-USER> (compare-structs)
Two different instances of example-struct, with same contents
Under EQ, they compare to: NIL
Under EQUALP, they compare to: T
NIL
CL-USER> (compare-arrays)
Two different arrays, with same dimensions and contents
Under EQUAL, they compare to: NIL
Under EQUALP, they compare to: T
NIL
CL-USER> (compare-strings)
Two different strings, with same contents
Under EQ, they compare to: NIL
Under EQUAL, they compare to: T
NIL
CL-USER> (compare-lists-1)
Two different lists, each with its own example-struct, 
those two structs being EQUALP
Under EQUAL, they compare to: NIL
Under EQUALP, they compare to: T
NIL
CL-USER> (compare-lists-2)
Two different lists, each containing the same example-struct
Under EQ, they compare to: NIL
Under EQUAL, they compare to: T
NIL
CL-USER> (compare-numbers)
The value 1/2, expressed as rational, real, and complex:
Comparing rational to real under =  T
Comparing rational to complex under =  T
Comparing real to complex under =  T
NIL

The less-familiar parts of Lisp for beginners — ensure-generic-function

Another rarely used Lisp function is ensure-generic-function.  This is used to create a dynamic function when one does not exist, or verify the compatibility of an existing dynamic function’s lambda list (think “argument list” in C++) with one supplied in the arguments.

To see an example of this in use, see the earlier article on add-method.

The less familiar parts of Lisp for beginners — summary D

I’ve written a few posts about features of the Lisp language that a newcomer arriving from C++ might not have encountered.  I’m going through them alphabetically, so here is a summary page of the functions beginning with the letter ‘D’:

declaim

declare

defconstant

define-compiler-macro

define-condition

define-method-combination

define-modify-macro

define-setf-expander

define-symbol-macro

defsetf

deftype

delete-package

deposit-field

do-symbols

dpb

dribble

dynamic-extent

 

The less-familiar parts of Lisp for beginners — dynamic-extent

Another obscure Lisp feature that the newcomer might not have encountered is dynamic-extent.  This is used as part of a declare operation.  It is purely a compiler hint, the Lisp implementation is free to ignore dynamic-extent entirely.

What a dynamic-extent declaration does is to indicate to the compiler that one or more symbols are entirely local to the form.  Their values do not return to the caller, they are not inserted into objects or lists, they live and die completely in the form where the dynamic-extent declaration appears.  They are local storage.  When this is known, the compiler has the option of stack-allocating the objects referenced by the symbols, rather than throwing them into the garbage-collected heap.  This can reduce computational overhead in the maintenance of the heap, and so speed up execution.

The less-familiar parts of Lisp for beginners — dribble

The next obscure command we’ll talk (briefly) about is dribble.  This is nothing more than an output capturing function that allows you to keep a record of your interaction with the Lisp environment.  You should usually not be using this.  You should be using SLIME under Emacs to do your Lisp development, and you can keep a much more helpful record using those tools.  I will note that dribble does not play well with SLIME, at least in my setup, which uses SBCL v1.1.14, Emacs 24.1.1, and SLIME from late January, 2013.