[Python-ideas] "While" suggestion
tjreedy at udel.edu
Fri Aug 1 05:00:46 CEST 2008
David Borowitz wrote:
> Precisely: you're talking about two different accepted definitions of
> I'm not going to say one type of formal semantics is better than
> another, but it's nice when everyone is at least on the same page :)
Thank you for the reference. I see that denotational and operational
are just the beginning of the semantics of semantics.
In writing about and comparing algorithms, I need a term that is
slightly in between but closer to operational than merely denotational.
I am thinking of using 'operationally equivalent' to describe two
algorithms that are denotationally (functionally) identical and which
compute the same essential intermediate objects (values) in the same
order, while not being 'operationally identical' (which would make them
the same thing).
Wikipedia refers 'operational equivalence' to 'observational
equivalence'. Other hits from Google suggest that it have been used
variably to mean things from operationally identical to merely
denotationally (functionally identical), but therefore a complete
substitute in the users operations.
In the present case, we agree that [genexp] == list(genexp] in the
Python meaning, denotational and operational, of '==', which is to
compare the denotational meaning of two expressions (the resulting
objects and their values). I also claim a bit more: [genexp] could be
but does not have to be, and in current CPython is not, operationally
identical to list(genexp). But I do expect that it is operationally
equivalent in the sense above. The essential objects and operations are
the list contents and the list that starts empty and grows one reference
at a time via append().
Terry Jan Reedy
More information about the Python-ideas