Re: Predicate for true lists

["Basil L. Contovounesios" <contovob@tcd.ie>]

[-- Attachment #1: Type: text/plain, Size: 1582 bytes --]

Paul Eggert <eggert@cs.ucla.edu> writes:

> Basil L. Contovounesios wrote:
>> OK, but my question still stands: do we use the term "proper" only to
>> name this function, but keep existing references to "true" lists in the
>> manual?  Or do we systematically switch from "true" to "proper"
>
> I suggest the latter. I've often heard them called "proper lists", and the
> phrase "true list" is less common in my experience.

I attach three patches (and a benchmark).  The first introduces the
function proper-list-length as per your suggestion in
https://lists.gnu.org/archive/html/emacs-devel/2018-06/msg00138.html
(please check whether I have properly attributed you, as I am unfamiliar
with the preferred way of doing this).

The second changes the Elisp manual to refer to "proper lists" instead
of "true lists".

The third moves the definition of zerop in lisp/subr.el from under the
'List functions' heading to under the 'Basic Lisp functions' heading.

Finally, here are the updated (byte-compiled) benchmark results:

    ‘proper-list-length’
      proper   (0.004452047000000001 0 0.0)
      dotted   (0.005584044999999999 0 0.0)
      circular (0.006193915          0 0.0)
    ‘format-proper-list-p’
      proper   (0.06397756299999999  0 0.0)
      dotted   (0.063610087          0 0.0)
      circular (0.09455345899999999  0 0.0)
    ‘ert--proper-list-p’
      proper   (0.29080201899999997  0 0.0)
      dotted   (0.290801063          0 0.0)
      circular (0.433813842          0 0.0)

WDYT?

Thanks,

-- 
Basil


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Add convenience function proper-list-length --]
[-- Type: text/x-diff, Size: 11681 bytes --]

From f42cb45f449dbb6c3d806398a128bc5914fdebab Mon Sep 17 00:00:00 2001
From: "Basil L. Contovounesios" <contovob@tcd.ie>
Date: Fri, 6 Jul 2018 00:41:11 +0300
Subject: [PATCH 1/3] Add convenience function proper-list-length

* lisp/subr.el (proper-list-length): New function.
Suggested by Paul Eggert <eggert@cs.ucla.edu> in
https://lists.gnu.org/archive/html/emacs-devel/2018-06/msg00138.html.
* doc/lispref/lists.texi (List Elements):
* etc/NEWS: Mention it.
* lisp/emacs-lisp/byte-opt.el (byte-optimize-if):
* lisp/emacs-lisp/cl-macs.el (cl--make-usage-args):
* lisp/org/ob-core.el (org-babel-insert-result): Use it.
* lisp/emacs-lisp/ert.el (ert--proper-list-p): Remove.
(ert--explain-equal-rec): Use proper-list-length instead.
* lisp/format.el (format-proper-list-p): Remove.
(format-annotate-single-property-change): Use proper-list-length
instead.
* test/lisp/emacs-lisp/ert-tests.el (ert-test-proper-list-p):
Move from here...
* test/lisp/subr-tests.el (subr-tests--proper-list-length):
...to here, mutatis mutandis.
---
 doc/lispref/lists.texi            | 17 +++++++++++++
 etc/NEWS                          |  6 +++++
 lisp/emacs-lisp/byte-opt.el       |  2 +-
 lisp/emacs-lisp/cl-macs.el        |  2 +-
 lisp/emacs-lisp/ert.el            | 22 ++++------------
 lisp/format.el                    | 12 ++-------
 lisp/org/ob-core.el               |  5 ++--
 lisp/subr.el                      |  6 +++++
 test/lisp/emacs-lisp/ert-tests.el | 42 -------------------------------
 test/lisp/subr-tests.el           | 18 +++++++++++++
 10 files changed, 58 insertions(+), 74 deletions(-)

diff --git a/doc/lispref/lists.texi b/doc/lispref/lists.texi
index 761750eb20..6850e9d74e 100644
--- a/doc/lispref/lists.texi
+++ b/doc/lispref/lists.texi
@@ -338,6 +338,23 @@ List Elements
 
 If @var{list} is not @code{nil} or a cons cell, @code{safe-length}
 returns 0.
