Rationalising c[ad]\{2,5\}r.

Rationalising c[ad]\{2,5\}r.

[Alan Mackenzie]

Hello, Emacs.

Right at the moment, our functions caar, cadr, cdar, cddr, caaar, caadr,
....., cddddr are in a mess:

1. caar,  cadr, cdar, and cddr are defined in subr.el;
2. c[ad]\{3,4\}r are actually called cl-caaar, etc;
3. cl-c[ad]\{3,4\}r are defined in cl-lib.el;
4. The aliases for the names without the cl- are defined in  cl.el;
5. c[ad]\{3,4\}r each contain the form
    (declare (compiler-macro cl--compiler-macro-cXXr)
  , whereas caar, cadr, cdar, cddr don't.  At the moment, I don't know
  whether this is a bug, or whether the two cases are just handled
  differently;
6. All the defuns are written out individually, making it hard to verify
  that they are all correct, and making it very hard to extend to 5 or
  more [ad]s, and also taking up a lot of lines of code spread over
  several files.el.

I propose the following solution: all these defuns should be in subr.el,
the canonical names will be caaadr etc., and there will be compatibility
aliases for cl-caaadr etc..  All these functions and aliases will be
generated by macros, thus saving source code lines, making them more
reliable, and enabling extension to the scheme with a trivial amount of
effort.

At the moment, the number of source file lines occupied by these
functions (including blank lines) is:
subr.el:    16
cl-lib.el: 120
cl.el:      24
           ---
TOTAL      160

In my proposed change, the macros and macro invocations occupy a mere 88
lines, and even extends the scheme to 5-[ad] defuns (like cadadar).
(Yes, I do have a use for caadadr, caddadr, and cdddadr in fix-re.el.)

Here is the code I propose to put into subr.el in place of the
declarations of caar etc.:

*************************************************************************

;; Macros to generate caar ... cdddddr in subr.el.
(eval-and-compile
  (defun gen-cXXr--rawname (n bits)
    "Generate and return a string like \"adad\" corresponding to N.
BITS is the number of a's and d's.
The \"corresponding\" means each bit of N is converted to an \"a\" (for zero)
or a \"d\" (for one)."
    (let ((name (make-string bits ?a))
	  (mask (lsh 1 (1- bits)))
	  (elt 0))
      (while (< elt bits)
	(if (/= (logand n mask) 0)
	    (aset name elt ?d))
	(setq elt (1+ elt)
	      mask (lsh mask -1)))
      name))

  (defun gen-cXXr--doc-string (raw)
    "Generate a doc string for a name like \"cadadr\".
RAW is the \"inner\" part of the name, e.g. \"adad\"."
    (concat
     "Return the `c"
     (mapconcat (lambda (ad) (char-to-string ad)) raw "r' of the `c")
     "r' of X."))

  (defun gen-cXXr--code (raw bits)
    "Generate the code for a defun like \"cadadr\" in terms of `car' and `cdr'.
RAW is the \"inner\" part of the name, e.g. \"adad\", BITS is the
length of RAW."
    (let ((code 'x)
	  (elt bits))
      (while (> elt 0)
	(setq elt (1- elt))
	(setq code (list (if (eq (aref raw elt) ?a) 'car 'cdr) code)))
      code))

  (defun gen-cXXr--defun (n bits compiler-macro)
    "Generate a `defun' for a symbol like \"cadadr\".
N is a number representing the \"inner\" part of the
symbol (e.g. binary 0101 for cadadr), BITS is the length of that
part of the symbol (e.g. 4).  If COMPILER-MACRO is non-nil,
include a `compiler-macro' declaration in the defun."
    (let ((raw (gen-cXXr--rawname n bits)))
      `(defun ,(intern (concat "c" raw "r")) (x)
	 ,(gen-cXXr--doc-string raw)
	 ,@(when compiler-macro
	     '((declare (compiler-macro cl--compiler-macro-cXXr))))
	 ,(gen-cXXr--code raw bits))))

  (defun gen-cXXr--make-seq (bits)
    "Generate a list of all integers with BITS bits, in ascending order."
    (let ((x (lsh 1 bits))
	  acc)
      (while (> x 0)
	(setq x (1- x))
	(push x acc))
      acc)))

(defmacro gen-cXXr-all (bits compiler-macro)
  "Generate defuns for all `c[ad]+r's with BITS a's and d's.
If COMPILER-MACRO is non-nil, include `compiler-macro'
declarations in the defuns."
  (let ((seq (gen-cXXr--make-seq bits)))
     `(progn
	,@(mapcar
	   (lambda (n)
	     (gen-cXXr--defun n bits compiler-macro))
	   seq))))

(defmacro gen-cXXr-all-cl-aliases (bits)
  "Generate cl- aliases for all defuns `c[ad]+r' with BITS a's and d's."
  (let ((seq (gen-cXXr--make-seq bits))
	)
    `(progn
       ,@(mapcar
	  (lambda (n)
	    (let ((raw (gen-cXXr--rawname n bits)))
	      `(defalias ',(intern (concat "cl-c" raw "r"))
		 ',(intern (concat "c" raw "r")))))
	  seq))))

