Investigating the complex trade-offs in this design space is
the subject of current research. 1, 16
Whether or not one believes in transactions, it does seem
likely that some combination of effect systems and/or ownership types will play an increasingly important role in concurrent programming languages, and these may contribute
to the guarantees desirable for memory transactions.
Our main claim is that transactional memory qualitatively raises the level of abstraction offered to programmers.
Just as high-level languages free programmers from worrying about register allocation, so transactional memory frees
the programmer from concerns about locks and lock acquisition order in designing shared-memory data structures.
More fundamentally, one can combine such abstractions
without knowing their implementations, a property that is
the key to constructing large programs.
References
1. Abadi, M., Birrell, A., Harris, T., and
Isard, M. Semantics of transactional
memory and automatic mutual
exclusion. POPL’08: Proceedings of
the 35th ACM SIGPLAn-SIGACT
Symposium on Principles of
Programming Languages, pp. 63–74,
ACM, Jan. 2008.
2. Blelloch, G.E., Hardwick, J.C.,
Sipelstein, J., Zagha, M., and
Chatterjee, S. Implementation of
a portable nested data-parallel
language. J. Parallel Distrib. Comput.,
21 ( 1): 4–14, 1994.
3. Carlstrom, B.D., McDonald, A., Chafi,
H., Chung, J., Minh, C. C., Kozyrakis,
C., and Olukotun, K. The Atomos
transactional programming language.
PLDI’06: Proceedings of the 2006
ACM SIGPLAn Conference on
Programming Language Design and
Implementation, pp. 1–13, ACM, June
2006.
4. Chung, J., Minh, C. C., McDonald,
A., Skare, T., Chafi, H., Carlstrom,
B. D., Kozyrakis, C., and Olukotun,
K. Tradeoffs in transactional
memory virtualization. ASPLOS’06:
Proceedings of the 12th International
Conference on Architectural Support
for Programming Languages and
Operating Systems, pp. 371–381,
ACM, Oct. 2006.
5. Damron, P., Fedorova, A., Lev,
Y., Luchangco, V., Moir, M., and
Nussbaum, D. Hybrid transactional
memory. ASPLOS’06: Proceedings
of the 12th International Conference
on Architectural Support for
Programming Languages and
Operating Systems, pp. 336–346,
ACM, Oct. 2006.
6. Daume III, H. Yet another Haskell
tutorial. http://www.cs.utah.edu/~hal/
docs/daume02yaht.pdf, 2006.
7. Gray, J., and Reuter, A. Transaction
Processing: Concepts and Techniques.
Morgan Kaufmann Publishers, Inc.,
1992.
8. Harris, T., and Fraser, K. Language
support for lightweight transactions.
OOPSLA’03: Proceedings of the 18th
ACM SIGPLAn Conference on Object-Oriented Programming, Systems,
Languages, and Applications, pp.
388–402, ACM, Oct. 2003.
9. Harris, T., Marlow, S., Peyton Jones,
S., and Herlihy, M. Composable
memory transactions. PPoPP’05:
Proceedings of the 10th ACM
SIGPLAn Symposium on Principles
and Practice of Parallel Programming,
pp. 48–60, ACM, June 2005.
10. Harris, T., and Peyton Jones,
S. Transactional memory with
data invariants. TRAnSACT’06:
Proceedings of the 1st ACM
SIGPLAn Workshop on Languages,
Compilers, and Hardware Support for
Transactional Computing, June 2006.
11. Herlihy, M., Luchangco, V., Moir, M.,
and Scherer, III, W.N. Software
transactional memory for dynamic-sized
data structures. PODC’03: Proceedings
of the 22nd ACM Symposium on
Principles of Distributed Computing, pp.
92–101, ACM, July 2003.
12. Herlihy, M. and Moss, J.E. B.
Transactional memory: Architectural
support for lock-free data structures.
ISCA’93: Proceedings of the 20th
International Symposium on
Computer Architecture, pp. 289–300,
ACM, May 1993.
13. Kumar, S., Chu, M., J. Hughes, C.,
Kundu, P., and Nguyen, A. Hybrid
transactional memory. PPoPP’06:
Proceedings of the 11th ACM
Like high-level languages, transactional memory does
not banish bugs altogether; for example, two threads can
easily deadlock if each awaits some communication from
the other. But the gain is very substantial: transactions provide a programming platform for concurrency that eliminates whole classes of concurrency errors, and allows the
programmer to concentrate on the really interesting bits.
acknowledgments
We would like to thank Byron Cook, Austin Donnelly,
Matthew Flatt, Jim Gray, Dan Grossman, Andres Löh, Jon
Howell, Jan-Willem Maessen, Jayadev Misra, Norman Ramsey, Michael Ringenburg, David Tarditi, and especially Tony
Hoare, for their helpful feedback on earlier versions of this
paper, and Guy Steele for his meticulous suggestions in preparing this revised version.
SIGPLAn Symposium on Principles
and Practice of Parallel Programming,
pp. 209–220, ACM, Mar 2006.
14. Larus, J., and Rajwar, R. Transactional
Memory (Synthesis Lectures on
Computer Architecture). Morgan &
Claypool Publishers, 2007.
15. Martin, M., Blundell, C., and Lewis, E.
Subtleties of transactional memory
atomicity semantics. IEEE Comput.
Archit. Lett. 5( 2): 17, 2006.
16. Moore, K.F. and Grossman, D. High-level small-step operational semantics
for transactions. POPL’08: Proceedings
of the 35th ACM SIGPLAn-SIGACT
Symposium on Principles of
Programming Languages, pp. 51–62,
ACM, Jan. 2008.
17. Moss, E.B. Nested transactions: An
approach to reliable distributed
computing. Tech. Rep. MIT/LCS/
TR-260, Massachusetts Institute of
Technology, Apr. 1981.
18. Peyton Jones, S. Tackling the
awkward squad: Monadic input/
output, concurrency, exceptions, and
foreign-language calls in Haskell.
Engineering Theories of Software
Construction, Marktoberdorf Summer
School 2000.
19. Peyton Jones, S. Beautiful
concurrency. In Beautiful Code (2007),
A. Oran and G. Wilson, Eds., O’Reilly.
Tim harris ( tharris@microsoft.com)
Microsoft Research
Simon Marlow (simonmar@microsoft.
com) Microsoft Research
© 2008 ACM 0001-0782/08/0800 $5.00
20. Peyton Jones, S., Gordon, A., and
Finne, S. Concurrent Haskell. POPL’96:
Proceedings of the 23rd ACM
SIGPLAn-SIGACT Symposium on
Principles of Programming Languages,
pp. 295–308, ACM, Jan. 1996.
21. Peyton Jones, S. and Wadler, P.
Imperative functional programming.
POPL’93: Proceedings of the 20th ACM
SIGPLAn-SIGACT Symposium on
Principles of Programming Languages,
pp. 71–84, ACM, Jan. 1993.
22. Rajwar, R., Herlihy, M., and Lai, K.
Virtualizing transactional memory.
ISCA’05: Proceedings of the 32nd
International Symposium on
Computer Architecture, pp. 494–505,
IEEE Computer Society, June 2005.
23. Shavit, N., and Touitou, D. Software
transactional memory. PODC’95:
Proceedings of the 14th ACM
Symposium on Principles of
Distributed Computing, pp. 204–213,
ACM, Aug. 1995.
24. Stone, J. M., Stone, H.S., Heidelberger,
P., and Turek, J. Multiple reservations
and the Oklahoma update. IEEE
Parallel and Distributed Technology
1( 4): 58–71, 1993.
25. Sutter, H. The free lunch is over:
A fundamental turn toward
concurrency in software. Dr. Dobb’s J.
(March 2005).
Simon Peyton Jones (simonpj@microsoft.
com) Microsoft Research
Maurice herlihy ( mph@cs.brown.edu)
Brown University