20
ory m odel. It has been used for communication with the ISO standardisation committee,
for teaching the memory model to students, and by ARM, Linux andGCCengineerswho
wish to underst and C/C++11. Cppmem was described in POPL in 2011 [28], and an
alternative implementation of the backend that used the Ni tpick counterexample gener-
ator [31]waspublishedinPPDPin2011[32], in work by Weber and some of the other
authors.
Chapter 5 describes problems found with the standard during the process of for mal -
isation, together with solutions that I took to the C and C++ standardisation commit-
tees. Many amendments were adopted by both standards in some form. This achieve-
ment involved discussing problems and drafting text for amendments with both my aca-
demic collaborators and many on the standardisation committee, including: Hans Boehm,
Lawrence Crowl, Peter Dimov, Benjamin Kosnik, Nick Maclaren,PaulMcKenney,Clark
Nelson, Scott Owens, Susmit Sarkar, Peter Sewell, Tjark Weber, Anthony Williams, and
Michael Wong. Some of these problems broke the central precepts of the language de-
sign. My changes fix these pr ob l ems and are now part of the ratified standards for C11
and C++11 [
30, 8], as well as the specification of the GPU framework, OpenCL 2.0[86].
This chapter ends by identifying an open problem in the designofrelaxed-memorypro-
gramming languages, called the “thin-air” problem, that limits the compositionality of
specifications, and leaves some u n d esi r abl e executions allowed that will not appear in
practice. This leaves the memory model sound, but not as precise as we would like.
Many of t h e comments and criticisms were submitted as workingpapersanddefectre-
ports [29, 20, 75, 73, 111, 27, 76, 77, 74].
Chapter 6 describes a mechanised HOL4 proof that shows t h e equivalence of th e
progressively simpler versions of the C/C++11 memory model,includingthosepresented
in Chapter 3,undersuccessivelytighterrequirementsonprograms. These results establish
that a complicated part of the specification is redundant and can simply be removed,
and they culminat e in the proof that the specification meets one of its key design goals
(albeit for programs without loops or recursion): despite the model’s complexity, if a race-
free program uses only regular memory accesses, locks and seq cst-annotated atomic
accesses, then it will behave in a sequentially consistent manner. This proof validates
that the model is usable by programmers who understand sequential consistency.
Chapter
7 describes work done in collaboration with Jade Alglave, Luc Maranget,
Kayvan Memarian, Scott Owens, Susmit Sarkar, Peter Sewell, Tjark Weber and Derek
Williams. We took t he co mpilation mappings fro m C/C++11 to the x86, Power and
ARM architectures that had been proposed by the C++11 design group and proved that
they do indeed preserve the semantics of the programming-language memory model in
execution above t h ose processors. This led to the discovery and resolution of a flaw in
one of the mappings. This chapter represents a second form of validation of the formal
model: it is implementable above common target architectures. My contribution, which
was smaller in this work, involved proving equivalent variants of the C/C++11 memory