🚀 go-pugleaf

William Ogden writes:
>A third major objective of semantics is to define formally for
>implementors precisely what effect their compilers/interpreters are
>supposed to produce under all circumstances. This is the objective
>which seems to favor denotational semantics. Denotational semantics
>are explicit semantics, as opposed to the implicit semantics which result
>from the operational approach. I.e., operational semantics produce a
>welter of irrelevant information (computational histories), from which the
>essential information (the input/output pairs, in the case of sequential
>programs) must be extracted.

As I think you have implicitly noted, computation histories are NOT
irrelevant in the case of parallel programs.  Programs which have 
multiple threads of execution are not the only programs for which 
computation histories are relevant, however.  Sequential programs which 
perform input and output have characteristics a compiler writer might 
want to ensure that are not properties of the input/output relation, 
particularly in the obvious case of programs that do not terminate.  
Sequential programs which can receive signals or interrupts from their 
environment are another instance of this.  What this boils down to is 
that even a sequential program can have a concurrently executing 
environment, and this can have consequences for language semantics that 
are similar to the consequences of having concurrency WITHIN a program.

Programs may experience exceptions that result from things like running 
out of space or overflowing a floating point variable.  In many cases, 
we do not want the language semantics to specify exactly when such 
exceptions may arise, but we DO want to specify at least something about 
how the program will RESPOND to such exceptions.  It may be possible to 
do this denotationally, but the complexity of the denotational solution 
may be more than it's worth.

To take a step further, one might want to include hard timing 
characteristics in one's language.  This would require an extension of 
even operational semantics (as it is usually defined) (unless you want 
to introduce some sort of kludge where the running time is part of the 
output, but that won't work for the cases I mentioned above).

I would venture to say that the class of programs for which computation 
histories are irrelevant is actually quite small from the standpoint of 
what programs people usually write, and want to ensure the correct 
compilation of.  Certainly this is my experience as a programmer.