Programming Language Design and Implementation (Torben Ægidius Mogensen) (z-library.sk, 1lib.sk, z-lib.sk)

Texts in Computer ScienceTCS M ogensen Programming Language Design and Implementation Program m ing Language Design and Im plem entation Second Edition 2nd Ed. Torben Ægidius Mogensen

Texts in Computer Science Series Editors Orit Hazzan, Faculty of Education in Technology and Science, Technion—Israel Institute of Technology, Haifa, Israel Frank Maurer, Department of Computer Science, University of Calgary, Calgary, Canada

Titles in this series now included in the Thomson Reuters Book Citation Index! ‘Texts in Computer Science’ (TCS) delivers high-quality instructional content for undergraduates and graduates in all areas of computing and information sci- ence, including core theoretical/foundational as well as advanced applied topics. TCS books should be reasonably self-contained and aim to provide students with modern and clear accounts of topics ranging across the computing curriculum. As a result, the books are ideal for semester courses or for individual self-study in cases where people need to expand their knowledge. All texts are authored by established experts in their fields, reviewed internally and by the series editors, and provide numerous examples, problems, and other pedagogical tools; many contain fully worked solutions. The TCS series is comprised of high-quality, self-contained books that have broad and comprehensive coverage and are generally in hardback format and sometimes contain color. For undergraduate textbooks that are likely to be more brief and modular in their approach, Springer offers the flexibly designed Undergraduate Topics in Computer Science series, to which we refer potential authors.

Torben Ægidius Mogensen Programming Language Design and Implementation Second Edition

Torben Ægidius Mogensen Department of Computer Science University of Copenhagen Copenhagen, Denmark ISSN 1868-0941 ISSN 1868-095X (electronic) Texts in Computer Science ISBN 978-3-031-93298-4 ISBN 978-3-031-93299-1 (eBook) https://doi.org/10.1007/978-3-031-93299-1 Originally published with the title: Programming Language Design and Implementation © The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG 2022, 2026 This work is subject to copyright. All rights are solely and exclusively licensed by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This Springer imprint is published by the registered company Springer Nature Switzerland AG The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland If disposing of this product, please recycle the paper.

Preface Design is a funny word. Some people think design means how it looks. But of course, if you dig deeper, it’s really how it works. Steve Jobs Successful design is not the achievement of perfection but the minimization and accommodation of imperfection. Henry Petroski This book aims to provide the reader with an overview of the design space for programming languages and how design choices affect implementation. It is not a classical compilers book, as it assumes the reader is familiar with basic compiler implementation techniques, nor is it a traditional comparative programming languages book, because it does not go into depth about any par- ticular language, but instead take examples from a wide variety of programming languages to illustrate design concepts. The book is organised around concepts. Each concept has a chapter that explains the concept, illustrates the concept through examples from past and present (using both mainstream and obscure languages), discussion about pros and cons of design choices, implementation and, where deemed necessary, a bit of formal theory. It is the opinion of the author that a designer of programming languages should not only know what other language designers have done but also have an opera- tional understanding of the consequences design choices have on implementation of these languages. Otherwise, the designer is liable to make design choices that renders implementation excessively difficult, impedes performance or makes it very hard for the users of the language to predict the behaviour of programs, especially when several language features are used in combination. Therefore, the description of the design space of various language features includes discussion and sketches of implementation. These sketches are not very detailed, but a com- petent programmer with knowledge of basic compiler techniques should be able to use the sketches as a guide for implementation. v

