bug#43557: 28.0.50; Please document which objects are mutable and which are not

bug#43557: 28.0.50; Please document which objects are mutable and which are not

[Philipp Stephani]

The "Mutability" section in the ELisp manual mentions that there are
mutable and immutable objects, but (besides giving a few examples)
doesn't document which objects are actually mutable.  At the very least,
there should be a list of functions that are guaranteed to return
mutable objects, and a statement about the mutability of function return
values in general.


In GNU Emacs 28.0.50 (build 106, x86_64-pc-linux-gnu, GTK+ Version 3.24.20, cairo version 1.16.0)
 of 2020-09-22
Repository revision: 797ff44d53ef4c4b800de8467b403c876cac3c1f
Repository branch: master
Windowing system distributor 'The X.Org Foundation', version 11.0.12008000
System Description: Debian GNU/Linux rodete

Configured using:
 'configure --enable-gcc-warnings=warn-only
 --enable-gtk-deprecation-warnings --without-pop --with-mailutils
 --enable-checking=all --enable-check-lisp-object-type --with-modules
 'CFLAGS=-O1 -ggdb3 -fno-omit-frame-pointer -fsanitize=address
 -fsanitize=undefined -fsanitize=pointer-compare
 -fsanitize=pointer-subtract''

Configured features:
XPM JPEG TIFF GIF PNG CAIRO SOUND DBUS GSETTINGS GLIB NOTIFY INOTIFY
LIBSELINUX GNUTLS FREETYPE HARFBUZZ ZLIB TOOLKIT_SCROLL_BARS GTK3 X11
XDBE XIM MODULES THREADS LIBSYSTEMD JSON PDUMPER

Important settings:
  value of $LANG: en_US.utf8
  value of $XMODIFIERS: @im=ibus
  locale-coding-system: utf-8-unix

Major mode: Lisp Interaction

Minor modes in effect:
  tooltip-mode: t
  global-eldoc-mode: t
  eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
None found.

Features:
(shadow sort mail-extr emacsbug message rmc dired dired-loaddefs rfc822
mml easymenu mml-sec epa epg epg-config gnus-util rmail rmail-loaddefs
text-property-search time-date mm-decode mm-bodies mm-encode mail-parse
rfc2231 mailabbrev gmm-utils mailheader sendmail rfc2047 rfc2045
ietf-drums mm-util mail-prsvr mail-utils phst skeleton derived edmacro
kmacro pcase ffap thingatpt url url-proxy url-privacy url-expand
url-methods url-history url-cookie url-domsuf url-util url-parse
auth-source cl-seq eieio eieio-core cl-macs eieio-loaddefs
password-cache json map url-vars mailcap rx gnutls puny dbus xml subr-x
seq byte-opt gv bytecomp byte-compile cconv compile comint ansi-color
ring cl-loaddefs cl-lib tooltip eldoc electric uniquify ediff-hook
vc-hooks lisp-float-type mwheel term/x-win x-win term/common-win x-dnd
tool-bar dnd fontset image regexp-opt fringe tabulated-list replace
newcomment text-mode elisp-mode lisp-mode prog-mode register page
tab-bar menu-bar rfn-eshadow isearch timer select scroll-bar mouse
jit-lock font-lock syntax facemenu font-core term/tty-colors frame
minibuffer cl-generic cham georgian utf-8-lang misc-lang vietnamese
tibetan thai tai-viet lao korean japanese eucjp-ms cp51932 hebrew greek
romanian slovak czech european ethiopic indian cyrillic chinese
composite charscript charprop case-table epa-hook jka-cmpr-hook help
simple abbrev obarray cl-preloaded nadvice button loaddefs faces
cus-face macroexp files window text-properties overlay sha1 md5 base64
format env code-pages mule custom widget hashtable-print-readable
backquote threads dbusbind inotify dynamic-setting system-font-setting
font-render-setting cairo move-toolbar gtk x-toolkit x multi-tty
make-network-process emacs)

