[Python-ideas] "While" suggestion

Terry Reedy 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 
> semantics:
> http://en.wikipedia.org/wiki/Formal_semantics_of_programming_languages
> 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 mailing list