Incompleteness in semantics and parallel-or

I remember seeing a link on LtU to some lecture notes explaining that in (denotational?) semantics of simple imperative programming languages, the semantics would have a serious hole if parallel-or was not included; the strong-exists operator made things even better.
I have searched and searched the archives, and cannot find any post that remotely resembles this. Help!

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I tried locating the post

But came up empty handed. Has this been something within the last six months?

some links

I don't know of the discussion you're referring to, but I mentioned on LtU a while back a somewhat related point made by Will Clinger on comp.lang.scheme ("Full abstraction is not very abstract"), and then here are several papers on this topic:

Full A vs. full C.

Good call. Just a point to bear in mind; Will Clinger is being polemical in that post (the ongoing war against the nonsesnse of Bill Richter), and the quote you make is misleading out of context: the essence of full abstraction is that you give a non-operational semantics; a denotational semantics that in any way is derived from an operational semantics, it will be fully complete but not fully abstract.

FWIW, my doctor-daddy was one of the five co-discoverers of the first fully abstract models of PCF, and my doctor-grandpa was one of the others.

Three skeleton references:
[1] Hyland-Ong game semantics
[2] Abramsky-Malacaria-Jagadeesan semantics
[3] Levy's idea of subsumptive semantics, which I think nails the real problem people have with modern approaches to full abstraction.

I'll flesh out those skeletons when I have more time.

- Charles

Aha!

While none of those references were exactly those I remember, full abstraction were definitely the keywords I had forgotten. Using those, I again found

But in the end, I did eventually find the notes I was looking for, and they were
Full abstraction and universality.