Memory information:
((conses 16 69082 7098)
 (symbols 48 8666 1)
 (strings 32 23937 1390)
 (string-bytes 1 771102)
 (vectors 16 13762)
 (vector-slots 8 188421 5360)
 (floats 8 26 30)
 (intervals 56 219 0)
 (buffers 992 11))

-- 
Google Germany GmbH
Erika-Mann-Straße 33
80636 München

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg

Diese E-Mail ist vertraulich.  Falls Sie diese fälschlicherweise erhalten haben
sollten, leiten Sie diese bitte nicht an jemand anderes weiter, löschen Sie
alle Kopien und Anhänge davon und lassen Sie mich bitte wissen, dass die E-Mail
an die falsche Person gesendet wurde.

This e-mail is confidential.  If you received this communication by mistake,
please don’t forward it to anyone else, please erase all copies and
attachments, and please let me know that it has gone to the wrong person.

bug#43557: 28.0.50; Please document which objects are mutable and which are not

[Lars Ingebrigtsen]

Philipp Stephani <p.stephani2@gmail.com> writes:

> The "Mutability" section in the ELisp manual mentions that there are
> mutable and immutable objects, but (besides giving a few examples)
> doesn't document which objects are actually mutable.  At the very least,
> there should be a list of functions that are guaranteed to return
> mutable objects, and a statement about the mutability of function return
> values in general.

Reading the section, it seems pretty clear to me, and outlines the cases
where you can't assume mutability (even if the objects may appear to be
mutable).

I'm not sure a list of mutable objects is a well-defined request, and
there are very few functions that can promise to return a mutable
object.  (I mean, (list 1 2 immutable-list) is mutable, but can contain
elements that aren't.)

So I'm not sure whether what you're requesting is feasible.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#43557: 28.0.50; Please document which objects are mutable and which are not

[Philipp Stephani]

Am Do., 15. Okt. 2020 um 17:34 Uhr schrieb Lars Ingebrigtsen <larsi@gnus.org>:
>
> Philipp Stephani <p.stephani2@gmail.com> writes:
>
> > The "Mutability" section in the ELisp manual mentions that there are
> > mutable and immutable objects, but (besides giving a few examples)
> > doesn't document which objects are actually mutable.  At the very least,
> > there should be a list of functions that are guaranteed to return
> > mutable objects, and a statement about the mutability of function return
> > values in general.
>
> Reading the section, it seems pretty clear to me, and outlines the cases
> where you can't assume mutability (even if the objects may appear to be
> mutable).

I disagree. "Pretty clear" would mean "allowing the reader to classify
each Lisp expression w.r.t. the mutability of its value", and as the
section only gives a few examples, it can't do that. What it should do
in addition is provide rules on how to classify any given Lisp
expression. Each possible Lisp expression has to fall into exactly one
of three categories:
- The value is mutable.
- The value is immutable.
- It is unspecified whether the value is mutable or immutable.
Given that we can't document this for every Lisp function in
existence, we need to pick some default, and document that default in
the manual. Also, we need to document the cases where the default
doesn't apply, either in the manual or in function docstrings.
I'm happy to add the necessary documentation, but for that we first
need a decision what the default is, and what the exceptions are.