vi Preface If this book can help just one language designer avoid making design choices that she or the users of her language later regrets, it is deemed a success. Do We Need New Programming Languages? In the 1930s, Alonzo Church and Alan Turing independently proposed models for mechanical computation. These models are now known as the lambda calcu- lus and Turing machines, respectively. Together with the logicians Stephen Kleene and J. B. Rosser, they later proved that any computation that can be done using the lambda calculus can also be done using Turing machines, and vice versa. Given that the two models are radically different, this led Church and Turing to hypoth- esise that no model of computation that can be realised by a physical machine can perform computations that can not also be performed by lambda calculus and Turing machines. These models are in this sense universal: They can be used to model any computation, and if something is proven to not be computable using a Turing machine (or the lambda calculus), then it can not be computed at all on a mechanical device. This hypothesis is called Church-Turing Thesis. It is not possible to prove this thesis, as there is no generally accepted formal definition of a mechanical device, but it is generally accepted to be true, as nobody has come up with a physically realisable model for mechanical (or electronic) computation that exceeds the power of Turing machines or lambda calculus. A programming language that (assuming no upper bound on available memory) can do everything a Turing machine or the lambda calculus can do is called Turing complete. Most programming languages are Turing complete, so you can argue that there is no need for new programming languages, as they will not be able to do some- thing that can not already be done. Even so, new languages appear all the time, so computational power is not the only interesting criterion for programming lan- guages. But it can be very hard to find objective criteria for when a new language is better than an existing language. Common criteria are: Program size: Are programs in language A shorter than equivalent programs in language B? Speed: Do programs in language A run faster than equivalent programs in language B? Ease of Programming: Is it easier to write a program in language A than an equivalent program in language B? Ease of reasoning about programs: Is it easier to prove correctness of programs in language A than in language B. But these criteria all have problems: Program size: If both A and B are Turing complete languages, and B can represent the text of programs in A as constants (such as strings) without significant expansion, it is possible to rewrite any sufficiently large program written in A to

Preface vii an equivalent program written in B that is only insignificantly larger. Basically, the rewritten program contains an interpreter for A and the representation of the original program. So any difference in program size will only affect relatively small programs. Speed: Speed of execution is more a matter of how a language is implemented than how it is designed. You can, at best, compare the speed of a particular program written in language A using a particular implementation of this language to a specific equivalent program in a specific implementation of language B. But it is hard to argue that the two programs represent the fastest way of doing this computation in their respective language implementations, so this says little about the speed of the programs themselves, and even less about the languages. Ease of Programming: This is a highly subjective matter: One programmer can think that it is much easier to program in language A, while another prefers language B. Even if you teach non-programmers to program in two differ- ent languages, spending equal effort on both, their preferences may depend on their cultural background, education, or personality, so it is, again, hard so say something objective about the languages themselves. Ease of reasoning about programs: For Turing-complete programming languages, proving that programs are correct with respect to some specification or that they have some desirable property (such as termination) is in general undecidable, so you can argue that all such languages are equally difficult to reason about. On the other hand, in every language, you can prove correctness and termination for some programs, so you can discuss the relative ease of doing so for similar programs in different languages. But reaching definitive conclusions from such discussions is difficult, because the requirement that the programs be similar may require one or both programs to be coded in a way that is not typical for the languages in question, so you can easily end up arguing about program style rather than languages. This does not mean that it is impossible to compare programming languages—one should just avoid very general statements like the above, and one should make reservations clear. But it is perfectly possible to argue that for a specific type of user (programmer), for a specific type of problem, for specific implementations, one language is better suited than another. This also means that a new programming language typically is designed for a specific type of user (programmer), for a specific type of problem or for a specific implementation method or machine.

viii Preface Weak Languages Many of the observations above rely on languages being Turing complete. If a language is not Turing complete, you can perfectly well and precisely argue about computational power, program size and execution speed (on a non-Turing complete machine). But why would you want to use a language that provably can not be used for any sort of computation? Turing completeness may give the highest possible power of computation, but this power itself has a prize: It can be very hard or impossible to decide properties about programs written in Turing complete languages: • It may be impossible to prove that a program is correct with respect to a formal specification. Some programs can be proven correct, but there are programs that can neither be proven correct nor incorrect. • It may be impossible to give bounds on computation time or resource use—even if you just want to know if the bounds are finite or not. Again, it is possible to prove bounds on some programs, but some programs will escape proof. It is possible to design programming languages where such proof or bounds can always be found, but this will be at the cost of Turing completeness. Many domain-specific languages will be deliberately designed this way to ensure spe- cific properties. While these languages can be useless outside the problem domain for which they are designed, they can be very useful for solving problems inside this domain. General Design Principles The remainder of the book will investigate design choices for different aspects of programming languages, but there are some cross-cutting guidelines that apply to the design process as a whole. The following guidelines are not hard laws, but something a designer should at least think about. 1. There is no single perfect language design for any given purpose. This does not mean that all designs are equally good—there are plenty of examples of bad language design. 2. Few design choices are good or bad in isolation, but one design choice may fit a given purpose better than others. And some sets of design choices can benefit each other, while other sets can interact badly. 3. Make everything as simple as possible, but no simpler.1 Simplicity is a good design principle, but one should not over-simplify, as that can impact practicality. 1 This saying is usually attributed to Albert Einsten.