+@end defun
+
+@defun proper-list-length object
+This function returns the length of @var{object} if it is a proper
+list, @code{nil} otherwise.  In addition to satisfying @code{listp}, a
+proper list is neither circular nor dotted.
+
+@example
+@group
+(proper-list-length '(a b c))
+    @result{} 3
+@end group
+@group
+(proper-list-length '(a b . c))
+    @result{} nil
+@end group
+@end example
 @end defun
 
   The most common way to compute the length of a list, when you are not
diff --git a/etc/NEWS b/etc/NEWS
index c92ee6e680..bd1b4509d6 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -689,6 +689,12 @@ manual for more details.
 \f
 * Lisp Changes in Emacs 27.1
 
++++
+** New function 'proper-list-length'.
+Given a proper list as argument, this function returns its length;
+otherwise, it returns nil.  This function can thus be used as a
+predicate for proper lists.
+
 ** define-minor-mode automatically documents the meaning of ARG
 
 +++
diff --git a/lisp/emacs-lisp/byte-opt.el b/lisp/emacs-lisp/byte-opt.el
index 3bc4c438d6..880bd6982d 100644
--- a/lisp/emacs-lisp/byte-opt.el
+++ b/lisp/emacs-lisp/byte-opt.el
@@ -983,7 +983,7 @@ byte-optimize-if
   (let ((clause (nth 1 form)))
     (cond ((and (eq (car-safe clause) 'progn)
                 ;; `clause' is a proper list.
-                (null (cdr (last clause))))
+                (proper-list-length clause))
            (if (null (cddr clause))
                ;; A trivial `progn'.
                (byte-optimize-if `(if ,(cadr clause) ,@(nthcdr 2 form)))
diff --git a/lisp/emacs-lisp/cl-macs.el b/lisp/emacs-lisp/cl-macs.el
index b50961adac..d95448afb8 100644
--- a/lisp/emacs-lisp/cl-macs.el
+++ b/lisp/emacs-lisp/cl-macs.el
@@ -498,7 +498,7 @@ cl--make-usage-args
       ;; `&aux' args aren't arguments, so let's just drop them from the
       ;; usage info.
       (setq arglist (cl-subseq arglist 0 aux))))
-  (if (cdr-safe (last arglist))         ;Not a proper list.
+  (if (not (proper-list-length arglist)) ; Not a proper list.
       (let* ((last (last arglist))
              (tail (cdr last)))
         (unwind-protect
diff --git a/lisp/emacs-lisp/ert.el b/lisp/emacs-lisp/ert.el
index 32bb367cdb..3b50225afb 100644
--- a/lisp/emacs-lisp/ert.el
+++ b/lisp/emacs-lisp/ert.el
@@ -472,18 +472,6 @@ ert--should-error-handle-error
 ;; buffer.  Perhaps explanations should be reported through `ert-info'
 ;; rather than as part of the condition.
 
-(defun ert--proper-list-p (x)
-  "Return non-nil if X is a proper list, nil otherwise."
-  (cl-loop
-   for firstp = t then nil
-   for fast = x then (cddr fast)
-   for slow = x then (cdr slow) do
-   (when (null fast) (cl-return t))
-   (when (not (consp fast)) (cl-return nil))
-   (when (null (cdr fast)) (cl-return t))
-   (when (not (consp (cdr fast))) (cl-return nil))
-   (when (and (not firstp) (eq fast slow)) (cl-return nil))))
-
 (defun ert--explain-format-atom (x)
   "Format the atom X for `ert--explain-equal'."
   (pcase x
@@ -498,12 +486,12 @@ ert--explain-equal-rec
       `(different-types ,a ,b)
     (pcase-exhaustive a
       ((pred consp)
-       (let ((a-proper-p (ert--proper-list-p a))
-             (b-proper-p (ert--proper-list-p b)))
-         (if (not (eql (not a-proper-p) (not b-proper-p)))
+       (let ((a-proper-p (proper-list-length a))
+             (b-proper-p (proper-list-length b)))
+         (if (not (eq (not a-proper-p) (not b-proper-p)))
              `(one-list-proper-one-improper ,a ,b)
            (if a-proper-p
-               (if (not (equal (length a) (length b)))
+               (if (/= (length a) (length b))
                    `(proper-lists-of-different-length ,(length a) ,(length b)
                                                       ,a ,b
                                                       first-mismatch-at
@@ -523,7 +511,7 @@ ert--explain-equal-rec
                      (cl-assert (equal a b) t)
                      nil))))))))
       ((pred arrayp)
-       (if (not (equal (length a) (length b)))
+       (if (/= (length a) (length b))
            `(arrays-of-different-length ,(length a) ,(length b)
                                         ,a ,b
                                         ,@(unless (char-table-p a)
diff --git a/lisp/format.el b/lisp/format.el
index 2f198e3eb7..bf535ca174 100644
--- a/lisp/format.el
+++ b/lisp/format.el
@@ -539,14 +539,6 @@ format-make-relatively-unique
 	(setq tail next)))
     (cons acopy bcopy)))
 
-(defun format-proper-list-p (list)
-  "Return t if LIST is a proper list.
-A proper list is a list ending with a nil cdr, not with an atom "
-  (when (listp list)
-    (while (consp list)
-      (setq list (cdr list)))
-    (null list)))
-
 (defun format-reorder (items order)
   "Arrange ITEMS to follow partial ORDER.
 Elements of ITEMS equal to elements of ORDER will be rearranged
@@ -1005,8 +997,8 @@ format-annotate-single-property-change
       ;; If either old or new is a list, have to treat both that way.
       (if (and (or (listp old) (listp new))
 	       (not (get prop 'format-list-atomic-p)))
-	  (if (or (not (format-proper-list-p old))
-		  (not (format-proper-list-p new)))
+          (if (not (and (proper-list-length old)
+                        (proper-list-length new)))
 	      (format-annotate-atomic-property-change prop-alist old new)
 	    (let* ((old (if (listp old) old (list old)))
 		   (new (if (listp new) new (list new)))
diff --git a/lisp/org/ob-core.el b/lisp/org/ob-core.el
index 5d5faaa6fd..09c43d8716 100644
--- a/lisp/org/ob-core.el
+++ b/lisp/org/ob-core.el
@@ -2310,10 +2310,9 @@ org-babel-insert-result
 		       (lambda (r)
 			 ;; Non-nil when result R can be turned into
 			 ;; a table.
-			 (and (listp r)
-			      (null (cdr (last r)))
+                         (and (proper-list-length r)
 			      (cl-every
-			       (lambda (e) (or (atom e) (null (cdr (last e)))))
+                               (lambda (e) (or (atom e) (proper-list-length e)))
 			       result)))))
 		  ;; insert results based on type
 		  (cond
diff --git a/lisp/subr.el b/lisp/subr.el
index ca184d8fc8..cb809a4ec7 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -555,6 +555,12 @@ zerop
   (declare (compiler-macro (lambda (_) `(= 0 ,number))))
   (= 0 number))
 
+(defun proper-list-length (object)
+  "Return OBJECT's length if it is a proper list, nil otherwise.
+A proper list is neither circular nor dotted (i.e., its last cdr
+is nil)."
+  (and (listp object) (ignore-errors (length object))))
+
 (defun delete-dups (list)
   "Destructively remove `equal' duplicates from LIST.
 Store the result in LIST and return it.  LIST must be a proper list.
diff --git a/test/lisp/emacs-lisp/ert-tests.el b/test/lisp/emacs-lisp/ert-tests.el
index e92b434274..cb957bd9fd 100644
--- a/test/lisp/emacs-lisp/ert-tests.el
+++ b/test/lisp/emacs-lisp/ert-tests.el
@@ -496,48 +496,6 @@ ert-test--which-file
 
 
 ;;; Tests for utility functions.
-(ert-deftest ert-test-proper-list-p ()
-  (should (ert--proper-list-p '()))
-  (should (ert--proper-list-p '(1)))
-  (should (ert--proper-list-p '(1 2)))
-  (should (ert--proper-list-p '(1 2 3)))
-  (should (ert--proper-list-p '(1 2 3 4)))
-  (should (not (ert--proper-list-p 'a)))
-  (should (not (ert--proper-list-p '(1 . a))))
-  (should (not (ert--proper-list-p '(1 2 . a))))
-  (should (not (ert--proper-list-p '(1 2 3 . a))))
-  (should (not (ert--proper-list-p '(1 2 3 4 . a))))
-  (let ((a (list 1)))
-    (setf (cdr (last a)) a)
-    (should (not (ert--proper-list-p a))))
-  (let ((a (list 1 2)))
-    (setf (cdr (last a)) a)
-    (should (not (ert--proper-list-p a))))
-  (let ((a (list 1 2 3)))
-    (setf (cdr (last a)) a)
-    (should (not (ert--proper-list-p a))))
-  (let ((a (list 1 2 3 4)))
-    (setf (cdr (last a)) a)
-    (should (not (ert--proper-list-p a))))
-  (let ((a (list 1 2)))
-    (setf (cdr (last a)) (cdr a))
-    (should (not (ert--proper-list-p a))))
-  (let ((a (list 1 2 3)))
-    (setf (cdr (last a)) (cdr a))
-    (should (not (ert--proper-list-p a))))
-  (let ((a (list 1 2 3 4)))
-    (setf (cdr (last a)) (cdr a))
-    (should (not (ert--proper-list-p a))))
-  (let ((a (list 1 2 3)))
-    (setf (cdr (last a)) (cddr a))
-    (should (not (ert--proper-list-p a))))
-  (let ((a (list 1 2 3 4)))
-    (setf (cdr (last a)) (cddr a))
-    (should (not (ert--proper-list-p a))))
-  (let ((a (list 1 2 3 4)))
-    (setf (cdr (last a)) (cl-cdddr a))
-    (should (not (ert--proper-list-p a)))))
-
 (ert-deftest ert-test-parse-keys-and-body ()
   (should (equal (ert--parse-keys-and-body '(foo)) '(nil (foo))))
   (should (equal (ert--parse-keys-and-body '(:bar foo)) '((:bar foo) nil)))
diff --git a/test/lisp/subr-tests.el b/test/lisp/subr-tests.el
index 52b61d9fb9..06e9a2b319 100644
--- a/test/lisp/subr-tests.el
+++ b/test/lisp/subr-tests.el
@@ -306,6 +306,24 @@ subr-test--frames-1
   (should (eq (string-to-char (symbol-name (gensym))) ?g))
   (should (eq (string-to-char (symbol-name (gensym "X"))) ?X)))
 
+(ert-deftest subr-tests--proper-list-length ()
+  "Test `proper-list-length' behavior."
+  (dotimes (length 4)
+    ;; Proper and dotted lists.
+    (let ((list (make-list length 0)))
+      (should (= (proper-list-length list) length))
+      (should (not (proper-list-length (nconc list 0)))))
+    ;; Circular lists.
+    (dotimes (n (1+ length))
+      (let ((circle (make-list (1+ length) 0)))
+        (should (not (proper-list-length (nconc circle (nthcdr n circle))))))))
+  ;; Atoms.
+  (should (not (proper-list-length 0)))
+  (should (not (proper-list-length "")))
+  (should (not (proper-list-length [])))
+  (should (not (proper-list-length (make-bool-vector 0 nil))))
+  (should (not (proper-list-length (make-symbol "a")))))
+
 (ert-deftest subr-tests--assq-delete-all ()
   "Test `assq-delete-all' behavior."
   (cl-flet ((new-list-fn
-- 
2.18.0


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: Refer to "proper lists" instead of "true lists" --]
[-- Type: text/x-diff, Size: 3385 bytes --]

From a77c216ff8777843667682721acbf3078f9edeab Mon Sep 17 00:00:00 2001
From: "Basil L. Contovounesios" <contovob@tcd.ie>
Date: Fri, 6 Jul 2018 00:47:55 +0300
Subject: [PATCH 2/3] Refer to "proper lists" instead of "true lists"

* doc/lispref/lists.texi (Cons Cells, Building Lists):
* doc/lispref/sequences.texi (Vector Functions): Do it.

Suggested in the following emacs-devel messages:
https://lists.gnu.org/archive/html/emacs-devel/2018-06/msg00112.html
https://lists.gnu.org/archive/html/emacs-devel/2018-06/msg00138.html
---
 doc/lispref/lists.texi     | 13 +++++++------
 doc/lispref/sequences.texi |  2 +-
 2 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/doc/lispref/lists.texi b/doc/lispref/lists.texi
index 6850e9d74e..cd2ff8d2f7 100644
--- a/doc/lispref/lists.texi
+++ b/doc/lispref/lists.texi
@@ -50,16 +50,17 @@ Cons Cells
 slots have similar properties).  Hence, the @sc{cdr} slot of each cons
 cell in a list refers to the following cons cell.
 
+@cindex proper list
 @cindex true list
   Also by convention, the @sc{cdr} of the last cons cell in a list is
 @code{nil}.  We call such a @code{nil}-terminated structure a
-@dfn{true list}.  In Emacs Lisp, the symbol @code{nil} is both a
+@dfn{proper list}.  In Emacs Lisp, the symbol @code{nil} is both a
 symbol and a list with no elements.  For convenience, the symbol
 @code{nil} is considered to have @code{nil} as its @sc{cdr} (and also
 as its @sc{car}).
 
-  Hence, the @sc{cdr} of a true list is always a true list.  The
-@sc{cdr} of a nonempty true list is a true list containing all the
+  Hence, the @sc{cdr} of a proper list is always a proper list.  The
+@sc{cdr} of a nonempty proper list is a proper list containing all the
 elements except the first.
 
 @cindex dotted list
@@ -71,10 +72,10 @@ Cons Cells
 @sc{cdr} could point to one of the previous cons cells in the list.
 We call that structure a @dfn{circular list}.
 
-  For some purposes, it does not matter whether a list is true,
+  For some purposes, it does not matter whether a list is proper,
 circular or dotted.  If a program doesn't look far enough down the
 list to see the @sc{cdr} of the final cons cell, it won't care.
-However, some functions that operate on lists demand true lists and
+However, some functions that operate on lists demand proper lists and
 signal errors if given a dotted list.  Most functions that try to find
 the end of a list enter infinite loops if given a circular list.
 
@@ -539,7 +540,7 @@ Building Lists
 is itself a list, then its elements become in effect elements of the
 result list.  If the final element is not a list, the result is a
 dotted list since its final @sc{cdr} is not @code{nil} as required
-in a true list.
+in a proper list.
 @end defun
 
   Here is an example of using @code{append}:
diff --git a/doc/lispref/sequences.texi b/doc/lispref/sequences.texi
index 566ba8de18..8eb877882c 100644
--- a/doc/lispref/sequences.texi
+++ b/doc/lispref/sequences.texi
@@ -1353,7 +1353,7 @@ Vector Functions
 @defun vconcat &rest sequences
 @cindex copying vectors
 This function returns a new vector containing all the elements of
-@var{sequences}.  The arguments @var{sequences} may be true lists,
+@var{sequences}.  The arguments @var{sequences} may be proper lists,
 vectors, strings or bool-vectors.  If no @var{sequences} are given,
 the empty vector is returned.
 
-- 
2.18.0


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #4: Rearrange definition of zerop in subr.el --]
[-- Type: text/x-diff, Size: 1424 bytes --]

From 772881e0c18f68c7651fabd637948cd5a87e7286 Mon Sep 17 00:00:00 2001
From: "Basil L. Contovounesios" <contovob@tcd.ie>
Date: Fri, 6 Jul 2018 00:56:45 +0300
Subject: [PATCH 3/3] ; Rearrange definition of zerop in subr.el

* lisp/subr.el (zerop): Move from under 'List functions' heading to
under 'Basic Lisp functions' heading.
---
 lisp/subr.el | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

diff --git a/lisp/subr.el b/lisp/subr.el
index cb809a4ec7..15a5d7b9e4 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -359,6 +359,13 @@ apply-partially
   (lambda (&rest args2)
     (apply fun (append args args2))))
 
+(defun zerop (number)
+  "Return t if NUMBER is zero."
+  ;; Used to be in C, but it's pointless since (= 0 n) is faster anyway because
+  ;; = has a byte-code.
+  (declare (compiler-macro (lambda (_) `(= 0 ,number))))
+  (= 0 number))
+
 \f
 ;;;; List functions.
 
@@ -548,13 +555,6 @@ nbutlast
 	   (if (> n 0) (setcdr (nthcdr (- (1- m) n) list) nil))
 	   list))))
 
-(defun zerop (number)
-  "Return t if NUMBER is zero."
-  ;; Used to be in C, but it's pointless since (= 0 n) is faster anyway because
-  ;; = has a byte-code.
-  (declare (compiler-macro (lambda (_) `(= 0 ,number))))
-  (= 0 number))
-
 (defun proper-list-length (object)
   "Return OBJECT's length if it is a proper list, nil otherwise.
 A proper list is neither circular nor dotted (i.e., its last cdr
-- 
2.18.0


[-- Attachment #5: Benchmark for proper-list-length --]
[-- Type: application/emacs-lisp, Size: 936 bytes --]