Help with recursive destructive function

Help with recursive destructive function

[Eric Abrahamsen]

So I'm revisiting my nemesis, eieio-persistent, and trying to write a
function for serializing data to disk in a generalized, data-agnostic
way.

The function needs to take a totally arbitrary list of data, and run a
function over it so that each element in the (possibly very nested) list
is tested and, if the test is positive, destructively replaced by a new
value.

I'd like to make it destructive because there could potentially be a
very large amount of data, and very few of the elements will actually
need to be altered, and I'm afraid copying enormous structures will be
slow.

I'm pretending that the job is to walk an arbitrary tree, and upcase any
and all strings in that tree. That's not the job, but I'm confident that
if I can make this work, it will be relatively simple to translate into
the actual job. (It will also have to handle hash-tables and vectors,
again I think that's all relatively straightforward.)

So here's my test data:

(setq test-data '("a" 1 "b" ("c" (2 ("d" . 3)) (4 . "e") "f")))

And the result I want (the destructive alteration of `test-data') is:

("A" 1 "B" ("C" (2 ("D" . 3)) (4 . "E") "F"))

The function I came up with always operates at one higher level of
nesting, because that's the only way to get a setf-able handle to
internal elements of the data structure: if you `mapc' a function over a
list, you can't use the resulting lambda argument symbol to set
anything. So I stay a level "up", in order to use setf, setcar, setcdr,
etc.

I did briefly consider `cl-symbol-macrolet', since it seems to be made
to address these sorts of problems, but this other solution more or less
came clear before I got a clear mental grasp of symbol-macrolet.

I'm hoping that someone might be willing to lend me some brain, and tell
me if I've done something conceptually wrong. Will this function do what
I expect it to do?

(defun walk (thing)
  (cond ((listp (cdr thing))
	 (dotimes (i (length thing))
	   (cond ((stringp (nth i thing))
		  (setf (nth i thing) (upcase (nth i thing))))
		 ((listp (nth i thing))
		  (walk (nth i thing))))))
	((consp thing)
	 (when (stringp (car thing))
	   (setcar thing (upcase (car thing))))
	 (when (stringp (cdr thing))
	   (setcdr thing (upcase (cdr thing)))))))

Re: Help with recursive destructive function

[Stefan Monnier]

>   (cond ((listp (cdr thing))
> 	 (dotimes (i (length thing))

You don't want that:

> 	   (cond ((stringp (nth i thing))
> 		  (setf (nth i thing) (upcase (nth i thing))))
> 		 ((listp (nth i thing))
> 		  (walk (nth i thing))))))

Each `nth i` will take time O(i) so you have an O(n^2) complexity right there.

You want to do something more like

    (let ((xs thing))
      (while (consp xs)
        (let ((x (car xs)))
          (cond
           ((stringp x) (setf (car xs) (upcase x)))
           ((listp x) (walk x)))
          (setq xs (cdr xs)))))


-- Stefan

Re: Help with recursive destructive function

[Michael Heerdegen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> You want to do something more like
>
>     (let ((xs thing))
>       (while (consp xs)
>         (let ((x (car xs)))
>           (cond
>            ((stringp x) (setf (car xs) (upcase x)))
>            ((listp x) (walk x)))
>           (setq xs (cdr xs)))))

`cl-loop' can do this out of the box (not recursively, though):

‘for VAR being the elements of-ref SEQUENCE’
     This clause iterates over a sequence, with VAR a ‘setf’-able
     reference onto the elements; see ‘in-ref’ above.

Exactly what he wants.

I'm not sure, however, if it's a good idea to use a recursive function
to do that.  Recursing on cdrs can soon hit Emacs limits for very long
lists (and Eric, remember all the nested quotes you will need to
traverse ;-) ).  I guess I would use an iterator: the definition would
still looks recursive, but the execution isn't problematic any more if
done right.


Michael.

Re: Help with recursive destructive function

[Michael Heerdegen]

I wrote:

> I guess I would use an iterator: the definition would still looks
> recursive, but the execution isn't problematic any more if done right.

Here is an example:

#+begin_src emacs-lisp
(iter-defun iter-tree-example (tree)
  (cl-loop for thing in-ref tree by #'cdr do
           (if (consp thing)
               (iter-yield-from (iter-tree-example thing))
             (iter-yield
              (ignore
               (when (stringp thing)
                 (cl-callf upcase thing)))))))

(let ((tree '("a" 1 ("b" "c" ("d")) "e")))
  (iter-do (_ (iter-tree-example tree)))
  tree)
==>
 ("A" 1
   ("B" "C"
    ("D"))
   "E")

(let ((huge-list (number-sequence 1 100000)))
  (setcdr (last huge-list) (cons "a" nil))
  (iter-do (_ (iter-tree-example huge-list)))
  (ignore huge-list))
|-- takes some time but doesn't crash
#+end_src

Yield values don't have any purpose but I guess without yielding you
would get no CPS rewrite but a standard recursive function that would be
problematic with the HUGE-LIST.


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> I wrote:
>
>> I guess I would use an iterator: the definition would still looks
>> recursive, but the execution isn't problematic any more if done right.

Thanks to both of you! This was some good food for thought. I made
Stefan's suggested change to my original function and it works fine. It
still looks ugly to me because I'm doing the same test-and-set in three
different places, but with sufficient poking I can probably get it all
inside the same loop.

All else being equal I prefer this more "basic" version, simply because
I understand everything that's happening in it. I haven't used `cl-loop'
before, but I assume it's not doing anything that

(while (consp thing)
  ...
  (setq thing (cdr thing))

Isn't doing? Oh, but then you wouldn't be able to use cl-callf directly
on thing.

Recursion is an issue, but the original version recurses on car, not
cdr, which I think (?) is much less of a problem. It went through your
huge-list with no trouble (and faster than the iterative version). I
suppose someone might have accumulated 801 levels of nested quotes in
their Gnus registry (god, I hope not), but otherwise I'm not sure it's a
worry.

On the third hand, if "bulletproof" is the goal, maybe it's best not to
risk it...

> #+begin_src emacs-lisp
> (iter-defun iter-tree-example (tree)
>   (cl-loop for thing in-ref tree by #'cdr do
>            (if (consp thing)
>                (iter-yield-from (iter-tree-example thing))
>              (iter-yield
>               (ignore
>                (when (stringp thing)
>                  (cl-callf upcase thing)))))))

> Yield values don't have any purpose but I guess without yielding you
> would get no CPS rewrite but a standard recursive function that would be
> problematic with the HUGE-LIST.

I guess this works because the calls to `iter-yield' and
`iter-yield-from' fully return from the function? Also, what does "CPS
rewrite" mean?

Thanks again,
Eric

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> I guess this works because the calls to `iter-yield' and
> `iter-yield-from' fully return from the function? Also, what does "CPS
> rewrite" mean?

"Continuation passing style".  You can google it.


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> I guess this works because the calls to `iter-yield' and
>> `iter-yield-from' fully return from the function? Also, what does "CPS
>> rewrite" mean?
>
> "Continuation passing style".  You can google it.

Ah, thanks. I know the concept, but not the acronym.

Re: Help with recursive destructive function

[Eric Abrahamsen]

On 05/05/18 17:41 PM, Michael Heerdegen wrote:
> I wrote:
>
>> I guess I would use an iterator: the definition would still looks
>> recursive, but the execution isn't problematic any more if done right.
>
> Here is an example:
>
> #+begin_src emacs-lisp
> (iter-defun iter-tree-example (tree)
>   (cl-loop for thing in-ref tree by #'cdr do
>            (if (consp thing)
>                (iter-yield-from (iter-tree-example thing))
>              (iter-yield
>               (ignore
>                (when (stringp thing)
>                  (cl-callf upcase thing)))))))
>
> (let ((tree '("a" 1 ("b" "c" ("d")) "e")))
>   (iter-do (_ (iter-tree-example tree)))
>   tree)
> ==>
>  ("A" 1
>    ("B" "C"
>     ("D"))
>    "E")

Oh hang on, this doesn't work for all cases: the "by #'cdr" prevents it
from hitting the cdr of cons cells:

(let ((tree '("c" (2 ("d" . 3)) (4 . "e") "f")))
  (iter-do (_ (iter-tree-example tree)))
  tree)

--> ("C" (2 ("D" . 3)) (4 . "e") "F")

The best I've been able to come up with is:

(defun useless (val)
  (while (consp val)
    (let ((head (car val)))
      (cond ((stringp head)
	     (setcar val (upcase head)))
	    ((listp head)
	     (useless head)))
      (when (stringp (cdr val))
	(setcdr val (upcase (cdr val))))
      (setq val (cdr val)))))

Recurses on car, and only repeats the test twice. I'd love to know if
that could be simplified...

Thanks again,
Eric

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> Oh hang on, this doesn't work for all cases: the "by #'cdr" prevents
> it from hitting the cdr of cons cells:
>
> (let ((tree '("c" (2 ("d" . 3)) (4 . "e") "f")))
>   (iter-do (_ (iter-tree-example tree)))
>   tree)
>
> --> ("C" (2 ("D" . 3)) (4 . "e") "F")

Not only that (it's easy to fix), but I also realized that this approach
doesn't circumvent the recursion issue.  But if your data is not
extremely deeply nested, recursion should not be such a problem.

> The best I've been able to come up with is:
>
> (defun useless (val)
>   (while (consp val)
>     (let ((head (car val)))
>       (cond ((stringp head)
> 	     (setcar val (upcase head)))
> 	    ((listp head)
> 	     (useless head)))
>       (when (stringp (cdr val))
> 	(setcdr val (upcase (cdr val))))
>       (setq val (cdr val)))))
>
> Recurses on car, and only repeats the test twice. I'd love to know if
> that could be simplified...

Looks ok to me in principle.


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> Oh hang on, this doesn't work for all cases: the "by #'cdr" prevents
>> it from hitting the cdr of cons cells:
>>
>> (let ((tree '("c" (2 ("d" . 3)) (4 . "e") "f")))
>>   (iter-do (_ (iter-tree-example tree)))
>>   tree)
>>
>> --> ("C" (2 ("D" . 3)) (4 . "e") "F")
>
> Not only that (it's easy to fix), but I also realized that this approach
> doesn't circumvent the recursion issue.  But if your data is not
> extremely deeply nested, recursion should not be such a problem.

Well... but... it might be deeply nested...

I'd like to have an iterative approach to work with as well -- it may
end up being slower, but if it's only a little slower, the slow-down is
worth the safety. If you have nothing to do on a Sunday afternoon (here)
and want to contribute a non-recursive iterative version, I would look
forward to testing!

Just saying,
Eric

Re: Help with recursive destructive function

[Clément Pit-Claudel]

On 2018-05-06 23:01, Eric Abrahamsen wrote:
> I'd like to have an iterative approach to work with as well

Here's a quick attempt:

    (defun deep-edit (f data)
      (let ((cur (list #'car #'setcar data))
            (stack (list (list #'cdr #'setcdr data))))
        (while cur
          (let* ((getter (car cur))
                 (setter (cadr cur))
                 (tree (caddr cur))
                 (subtree (funcall getter tree)))
            (funcall setter tree (funcall f subtree))
            (cond
             ((consp subtree)
              (push (list #'cdr #'setcdr subtree) stack)
              (setq cur (list #'car #'setcar subtree)))
             (t (setq cur (pop stack))))))))

    (setq test-data '("a" 1 "b" ("c" (2 ("d" . 3)) (4 . "e") "f")))

    (defun f (subtree)
      (if (stringp subtree)
          (upcase subtree)
        subtree))

    (deep-edit #'f test-data)

… I'd actually tend to write it like this, if pcase is OK:

    (defun deep-edit (f data)
      (let ((cur `(car setcar ,data))
            (stack `((cdr setcdr ,data))))
        (while (or cur stack)
          (pcase-let* ((`(,getter ,setter ,cell) cur)
                       (subtree (funcall getter cell)))
            (funcall setter cell (funcall f subtree))
            (cond
             ((consp subtree)
              (push `(cdr setcdr ,subtree) stack)
              (setq cur `(car setcar ,subtree)))
             (t (setq cur (pop stack))))))))

Let me know if it needs clarification.  I haven't tested it much, either.

Clément.

Re: Help with recursive destructive function

[Michael Heerdegen]

Clément Pit-Claudel <cpitclaudel@gmail.com> writes:

>     (defun deep-edit (f data)
>       (let ((cur `(car setcar ,data))
>             (stack `((cdr setcdr ,data))))
>         (while (or cur stack)
>           (pcase-let* ((`(,getter ,setter ,cell) cur)
>                        (subtree (funcall getter cell)))
>             (funcall setter cell (funcall f subtree))
>             (cond
>              ((consp subtree)
>               (push `(cdr setcdr ,subtree) stack)
>               (setq cur `(car setcar ,subtree)))
>              (t (setq cur (pop stack))))))))

Well done!

A random example and two corner cases seem to work ok:

(defun edit-elt (thing)
  (if (stringp thing) (upcase thing) thing))

(let ((tree '("c" (2 ("d" . 3)) (4 . "e") "f" (("g" . "h")))))
  (deep-edit #'edit-elt tree)
  tree)
==>
 ("C"
   (2
    ("D" . 3))
   (4 . "E")
   "F"
   (("G" . "H")))

(let ((huge-list (number-sequence 1 100000)))
  (setcdr (last huge-list) (cons "a" nil))
  (deep-edit #'edit-elt huge-list))
|-- no crash

(let ((deeply-nested-list (list nil)))
  (let ((pointer deeply-nested-list))
    (dotimes (_ 100000)
      (setf (car pointer) (list nil)
            pointer (car pointer)))
    (setf (car pointer) "a"))
  (deep-edit #'edit-elt deeply-nested-list))
|- no crash


Michael.

Re: Help with recursive destructive function

[Stefan Monnier]

>     (defun deep-edit (f data)
>       (let ((cur (list #'car #'setcar data))
>             (stack (list (list #'cdr #'setcdr data))))
>         (while cur
>           (let* ((getter (car cur))
>                  (setter (cadr cur))
>                  (tree (caddr cur))
>                  (subtree (funcall getter tree)))
>             (funcall setter tree (funcall f subtree))
>             (cond
>              ((consp subtree)
>               (push (list #'cdr #'setcdr subtree) stack)
>               (setq cur (list #'car #'setcar subtree)))
>              (t (setq cur (pop stack))))))))

BTW, a "cleaner" (tho less efficient) way uses gv-ref:

    (defun deep-edit (f data)
      (let ((cur (gv-ref (car data)))
            (stack (list (gv-ref (cdr data)))))
        (while (or cur stack)
          ;; Probably should use (cl-callf f (gv-deref cell)).
          (pcase (setf (gv-deref cur) (funcall f (gv-deref cell)))
            ((and (pred consp) subtree)
              (push (gv-ref (cdr subtree)) stack)
              (setq cur (gv-ref (car subtree))))
            (t (setq cur (pop stack)))))))

tho the above has a bug when cur is nil, so it won't work as is.


        Stefan "it'd be great to be able to represent a gv-ref as
                a 3-element tuple so as to make it as efficient as your
                code, tho"

Re: Help with recursive destructive function

[Eric Abrahamsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>     (defun deep-edit (f data)
>>       (let ((cur (list #'car #'setcar data))
>>             (stack (list (list #'cdr #'setcdr data))))
>>         (while cur
>>           (let* ((getter (car cur))
>>                  (setter (cadr cur))
>>                  (tree (caddr cur))
>>                  (subtree (funcall getter tree)))
>>             (funcall setter tree (funcall f subtree))
>>             (cond
>>              ((consp subtree)
>>               (push (list #'cdr #'setcdr subtree) stack)
>>               (setq cur (list #'car #'setcar subtree)))
>>              (t (setq cur (pop stack))))))))
>
> BTW, a "cleaner" (tho less efficient) way uses gv-ref:
>
>     (defun deep-edit (f data)
>       (let ((cur (gv-ref (car data)))
>             (stack (list (gv-ref (cdr data)))))
>         (while (or cur stack)
>           ;; Probably should use (cl-callf f (gv-deref cell)).
>           (pcase (setf (gv-deref cur) (funcall f (gv-deref cell)))
>             ((and (pred consp) subtree)
>               (push (gv-ref (cdr subtree)) stack)
>               (setq cur (gv-ref (car subtree))))
>             (t (setq cur (pop stack)))))))
>
> tho the above has a bug when cur is nil, so it won't work as is.

All this went very rapidly over my head, but I guess that's what I was
hoping for! I'll wait and see if you all work this through any further,
then play around with the results, and update bug #29541 with a new patch.

Thanks!

Eric

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> All this went very rapidly over my head, but I guess that's what I was
> hoping for! I'll wait and see if you all work this through any further,

What's left to do?  Arrays?  What else?


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> All this went very rapidly over my head, but I guess that's what I was
>> hoping for! I'll wait and see if you all work this through any further,
>
> What's left to do?  Arrays?  What else?

Arrays, hash tables, backwards compatibility, removing spurious
type-checking, doing a non-destructive version for writing (the
destructive one is just for reading), and deciding how to unambiguously
handle the "lists versus lists-as-objects" problem.

These are the sorts of things I can typically handle (sometimes even
without bugs!), whereas Clement's (or your, or Stefan's) function
isn't...

Eric

Re: Help with recursive destructive function

[Clément Pit-Claudel]

On 2018-05-08 14:42, Eric Abrahamsen wrote:
> These are the sorts of things I can typically handle (sometimes even
> without bugs!), whereas Clement's (or your, or Stefan's) function
> isn't...

I'm happy to clarify obscure bits in that function, if you point them out :)

Clément.

Re: Help with recursive destructive function

[Eric Abrahamsen]

Clément Pit-Claudel <cpitclaudel@gmail.com> writes:

> On 2018-05-08 14:42, Eric Abrahamsen wrote:
>> These are the sorts of things I can typically handle (sometimes even
>> without bugs!), whereas Clement's (or your, or Stefan's) function
>> isn't...
>
> I'm happy to clarify obscure bits in that function, if you point them out :)

It's okay, if I put my finger on the screen and move my lips while I
read, I can more or less grok what's happening -- I'm telling myself "it
stacks data rather than stacking function calls", and that's good
enough.

I don't think it's a problem. I'll put comments in there, and while it
still seems obscure at first glance, at least it's short :)

Thank you!

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> These are the sorts of things I can typically handle (sometimes even
> without bugs!), whereas Clement's (or your, or Stefan's) function
> isn't...

I tweaked it a bit and extended the idea for arrays.  Hope the comments
are helpful.  Uses seq.el and cl-lib.


#+begin_src emacs-lisp
;; -*- lexical-binding: t -*-

(defun deep-edit (edit-fun data)
  ;; DATA is the structure to process.
  ;;
  ;; EDIT-FUN is a function accepting one argument THING that returns
  ;; non-nil when THING is something to be replaced.  The non-nil
  ;; return value should be a function that when called with the THING as
  ;; argument returns the replacement for THING.
  ;; Example: (lambda (thing) (and (stringp thing) #'upcase)) as
  ;; EDIT-FUN would cause all strings being replaced with their upcased
  ;; version.
  (let ((stack `((identity ignore ,data))))
    (while stack
      (pcase-let* ((`(,getter ,setter ,cell) (pop stack))
                   (current                  (funcall getter cell))
                   (modify-fun               (funcall edit-fun current)))
        (cond
         ;; 1. When we should replace CURRENT, do it
         (modify-fun
          (funcall setter cell (funcall modify-fun current)))
         ;; FIXME: Do hash-tables fit here?

         ;; 2. Check whether we need to traverse CURRENT
         ((consp current)
          (cl-callf2 append
              `((car setcar ,current)
                (cdr setcdr ,current))
              stack))
         ((and (arrayp current) (not (stringp current)))
          (cl-callf2 append
              (let ((i -1))
                (seq-map
                 (lambda (_)
                   (let ((j (cl-incf i)))
                     `(,(lambda (x)   (aref x j))
                       ,(lambda (x v) (aset x j v))
                       ,current)))
                 current))
              stack)))))))

;; Example to try:
(let ((tree '("a" "b" "c"
              (2 ("d" . 3))
              (4 . "e")
              "f"
              (("g" . "h")
               (["i" "j"
                 ("k" "l")
                 nil
                 []])))))
  (deep-edit
   (lambda (thing) (and (stringp thing) #'upcase))
   tree)
  tree)
#+end_src


Michael.

Re: Help with recursive destructive function

[Michael Heerdegen]

I <michael_heerdegen@web.de> write:

> I tweaked it a bit and extended the idea for arrays.  Hope the comments
> are helpful.  Uses seq.el and cl-lib.

Here is a new version.  Changes:

- Uses gv places as references.

- Handles hash tables.  Therefore defines a place expressions to make
hash table keys setf'able (because I guess there are cases where you
need to modify hash table keys and not only values).

- Distinguishes modifying vs processing things.  Now the stack only
contains trees to process instead of refs.


#+begin_src emacs-lisp
;; -*- lexical-binding: t -*-

(eval-when-compile (require 'cl-lib))
(require 'seq)

(defun deep-edit-hash-key (key table)
  "Special place to make hash-table keys setf'able."
  (ignore table)
  key)

(gv-define-setter deep-edit-hash-key (new-key key table)
  (let ((val (make-symbol "val")))
    `(let ((,val (gethash ,key ,table)))
       (remhash ,key ,table)
       (puthash ,new-key ,val ,table))))


(defun deep-edit (needs-edit-predicate should-traverse-predicate data)
  ;; DATA is the structure to process.
  ;;
  ;; NEEDS-EDIT-PREDICATE is a function accepting one argument THING
  ;; that returns non-nil when THING is something to be replaced.  The
  ;; non-nil return value should be a function that when called with the
  ;; THING as argument returns the replacement for THING.  Example:
  ;; (lambda (thing) (and (stringp thing) #'upcase)) as
  ;; NEEDS-EDIT-PREDICATE would cause all strings to be replaced with
  ;; the upcased version.
  ;;
  ;; SHOULD-TRAVERSE-PREDICATE should return non-nil when the argument
  ;; needs to be traversed.
  (let ((stack (list data)))
    (cl-flet ((handle-refs
               (lambda (refs)
                 (dolist (ref refs)
                   (let ((val (gv-deref ref)))
                     (if-let ((modify-fun (funcall needs-edit-predicate val)))
                         (cl-callf (lambda (x) (funcall modify-fun x))
                             (gv-deref ref))
                       (when (funcall should-traverse-predicate val)
                         (push val stack))))))))
      (while stack
        (let ((current (pop stack)))
          (cond
           ((consp current)
            (handle-refs `(,(gv-ref (car current))
                           ,(gv-ref (cdr current)))))
           ((and (arrayp current) (not (stringp current)))
            (handle-refs
             (mapcar (lambda (idx) (gv-ref (aref current idx)))
                     (number-sequence 0 (1- (length current))))))
           ((hash-table-p current)
            (let ((refs '()))
              (maphash (lambda (key _val)
                         ;; Order matters here!
                         (push (gv-ref (gethash key current))            refs)
                         (push (gv-ref (deep-edit-hash-key key current)) refs))
                       current)
              (handle-refs (nreverse refs))))))))))

;; Example to try:
(let* ((a-hash-table (make-hash-table))
       (tree `("a" "b" "c"
               (2 ("d" . 3))
               (4 . "e")
               "f"
               (("g" . "h")
                (["i" "j"
                  ("k" "l")
                  nil
                  []
                  ,a-hash-table])))))
  (puthash 'a "a"          a-hash-table)
  (puthash 'b (list 2 "b") a-hash-table)
  (puthash "c" 3           a-hash-table)
  (puthash '(4 "d") "ddd"  a-hash-table)
  (deep-edit
   (lambda (thing) (and (stringp thing) #'upcase))
   (lambda (thing) (or (consp thing)
                       (arrayp thing)
                       (hash-table-p thing)))
   tree)
  tree)
#+end_src


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

On 05/10/18 19:08 PM, Michael Heerdegen wrote:
> I <michael_heerdegen@web.de> write:
>
>> I tweaked it a bit and extended the idea for arrays.  Hope the comments
>> are helpful.  Uses seq.el and cl-lib.
>
> Here is a new version.  Changes:
>
> - Uses gv places as references.

This is great, and I really like the use of gv -- morally it seems like
the right tool. I will have time this weekend to apply all this to eieio-persistent.

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> This is great, and I really like the use of gv -- morally it seems like
> the right tool.

Didn't profile speed, however - hope it's good enough.

> I will have time this weekend to apply all this to eieio-persistent.

Where can I have a look at your work?


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> This is great, and I really like the use of gv -- morally it seems like
>> the right tool.
>
> Didn't profile speed, however - hope it's good enough.

I'm trying to break the changes into discrete steps, and benchmark each
step, so hopefully we'll know.

>> I will have time this weekend to apply all this to eieio-persistent.
>
> Where can I have a look at your work?

Nowhere yet -- I got partway through this, and ran up against a dumb
problem maybe you can help me with.

For backwards compatibility, we need to be able to handle lists that are
quoted, or that start with the symbol `list'. This will sound familiar
to you... In the non-destructive version, it was easy enough just to
return (cdr thing) instead of thing.

In the destructive version, this means that `handle-refs' would need to
first edit and *then* traverse the cons, which is not what it's set up
to do, obviously. I could probably cheat and move the backward
compatibility into some other part of `deep-edit' itself, but I was
trying to avoid that because that function could be useful elsewhere as
part of the general library.

Here's what the problem actually looks like:

#+BEGIN_SRC elisp
  (defun edit-func (proposed-value)
    (cond ((and (consp proposed-value)
                (eq (car proposed-value) 'list))
           #'cdr)
          ((and (consp proposed-value)
                (eq (car proposed-value) 'quote))
           #'cadr)
          ((stringp proposed-value)
           #'upcase)
          (t nil)))

  (let ((tree '("b" '((first ("one" "two" "three"))
                      (second ("four" "five" "six")))
                "c" (list "seven" "eight" "nine"))))
    (deep-edit #'edit-func
               (lambda (thing) (consp thing))
               tree)
    tree)
#+END_SRC

Do you have any good ideas about this?

Thanks again,
Eric

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> For backwards compatibility, we need to be able to handle lists that are
> quoted, or that start with the symbol `list'. This will sound familiar
> to you... In the non-destructive version, it was easy enough just to
> return (cdr thing) instead of thing.

What will this code do when the saved list was really quoted, or was a
list with the symbol list as first element?  Wouldn't the backward
compatible version cause errors?

> In the destructive version, this means that `handle-refs' would need to
> first edit and *then* traverse the cons, which is not what it's set up
> to do, obviously. I could probably cheat and move the backward
> compatibility into some other part of `deep-edit' itself, but I was
> trying to avoid that because that function could be useful elsewhere as
> part of the general library.

My implementation so far doesn't perfectly fit that case (as you
noticed).

Do you expect something occurring like '1 or (list) - i.e. cases where
the remaining thing is an atom (like 1 and nil above)?

If not, I would just tweak `handle-refs' so that it calls the modify
function _and_ additionally pushes the replacement to the stack when
some condition is met.  You could make it so that `edit-func' returns a
special value for this case, like in

#+begin_src emacs-lisp
(defun edit-func (proposed-value)
    (cond ((and (consp proposed-value)
                (eq (car proposed-value) 'list))
           (list t #'cdr))
          ((and (consp proposed-value)
                (eq (car proposed-value) 'quote))
           (list t #'cadr))
          ((stringp proposed-value)
           #'upcase)
          (t nil)))
#+end_src

where (list t FUN) would mean that we want to modify the value with FUN
and additionally push the resulting (remaining) tree to the stack.  Not
much magic here...


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

On 05/15/18 01:16 AM, Michael Heerdegen wrote:
> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> For backwards compatibility, we need to be able to handle lists that are
>> quoted, or that start with the symbol `list'. This will sound familiar
>> to you... In the non-destructive version, it was easy enough just to
>> return (cdr thing) instead of thing.
>
> What will this code do when the saved list was really quoted, or was a
> list with the symbol list as first element?  Wouldn't the backward
> compatible version cause errors?

Yup. But no more errors than it already would. This will also be an
issue when I try to unambiguously identify lists-that-should-be-objects.
The only surefire way around this that I can think of is writing an
eieio-persistent version number into the files.

>> In the destructive version, this means that `handle-refs' would need to
>> first edit and *then* traverse the cons, which is not what it's set up
>> to do, obviously. I could probably cheat and move the backward
>> compatibility into some other part of `deep-edit' itself, but I was
>> trying to avoid that because that function could be useful elsewhere as
>> part of the general library.
>
> My implementation so far doesn't perfectly fit that case (as you
> noticed).
>
> Do you expect something occurring like '1 or (list) - i.e. cases where
> the remaining thing is an atom (like 1 and nil above)?

Yes -- there's a check in the current code precisely for the (list)
case.

> If not, I would just tweak `handle-refs' so that it calls the modify
> function _and_ additionally pushes the replacement to the stack when
> some condition is met.  You could make it so that `edit-func' returns a
> special value for this case, like in
>
> #+begin_src emacs-lisp
> (defun edit-func (proposed-value)
>     (cond ((and (consp proposed-value)
>                 (eq (car proposed-value) 'list))
>            (list t #'cdr))
>           ((and (consp proposed-value)
>                 (eq (car proposed-value) 'quote))
>            (list t #'cadr))
>           ((stringp proposed-value)
>            #'upcase)
>           (t nil)))
> #+end_src
>
> where (list t FUN) would mean that we want to modify the value with FUN
> and additionally push the resulting (remaining) tree to the stack.  Not
> much magic here...

I had been treating it as magic :) I'll try to loosen up a bit and
experiment with something that might also handle the (list) case.

Re: Help with recursive destructive function

[Eric Abrahamsen]

On 05/15/18 01:16 AM, Michael Heerdegen wrote:
> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> For backwards compatibility, we need to be able to handle lists that are
>> quoted, or that start with the symbol `list'. This will sound familiar
>> to you... In the non-destructive version, it was easy enough just to
>> return (cdr thing) instead of thing.
>
> What will this code do when the saved list was really quoted, or was a
> list with the symbol list as first element?  Wouldn't the backward
> compatible version cause errors?

After weeks of avoiding this, I'm nearly there. This version does
everything I need it to, EXCEPT I have somehow lost the ability to
handle single-atom data, which was the whole point of passing in a
gv-ref. I don't understand why, it seemed to be working fine, but I
switched to cl-labels and maybe changed some other things (I didn't keep
the intermediate version), and now it just doesn't do it. Would you help
me take one more look at this?

It also doesn't handle '(list), but those cases are rare and occur at
top-level, so I can take care of them in pre-processing.

#+BEGIN_SRC elisp

(defun deep-edit (data edit-p traverse-p)
  (let ((stack (list (gv-deref data))))
    (cl-labels ((handle-refs
                 (refs)
                 (dolist (ref refs)
                   (let* ((val (gv-deref ref))
                          (edit (when val (funcall edit-p val))))
                     (when (car edit)
                       (cl-callf (lambda (x) (funcall (car edit) x))
                           (gv-deref ref))
                       (when (cdr edit)
                         (handle-refs (list ref))))
                     (when (funcall traverse-p (gv-deref ref))
                       (push (gv-deref ref) stack))))))
      (while stack
        (let ((current (pop stack)))
          (cond
           ((consp current)
            (handle-refs `(,(gv-ref (car current))
                           ,(gv-ref (cdr current)))))
           ((and (arrayp current) (not (stringp current)))
            (handle-refs
             (mapcar (lambda (idx) (gv-ref (aref current idx)))
                     (number-sequence 0 (1- (length current))))))
           ((hash-table-p current)
            (let ((refs '()))
              (maphash (lambda (key _val)
                         ;; Order matters here!
                         (push (gv-ref (gethash key current)) refs)
                         (push (gv-ref (deep-edit-hash-key key current))
                               refs))
                       current)
              (handle-refs (nreverse refs))))))))))

(let ((tree '("one" two ''(three "four" (list "five")))))
 (deep-edit
  (gv-ref tree)
  (lambda (thing)
    (cond ((consp thing)
           (pcase (car thing)
             ('list (cons #'cdr t))
             ('quote (cons #'cadr t))))
          ((stringp thing)
           (cons #'upcase nil))))
  (lambda (thing)
    (consp thing)))
 tree)

#+END_SRC

The above works, yet if I change `tree' to be a plain string "one", it
isn't transformed. I just can't see why.

Eric

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> After weeks of avoiding this, I'm nearly there. This version does
> everything I need it to, EXCEPT I have somehow lost the ability to
> handle single-atom data, which was the whole point of passing in a
> gv-ref. I don't understand why [...]

Did this really ever work like this?  Because, you said you want to
alter the given data.  If you pass the function a string, and you really
want to alter that string, you can't just call `upcase' because that
returns a new string.  You would have to write a function that alters
the string itself.  You could also return a new string, but then there
is no need for `gv-ref'.


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> After weeks of avoiding this, I'm nearly there. This version does
>> everything I need it to, EXCEPT I have somehow lost the ability to
>> handle single-atom data, which was the whole point of passing in a
>> gv-ref. I don't understand why [...]
>
> Did this really ever work like this?  Because, you said you want to
> alter the given data.  If you pass the function a string, and you really
> want to alter that string, you can't just call `upcase' because that
> returns a new string.  You would have to write a function that alters
> the string itself.  You could also return a new string, but then there
> is no need for `gv-ref'.

Pretty sure it did work, in effect it was doing this:

(defun upcase-ref (ref)
  (cl-callf upcase (gv-deref ref)))

(let ((tree "one"))
  (upcase-ref (gv-ref tree))
  tree)

Which for some reason the larger function is not doing any more. I'm not
sure if it's necessary, but for instance I will have to be able to
replace a list (representing an object constructor) into an actual
object, which I assume is equivalent to this string upcase example.

I also realized that I cleverly replaced cl-flet with cl-labels so that
I could recursively transform values that need to be transformed
multiple times... forgetting that the whole point of this was to make it
iterative, not recursive. I suppose I can go back to cl-flet and a
`while' loop.

I'm kind of regretting getting myself stuck in this quagmire!

Eric

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> Pretty sure it did work, in effect it was doing this:
>
> (defun upcase-ref (ref)
>   (cl-callf upcase (gv-deref ref)))
>
> (let ((tree "one"))
>   (upcase-ref (gv-ref tree))
>   tree)

Ok.  This changes the binding of the variable named "tree", but not the
value.  The old value is gone.  I guess this is good enough for what you
want.

> Which for some reason the larger function is not doing any more. I'm not
> sure if it's necessary, but for instance I will have to be able to
> replace a list (representing an object constructor) into an actual
> object, which I assume is equivalent to this string upcase example.

The first thing `deep-edit' does when binding `stack' is to dereference
the passed reference.  The reference itself is never used, so its
"target" can't be changed.


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

On 05/14/18 16:27 PM, Michael Heerdegen wrote:
> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> This is great, and I really like the use of gv -- morally it seems like
>> the right tool.
>
> Didn't profile speed, however - hope it's good enough.
>
>> I will have time this weekend to apply all this to eieio-persistent.
>
> Where can I have a look at your work?

This is progressing terribly slowly, in part because of business trips,
and in part because obviously I fundamentally don't understand how
values work in elisp.

I wanted to tweak the process a bit: object slots look like: '(:slot1
"val1" :slot2 "val2"), and instead of dumping that whole list into
deep-edit, I want to call `deep-edit' once per *value*. In part that
would reduce the total number of iterations, but mostly it would make
the process more robust, avoiding a bug I hit while testing on an EBDB
database.

#+BORING_BACKGROUND
One of the slots in an EBDB database is :record-class, which defaults to
'ebdb-person-record. Let's pretend a database is created with the slots
'(:file "foo.txt" :record-class ebdb-person-record :state broken).

As `deep-edit' cdr's down the slot list, it eventually ends up with
'(ebdb-person-record :state broken), and tries to make an object out of
that, which fails.

The real solution is to have a more explicit tag saying "this should be
an object", but we don't have that now, and more importantly we won't
when it comes to reading older persistence files in a
backwards-compatible fashion.
#+END

I can't for the life of me pass values to `deep-edit' so that the
changes are reliably reflected in the original structure of "slots".
Here's a simple baseline that works correctly:

#+BEGIN src elisp
(let ((lst '(:one "one" :two ("some" "strings") :three "three")))
  (deep-edit (lambda (x) (and (stringp x) #'upcase))
	     #'consp
	     lst)
  lst)
#+END
=> (:one "ONE" :two ("SOME" "STRINGS") :three "THREE")

Then, naively, I call `deep-edit' on every other list item:

#+BEGIN src elisp
(let* ((lst '(:one "one" :two ("some" "strings") :three "three"))
       (len (length lst))
       (idx 1))
  (while (< idx len)
    (deep-edit (lambda (x) (and (stringp x) #'upcase))
	       #'consp
	       (nth idx lst))
    (cl-incf idx 2))
  lst)
#+END
=> (:one "one" :two ("SOME" "STRINGS") :three "three")

That only worked for consp values. I don't understand this: `nth' is
implemented in C as (car (nthcdr)), and nthcdr looks to me like it's
producing a chunk of the underlying list structure. So does car of
nthcdr return a simple value (ie something un-setf-able) if car is an
atom, but something still connected to the original list structure
(setf-able) if car is a cons cell?

If that's the case, I'm not sure how to reliably pass a settable value
in to `deep-edit'. We could pass gv-refs into `deep-edit', in which case
it would have to check values to see if they're already references or
not (or gv-ref itself could do that check).

I can't think of anything else. But more importantly, I'd like to know
why I'm wrong about `nth' here...

Thanks,
Eric

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> [...]
> That only worked for consp values. I don't understand this: `nth' is
> implemented in C as (car (nthcdr)), and nthcdr looks to me like it's
> producing a chunk of the underlying list structure. So does car of
> nthcdr return a simple value (ie something un-setf-able)

Yes, setf'able are only (some) expressions (the "place expressions"),
not plain values.  If you evaluate a (place) expression (functions
evaluate their arguments), you loose the connection to the place.
That's why `setf', `cl-callf', `pop' e.a. are necessarily macros.

(A suggesting analogy with quantum states that collapse when measured:
places collapse to values when passed to a function.)

> if car is an atom, but something still connected to the original list
> structure (setf-able) if car is a cons cell?

No, it's still not setf-able (try to replace the cons with an integer,
for example).  It's only that the original list and this cons share data
(like so often in Lisp), so if you setf the car of this cons, the
content of the original list is also altered.  If the car of this cons
was a string, and you use a destructive string operation on it, the
original list also "changes" (in this sense).  Nothing special about
setf here.

> If that's the case, I'm not sure how to reliably pass a settable value
> in to `deep-edit'. We could pass gv-refs into `deep-edit',

That would also be my first naive idea.

> In which case it would have to check values to see if they're already
> references or not (or gv-ref itself could do that check).

It's easy to change the function to accept gv-refs instead of values,
since it already uses them internally.  But AFAIK there is no test if
some value is a `gv-ref'.  Do you need deep-edit to also accept plain
values?  Then you could just pass values V as (list :value V) to make
the cases distinguishable.


Regards,

Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> [...]
>> That only worked for consp values. I don't understand this: `nth' is
>> implemented in C as (car (nthcdr)), and nthcdr looks to me like it's
>> producing a chunk of the underlying list structure. So does car of
>> nthcdr return a simple value (ie something un-setf-able)
>
> Yes, setf'able are only (some) expressions (the "place expressions"),
> not plain values.  If you evaluate a (place) expression (functions
> evaluate their arguments), you loose the connection to the place.
> That's why `setf', `cl-callf', `pop' e.a. are necessarily macros.
>
> (A suggesting analogy with quantum states that collapse when measured:
> places collapse to values when passed to a function.)

Right, "places collapse to values when passed to a function". I
understood this intuitively, but was confounded by this sort of thing:

(defun my-set-car (thing)
  (setcar thing 'ferrari))

(let ((tree '(1 volvo pinto)))
  (my-set-car tree)
  tree) => (ferrari volvo pinto)

Where it sure looks like the tree has retained its identity and
integrity throughout the operation. But this is only a side-effect of
the fact that lisp re-uses structures (I think there was a bug report
not long ago about identical strings getting re-used in unexpected
ways). And all the n* functions like `nconc' and `nreverse' only act on
lists. Okay, I think this is sinking in.

[...]

>> If that's the case, I'm not sure how to reliably pass a settable value
>> in to `deep-edit'. We could pass gv-refs into `deep-edit',
>
> That would also be my first naive idea.
>
>> In which case it would have to check values to see if they're already
>> references or not (or gv-ref itself could do that check).
>
> It's easy to change the function to accept gv-refs instead of values,
> since it already uses them internally.  But AFAIK there is no test if
> some value is a `gv-ref'.  Do you need deep-edit to also accept plain
> values?  Then you could just pass values V as (list :value V) to make
> the cases distinguishable.

I think this function could be useful in many situations, so I'd like to
make it fairly general -- gv-refs or values.

How would you feel about gv-ref itself doing a check?

(if (and (eq 'closure (caar place))
         (eq 'closure (cadr place)))
    place
  (gv-letplace ...etc...)

Too hacky?

Eric

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> How would you feel about gv-ref itself doing a check?
>
> (if (and (eq 'closure (caar place))
>          (eq 'closure (cadr place)))
>     place
>   (gv-letplace ...etc...)
>
> Too hacky?

`functionp' would probably better, since it's not forbidden to be used
in dynamically bound Lisp.  Most place expressions will not contain
something functionp I think.  Using a unique tag would probably be
cleaner.

I'm not sure if having `gv-ref-p' would be useful, I can imagine that it
could, but have myself used this only once or twice.


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> How would you feel about gv-ref itself doing a check?
>>
>> (if (and (eq 'closure (caar place))
>>          (eq 'closure (cadr place)))
>>     place
>>   (gv-letplace ...etc...)
>>
>> Too hacky?
>
> `functionp' would probably better, since it's not forbidden to be used
> in dynamically bound Lisp.  Most place expressions will not contain
> something functionp I think.  Using a unique tag would probably be
> cleaner.

I'm conscious of having set out to fix an annoying bug in the Gnus
registry, then moving on to re-write most of eieio-persistent, and now
apparently mucking about in the guts of gv-ref/gv-defer, which three
weeks ago I didn't even know existed. Mission creep is real! Maybe we
should be opening a separate bug report so other people can comment on
adding a unique tag.

> I'm not sure if having `gv-ref-p' would be useful, I can imagine that it
> could, but have myself used this only once or twice.

An intermediate solution could be to write a `gv-ref-p' inline that's
only meant for use with `deep-edit'.

Eric

Re: Help with recursive destructive function

[Eric Abrahamsen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> Michael Heerdegen <michael_heerdegen@web.de> writes:
>
>> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>>
>>> How would you feel about gv-ref itself doing a check?
>>>
>>> (if (and (eq 'closure (caar place))
>>>          (eq 'closure (cadr place)))
>>>     place
>>>   (gv-letplace ...etc...)
>>>
>>> Too hacky?
>>
>> `functionp' would probably better, since it's not forbidden to be used
>> in dynamically bound Lisp.  Most place expressions will not contain
>> something functionp I think.  Using a unique tag would probably be
>> cleaner.
>
> I'm conscious of having set out to fix an annoying bug in the Gnus
> registry, then moving on to re-write most of eieio-persistent, and now
> apparently mucking about in the guts of gv-ref/gv-defer, which three
> weeks ago I didn't even know existed. Mission creep is real! Maybe we
> should be opening a separate bug report so other people can comment on
> adding a unique tag.
>
>> I'm not sure if having `gv-ref-p' would be useful, I can imagine that it
>> could, but have myself used this only once or twice.
>
> An intermediate solution could be to write a `gv-ref-p' inline that's
> only meant for use with `deep-edit'.

Also, this isn't terribly relevant but while fooling around I came upon
`cl-nsublis' in "cl-seq", which is sort of similar to what we're doing
here, except that:

- It is recursive (on car) instead of iterative.
- It destructively replaces elements based on an alist lookup: if an
  element matches an alist key, it's replaced with the alist value.

It's not quite applicable here, but I was interested to find something
so close to requirements. Tbh I don't think an alist lookup is very
useful. I suppose with an appropriate :test you could still have a
refined test, but the replacement is still a blunt instrument. Nearly
there, but not quite...

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> - It is recursive (on car) instead of iterative.

Yes, that's not good in your use case.

> - It destructively replaces elements based on an alist lookup: if an
>   element matches an alist key, it's replaced with the alist value.

It also handles only lists - it can't traverse arrays, hash tables,
structs, etc.  If you give that all up, however, `cl-sublis' is the
canonical thing you get.

Note that "destructively" doesn't necessarily mean you can reuse the
original structure (which is what you want).  In this case the
implementation seems to guarantee that, however.


Michael.

Re: Help with recursive destructive function

[Eric Abrahamsen]

On 06/07/18 01:30 AM, Michael Heerdegen wrote:
> Eric Abrahamsen <eric@ericabrahamsen.net> writes:
>
>> - It is recursive (on car) instead of iterative.
>
> Yes, that's not good in your use case.
>
>> - It destructively replaces elements based on an alist lookup: if an
>>   element matches an alist key, it's replaced with the alist value.
>
> It also handles only lists - it can't traverse arrays, hash tables,
> structs, etc.  If you give that all up, however, `cl-sublis' is the
> canonical thing you get.

Well, if the alist value was allowed to be a callable, we could get all
that (not saying that's a good idea, I'm just saying it's awfully close).

> Note that "destructively" doesn't necessarily mean you can reuse the
> original structure (which is what you want).  In this case the
> implementation seems to guarantee that, however.

I thought that was exactly what "destructive" meant!?

Anyhoo, I think I've got a close enough handle on this to make the next
steps, thanks again for all your help.

Eric

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> I thought that was exactly what "destructive" meant!?

Sometimes, but in general it only means that the original data can be
changed (destroyed) for better performance.  See

  (info "(elisp) Sets And Lists")

and the description of `delq' for some background.


Michael.

Re: Help with recursive destructive function

[Michael Heerdegen]

Eric Abrahamsen <eric@ericabrahamsen.net> writes:

> [...] Maybe we should be opening a separate bug report so other people
> can comment on adding a unique tag.

I'm not so super convinced that it would be so useful.  At least in your
case, there's a simple workaround.


Michael.

Re: Help with recursive destructive function

[Stefan Monnier]

> I think this function could be useful in many situations, so I'd like to
> make it fairly general -- gv-refs or values.

Why "or values"?  It's easy for the caller to wrap its argument in
`(gv-ref ...)` and lets the function be more efficient.

> How would you feel about gv-ref itself doing a check?
>
> (if (and (eq 'closure (caar place))
>          (eq 'closure (cadr place)))
>     place
>   (gv-letplace ...etc...)
>
> Too hacky?

Beside the obvious problem of checking equality vs `closure` which will
break down with byte-compiled code, the more serious problem is that
this code is run at macro-expansion time, not at run-time, so `place` is
a Elisp *expression* and not an Elisp *value*.

IOW your test will only trigger when the *source code* is of the form

    (gv-ref ((closure ...) . (closure ...)))


-- Stefan

Re: Help with recursive destructive function

[Eric Abrahamsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I think this function could be useful in many situations, so I'd like to
>> make it fairly general -- gv-refs or values.
>
> Why "or values"?  It's easy for the caller to wrap its argument in
> `(gv-ref ...)` and lets the function be more efficient.

Fair enough, I guess I was just thinking gv-ref will be unfamiliar to
most people, but if the docstring is clear it doesn't matter.

>> How would you feel about gv-ref itself doing a check?
>>
>> (if (and (eq 'closure (caar place))
>>          (eq 'closure (cadr place)))
>>     place
>>   (gv-letplace ...etc...)
>>
>> Too hacky?
>
> Beside the obvious problem of checking equality vs `closure` which will
> break down with byte-compiled code, the more serious problem is that
> this code is run at macro-expansion time, not at run-time, so `place` is
> a Elisp *expression* and not an Elisp *value*.
>
> IOW your test will only trigger when the *source code* is of the form
>
>     (gv-ref ((closure ...) . (closure ...)))

Bleagh, okay. I will stop trying to be clever.

Thanks,
Eric