Skip to main content
SpringerLink
Log in
Book cover

International and Interdisciplinary Conference on Modeling and Using Context

CONTEXT 2007: Modeling and Using Context pp 291–302Cite as

Delimited Continuations in Operating Systems

  • Conference paper

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 4635))

Abstract

Delimited continuations are the meanings of delimited evaluation contexts in programming languages. We show they offer a uniform view of many scenarios that arise in systems programming, such as a request for a system service, an event handler for input/ output, a snapshot of a process, a file system being read and updated, and a Web page. Explicitly recognizing these uses of delimited continuations helps us design a system of concurrent, isolated transactions where desirable features such as snapshots, undo, copy-on-write, reconciliation, and interposition fall out by default. It also lets us take advantage of efficient implementation techniques from programming-language research. The Zipper File System prototypes these ideas.

This is a preview of subscription content, log in via an institution.

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Reynolds, J.C.: The discoveries of continuations. Lisp and Symbolic Computation 6, 233–247 (1993)

    Article  Google Scholar 

  2. Strachey, C., Wadsworth, C.P.: Continuations: A mathematical semantics for handling full jumps. Higher-Order and Symbolic Computation 13, 135–152 (2000)

    Article  MATH  Google Scholar 

  3. Fischer, M.J.: Lambda-calculus schemata. Lisp and Symbolic Computation 6, 259–288 (1993)

    Article  Google Scholar 

  4. Kelsey, R., Clinger, W.D., Rees, J., Abelson, H., Dybvig, R.K., Haynes, C.T., Rozas, G.J., Adams IV, N.I., Friedman, D.P., Kohlbecker, E., Steele, G.L., Bartley, D.H., Halstead, R., Oxley, D., Sussman, G.J., Brooks, G., Hanson, C., Pitman, K.M., Wand, M.: Revised5 report on the algorithmic language Scheme. Higher-Order and Symbolic Computation 11, 7–105 (1998), Also as ACM SIGPLAN Notices 33(9), 26–76

    Google Scholar 

  5. Steele, Jr., G.L.: RABBIT: A compiler for SCHEME. Master’s thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Also as Memo 474, Artificial Intelligence Laboratory, Massachusetts Institute of Technology (1978)

    Google Scholar 

  6. Shan, C.c., Barker, C.: Explaining crossover and superiority as left-to-right evaluation. Linguistics and Philosophy 29, 91–134 (2006)

    Article  Google Scholar 

  7. Barker, C., Shan, C.c.: Types as graphs: Continuations in type logical grammar. Journal of Logic, Language and Information 15, 331–370 (2006)

    Article  MathSciNet  Google Scholar 

  8. Wand, M.: Continuation-based multiprocessing revisited. Higher-Order and Symbolic Computation, 283 (1999)

    Google Scholar 

  9. Ritchie, D.M.: The Evolution of the Unix Time-sharing System. AT&T Bell Laboratories Technical Journal 63, 1577–1593 (1984)

    Google Scholar 

  10. Sitaram, D., Felleisen, M.: Control delimiters and their hierarchies. Lisp and Symbolic Computation 3, 67–99 (1990)

    Article  Google Scholar 

  11. Kiselyov, O.: How to remove a dynamic prompt: Static and dynamic delimited continuation operators are equally expressible. Technical Report 611, Computer Science Department, Indiana University (2005)

    Google Scholar 

  12. Kiselyov, O., Shan, C.c., Friedman, D.P., Sabry, A.: Backtracking, interleaving, and terminating monad transformers (functional pearl). In: ICFP 2005: Proceedings of the ACM International Conference on Functional Programming, pp. 192–203. ACM Press, New York (2005)

    Chapter  Google Scholar 

  13. Cartwright, R., Felleisen, M.: Extensible denotational language specifications. In: Hagiya, M., Mitchell, J.C. (eds.) TACS 1994. LNCS, vol. 789, pp. 244–272. Springer, Heidelberg (1994)

    Google Scholar 

  14. Kumar, S., Bruggeman, C., Dybvig, R.K.: Threads yield continuations. Lisp and Symbolic Computation 10(2), 223–236 (1998)

    Article  Google Scholar 

  15. Dybvig, R.K., Hieb, R.: Continuations and concurrency. In: Proceedings of the Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 128–136. ACM Press, New York (1990)

    Google Scholar 

  16. Dybvig, R.K., Hieb, R.: Engines from continuations. Journal of Computer Languages 14(2), 109–123 (1989)

    Article  Google Scholar 

  17. Shivers, O.: Continuations and threads: Expressing machine concurrency directly in advanced languages. In: Proceedings of the Second ACM SIGPLAN Workshop on Continuations, ACM Press, New York (1997)

    Google Scholar 

  18. Haynes, C.T., Friedman, D.P., Wand, M.: Obtaining coroutines with continuations. Journal of Computer Languages 11, 143–153 (1986)

    Article  MATH  Google Scholar 

  19. Li, P., Zdancewic, S.: A language-based approach to unifying events and threads (2006), http://www.cis.upenn.edu/~stevez/papers/LZ06b.pdf

  20. Adya, A., Howell, J., Theimer, M., Bolosky, W.J., Douceur, J.R.: Cooperative task management without manual stack management, or, event-driven programming is not the opposite of threaded programming. In: Proceedings of the 2002 USENIX Annual Technical Conference, USENIX, pp. 289–302 (2002)

    Google Scholar 

  21. Sumii, E.: An implementation of transparent migration on standard Scheme. In: Felleisen, M. (ed.) Proceedings of the Workshop on Scheme and Functional Programming. Number 00-368 in Tech. Rep. Department of Computer Science, Rice University, pp. 61–63 (2000)

    Google Scholar 

  22. Sewell, P., Leifer, J.J., Wansbrough, K., Zappa Nardelli, F., Allen-Williams, M., Habouzit, P., Vafeiadis, V.: Acute: High-level programming language design for distributed computation. In: ICFP 2005: Proceedings of the ACM International Conference on Functional Programming, pp. 15–26. ACM Press, New York (2005)

    Chapter  Google Scholar 

  23. Murphy VII, T., Crary, K., Harper, R.: Distributed control flow with classical modal logic. In: Ong, C.H.L. (ed.) CSL 2005. LNCS, vol. 3634, pp. 51–69. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  24. Queinnec, C.: Continuations and web servers. Higher-Order and Symbolic Computation 17, 277–295 (2004)

    Article  Google Scholar 

  25. Graunke, P.T.: Web Interactions. PhD thesis, College of Computer Science, Northeastern University (2003)

    Google Scholar 

  26. Colomba, A.: SISCweb: A framework to facilitate writing stateful Scheme web applications in a J2EE environment (2007), http://siscweb.sf.net/

  27. Balat, V., et al.: Ocsigen: A Web server and a programming framework providing a new way to create dynamic Web sites (2007), http://www.ocsigen.org

  28. Belapurkar, A.: Use continuations to develop complex Web applications. IBM developerWorks (2004)

    Google Scholar 

  29. Krishnamurthi, S., Hopkins, P.W., McCarthy, J., Graunke, P.T., Pettyjohn, G., Felleisen, M.: Implementation and use of the PLT Scheme Web server. Higher-Order and Symbolic Computation (2007)

    Google Scholar 

  30. Williams, N.J.: An implementation of scheduler activations on the NetBSD operating system. In: Proceedings of the FREENIX Track: USENIX Annual Technical Conference, Berkeley, CA, USENIX (2002) pp. 99–108 (2002)

    Google Scholar 

  31. Shieh, A., Myers, A., Sirer, E.G.: Trickles: A stateless transport protocol. Summaries of OSDI 2004. USENIX;login (2004) 6th Symposium on Operating Systems Design and Implementation, OSDI 2004. vol. 30(2) p. 66, Work-in-Progress Reports (2005)

    Google Scholar 

  32. Hallgren, T., Jones, M.P., Leslie, R., Tolmach, A.P.: A principled approach to operating system construction in Haskell. In: Danvy, O., Pierce, B.C. (eds.) Proceedings of the 10th ACM SIGPLAN International Conference on Functional Programming, ICFP 2005, Tallinn, Estonia, September 26-28, 2005, pp. 116–128. ACM Press, New York (2005)

    Chapter  Google Scholar 

  33. Launchbury, J., Peyton Jones, S.L.: State in Haskell. Lisp and Symbolic Computation 8, 293–341 (1995)

    Article  Google Scholar 

  34. Moggi, E., Sabry, A.: Monadic encapsulation of effects: A revised approach (extended version). Journal of Functional Programming 11, 591–627 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  35. Danvy, O., Nielsen, L.R.: Defunctionalization at work. In: Proceedings of the 3rd International Conference on Principles and Practice of Declarative Programming, pp. 162–174. ACM Press, New York (2001)

    Chapter  Google Scholar 

  36. Nyström, J.H., Trinder, P.W., King, D.J.: Are high-level languages suitable for robust telecoms software? In: Winther, R., Gran, B.A., Dahll, G. (eds.) SAFECOMP 2005. LNCS, vol. 3688, pp. 275–288. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  37. Kiselyov, O.: General ways to traverse collections (2004), http://okmij.org/ftp/Scheme/enumerators-callcc.html http://okmij.org/ftp/Computation/Continuations.html

  38. Huet, G.: The zipper. Journal of Functional Programming 7, 549–554 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  39. Clinger, W.D., Hartheimer, A., Ost, E.M.: Implementation strategies for continuations. Higher-Order and Symbolic Computation 12, 7–45 (1999)

    Article  MATH  Google Scholar 

  40. Bruggeman, C., Waddell, O., Dybvig, R.K.: Representing control in the presence of one-shot continuations. In: ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation, ACM Press, New York (1996)

    Google Scholar 

  41. Gasbichler, M., Sperber, M.: Final shift for call/cc: Direct implementation of shift and reset. In: ICFP 2002: Proceedings of the ACM International Conference on Functional Programming, pp. 271–282. ACM Press, New York (2002)

    Chapter  Google Scholar 

  42. Derrin, P., Elphinstone, K., Klein, G., Cock, D., Chakravarty, M.M.T.: Running the manual: an approach to high-assurance microkernel development. In: Haskell 2006: Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, pp. 60–71. ACM Press, New York (2006)

    Chapter  Google Scholar 

  43. Jones, I., et al.: Halfs, a Haskell filesystem (2006), http://www.haskell.org/halfs/

  44. Ernst, E.: Method mixins. Report PB-557, Department of Computer Science, University of Aarhus, Denmark (2002)

    Google Scholar 

  45. Van Roy, P.: Convergence in language design: A case of lightning striking four times in the same place. In: Hagiya, M., Wadler, P. (eds.) FLOPS 2006. LNCS, vol. 3945, pp. 2–12. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. FNMOC,  

    Oleg Kiselyov

  2. Rutgers University,  

    Chung-chieh Shan

Authors
  1. Oleg Kiselyov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chung-chieh Shan
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Boicho Kokinov Daniel C. Richardson Thomas R. Roth-Berghofer Laure Vieu

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kiselyov, O., Shan, Cc. (2007). Delimited Continuations in Operating Systems. In: Kokinov, B., Richardson, D.C., Roth-Berghofer, T.R., Vieu, L. (eds) Modeling and Using Context. CONTEXT 2007. Lecture Notes in Computer Science(), vol 4635. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74255-5_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-74255-5_22

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-74254-8

  • Online ISBN: 978-3-540-74255-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation