Re: moving more cl seq/mapping support into core

[MON KEY <monkey@sandpframing.com>]

On Mon, Oct 4, 2010 at 1:33 PM, Daniel Colascione
<dan.colascione@gmail.com> wrote:
> On 10/3/2010 7:03 PM, Richard Stallman wrote:
>>     Whatever the current/existing rationales may be, surely _some_ will
>>     cease to be relevant by any reasonably sane justification in lieu of
>>     lexically scoped environments.
>>
>> I don't think that relates to this issue.
>> This issue is about global names.
>>
>
> _What_ global names? cl.el is _already_ widely used. What symbols
> actually cause a problem _in practice_, _today_?
>

Its tautological... CL symbols which name a function exist with global
names and therefor can not be allowed to pollute the global name
space.

As indicated with my earlier example, when `byte-compile-warnings' is
non-nil and '(byte-compile-warning-enabled-p 'cl-functions)' returns
non-nil (per a symbol's membership in `byte-compile-cl-functions'),
then byte-compilation signals a warning that the symbol was called at
runtime (regardless of when/where that symbol was actually defined).

IOW, the CL functions exists in a state of privileged limbo in that
they can not be called at runtime but nor are they allowed to be
redefined at compile time...

IIUC this cycle is a product of the current byte-compilers relatively
flat environment which is what prompted the assertion:

,----
| Whatever the current/existing rationales may be, surely _some_ will
| cease to be relevant by any reasonably sane justification in lieu of
| lexically scoped environments.
`----

The lexbind promotes less flat environments with its `heap environment
vectors' see for example the variables:

 `byte-compile-lexical-environment',
 `byte-compile-current-heap-environment',
 `byte-compile-current-num-closures', `byte-stack-ref',
 `byte-stack-set', `byte-stack-set2', `byte-vec-ref', `byte-vec-set',
 `byte-discardN', `byte-discardN-preserve-tos'

And employs an entirely different compile time expansion of macro
environments e.g. the constant
`byte-compile-initial-macro-environment'. The lexbind byte-compiler
handles these environments and those established by lexical closures
in new ways. This includes modification of the existing
`byte-compile-lambda' with a significantly new re-direction through
`byte-compile-closure', `byte-compile-make-closure',
`byte-compile-make-lambda-lexenv', etc. Indeed, whenever an anonymous
function occurs inside a lexical-binding all compile-time variables
are affected by use of separate 'heapenv' heap environment vectors.

Whatever. I'm sure some of the above is very much in flux in
Stefan/Miles' private branches and likely to change before those
emerge (presumably circa Spring 2011).

The intent of my above referenced query is to learn how much of the
global names argument will remain relevant for those CL symbols (and
their locals) which currently "pollute" the global names but which
(if adapted in lieu of lexbind) might have some not insignificant
portion of this pollution encapsulated with closed over 'lexenv'
environments including any byte-compiler optimizations over the
'lexvars' of these environments.

More specifically, if some aspect(s) of the above are indeed
possible/reasonable and the pollution might be reduced, I'm curious to
learn if those CL functions which accept keywords could be abstracted
in such a way that they might be included in core without constraints
on these necessarily being "keywordless" but instead that there be a
proviso for requisite compile-time analysis capable of determining
whether the function body expects non-keyword arguments or instead a
keyword variant.

This would:

 - Allow backwards compatibility with existing uses of CL functions;

 - Provide an opportunity to revisit certain places where the existing
   cl.el implementation is regarded deficient/sub-optimal;

 - Provide 3rd party developers the opportunity adapt existing code to
   use a 'lighter' non-keyword CL variants where appropriate;

 - Acknowledges Stefan's distaste of maintaining distinct symbol-names
   for the Emacs lisp core function vs the CL counterpart, e.g. push,
   pop, dotimes, dolist, etc.;

  - Ease documentation concerns because portions of the existing CL
    info could be incorporated without requiring that all references
    to the keyword usage be gutted. Instead, documentation for the
    default non-keyword version would be added along with
    clarification of the differences. Given that Emacs installs with
    the cl.info the this should help keep the expense of documentation
    overhead down. (Assumes there aren't lingering arm-waving
    intentions about some vague copyright restriction w/re the cl.info
    manual and the ANSI spec);

It is apropos the possibility that some of the above hypotheticals
might have relevance/traction that I asserted previously:

,----
| It is important that those willing to revisit/revise the cl.el
| deficiencies have a clear roadmap/guideline as to what is acceptable,
| why, and what the sane justifications for these guidelines are.
`----

Right now there are numerous alternative and (functionally divergent)
implementations of the CL functions which often have been written to
not trigger signalling of CL related runtime byte-compiler
warnings. I've pointed out some that are already in core.

Note, none of these appear to have been written in a spirit of:

 "Oh, I wrote this because I don't want all of those CL features."

Indeed, most of the packages which employ cl feature duplication do
rely elsewhere on CL macros, but these don't trigger the runtime
warnings.

So, as an example, one finds that prior to Bzr-98091 of 2009-10-11
eieio.el's `eieio-add-new-slot' called `union' twice, each time inside
deeply nested conditionals. These `union' calls were responsible for
informing the adjustment of class slot attributes pertinent to
custom-group classes. Who knows if anyone is using this stuff (what with
it being custom and all).  Regardless, both of these calls have since
been adapted by virtue of a "manual inlining"... The first such
`union' call involves a tweak of an index into
`class-public-custom-group'. It is triggered when `eieio-add-new-slot'
optional arg DEFAULTOVERRIDE is non-nil. The second also is a similar
tweak triggered in the same manner but instead finds a takes a union
of an index into `class-class-allocation-custom-group'. Now,
presumably user code won't rely on these tweaks occurring all that
frequently as the DEFAULTOVERRIDE arg is the first optional arg in the
`eieio-add-new-slot' lambda-list. Indeed, it follows 11 other
obviously more important parameters e.g.:

 (1- (length '(newc a d doc type cust label custg print
               prot init alloc &optional defaultoverride skipnil)))

and can't possibly be all that important in its priveleged 12th
position given that the _eleven_ preceding args are mandatory...
 "Nah, we don't need no stinkin' keywords."  Or not.

Instance one of `union's demise by duplication:

,---- lisp/emacs-lisp/eieio.el `eieio-add-new-slot' @Bzr-98018
|  (when custg
|    (let ((where-groups
|           (nthcdr num (aref newc class-public-custom-group))))
|      (setcar where-groups
|              (union (car where-groups)
|                     (if (listp custg) custg (list custg))))))
`----

,---- lisp/emacs-lisp/eieio.el `eieio-add-new-slot' @Bzr-101790
| (when custg
|   (let* ((groups
|           (nthcdr num (aref newc class-public-custom-group)))
|          (list1 (car groups))
|          (list2 (if (listp custg) custg (list custg))))
|     (if (< (length list1) (length list2))
|         (setq list1 (prog1 list2 (setq list2 list1))))
|     (dolist (elt list2)
|       (unless (memq elt list1)
|         (push elt list1)))
|     (setcar groups list1)))
`----

Note, the only discernible difference between the chunks above and
those below are the let bindings of the local `groups` var to an index
into `class-class-allocation-custom-group' instead of
`class-public-custom-group', otherwise they are identical.

Instance two of `union's demise by duplication:

,---- lisp/emacs-lisp/eieio.el `eieio-add-new-slot' @Bzr-98018
| (when custg
|   (let ((where-groups
|          (nthcdr num (aref newc class-class-allocation-custom-group))))
|     (setcar where-groups
|             (union (car where-groups)
|                    (if (listp custg) custg (list custg))))))
`----

,---- lisp/emacs-lisp/eieio.el `eieio-add-new-slot' @Bzr-101790
| (when custg
|   (let* ((groups
|           (nthcdr num (aref newc class-class-allocation-custom-group)))
|          (list1 (car groups))
|          (list2 (if (listp custg) custg (list custg))))
|     (if (< (length list1) (length list2))
|         (setq list1 (prog1 list2 (setq list2 list1))))
|     (dolist (elt list2)
|       (unless (memq elt list1)
|         (push elt list1)))
|     (setcar groups list1)))
`----

