unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
* [PATCH] Add cl-map-into
@ 2021-09-23 23:35 akater
  2021-09-27 17:18 ` Stefan Monnier
  0 siblings, 1 reply; 22+ messages in thread
From: akater @ 2021-09-23 23:35 UTC (permalink / raw)
  To: emacs-devel


[-- Attachment #1.1: Type: text/plain, Size: 283 bytes --]

Absense of Common Lisp's map-into in cl-lib is an unfortunate omission.
The proposed patch adds it.

There are several issues with existing multi-sequence cl- functions in
cl-lib.  Hopefully, our approach could be used to improve the situation.
See comment in the patch for details.

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

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Add cl-map-into --]
[-- Type: text/x-diff, Size: 11233 bytes --]

From c01eb04cb031f38fe3270de5a75a3809b1034750 Mon Sep 17 00:00:00 2001
From: akater <nuclearspace@gmail.com>
Date: Wed, 15 Sep 2021 19:42:47 +0000
Subject: [PATCH] Add cl-map-into

map-into is a standard Common Lisp function that acts as cl-map, only
values are recorded into a preallocated sequence.

* lisp/emacs-lisp/cl-extra.el
(cl-map-into): New primary function
(cl--map-into-basic-call-arguments-limit,
cl--map-into-max-small-signature): New auxillary constant
(cl--map-into-mappers-array, cl--map-into-mappers-alist): New variable
(cl--compute-map-into-signature, cl--make-map-into-mapper): New auxillary function
(cl--do-seq-type-signature): New auxillary macro
---
 lisp/emacs-lisp/cl-extra.el | 228 ++++++++++++++++++++++++++++++++++++
 1 file changed, 228 insertions(+)

diff --git a/lisp/emacs-lisp/cl-extra.el b/lisp/emacs-lisp/cl-extra.el
index 3840d13ecf..84ce153758 100644
--- a/lisp/emacs-lisp/cl-extra.el
+++ b/lisp/emacs-lisp/cl-extra.el
@@ -88,6 +88,234 @@ defun cl-equalp (x y)
 	(t (equal x y))))
 
 
+;;; map-into
+
+;; We implement a simple dispatcher for sequence types.
+;;
+;; cl-extra has cl--mapcar-many for similar purpose.
+;; The core issue with it, it goes through args pre-emptively
+;; to compute min length when there are more than 2 arguments
+;; which makes it and its reverse dependencies fail on circular lists
+;; unless there are <3 args.
+;; Other issues are
+;; - it performs type checks for sequences of known types at runtime
+;; - it may cons whole arglist thrice per invocation
+;; - looks like it's hard to extend.
+
+;; Our approach doesn't have these issues.
+
+(defconst cl--map-into-basic-call-arguments-limit 7
+  "Maximal reasonably expected number of arguments to `cl-map-into'.
+
+`cl-map-into' caches its code corresponding to various signature
+types of arglists supplied to `cl-map-into'.  Arglists may vary
+in length.
+
+Code corresponding to arglists of length less than
+`cl--map-into-basic-call-arguments-limit' is accessed via array.
+
+Code corresponding to arglists of length greater than or equal to
+`cl--map-into-basic-call-arguments-limit' is accessed via alist.
+")
+
+(defconst cl--map-into-max-small-signature
+  (expt 2 cl--map-into-basic-call-arguments-limit)
+  "Length of array to allocate for caching `cl-map-into' mappers
+corresponding to small arglists.
+
+Such mappers are accessed by their position in an array; position
+equals the signature.
+
+Consider `cl-map-into' arglist
+
+(target f seq-1 seq-2)
+
+call-arguments-limit corresponding to arglists of this length or
+shorter, is 4 (as there are 4 arguments).  This leaves at most 3
+sequences to contribute to type signature.
+
+Hovewer, we have to store one additional bit for fixnum-based
+encoding to be unambiguous and simple.  So overall array length
+ends up being exactly (expt 2 call-arguments-limit).")
+
+(defvar cl--map-into-mappers-array
+  (make-vector cl--map-into-max-small-signature nil)
+  "Array holding mappers corresponding to small arglists of `cl-map-into'.
+
+Element type is (or function null).")
+
+(defvar cl--map-into-mappers-alist nil
+  "Alist holding mappers corresponding to large arglists of `cl-map-into'.")
+
+(defun cl--compute-map-into-signature (&rest all-sequences)
+  "Compute lookup key for `cl-map-into''s almost-arglist ALL-SEQUENCES.
+
+Namely: ALL-SEQUENCES would be (TARGET   &rest SEQUENCES)
+               for (cl-map-into TARGET f &rest SEQUENCES)
+
+As a side effect, it checks that ALL-SEQUENCES are of sequence
+types.
+
+Example:
+ELISP> (mapcar (lambda (arglist)
+                 (apply #'cl--compute-map-into-signature arglist))
+               '(( () () () )                ; signature #b1000
+                 ( () () [] )                ; signature #b1001
+                 ( () [] () )                ; signature #b1010
+                 ( () [] [] )                ; signature #b1011
+                 ( [] () () )                ; signature #b1100
+                 ))
+(8 9 10 11 12)"
+  ;; This is not `cl-map-into'-specific and could be used for other caches
+  ;; which is why we don't specify arglist as (target &rest sequences).
+  ;; For the time being (while this dispatch is not used widely),
+  ;; neither docstring nor name reflect this.
+  (let ((signature 1))
+    (dolist (s all-sequences signature)
+      (setq signature (ash signature 1))
+      (cl-etypecase s
+        (list)
+        (vector (cl-incf signature))))))
+
+;; ;; todo: move to tests
+
+;; (cl-map-into (list 0 0 0) #'+ [41 40 39] '(1 2 3))
+;; (cl-map-into (list 0 0 0) #'+ '(1 2 3) [41 40 39])
+
+;; (let ((s (list 0 0 0)))
+;;   (cl-map-into s #'+ '(1 2 3) [41 40 39])
+;;   s)
+;; (let ((s (cl-coerce '(18 19 20) 'vector)))
+;;   (cl-map-into s #'+ s '(6 4 2 1 not-even-a-number) s)
+;;   s)
+
+(cl-defmacro cl--do-seq-type-signature ((type-var signature &optional result)
+                                        &body body)
+  "With TYPE-VAR bound to sequence type, evaluate BODY forms.  Return RESULT.
+
+TYPE-VAR goes across sequence types in an arglist corresponding
+to SIGNATURE that encodes sequence types in that arglist.
+
+Iteration goes from arglist's end to arglist's start.
+
+If :first is present at toplevel in BODY, all forms following
+it (and those forms only) are evaluated in order when TYPE-VAR is
+bound to the first sequence type in the arglist --- which would
+be the last sequence type derived from SIGNATURE: see the
+previous paragraph.  At other iteration steps, only forms
+preceding the first :first are evaluated.
+
+Subsequent instances of toplevel :first in BODY don't affect anything."
+  (declare (indent 1))
+  (let* ((main (cl-copy-list body))
+         (first (if (eq :first (car main)) (progn (setf main nil)
+                                                  (cdr main))
+                  (cl-loop with sublist = main
+                           while sublist do
+                           (when (eq :first (cadr sublist))
+                             (setf first (cddr sublist) (cdr sublist) nil)
+                             (cl-return first))
+                           (pop sublist)))))
+    (let ((sig (gensym "sig-")))
+      `(let ((,sig ,signature) ,type-var)
+         ;; (declare (type (integer (1)) ,sig)
+         ;;          ;; Let's keep nil for now.
+         ;;          (type (member nil list vector) ,type-var))
+         (cl-check-type ,sig (integer (1)))
+         (cl-loop (cond
+                   ((or (when (= 2 ,sig) (setq ,type-var 'list))
+                        (when (= 3 ,sig) (setq ,type-var 'vector)))
+                    ;; TODO: This duplicates main code sometimes,
+                    ;; think of elegant enough way to eliminate duplication.
+                    ,@(or first main) (cl-return ,result))
+                   (t (setq ,type-var (if (zerop (mod ,sig 2))
+                                          'list
+                                        'vector))
+                      ,@main))
+                  (setf ,sig (floor ,sig 2)))))))
+
+(defun cl--make-map-into-mapper (signature &optional do-not-compile)
+  "Return mapper for `cl-map-into' specialized on arglists of type encoded by SIGNATURE.
+
+If DO-NOT-COMPILE is nil (default), return byte-compiled function.
+Otherwise, return lambda form.
+
+Example:
+ELISP> (cl--make-map-into-mapper #b1011 t)
+(lambda (f target-list vector-2 vector-1)
+  (cl-symbol-macrolet ((place (car target-cons)))
+    (cl-loop for target-cons on target-list
+             for elt-2 across vector-2
+             for elt-1 across vector-1
+             do (setf place (funcall f elt-2 elt-1))
+             finally return target-list)))"
+  (let ((gensym-counter 1) f xs ss loop
+        target-type target-index target-place target-var)
+    (cl-macrolet ((nconcf (var &rest seqs) `(setf ,var (nconc ,@seqs ,var))))
+      ;; The only good thing about this name is, it's short and ends with f
+      (cl--do-seq-type-signature (type signature)
+        (nconcf loop (list 'for (let ((it (gensym "elt-")))
+                                  (push it xs)
+                                  (cl-decf gensym-counter)
+                                  it)
+                           (cl-case type
+                             (list 'in)
+                             (vector 'across))
+                           (let ((it (gensym (concat (symbol-name type) "-"))))
+                             (push it ss)
+                             it)))
+        :first (setq target-type type
+                     target-var (make-symbol
+                                 (concat "target-" (symbol-name target-type))))
+        (nconcf loop (list 'for)
+                (cl-case type
+                  (list (list (setq target-index (make-symbol "target-cons"))
+                              'on target-var))
+                  (vector (list (setq target-index (gensym "target-i"))
+                                'to `(1- (length ,target-var))))))))
+    (funcall
+     (if do-not-compile #'identity #'byte-compile)
+     `(lambda ,(cons (setq f (make-symbol "f")) (cons target-var ss))
+        (cl-symbol-macrolet ((,(setq target-place (make-symbol "place"))
+                              ,(cl-case target-type
+                                 (list `(car ,target-index))
+                                 (vector `(aref ,target-var ,target-index)))))
+          (cl-loop ,@(nconc loop `(do (setf ,target-place (funcall ,f ,@xs))
+                                      ;; Bytecode looks better
+                                      ;; with finally return ..
+                                      ;; than with finally (cl-return ..).
+                                      finally return ,target-var))))))))
+
+(defun cl-map-into (target function &rest sequences)
+  "Common Lisp's map-into.
+
+Destructively modify TARGET to contain the results of applying
+FUNCTION to each element in the argument SEQUENCES in turn.
+
+TARGET and each element of SEQUENCES can each be either a list
+or a vector.  If TARGET and each element of SEQUENCES are not
+all the same length, the iteration terminates when the shortest sequence
+(of any of the SEQUENCES or the TARGET) is exhausted.  If TARGET
+is longer than the shortest element of SEQUENCES, extra elements
+at the end of TARGET are left unchanged."
+  (cl-check-type function function)
+  (apply
+   (let* ((sig (apply #'cl--compute-map-into-signature target sequences))
+          (small (< sig cl--map-into-max-small-signature)))
+     (cl-symbol-macrolet ((basic-cache (aref cl--map-into-mappers-array sig))
+                          (general-cache
+                           ;; TODO: Order alist entries for faster lookup
+                           ;; (note that we'll have to abandon alist-get then).
+                           (alist-get sig cl--map-into-mappers-alist
+                                      nil nil #'=)))
+       (or (and small basic-cache)
+           (and (not small) general-cache)
+           (let ((mapper (cl--make-map-into-mapper sig)))
+             (if small (setf basic-cache mapper)
+               (setf general-cache mapper))))))
+   function target sequences))
+
+
 ;;; Control structures.
 
 ;;;###autoload
-- 
2.32.0


^ permalink raw reply related	[flat|nested] 22+ messages in thread

end of thread, other threads:[~2021-10-26 12:52 UTC | newest]

Thread overview: 22+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2021-09-23 23:35 [PATCH] Add cl-map-into akater
2021-09-27 17:18 ` Stefan Monnier
2021-09-29 19:30   ` akater
2021-09-29 20:26     ` Stefan Monnier
2021-09-30  6:38       ` Bozhidar Batsov
2021-09-30 13:03         ` Adam Porter
2021-09-30 13:09           ` Bozhidar Batsov
2021-09-30 13:21             ` Adam Porter
2021-09-30 15:00               ` akater
2021-10-01 18:40         ` Stefan Monnier
2021-10-01 18:51           ` Eli Zaretskii
2021-10-01 19:04             ` Tassilo Horn
2021-10-01 20:52               ` Stefan Monnier
2021-10-01 22:08                 ` Glenn Morris
2021-10-02  3:53                   ` Stefan Monnier
2021-10-06 23:35   ` [PATCH] Add cl-map-into, revision 2 akater
2021-10-07  7:18     ` Eli Zaretskii
2021-10-07  8:24       ` akater
2021-10-07  9:00         ` Eli Zaretskii
2021-10-09  2:46       ` [PATCH] Add cl-map-into, revision 3 akater
2021-10-13 22:32         ` Stefan Monnier
2021-10-26 12:52           ` akater

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).