-
Notifications
You must be signed in to change notification settings - Fork 11
Collected Papers and Books on Language Design
This list was started from a series of emails requesting recommendations for grad students studying language design. This list is gathered here, and we hope to elaborate, distill and add commentary as the list evolves.
Ken Iverson’s Notation as a Tool of Thought
John Backus’s Can Programming Be Liberated From the von Neumann Style?
Dennis Ritchie’s “The Development of the C Language” (my version attached) ascribes it to BCPL and B compatibility. See the end of the section “Origins: the languages” and the first part of the section “Embryonic C”.
https://dl.acm.org/doi/abs/10.1145/155360.155580 From HOPL-2: https://dl.acm.org/toc/sigplan/1993/28/3
- Specific languages
Anonymous [Greg Nelson]. How the language got its spots. Chapter 8 of System Programming With Modula-3. Prentice-Hall, 1991. https://archive.org/details/systems-programming-with-modula-3/page/216/mode/2up?view=theater [A fictional dialog between five designers discussing aspects of Modula-3’s type system, generics, and parameter passing modes.]
Herbert Stoyan. Early LISP history (1956-1959). In Proceedings of the 1984 ACM Symposium on LISP and functional programming, Austin, Texas, pages 299-310. https://dl.acm.org/doi/pdf/10.1145/800055.802047 (open access) [A history paper, very interesting because Stoyan reconstructs McCarthy’s design process almost step-by-step by studying McCarthy’s early writings, many of which are available here: https://www.softwarepreservation.org/projects/LISP/lisp15_family/#Documents_ .]
Guy L. Steele Jr. Growing a Language. OOPSLA 1998 and Higher-Order and Symbolic Computation volume 12, pages 221–236 (1999). https://www.cs.virginia.edu/~evans/cs655/readings/steele.pdf https://www.youtube.com/watch?v=_ahvzDzKdB0 https://doi.org/10.1023/A:1010085415024
T.R.G. Green, M. Petre, Usability Analysis of Visual Programming Environments: A ‘Cognitive Dimensions’ Framework, Journal of Visual Languages & Computing, Volume 7, Issue 2, 1996, Pages 131-174, ISSN 1045-926X, https://doi.org/10.1006/jvlc.1996.0009. (https://www.sciencedirect.com/science/article/pii/S1045926X96900099) Abstract: The cognitive dimensions framework is a broad-brush evaluation technique for interactive devices and for non-interactive notations. It sets out a small vocabulary of terms designed to capture the cognitively-relevant aspects of structure, and shows how they can be traded off against each other. The purpose of this paper is to propose the framework as an evaluation technique for visual programming environments. We apply it to two commercially-available dataflow languages (with further examples from other systems) and conclude that it is effective and insightful; other HCI-based evaluation techniques focus on different aspects and would make good complements. Insofar as the examples we used are representative, current VPLs are successful in achieving a good ‘closeness of match’, but designers need to consider the ‘viscosity ’ (resistance to local change) and the ‘secondary notation’ (possibility of conveying extra meaning by choice of layout, colour, etc.).
A major research direction for many years has been finding alternatives for traditional text-based source representation and parsing, moving towards language workbenches, structural editing etc. This has really not happened, but IDEs and compilers have become quite intertwined. Maybe Eelco Visser's Spoofax paper is a good (seminal) one on language workbenches:
Lennart C.L. Kats and Eelco Visser. 2010. The spoofax language workbench: rules for declarative specification of languages and IDEs. In Proceedings of the ACM international conference on Object oriented programming systems languages and applications (OOPSLA '10). Association for Computing Machinery, New York, NY, USA, 444–463. https://doi.org/10.1145/1869459.1869497
(In 2021 it received the most influential paper award of 2010 OOPSLA).
A lot has happened with expressing concurrency in the past decade or so: coroutines are back in fashion, futures and promises are pretty standard ways of arranging computations. Maybe the reading list could include papers about algebraic effects, which offer a unifying (perhaps practical) framework for these control structures (and others, including exceptions and continuations). Algebraic effects in their purest form are perhaps in the (research language) Koka by Dan Leijen. Not sure which paper would be the best. Two suggestions:
Daan Leijen. 2017. Structured asynchrony with algebraic effects. In Proceedings of the 2nd ACM SIGPLAN International Workshop on Type-Driven Development (TyDe 2017). Association for Computing Machinery, New York, NY, USA, 16–29. https://doi.org/10.1145/3122975.3122977
Daan Leijen. 2017. Type directed compilation of row-typed algebraic effects. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL '17). Association for Computing Machinery, New York, NY, USA, 486–499. https://doi.org/10.1145/3009837.3009872
Gradual typing has become mainstream in the most recent decade or so (think TypeScript, Flowtype, type hints in Python), so maybe that could be covered. There is a ton of papers, so it is hard to pick just one. This paper gives a pretty solid explanation of what gradual typing is, and some categorises various systems in the gradual landscape of gradual typing, so maybe a good starting point:
https://drops.dagstuhl.de/opus/volltexte/2015/5031/pdf/21.pdf
Webassembly is quite influential (and Bjarne's really excellent student Luke Wagner is one of the authors :)
Andreas Haas, Andreas Rossberg, Derek L. Schuff, Ben L. Titzer, Michael Holman, Dan Gohman, Luke Wagner, Alon Zakai, and JF Bastien. 2017. Bringing the web up to speed with WebAssembly. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2017). Association for Computing Machinery, New York, NY, USA, 185–200. https://doi.org/10.1145/3062341.3062363
Maybe somerhing about ownership types, as Rust brought them to focus (and ownership very connected to C++ and RAII):
David J. Pearce. 2021. A Lightweight Formalism for Reference Lifetimes and Borrowing in Rust. ACM Trans. Program. Lang. Syst. 43, 1, Article 3 (March 2021), 73 pages. https://doi.org/10.1145/3443420
“Communicating Sequential Processes” by C.A.R. Hoare
“A Theory of Type Polymorphism in Programming” by R. Milner
“The Development of the C Language” by D.M.Ritchie
“Comprehending Monads” by P. Wadler
“Parsing Expression Grammars: A Recognition-Based Syntactic Foundation” by B. Ford
“A Comparative Study of Language Support for Generic Programming” by R/ Garcia, J. Järvi, A. Lumsdaine, J. Siek, and J. Willcock
TARTAN: Language Design for the Ironman Requirement: Notes and Examples Mary Shaw, Paul Hilfinger, Wm. A. Wulf Carnegie-Mellon University technical report CMU-CS-78-132
A History of CLU Barbara Liskov Massachusetts Institute of Technology, April 1992 (sorry, but my copy has no publication information)
Eiffel: An introduction Bertrand Meyer Interactive Software Engineering Inc. report TR-EI-3/GI version 2.1
Early Experience with Mesa Charles M. Geschke, James H. Morris Jr., Edwin H Slatterthwaite Communications of the ACM, August 1977, volume 20, number 8
The Denotational Semantics of Programming Languages R.D. Tennent Communications of the ACM, August 1976, volume 19, number 8
Self: The Power of Simplicity David Ungar, R. B. Smith OOPSLA '87 Conference Proceedings SIGPLAN Notices, volume 22, number 12, December 1987
From Modula to Oberon N. Wirth Tuesday 23 February 1988 (sorry, but my copy has no publication information)
The Ada Rational I suggest this because Ada exposes some language structures as choices available to the programmer that other languages implicitly make.
Wirth’s Compiler Construction if you can find a copy.
Bertrand Meyer’s Introduction to the Theory of Programming Languages
Denotational Semantics: A Methodology for Language Development by David A. Schmidt