Demystifying magic: high-level low-level programming

ABSTRACT

The power of high-level languages lies in their abstraction over hardware and software complexity, leading to greater security, better reliability, and lower development costs. However, opaque abstractions are often show-stoppers for systems programmers, forcing them to either break the abstraction, or more often, simply give up and use a different language. This paper addresses the challenge of opening up a high-level language to allow practical low-level programming without forsaking integrity or performance.

The contribution of this paper is three-fold: 1) we draw together common threads in a diverse literature, 2) we identify a framework for extending high-level languages for low-level programming, and 3) we show the power of this approach through concrete case studies. Our framework leverages just three core ideas: extending semantics via intrinsic methods, extending types via unboxing and architectural-width primitives, and controlling semantics via scoped semantic regimes. We develop these ideas through the context of a rich literature and substantial practical experience. We show that they provide the power necessary to implement substantial artifacts such as a high-performance virtual machine, while preserving the software engineering benefits of the host language.

The time has come for high-level low-level programming to be taken more seriously: 1) more projects now use high-level languages for systems programming, 2) increasing architectural heterogeneity and parallelism heighten the need for abstraction, and 3) a new generation of high-level languages are under development and ripe to be influenced.

REFERENCES

• 1: A.-R. Adl-Tabatabai, J. Bharadwaj, D.-Y. Chen, A. Ghuloum, V. Menon, B. Murphy, M. Serrano, and T. Shpeisman. The StarJIT compiler: a dynamic compiler for managed runtime environments. Intel Technology Journal, 7(1):19--31, Feb. 2003.
• 2: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 3: Mark Aiken , Manuel Fähndrich , Chris Hawblitzel , Galen Hunt , James Larus, Deconstructing process isolation, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178599]
• 4: E. Allen, D. Chase, J. Hallett, V. Luchangco, J.-W. Maesse, S. Ryu, G. L. S. Jr., and S. Tobin-Hochstadt. The Fortress language specification, version 1.0. Technical report, Sun Microsystems, Mar. 2008.
• 5: Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.314-324, November 01-05, 1999, Denver, Colorado, United States
• 6: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 7: Apache. DRLVM -- Dynamic Runtime Layer Virtual Machine. http://harmony.apache.org/subcomponents/drlvm/.
• 8: B. Bershad, S. M. Blackburn, H. Boehm, M. Cierniak, C. Click, D. Frampton, D. Gregg, D. Grove, X. Li, B. Mathiske, and G. Skinner. First Moxie brainstorming meeting, Dec. 2005. http://moxie.sf.net/.
• 9: Brian N. Bershad , Craig Chambers , Susan Eggers , Chris Maeda , Dylan McNamee , Przemyslaw Pardyak , Stefan Savage , Emin Gün Sirer, SPIN: an extensible microkernel for application-specific operating system services, Proceedings of the 6th workshop on ACM SIGOPS European workshop: Matching operating systems to application needs, September 12-14, 1994, Wadern, Germany [doi>10.1145/504390.504408]
• 10: B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 11: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Oil and Water? High Performance Garbage Collection in Java with MMTk, Proceedings of the 26th International Conference on Software Engineering, p.137-146, May 23-28, 2004
• 12: S. M. Blackburn, S. I. Salishev, M. Danilov, O. A. Mokhovikov, A. A. Nashatyrev, P. A. Novodvorsky, V. I. Bogdanov, X. F. Li, and D. Ushakov. The Moxie JVM experience. Technical Report TRCS-08-01, Australian National University, Department of Computer Science, Jan. 2008.
• 13: Hans-Juergen Boehm, Space efficient conservative garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.197-206, June 21-25, 1993, Albuquerque, New Mexico, United States
• 14: Hans-J. Boehm, Threads cannot be implemented as a library, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 15: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 16: L. Cardelli, J. Donahue, L. Glassman, I. Jordan, B. Kalsow, and G. Nelson. Modula-3 report (revised). Technical Report 52, DEC SRC, Nov. 1989.
• 17: B.L. Chamberlain , D. Callahan , H.P. Zima, Parallel Programmability and the Chapel Language, International Journal of High Performance Computing Applications, v.21 n.3, p.291-312, August 2007 [doi>10.1177/1094342007078442]
• 18: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 19: Michal Cierniak , Marsha Eng , Neal Glew , Brian Lewis , James Stichnoth, The Open Runtime Platform: a flexible high-performance managed runtime environment: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.5-6, p.617-637, April 2005 [doi>10.1002/cpe.v17:5/6]
• 20: ECMA. C# Language Specification, ECMA-334. http://www.ecma-international.org/publications/standards/Ecma-334.htm, June 2006. (ISO/IEC 23270:2006).
• 21: ECMA. Common Language Infrastructure (CLI), ECMA-335. http://www.ecma-international.org/publications/standards/Ecma-335.htm, June 2006. (ISO/IEC 23271:2006).
• 22: Manuel Fähndrich , Mark Aiken , Chris Hawblitzel , Orion Hodson , Galen Hunt , James R. Larus , Steven Levi, Language support for fast and reliable message-based communication in singularity OS, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium
• 23: Pietro Ferrara , Francesco Logozzo , Manuel Fähndrich, Safer unsafe code for .NET, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 24: M. E. Fiuczynski, W. C. Hsieh, E. G. Sirer, P. Pardyak, and B. N. Bershad. Low-level systems programming with Modula-3. In Threads: A Modula-3 Newsletter, number 3, Fall 1997.
• 25: C. Flack, T. Hosking, and J. Vitek. Idioms in OVM. Technical Report CSD-TR-03-017, Purdue University, 2003.
• 26: John G. Fletcher, No! high level languages should not be used to write systems software, Proceedings of the 1975 annual conference, p.209-211, January 1975 [doi>10.1145/800181.810319]
• 27: J. G. Fletcher , C. S. Badger , G. L. Boer , G. G. Marshall, On the appropriate language for system programming, ACM SIGPLAN Notices, v.7 n.7, p.28-30, July 1972 [doi>10.1145/953360.953361]
• 28: Dennis J. Frailey, Should high level languages be used to write systems software?, Proceedings of the 1975 annual conference, p.205, January 1975 [doi>10.1145/800181.810317]
• 29: R. Garner. JMTK: a portable memory management toolkit. Honours thesis, Australian National University, Dec. 2003.
• 30: Robin Garner , Stephen M. Blackburn , Daniel Frampton, Effective prefetch for mark-sweep garbage collection, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296915]
• 31: David Gay , Rob Ennals , Eric Brewer, Safe manual memory management, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296911]
• 32: Neal Glew , Spyridon Triantafyllis , Michał Clerniak , Marsha Eng , Brian Lewis , James Stichnoth, LIL: an architecture-neutral language for virtual-machine stubs, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.9-9, May 06-07, 2004, San Jose, California
• 33: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 34: Dan Grossman, Type-safe multithreading in cyclone, Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, January 18-18, 2003, New Orleans, Louisiana, USA
• 35: Thomas Hallgren , Mark P. Jones , Rebekah Leslie , Andrew Tolmach, A principled approach to operating system construction in Haskell, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 36: Timothy Hart , Michael Levin, The New Compiler, Massachusetts Institute of Technology, Cambridge, MA, 1962
• 37: Martin Hirzel , Robert Grimm, Jeannie: granting java native interface developers their wishes, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 38: James J. Horning, Yes! high level languages should be used to write systems software, Proceedings of the 1975 annual conference, p.206-208, January 1975 [doi>10.1145/800181.810318]
• 39: Shan Shan Huang , Amir Hormati , David F. Bacon , Rodric Rabbah, Liquid Metal: Object-Oriented Programming Across the Hardware/Software Boundary, Proceedings of the 22nd European conference on Object-Oriented Programming, July 07-11, 2008, Paphos, Cypress [doi>10.1007/978-3-540-70592-5_5]
• 40: G. Hunt, J. Larus, M. Abadi, M. Aiken, P. Barham, M. Fähndrich, C. Hawblitzel, O. Hodson, S. Levi, N. Murphy, B. Steensgaard, D. Tarditi, T. Wobber, and B. Zill. An overview of the Singularity project. Technical Report MSR-TR-2005-135, Microsoft Research, 2005.
• 41: Galen C. Hunt , James R. Larus, Singularity: rethinking the software stack, ACM SIGOPS Operating Systems Review, v.41 n.2, p.37-49, April 2007 [doi>10.1145/1243418.1243424]
• 42: Trevor Jim , J. Greg Morrisett , Dan Grossman , Michael W. Hicks , James Cheney , Yanling Wang, Cyclone: A Safe Dialect of C, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.275-288, June 10-15, 2002
• 43: K. Kennedy. Generation of high performance domain-specific languages from component libraries. http://www.cs.rice.edu/~ken/Presentations/TelescopeOSU.pdf.
• 44: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 45: S. Kuksenko. Suggestion: Let's write some small and hot native (kernel) methods on vmmagics. http://www.mail-archive.com/[e-mail]/msg07606.html, May 2007.
• 46: D. Lea. Low-level memory fences. http://gee.cs.oswego.edu/dl/concurrent/dist/docs/java/util/concurrent/atomic/Fences.html.
• 47: Sheng Liang, Java Native Interface: Programmer's Guide and Reference, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 48: Jan-Willem Maessen , Vivek Sarkar , David Grove, Program analysis for safety guarantees in a Java virtual machine written in Java, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.62-65, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379668]
• 49: S. Microsystems. Maxine Research Project. http://research.sun.com/projects/maxine.
• 50: J. Eliot B. Moss , Trek Palmer , Timothy Richards , Edward K. Walters, II , Charles C. Weems, CISL: a class-based machine description language for co-generation of compilers and simulators, International Journal of Parallel Programming, v.33 n.2, p.231-246, June 2005 [doi>10.1007/s10766-005-3587-1]
• 51: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 52: E. Prangsma. Why Java is practical for modern operating systems. In Libre Software Meeting, 2005. Presentation only. See www.jnode.org.
• 53: Martin Richards, BCPL: a tool for compiler writing and system programming, Proceedings of the May 14-16, 1969, spring joint computer conference, May 14-16, 1969, Boston, Massachusetts [doi>10.1145/1476793.1476880]
• 54: Armin Rigo , Samuele Pedroni, PyPy's approach to virtual machine construction, Companion to the 21st ACM SIGPLAN symposium on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA [doi>10.1145/1176617.1176753]
• 55: Dennis M. Ritchie, The development of the C language, The second ACM SIGPLAN conference on History of programming languages, p.201-208, April 20-23, 1993, Cambridge, Massachusetts, United States
• 56: Stuart Ritchie, Systems Programming in Java, IEEE Micro, v.17 n.3, p.30-35, May 1997 [doi>10.1109/40.591652]
• 57: Jonathan Shapiro, Programming language challenges in systems codes: why systems programmers still use C, and what to do about it, Proceedings of the 3rd workshop on Programming languages and operating systems: linguistic support for modern operating systems, p.9-es, October 22-22, 2006, San Jose, California [doi>10.1145/1215995.1216004]
• 58: Doug Simon , Cristina Cifuentes , Dave Cleal , John Daniels , Derek White, Java™ on the bare metal of wireless sensor devices: the squawk Java virtual machine, Proceedings of the 2nd international conference on Virtual execution environments, June 14-16, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134760.1134773]
• 59: Levon Stepanian , Angela Demke Brown , Allan Kielstra , Gita Koblents , Kevin Stoodley, Inlining java native calls at runtime, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064997]
• 60: Bjarne Stroustrup, The C++ programming language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 61: Bjarne Stroustrup, A history of C++: 1979–1991, The second ACM SIGPLAN conference on History of programming languages, p.271-297, April 20-23, 1993, Cambridge, Massachusetts, United States
• 62: David Stutz , Ted Neward , Geoff Shilling, Shared Source Cli Essentials, O'Reilly & Associates, Inc., Sebastopol, CA, 2002
• 63: David Ungar , Adam Spitz , Alex Ausch, Constructing a metacircular Virtual machine in an exploratory programming environment, Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA [doi>10.1145/1094855.1094865]
• 64: Kris Venstermans , Lieven Eeckhout , Koen De Bosschere, 64-bit versus 32-bit Virtual Machines for Java: Research Articles, Software—Practice & Experience, v.36 n.1, p.1-26, January 2006 [doi>10.1002/spe.v36:1]
• 65: J. R. Vernooij. SAMBA developers guide. http://www.samba.org/samba/docs/Samba-Developers-Guide.pdf, Apr. 2008.
• 66: John Whaley, Joeq: a virtual machine and compiler infrastructure, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.58-66, June 12-12, 2003, San Diego, California [doi>10.1145/858570.858577]
• 67: W. A. Wulf , D. B. Russell , A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, v.14 n.12, p.780-790, Dec. 1971 [doi>10.1145/362919.362936]
• 68: Hiroshi Yamauchi , Mario Wolczko, Writing Solaris device drivers in Java, Proceedings of the 3rd workshop on Programming languages and operating systems: linguistic support for modern operating systems, p.3-es, October 22-22, 2006, San Jose, California [doi>10.1145/1215995.1215998]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection); Run-time environments; Optimization; Compilers

General Terms:
Design, Experimentation, Languages, Performance, Reliability

Keywords:
debugging, intrinsics, jikes rvm, magic, mmtk, systems programming, virtualization, vmmagic