(gen-cXXr-all 2 nil)
(gen-cXXr-all 3 t)
(gen-cXXr-all-cl-aliases 3)
(gen-cXXr-all 4 t)
(gen-cXXr-all-cl-aliases 4)
(gen-cXXr-all 5 t)
*************************************************************************

Comments?

-- 
Alan Mackenzie (Nuremberg, Germany).

RE: Rationalising c[ad]\{2,5\}r.

[Drew Adams]

> 1. caar,  cadr, cdar, and cddr are defined in subr.el;
> 2. c[ad]\{3,4\}r are actually called cl-caaar, etc;

Gag. Why is that?

> 3. cl-c[ad]\{3,4\}r are defined in cl-lib.el;

Why is that?
What's next, cl-setq?

> 4. The aliases for the names without the cl- are defined in  cl.el;
> 5. c[ad]\{3,4\}r each contain the form
>     (declare (compiler-macro cl--compiler-macro-cXXr)
>   , whereas caar, cadr, cdar, cddr don't.  At the moment, I don't know
>   whether this is a bug, or whether the two cases are just handled
>   differently;
> 6. All the defuns are written out individually, making it hard to verify
>   that they are all correct, and making it very hard to extend to 5 or
>   more [ad]s, and also taking up a lot of lines of code spread over
>   several files.el.
> 
> I propose the following solution: all these defuns should be in subr.el,
> the canonical names will be caaadr etc., 

Yes.  How about the _only_ names, instead?

> and there will be compatibility aliases for cl-caaadr etc..  

Why? Why is that needed?

All of these things pre-date Common Lisp.
They are _Lisp_ names, from Day One.

Has this slick cl-* paint job perhaps gotten out of hand?

Re: Rationalising c[ad]\{2,5\}r.

[Thien-Thi Nguyen]

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

() Alan Mackenzie <acm@muc.de>
() Wed, 11 Mar 2015 21:43:24 +0000

   Comments?

Bravo!

     (defun gen-cXXr--make-seq (bits)
       "Generate a list of all integers with BITS bits, in ascending order."
       (let ((x (lsh 1 bits))
             acc)
         (while (> x 0)
           (setq x (1- x))
           (push x acc))
         acc))

You can save some lines by using ‘number-sequence’:

 (defun gen-cXXr--make-seq (bits)
   "Generate a list of all integers with BITS bits, in ascending order."
   (number-sequence 0 (1- (lsh 1 bits))))

I wonder (idly) if the number of ‘(number-sequence 0 (1- ...))’
in the codebase justifies adding ‘iota’.  Hmmm.

-- 
Thien-Thi Nguyen
   GPG key: 4C807502
   (if you're human and you know it)
      read my lisp: (responsep (questions 'technical)
                               (not (via 'mailing-list)))
                     => nil

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: Rationalising c[ad]\{2,5\}r.

[Artur Malabarba]

>> 1. caar,  cadr, cdar, and cddr are defined in subr.el;
>> 2. c[ad]\{3,4\}r are actually called cl-caaar, etc;
>
> Gag. Why is that?

My guess is that these were initially defined in `cl.el' (which, if
that's the case, I agree was a mistake), and afterwards all cl
functions were renamed to `cl-' prefixes by cl-lib (in the process of
abolishing `cl.el').

>> and there will be compatibility aliases for cl-caaadr etc..
>
> Why? Why is that needed?

To not make it harder for developers to support Emacs 24.X

> Has this slick cl-* paint job perhaps gotten out of hand?

Well, it's not exactly getting worse. It's the same it's always been, isn't it?

Re: Rationalising c[ad]\{2,5\}r.

[Alan Mackenzie]

Hi, Thien-Thi.

On Wed, Mar 11, 2015 at 11:15:53PM +0100, Thien-Thi Nguyen wrote:
> () Alan Mackenzie <acm@muc.de>
> () Wed, 11 Mar 2015 21:43:24 +0000

>    Comments?

> Bravo!

>      (defun gen-cXXr--make-seq (bits)
>        "Generate a list of all integers with BITS bits, in ascending order."
>        (let ((x (lsh 1 bits))
>              acc)
>          (while (> x 0)
>            (setq x (1- x))
>            (push x acc))
>          acc))

> You can save some lines by using ‘number-sequence’:

Thanks, I didn't know about `number-sequence'.  I'll start using it.
Just one thing, though, since `number-sequence' is also defined in
subr.el, I'd have to wrap it in `eval-and-compile' to be able to use it
in my macros.

>  (defun gen-cXXr--make-seq (bits)
>    "Generate a list of all integers with BITS bits, in ascending order."
>    (number-sequence 0 (1- (lsh 1 bits))))

That's short enough that I might not really need the function
`gen-cXXr--make-seq'.

> I wonder (idly) if the number of ‘(number-sequence 0 (1- ...))’
> in the codebase justifies adding ‘iota’.  Hmmm.

`iota'?  A Greek letter, or a tiny amount.  I'm afraid you've lost me.
;-)

> -- 
> Thien-Thi Nguyen
>    GPG key: 4C807502
>    (if you're human and you know it)
>       read my lisp: (responsep (questions 'technical)
>                                (not (via 'mailing-list)))
>                      => nil

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: Rationalising c[ad]\{2,5\}r.

[Thien-Thi Nguyen]

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

() Alan Mackenzie <acm@muc.de>
() Wed, 11 Mar 2015 23:00:54 +0000

   Thanks, I didn't know about `number-sequence'.  I'll start
   using it.  Just one thing, though, since `number-sequence' is
   also defined in subr.el, I'd have to wrap it in
   `eval-and-compile' to be able to use it in my macros.

Hmm.

   >  (defun gen-cXXr--make-seq (bits)
   >    "Generate a list of all integers with BITS bits, in ascending order."
   >    (number-sequence 0 (1- (lsh 1 bits))))

   That's short enough that I might not really need the function
   `gen-cXXr--make-seq'.

Less is more!

   `iota'?  A Greek letter, or a tiny amount.  I'm afraid you've
   lost me.  ;-)

I first heard of ‘iota’ in Scheme:

 (iota 8) => (0 1 2 3 4 5 6 7)

which was inspired by APL (i believe):

 https://en.wikipedia.org/wiki/APL_(programming_language)

although the APL ‘iota’ (written "ι" (U+03b9)) produces
a 1-based sequence instead of 0-based.  I wonder what the
Common Lisp idiom for this functionality would be...

-- 
Thien-Thi Nguyen
   GPG key: 4C807502
   (if you're human and you know it)
      read my lisp: (responsep (questions 'technical)
                               (not (via 'mailing-list)))
                     => nil

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: Rationalising c[ad]\{2,5\}r.

[Artur Malabarba]

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

> Just one thing, though, since `number-sequence' is also defined in
> subr.el, I'd have to wrap it in `eval-and-compile' to be able to use it
> in my macros.

I don't understand. Why is that?

[-- Attachment #2: Type: text/html, Size: 265 bytes --]

Re: Rationalising c[ad]\{2,5\}r.

[Samuel W. Flint]

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

Thien-Thi Nguyen <ttn@gnu.org> writes:

> I first heard of ‘iota’ in Scheme:
>
>  (iota 8) => (0 1 2 3 4 5 6 7)
>
> which was inspired by APL (i believe):
>
>  https://en.wikipedia.org/wiki/APL_(programming_language)
>
> although the APL ‘iota’ (written "ι" (U+03b9)) produces
> a 1-based sequence instead of 0-based.  I wonder what the
> Common Lisp idiom for this functionality would be...

(defun ι (n)
         (loop for i from 0 to n collecting i))

At least that's what I've always seen.  I guess you could to something
like the following if you don't want to use LOOP:

(defun ι (n)
         (let ((list '()))
           (do ((i 0 (1+ i)))
               ((= i n) t)
             (push i list))
           (reverse list)))

Sam

--
Samuel W. Flint
swflint@flintfam.org                  (402) 517-8468      <XMPP>
freenode: swflint
http://flintfam.org/~swflint
4096R/266596F4
      (9477 D23E 389E 40C5 2F10  DE19 68E5 318E 2665 96F4)
"The most dangerous phrase in the language is, 'We've always done it
this way'."  -- Grace Hopper

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 818 bytes --]

RE: Rationalising c[ad]\{2,5\}r.

[Drew Adams]

> >> 1. caar,  cadr, cdar, and cddr are defined in subr.el;
> >> 2. c[ad]\{3,4\}r are actually called cl-caaar, etc;
> >
> > Gag. Why is that?
> 
> My guess is that these were initially defined in `cl.el' (which,
> if that's the case, I agree was a mistake),

It doesn't much matter where they were defined.  They are basic
Lisp.  Who cares where `setq' is defined, in terms of modularity
or namespaces?

> and afterwards all cl functions were renamed to `cl-' prefixes by
> cl-lib (in the process of abolishing `cl.el').

That was an even bigger mistake - doing that systematically, I mean.
`cl-car', `cl-cdr',...  Sheesh - what silliness.

Also: bug #20056: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=20056

`car' is Lisp.  It is not special to Common Lisp.
`letf' is Emacs Lisp.  It is not Common Lisp.

Neither should get the `cl-' prefix.  Neither is emulating
Common Lisp, and neither is confusable with something else
already existing in Emacs Lisp.

> >> and there will be compatibility aliases for cl-caaadr etc..
> >
> > Why? Why is that needed?
> 
> To not make it harder for developers to support Emacs 24.X

Well, if you mean keeping `caaadr', then yes.  It's `cl-caaadr'
that has no raison d'etre.  Keep `caaadr'; toss `cl-caaadr'.
No need for any aliasing then to make things easier for
"developers to support Emacs 24.X".

Putting it like you did is trying to make a virtue out of
necessity (or a purse out of a sow's ear, if you prefer).
Given the existence of `cl-caaadr', yes, of course we would
then need to alias `caaadr' to it.  Get rid of `cl-caaadr',
and no, no aliasing is needed.

> > Has this slick cl-* paint job perhaps gotten out of hand?
> 
> Well, it's not exactly getting worse. It's the same it's always
> been, isn't it?

See above.  Yes, this kind of thing is worse, IMHO.  And no,
prefix `cl-' has not always been applied to such things.

Re: Rationalising c[ad]\{2,5\}r.

[Stephen J. Turnbull]

Artur Malabarba writes:

 > > Has this slick cl-* paint job perhaps gotten out of hand?
 > 
 > Well, it's not exactly getting worse. It's the same it's always
 > been, isn't it?

No, it is in no way the same as it has always been.  Originally cl.el
and cl-macs.el simply added the Common Lisp functionality (often
incomplete, sometimes arguably buggy) to the top-level pseudo-
namespace.  RMS always vetoed adding these facilities to the core
language, and cl-lib has been around for a few years, I guess, but
this business of moving everything out of the core pseudo-namespace
and in to the "cl-" pseudo-namespace is only a year or so old.

I assume the grand plan is something like "keep the core pseudo-
namespace as small as possible to make it easier to move to a Scheme
core (presumably Guile) by 2050".  The thing is, Emacs Lisp is a
Lisp2, and Scheme is a Lisp1.  Unless you're going to rewrite all of
lisp/ and ELPA in Scheme -- requiring a completely different style!
which *will* break people's heads -- you're going to have an emulation,
and the killer apps (cc-mode, gnus, AUCTeX, and org for starters) that
attract people to Emacs development will stay written in a Lisp2 for a
long (long long long ...) time.

FYI, XEmacs has placed its bet.  Although our senior Lisp implementor
is the first listed editor of R6RS, we're continuing to implement
Common Lisp features (most recently labels and multiple values) in the
C core.  (Not that we expect common use in mainstream Emacs.  The
point is that we don't think we're screwing ourselves by hitching our
wagon to the Lisp2 horse.)

Re: Rationalising c[ad]\{2,5\}r.

[Alan Mackenzie]

Hello, Artur.

On Wed, Mar 11, 2015 at 09:52:07PM -0300, Artur Malabarba wrote:
> > Just one thing, though, since `number-sequence' is also defined in
> > subr.el, I'd have to wrap it in `eval-and-compile' to be able to use it
> > in my macros.

> I don't understand. Why is that?

Normally, during byte compilation, the newly compiled defuns and defvars
are simply written to the output file.  They cannot be executed/accessed
until that file.elc is later loaded.

This would be a problem for my macro `gen-cXXr-all', which wants to
_run_ `number-sequence' whilst subr.el is being compiled.  The solution
is `eval-and-compile', which instructs the byte compiler both to write
the compiled `number-sequence' to the output file and to evaluate it, so
that it is available for use later during the compilation.

I don't think this is particularly well described in the Elisp manual,
particularly with the sentence "Most uses of `eval-and-compile' are
fairly sophisticated.", which does sound a little patronising.

-- 
Alan Mackenzie (Nuremberg, Germany).

RE: Rationalising c[ad]\{2,5\}r.

[Artur Malabarba]

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

> It doesn't much matter where they were defined.  They are basic
> Lisp.  Who cares where `setq' is defined, in terms of modularity
> or namespaces?
> (...)
> That was an even bigger mistake - doing that systematically, I mean.
> `cl-car', `cl-cdr',...  Sheesh - what silliness.
>
> `car' is Lisp.  It is not special to Common Lisp.
> `letf' is Emacs Lisp.  It is not Common Lisp.
>
> Neither should get the `cl-' prefix.  Neither is emulating
> Common Lisp, and neither is confusable with something else
> already existing in Emacs Lisp.

You confuse me with someone who cares about this package. I was just trying
to answer your questions.

As long as I can develop packages for 24.1 without having to jump through
hoops, I don't care at all where all this functions are defined.

> > >> and there will be compatibility aliases for cl-caaadr etc..
> > >
> > > Why? Why is that needed?
> >
> > To not make it harder for developers to support Emacs 24.X
>
> Well, if you mean keeping `caaadr', then yes.  It's `cl-caaadr'
> that has no raison d'etre.  Keep `caaadr'; toss `cl-caaadr'.

Has, `caaadr' always existed (since 24.1) without explicitly `require'ing
the `cl' package?

If the answer is yes, then I'm fine with removing the prefixed alias.

> Putting it like you did is trying to make a virtue out of
> necessity (or a purse out of a sow's ear, if you prefer).

Again, forgive me if I misexpressed myself as someone who cares. I wasn't
defending the package. I just want to ensure we don't break existing code
(or, if we do, at least ensure it's not a pain to unbreak).

[-- Attachment #2: Type: text/html, Size: 2032 bytes --]

Re: Rationalising c[ad]\{2,5\}r.

[Artur Malabarba]

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

On Mar 12, 2015 4:34 AM, "Stephen J. Turnbull" <stephen@xemacs.org> wrote:
>
> Artur Malabarba writes:
>
>  > > Has this slick cl-* paint job perhaps gotten out of hand?
>  >
>  > Well, it's not exactly getting worse. It's the same it's always
>  > been, isn't it?
>
> No, it is in no way the same as it has always been.  Originally cl.el
> and cl-macs.el simply added the Common Lisp functionality (often
> incomplete, sometimes arguably buggy) to the top-level pseudo-
> namespace.  RMS always vetoed adding these facilities to the core
> language, and cl-lib has been around for a few years, I guess, but
> this business of moving everything out of the core pseudo-namespace
> and in to the "cl-" pseudo-namespace is only a year or so old.

Yes, I was referring to cl-lib, not cl. I don't think it's gotten any worse
since its inception (though I'm not claiming to know all the history).

[-- Attachment #2: Type: text/html, Size: 1167 bytes --]

Re: Rationalising c[ad]\{2,5\}r.

[Artur Malabarba]

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

Makes sense, thanks for the explanation.
On Mar 12, 2015 8:56 AM, "Alan Mackenzie" <acm@muc.de> wrote:

> Hello, Artur.
>
> On Wed, Mar 11, 2015 at 09:52:07PM -0300, Artur Malabarba wrote:
> > > Just one thing, though, since `number-sequence' is also defined in
> > > subr.el, I'd have to wrap it in `eval-and-compile' to be able to use it
> > > in my macros.
>
> > I don't understand. Why is that?
>
> Normally, during byte compilation, the newly compiled defuns and defvars
> are simply written to the output file.  They cannot be executed/accessed
> until that file.elc is later loaded.
>
> This would be a problem for my macro `gen-cXXr-all', which wants to
> _run_ `number-sequence' whilst subr.el is being compiled.  The solution
> is `eval-and-compile', which instructs the byte compiler both to write
> the compiled `number-sequence' to the output file and to evaluate it, so
> that it is available for use later during the compilation.
>
> I don't think this is particularly well described in the Elisp manual,
> particularly with the sentence "Most uses of `eval-and-compile' are
> fairly sophisticated.", which does sound a little patronising.
>
> --
> Alan Mackenzie (Nuremberg, Germany).
>

[-- Attachment #2: Type: text/html, Size: 1590 bytes --]

Re: Rationalising c[ad]\{2,5\}r.

[Alan Mackenzie]

Hello, Drew.

On Wed, Mar 11, 2015 at 03:00:50PM -0700, Drew Adams wrote:
> > 1. caar,  cadr, cdar, and cddr are defined in subr.el;
> > 2. c[ad]\{3,4\}r are actually called cl-caaar, etc;

> Gag. Why is that?

Lack of clear thinking, conflicting design goals, ..., who knows?

> > 3. cl-c[ad]\{3,4\}r are defined in cl-lib.el;

> Why is that?
> What's next, cl-setq?

:-)  Let's hope not.

[ .... ]

> > I propose the following solution: all these defuns should be in subr.el,
> > the canonical names will be caaadr etc., 

> Yes.  How about the _only_ names, instead?

> > and there will be compatibility aliases for cl-caaadr etc..  

> Why? Why is that needed?

Because there are lots of uses of cl-c[ad]\{3,4\}r in the field.  There
are currently 56 uses in the Emacs sources, which we could easily fix,
but there will be an unknown, possibly high, number in packages and code
we don't control.  It would be ill-mannered simply to remove these names.
They should be marked as obsolete, perhaps.

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: Rationalising c[ad]\{2,5\}r.

[Stefan Monnier]

> I propose the following solution: all these defuns should be in subr.el,

Emacs lived with just car/cdr for many many years.  Then someone saw
that (car (cdr ...)) was fairly common in Elisp and decided that it was
worth moving cl.el's cadr/caar/cadr/cddr to subr.el (tho only those,
keeping the longer ones in cl.el).

While there are a few uses of cXXr with more than 2 Xs, these aren't
very common, and I personally find them to be not terribly readable
(basically, car/cdr feel a bit like assembly-level programming to me,
since they access structure elements without giving them a name).

Additionally, these are usually somewhat inefficient (because some of
the inner car/cdr could/should be shared between different calls, but
our byte-compiler doesn't know how to do
common-subexpression-elimination, so it's better to spell them out as
something like (cadr (cadr x)) and then to manually move the inner cadr
to a let-binding to share it between various cXXr calls).

So while I'm not dead-set against adding many more cXXXr to subr.el, I'm
not in favor of it, since I think it encourages a poorly-readable and
inefficient programming style.

This said, I am in favor of moving cl--compiler-macro-cXXr to subr.el and
making use of it (in place of inlining) for cadr/caar/cddr/cdar.
[ It's my fault if it's not done that way yet, but that was just
  a mistake on my part.  ]

> Just one thing, though, since `number-sequence' is also defined in
> subr.el, I'd have to wrap it in `eval-and-compile' to be able to use it
> in my macros.

I'm not sure it's necessary, because subr.el is preloaded (and preloaded
early, i.e. before eager macro-expansion is enabled).


        Stefan

RE: Rationalising c[ad]\{2,5\}r.

[Drew Adams]

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

> > >> and there will be compatibility aliases for cl-caaadr etc..
> > > Why? Why is that needed?
> > To not make it harder for developers to support Emacs 24.X
>
> Well, if you mean keeping `caaadr', then yes.  It's `cl-caaadr'
> that has no raison d'etre.  Keep `caaadr'; toss `cl-caaadr'.

Has, `caaadr' always existed (since 24.1) without explicitly `require'ing the `cl' package?

Yes. Just require `cl-macs.el'. Or require `cl.el' at byte-compile time.
These are macros.

If the answer is yes, then I'm fine with removing the prefixed alias. 

[-- Attachment #2: Type: text/html, Size: 2738 bytes --]

RE: Rationalising c[ad]\{2,5\}r.

[Drew Adams]

> > > and there will be compatibility aliases for cl-caaadr etc..
> 
> > Why? Why is that needed?
> 
> Because there are lots of uses of cl-c[ad]\{3,4\}r in the field.  There
> are currently 56 uses in the Emacs sources, which we could easily fix,
> but there will be an unknown, possibly high, number in packages and code
> we don't control.  It would be ill-mannered simply to remove these names.
> They should be marked as obsolete, perhaps.

See my reply to Artur/Bruce.  I meant only that the `cl-' versions are
not needed.  We should definitely not remove the c[ad]\{3,4\}r.

If there are already "lots of" cl-c[ad]\{3,4\}r in the field, then
that would be too bad.  But I doubt that that is the case.

Occurrences of such barbarities would, I expect, represent only the
exceptional overzealous, early-adopter, conversion of *existing*
c[ad]\{3,4\}r.  The 56 uses in the Emacs sources are in fact a case
in point.  Who would write (cl-cadddr (cl-cdar x)) in new code?
 
And even if it is case that there are "lots of" such occurrences out
there, we should just apologize for our recent-past silliness, redefine
the cl-c[ad]\{3,4\}r as temporary (only) aliases for c[ad]\{3,4\}r,
deprecate those aliases, and remove them as soon as possible thereafter.

I would be quite surprised if there are really a lot of cl-c[ad]\{3,4\}r
out there.  But there are no doubt lots of c[ad]\{3,4\}r out there.

Re: Rationalising c[ad]\{2,5\}r.

[Alan Mackenzie]

Hello, Stefan.

On Thu, Mar 12, 2015 at 09:53:13AM -0400, Stefan Monnier wrote:
> > I propose the following solution: all these defuns should be in subr.el,

> Emacs lived with just car/cdr for many many years.  Then someone saw
> that (car (cdr ...)) was fairly common in Elisp and decided that it was
> worth moving cl.el's cadr/caar/cadr/cddr to subr.el (tho only those,
> keeping the longer ones in cl.el).

Yes.  That causes problems (even if not serious ones) because the longer
ones are loaded only with cl.

> While there are a few uses of cXXr with more than 2 Xs, these aren't
> very common, ....

They're not that rare.  I count 304 currently in Emacs, including
eudc-cdaar (twice), in 78 files.  That's a lot of files that need to
require cl.

> .... and I personally find them to be not terribly readable (basically,
> car/cdr feel a bit like assembly-level programming to me, since they
> access structure elements without giving them a name).

They may not be very readable, but they're more readable as "(cadar ..)"
than as "(car (cdr (car ..)))".

> Additionally, these are usually somewhat inefficient (because some of
> the inner car/cdr could/should be shared between different calls, but
> our byte-compiler doesn't know how to do
> common-subexpression-elimination, so it's better to spell them out as
> something like (cadr (cadr x)) and then to manually move the inner cadr
> to a let-binding to share it between various cXXr calls).

I think the difference in execution time would tend towards zero.  Each
`car' or `cdr' is but a single compiled instruction, and let-binding
variables, then accessing them, must be quite slow by comparison.

> So while I'm not dead-set against adding many more cXXXr to subr.el, I'm
> not in favor of it, since I think it encourages a poorly-readable and
> inefficient programming style.

OK.  How about us sticking with the current maximum of four?

> This said, I am in favor of moving cl--compiler-macro-cXXr to subr.el and
> making use of it (in place of inlining) for cadr/caar/cddr/cdar.
> [ It's my fault if it's not done that way yet, but that was just
>   a mistake on my part.  ]

I've incorporated that into the current version of my change.

> > Just one thing, though, since `number-sequence' is also defined in
> > subr.el, I'd have to wrap it in `eval-and-compile' to be able to use it
> > in my macros.

> I'm not sure it's necessary, because subr.el is preloaded (and preloaded
> early, i.e. before eager macro-expansion is enabled).

I'll try making my changes to subr.el then bootstrapping.

>         Stefan

-- 
Alan Mackenzie (Nuremberg, Germany).

RE: Rationalising c[ad]\{2,5\}r.

[Drew Adams]

> How about us sticking with the current maximum of four?

Four is all that Common Lisp defines, anyway.

http://www.lispworks.com/documentation/HyperSpec/Body/f_car_c.htm

Re: Rationalising c[ad]\{2,5\}r.

[Stefan Monnier]

> They're not that rare.  I count 304 currently in Emacs, including
> eudc-cdaar (twice), in 78 files.  That's a lot of files that need to
> require cl.

Most likely 99.9% of these files also use other CL facilities, so that
wouldn't save them from requiring CL.  And in any case, using CL
facilities is perfectly fine (provided you do it via cl-lib rather than
cl.el).

> let-binding variables, then accessing them, must be quite slow
> by comparison.

Via dynamically scoped vars, that's indeed the case.
But with lexical-binding not anymore.


        Stefan

Re: Rationalising c[ad]\{2,5\}r.

[Alan Mackenzie]

Hello, Stefan.

On Fri, Mar 13, 2015 at 04:38:05PM -0400, Stefan Monnier wrote:
> > They're not that rare.  I count 304 currently in Emacs, including
> > eudc-cdaar (twice), in 78 files.  That's a lot of files that need to
> > require cl.

> Most likely 99.9% of these files also use other CL facilities, so that
> wouldn't save them from requiring CL.  And in any case, using CL
> facilities is perfectly fine (provided you do it via cl-lib rather than
> cl.el).

I don't know how many of them require other bits of CL.  But the point
is that CL is not loaded by default, so any use of cXXXr in standard
files is awkward.  I'm thinking in particular about my new fix-re.el
here.

> > let-binding variables, then accessing them, must be quite slow
> > by comparison.

> Via dynamically scoped vars, that's indeed the case.
> But with lexical-binding not anymore.

OK, fair enough.  But unless we're talking about doing cXXXr needlessly
in a tight loop, it's hardly going to make a noticeable difference.

Here's what I now propose to commit.  In the patch:

1. All c[ad]\{3,4\}r are now declared in subr.el, generated from macros.
2. Each of these has a cl-cXXXr as an alias, declared as obsolete as
  from 25.1.
3. caar, cadr, cdar, and cddr are now declared as defuns (changed from
  defsubsts).
4. All the cXXr, including caar, etc., use the compiler macro
  `compiler-macro-cXXr' (renamed by removing "cl-" from the name).

It proved impractical also to generate caar, cadr, cdar, and cddr from
the macros, since there were circular dependencies in the
`compiler_macro' form in `zerop'.  I now accept that adding in 5 element
cXXXr's would be tasteless and uncalled for.



diff --git a/lisp/subr.el b/lisp/subr.el
index deadca6..89371f4 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -339,20 +339,38 @@ configuration."
 \f
 ;;;; List functions.
 
-(defsubst caar (x)
+(defun compiler-macro-cXXr (form x)
+  (let* ((head (car form))
+         (n (symbol-name (car form)))
+         (i (- (length n) 2)))
+    (if (not (string-match "c[ad]+r\\'" n))
+        (if (and (fboundp head) (symbolp (symbol-function head)))
+            (compiler-macro-cXXr (cons (symbol-function head) (cdr form))
+                                     x)
+          (error "Compiler macro for cXXr applied to non-cXXr form"))
+      (while (> i (match-beginning 0))
+        (setq x (list (if (eq (aref n i) ?a) 'car 'cdr) x))
+        (setq i (1- i)))
+      x)))
+
+(defun caar (x)
   "Return the car of the car of X."
+  (declare (compiler-macro compiler-macro-cXXr))
   (car (car x)))
 
-(defsubst cadr (x)
+(defun cadr (x)
   "Return the car of the cdr of X."
+  (declare (compiler-macro compiler-macro-cXXr))
   (car (cdr x)))
 
-(defsubst cdar (x)
+(defun cdar (x)
   "Return the cdr of the car of X."
+  (declare (compiler-macro compiler-macro-cXXr))
   (cdr (car x)))
 
-(defsubst cddr (x)
+(defun cddr (x)
   "Return the cdr of the cdr of X."
+  (declare (compiler-macro compiler-macro-cXXr))
   (cdr (cdr x)))
 
 (defun last (list &optional n)
@@ -478,6 +496,80 @@ argument VECP, this copies vectors as well as conses."
 	    (aset tree i (copy-tree (aref tree i) vecp)))
 	  tree)
       tree)))
+
+;; Macros to generate caaar ... cddddr.
+(defun gen-cXXr--rawname (n bits)
+  "Generate and return a string like \"adad\" corresponding to N.
+BITS is the number of a's and d's.
+The \"corresponding\" means each bit of N is converted to an \"a\" (for zero)
+or a \"d\" (for one)."
+  (let ((name (make-string bits ?a))
+	(mask (lsh 1 (1- bits)))
+	(elt 0))
+    (while (< elt bits)
+      (if (/= (logand n mask) 0)
+	  (aset name elt ?d))
+      (setq elt (1+ elt)
+	    mask (lsh mask -1)))
+    name))
+
+(defun gen-cXXr--doc-string (raw)
+  "Generate a doc string for a name like \"cadadr\".
+RAW is the \"inner\" part of the name, e.g. \"adad\"."
+  (concat
+   "Return the `c"
+   (mapconcat #'char-to-string raw "r' of the `c")
+   "r' of X."))
+
+(defun gen-cXXr--code (raw bits)
+  "Generate the code for a defun like \"cadadr\" in terms of `car' and `cdr'.
+RAW is the \"inner\" part of the name, e.g. \"adad\", BITS is the
+length of RAW."
+  (let ((code 'x)
+	(elt bits))
+    (while (> elt 0)
+      (setq elt (1- elt))
+      (setq code (list (if (eq (aref raw elt) ?a) 'car 'cdr) code)))
+    code))
+
+(defun gen-cXXr--defun (n bits)
+  "Generate a `defun' for a symbol like \"cadadr\".
+N is a number representing the \"inner\" part of the
+symbol (e.g. binary 0101 for cadadr), BITS is the length of that
+part of the symbol (e.g. 4).  include a `compiler-macro'
+declaration in the defun."
+  (let ((raw (gen-cXXr--rawname n bits)))
+    `(defun ,(intern (concat "c" raw "r")) (x)
+       ,(gen-cXXr--doc-string raw)
+       (declare (compiler-macro compiler-macro-cXXr))
+       ,(gen-cXXr--code raw bits))))
+
+(defmacro gen-cXXr-all (bits)
+  "Generate defuns for all `c[ad]+r's with BITS a's and d's.
+Include `compiler-macro' declarations in the defuns."
+  `(progn
+     ,@(mapcar
+	(lambda (n)
+	  (gen-cXXr--defun n bits))
+	(number-sequence 0 (1- (lsh 1 bits))))))
+
+(defmacro gen-cXXr-all-cl-aliases (bits)
+  "Generate cl- aliases for all defuns `c[ad]+r' with BITS a's and d's.
+Also mark the aliases as obsolete."
+  `(progn
+     ,@(mapcar
+	(lambda (n)
+	  (let* ((raw (gen-cXXr--rawname n bits))
+		 (old (intern (concat "cl-c" raw "r")))
+		 (new (intern (concat "c" raw "r"))))
+	    `(progn (defalias ',old ',new)
+		    (make-obsolete ',old ',new "25.1"))))
+	(number-sequence 0 (1- (lsh 1 bits))))))
+
+(gen-cXXr-all 3)		; Generate `caaar', `caadr', ..., `cdddr'.
+(gen-cXXr-all-cl-aliases 3)
+(gen-cXXr-all 4)		 ; Generate `caaaar', `caaadr', ..., `cddddr'.
+(gen-cXXr-all-cl-aliases 4)
 \f
 ;;;; Various list-search functions.
 

[Boring patch ripping out stuff from cl-lib.el, etc., not shown.]


>         Stefan

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: Rationalising c[ad]\{2,5\}r.

[Stefan Monnier]

> I don't know how many of them require other bits of CL.  But the point
> is that CL is not loaded by default, so any use of cXXXr in standard
> files is awkward.  I'm thinking in particular about my new fix-re.el
> here.

You can use cl-lib freely in most files.  The only exception is for
preloaded files which can only (eval-when-compiler (require 'cl-lib))
(with some further exceptions for the earliest files, for obvious
reasons of bootstrap limitations).

So you can (eval-when-compiler (require 'cl-lib)) in fix-re.el without
any hesitation.  IOW no need to add anything to subr.el for that.
This said, fix-re.el seems to be the quintessential example of abuse of
heaps of car/cdr which make the code unreadable.

> OK, fair enough.  But unless we're talking about doing cXXXr needlessly
> in a tight loop, it's hardly going to make a noticeable difference.

Agreed.

> 1. All c[ad]\{3,4\}r are now declared in subr.el, generated from macros.

I'm still not convinced it's a good idea to add those to subr.el.

> 2. Each of these has a cl-cXXXr as an alias, declared as obsolete as
>   from 25.1.

These aliases and obsolescence settings would belong in cl-lib.el.

> 3. caar, cadr, cdar, and cddr are now declared as defuns (changed from
>   defsubsts).
> 4. All the cXXr, including caar, etc., use the compiler macro
>   `compiler-macro-cXXr' (renamed by removing "cl-" from the name).

Please keep a "--" in the name to indicate it's an internal function.
For lack of a good prefix, I'd use "internal--".


        Stefan

Re: Rationalising c[ad]\{2,5\}r.

[Alan Mackenzie]

Hello, Stefan

I've finally committed this change (getting rid of cl-caddr, etc.).  make
bootstrap works with it.

As you requested over course of the thread, c[ad]\{3,4\}r remain in
cl-lib.el with obsolete aliases for the cl-.. names, there are no
c[ad]\{5\}r, and the defsubsts for caar, cadr, cdar, and cddr in subr.el
are now defuns with a compiler macro.  eudc-cadr, and friends, have
simply vanished.

On Fri, Mar 13, 2015 at 07:00:20PM -0400, Stefan Monnier wrote:
> > I don't know how many of them require other bits of CL.  But the point
> > is that CL is not loaded by default, so any use of cXXXr in standard
> > files is awkward.  I'm thinking in particular about my new fix-re.el
> > here.

> You can use cl-lib freely in most files.  The only exception is for
> preloaded files which can only (eval-when-compiler (require 'cl-lib))
> (with some further exceptions for the earliest files, for obvious
> reasons of bootstrap limitations).

> So you can (eval-when-compiler (require 'cl-lib)) in fix-re.el without
> any hesitation.  IOW no need to add anything to subr.el for that.
> This said, fix-re.el seems to be the quintessential example of abuse of
> heaps of car/cdr which make the code unreadable.

> > OK, fair enough.  But unless we're talking about doing cXXXr needlessly
> > in a tight loop, it's hardly going to make a noticeable difference.

> Agreed.

> > 1. All c[ad]\{3,4\}r are now declared in subr.el, generated from macros.

> I'm still not convinced it's a good idea to add those to subr.el.

> > 2. Each of these has a cl-cXXXr as an alias, declared as obsolete as
> >   from 25.1.

> These aliases and obsolescence settings would belong in cl-lib.el.

> > 3. caar, cadr, cdar, and cddr are now declared as defuns (changed from
> >   defsubsts).
> > 4. All the cXXr, including caar, etc., use the compiler macro
> >   `compiler-macro-cXXr' (renamed by removing "cl-" from the name).

> Please keep a "--" in the name to indicate it's an internal function.
> For lack of a good prefix, I'd use "internal--".


>         Stefan

-- 
Alan Mackenzie (Nuremberg, Germany).