THIS text is about programming language concepts. The goal is not to learn the nuances of particular languages, but rather to explore and establish a deeper understanding of the general concepts or principles of programming languages, with a particular emphasis on programming. Such an understanding prepares us to evaluate how a variety of languages address these concepts and to discern the appropriate languages for a given task. It also arms us with a larger toolkit of programming techniques from which to build abstractions. The text’s objectives and the recurring themes and learning outcomes of this course of study are outlined in Sections 1.1, 1.6, and 1.8, respectively.

This text is intended for the student who enjoys problem solving, programming, and exploring new ways of thinking and programming languages that support those views. It exposes readers to alternative styles of programming. The text challenges students to program in languages beyond what they may have encountered thus far in their university studies of computer science studies— specifically, to write programs in languages that do not have variables.

Locus of Focus: Notes for Instructors

This text focuses on the concepts of programming languages that constitute requisite knowledge for undergraduate computer science students. Thus, it is intentionally light on topics that most computing curricula emphasize in other courses. A course in programming languages emphasizes topics that students typically do not experience in other courses: functional programming (Chapter 5), typing (Chapters 7–9), interpreter implementation (Chapters 10–12), control abstraction (Chapter 13), logic/declarative programming (Chapter 14), and, more generally, formalizing the language concepts and the design/implementation options for those concepts that students experience through programming. We also emphasize eclectic language features and programming techniques that lead to powerful and practical programming abstractions: currying, lazy evaluation, and first-class continuations (e.g., call/cc).

Book Overview: At a Glance

The approach to distilling language concepts is captured in the following sequence of topics:

Before we implement concepts in languages, we commence by studying the most fundamental principles of languages and developing a vocabulary of concepts for subsequent study. Chapter 2 covers language definition and description methods (e.g., grammars). We also explore the fundamentals of functional programming (primarily in Scheme in Chapter 5), which is quite different from the styles of programming predominant in the languages with which students are probably most familiar. To manage the complexity inherent in interpreters, we must make effective use of data abstraction techniques. Thus, we also study data abstraction and, specifically, how to define inductive data types, as well as representation strategies to use in the implementation of abstract data types. In Chapters 10–12, we implement a progressive series of interpreters in Python, using functional and object-oriented techniques, for a language called Camille that operationalize the concepts that we study in the first module, including binding, scope, and recursion, and assess the differences in the resulting versions of Camille. Following the interpreter implementation module, we fan out and explore other styles of programming. A more detailed outline of the topics covered is given in Section 1.7.

Chapter Dependencies

The following figure depicts the dependencies between the chapters of this text.

Instructors can take multiple pathways through this text to customize their languages course. Within each of the following tracks, instructors can add or subtract material based on these chapter dependencies to suit the needs of their students.

Multiple Pathways

Since the content in this text is arranged in a modular fashion, the pathways through it are customizable.

Customized Courses of Study

Multiple approaches may be taken toward establishing an understanding of programming language concepts. One way to learn language principles is to study how they are supported in a variety of programming languages and to write programs in those languages to probe those concepts. Another approach to learning language concepts is to implement them by building interpreters for computer languages—the focus of Chapters 10–12. Yet another avenue involves a hybrid of these two approaches. The following tracks through the chapters of this text represent the typical approaches to teaching programming languages.

Concepts-Based Approach

The following figure demonstrates the concepts-based approach through the text.

The path through the text modeled here focuses solely on the conceptual parts of Chapters 9 and 10–12, and omits the “Interpreter Implementation” module in favor of the “Other Styles of Programming” module.

Interpreter-Based Approach

The following figure demonstrates the interpreter-based approach using Python.

This approach is the complement of the concepts-only approach, in that it uses the “Interpreter Implementation” module and the entirety of Chapter 9 instead of the “Other Styles of Programming” module and the conceptual chapters of the “Types” module (i.e., Chapters 7–8).

Hybrid Concepts/Interpreter Approach

The following approach involves a synthesis of the concepts- and interpreter-based approaches.

The pathway modeled here retains the entirety of each of the “Types” and “Other Styles of Programming” modules, but omits Chapter 12 of the “Interpreter Implementation” module, except for the conceptual parts (i.e., the survey of parameter-passing mechanisms, including lazy evaluation).

