why cannot assign to function call

[Mark Wooding]

[Sigh.  I must apologize for the length of this article.  I can't, alas,
see a satisfactory way of trimming it.  The doubly-quoted stuff later on
was by me.]

Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> wrote:

> I'm pretty sure that no other pure-Python coder has manipulated 
> references either. They've manipulated objects.

No: not directly.  The Python program deals solely with references;
anything involving actual objects is mediated by the runtime.

> Whatever the VM does under the hood is another story.

(And, to stave off a return to the discussion about synchronized clones
and other implementation techniques, whether a reference is a memory
pointer, a tagged immutable immediate value, or an element of an
equivalence-class of clones is an irrelevant implementation detail; but
the reference needs to exist to explain observed, specified behaviour.
For the purposes of this discussion, I shall continue to use the
commonly accepted term `reference' to denote an arbitrary and
implementation-specific choice of the isomorphism class of such possible
implementation techniques.)

> That's why we should try to keep the different layers of explanation
> separate, without conflating them. Python programmers don't actually
> flip bits, and neither do they manipulate references. Python
> programmers don't have access to bits, or references. What they have
> access to is objects.

No, that's my point: Python programmers /don't/ have direct access to
objects.  The objects themselves are kept at arm's length by the
indirection layer of references.  

> (Of course, there are ways to get under the hood if you really want
> to.)

Yes, but -- as I've done throughout this discussion -- I shall continue
to use only Python examples whose behaviour is fully specified and
implementation independent in order to support my thesis.

> > Python does pass-by-value, but the things it passes -- by value --
> > are references.
> 
> If you're going to misuse pass-by-value to describe what Python does, 
> *everything* is pass-by-value "where the value is foo", for some foo.

No.  I've tried explaining this before, with apparently little success.
This is probably my fault: I don't seem to be good at explaining
concepts to people whose mindset is significantly different to mine.
(My refusal to ignore complicated corner cases doesn't help.)

The words `value' and `reference' have significantly different meanings
depending on whether we're talking on the one hand about data models and
on the other hand about argument-passing models.  In particular, the
latter focuses on details at a lower abstraction level.  This is
extremely unfortunate, and is causing a lot of confusion.  I can only
speculate that the origins of this mess are historical and have their
origins in the fact that lower-level languages have tended to have more
exotic argument-passing models.

This is going to be (as far as I can make it) a language-independent
survey.  That in itself is going to make matters complicated, because I
know a lot of programming languages, and they differ in sometimes subtle
ways.

Enough of the disclaimers, and on to some terminology.  For the
avoidance of confusion, I shall use the following terms in perhaps
technical senses, defined below.  Even so, I believe that I'm using
these terms in the senses (or at least, in ways similar to the senses)
commonly understood in the field of programming language design.

  * A /value/ is an item of data.  The range and nature of values is
    language specific.  Typically, values encompass at least some kinds
    of numbers, textual data, and compound data structures; they may
    also include behavioural items such as functions.

  * A /location/[1] is an area of memory suitable for storing the
    /immediate representation/ (which I shall abbreviate to /IR/) of a
    value.  (A location may be capable of storing things other than IRs,
    e.g., representations of unevaluated expressions in lazily evaluated
    languages.  Locations may vary in size, e.g., in order to be capable
    of storing different types of IRs.)

  * A /variable/ is a location to which has been /bound/ a name.  Given
    an occurrence of a name in a program's source, there is a language
    specific rule for determining the variable to which it is bound.

  * /Evaluation/ is the process of determining a value from an
    expression.  The /value of/ an expression is the result of
    evaluating the expression.  This value is, in general, dependent on
    the contents of the locations to which names appearing in the
    expression are bound.

  * A /function/ (synonymously, /procedure/) is a subprogram which may
    be /called/ by another (not necessarily distinct) part of the
    program, supplying zero or more /arguments/, performing a
    computation depending on these arguments, and returning zero or more
    /results/.  Whether functions are values is language specific.  The
    nature of the arguments and results is language specific.

[1] Previously, I used the term `slot' for what I'm now calling
    a `location'.

The argument passing model `pass-by-value' has a number of distinctive
properties.

  * The argument expression is fully evaluated before the function is
    called, yielding an argument value.

  * The corresponding parameter name is bound to a fresh location.

  * The argument value IR is stored in the parameter's location.

By contrast, the `pass-by-reference' model has other distinguishing
properties.

  * Whether arbitrary argument expressions are permitted is language
    dependent; often, only a subset of available expressions -- those
    that designate locations -- are permitted.  If the argument
    expression does designate a location, then this location is the
    /argument location/.  If arbitrary expressions are permitted, and
    the expression does not designate a location, then a fresh location
    is allocated to be the argument location, the expression evaluated,
    and the resulting IR stored in the argument location.

  * The corresponding parameter name is bound to the argument location.

There are other models, including value/return and call-by-name.

It should be clear that it is possible to write the traditional `swap'
function trivially using pass-by-reference, but one requires explicit
indirection in order to achieve the same effect using pass-by-value.

> You can't have anything but pass-by-value with current computer
> technology, because computers don't actually move arguments, they only
> copy bytes. So pass-by-value becomes a meaningless term, because it
> describes every computer language imaginable, including hypothetical
> ones using calling conventions not yet invented, and therefore
> explains nothing.

I hope that I have convincingly demonstrated that it's possible to
define `pass-by-value' in a coherent manner, consistent with
conventional usage, and distinguishing it clearly from `pass-by-
reference'.

> > (The `pass-by-*' notions are confusingly named anyway.  Pass-by-name
> > doesn't actually involve names at all.)
> 
> You might find them confusing, but I don't. What I find confusing is
> that people insist on misusing terminology invented for describing one
> type of behaviour in order to use it for a completely different type
> of behaviour just because of certain similarities under the hood.

I hope that I've also demonstrated that the similarities `under the
hood' are not actually there.  Indeed, I've defined `pass-by-reference'
without describing references at all.

This is actually as it should be.  The simple assembler procedure

	xchg	 eax, ebx
	ret

implements a `swap' function pretty well.  We can map the abstract
concepts listed above onto the low-level details easily: locations can
be in memory on in registers; argument locations are in registers;
argument value IRs are words; and the binding of names to locations is
fixed.

> > I agree with the comment about Pascal, but C is actually pretty similar
> > to Python here.  C only does pass-by-value.
> 
> Except for arrays.

Even for those.  C doesn't pass arrays at all; instead it passes
(programmer-visible) pointers.  See other article.

> > If you want a function to modify your variable, you have to pass a
> > pointer value which points to it.
> 
> Yes, because the variable is copied before the function sees it. So if
> you pass a struct, and modify one of the struct's fields, the caller
> doesn't see the change.
> 
> Now try that with Python, and you'll see completely different behaviour. 
> (You'll have to use something *like* a struct, because Python doesn't 
> have them. Try an object with attributes.)

That's because C's IRs are raw value representations; its `locations'
correspond to what the C standard calls `objects' (3.15).  Pass-by-value
works by storing IRs in freshly allocated locations -- in C, these are
objects with automatic storage duration (6.2.4, 6.5.2.2).

> In other words... C is call-by-value, and (according to you) Python is 
> call-by-value, but they behaviour differently.

And this is entirely due to the difference in their immediate
representations of values.

> > Python has no pointer values, so you need a different hack.  The
> > hack usually involves lists.  (Though it's easier in the main to return
> > compound data objects like tuples.  I don't suppose that a proposal for
> > true multiple return values would go down well here.  No, didn't think
> > so...)
> 
> Out of curiosity, what makes Python returning tuples less "true" than 
> "true multiple return values", and what can you do with TMRVs that you 
> can't do with tuples?

`What can you do with ... that you can't do with ...' questions are
meaningless when asked about Turing-complete languages, since they're
obviously equipotent.

In Python, if I want to convey multiple results to a function's caller,
I usually use a tuple.  This is a proper first-class value and needs to
be properly allocated and populated, and a reference returned.  Python's
unpacking assignment syntax provides a relatively reasonable way of
destructuring the tuple and recovering the individual results.  So all
of that's fine.

  * Construction, population and destructuring of the intermediate tuple
    has a performance impact.  An intelligent compiler with knowledge of
    the function and the call site might be able to optimize the tuple
    away, but this is difficult due to Python's intrinsically dynamic
    nature: dynamic typing means a compiler must be better at drawing
    inferences from complicated code, and it not actually be possible to
    determine at compile time which actual function is being called
    anyway.  (Not that I'd have Python any other way.)  This would
    matter more if there were a significant statically-compiled
    implementation of Python that was intended for high-performance
    computing.

  * I quite frequently find myself only interested in one of several
    results from a function.  For example, a function which parses some
    data from the head of a string might plausibly return both the
    parsed object and the remainder of the string.  If I'm interested
    only in the object, I'll write something like

      obj = parse(string)

    and then obj will be a tuple.  If the thing I'm expecting might be a
    tuple (or at least a sequence of some kind) it might be a while
    before an error occurs, if ever.  Multiple return values would
    either (Common Lisp model) let me ignore return values I wasn't
    interested in, or (Scheme model) signal errors that I'd done
    something wrong.  The Common Lisp model is riskier (I can ignore
    things which perhaps I shouldn't) but more flexible (in particular,
    I can enhance functions by adding return values without breaking
    existing callers, and I can write functions which return potentially
    interesting things which they computed anyway but weren't part of
    the main objective).

It's not a big deal.  Forget I mentioned it.  In particular, there's no
convenient syntax left to use for multiple return values anyway.

When (not if) I want Lisp, I /do/ know where to find it.

> x = 23
> 
> There's a name, and an object, and I've bound the name to the object so I 
> can refer to the object 23 by the name x.

(Assume that x was previously unbound, and this is evaluated at top
level) The above expression: binds x to a new location, and stores the
immediate representation of the constant 23 in this location.
(Languages -- other than C++ -- seem pretty uniform in their
interpretation of assignment as overwriting a location with a new IR.)

Because 23 is immutable, its IR doesn't actually matter that much.
These things become apparent only with mutable data.

> >  You bind names slots in which you store references.

Oops.  Missing `to' between `names' and `slots'.  Sorry.

> I'm pretty sure I don't. I'd have noticed.

You bind names to locations which store immediate representations.
Python IRs are (in the sense defined above) exclusively references.

> You may have missed my last question:
> 
> >> > How do we deal with anonymous objects in your model?

No.  I decided that it was irrelevant given the previous answers I'd
already given.  That is, if an object's only attached paperweights are
stored in other objects -- maybe in boxes -- then it has no obvious
name; if there is no path from you to the object, then no action you
take can be affected if the daemon clears it away -- so it might as well
do that.

(This is my fault, I know, but: `model' is the wrong word for the
objects/boxes/string/paperweights description.  `Metaphor' is probably
better.  Sorry for my lack of precision on this subject.)

> > What I am pretty sure of is that references are going to have to
> > enter the picture at some point, because other models get too
> > complicated.

> Well, I dare say that at *some* point all models are insufficient. 

No.  The Python Language Reference presents a model of Python.  CPython,
and other implementations are expected to implement this model: failure
to do so is (presumably) a bug in the implementation, or a defect in the
document.  The PLM (assumed defect-free) is therefore a sufficient model
of Python, capable of describing all aspects of the language which are
not implementation specific.

> The map is not the territory, and there's always something that gets
> left out. 

The trick is to explain Python, rather than implementations of Python.
But the behaviour of

  l = [1, 2, 3]
  l[1] = l

can be understood without recourse to implementation specifics.  I argue
-- and this has really been my point all along -- that this
understanding is best achieved by a diagram of the form

                 ,----------,
                 v          |
      +---+    +---+        |
   l: | *----> | *-----> 1  |
      +---+    +---+        |
               | *----------'
               +---+
               | *-----> 3
               +---+

than by one of the form

      +-----+
   l: |  1  |
      +-----+
      |  <------------- in here is an identical copy of l
      +-----+
      |  3  |
      +-----+

This immediately gets me thinking about `Gödel Escher Bach', strange
loops, and all manner of weirdness.  Such things still give me the
willies occasionally.

(I'm willing to accept that I suck at drawing diagrams, and that I might
anyway have accidentally misrepresented your position.  If you think you
can draw a more convincing diagram of this data structure, according to
your model, please do.)

> But I think your model with strings is more complicated: robots,
> sticky Blu-Tack, string that you can't touch or see, and so forth.

The metaphor is complicated, yes, but the concepts are somewhat
complicated too.  Fortunately there are direct mappings from the
metaphor to identifiable 

> Compared to that, TARDIS technology enabling objects to be in two
> places at once is remarkably straightforward. Despite it being
> physically unrealistic, it's logically simple.

You certainly get to talk about Tardises, which is cool. ;-) There is
some interesting and relevant material in the classic Who stories
`Logopolis' and `Castrovalva'.  And, if the resulting recursion is
explained thoroughly, it'll lead you on some fascinating diversions
around some valuable areas of theory...

-- [mdw]