Home » forums » LtU Forum

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!

By Jacques Carette at 2005-01-12 03:18 | LtU Forum | previous forum topic | next forum topic | other blogs | 6039 reads

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?

By Chris Rathman at Thu, 2005-01-13 16:39 | login or register to post comments

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:

By Dave Herman at Thu, 2005-01-13 19:03 | login or register to post comments

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

By Charles A Stewart at Fri, 2005-01-14 00:05 | login or register to post comments

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.

By Jacques Carette at Fri, 2005-01-14 03:32 | login or register to post comments