Mapping from ACM/IEEE Curriculum to Chapters

Table 1 presents a mapping from the nine draft competencies (A–I) for programming languages in the ACM/IEEE Computing Curricula 2020 (Computing Curricula 2020 Task Force 2020, p. 113) to the chapters of this text where the material leading to those competencies is addressed or covered.

Table 1 Mapping from the ACM/IEEE Computing Curricula 2020 to Chapters of This Text

Table 2 presents a mapping from the 17 topics in the ACM/IEEE Curriculum Standards for Programming Languages in Undergraduate CS Degree Programs 2013 [The Joint Task Force on Computing Curricula: Association for Computing Machinery (ACM) and IEEE Computer Society 2013, pp. 155–166] to the chapters of this text where they are covered.

Table 2 Mapping from the 2013 ACM/IEEE Computing Curriculum Standards to Chapters of This Text

Prerequisites for This Course of Study

This book assumes no prior experience with functional or declarative programming or programming in Python, Scheme, Haskell, ML, Prolog, or any of the other languages used in the text. However, we assume that readers are familiar with intermediate imperative and/or object-oriented programming in a block-structured language, such as Java or C++, and have had courses in both data structures and discrete mathematics.

The examples in this text are presented in multiple languages—this is necessary to detach students from an una lingua mindset. However, to keep things simple, the only languages students need to know to progress through this text are Python (Appendix A is a primer on Python programming), Scheme (covered in Chapter 5), and either ML or Haskell (covered in the online appendices). Beyond these languages, a working understanding of Java or C/C++ is sufficient to follow the code snippets and examples because they often use a Java/C-like syntax.

Beyond these requisites, an intellectual and scientific curiosity, a thirst for learning new concepts and exploring compelling ideas, and an inclination to experience familiar ideas from new perspectives are helpful dispositions for this course of study.

A message I aspire to convey throughout this text is that programming should be creative, artistic, and a joy, and programs should be beautiful. The study of programming languages ties multiple loose ends in the study of computer science together and helps foster a more holistic view of the discipline of computing. I hope readers experience multiple epiphanies as they work through the concepts presented and are as mystified as I was the first time I explored and discovered this material. Let the journey begin.

Note to Readers

Establishing an understanding of the organization and concepts of programming languages and the elegant programming abstractions/techniques enabled by a mastery of those concepts requires work. This text encourages its reader to learn language concepts much as one learns to swim or drive a car—not just by reading about it, but by doing it—and within that space lies the joy. A key theme of this text is the emphasis on implementation. The programming exercises afford the reader ample opportunities to implement the language concepts we discuss and require a fair amount of critical thought and design.

Moreover, this text is not intended to be read passively. Students are encouraged to read the text with their Python, Racket Scheme, ML, Haskell, or Prolog interpreter open to enter the expressions as they read them so that they can follow along with our discussion. The reward of these mechanics is a more profound understanding of language concepts resulting from having implemented them, and the epiphanies that emerge during the process.

Lastly, I hope to (1) develop and improve readers’ ability to generalize patterns from the examples provided, and subsequently (2) develop their aptitude and intuition for quickly recognizing new instances of these self-learned patterns when faced with similar problems in domains/contexts in which they have little experience. Thus, many of the exercises seek to evaluate how well readers can synthesize the concepts and ideas presented for use when independently approaching and solving unfamiliar problems.

Supplemental Material

Supplemental material for this text, including presentation slides and other instructor-related resources, is available online.

Source Code Availability

The source code of the Camille interpreters in Python developed in Chapters 10–12 is available as a Git repository in BitBucket at https://bitbucket.org/camilleinterpreter/camille-interpreter-in-python-release/.

Solutions to Conceptual and Programming Exercises

Solutions to all of the conceptual and programming exercises are available only to instructors at go.jblearning.com/perugini1e or by contacting your Jones & Bartlett Learning sales representative.

Programming Language Availability

Acknowledgments

With a goal of nurturing students, and with an abiding respect for the craft of teaching, I have sought to produce a text that both illuminates language concepts that are enlightening to the mind and is faithful and complete as well as useful and practical. Doing so has been a labor of love. This text would not have been possible without the support and inspiration from a variety of sources.