Now for a game of "one of these things looks alot like the other one":

,---- lisp/emacs-lisp/cl-seq.el `union' @Bzr-101804
|
| (cond ((null cl-list1) cl-list2) ((null cl-list2) cl-list1)
|       ((equal cl-list1 cl-list2) cl-list1)
|       (t
|        (or (>= (length cl-list1) (length cl-list2))
|            (setq cl-list1 (prog1 cl-list2 (setq cl-list2 cl-list1))))
|        (while cl-list2
|          (if (or cl-keys (numberp (car cl-list2)))
|              (setq cl-list1
|                    (apply 'adjoin (car cl-list2) cl-list1 cl-keys))
|            (or (memq (car cl-list2) cl-list1)
|                (push (car cl-list2) cl-list1)))
|          (pop cl-list2))
|        cl-list1))
|
`----

In the absence of a change to the current runtime ban more of the
above will continue to spring up.  Now, no doubt when Chong Yidong
must be bothered to implement this sort of hackery one can expect a
_correct_ hack. Right? Its not like the above isn't mostly a
copy/paste job into an unbelievably deeply chunk of nested
nastiness...

The "problem" though is that many such like workarounds aren't
instrumented courtesy Chong/Stefan/Richard et al, but instead by 3rd
parties whom none-the-less _are_ making attempts to comply with the CL
function runtime ban. It isn't enough for emacs-devels to dismiss
those parties (as they sometimes do) with:

 "Well, either ignore the byte-compiler warnings if they bother
  you so much or don't use the CL features in your library"

This is insults both the 3rd party developer and any party whom
attempts installing the third party library. When byte-compilation of
the 3rd party code signals a bunch of byte-compiler warnings it casts
doubt or creates fear and uncertainty and may make it appear as if the
library is deficient/suspect. All else being equal, the cumulative
effect of these byte-compiler warnings is a form of discriminatory
rankism which privileges the Emacs core libraries which in turn
promotes further entrenchment of the CL runtime ban, e.g.:

 "None of the core libraries require/rely on CL functions which
  pollute the global names in order to get things done."

Indeed, they don't - most likely they just implement it in C instead.

This isn't an option to 3rd party developers. So, to avoid the
_appearance_ of being "unclean" 3rd parties often either:

- copy the CL function definitions verbatim
  (which _is_ itself a colossal pollution of the "global names");

- attempt to (re)implement the portions of the CL feature set they
  would otherwise use were the ban not in place

It is clear that both of the above choices are and have been occurring.

With regards the re-implementation approach, this is where the CL
runtime ban fails to benefit both the community of Emacs users and
3rd party authors in the "real world" because (re)implementing any
subset of the CL feature is:

- hard to accomplish in the absence of runtime usage of the CL
  features, i.e. the act itself lands one in the Turing Tar Pit;

- a waste of energy rebuilding the existent usable, distributed, and
  tested featureset esp. as it at least attempts adherence to a
  formally peer reviewed specification;

- likely won't benefit from the same byte-compiler optimizations as a
  cl-*.el counterpart;

- apt to error in unexpected/unforeseen non-standard ways;

This is grossly unfortunate because it is clear that despite these
obstacles 3rd parties do endeavor re-implementing workarounds to the
CL runtime ban despite Philip Greenspun's "Tenth Rule" leering back at
them.  The gross aspect of this circumstance being that "Greenspun's
Tenth" is most likely a precept well known to the unfortunate
attempting to recapture some semblance of the Common Lisp so denied...

By way of an example we have the following:

