skip to main content
10.1145/3133850.3133857acmconferencesArticle/Chapter ViewAbstractPublication PagessplashConference Proceedingsconference-collections
research-article
Open access

Selfie and the basics

Published: 25 October 2017 Publication History

Abstract

Imagine a world in which virtually everyone at least intuitively understands the fundamental principles of information and computation. However, computer science, in research and in education, is still a young field compared to others and lacks maturity despite the enormous demand created by information technology. To address the problem we would like to encourage everyone in the computer science community to go back to their favorite topic and identify the absolute basics that they feel are essential for understanding the topic. We present here our experience in trying to do just that with programming languages and runtime systems as our favorite topic. We argue that understanding the construction of their semantics and the self-referentiality involved in that is essential for understanding computer science. We have developed selfie, a tiny self-compiling C compiler, self-executing MIPS emulator, and self-hosting MIPS hypervisor all implemented in a single, self-contained file using a tiny subset of C. Selfie has become the foundation of our classes on the design and implementation of programming languages and runtime systems. Teaching selfie has also helped us identify some of the absolute basics that we feel are essential for understanding computer science in general.

References

[1]
M. Aigner, A. Haas, C.M. Kirsch, M. Lippautz, A. Sokolova, S. Stroka, and A. Unterweger. 2011. Short-term Memory for Self-collecting Mutators. In Proc. International Symposium on Memory Management (ISMM) . ACM, 99–108.
[2]
M. Aigner and C.M. Kirsch. 2013. ACDC: Towards a Universal Mutator for Benchmarking Heap Management Systems. In Proc. International Symposium on Memory Management (ISMM) . ACM, 75–84.
[3]
M. Aigner, C.M. Kirsch, M. Lippautz, and A. Sokolova. 2015. Fast, Multicore-Scalable, Low-Fragmentation Memory Allocation through Large Virtual Memory and Global Data Structures. In Proc. ACM SIG-PLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA) . ACM, 451–469.
[4]
A. Biere, A. Cimatti, E.M. Clarke, and Y. Zhu. 1999. Symbolic Model Checking without BDDs. In Proc. International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (LNCS), Vol. 1579. Springer, 193–207.
[5]
Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.). 2009. Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, Vol. 185. IOS Press.
[6]
C. Cadar, D. Dunbar, and D. Engler. 2008. KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs. In Proc. USENIX Conference on Operating Systems Design and Implementation (OSDI) . USENIX Association, 209–224.
[7]
S.S. Craciunas, C.M. Kirsch, H. Payer, A. Sokolova, H. Stadler, and R. Staudinger. 2008. A Compacting Real-Time Memory Management System. In Proc. USENIX Annual Technical Conference.
[8]
E.W. Dijkstra. 1968. The Structure of the “THE”-Multiprogramming System. Commun. ACM 11, 5 (May 1968), 341–346.
[9]
M. Dodds, A. Haas, and C.M. Kirsch. 2015. A Scalable, Correct TimeStamped Stack. In Proc. Symposium on Principles of Programming Languages (POPL) . ACM, 233–246.
[10]
Matthias Felleisen, Conrad Barski, and David Van Horn. 2013. Realm of Racket: Learn to Program, One Game at a Time! No Starch Press.
[11]
M. Felleisen and S. Krishnamurthi. 2009. Viewpoint: Why Computer Science Doesn’t Matter. Commun. ACM 52, 7 (July 2009), 37–40.
[12]
B. Ford, M. Hibler, J. Lepreau, P. Tullmann, G. Back, and S. Clawson. 1996. Microkernels Meet Recursive Virtual Machines. In Proc. Symposium on Operating Systems Design and Implementation (OSDI) . ACM, 137–151.
[13]
P. Godefroid, M. Y. Levin, and D. Molnar. 2008. Automated Whitebox Fuzz Testing. In Proc. Symposium on Network and Distributed Systems Security (NDSS) . 151–166.
[14]
Adele Goldberg and David Robson. 1983. Smalltalk-80: The Language and Its Implementation . Addison Wesley.
[15]
John L. Hennessy and David A. Patterson. 2011. Computer Architecture: A Quantitative Approach . Morgan Kaufmann.
[16]
T.A. Henzinger, C.M. Kirsch, H. Payer, A. Sezgin, and A. Sokolova. 2013. Quantitative Relaxation of Concurrent Data Structures. In Proc. Symposium on Principles of Programming Languages (POPL) . ACM.
[17]
Matt Kaufmann, Panagiotis Manolios, and J Strother Moore. 2000. Computer-Aided Reasoning: An Approach . Kluwer.
[18]
Brian W. Kernighan and Dennis M. Ritchie. 2000. The C Programming Language . Prentice Hall.
[19]
G. Klein, K. Elphinstone, G. Heiser, J. Andronick, D. Cock, P. Derrin, D. Elkaduwe, K. Engelhardt, R. Kolanski, M. Norrish, T. Sewell, H. Tuch, and S. Winwood. 2009. seL4: Formal Verification of an OS Kernel. In Proc. ACM SIGOPS Symposium on Operating Systems Principles (SOSP) . ACM, 207–220.
[20]
Donald E. Knuth. 2011. The Art of Computer Programming, Volumes 1–4 . Addison Wesley.
[21]
Ramana Kumar. 2015. Self-compilation and self-verification. PhD thesis. University of Cambridge.
[22]
Ole Lehrmann Madsen, Birger Mø-Pedersen, and Kristen Nygaard. 1993. Object-oriented Programming in the BETA Programming Language. ACM Press/Addison Wesley.
[23]
J. Liedtke. 1996. Toward Real Microkernels. Commun. ACM 39, 9 (Sept. 1996), 70–77.
[24]
Noam Nisan and Shimon Schocken. 2005. The Elements of Computing Systems: Building a Modern Computer from First Principles . MIT Press.
[25]
Martin Richards and Colin Whitby-Strevens. 2009. BCPL: The Language and its Compiler . Cambridge University Press.
[26]
Patty M. Sailer, Philip M. Sailer, and David R. Kaeli. 1996. The DLX Instruction Set Architecture Handbook (1st ed.). Morgan Kaufmann.
[27]
Michael Sipser. 1996. Introduction to the Theory of Computation. International Thomson Publishing.
[28]
Gerald Jay Sussman and Hal Abelson. 1996. Structure and Interpretation of Computer Programs . MIT Press, Second Edition.
[29]
Y. Vizel, G. Weissenbacher, and S. Malik. 2015. Boolean Satisfiability Solvers and Their Applications in Model Checking. Proc. IEEE 103, 11 (2015), 2021–2035.
[30]
Niklaus Wirth. 1973. Systematic Programming: An Introduction. Prentice Hall.
[31]
Niklaus Wirth. 1976. Algorithms + Data Structures = Programs. Prentice Hall.
[32]
Niklaus Wirth. 1996. Compiler Construction. Addison Wesley.

Cited By

View all
  • (2021)ASE: A Value Set Decision Procedure for Symbolic Execution2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)10.1109/ASE51524.2021.9678584(203-214)Online publication date: Nov-2021
  • (2019)ChocoPy: a programming language for compilers coursesProceedings of the 2019 ACM SIGPLAN Symposium on SPLASH-E10.1145/3358711.3361627(41-45)Online publication date: 25-Oct-2019
  • (2018)On the self in selfie (invited talk)Proceedings of the 10th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3281287.3281288(1-3)Online publication date: 4-Nov-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
Onward! 2017: Proceedings of the 2017 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software
October 2017
261 pages
ISBN:9781450355308
DOI:10.1145/3133850
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 October 2017

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Computer Science for All
  2. Self-Referentiality

Qualifiers

  • Research-article

Conference

SPLASH '17
Sponsor:

Acceptance Rates

Overall Acceptance Rate 40 of 105 submissions, 38%

Upcoming Conference

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)142
  • Downloads (Last 6 weeks)15
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)ASE: A Value Set Decision Procedure for Symbolic Execution2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)10.1109/ASE51524.2021.9678584(203-214)Online publication date: Nov-2021
  • (2019)ChocoPy: a programming language for compilers coursesProceedings of the 2019 ACM SIGPLAN Symposium on SPLASH-E10.1145/3358711.3361627(41-45)Online publication date: 25-Oct-2019
  • (2018)On the self in selfie (invited talk)Proceedings of the 10th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3281287.3281288(1-3)Online publication date: 4-Nov-2018
  • (2018)You Can Program What You Want but You Cannot Compute What You WantPrinciples of Modeling10.1007/978-3-319-95246-8_1(1-15)Online publication date: 20-Jul-2018

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media