I owe a debt of gratitude to the computer scientists with expertise in languages who, through authoring the beautifully crafted textbooks from which I originally learned this material, have broken new ground in the pedagogy of programming languages: Abelson and Sussman (1996); Friedman, Wand, and Haynes (2001); and Friedman and Felleisen (1996a, 1996b). I am particularly grateful to the scholars and educators who originally explored the language landscape and how to most effectively present the concepts therein. They shared their results with the world through the elegant and innovative books they wrote with precision and flair. You are truly inspirational. My view of programming languages and how best to teach languages has been informed and influenced by these seminal books. In writing this text, I was particularly inspired by Essentials of Programming Languages (Friedman, Wand, and Haynes 2001). Chapters 10–11 and Sections 12.2, 12.4, 12.6, and 12.7 of this text are inspired by their Chapter 3. Our contribution is the use of Python to build EOPL-style interpreters. The Little Schemer (Friedman and Felleisen 1996a) and The Seasoned Schemer (Friedman and Felleisen 1996b) were a delight to read and work through, and The Structure and Interpretation of Computer Programs (Abelson and Sussman 1996) will always be a classic. These books are gifts to our field.

Other books have also been inspiring and influential in forming my approach to teaching and presenting language concepts, including Dybvig 2009, Graham (2004b, 1993), Kamin (1990), Hutton (2007), Krishnamurthi (2003, 2017), Thompson (2007), and Ullman (1997). Readers familiar with these books will observe their imprint here. I have attempted to weave a new tapestry here from the palette set forth in these books through my synthesis of a conceptual/principles-based approach with an interpreter-based approach. I also thank James D. Arthur, Naren Ramakrishnan, and Stephen H. Edwards at Virginia Tech, who first shared this material with me.

I have also been blessed with bright, generous, and humble students who have helped me with the development of this text in innumerable ways. Their help is heartfelt and very much appreciated. In particular, Jack Watkin, Brandon Williams, and Zachary Rowland have contributed significant time and effort. I am forever thankful to and for you. I also thank other University of Dayton students and alumni of the computer science program for helping in various ways, including Travis Suel, Patrick Marsee, John Cresencia, Anna Duricy, Masood Firoozabadi, Adam Volk, Stephen Korenewych, Joshua Buck, Tyler Masthay, Jonathon Reinhart, Howard Poston, and Philip Bohun.

I thank my colleagues Phu Phung and Xin Chen for using preliminary editions of this text in their courses. I also thank the students at the University of Dayton who used early manuscripts of this text in their programming languages courses and provided helpful feedback.

Thanks to John Lewis at Virginia Tech for putting me in contact with Jones & Barlett Learning and providing guidance throughout the process of bringing this text to production. I thank Simon Thompson at the University of Kent (in the United Kingdom) for reviewing a draft of this maniscript and providing helpful feedback. I am grateful to Doug Hodson at the Air Force Institute of Technology and Kim Conde at the University of Dayton for providing helpful editorial comments. Thanks to Julianne Morgan at the University of Dayton for being generous with her time and helping in a variety of ways.

Many thanks to the University of Dayton and the Department of Computer Science, in particular, for providing support, resources, and facilities, including two sabbaticals, to make this text possible. I also thank the team at Jones & Bartlett Learning, especially Ned Hinman, Melissa Duffy, Jennifer Risden, Sue Boshers Jill Hobbs, and James Fortney for their support throughout the entire publication process.

I thank Camille and Carla for their warm hospitality and the members of the Corpus Christi FSSP Mission in Naples, Florida, especially Father Dorsa, Katy Allen, Connor DeLoach, Rosario Sorrentino, and Michael Piedimonte, for their prayers and support.

I thank my parents, Saverio and Georgeanna Perugini, and grandmother, Lucia Daloia, for love and support. Thank you to Mary and Patrick Sullivan; Matthew and Hilary Barhorst and children; Ken and Mary Beth Artz; and Steve and Mary Ann Berning for your friendship and the kindness you have shown me. Lastly, I thank my best friends—my Holy Family family—for your love, prayers, and constant supportive presence in my life: Dimitri Savvas; Dan Warner; Jim and Christina Warner; Maria, Angela, Rosa, Patrick, Joseph, Carl, and Gina Hess; Vince, Carol, and Tosca. I love you. Deo gratias. Ave Maria.

Saverio Perugini
April 2021