,----
| From: 	Stefan Monnier
| Subject: Re: testing framework and package.el
| Date: 	Tue, 28 Sep 2010 00:57:51 +0200
| (URL `http://lists.gnu.org/archive/html/emacs-devel/2010-09/msg01500.html')
|
| IIRC we've agreed to try and install ERT, either on elpa or in Emacs
| itself, and then try and move the few tests we already have
| scattered about to use ERT.  But I haven't heard much about it
| recently
`----

Taking a look at ert.el package on Christian Ohler's git repo:
 (URL `git://github.com/ohler/ert.git')
one finds yet more CL feature duplication attempts. These presumably
queued up for inclusion in Emacs proper in the not so distant future.
Below are the CL "duplicate" features from ert/lisp/emacs-lisp/ert.el

The features `ert--cl-do-remf' and `ert--remprop' are verbatim copies
of `cl-do-remf'. The features `ert--remove-if-not',
`ert--intersection', `ert--set-difference', `ert--set-difference-eq',
and `ert--union' are keywordless re-implementations of CL features
which leverage the `loop' macro to mimic the CL features
`intersection', `set-difference', and `union'.

It should be noted however that (with the exception of `ert--union')
these are not at all faithful duplicates of either the CL features or
their ANSI brethren as they fail to check that their args are
proper-lists/sequences...

Now, I'm given to believe that Ohler is not only an accomplished hack,
but also prob. one well aware of the Common Lisp ANSI spec. So his
floundering on the proper-list/proper-seq thing is prob. indicative of
something.

Does Ohler believe that his CL duplicates are better for their
non-conformance and breaking with both the semantics of both the CL
features and the Common Lisp features? Maybe he finds his duplicates
achieve a desirable performance gain. Or, maybe he just doesn't feel it
worth the trouble to rewrite _all_ of cl*.el.

This said, that ERT is slated as the "blessed" Emacs unit test
framework begs a more important question.

If Ohler implemented his CL feature duplications as a kludge would he
have simply done a (require 'cl) and been done with it were it not for
the CL runtime ban?

And if so, would ERT be better/more correct by so doing?

Whatever. Say hello to the latest iteration of a Lisper doing his best
to suffer a foolish policy.

,---- ert/lisp/emacs-lisp/ert.el (URL `http://github.com/ohler/ert')
|
|
| (defun ert--cl-do-remf (plist tag)
|   "Copy of `cl-do-remf'.  Modify PLIST by removing TAG."
|   (let ((p (cdr plist)))
|     (while (and (cdr p) (not (eq (car (cdr p)) tag)))
|             (setq p (cdr (cdr p))))
|     (and (cdr p) (progn (setcdr p (cdr (cdr (cdr p)))) t))))
|
| (defun ert--remprop (sym tag)
|   "Copy of `cl-remprop'.  Modify SYM's plist by removing TAG."
|   (let ((plist (symbol-plist sym)))
|     (if (and plist (eq tag (car plist)))
| 	(progn (setplist sym (cdr (cdr plist))) t)
|       (ert--cl-do-remf plist tag))))
|
| ;; :NOTE Vector agnostic.
| ;; (ert--remove-if-not 'stringp ["a" "b" c])  ;=> nil
| ;; (ert--remove-if-not 'stringp '("a" "b" c)) ;=> ("a" "b")
| ;; (remove-if-not 'stringp ["a" "b" c])       ;=> ["a" "b"]
| ;; (remove-if-not 'stringp '("a" "b" c))      ;=> ("a" "b")
| (defun ert--remove-if-not (ert-pred ert-list)
|   "A reimplementation of `remove-if-not'.
| ERT-PRED is a predicate, ERT-LIST is the input list."
|   (loop for ert-x in ert-list
|         if (funcall ert-pred ert-x)
|         collect ert-x))
|
| ;; :NOTE `set-difference' w/ Common Lisp's default implicit 'eql test.
| ;; Mostly equivalent to cl-seq.el's `intersection'
| ;;  (intersection '(a b) '(c a) :test 'eql)
| ;; But,  does not check that args are proper lists:
| ;; (ert--intersection '(a . c) '(b   d)) ;=> nil
| ;; (intersection '(a . c) '(b   d)) ;=> (wrong-type-argument listp c)
| (defun ert--intersection (a b)
|   "A reimplementation of `intersection'.  Intersect the sets A and B.
| Elements are compared using `eql'."
|   (loop for x in a
|         if (memql x b)
|         collect x))
|
| ;; :NOTE `set-difference' w/ Common Lisp's default implicit 'eql test.
| ;; Mostly equivalent to cl-seq.el's `set-difference':
| ;;  (set-difference a b :test 'eql)
| ;; But, does not check that args are proper lists:
| ;;  (ert--set-difference '(a . c) '(b   d)) ;=> (a)
| ;;  (set-difference '(a . c) '(b   d) :test 'eql)
| ;;  => (wrong-type-argument listp c)
| (defun ert--set-difference (a b)
|   "A reimplementation of `set-difference'.
| Subtract the set B from the set A.
| Elements are compared using `eql'."
|   (loop for x in a
|         unless (memql x b)
|         collect x))
|
| ;; :NOTE This is roughly cl.el's `set-difference' w/ the implicit
| ;; 'eq test.
| ;; Mostly equivalent to Common Lisp's: (set-difference a b :test 'eq)
| ;; But, does not check that args are proper lists:
| ;; (ert--set-difference-eq '(a . c) '(b   d)) ;=> (a)
| ;; (set-difference '(a . c)  '(b   d)) ;=> (wrong-type-argument listp c)
| (defun ert--set-difference-eq (a b)
|   "A reimplementation of `set-difference'.
| Subtract the set B from the set A.
| Elements are compared using `eq'."
|   (loop for x in a
|         unless (memq x b)
|         collect x))
|
| ;; :NOTE Unlike above doesn't error when args not proper lists
| ;; (ert--union '(a . c) '(b   d)) ;=> (wrong-type-argument listp c)
| (defun ert--union (a b)
|   "A reimplementation of `union'.
| Compute the union of the sets A and B.
| Elements are compared using `eql'."
|   (append a (ert--set-difference b a)))
|
| (eval-and-compile
|   (defvar ert--gensym-counter 0))
|
| ;; :NOTE Does note accept integer for optional arg PREFIX.
| (eval-and-compile
|   (defun ert--gensym (&optional prefix)
|     "Only allows string PREFIX, not compatible with CL."
|     (unless prefix (setq prefix "G"))
|     (make-symbol (format "%s%s"
|                          prefix
|                          (prog1 ert--gensym-counter
|                            (incf ert--gensym-counter))))))
|
| ;; :NOTE Could chang parameter list to ( ... &optional key test)
| (defun* ert--remove* (x list &key key test)
|   "Does not support all the keywords of remove*."
|   (unless key (setq key #'identity))
|   (unless test (setq test #'eql))
|   (loop for y in list
|         unless (funcall test x (funcall key y))
|         collect y))
|
| (defun ert--mismatch (a b)
|   "Return index of first element that differs between A and B.
| Like `mismatch'.  Uses `equal' for comparison."
|   (cond ((or (listp a) (listp b))
|          (ert--mismatch (ert--coerce-to-vector a)
|                         (ert--coerce-to-vector b)))
|         ((> (length a) (length b))
|          (ert--mismatch b a))
|         (t
|          (let ((la (length a))
|                (lb (length b)))
|            (assert (arrayp a) t)
|            (assert (arrayp b) t)
|            (assert (<= la lb) t)
|            (loop for i below la
|                  when (not (equal (aref a i) (aref b i))) return i
|                  finally (return (if (/= la lb)
|                                      la
|                                    (assert (equal a b) t)
|                                    nil)))))))
|
| (defun ert--subseq (seq start &optional end)
|   "Returns a subsequence of SEQ from START to END."
|   (when (char-table-p seq) (error "Not supported"))
|   (let ((vector (substring (ert--coerce-to-vector seq) start end)))
|     (etypecase seq
|       (vector vector)
|       (string (concat vector))
|       (list (append vector nil))
|       (bool-vector (loop with result = (make-bool-vector (length vector) nil)
|                          for i below (length vector) do
|                          (setf (aref result i) (aref vector i))
|                          finally (return result)))
|       (char-table (assert nil)))))
|
| (defun ert--special-operator-p (thing)
|   "Return non-nil if THING is a symbol naming a special operator."
|   (and (symbolp thing)
|        (let ((definition (indirect-function thing t)))
|          (and (subrp definition)
|               (eql (cdr (subr-arity definition)) 'unevalled)))))
|
`----

--
/s_P\