Preface ix 4. If a language is difficult to describe precisely, it is likely difficult to under- stand and use. So make sure syntax and semantics have clear (possibly formal) descriptions. 5. When you design a language or language feature, you should have at least a rough idea of how this can be implemented. This understanding need not be present when a language or feature is investigated (indeed, the investigation may include research for implementation techniques), but it should be before a final design decision is made. 6. Excepting very specialised (domain-specific) languages, a programming lan- guage is not very useful unless it is supported by a comprehensive library—if you have to write everything from scratch, all but the most trivial programs will be major efforts. So, unless you have resources to write a substantial library from scratch, you should enable use of libraries written in or for other programming languages. To the Reader The book has been designed to be used as a textbook in an advanced undergrad- uate or introductory graduate course in computer science and related fields, but it can also be used by professionals who want to design and implement their own programming languages, regardless of whether these are intended for personal use only or they are hoped to become used by a large number of people. The book assumes that the reader is familiar with basic compiler techniques such as parsing and code generation at a level corresponding to an undergraduate introductory compilers course. It also assumes the reader has experience with pro- gramming in at least a couple of significantly different programming languages. In particular, the reader should have at least a bit experience with polymorphically typed functional languages with pattern matching (such as Standard ML, OCaml, F# or Haskell) imperative languages (primarily C) and object-oriented languages (such as Java or C#). If you haven’t already, you can try these languages (and oth- ers) out when they are mentioned in the book. There are plenty of online tutorials you can use for this. Like in most textbooks, each chapter concludes with a number of exercises. These are primarily intended to help the reader get a better understanding of the concepts in the chapter. For this reason, many sections in a chapter will conclude with a few suggestions of exercises that the reader is encouraged to try solving before continuing to the next section. Every chapter also includes a list of suggested further reading that goes deeper into the subjects covered in the chapter.

x Preface A Note About Large Language Models Large language models, often misleadingly called “artificial intelligence”, can probably give plausible and sometimes correct answers to some (but far from all) the exercises in this book. I would, however, warn against using them: The purpose of the exercises is to make you think and learn, and just being told a (pos- sibly wrong) answer by an overconfident chatbot will impede both thinking and learning. About the Second Edition The first edition of this book was published in 2022. Several changes have been made in the second edition (published in 2025), the most notable being: • Splitting the chapter about types into two chapters, one about simple types and the other about polymorphic types. This means that some chapter numbers have changed. • Expanding several chapters, including the two above as well as the chapters about the history of programming languages, modules, and domain-specific languages. Small additions have been made to other chapters. • Adding exercises. Note that this has changed the numbering of some exercises. Copenhagen, Denmark Torben Ægidius Mogensen Acknowledgements I want to thank my co-teacher Hans Hüttel on the course “Pro- gramming Language Design” at the University of Copenhagen for their suggestions for changes for the second edition of this book as well as the students and teaching assistants in the course who have pointed out typos and places where the text could be clearer. I also want to thank James Avery for checking the section on quantum computing for errors and suggesting changes to make it more precise.

Competing Interests The author has no competing interests to declare that are relevant to the content of this manuscript. xi

Contents 1 A Brief History of Programming Languages . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Before Computers: Turing Machines and Lambda Calculus . . . . 2 1.2 Programmable Electronic Computers . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Early and Influential Programming Languages . . . . . . . . . . . . . . . . . 8 1.3.1 Plankalkül . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.2 FORTRAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.3 LISP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.4 COBOL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.5 ALGOL 60 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.6 APL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.7 PL/I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.8 BASIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3.9 Simula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.10 Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.11 Smalltalk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.12 C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.13 Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.14 ISWIM, ML, and Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3.15 Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.3.16 Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.3.17 Rust . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2 Implementation Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.1 Compilation and Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.2 REPLs and IDEs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Intermediate Code and Virtual Machines . . . . . . . . . . . . . . . . . . . . . . 31 2.4 Hybrid Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.5 Cross Compilers, Reverse Compilers, and Obfuscation . . . . . . . . . 34 2.6 Bootstrapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.6.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 xiii

xiv Contents 2.6.2 Compiling Compilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6.3 Full Bootstrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.7 Choosing the Language in Which to Write a Compiler . . . . . . . . . 42 2.8 How Implementation Techniques Can Influence Language Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.1 Lexical Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1.1 Character Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1.2 Case Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.1.3 Identifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.1.4 Whitespace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.1.5 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.1.6 Reserved Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.1.7 Separation of Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.1.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.2 Grammatical Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.2.1 Line-Based Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.2.2 Multi-line Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.3 Syntax that Looks Like a Natural Language . . . . . . . . . . 60 3.2.4 Bracketed Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.2.5 Prefix, Post Fix, and Operator-Precedence Syntax . . . . 62 3.2.6 Context-Free Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.2.7 Stronger Grammar Formalisms . . . . . . . . . . . . . . . . . . . . . . 65 3.2.8 Other Syntactic Considerations . . . . . . . . . . . . . . . . . . . . . . 65 3.2.9 Bracketing Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.3 Concerns that Span Both Lexing and Grammar . . . . . . . . . . . . . . . . 69 3.3.1 Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3.2 Visual Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.4 Considerations When Designing Syntax . . . . . . . . . . . . . . . . . . . . . . . 71 3.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.2 Static Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.3 Stack Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.4 Heap Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.5 Manual Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.5.1 A Simple Implementation of malloc() and free() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

Contents xv 4.5.2 Joining Freed Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.5.3 Sorting by Block Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 4.5.4 Large Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.5.5 Summary of Manual Memory Management . . . . . . . . . . 89 4.6 Automatic Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.7 Reference Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.8 Tracing Garbage Collectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.8.1 Mark-Sweep Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.8.2 Two-Space Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.8.3 Generational and Concurrent Collectors . . . . . . . . . . . . . . 100 4.9 Summary of Automatic Memory Management . . . . . . . . . . . . . . . . . 104 4.10 Node Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.11 Memory Management and Language Design . . . . . . . . . . . . . . . . . . 105 4.12 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5 Scopes, Functions, and Parameter Passing . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.1 Scope Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.1.1 Global Scoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.1.2 Local Variables only . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.1.3 Block Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.1.4 Nested Function Declarations . . . . . . . . . . . . . . . . . . . . . . . . 118 5.1.5 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.1.6 Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.1.7 Parameter-Passing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.2 Implementing Functions and Function Calls . . . . . . . . . . . . . . . . . . . 124 5.2.1 Summary of Implementing Function Calls . . . . . . . . . . . 124 5.2.2 C-Style Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.2.3 Nested Function Declarations . . . . . . . . . . . . . . . . . . . . . . . . 125 5.3 Functions as Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 5.4 First-Class Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.5 Functional Programming Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.5.1 Impure Functional Languages . . . . . . . . . . . . . . . . . . . . . . . 130 5.5.2 Defunctionalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.5.3 Pure Functional Languages . . . . . . . . . . . . . . . . . . . . . . . . . . 133 5.5.4 Lazy Functional Languages . . . . . . . . . . . . . . . . . . . . . . . . . . 134 5.5.5 Strictness Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 5.6 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 5.6.1 Tagged Return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 5.6.2 Stack Unwinding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 5.6.3 Using a Handler Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 5.7 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

xvi Contents 6 Control Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 6.1 Jumps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 6.2 Structured Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 6.2.1 Conditionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 6.2.2 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 6.2.3 Whole-Collection Operations . . . . . . . . . . . . . . . . . . . . . . . . 155 6.2.4 Break and Continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 6.2.5 Structured Versus Unstructured Control . . . . . . . . . . . . . . 158 6.3 Exceptions and Continuations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 6.3.1 Continuations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6.4 Function Calls as Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 6.5 Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 6.5.1 Coroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 6.5.2 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 6.5.3 Message Passing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 7 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 7.1 Checking Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 7.2 Type Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 7.3 Atomic and Composite Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 7.3.1 Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 7.3.2 Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 7.3.3 Boolean Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 7.3.4 Enumerated Types and Symbols . . . . . . . . . . . . . . . . . . . . . 183 7.3.5 Product Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 7.3.6 Records and Structs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 7.3.7 Collection Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 7.3.8 Union and Sum Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 7.3.9 Function Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 7.3.10 Recursive Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 7.3.11 Named Types and Type Equivalence . . . . . . . . . . . . . . . . . 196 7.4 Using Types to Restrict Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 7.4.1 Information-Flow Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 7.4.2 Using Types to Keep Track of Life Times of Data . . . 200 7.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 8 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 8.1 Ad Hoc Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 8.1.1 Overloading in Dynamically Typed Languages . . . . . . . 208 8.2 Interface Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

Contents xvii 8.3 Subtype Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 8.3.1 Functions and Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 8.3.2 Conditional Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 8.4 Parametric Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 8.4.1 Uniform Parametric Polymorphism . . . . . . . . . . . . . . . . . . 216 8.4.2 Bounded Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 8.5 Polymorphic Type Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 8.5.1 The Hindley-Milner Algorithm . . . . . . . . . . . . . . . . . . . . . . 221 8.5.2 Structural Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 8.6 Polymorphism in Various Languages . . . . . . . . . . . . . . . . . . . . . . . . . . 227 8.6.1 Standard ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 8.6.2 Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 8.6.3 Haskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 8.7 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 8.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 9 Modularisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 9.1 Simple Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 9.1.1 Specification and Implementation . . . . . . . . . . . . . . . . . . . . 238 9.1.2 Shared Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 9.2 Modules with Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 9.2.1 Abstraction Through Header Files . . . . . . . . . . . . . . . . . . . 240 9.3 Name Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 9.3.1 Nested Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 9.4 Modules and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 9.5 Modules as Parameters/Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 9.6 The ML Module System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 9.7 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 9.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 10 Language Paradigms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 10.1 What Is a Language Paradigm? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 10.1.1 Data Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 10.1.2 Execution Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 10.1.3 Type System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 10.1.4 Scoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 10.1.5 Structuring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 10.1.6 Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 10.2 A Closer Look at Some Paradigms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 10.3 Object-Oriented Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 10.3.1 Classes and Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 10.3.2 Single Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 10.3.3 Multiple Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 10.3.4 Prototype-Based Languages . . . . . . . . . . . . . . . . . . . . . . . . . 257

xviii Contents 10.4 Logic Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 10.4.1 Pure Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 10.4.2 List Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 10.4.3 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 10.4.4 Full Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 10.4.5 Other Logic Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 10.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 10.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 11 Domain-Specific Programming Languages . . . . . . . . . . . . . . . . . . . . . . . . . 275 11.1 GPLs Versus DSLs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 11.2 When Should You (Not) Design a New DSL? . . . . . . . . . . . . . . . . . 277 11.3 How Do You Design a DSL? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 11.4 How Do You Implement a DSL? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 11.4.1 Implementation as Embedded Language . . . . . . . . . . . . . 280 11.4.2 Implementation by Preprocessor . . . . . . . . . . . . . . . . . . . . . 284 11.4.3 Implementation as Compiler/Interpreter Modification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 11.4.4 Implementation as Stand-Alone Language . . . . . . . . . . . 285 11.5 Examples of DSLs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 11.5.1 SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 11.5.2 Bash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 11.5.3 Spreadsheets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 11.5.4 Scratch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 11.5.5 TEX and LaTEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 11.5.6 Graphviz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 11.5.7 OpenSCAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 11.5.8 Troll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 11.5.9 CRL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 11.5.10 Futhark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 11.5.11 Hermes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 11.5.12 Sleigh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 11.6 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 12 Specifying the Semantics of a Programming Language . . . . . . . . . . . . . 301 12.1 Informal Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 12.2 Specification by Reference Implementation . . . . . . . . . . . . . . . . . . . . 302 12.3 Formal Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 12.3.1 Notation for Logic Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 12.3.2 Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 12.3.3 Judgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 12.3.4 Semantic Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

Contents xix 12.4 Type Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 12.5 Operational Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 12.5.1 Operational Semantics for a Functional Language . . . . 310 12.5.2 Relating Type Systems and Operational Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 12.5.3 Operational Semantics for an Imperative Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 12.5.4 Unstructured Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 12.5.5 Nontermination and Nondeterminism . . . . . . . . . . . . . . . . 316 12.6 Static Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 12.7 Languages that Have Formal Semantics . . . . . . . . . . . . . . . . . . . . . . . 319 12.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 12.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 13 Exploring the Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 13.1 Limits of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 13.1.1 When Is a Language Turing Complete? . . . . . . . . . . . . . . 329 13.2 Limits on Program Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 13.3 Languages at the Limit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 13.3.1 Reversible Programming Languages . . . . . . . . . . . . . . . . . 333 13.3.2 Quantum Programming Languages . . . . . . . . . . . . . . . . . . . 339 13.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 13.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

List of Figures Fig. 1.1 A turing machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Fig. 1.2 Transitions in a turing machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Fig. 1.3 Syntax of lambda terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Fig. 1.4 A reduction sequence in the lambda calculus . . . . . . . . . . . . . . . . 5 Fig. 1.5 FORTRAN layout as shown in the 1956 manual . . . . . . . . . . . . . 9 Fig. 1.6 Transpose procedure in ALGOL 60 . . . . . . . . . . . . . . . . . . . . . . . . . 14 Fig. 1.7 Layout of an APL keyboard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Fig. 1.8 Simula classes and objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Fig. 4.1 Operations on a simple free list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Fig. 4.2 Operations on a doubly-linked free list with joining . . . . . . . . . . 86 Fig. 4.3 Pseudocode for mark-sweep collection . . . . . . . . . . . . . . . . . . . . . . 95 Fig. 4.4 Two-space collection of two nodes that point to each other . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Fig. 4.5 Maximal sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Fig. 5.1 Local function declaration in Gnu C . . . . . . . . . . . . . . . . . . . . . . . . 119 Fig. 5.2 Nested function declarations in Gnu C . . . . . . . . . . . . . . . . . . . . . . 125 Fig. 5.3 Adding reference parameters to the functions from Fig. 5.2 and making all functions global . . . . . . . . . . . . . . . 126 Fig. 5.4 Packing local variables into structs . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Fig. 5.5 Function parameters in Gnu C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Fig. 5.6 Closure conversion in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 Fig. 5.7 Nested function declarations in standard ML . . . . . . . . . . . . . . . . 131 Fig. 5.8 Lambda-lifted function declarations in standard ML . . . . . . . . . . 131 Fig. 5.9 Using static links in standard ML . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Fig. 5.10 Functional values in standard ML . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Fig. 5.11 Closure conversion in standard ML . . . . . . . . . . . . . . . . . . . . . . . . . 133 Fig. 5.12 Defunctionalised closure conversion . . . . . . . . . . . . . . . . . . . . . . . . 133 Fig. 5.13 Call-by-name transformation applied to Fig. 5.7 . . . . . . . . . . . . . 135 Fig. 5.14 Call-by-need transformation applied to Fig. 5.7 . . . . . . . . . . . . . . 136 Fig. 5.15 Nested functions for Exercise 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 Fig. 5.16 Functions for Exercise 5.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 xxi