>
> I'm not sure a list of mutable objects is a well-defined request, and
> there are very few functions that can promise to return a mutable
> object.  (I mean, (list 1 2 immutable-list) is mutable, but can contain
> elements that aren't.)

Then the docstring of `list' and the ELisp manual should say that. The
difference between shallow and deep immutability might not be clear to
all readers, so it's important that it's documented as well.

>
> So I'm not sure whether what you're requesting is feasible.

It must be feasible, otherwise programming in ELisp becomes, strictly
speaking, impossible. Given code such as
(let ((var (some-list-returning-function ...))) ...)
it must be possible for programmers to derive whether (setcar var ...)
is allowed from some set of rules plus the docstring of the function.
This is not some theoretical problem: This bug was triggered by a code
review where the author and reviewer disagreed what could be assumed
about the mutability of the return value of arbitrary functions, so
fixing this bug has very practical consequences.

bug#43557: 28.0.50; Please document which objects are mutable and which are not

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> I disagree. "Pretty clear" would mean "allowing the reader to classify
> each Lisp expression w.r.t. the mutability of its value", and as the
> section only gives a few examples, it can't do that. What it should do
> in addition is provide rules on how to classify any given Lisp
> expression. Each possible Lisp expression has to fall into exactly one
> of three categories:
> - The value is mutable.
> - The value is immutable.
> - It is unspecified whether the value is mutable or immutable.

While I can kinda see where you're going, it's still pretty fuzzy to me.
I think it would be more clear if you could give concrete cases where
you'd want to use such information.

> Then the docstring of `list' and the ELisp manual should say that. The
> difference between shallow and deep immutability might not be clear to
> all readers, so it's important that it's documented as well.

This is a pervasive issue, much more pervasive than `list` and that
applies to pretty much all programming languages.  So I don't think it
has its place in the doc of `list`.

I hope the box diagrams of the intro to ELisp can be considered
a documentation of this phenomenon.

> it must be possible for programmers to derive whether (setcar var ...)
> is allowed from some set of rules plus the docstring of the function.

[ Aha: here's is an example!  ]

Mutability says whether it is *possible*, rather than whether it's
*allowed*.  Most (all?) cons cells are mutable, but it is strongly
recommended to refrain from mutating most cons cells (because it
can/will have unexpected consequences because that same cons cell is
also used elsewhere).

So what you're asking here is not exactly mutability but something
slightly different, which is not very well defined nor
documented, indeed.


        Stefan

bug#43557: 28.0.50; Please document which objects are mutable and which are not

[Philipp]

> Am 03.06.2021 um 16:41 schrieb Stefan Monnier <monnier@iro.umontreal.ca>:
> 
>> I disagree. "Pretty clear" would mean "allowing the reader to classify
>> each Lisp expression w.r.t. the mutability of its value", and as the
>> section only gives a few examples, it can't do that. What it should do
>> in addition is provide rules on how to classify any given Lisp
>> expression. Each possible Lisp expression has to fall into exactly one
>> of three categories:
>> - The value is mutable.
>> - The value is immutable.
>> - It is unspecified whether the value is mutable or immutable.
> 
> While I can kinda see where you're going, it's still pretty fuzzy to me.
> I think it would be more clear if you could give concrete cases where
> you'd want to use such information.

I don't know how concrete a case you want here, but basically I'd like the manual to describe the semantics of

(let ((var FORM)) (setcar var VAL))

for arbitrary values of FORM (assuming that FORM returns a cons object).  Likewise for `aset', `set', and the other object-mutating primitives.
What the semantics of such a form are depends crucially on the mutability of the value returned by FORM: if FORM returns an immutable object, then the overall form triggers undefined behavior.  In other words, the manual needs to provide a procedure to classify forms according to the mutability of their return values.

> 
>> Then the docstring of `list' and the ELisp manual should say that. The
>> difference between shallow and deep immutability might not be clear to
>> all readers, so it's important that it's documented as well.
> 
> This is a pervasive issue, much more pervasive than `list` and that
> applies to pretty much all programming languages.  So I don't think it
> has its place in the doc of `list`.
> 
> I hope the box diagrams of the intro to ELisp can be considered
> a documentation of this phenomenon.

The Lisp manual should still make this distinction explicitly.  It can be derived from the structure of lists, but it's a subtle point that deserved reiterating.

> 
>> it must be possible for programmers to derive whether (setcar var ...)
>> is allowed from some set of rules plus the docstring of the function.
> 
> [ Aha: here's is an example!  ]
> 
> Mutability says whether it is *possible*, rather than whether it's
> *allowed*.  Most (all?) cons cells are mutable, but it is strongly
> recommended to refrain from mutating most cons cells (because it
> can/will have unexpected consequences because that same cons cell is
> also used elsewhere).
> 
> So what you're asking here is not exactly mutability but something
> slightly different, which is not very well defined nor
> documented, indeed.

I don't think there's a meaningful distinction between "possible" and "allowed" as far as code authors are concerned, and I don't think the manual should use such vague terms.  Likewise, "strongly recommended" belongs into a style guide, not a reference manual.  In the end, the ability to write programs boils down to knowing the semantics of the lexical entities of the programming language in question, and for that to work the semantics need to be documented.
The Info node `Mutability' isn't actually so bad in explaining these concepts on a conceptual level.  It says clearly that mutable and immutable objects exist, and that attempting to mutate an immutable object triggers undefined behavior.  (I dislike the manual's usage of the phrase "should not" to mean "undefined behavior", but that's a different can of worms that we don't need to open here.)  I don't want to introduce new concepts or terminology here.  What's missing is really what this bug is asking for: a procedure to derive the mutability of objects from the forms that produce them.  The `Mutability' node documents this for some objects, but not all.

bug#43557: 28.0.50; Please document which objects are mutable and which are not

[Philipp]

> Am 04.06.2021 um 15:01 schrieb Philipp <p.stephani2@gmail.com>:
> 
> 
> 
>> Am 03.06.2021 um 16:41 schrieb Stefan Monnier <monnier@iro.umontreal.ca>:
>> 
>>> I disagree. "Pretty clear" would mean "allowing the reader to classify
>>> each Lisp expression w.r.t. the mutability of its value", and as the
>>> section only gives a few examples, it can't do that. What it should do
>>> in addition is provide rules on how to classify any given Lisp
>>> expression. Each possible Lisp expression has to fall into exactly one
>>> of three categories:
>>> - The value is mutable.
>>> - The value is immutable.
>>> - It is unspecified whether the value is mutable or immutable.
>> 
>> While I can kinda see where you're going, it's still pretty fuzzy to me.
>> I think it would be more clear if you could give concrete cases where
>> you'd want to use such information.
> 
> I don't know how concrete a case you want here, but basically I'd like the manual to describe the semantics of
> 
> (let ((var FORM)) (setcar var VAL))
> 
> for arbitrary values of FORM (assuming that FORM returns a cons object).  Likewise for `aset', `set', and the other object-mutating primitives.
> What the semantics of such a form are depends crucially on the mutability of the value returned by FORM: if FORM returns an immutable object, then the overall form triggers undefined behavior.  In other words, the manual needs to provide a procedure to classify forms according to the mutability of their return values.

To provide a more concrete example:

Assume you have the following (nonsense) function, with unknown implementation:

(defun my-cons ()
  "Return a cons cell consisting of the integers 1 and 2."
  ...)

I. Given only that information and the manual, is the following code valid (i.e. can't trigger undefined behavior in any case)?

(setcar (my-cons) 5)

II. Which of the following implementations of `my-cons' is correct (i.e. follows the rules of Emacs Lisp as described in the manual)?

(a)
(defun my-cons ()
  "Return a cons cell consisting of the integers 1 and 2."
  '(1 . 2))

(b)
(defun my-cons ()
  "Return a cons cell consisting of the integers 1 and 2."
  (cons 1 2)

(c)
(defun my-cons ()
  "Return a cons cell consisting of the integers 1 and 2."
  (if (eq (random 2) 0) '(1 . 2) (cons 1 2))

From what I can see there are four options:

1. Unless otherwise specified, objects are mutable.  Then the `setcar' form is valid, and only implementation (b) is correct.
2. Unless otherwise specified, objects are immutable.  Then the `setcar' form always triggers undefined behavior, and only implementation (a) is correct.
3. Unless otherwise specified, the objects that forms return are of unspecified mutability (i.e. they can be mutable or immutable).  Then the `setcar' form is invalid because the caller of `my-cons' can't assume that its return value is mutable, and all three implementations of `my-cons' are correct.
4. Mutability of the return object must be specified in all cases.  Then none of the implementations is correct, since none of them specifies the mutability of the returned cons object.

What I'd like here (among other things) is a statement in the manual which of the options (1)-(4) is the correct one.  (Or are there other options?)

bug#43557: 28.0.50; Please document which objects are mutable and which are not

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> Assume you have the following (nonsense) function, with unknown implementation:
>
> (defun my-cons ()
>   "Return a cons cell consisting of the integers 1 and 2."
>   ...)
>
> I. Given only that information and the manual, is the following code valid
> (i.e. can't trigger undefined behavior in any case)?
>
> (setcar (my-cons) 5)

I don't think we want to labels this as "undefined" or "invalid"
(Emacs and Emacs Lisp tries hard to avoid enforcing abstraction
boundaries, and relies instead on softer forms of discipline), but I'd
say that using `setcar` above is risky because the user has no guarantee
about what it may impact.

I think the rule is basically, that you should only ever use `setc[ad]r`
on cons cells you yourself created.  But indeed the manual fails to
document which functions guarantee to return "fresh" new cells, which
makes it hard to know which cells "you yourself created".

> II. Which of the following implementations of `my-cons' is correct
> (i.e. follows the rules of Emacs Lisp as described in the manual)?

All of them.

> From what I can see there are four options:
>
> 1. Unless otherwise specified, objects are mutable.  Then the `setcar' form
> is valid, and only implementation (b) is correct.
> 2. Unless otherwise specified, objects are immutable.  Then the `setcar'
> form always triggers undefined behavior, and only implementation (a)
> is correct.
> 3. Unless otherwise specified, the objects that forms return are of
> unspecified mutability (i.e. they can be mutable or immutable).  Then the
> `setcar' form is invalid because the caller of `my-cons' can't assume that
> its return value is mutable, and all three implementations of `my-cons'
> are correct.
> 4. Mutability of the return object must be specified in all cases.
> Then none of the implementations is correct, since none of them specifies
> the mutability of the returned cons object.

I think we have (3).


        Stefan

bug#43557: 28.0.50; Please document which objects are mutable and which are not

[Philipp]

> Am 05.06.2021 um 17:15 schrieb Stefan Monnier <monnier@IRO.UMontreal.CA>:
> 
>> Assume you have the following (nonsense) function, with unknown implementation:
>> 
>> (defun my-cons ()
>>  "Return a cons cell consisting of the integers 1 and 2."
>>  ...)
>> 
>> I. Given only that information and the manual, is the following code valid
>> (i.e. can't trigger undefined behavior in any case)?
>> 
>> (setcar (my-cons) 5)
> 
> I don't think we want to labels this as "undefined" or "invalid"
> (Emacs and Emacs Lisp tries hard to avoid enforcing abstraction
> boundaries, and relies instead on softer forms of discipline),

I'm counting almost 100 occurrences of the words "undefined" or "unspecified" in the reference manual, so this isn't really new terminology.  It's even used in the manual directly for this purpose:

   If a program attempts to change objects that should not be
   changed, the resulting behavior is undefined [...]

The remaining weirdness here is saying "objects that should not be changed" instead of "immutable objects".
Most programming languages have some notion of "undefined" or "unspecified", often to allow optimizations or multiple implementations.  While there are downsides to introducing such behavior, often it's a reasonable compromise between underspecifying and overspecifying the language.
In this case, the manual already explains in a footnote that the current behavior is undesirable and Emacs Lisp should move into a direction where attempting to mutate immutable objects signals an error (thereby removing the undefined behavior).

> but I'd
> say that using `setcar` above is risky because the user has no guarantee
> about what it may impact.

I think that a word like "risky" has no place in a reference manual.  What does that even mean?  What are the risks?  Why introduce such vague and confusing terminology to begin with?  How would this help Emacs Lisp programmers?

> 
> I think the rule is basically, that you should only ever use `setc[ad]r`
> on cons cells you yourself created.

What does "should" mean here?  What happens if users don't follow this "recommendation"?  How do they identify "cons cells you yourself created"?
Again, I think such terminology brings up more questions than it answers.

>  But indeed the manual fails to
> document which functions guarantee to return "fresh" new cells, which
> makes it hard to know which cells "you yourself created".

Then let's document that (while avoiding terms such as "you yourself created").

> 
>> II. Which of the following implementations of `my-cons' is correct
>> (i.e. follows the rules of Emacs Lisp as described in the manual)?
> 
> All of them.

Good.  Then let's document that!

> 
>> From what I can see there are four options:
>> 
>> 1. Unless otherwise specified, objects are mutable.  Then the `setcar' form
>> is valid, and only implementation (b) is correct.
>> 2. Unless otherwise specified, objects are immutable.  Then the `setcar'
>> form always triggers undefined behavior, and only implementation (a)
>> is correct.
>> 3. Unless otherwise specified, the objects that forms return are of
>> unspecified mutability (i.e. they can be mutable or immutable).  Then the
>> `setcar' form is invalid because the caller of `my-cons' can't assume that
>> its return value is mutable, and all three implementations of `my-cons'
>> are correct.
>> 4. Mutability of the return object must be specified in all cases.
>> Then none of the implementations is correct, since none of them specifies
>> the mutability of the returned cons object.
> 
> I think we have (3).
> 

Can we find a wording that we agree on and put it into the manual?

bug#43557: 28.0.50; Please document which objects are mutable and which are not

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

>> but I'd say that using `setcar` above is risky because the user has
>> no guarantee about what it may impact.
> I think that a word like "risky" has no place in a reference manual.

It doesn't have its place in the part that describes technically the
effect of the operation.  It can have its place in the part that gives
recommendations for style and recommended practices.

> What does that even mean?  What are the risks?

That the effect goes further than the author anticipated.

> Why introduce such vague and confusing terminology to begin with?

In the hope of saving them (and/or others) some serious head scratching,
and more generally in the hope to improve the reliability of ELisp code
out there.

>> I think the rule is basically, that you should only ever use `setc[ad]r`
>> on cons cells you yourself created.
> What does "should" mean here?

It's here a recommendation and a request.

> What happens if users don't follow this "recommendation"?

Experience teaches us that when a piece of code uses `setcar` on
a cons-cell built by some "unrelated" piece of code, there's a high
probability that sooner or later the `setcar` will end up modifying more
data than intended (because that same cons cell is shared with some
other "unrelated" data structure).
I.e. you get a bug; one that can take a fair bit of effort to track down.

> How do they identify "cons cells you yourself created"?

When in doubt, assume that it's not "a cons cells you yourself created".

> Again, I think such terminology brings up more questions than it answers.

Agreed.  Mutation is pretty nasty, indeed.

>> But indeed the manual fails to document which functions guarantee to
>> return "fresh" new cells, which makes it hard to know which cells
>> "you yourself created".
> Then let's document that (while avoiding terms such as "you yourself created").

I'd welcome that, yes.

> Can we find a wording that we agree on and put it into the manual?

I can't think of a reason why not.


        Stefan

bug#43557: 28.0.50; Please document which objects are mutable and which are not

[Dmitry Gutov]

Hi Stefan,

On 03.06.2021 17:41, Stefan Monnier via Bug reports for GNU Emacs, the 
Swiss army knife of text editors wrote:
> Mutability says whether it is*possible*, rather than whether it's
> *allowed*.  Most (all?) cons cells are mutable, but it is strongly
> recommended to refrain from mutating most cons cells (because it
> can/will have unexpected consequences because that same cons cell is
> also used elsewhere).

See bug#40671 (and the lengthy argument in there) to know how this term 
in the Emacs manual came to mean something else than it usually means.